[Bitcoin-development] BIP proposal: Authenticated prefix trees

Peter Todd pete at petertodd.org
Fri Dec 20 12:47:10 UTC 2013

On Fri, Dec 20, 2013 at 03:10:50AM -0800, Mark Friedenbach wrote:
> On 12/20/2013 02:48 AM, Peter Todd wrote:
> > On Thu, Dec 19, 2013 at 05:47:52PM -0800, Mark Friedenbach wrote:
> >> This BIP describes the authenticated prefix tree and its many 
> >> variations in terms of its serialized representation. Additional
> >> BIPs describe the application of authenticated prefix trees to
> >> such applications as committed indices, document time-stamping,
> >> and merged mining.
> > 
> > Could you expand more on how prefix trees could be used for 
> > time-stamping and merged mining?
> The root hash of a prefix tree is placed in the coinbase at a location
> standardized by convention.

Right, last txout in an OP_RETURN like we discussed.

> For document time-stamping, the key can be
> the hash of the document.

Don't you mean the value is the hash of the document and the key is

> For merged mining, the key is the hash of
> the genesis block of the altchain, and the value is the hash of the
> aux-pow (for p2pool, the share hash).

What's the advantage over the direction-based system I proposed before?
Seems to me the code required to validate the proof is significantly
more complex in your scheme.


> In the system I have in mind this adds 43 bytes to the coinbase
> transaction,

By 43 bytes you mean the whole op_return txout right?

> >>>>> dict = AuthTree() dict['Curie'] = VARINT(1898) 
> >>>>> dict('Einstein') = VARINT(1905) dict['Fleming'] =
> >>>>> VARINT(1928) dict['中本'] = VARINT(2009)
> > 
> > I'd be inclined to leave the unicode out of the code examples as
> > many editors and shells still don't copy-and-paste it nicely. Using
> > it in BIP documents themselves is fine and often has advantages re:
> > typesetting, but using it in crypto examples like this just makes
> > it harder to reproduce the results by hand unnecessarily.
> Thanks for the feedback, I rather agree. When I was creating that
> example for some reason I wanted the right branch of the root node to
> be used, which is difficult when only 7-bit ASCII keys are used. But I
> don't think the illustrative point I had in mind ended up being
> particularly relevant, so I'll rework it.

That example is python, so I'd suggest just using escape sequences
myself. You probably also should include the "b" prefix to make the
strings explicitly binary for py3 compatibility, ie dict[b'\xbe\xef']

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 685 bytes
Desc: Digital signature
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20131220/267c3c6c/attachment.sig>

More information about the bitcoin-dev mailing list