[Bitcoin-development] Ultimate Blockchain Compression w/ trust-free lite node
amiller at cs.ucf.edu
Tue Jun 19 18:29:45 UTC 2012
Alan Reiner wrote:
> A PATRICIA tree/trie would be ideal, in my mind, as it also has a
> completely deterministic structure, and is an order-of-magnitude more
> space-efficient. Insert, delete and query times are still O(1).
> However, it is not a trivial implementation. I have occasionally looked
> for implementations, but not found any that were satisfactory.
PATRICIA Tries (aka Radix trees) have worst-case O(k), where k is the
number of bits in the key. Notice that since we would storing k-bit
hashes, the number of elements must be less than 2^k, or else by
birthday paradox we would have a hash collision! So O(log N) <= O(k).
You're right, though, that such a trie would have the property that
any two trees containing the same data (leaves) will be identical. I
can't think of any reason why this is useful, although I am hoping we
can figure out what is triggering your intuition to desire this! I am
indeed assuming that the tree will be incrementally constructed
according to the canonical (blockchain) ordering of transactions, and
that the balancing rules are agreed on as part of the protocol.
More information about the bitcoin-dev