2 ms·

> A skip list structure where each node has multiple hashes/identities would let you skip the last five years of edits and pull down only the individual edits f

• hinkley 3y ago
  Not in crypto, but it’s a linked list structure with a logarithmic number of additional pointers that refer forward (or in the case of a diff algorithm, backward) into the list, to provide closer to log n lookup time. I think they were invented by Bill Pugh, a professor who also had some noteworthiness in Java concurrency fifteen years ago, which is how I heard of them. Wikipedia agrees (W Pugh for William) https://en.wikipedia.org/wiki/Skip_list https://en.wikipedia.org/wiki/Skip_list So the way I see it, you’d overlay the linear tree with one that refers to a single, recent hash, a much older hash (or another meta node of the same degree) and a roll up delta from that older hash, with a new hash that satisfies both. Then every time the number of records double, you add another layer over the previous one.