From: Thomas Voegtlin <thomasv1@gmx•de>
To: bitcoin-development@lists•sourceforge.net
Subject: Re: [Bitcoin-development] BIP proposal: Authenticated prefix trees
Date: Tue, 07 Jan 2014 07:31:57 +0100 [thread overview]
Message-ID: <52CB9F5D.1040903@gmx.de> (raw)
In-Reply-To: <52CB4885.6090003@monetize.io>
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?
next prev parent reply other threads:[~2014-01-07 6:32 UTC|newest]
Thread overview: 14+ messages / expand[flat|nested] mbox.gz Atom feed top
2013-12-20 1:47 Mark Friedenbach
2013-12-20 6:48 ` Jeremy Spilman
2013-12-20 11:21 ` Mark Friedenbach
2013-12-20 13:17 ` Peter Todd
2013-12-20 18:41 ` Mark Friedenbach
2013-12-20 10:48 ` Peter Todd
[not found] ` <52B425BA.6060304@monetize.io>
2013-12-20 12:47 ` Peter Todd
2013-12-20 19:48 ` Gregory Maxwell
2013-12-20 22:04 ` Mark Friedenbach
2014-01-05 18:43 ` Thomas Voegtlin
2014-01-06 18:13 ` Peter Todd
2014-01-07 0:21 ` Mark Friedenbach
2014-01-07 6:31 ` Thomas Voegtlin [this message]
2014-01-08 1:04 ` Mark Friedenbach
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=52CB9F5D.1040903@gmx.de \
--to=thomasv1@gmx$(echo .)de \
--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