Received: from sog-mx-2.v43.ch3.sourceforge.com ([172.29.43.192] helo=mx.sourceforge.net) by sfs-ml-3.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1W0QCr-0003Np-0e for bitcoin-development@lists.sourceforge.net; Tue, 07 Jan 2014 06:32:05 +0000 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; Received: from mout.gmx.net ([212.227.17.22]) by sog-mx-2.v43.ch3.sourceforge.com with esmtps (TLSv1:AES128-SHA:128) (Exim 4.76) id 1W0QCp-0001LW-Mr for bitcoin-development@lists.sourceforge.net; Tue, 07 Jan 2014 06:32:04 +0000 Received: from [192.168.1.27] ([86.73.30.122]) by mail.gmx.com (mrgmx103) with ESMTPSA (Nemesis) id 0LymjL-1VN2ZG0Cmd-0168OF for ; Tue, 07 Jan 2014 07:31:57 +0100 Message-ID: <52CB9F5D.1040903@gmx.de> Date: Tue, 07 Jan 2014 07:31:57 +0100 From: Thomas Voegtlin 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 X-Provags-ID: V03:K0:9XztzpSpO9x4FoZYJ5LMc6VwrwmdxYJKYQB9nd7OU7Zn6v1IocP /FzdzXpr1NLEqvnF2AORjEuJhvLMBh8SoaiYaFmbfKXn6/qoA0+MOImQ+hmhkDrg9FGkK5I ePlXWXvf2foJRkpEzzEI1FdEf1heBd6qBEWG/qXGPmjQA27e8m0L6Ers9lxHeNgiUrRqnEE V8mmx8Va8reXcO6v9+mSg== X-Spam-Score: -1.2 (-) X-Spam-Report: Spam Filtering performed by mx.sourceforge.net. See http://spamassassin.org/tag/ for more details. -0.0 RCVD_IN_DNSWL_NONE RBL: Sender listed at http://www.dnswl.org/, no trust [212.227.17.22 listed in list.dnswl.org] -1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for sender-domain 0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider (thomasv1[at]gmx.de) -0.0 SPF_PASS SPF: sender matches SPF record 0.2 FREEMAIL_ENVFROM_END_DIGIT Envelope-from freemail username ends in digit (thomasv1[at]gmx.de) X-Headers-End: 1W0QCp-0001LW-Mr Subject: Re: [Bitcoin-development] BIP proposal: Authenticated prefix trees X-BeenThere: bitcoin-development@lists.sourceforge.net X-Mailman-Version: 2.1.9 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 07 Jan 2014 06:32:05 -0000 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?