Received-SPF: pass (sog-mx-2.v43.ch3.sourceforge.com: domain of gmx.de
	designates 212.227.17.22 as permitted sender)
	client-ip=212.227.17.22; envelope-from=thomasv1@gmx.de;
	helo=mout.gmx.net; 
Message-ID: <52CB9F5D.1040903@gmx.de>
Date: Tue, 07 Jan 2014 07:31:57 +0100
From: Thomas Voegtlin <thomasv1@gmx.de>
User-Agent: Mozilla/5.0 (X11; Linux x86_64;
	rv:24.0) Gecko/20100101 Thunderbird/24.2.0
MIME-Version: 1.0
To: bitcoin-development@lists.sourceforge.net
References: <52B3A1C8.5000005@monetize.io>
	<52C9A7EE.2050904@gmx.de>	<20140106181324.GB28880@petertodd.org>
	<52CB4885.6090003@monetize.io>
In-Reply-To: <52CB4885.6090003@monetize.io>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 8bit
Subject: Re: [Bitcoin-development] BIP proposal: Authenticated prefix trees
Precedence: list


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?