2 ms·
Many of these systems also don’t have a Merkle tree, they have a Merkle linked list. Which I think contributes a lot to the syncing problem. A skip list structu
by hinkley 3y ago
Many of these systems also don’t have a Merkle tree, they have a Merkle linked list. Which I think contributes a lot to the syncing problem. 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 for the last month.
The “Merkle tree” I worked on before this blockchain nonsense started was a Merkle DAG, representing a mostly linear state flow with some parallel elements.
- r3trohack3r 3y ago> 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 for the last month. Do you have any references or reading material on this pattern? Would love to learn more.
- hinkley 3y agoNot 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.