[Bitcoin-development] Ultimate Blockchain Compression w/ trust-free lite node

[Andrew Miller]

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.

-- 
Andrew Miller