From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from sog-mx-1.v43.ch3.sourceforge.com ([172.29.43.191] helo=mx.sourceforge.net) by sfs-ml-2.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1VtzUC-0003xo-Ni for bitcoin-development@lists.sourceforge.net; Fri, 20 Dec 2013 12:47:24 +0000 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; Received: from outmail148112.authsmtp.co.uk ([62.13.148.112]) by sog-mx-1.v43.ch3.sourceforge.com with esmtp (Exim 4.76) id 1VtzUB-0005VH-5U for bitcoin-development@lists.sourceforge.net; Fri, 20 Dec 2013 12:47:24 +0000 Received: from mail-c235.authsmtp.com (mail-c235.authsmtp.com [62.13.128.235]) by punt17.authsmtp.com (8.14.2/8.14.2/) with ESMTP id rBKClHJj057595; Fri, 20 Dec 2013 12:47:17 GMT Received: from savin (76-10-178-109.dsl.teksavvy.com [76.10.178.109]) (authenticated bits=128) by mail.authsmtp.com (8.14.2/8.14.2/) with ESMTP id rBKClAfs072165 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO); Fri, 20 Dec 2013 12:47:12 GMT Date: Fri, 20 Dec 2013 07:47:10 -0500 From: Peter Todd To: Mark Friedenbach , 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) X-Server-Quench: d956f7e0-6974-11e3-b802-002590a15da7 X-AuthReport-Spam: If SPAM / abuse - report it at: http://www.authsmtp.com/abuse X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVKBZePFsRUQkR aAdMdAIUHFAXAgsB AmUbWlZeVFp7WGA7 bAxPbAVDY01GQQRq WVdMSlVNFUsqc2dy Wm9IERl1dQRAfTBx Z0BqWj4PVUF8I0Eo QlNSHGoCeGZhPWMC AkhYdR5UcAFPdx8U a1UrBXRDAzANdhES HhM4ODE3eDlSNilR RRkIIFQOdA4hPwZ0 XwoFBTI0FElXDwwu MxwrLEIdF08NP0l6 KUEsV1MIewMIBwBF dwAA X-Authentic-SMTP: 61633532353630.1023:706 X-AuthFastPath: 0 (Was 255) X-AuthSMTP-Origin: 76.10.178.109/587 X-AuthVirus-Status: No virus detected - but ensure you scan with your own anti-virus system. X-Spam-Score: -1.5 (-) X-Spam-Report: Spam Filtering performed by mx.sourceforge.net. See http://spamassassin.org/tag/ for more details. -1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for sender-domain -0.0 SPF_PASS SPF: sender matches SPF record 0.0 URIBL_BLOCKED ADMINISTRATOR NOTICE: The query to URIBL was blocked. See http://wiki.apache.org/spamassassin/DnsBlocklists#dnsbl-block for more information. [URIs: petertodd.org] X-Headers-End: 1VtzUB-0005VH-5U 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: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 20 Dec 2013 12:47:24 -0000 --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--