You are reading content from Scuttlebutt
User has not chosen to be hosted publicly
@aljoscha %AzD3zSWZBw20cHi8/k7EG+NtjgaDbocS7uhrqY3OoKw=.sha256


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-
, 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)...

@aljoscha %vM+JQ+kTzgnodQx5MLx2TmU6G1RwSt7D9H0aznjVgnE=.sha256

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.

User has not chosen to be hosted publicly
Join Scuttlebutt now