Merkle Tree
en.wikipedia.org
en.wikipedia.org
In my case, I'd recognized the problem of digital time-stamping, but couldn't come up with a solution, failing to identify the essential role of an observer. The problem is indeed about the efficient use of observers while cryptographically securing the work to be timestamped.
I went to a talk by Stuart Haber on his work with W. Scott Stornetta on digital timestamping, slapped my forehead, and thought of the idea of a Merkle tree to make their approach more efficient. How much information does a client need to save to confirm their time-stamp, after a hash of their document has been merged into an observable event? With a linear chain, one needs all the hashes in the chain. With a tree, one gets a logarithmic speedup.
There were recent stories in the New York Times about how quickly computer science was advancing with the advent of email. Someone could go on vacation for a few days and miss everything. Inspired, I pulled an all-nighter writing up my improvement, emailed it in the morning to the people at the talk, and slept. We discovered that this thing I'd devised was called a Merkle tree. Haber and Stornetta rolled my work into a second paper, which (like their first) was cited by the original Bitcoin whitepaper. My involvement was so slight that online accounts often don't include my name.
There are many mathematicians out there much smarter than me. If I can think of a Merkle tree as an indivisible immediate thought, facing the right problem, Merkle trees are too obvious to deserve a patent.
I feel similarly, at this moment in time. But in 197x I can only imagine they were somewhat less obvious. "Perspective worth 80 IQ points", etc.
[1] https://github.com/opentimestamps/opentimestamps-server/blob...
[2] https://docs.grin.mw/wiki/chain-state/merkle-mountain-range/
I recommend this awesome series of blog posts to learn more about hash-based signatures [2] (Merkle Trees are discussed in the third article).
Finally, a shameless plug of a repo [3] where I implement Lamport and Winternitz's schemes for one-time signatures and Merkle trees for many-times signatures. I make use of the C reference implementation of SHAKE-128, which is currently considered to be the most secure hash algorithm from NIST.
[1]: https://en.wikipedia.org/wiki/Hash-based_cryptography
[2]: https://cryptoservices.github.io/quantum/2015/12/04/one-time...
Hypothetically, this technique could speed-up processing of trees for transactions that occur in real-time (i.e. historical operations filter to the bottom of the tree).
Also, the fact that Merkle Trees are keyed by hash automatically eliminates the only caveat of the splay tree algorithm WRT insertions.
The reason I really like the splay tree algorithm is that it is very friendly to linear storage operations. You only need to write a minimal subtree update to disk each time you make a series of updates (batches being ideal).
Discussion there includes Plan 9's Venti filesystem, which I have always admired as throughly well engineered.