From: Andrew Miller <amiller@cs•ucf.edu>
To: bitcoin-development@lists•sourceforge.net
Subject: Re: [Bitcoin-development] Ultimate Blockchain Compression w/ trust-free lite node
Date: Tue, 19 Jun 2012 14:29:45 -0400 [thread overview]
Message-ID: <CAF7tpEzi80MT5Ud46_BgvnLKXrcWhkNZNOiuY7NMnL-z0C0GqA@mail.gmail.com> (raw)
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
next reply other threads:[~2012-06-19 18:29 UTC|newest]
Thread overview: 9+ messages / expand[flat|nested] mbox.gz Atom feed top
2012-06-19 18:29 Andrew Miller [this message]
-- strict thread matches above, loose matches on Subject: below --
2012-06-19 16:46 Andrew Miller
2012-06-19 17:33 ` Alan Reiner
2012-06-19 17:59 ` Gregory Maxwell
2012-06-19 18:12 ` Alan Reiner
2012-06-19 18:18 ` Mark Friedenbach
2012-06-19 18:30 ` Alan Reiner
2012-06-21 21:42 ` Mike Koss
2012-06-21 22:02 ` Gregory Maxwell
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAF7tpEzi80MT5Ud46_BgvnLKXrcWhkNZNOiuY7NMnL-z0C0GqA@mail.gmail.com \
--to=amiller@cs$(echo .)ucf.edu \
--cc=bitcoin-development@lists$(echo .)sourceforge.net \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox