Received-SPF: pass (sog-mx-2.v43.ch3.sourceforge.com: domain of gmail.com
	designates 74.125.82.53 as permitted sender)
	client-ip=74.125.82.53; envelope-from=socrates1024@gmail.com;
	helo=mail-wg0-f53.google.com; 
MIME-Version: 1.0
Sender: socrates1024@gmail.com
Date: Tue, 19 Jun 2012 14:29:45 -0400
Message-ID: <CAF7tpEzi80MT5Ud46_BgvnLKXrcWhkNZNOiuY7NMnL-z0C0GqA@mail.gmail.com>
From: Andrew Miller <amiller@cs.ucf.edu>
To: bitcoin-development@lists.sourceforge.net
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Subject: Re: [Bitcoin-development] Ultimate Blockchain Compression w/
	trust-free lite node
Precedence: list

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. =A0Insert, delete and query times are still O(1).
> However, it is not a trivial implementation. =A0I have occasionally looke=
d
> 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) <=3D 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.

--=20
Andrew Miller