Author: Andrew Miller 2012-06-19 16:46:52
Published on: 2012-06-19T16:46:52+00:00
In a discussion about Merkle trees, Peter Todd suggested discarding vertexes that cause the tree to become unbalanced and setting the depth of imbalance to prevent this from happening. Andrew Miller, however, proposed a simpler solution for balancing binary search trees. He explained that it's important to balance a binary search tree so that the maximum length from the root to a leaf is bounded by O(log N). This can be achieved with algorithms such as AVL trees or Red-Black trees that store balancing metadata at each node, making every operation require a worst-case effort of O(log N). Miller also noted that any (acyclic) recursive data structure can be 'Merkle-ized' by adding a hash of the child node alongside each link/pointer, allowing verification of the data for each node as one traverses the structure. The storage burden can be delegated to an untrusted helper server as long as a lite-client knows the O(1) root hash. A lite-client can then request only the data relevant to the nodes required to insert and rebalance its tree, knowing the hash for each chunk of data in advance of accessing it. After computing the updated root hash, the client can discard the processed data. Miller's technique has been well discussed in the academic literature, and while he is not aware of any existing implementation, he created his own on GitHub as an explanatory aid. Two academic papers [1],[2] are cited by Miller as references.
Updated on: 2023-06-06T05:49:30.802008+00:00