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
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
|
Return-Path: <sergio.d.lerner@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 171FF905
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 24 May 2016 14:31:13 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-ig0-f177.google.com (mail-ig0-f177.google.com
[209.85.213.177])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id ECF351C1
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 24 May 2016 14:31:11 +0000 (UTC)
Received: by mail-ig0-f177.google.com with SMTP id bi2so53352486igb.0
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 24 May 2016 07:31:11 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=mime-version:in-reply-to:references:from:date:message-id:subject:to
:cc; bh=DusJUGb61s2tyWddY8EwMUxCKntAwYHWlRel8MkFHcg=;
b=Ce6a5G5ymnheJPt8hNZ0vv68ABc40YFuEuqtcdG8iCK13b9lm9i7ZX5iPsYjj5QLyd
X1pRHdResk9d/1vqJ/2QweU/k9SMJIAB5DxBGizgBy4sZ/ED0I4GQ+YtopzV2dkcuJRZ
p2Hpgm1I5mFkIPL3AwX8knSciTL/ilx54nMeJDQQd3Hvl/mXVPZO/qzESKd3kGlPP6OS
yYiTRdszdujb7k1w4qPUA+FsHiqvGlrc882qmpcVQ3AdhyHjvi61d+tMXtG1hWGyZgPr
LIigC0nRYUkwE+U1LcfWA+l3Nfi6Ry91iY8tKd/X6tSG0dvqL93JEQgXnAU+XYwEsGd9
2opA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20130820;
h=x-gm-message-state:mime-version:in-reply-to:references:from:date
:message-id:subject:to:cc;
bh=DusJUGb61s2tyWddY8EwMUxCKntAwYHWlRel8MkFHcg=;
b=EDFFsmEgLjea+gqng1cKLLbFNIwdvVUTWfcaMlTeCWEu99KI6qMcpxVuCQMtvHmDo7
UuAEzM7eDpBa5ZY5HvIwqDa+/w/9XJ2hFZnbaCcJKaLKrTHeFvx2VSwEc6nnM7M05yCz
tSDYkLiVlf197YILPmQyPl8STe6/Oz5ToteuGauOuKZH/sm1znwumTfoglnIkrRIinvD
RlxWsnocf+/C0jH3wQYl+mkaiiEpES2BAFzOK72oKgkWVUJlvwI7+zk3WIfrUfqxftfg
qWTRNo58/pjrS7gCI7XOiXF/8/PhId1uo93GGyljrT24uz3I9jrTSH8+Gpck98hxMuec
h41A==
X-Gm-Message-State: AOPr4FVLYeXs8HuuZ4kxbDkTn8nBJ+o0p7haCOfoqq6qxZsh5gZo+2FH+vUMzxSLlMNPuNK5oRKD+ZESyVAbZA==
X-Received: by 10.50.111.15 with SMTP id ie15mr18256416igb.94.1464100269552;
Tue, 24 May 2016 07:31:09 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.107.142.69 with HTTP; Tue, 24 May 2016 07:30:30 -0700 (PDT)
In-Reply-To: <CAD5xwhjOd+3FRL59EKE6n4d-RmXSjNFmXZJECDWJKfGdz9oiXw@mail.gmail.com>
References: <CAAEDBiEB_RXBjrLB8kDb52bJOwZK-arVeHA_9LyoDgAraLKHNg@mail.gmail.com>
<CBBB62CD-2E30-4C9F-962E-3F340B29EDA7@xbt.hk>
<CAAEDBiE08h=+8ntQ=mMyA0jaxj2H_6r2k0u4GdOhEkFNYEAhYQ@mail.gmail.com>
<CAAf19WpiJDeVxi12mR8xFdjZttVYNRbsgYZzLxn2SLZDJYJHDQ@mail.gmail.com>
<CAD5xwhjOd+3FRL59EKE6n4d-RmXSjNFmXZJECDWJKfGdz9oiXw@mail.gmail.com>
From: Sergio Demian Lerner <sergio.d.lerner@gmail.com>
Date: Tue, 24 May 2016 11:30:30 -0300
Message-ID: <CAKzdR-rFXYGHzxo8Vj7DC1xFitJwoPJH8Kyn0EcBabNB+AwZWA@mail.gmail.com>
To: Jeremy <jlrubin@mit.edu>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary=089e01536be47b7bf805339768c7
X-Spam-Status: No, score=-2.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,HTML_MESSAGE,RCVD_IN_DNSWL_LOW
autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
Subject: Re: [bitcoin-dev] BIP: OP_PRANDOM
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: Tue, 24 May 2016 14:31:13 -0000
--089e01536be47b7bf805339768c7
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Bitcoin Beacon paper relevant here
Basically is suggest using deciding a random bit on the majority 1s or 0s
of lsb bits taken from last block hashes.
Iddo Bentov=E2=88=97 Technion, Ariel Gabizon, David Zuckerman
We examine a protocol =CF=80beacon that outputs unpredictable and publicly
verifiable randomness, meaning that the output is unknown at the time that
=CF=80beacon starts, yet everyone can verify that the output is close to un=
iform
after =CF=80beacon terminates. We show that =CF=80beacon can be instantiate=
d via
Bitcoin under sensible assumptions; in particular we consider an adversary
with an arbitrarily large initial budget who may not operate at a loss
indefinitely.
In case the adversary has an infinite budget, we provide an impossibility
result that stems from the similarity between the Bitcoin model and
Santha-Vazirani sources. We also give a hybrid protocol that combines
trusted parties and a Bitcoin-based beacon.
On Sun, May 22, 2016 at 10:30 AM, Jeremy via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:
> nack -- not secure.
>
> OP_PRANDOM also adds extra validation overhead on a block potentially
> composed of transactions all spending an OP_PRANDOM output from all
> different blocks.
>
> I do agree that random numbers are highly desirable though.
>
> I think it would be much better for these use cases to add OP_XOR back an=
d
> then use something like Blum's fair coin-flipping over the phone. OP_XOR
> may have other uses too.
>
> I have a write-up from a while back which does Blum's without OP_XOR usin=
g
> OP_SIZE for off-chain probabilistic payments if anyone is interested. No
> fork needed, but of course it is more limited and broken in a number of
> ways.
>
> (sorry to those of you seeing this twice, my first email bounced the list=
)
>
> --
> @JeremyRubin <https://twitter.com/JeremyRubin>
> <https://twitter.com/JeremyRubin>
>
> On Fri, May 20, 2016 at 2:32 PM, Eric Martindale via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> Matthew,
>>
>> You should take a look at OP_DETERMINISTICRANDOM [1] from the Elements
>> Project. It aims to achieve a similar goal.
>>
>> Code is in the `alpha` branch [2].
>>
>> [1]: https://www.elementsproject.org/elements/opcodes/
>> [2]:
>> https://github.com/ElementsProject/elements/blob/alpha/src/script/interp=
reter.cpp#L1252-L1305
>>
>> On Fri, May 20, 2016 at 8:29 AM Matthew Roberts via bitcoin-dev <
>> bitcoin-dev@lists.linuxfoundation.org> wrote:
>>
>>> Good point, to be honest. Maybe there's a better way to combine the
>>> block hashes like taking the first N bits from each block hash to produ=
ce a
>>> single number but the direction that this is going in doesn't seem idea=
l.
>>>
>>> I just asked a friend about this problem and he mentioned using the has=
h
>>> of the proof of work hash as part of the number so you have to throw aw=
ay a
>>> valid POW if it doesn't give you the hash you want. I suppose its possi=
ble
>>> to make it infinitely expensive to manipulate the number but I can't th=
ink
>>> of anything better than that for now.
>>>
>>> I need to sleep on this for now but let me know if anyone has any bette=
r
>>> ideas.
>>>
>>>
>>>
>>> On Fri, May 20, 2016 at 6:34 AM, Johnson Lau <jl2012@xbt.hk> wrote:
>>>
>>>> Using the hash of multiple blocks does not make it any safer. The mine=
r
>>>> of the last block always determines the results, by knowing the hashes=
of
>>>> all previous blocks.
>>>>
>>>>
>>>> =3D=3D Security
>>>>
>>>> Pay-to-script-hash can be used to protect the details of contracts tha=
t
>>>> use OP_PRANDOM from the prying eyes of miners. However, since there is=
also
>>>> a non-zero risk that a participant in a contract may attempt to bribe =
a
>>>> miner the inclusion of multiple block hashes as a source of randomness=
is a
>>>> must. Every miner would effectively need to be bribed to ensure contro=
l
>>>> over the results of the random numbers, which is already very unlikely=
. The
>>>> risk approaches zero as N goes up.
>>>>
>>>>
>>>>
>>> _______________________________________________
>>> bitcoin-dev mailing list
>>> bitcoin-dev@lists.linuxfoundation.org
>>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>>
>>
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
>>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
--089e01536be47b7bf805339768c7
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">Bitcoin Beacon paper relevant here<br><br>Basically is sug=
gest using deciding a random bit on the majority 1s or 0s of lsb bits taken=
from last block hashes.<br><br>Iddo Bentov=E2=88=97 Technion, Ariel Gabizo=
n,=C2=A0 David Zuckerman<br><br>We examine a protocol =CF=80beacon that out=
puts unpredictable and publicly verifiable randomness, meaning that the out=
put is unknown at the time that =CF=80beacon starts, yet everyone can verif=
y that the output is close to uniform after =CF=80beacon terminates. We sho=
w that =CF=80beacon can be instantiated via Bitcoin under sensible assumpti=
ons; in particular we consider an adversary with an arbitrarily large initi=
al budget who may not operate at a loss indefinitely.<br>In case the advers=
ary has an infinite budget, we provide an impossibility result that stems f=
rom the similarity between the Bitcoin model and Santha-Vazirani sources. W=
e also give a hybrid protocol that combines trusted parties and a Bitcoin-b=
ased beacon.<br></div><div class=3D"gmail_extra"><br><div class=3D"gmail_qu=
ote">On Sun, May 22, 2016 at 10:30 AM, Jeremy via bitcoin-dev <span dir=3D"=
ltr"><<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D=
"_blank">bitcoin-dev@lists.linuxfoundation.org</a>></span> wrote:<br><bl=
ockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #=
ccc solid;padding-left:1ex"><div dir=3D"ltr"><div class=3D"gmail_extra">nac=
k -- not secure.=C2=A0<br><br>OP_PRANDOM also adds extra validation overhea=
d on a block potentially composed of transactions all spending an OP_PRANDO=
M output from all different blocks.<br><br>I do agree that random numbers a=
re highly desirable though.<br><br>I think it would be much better for thes=
e use cases to add OP_XOR back and then use something like Blum's fair =
coin-flipping over the phone. OP_XOR may have other uses too.<br><br>I have=
a write-up from a while back which does Blum's without OP_XOR using OP=
_SIZE for off-chain probabilistic payments if anyone is interested. No fork=
needed, but of course it is more limited and broken in a number of ways.=
=C2=A0<br><br>(sorry to those of you seeing this twice, my first email boun=
ced the list)</div><div><br><div><div><div><div dir=3D"ltr">--<br><a href=
=3D"https://twitter.com/JeremyRubin" target=3D"_blank">@JeremyRubin</a><a h=
ref=3D"https://twitter.com/JeremyRubin" target=3D"_blank"></a></div></div><=
/div>
</div><div><div class=3D"h5">
<br><div class=3D"gmail_quote">On Fri, May 20, 2016 at 2:32 PM, Eric Martin=
dale via bitcoin-dev <span dir=3D"ltr"><<a href=3D"mailto:bitcoin-dev@li=
sts.linuxfoundation.org" target=3D"_blank">bitcoin-dev@lists.linuxfoundatio=
n.org</a>></span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"m=
argin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204=
,204);border-left-style:solid;padding-left:1ex"><div dir=3D"ltr">Matthew,<d=
iv><br></div><div>You should take a look at OP_DETERMINISTICRANDOM [1] from=
the Elements Project.=C2=A0 It aims to achieve a similar goal.<br><br>Code=
is in the `alpha` branch [2].</div><div><br></div><div>[1]:=C2=A0<a href=
=3D"https://www.elementsproject.org/elements/opcodes/" target=3D"_blank">ht=
tps://www.elementsproject.org/elements/opcodes/</a><br>[2]:=C2=A0<a href=3D=
"https://github.com/ElementsProject/elements/blob/alpha/src/script/interpre=
ter.cpp#L1252-L1305" target=3D"_blank">https://github.com/ElementsProject/e=
lements/blob/alpha/src/script/interpreter.cpp#L1252-L1305</a></div></div><b=
r><div class=3D"gmail_quote"><div><div><div dir=3D"ltr">On Fri, May 20, 201=
6 at 8:29 AM Matthew Roberts via bitcoin-dev <<a href=3D"mailto:bitcoin-=
dev@lists.linuxfoundation.org" target=3D"_blank">bitcoin-dev@lists.linuxfou=
ndation.org</a>> wrote:<br></div></div></div><blockquote class=3D"gmail_=
quote" style=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-=
color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div><div>=
<div dir=3D"ltr"><div>Good point, to be honest. Maybe there's a better =
way to combine the block hashes like taking the first N bits from each bloc=
k hash to produce a single number but the direction that this is going in d=
oesn't seem ideal. <br><br></div><div>I just asked a friend about this =
problem and he mentioned using the hash of the proof of work hash as part o=
f the number so you have to throw away a valid POW if it doesn't give y=
ou the hash you want. I suppose its possible to make it infinitely expensiv=
e to manipulate the number but I can't think of anything better than th=
at for now.<br><br></div><div>I need to sleep on this for now but let me kn=
ow if anyone has any better ideas.<br></div><div><br><br></div></div><div c=
lass=3D"gmail_extra"><br><div class=3D"gmail_quote">On Fri, May 20, 2016 at=
6:34 AM, Johnson Lau <span dir=3D"ltr"><<a href=3D"mailto:jl2012@xbt.hk=
" target=3D"_blank">jl2012@xbt.hk</a>></span> wrote:<br><blockquote clas=
s=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;b=
order-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"=
><div style=3D"word-wrap:break-word"><div>Using the hash of multiple blocks=
does not make it any safer. The miner of the last block always determines =
the results, by knowing the hashes of all previous blocks.</div><span><div>=
<br></div><div><blockquote type=3D"cite"><div dir=3D"ltr"><p style=3D"margi=
n-bottom:0in;line-height:100%"><br>
</p><p style=3D"margin-bottom:0in;line-height:100%">=3D=3D Security</p><p s=
tyle=3D"margin-bottom:0in;line-height:100%">Pay-to-script-hash
can be used to protect the details of contracts that use OP_PRANDOM
from the prying eyes of miners. However, since there is also a
non-zero risk that a participant in a contract may attempt to bribe a
miner the inclusion of multiple block hashes as a source of
randomness is a must. Every miner would effectively need to be bribed
to ensure control over the results of the random numbers, which is
already very unlikely. The risk approaches zero as N goes up.</p></div></bl=
ockquote></div><br></span></div></blockquote></div><br></div></div></div><s=
pan>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</span></blockquote></div>
<br>_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
<br></blockquote></div><br></div></div></div></div>
<br>_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.=
linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
<br></blockquote></div><br></div>
--089e01536be47b7bf805339768c7--
|