Jup, the schemes are highly related. The way I think about it is that MMRs, certificate transparency logs and hypercore are essentially doing the same thing in slight variations: entry `n`

has a couple of disjoint trees of descending size in its past (take the binary representation of `n`

, each one-digit at position `k`

corresponds to a tree of size `2^k`

). The mechanism by which you connect those trees is almost an implementation detail. The optimally efficient accountable time-stamping has the earliest occurrence of that pattern I know about.

Bamboo uses the scheme from New Linking Schemes for Digital Time-

Stamping, whereas the analogy you described works even better for the scheme from Time-

Stamping with Binary Linking Schemes (which is exactly the log-2 construction you mentioned). I've been meaning to publish on this for a while, but writing takes so much time (as does teaching)...

I've been meaning to publish on this for a while, [...].

To specify that a bit: if you take the base-2 linking scheme construction but only store data in the leaves, you get a more efficient result than any prior published work. That construction is imo what the "optimally efficient accountable time-stamping" *should* have chosen, but apparently they didn't see it.

That construction is also highly related to a perfect deterministic skip list where the links between layers go into the "wrong" direction compared to a classic skip list: change the links that in the classic construction to always go to the highest possible layer, and you again obtain the base-2 linking scheme with data stored in leaves only.

@7suh Finished the proper write-ups, see %8ZxNBht...