Author: Alan Reiner 2012-06-19 18:30:16
Published on: 2012-06-19T18:30:16+00:00
In a discussion about the best data structure to use for Bitcoin, Alan Reiner suggests that a raw trie would be ideal because it has a deterministic structure and constant time access to elements. However, he notes that space efficiency could be an issue. A PATRICIA tree/trie is also mentioned as a preferable option due to its deterministic structure and increased space-efficiency, but it is not a simple implementation. Mark Friedenbach argues that tries are dependent on the distribution of input data for balancing, and a malicious actor could construct transaction or address hashes to grow some segments of the trie in an unbalanced fashion. However, Reiner clarifies that he was using "unbalanced" to refer to query time and insert/delete time, and explains that if the nodes branch based on the next byte of the key hash, the max depth of the trie is always 32, making it deterministic and history-independent. While disk space could be affected by a malicious actor inducing more branching, access requests would still take only O(1) time.
Updated on: 2023-06-06T05:50:50.307430+00:00