Author: Alan Reiner 2012-06-19 17:33:31
Published on: 2012-06-19T17:33:31+00:00
In a forum thread, the issue of using a tree-structure with multiple valid configurations for the same set of unspent-TxOuts was raised. If a binary tree is used, it would require replaying the entire history of insertions and deletions in the correct order to get the tree structure and correct root. Using something like a red-black tree, while theoretically well-known, could be subject to implementation errors that could lead to significant portions of the network not agreeing on the correct root. A raw trie structure would solve all the above issues as it has the same configuration no matter how elements are inserted or deleted, and accesses to elements in the tree are constant time. However, space-efficiency is an issue. A PATRICIA tree/trie would be ideal as it also has a completely deterministic structure and is an order-of-magnitude more space-efficient. But it is not a trivial implementation, and satisfactory implementations are hard to find.Andrew Miller proposed that any (acyclic) recursive data structure can be Merkle-ized, simply by adding a hash of the child node alongside each link/pointer. This way, you can verify the data for each node very naturally as you traverse the structure. This technique has been well discussed in the academic literature, and he even made his own implementation, which is available on Github. The rest of the storage burden can be delegated to an untrusted helper server, making it easy for a lite-client to insert and rebalance its tree.
Updated on: 2023-06-06T05:50:32.411287+00:00