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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
|
Return-Path: <kanzure@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 646165A9
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 27 Jul 2017 18:56:46 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-yw0-f179.google.com (mail-yw0-f179.google.com
[209.85.161.179])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 689CE3CA
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 27 Jul 2017 18:56:45 +0000 (UTC)
Received: by mail-yw0-f179.google.com with SMTP id u207so50337641ywc.3
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 27 Jul 2017 11:56:45 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:from:date:message-id:subject:to;
bh=P0WDxnmDHPfYed/c8pGxv30Bx/r/Yx3NfxTKETu1sOM=;
b=P65QwRBDt3YitoWtSUFYtnamKh/j3cSrIV2Dzcz/X6zC1Xs7xnKju/xdG2ClIH9wqv
QjBKh98WTBH4x0pecxuY2eCBOniwwEGu7DLoj3zBgcUlN/5uTijc/PPER6Mzgxhny2nt
pRYP/BhL8IQqSZ3+qAfKpZoEty3C03T/tY97D8jqkz1fXHl2xeoVc/O0tGyfq+tIjG4Y
VvuE0QAz4RZe69phHAQgkD1hTT/EXr2oj3V3lO7JhEk9Zz/uKqbdl/DWF1u30O7O6EWh
cEkRXNvbZWy4bUeT628qAChWLcc10Ko8MxToMSf4lHx+HZqjhHwYtjzCr6GROGK4oeXw
QDqg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:from:date:message-id:subject:to;
bh=P0WDxnmDHPfYed/c8pGxv30Bx/r/Yx3NfxTKETu1sOM=;
b=nUM2vAKT0d6L/UxfCk3ElUlQUpqViv1fNwVOM8TQIJUV612f4OifmxqU0Qq0Btz5xb
6qzFgN3zDtYxWGXxmALEzRnykz91jCYa8liRMI2K2SCd2slGgkSkhoc+WAC3OsqQ3lVN
T+lZgR2ByK4Tw+3p6D5+KDG3SqCwlzbBinShX3aLHEQBYgOl7kgFiaMVJz1fjKbGq/vg
nvA0Rgr8HHKbSzWOOLAbTOfXG+si+N8gherl7gHliNaIBPSKnZJzgJ/tRzeIxfJyynDd
iXXvwUCKm1Rf12C3lz6vVzvrUqH4khzOZTrdNx+LzgkxLki5fqsChY7Y0kyX32EGsAf/
ovEA==
X-Gm-Message-State: AIVw110DNWIWFKVpN/xjMT95q/kR0jPAwLiTTzJFOgnd+pZUdAJG4gbQ
3C3VegNm+xB4ntHJqM7d9F7Ugq5tTN3r
X-Received: by 10.37.119.81 with SMTP id s78mr4398547ybc.33.1501181804111;
Thu, 27 Jul 2017 11:56:44 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.129.226.67 with HTTP; Thu, 27 Jul 2017 11:56:43 -0700 (PDT)
From: Bryan Bishop <kanzure@gmail.com>
Date: Thu, 27 Jul 2017 13:56:43 -0500
Message-ID: <CABaSBazdodBNWJ+q8AGhJ8xZ7F+BkWb=5yp9DCs4tHhVny28CA@mail.gmail.com>
To: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>,
Bryan Bishop <kanzure@gmail.com>
Content-Type: multipart/alternative; boundary="001a114bd8522d714e055551206b"
X-Spam-Status: No, score=-1.5 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, HTML_MESSAGE,
RCVD_IN_DNSWL_NONE,
RCVD_IN_SORBS_SPAM autolearn=no version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
Subject: [bitcoin-dev] Fwd: [Mimblewimble] proofs of position and UTXO set
commitments
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: Thu, 27 Jul 2017 18:56:46 -0000
--001a114bd8522d714e055551206b
Content-Type: text/plain; charset="UTF-8"
---------- Forwarded message ----------
From: Bram Cohen <bram@bittorrent.com>
Date: Thu, Jul 27, 2017 at 1:21 PM
Subject: Re: [Mimblewimble] Switch to Blake2
To: Ignotus Peverell <igno.peverell@protonmail.com>
Cc: Bryan Bishop <kanzure@gmail.com>
I have quite a few thoughts about proofs of position. I gave a talk about
it which hopefully gets the points across if you go through all the Q&A:
https://www.youtube.com/watch?v=52FVkHlCh7Y
On Mon, Jul 24, 2017 at 12:12 PM, Ignotus Peverell <
igno.peverell@protonmail.com> wrote:
> Interesting, thanks for the link. Seems we arrived at similar conclusions
> regarding the hash function, with similar frustrations with respect to
> blake2b/2s.
>
> Funny that it's also for the same merkle set application. We ended up with
> a Merkle Mountain Range [1] instead of a Patricia tree. The MMR is
> append-only and makes pruning easy, which works well for MimbleWimble. You
> can navigate down the MMR with just the position the element was inserted
> at, so we just keep a simple index for that. Memory layout is great as a
> lot of it is immutable and sit close together, although the current impl
> doesn't leverage that too well yet. Wonder if Bram looked at MMRs? Patricia
> trees may make more sense for Bitcoin though.
>
> Proof of positions are cool, might look at that some more in the near
> future, when we're less busy implementing everything else ;-)
>
>
> - Igno
>
> [1] https://github.com/ignopeverell/grin/blob/master/doc/merkle.md
>
> -------- Original Message --------
> Subject: Re: [Mimblewimble] Switch to Blake2
> Local Time: July 24, 2017 6:44 PM
> UTC Time: July 24, 2017 6:44 PM
> From: kanzure@gmail.com
> To: Ignotus Peverell <igno.peverell@protonmail.com>, Bram Cohen <
> bram@bittorrent.com>, Bryan Bishop <kanzure@gmail.com>
>
> On Fri, Jul 21, 2017 at 1:12 PM, Ignotus Peverell <
> igno.peverell@protonmail.com> wrote:
>
>> So I'm considering a switch to the Blake2 [3] hash function.
>>
>
> Bram recently made some comments about blake a few weeks ago:
> http://diyhpl.us/wiki/transcripts/sf-bitcoin-meetup/2017-07-
> 08-bram-cohen-merkle-sets/
>
> - Bryan
> http://heybryan.org/
> 1 512 203 0507 <(512)%20203-0507>
>
>
>
--
- Bryan
http://heybryan.org/
1 512 203 0507
--001a114bd8522d714e055551206b
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><br><div class=3D"gmail_quote">---------- Forwarded messag=
e ----------<br>From: <b class=3D"gmail_sendername">Bram Cohen</b> <span di=
r=3D"ltr"><<a href=3D"mailto:bram@bittorrent.com">bram@bittorrent.com</a=
>></span><br>Date: Thu, Jul 27, 2017 at 1:21 PM<br>Subject: Re: [Mimblew=
imble] Switch to Blake2<br>To: Ignotus Peverell <<a href=3D"mailto:igno.=
peverell@protonmail.com">igno.peverell@protonmail.com</a>><br>Cc: Bryan =
Bishop <<a href=3D"mailto:kanzure@gmail.com">kanzure@gmail.com</a>><b=
r><br><br><div dir=3D"ltr">I have quite a few thoughts about proofs of posi=
tion. I gave a talk about it which hopefully gets the points across if you =
go through all the Q&A:<div><br></div><div><a href=3D"https://www.youtu=
be.com/watch?v=3D52FVkHlCh7Y" target=3D"_blank">https://www.youtube.com/wat=
ch?<wbr>v=3D52FVkHlCh7Y</a><br></div></div><div class=3D"HOEnZb"><div class=
=3D"h5"><div class=3D"gmail_extra"><br><div class=3D"gmail_quote">On Mon, J=
ul 24, 2017 at 12:12 PM, Ignotus Peverell <span dir=3D"ltr"><<a href=3D"=
mailto:igno.peverell@protonmail.com" target=3D"_blank">igno.peverell@proton=
mail.com</a>></span> wrote:<br><blockquote class=3D"gmail_quote" style=
=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div>Int=
eresting, thanks for the link. Seems we arrived at similar conclusions rega=
rding the hash function, with similar frustrations with respect to blake2b/=
2s.<br></div><div><br></div><div>Funny that it's also for the same merk=
le set application. We ended up with a Merkle Mountain Range [1] instead of=
a Patricia tree. The MMR is append-only and makes pruning easy, which work=
s well for MimbleWimble. You can navigate down the MMR with just the positi=
on the element was inserted at, so we just keep a simple index for that. Me=
mory layout is great as a lot of it is immutable and sit close together, al=
though the current impl doesn't leverage that too well yet. Wonder if B=
ram looked at MMRs? Patricia trees may make more sense for Bitcoin though.<=
br></div><div><br></div><div>Proof of positions are cool, might look at tha=
t some more in the near future, when we're less busy implementing every=
thing else ;-)<br></div><div><br></div><div class=3D"m_-8211544057623852129=
m_7438166164816387555protonmail_signature_block"><div class=3D"m_-821154405=
7623852129m_7438166164816387555protonmail_signature_block-user m_-821154405=
7623852129m_7438166164816387555protonmail_signature_block-empty"><br></div>=
<div class=3D"m_-8211544057623852129m_7438166164816387555protonmail_signatu=
re_block-proton">- Igno<br></div><div class=3D"m_-8211544057623852129m_7438=
166164816387555protonmail_signature_block-proton"><br></div><div class=3D"m=
_-8211544057623852129m_7438166164816387555protonmail_signature_block-proton=
">[1] <a href=3D"https://github.com/ignopeverell/grin/blob/master/doc/merkl=
e.md" target=3D"_blank">https://github.com/ignopeverel<wbr>l/grin/blob/mast=
er/doc/merkle.<wbr>md</a><br></div></div><div class=3D"m_-82115440576238521=
29HOEnZb"><div class=3D"m_-8211544057623852129h5"><div><br></div><blockquot=
e class=3D"m_-8211544057623852129m_7438166164816387555protonmail_quote" typ=
e=3D"cite"><div>-------- Original Message --------<br></div><div>Subject: R=
e: [Mimblewimble] Switch to Blake2<br></div><div>Local Time: July 24, 2017 =
6:44 PM<br></div><div>UTC Time: July 24, 2017 6:44 PM<br></div><div>From: <=
a href=3D"mailto:kanzure@gmail.com" target=3D"_blank">kanzure@gmail.com</a>=
<br></div><div>To: Ignotus Peverell <<a href=3D"mailto:igno.peverell@pro=
tonmail.com" target=3D"_blank">igno.peverell@protonmail.com</a>><wbr>, B=
ram Cohen <<a href=3D"mailto:bram@bittorrent.com" target=3D"_blank">bram=
@bittorrent.com</a>>, Bryan Bishop <<a href=3D"mailto:kanzure@gmail.c=
om" target=3D"_blank">kanzure@gmail.com</a>><br></div><div><br></div><di=
v dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote"><div>On=
Fri, Jul 21, 2017 at 1:12 PM, Ignotus Peverell <span dir=3D"ltr"><<a hr=
ef=3D"mailto:igno.peverell@protonmail.com" rel=3D"noreferrer nofollow noope=
ner" target=3D"_blank">igno.peverell@protonmail.com</a>></span> wrote:<b=
r></div><blockquote style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid=
rgb(204,204,204);padding-left:1ex" class=3D"gmail_quote"><div>So I'm c=
onsidering a switch to the Blake2 [3] hash function.<br></div></blockquote>=
</div><div><br></div><div>Bram recently made some comments about blake a fe=
w weeks ago:<br></div></div><div class=3D"gmail_extra"><div><a href=3D"http=
://diyhpl.us/wiki/transcripts/sf-bitcoin-meetup/2017-07-08-bram-cohen-merkl=
e-sets/" rel=3D"noreferrer nofollow noopener" target=3D"_blank">http://diyh=
pl.us/wiki/transcri<wbr>pts/sf-bitcoin-meetup/2017-07-<wbr>08-bram-cohen-me=
rkle-sets/</a><br></div><div><br></div><div class=3D"m_-8211544057623852129=
m_7438166164816387555gmail_signature"><div>- Bryan<br></div><div><a href=3D=
"http://heybryan.org/" rel=3D"noreferrer nofollow noopener" target=3D"_blan=
k">http://heybryan.org/</a><br></div><div><a href=3D"tel:(512)%20203-0507" =
value=3D"+15122030507" target=3D"_blank">1 512 203 0507</a><br></div></div>=
</div></div></blockquote><div><br></div></div></div></blockquote></div><br>=
</div>
</div></div></div><br><br clear=3D"all"><div><br></div>-- <br><div class=3D=
"gmail_signature" data-smartmail=3D"gmail_signature">- Bryan<br><a href=3D"=
http://heybryan.org/" target=3D"_blank">http://heybryan.org/</a><br>1 512 2=
03 0507</div>
</div>
--001a114bd8522d714e055551206b--
|
