Posts

Showing posts from November, 2018

Storing Arbitrary-Length Data in a Merkle Tree

Image
A hash tree, or a Merkle tree, is a data structure that allows you to take a lot of information and summarize it together in such a way that you (the "prover") can succinctly prove to somebody else (the "skeptic") that certain data is included.
Background Here is a typical Merkle-tree implementation:



Arrows represent inclusion in a hash. For example, A = hash(B, C). Hash() is customarily sha256().

Facts F1, F2, F3 and F4 are private. Or, a lighter requirement, there are just so many facts that you cannot be bothered to explain them to somebody else. You will publish root node A, the hash root. And this is proof to the world that this entire tree is encoded in A (if you choose to expose the tree). This rests on the worldwide assumption that hashes don't collide. If somebody is interested to confirm that F3 is included in A then you must share with them F4 and B so that they can recalculate A and confirm it matches the A you published.

Here is how that proof look…