[Bitcoin-development] BIP proposal: Authenticated prefix trees

Mark Friedenbach mark at monetize.io
Fri Dec 20 11:21:38 UTC 2013

Hash: SHA1

Hi Jeremy, Let's give a preview of the application-oriented BIPs I

Stateless validation and mining involves prefixing transaction and
block messages with proofs of their UTxO state changes. These are the
"operational proofs" I describe in the draft, and they work on prefix
trees whose root hashes committed to the coinbase in a soft-fork
upgrade of the validation rules.

"Ultimate blockchain compression" involves consensus over an address
index, which can be queried over the p2p network by lightweight nodes.
The structure of the index is an authenticated prefix tree, and the
results of such a query is an an inclusion proof.

Document time-stamping and this new method of merged mining use the
same structure: a prefix tree whose root hash value is committed to a
pruneable output of the coinbase transaction. Document timestamp
proofs and merged mining proof-of-works are inclusion proofs over this

I hope that shows how the BIP directly affects interoperability of the
bitcoin protocol and clients which use these applications. I released
this BIP first to get some feedback on the structure itself, which
will be used by all of the application-specific BIPs which follow.

Stepping back and speaking generically, the purpose of a BIP as I see
it is to standardize details which affect interoperability between
clients. In fact, at a cursory glance only about half of the BIPs deal
with protocol issues directly - the rest deal with local /
user-interface issues like key derivation or JSON-RPC APIs. Even if
none of the applications involved protocol changes, I still think BIPs
like this would be of value in that they serve to standardize things
which are or will seek to become commonly used and widely implemented.


On 12/19/2013 10:48 PM, Jeremy Spilman wrote:
> Wow there's a lot here to think about. I'm pretty sure I haven't
> grasped the full implications yet.
> I see it proposes to also introduce additional BIPs describing the
> use of the data stucture for stateless validation & mining, the UBC
> address index for "SPV+" operating modes, document timestamping and
> merged mining.
> Can the BIP stand alone as a BIP without some specific changes to
> the protocol or end-user accessible features defined within it? It
> seems like an extremely useful data stucture, but as I understand
> it the purpose of BIPS is defining interoperability points, not
> implementation details?
> Unless the tree itself is becoming part of the protocol, seems like
> its spec, test vectors, and reference implementation can live
> elsewhere, but I would love to read about BIPS which use this tree
> to accomplish some amazing scalability or security benefits.
Version: GnuPG v1.4.14 (GNU/Linux)
Comment: GPGTools - http://gpgtools.org
Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/


More information about the bitcoin-dev mailing list