[Bitcoin-development] BIP proposal: Authenticated prefix trees

[Mark Friedenbach]

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

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

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
tree.

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.

Cheers,
Mark

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.
> 
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.14 (GNU/Linux)
Comment: GPGTools - http://gpgtools.org
Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/

iQIcBAEBAgAGBQJStChCAAoJEAdzVfsmodw42DcQAIlgkukh5K/XYloIiT5pgaHS
xCZXtOvxpNUep8x35rvEO1ePjvPvUkbUE2jRw2se1rSMkhzw3PpHHtXV/gIOGqUe
WVKeeIM5pZX56sEcEdUQ1pTwB2rmtSNeyCuHl8fLatk8eLhcAHcpv/7esLuAjWCr
EE840s8+q3ltuzKi3nqxK84bwIohgSMKhncfonNp5lMAtug8Itqopq3DPDoxwiK/
qUwSz5UCEMH6oNHnywzhKGUhBErqo4q8IgAKcZYBZZ9n4BRjf4ngoCw9n5wCef8v
tyTvwrg0nSQTQa67cg7RCsY7SisrI9gaMvCYTSvEMKdw9X0aqAX1p0yZpTbV+dIr
Q2ZT6gJmg2sD22zKY1/58oq+PiNO+nRS81OG2znZofsIfhOVW0bIZAQ8+zZtFW40
vXxMuHCNieCK8e7f9A6LLv/Zz7rmNxdQ6cHBEL1nIs1Y4d1FpHJVI2LHi54QmVXf
C5PKF/e7K2eD3LZMNxS818rZaiJJ7qmpjS3rkG2owHyJHEhBJIlkYXfI1YCraT+b
R5AzAh2Oz0Nyb5ChP2VSaecJNjGvRMo7Z6HCytmgAGOEcDDZkxSv0kkprbvchqXx
XziFgA4iSajBKYWPiPLGMADfMPT6zd4fhDjyaN8+LPO3d3ZK1VwmQDLRQ3DxfeIP
RgchHR/pS77XI7hCFwtN
=ao17
-----END PGP SIGNATURE-----