From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from sog-mx-2.v43.ch3.sourceforge.com ([172.29.43.192] helo=mx.sourceforge.net) by sfs-ml-1.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1W0KQI-00023T-SK for bitcoin-development@lists.sourceforge.net; Tue, 07 Jan 2014 00:21:34 +0000 Received: from mail-pd0-f169.google.com ([209.85.192.169]) by sog-mx-2.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1W0KQH-0000is-H9 for bitcoin-development@lists.sourceforge.net; Tue, 07 Jan 2014 00:21:34 +0000 Received: by mail-pd0-f169.google.com with SMTP id v10so18830856pde.0 for ; Mon, 06 Jan 2014 16:21:27 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:message-id:date:from:organization:user-agent :mime-version:to:subject:references:in-reply-to:content-type :content-transfer-encoding; bh=yNnBBWU/bipB06ppClz58BxSjXQziPZk3BysZHT7sAk=; b=DzccAtl7ZqqiZLaKQ6kaLPYE2yFo/NQNifUY+2sNQX3wQC5L3zYGRQaXuKffCHnqlu wTWtPNjjItgPg9dnLvhQlenXovL6OB0d1wBBgqEN5G/wqi6UUfPqqp3ZKLzT/VHst3Ux ONbBbvYf1rvKUOE+M7ZOD9b24cf3/PY6MEna5ZYgTUURzI2Sc22JdkepNYuAmYcLd2jo sP29cpZlUeqp3qNT2J9tG4zY6dTJp4hy++SfK0ejfysOciinVr740WbKHuH78pWZlXmc jHFmZzbhcR/sL+Ig32eVjbQws7hSCH1eWUzBHS36lnasaQNMDZVBPMHEUxhRcqnvaW7l j+zw== X-Gm-Message-State: ALoCoQnGYbxJEwmJN3yFacs1AQ6dEDH/zQ7FwMHkDRgxw5xR82uSWHKBD4jfsR4wCk7SD4h/sTxq X-Received: by 10.68.4.194 with SMTP id m2mr1310518pbm.19.1389054087455; Mon, 06 Jan 2014 16:21:27 -0800 (PST) Received: from [192.168.127.242] (50-0-36-25.dsl.dynamic.sonic.net. [50.0.36.25]) by mx.google.com with ESMTPSA id qf7sm172340590pac.14.2014.01.06.16.21.25 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Mon, 06 Jan 2014 16:21:26 -0800 (PST) Message-ID: <52CB4885.6090003@monetize.io> Date: Mon, 06 Jan 2014 16:21:25 -0800 From: Mark Friedenbach Organization: Monetize.io Inc. 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> In-Reply-To: <20140106181324.GB28880@petertodd.org> X-Enigmail-Version: 1.6 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-Spam-Score: 0.0 (/) 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 [209.85.192.169 listed in list.dnswl.org] X-Headers-End: 1W0KQH-0000is-H9 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 00:21:35 -0000 -----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. 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. The "disadvantage" is that performance is closely tied to key length, making H(scriptPubKey) the much more desirable option. I'm sure you see that as an advantage, however :) > Also have you considered creating per-block indexes of all > scriptPubKeys, spent or unspent, queryable via the same partial > prefix method? This would be quite easy to do, separate from the UTXO structure but using the same trie format. -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.14 (GNU/Linux) Comment: GPGTools - http://gpgtools.org Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/ iQIcBAEBAgAGBQJSy0iFAAoJEAdzVfsmodw434MQAIA/fDYT7SfMtfLEgDQKhXCn slRqFEx/HXjvgHHSYnbr9V+8LrGzNvT2ImebbV9ge8VlziAFNGIUq2EYhFs4kHWu GVm9aL8Jj/27SvM0tRwr9n2XIifKOh2sVINAjbv+UwPv/O+cULU95/b53DEF6aqI OWxioOR50TPe4t9AevAGVypNLm1DsyDdymhO9xyBN92xGTNj5QKL5hHG3kcsLIl1 7KaxO0w4UC2sdSGj9FeyH1b0zYg8FlzjJHc1CUshHwUwyYo8LRJtRypL5lrayERg Er/kIGEDovcenNBW8G79l+8VKPfB/lMTssT2pDiQL+1e1fg46CIQxHSyap2JSFTE jgleRk/+1NK/ZjOQ8dEBPZK3TE1WY3qlm/ekjG/8W5kXqcxzFBoAkeBNXuJ/8UMi mKe+DTmbp0xnvLO1p+hpugXKfrQSpcFL+ZvJHlFS1lz7O1N3WvuDCNP9El+L6ueM nFzjr1NTnX0z4vYtscI7qBKVqUrB7Z84c3O/lSYpw4Jilxl4trzV4cn7+AF7KWGM ktR9JJeIoNcJ2Zx4EpRp6OSwhtLkWZyLpPnidQ2p6ev2ytXpTpGsW/i5XS2w57UD 2IG5E0Q7Xzvd58lI/YollWQcagVOZdyzYXa+wVZoFQ6gLF47andpUmtUJOhI7gxv T/rWhPhkTMUn8TdvUcV/ =N9zM -----END PGP SIGNATURE-----