|
November 13, 2017, 11:48:45 AM |
|
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
This is an interesting thought that came to mind yesterday while sitting in the bus for multiple hours.
Merkle Chains
You all know about the concept of Merkle chains, where new information that is published refers back to earlier snippets of information, ensuring that:
- New information depends on the old information. - Thus, we create a temporal ordering of information snippets. - This also means that the old information cannot be changed anymore without invalidating all information that (directly or indirectly) referred to it. (And if re-creating an information snippet is expensive, this means that the further in the past, the more expensive it would be alter a snippet).
Of course, this is one of the core concepts that is used in the Blockchain, with each block referring to the previous block.
[em]I make te separation here between a Merkle Tree, where tree elements contain a 'summary hash' of their children (allowing you to check tree consistency without requiring access to the whole tree's data), and a Merkle Chain, where every element refers back to the previous one. Obviously, a Merkle Chain is(/can be modeled as) a Merkle Tree where the 'root' element is moved to a subtree every time with the latest element becoming the new root. [/em]
Commit-Reveal
On the other hand, we have the commit-reveal protocol that now is used in some betting systems (like provably fair casinos), decentralized random number generators, decentralized voting systems and schelling-point-based oracle systems.
Here, every node first has some time to publicize a hash (called the commit) of the value they will reveal later. After a party has received enough commits (or after a certain timeout has passed), it will publish its value. Everyone can then check if the published value matches with the commit.
This simple protocol ensures that a node cannot 'change their mind' after seeing the result of (one or multiple) other nodes.
The combination
Interestingly, these two techniques are basically each others inverses: When creating a Merkle chain, you first publish some information, followed by some information that refers back to it using a hash. When using the commit-reveal method, you first publish a hash, and later publish some information that the hash turns out to refer to.
Besides this realization, something interesting happens when you enforce that a snippet of data should both refer back to a previous piece of information, as well as referring forward using a hash to the next snippet of information:
- These hashes can only be predicted when all information (of which the currently-sent snippet is a part) is known prior to sending the first snippet. - To do it properly, the first information snippet and the last information snippet need to refer to each-other. You're now creating a basically closed immutable loop of information (that can only be replaced as a whole).
Maybe there are other interesting properties as well.
I am not sure if there are practical applications for this knowledge, but I thought it was interesting enough to share. Maybe it sparks some other idea in someone else's mind :-).
~Wiebe-Marten -----BEGIN PGP SIGNATURE----- Version: GnuPG v1
iQIcBAEBAgAGBQJaCYaNAAoJEBfPRUP+Bdzsdq0P/1Cz1s6I6lRtO/DuKx8iU6Qs lDD0R8cbqZX+gTlhnkYMp+0M32qrsgEKQob+oNMfH2lJsV2l9Vr6YlPQO3T4lEpT G3U0+TRGPeaqvJPSx2BIM0/qHgEKdrK9fsB6mBGFswjsK+sA+KVQIfRiBjHmw8cx u8plAdnw/lDkLWKbtav3qr6m2oXtV2vl8qmnneF4aXPjogjvf+MvE3Am6ZEVd4fS RQqoHmIGPRDWFaigcHGQuf0aJJ+lvSaA9Cgx+M33TujNu4JoaQGsLdJrH96YUwSQ CH1r5rIaASTCyMqQbnI9xO/ZWt6UFeorz3yBO9OJNLPFFcrkNCLV+oG9RICqDP+C 2PjQGszf0OmpN3BEMksRwxElA1i+jG+yXlEAUpsT/vJsAcHrEUhFON232a+1ImEx 0Id7el+Sb070ztarEe8UpXpWQHuEiHzhx6c2Ull4J6BC+glvfoLbL/VRik8Iz2/+ quzeN/eVqzu9TRPYxJDZn0XLuMz/FjwhAgvj0ncWhYMv5Vi1WxiCzyN5MPTmPYqH +DmRq0nhdZSmL1vGF89EVwNWMF+dryJg+kuckneCvSTZruAkBJ49OysZ/u1yT+RA nfVSR2EfNSScS7Lh7PckZYdRFccfcCUMcYcoopVoJlsYgpW9pm5PVUTxP6EJjS+w uWxLWWP/5BjFQbur4gE6 =OaM0 -----END PGP SIGNATURE-----
|