Author: Mike Koss 2012-06-21 21:42:58
Published on: 2012-06-21T21:42:58+00:00
The discussion begins with the question of whether it makes sense to adopt a more complex data structure than the Merkle tree for including in the Bitcoin protocol. The Merkle tree already allows replacing any unneeded transaction just by its hash, and possibly a whole subtree if the unneeded transaction falls within a common node of the Merkle tree. If a lite client only cares to retain a single transaction in a block, it will only need O(log2(T)) Merkle hashes plus the transaction it cares about.Then, there is a debate on whether a raw trie structure or a PATRICIA tree/trie would be ideal for this purpose. A trie has the same configuration no matter how elements are inserted or deleted, and accesses to elements in the tree are constant time - O(1). However, a malicious actor could construct transaction or address hashes in such a way as to grow some segment of the trie in an unbalanced fashion. Self-balancing search trees (KVL, RB, 2-3-4, whatever) don't suffer from this problem, and they can't be exploited under particular timing-sensitive circumstances.In conclusion, while a trie has deterministic (history-independent) and cannot become unbalanced in terms of access time, disk space can be affected by a malicious actor. The more branching he can induce, the more branch nodes that are created to support branches with only one leaf.
Updated on: 2023-06-06T05:51:29.815346+00:00