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 <mark@monetize.io>) id 1W0hZz-0002nn-4q
	for bitcoin-development@lists.sourceforge.net;
	Wed, 08 Jan 2014 01:05:07 +0000
Received: from mail-yh0-f48.google.com ([209.85.213.48])
	by sog-mx-2.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128)
	(Exim 4.76) id 1W0hZx-000855-Co
	for bitcoin-development@lists.sourceforge.net;
	Wed, 08 Jan 2014 01:05:07 +0000
Received: by mail-yh0-f48.google.com with SMTP id f73so185941yha.35
	for <bitcoin-development@lists.sourceforge.net>;
	Tue, 07 Jan 2014 17:04:59 -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=xKb3bAiP0BKBSexpHTOXR+jnpZW/hzzpkLWyU6K5tx4=;
	b=EzJ6n2TEd8e6xqIKQoC3Y5Lsm9/+/62IVtipumoTBHoS7bI/s6nw3wFNoMzPGLvrn3
	FMD8a6mI+fOWriub9sE1/CqpS5jYvD87H6Zk+OO9ZMeE6+gEBt0TRNgyzjodRSC1UGkT
	z7Z7hqMz20Y//bUFlDF4we4VOwisBgKjbKAZRTCSXJ6JQ344rdK6gGkv85xRSPTQll8X
	4lraPB0wGXkM7aaMgvs2Z3VRGNyXHrm/2iW8Id1MUotwUO1nbTrURlbopfoFMxab3tDj
	DWFBEWNMcfCX7bTG7zN699bo/r2vJXdtFISRdxyYLsmmqwEkYaJ2QSJMlq94KWhiRAsq
	13nQ==
X-Gm-Message-State: ALoCoQlc3SBsEwIyGBSzxmR98G9jAncPQqIFuom6m5Eoty9xlzNrzbUcbaUbocX+snR1Ni0WPSTZ
X-Received: by 10.236.77.231 with SMTP id d67mr64776yhe.113.1389143099625;
	Tue, 07 Jan 2014 17:04:59 -0800 (PST)
Received: from [192.168.127.246] (adsl-71-131-176-215.dsl.sntc01.pacbell.net.
	[71.131.176.215])
	by mx.google.com with ESMTPSA id h66sm26474854yhb.7.2014.01.07.17.04.57
	for <multiple recipients>
	(version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128);
	Tue, 07 Jan 2014 17:04:58 -0800 (PST)
Message-ID: <52CCA43A.9080004@monetize.io>
Date: Tue, 07 Jan 2014 17:04:58 -0800
From: Mark Friedenbach <mark@monetize.io>
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: Thomas Voegtlin <thomasv1@gmx.de>, 
	Bitcoin Dev <bitcoin-development@lists.sourceforge.net>
References: <52B3A1C8.5000005@monetize.io>	<52C9A7EE.2050904@gmx.de>	<20140106181324.GB28880@petertodd.org>	<52CB4885.6090003@monetize.io>
	<52CB9F5D.1040903@gmx.de>
In-Reply-To: <52CB9F5D.1040903@gmx.de>
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.
X-Headers-End: 1W0hZx-000855-Co
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: <bitcoin-development.lists.sourceforge.net>
List-Unsubscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
	<mailto:bitcoin-development-request@lists.sourceforge.net?subject=unsubscribe>
List-Archive: <http://sourceforge.net/mailarchive/forum.php?forum_name=bitcoin-development>
List-Post: <mailto:bitcoin-development@lists.sourceforge.net>
List-Help: <mailto:bitcoin-development-request@lists.sourceforge.net?subject=help>
List-Subscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
	<mailto:bitcoin-development-request@lists.sourceforge.net?subject=subscribe>
X-List-Received-Date: Wed, 08 Jan 2014 01:05:07 -0000

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 01/06/2014 10:31 PM, Thomas Voegtlin wrote:
> 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.

Not really. Just use a suffix to determine the number of bits used in
the final key byte. For example, the string "abc" would have the key

    0x61626308 // "abc\x08"

Dropping the final bit would mean masking it off and having a
different terminating value:

    0x61626207 // "abb\x07"

That way you keep the lexical ordering of keys necessary for database
iteration, and the efficient binary encoding.

> 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?

It is an iterative change, I believe. You might be confusing this idea
with Peter Todd's TXO commitment proposal using MMR trees, which is a
drastic change with its own set of tradeoffs. Just to be clear, here's
what I'm proposing:

1) Restructure the current UTXO index to be a Merkle tree, basically
by splitting coins into individual outputs and adding interior nodes
to the leveldb database.

2) Add hash commitments of this structure to the coinbase.

It's still mapping txid's to unspent outputs, just as before - this
has nothing to do with the script keyed "wallet index." It's just now
nodes can prefix optional proofs to block or transaction messages
which prove by reference to the current best block's hash the spend
status of the inputs of a transaction, or all the inputs of all the
transactions of a block.

If the more expensive proof-updatable hashing is used, then these
proofs can even be composed or "rebased" onto a new block by applying
the contents of an "operational proof" representing the diff between
two blocks / the application of a series of transactions.

This means that a node which does not have access to the UTXO set can
nevertheless receive transactions or entire blocks with prefixed
proofs and check the validity of the transaction with just the
information available (proof + transaction contents).

All that is required after the above soft-fork is a protocol version
update and/or a service bit to indicate the ability to send or receive
proof-prefixed messages. I'd call that an incremental update.

[Aside: adding the wallet index requires storing the entire UTXO set
in duplicated form, indexed this time by scriptPubKey or
H(scriptPubKey), and including proofs of this structure as well. It is
unlikely that any soft-fork would occur forcing consensus over the
wallet index, but it could be done as a meta-chain or as an index
covering just the contents of the block.]
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.14 (GNU/Linux)
Comment: GPGTools - http://gpgtools.org
Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/

iQIcBAEBAgAGBQJSzKQ2AAoJEAdzVfsmodw4hyoQAJ0f6P3ijZCEw7IPd/RcrmkI
Viv4j17ZyAAcbNUplvjzhr/tIIKYPg51ltvfkp8cGRHgez88QsljzvM8B5n+nbPa
jaaI6eiJ3AU1bR8hWYKtlXFwMvRjyr3ofl8hhTvYptGv9x3/Tr+2FwxIRY0413m6
2h95vItsvBs8v7clqLoBEqx9uyUpsH3+J32V4oGubrNAFXh1oOHi4Ban+TOKYaQV
GHZaIZ3bVAvcMd5riaWSPUPLHwJnxQ8w6SlVRy2UNUPe+9yTuy4n1GW4vk4WHvop
FgZFrM3LBmh1MhlYHRdEUUtwk3mfDuGbfW5UJVMri0Nis1PsXr5VK4qQaMbd/9e6
M2uWKslY9QCnzMajnHen9OwotteAJy2I1KHVcxXb0tFqrvqZ6o/auIe0G4VdKYuI
XfNF3mokX93tiSflmphDba6qgB/W+Y6UD2gG2AeFuMGhFF/Hy62pVC6Zx7PKZ3vL
Kh27rKkO/0FJau2JCQm5xBiQgCnKghqOiHefY3o+l+Y9kJ8fXKWCuwJ0lJ3LxZ2u
8H6sp6Jm9Ct9L90wSn7VmmI5H3bRe8sa7sylH4BR2T6jP3/tKDYTEeNWj+F9FfO1
FxsjYrjAyv1HxYYKd/Y1svEVSsKMv3a2SR9pF36ynBABdFjvx+oEuCyCO4tspFe6
15eA1QoMKvEQe/Ww5kRC
=L9WT
-----END PGP SIGNATURE-----