Received-SPF: pass (sog-mx-1.v43.ch3.sourceforge.com: domain of petertodd.org
	designates 62.13.148.112 as permitted sender)
	client-ip=62.13.148.112; envelope-from=pete@petertodd.org;
	helo=outmail148112.authsmtp.co.uk; 
Date: Fri, 20 Dec 2013 07:47:10 -0500
From: Peter Todd <pete@petertodd.org>
To: Mark Friedenbach <mark@monetize.io>,
	bitcoin-development@lists.sourceforge.net
Message-ID: <20131220124710.GB21148@savin>
References: <52B3A1C8.5000005@monetize.io> <20131220104826.GC23836@savin>
	<52B425BA.6060304@monetize.io>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
	protocol="application/pgp-signature"; boundary="i0/AhcQY5QxfSsSZ"
Content-Disposition: inline
In-Reply-To: <52B425BA.6060304@monetize.io>
User-Agent: Mutt/1.5.21 (2010-09-15)
Subject: Re: [Bitcoin-development] BIP proposal: Authenticated prefix trees
Precedence: list


--i0/AhcQY5QxfSsSZ
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

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=20
> >> 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.
> >=20
> > Could you expand more on how prefix trees could be used for=20
> > time-stamping and merged mining?
>=20
> 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
irrelevant?

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

http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg03=
149.html

> 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 =3D AuthTree() dict['Curie'] =3D VARINT(1898)=20
> >>>>> dict('Einstein') =3D VARINT(1905) dict['Fleming'] =3D
> >>>>> VARINT(1928) dict['=E4=B8=AD=E6=9C=AC'] =3D VARINT(2009)
> >=20
> > 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.
>=20
> 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']

--=20
'peter'[:-1]@petertodd.org
000000000000000216e3750a9ad9584395352d728a3c543844eab3bfc9ce1073

--i0/AhcQY5QxfSsSZ
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.12 (GNU/Linux)

iQGrBAEBCACVBQJStDxNXhSAAAAAABUAQGJsb2NraGFzaEBiaXRjb2luLm9yZzAw
MDAwMDAwMDAwMDAwMDI4ZmQwNzdmYjFlMzNlOTQyZTNlODc1YWEyOWNlYzEzNGZl
ZDg5ZDY1MDI0MmM1NzcvFIAAAAAAFQARcGthLWFkZHJlc3NAZ251cGcub3JncGV0
ZUBwZXRlcnRvZC5vcmcACgkQJIFAPaXwkfv0EggApL/gMCjA29AmWebyN57xEF4I
uUb6ErFLAgQw9Z3gFwWsM9dFmj6EoTXOcPbAQm5c6wHX8lYqXD9oC8b9bx9z0F9f
MIabnMfTUhoRDSglErL3rCenTWcmT3gaBWfFCZlepOC3KWyJneNrX/8pyamgTtSD
UYHb1nx8qBIRvYJwxQ8EgS90XFEAeeKKm50ubYX6NHfTXmieLsmvQNTDsMb2DYO8
TdKD1CS4WTQTnE+v1ftRCAiEaqfDYdXZqVBJ2glQ8s8+RAGziPvRP7nFroS9uQtH
A2bLoPT0woop9T+NYSbqbm+zHmAd0NdW+t/ZiIWTr/KOm2h35DkZ3FXTguDGJg==
=r9/V
-----END PGP SIGNATURE-----

--i0/AhcQY5QxfSsSZ--