Topic: Fun stuff with merkle-chaining vs. commit-reveal (Read 404 times)

remind me of sealed sets article from Peter Todd, where merkle trees (I think he called merkle mountains, something to do with his hikings) is used to validate data backward and each closing of set has commit that reveals the next opening, ensuring integrity backward and forward.

I am inclined to think that there are many practical applications. One application would be high-speed, high-resolution, secure digital timestamping. If you define a formal protocol (e.g. specified by a finite-state machine), you can build a distributed network that processes timestamp requests in a deterministic way. The only catch is that there is no built-in way to measure real-world time (so to order timestamp requests). One way to solve this would be to just cheat off the blockchain and use it as a secure timestamping service. The downside of this is that you are back to 10 minute time-resolution. A self-contained solution would be to use proof-of-work not as a mining system but, rather, as a self-contained time-service within the network. So, the network proceeds along its protocol FSM until it reaches a PoW sync-point. At this point, everyone just waits until a PoW is mined before continuing. The network-wide "nonce" is reset using this PoW so that all old transactions can be instantly recognized as old by checking their nonce. In this way, the network does not need to track its past history yet it can remain secure. The protocol would be able to adjust its PoW but there is no reason that PoW mining would become extraordinarily intense because its only purpose is to serialize the network to keep everyone on roughly the same clock. If you do it right, you can also dynamically partition the network so that timestamp requests can be processed in parallel and aggregated together. Basically, by generating a PoW (separate from the syncing PoW), you can use this as a "partitioning token" so that you can be trusted to generate a timestamp without the entire network having to validate it. This prevents Sybil attacks, while allowing the network to scale horizontally. You could incentivize the whole system by using a cryptocurrency to apportion user fees in some reasonable way to everyone who contributes to processing the network. LN would be perfect for arranging these payments. The real-world applications are literally limitless. Unlike the absurdity of corporations using "blockchain technology" internally, a timestamping service built in this way would make sense for corporations to use internally because it shifts the burden of securely ordering/syncing events onto the timestamping-service (which specializes in this). If the network is designed to achieve sufficient horizontal scaling, it could even handle use-cases like secure, high-resolution timestamping of events in an MMO game. This would alleviate a lot of headaches facing game designers.

-----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-----