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
|
Return-Path: <bram@bittorrent.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 8F792B22
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 24 Feb 2017 03:32:45 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-it0-f44.google.com (mail-it0-f44.google.com
[209.85.214.44])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 0258A193
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 24 Feb 2017 03:32:44 +0000 (UTC)
Received: by mail-it0-f44.google.com with SMTP id y135so9170040itc.1
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 23 Feb 2017 19:32:44 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=bittorrent-com.20150623.gappssmtp.com; s=20150623;
h=mime-version:in-reply-to:references:from:date:message-id:subject:to
:cc; bh=kou25u+DEOIzHFibq9or52hiCsqpptHXFiNPFg8GSa4=;
b=rqLpVhwdi0/V8qojj/LwV7V2CdP6EK3LdF4/Y9+UNek0mmKqFWnJr0ZNIidR/J0NSf
TMMgEy/Ao+XxbCx2W67M1SJotOOA9777+MQaeJRzsRhjDOZi1yp1LpmSDo+TDgX6/9X8
2zKbppg/mttSnfrHu/SqgF6OhAPm3Qxn+MpoqodHbmtfvLOUBwSYRIDxc738K5GsDHEE
3+XO7XaWWJYEfLzcfPZ457N3T2BPm6qVAaZ1AHFGqOWhJlBa+LkF+J8Ktrjr/4KLQcaC
B6nL/z/x10kYPlIcOuzEiBdIy5jQ2S2adn/1BOdS55KxKb0jTksavMrRFs97FbsaZzYE
FtAg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:in-reply-to:references:from:date
:message-id:subject:to:cc;
bh=kou25u+DEOIzHFibq9or52hiCsqpptHXFiNPFg8GSa4=;
b=XIdgBhFLiuqIBM4ki9uA/SDlv1IDAAdzI1rEjEVQdospVswRlYfCL6V4A7gyCUyCKw
FmM9A1PhimI9m4Nbokfppn2Unh57I8bzXQ6NlvvQVKgkbJ2++OLe4193Uepr2GbrZDfJ
FJ4k2YcBUigN0G359wPIir2bc7GnrKo/Ts4KnBKwSHsD0MredzZIpHZ+NOwaqp3x2DkU
SWjSGtFrXCgpy4TOahOPTYFlI4MsfHjawdm8K0bI48UU+bt9sIWMAmwOys+HC/WoCdNE
JhVpTYaReMeCzF7aRW9RqEbK5C8iyTBLSZjiKGZyBnJSYUTPUgunliKLDV7onuedIVCB
X2MQ==
X-Gm-Message-State: AMke39mEHa5/sJrZ4CL1c+sXlofp6G3+2/iJsJg3V78Ci/zdXJWxG4IQZlaycIIG1NBRa7Hf8PCJAQrBANaGHTq9
X-Received: by 10.36.25.83 with SMTP id b80mr862508itb.98.1487907164378; Thu,
23 Feb 2017 19:32:44 -0800 (PST)
MIME-Version: 1.0
Received: by 10.36.73.150 with HTTP; Thu, 23 Feb 2017 19:32:43 -0800 (PST)
In-Reply-To: <20170224031531.GA32118@savin.petertodd.org>
References: <20170223011506.GC905@savin.petertodd.org>
<CAAcC9ys5sUxVfOjogFiF3gzk51D_L=QQkOYevTH=qbh_RkA3Hw@mail.gmail.com>
<CA+KqGkrUneGe4yORi=JAAWzoO0UftMUuJm3S-__W5sBh-+T1vQ@mail.gmail.com>
<20170223235105.GA28497@savin.petertodd.org>
<CA+KqGkowxEZeAFYa2JJchBDtRkg1p3YZNocivzu3fAtgRLDRBQ@mail.gmail.com>
<20170224010943.GA29218@savin.petertodd.org>
<CA+KqGkrOK76S3ffPJmpqYcBwtSeKESqN16yZsrwzDR6JZZmwFA@mail.gmail.com>
<20170224025811.GA31911@savin.petertodd.org>
<CA+KqGkq7gavAnAk-tcA+gxL2sWpv3ENhEmHrQHaPdyAsKrLjGg@mail.gmail.com>
<20170224031531.GA32118@savin.petertodd.org>
From: Bram Cohen <bram@bittorrent.com>
Date: Thu, 23 Feb 2017 19:32:43 -0800
Message-ID: <CA+KqGkrfhg3GnbWwvKXHQ2NWuCnfzYyTPUxRhzYMuDBiNQR4eA@mail.gmail.com>
To: Peter Todd <pete@petertodd.org>
Content-Type: multipart/alternative; boundary=001a11440182fdfdd905493e618e
X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, HTML_MESSAGE, RCVD_IN_DNSWL_LOW,
RCVD_IN_SORBS_SPAM autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] A Better MMR Definition
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Fri, 24 Feb 2017 03:32:45 -0000
--001a11440182fdfdd905493e618e
Content-Type: text/plain; charset=UTF-8
On Thu, Feb 23, 2017 at 7:15 PM, Peter Todd <pete@petertodd.org> wrote:
>
> Glad we're on the same page with regard to what's possible in TXO
> commitments.
>
> Secondly, am I correct in saying your UTXO commitments scheme requires
> random
> access? While you describe it as a "merkle set", obviously to be merkelized
> it'll have to have an ordering of some kind. What do you propose that
> ordering
> to be?
>
The ordering is by the bits in the hash. Technically it's a Patricia Trie.
I'm using 'merkle tree' to refer to basically anything with a hash root.
> Maybe more specifically, what exact values do you propose to be in the set?
>
>
That is unspecified in the implementation, it just takes a 256 bit value
which is presumably a hash of something. The intention is to nail down a
simple format and demonstrate good performance and leave those semantics to
a higher layer. The simplest thing would be to hash together the txid and
output number.
--001a11440182fdfdd905493e618e
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote">On T=
hu, Feb 23, 2017 at 7:15 PM, Peter Todd <span dir=3D"ltr"><<a href=3D"ma=
ilto:pete@petertodd.org" target=3D"_blank">pete@petertodd.org</a>></span=
> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;bo=
rder-left:1px #ccc solid;padding-left:1ex"><div class=3D"HOEnZb"><div class=
=3D"h5"><br>
</div></div>Glad we're on the same page with regard to what's possi=
ble in TXO commitments.<br>
<br>
Secondly, am I correct in saying your UTXO commitments scheme requires rand=
om<br>
access? While you describe it as a "merkle set", obviously to be =
merkelized<br>
it'll have to have an ordering of some kind. What do you propose that o=
rdering<br>
to be?<br></blockquote><div><br></div><div>The ordering is by the bits in t=
he hash. Technically it's a Patricia Trie. I'm using 'merkle tr=
ee' to refer to basically anything with a hash root.</div><div>=C2=A0</=
div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-lef=
t:1px #ccc solid;padding-left:1ex">Maybe more specifically, what exact valu=
es do you propose to be in the set?<br>
<div class=3D"HOEnZb"><div class=3D"h5"><br></div></div></blockquote><div><=
br></div><div>That is unspecified in the implementation, it just takes a 25=
6 bit value which is presumably a hash of something. The intention is to na=
il down a simple format and demonstrate good performance and leave those se=
mantics to a higher layer. The simplest thing would be to hash together the=
txid and output number.</div></div></div></div>
--001a11440182fdfdd905493e618e--
|
