Le 07/01/2014 01:21, Mark Friedenbach a écrit : > -----BEGIN PGP SIGNED MESSAGE----- > Hash: SHA1 > > On 01/06/2014 10:13 AM, Peter Todd wrote: >> On Sun, Jan 05, 2014 at 07:43:58PM +0100, Thomas Voegtlin wrote: >>> I have written a Python-levelDB implementation of this UTXO >>> hashtree, which is currently being tested, and will be added to >>> Electrum servers. >> Along the lines of my recent post on blockchain data: >> >> Is it going to be possible to do partial prefix queries on that >> tree? > There's really two tree structures being talked about here. Correct me > if I'm wrong Thomas, but last time I looked at your code it was still > implementing a 256-way PATRICIA trie, correct? This structure lends > itself to indexing either scriptPubKey or H(scriptPubKey) with > approximately the same performance characteristics, and in the > "Ultimate blockchain compression" thread there is much debate about > which to use.
You are right. The 256-way branching follows from the fact that the tree was implemented using a key-value database operating with byte strings (leveldb). With this implementation constraint, a different branching would probably be possible but wasteful. My recent code creates one leaf per unspent, and uses 56-byte keys built as: H(scriptPubKey) + txid + txpos (This is not pushed yet, it needs cleanup. Previous code created one leaf per address) Partial prefix queries are possible with database iterators. > In the process of experimentation I've since moved from a 256-way > PATRICIA trie to a bitwise, non-level-compressed trie structure - what > I call proof-updatable trees in the BIP. These have the advantage of > allowing stateless application of one proof to another, and as > consequence enable mining & mempool operations without access to the > UTXO set, so long as proofs are initially provided in the transaction > & block wire format. I see the advantage of doing that, but this looks really far-fetched.. My understanding is that it would require a complete change in the way clients and miners work. Could such a change be brought iteratively? ------------------------------------------------------------------------------ Rapidly troubleshoot problems before they affect your business. Most IT organizations don't have a clear picture of how application performance affects their revenue. With AppDynamics, you get 100% visibility into your Java,.NET, & PHP application. Start your 15-day FREE TRIAL of AppDynamics Pro! http://pubads.g.doubleclick.net/gampad/clk?id=84349831&iu=/4140/ostg.clktrk _______________________________________________ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
