I've finished two papers on append-only logs, to be submitted to Usenix security 2024.

https://arxiv.org/abs/2308.13836

The first argues that "append-only log" is a misleading name, proposes "prefix authentication" as an alternative, and gives a detailed summary and recontextualization of prior work.

https://arxiv.org/abs/2308.15058

The second proposes a new way of using backlinks for verification that outperforms hypercore, bamboo, and certificate transparency logs.

@mix.desktop I think you were the one to come up with the vertebra and spine terminology some years ago. Let's see if those can make it into academia =)

Can I get attribution on that @aljoscha, it would be exciting to have bragging rights in another sphere (joking/ not joking)

I said to @cft I'd be interested in collaborations on papers as something to explore in the future.

Beautiful diagram btw... look fwd to reading these papers

@7suh Thank you for the links, I hadn't really looked beyond the Todd one before.

As far as I can tell, MMRs are identical to the certificate transparency scheme (RFC 9162, formerly RFC 6962), and the FlyClient paper seems to agree:

The idea had been proposed before in the context of certificate transparency logs [38] to show that any particular version of an append-only log is a superset of any previous version.

So my second paper is not doing the same a MMRs, in fact it outperforms MMRs. Or are you saying I should present MMRs as the progenitor and CT logs as the reinvention? This page states that google started developing CT in 2011, they had running logs and an RFC in 2013. Given the whole complexity of the rfc (MMDs etc), chances are they had the merkle tree construction a lot earlier. So I'd be unconfortable to present one as definitely preceding the other.

But I'm definitely going to cite MMRs, probably via the FlyClient paper.

Reading these also pointed me to vector commitments, which will make it into the related work section of the first paper.

@7suh

Think the following does justice to Todd and the brave wizard hackers?

Concurrently to the design of certificate transparency,
Todd [48] proposed an identical approach under the moniker
of merkle mountain ranges (MMRs). This work laid the foun-
dation for the open timestamps standard [37], and is used in
the anonymously designed MimbleWimble [20] [17] and its
light client design FlyClient [9].

@misc{todd2012,
  title = {Merkle Mountain Ranges},
  author={Peter Todd},
  howpublished = {\url{https://github.com/opentimestamps/opentimestamps-server/blob/4f5a3c6ae56be766cc6d83e31fb5341f78ecad7c/doc/merkle-mountain-range.md}},
  note = {Accessed: 2023-09-20}
}

@inproceedings{bunz2020flyclient,
  title={Flyclient: Super-light clients for cryptocurrencies},
  author={B{\"u}nz, Benedikt and Kiffer, Lucianna and Luu, Loi and Zamani, Mahdi},
  booktitle={2020 IEEE Symposium on Security and Privacy (SP)},
  pages={928--946},
  year={2020},
  organization={IEEE},
  note={\url{https://ieeexplore.ieee.org/document/9152680}}
}

@misc{opentimestamps,
  title = {Open Timestamps},
  author={open timestamps},
  howpublished = {\url{https://opentimestamps.org/}},
  note = {Accessed: 2023-09-20}
}

@misc{mimblewimble,
  title = {MimbleWimble},
  author={Tom Elvis Jedusor},
  howpublished = {\url{https://github.com/mimblewimble/docs/wiki/A-Brief-History-of-MimbleWimble-White-Paper}},
  note = {Accessed: 2023-09-20}
}

@inproceedings{fuchsbauer2019aggregate,
  title={Aggregate cash systems: A cryptographic investigation of mimblewimble},
  author={Fuchsbauer, Georg and Orr{\`u}, Michele and Seurin, Yannick},
  booktitle={Advances in Cryptology--EUROCRYPT 2019: 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19--23, 2019, Proceedings, Part I 38},
  pages={657--689},
  year={2019},
  organization={Springer},
  note={\url{https://eprint.iacr.org/2018/1039.pdf}}
}