1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
|
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 <pete@petertodd.org>) 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 <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)
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: <bitcoin-development.lists.sourceforge.net>
List-Unsubscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=unsubscribe>
List-Archive: <http://sourceforge.net/mailarchive/forum.php?forum_name=bitcoin-development>
List-Post: <mailto:bitcoin-development@lists.sourceforge.net>
List-Help: <mailto:bitcoin-development-request@lists.sourceforge.net?subject=help>
List-Subscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=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--
|
