path: root/79/6611c06e413617806ddb13eb669edde22443a6

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 C54AC8CC
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Tue, 24 May 2016 14:37:16 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-it0-f54.google.com (mail-it0-f54.google.com
	[209.85.214.54])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id A380687
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Tue, 24 May 2016 14:37:15 +0000 (UTC)
Received: by mail-it0-f54.google.com with SMTP id z189so46104181itg.0
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Tue, 24 May 2016 07:37:15 -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=9KongUbOaVUd42pOKGRbcs9gdzJZfhMG5uyiFtiLi6g=;
	b=c6NtFY6B3tq36/x14pZ80S2Fj4NZ0MiVkNxnKKNzuhhnmBJuflaeseaVho0jtCSC19
	LmFlqP9TSeV+ZbVfQjXLCZm2wiBmXw9vuMwrcqvyHX9ARejugdjGSCmxkYwYW8NQOpCS
	53834oQxhskFPaZZOe5iCKDzSeRaOQ2baR/Ftr/jsspplceNjc2Qv5pNS/uIxqu/kKzQ
	78BIaDI0Dldq+PQ18ZvAQolhZYpYKv3Xo0ex+iK1MOthc3ZcySBD8yzItdb0oBuyMdk/
	4s8YNNhMgyEj1QNY7Umn0+Zjw70aIuBMrnLliWh+VvXempaBzzh5uBNlSjJ3Qri/uo/t
	yrow==
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=9KongUbOaVUd42pOKGRbcs9gdzJZfhMG5uyiFtiLi6g=;
	b=ZBNLsvqcLgudShk6s8rae138yqEok6mMJnY08xnb1gjvZf5qOf3foDxiIm80b0uat7
	vi6o4RhIm3bghl6lCdiX22zOG+1sCUeISnJC8LoHWSwhqQE/VmbqCFJYQCsLf32x4/v7
	Fs3rD1EaRNjHregAt3tSjrZw77+ZJFYwyogX+Qnuou0YSnhh+aOhu/j2xwl5yoAwZ56e
	ahcpSb7alMrsXSGgb0H6wRs2pC8WB5XTR3DxYvHURjBaDHFkuAbv77FaxLjTkKXElC9O
	gC0+qBvC8zcZxPJKPhb4G0KZOCpZbcJYNWo7hEZWoQkDNcymYjRZlGn6bbY8Yb2gn6p7
	YR9A==
X-Gm-Message-State: AOPr4FWLkhT4iYJnMxwPOCLjBCEPt5JazFGWp48hOQkx1ccFs9d2VckBUCznv4YwKgEKKfjFnoYBdulTgUhQSw==
X-Received: by 10.36.11.84 with SMTP id 81mr18294878itd.76.1464100635030; Tue,
	24 May 2016 07:37:15 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.107.142.69 with HTTP; Tue, 24 May 2016 07:36:35 -0700 (PDT)
In-Reply-To: <CAKzdR-rFXYGHzxo8Vj7DC1xFitJwoPJH8Kyn0EcBabNB+AwZWA@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>
	<CAKzdR-rFXYGHzxo8Vj7DC1xFitJwoPJH8Kyn0EcBabNB+AwZWA@mail.gmail.com>
From: Sergio Demian Lerner <sergio.d.lerner@gmail.com>
Date: Tue, 24 May 2016 11:36:35 -0300
Message-ID: <CAKzdR-pr3FK=H-aVdkJkx8FwobVRnakF_x0405=0=FC7q+=cVA@mail.gmail.com>
To: Jeremy <jlrubin@mit.edu>, 
	Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary=001a1140c338443b750533977e9a
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, HTML_MESSAGE,
	RCVD_IN_DNSWL_NONE 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:37:16 -0000

--001a1140c338443b750533977e9a
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

Missing link to paper: https://arxiv.org/abs/1605.04559

Another relevant paper:

On Bitcoin as a public randomness source
Joseph Bonneau, Jeremy Clark, and Steven Goldfeder
https://eprint.iacr.org/2015/1015.pdf

On Tue, May 24, 2016 at 11:30 AM, Sergio Demian Lerner <
sergio.d.lerner@gmail.com> wrote:

> 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 publicl=
y
> verifiable randomness, meaning that the output is unknown at the time tha=
t
> =CF=80beacon starts, yet everyone can verify that the output is close to =
uniform
> after =CF=80beacon terminates. We show that =CF=80beacon can be instantia=
ted via
> Bitcoin under sensible assumptions; in particular we consider an adversar=
y
> 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
>> and 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
>> using OP_SIZE for off-chain probabilistic payments if anyone is interest=
ed.
>> 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 lis=
t)
>>
>> --
>> @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/inter=
preter.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 prod=
uce a
>>>> single number but the direction that this is going in doesn't seem ide=
al.
>>>>
>>>> I just asked a friend about this problem and he mentioned using the
>>>> hash of the proof of work hash as part of the number so you have to th=
row
>>>> away a valid POW if it doesn't give you the hash you want. I suppose i=
ts
>>>> possible to make it infinitely expensive to manipulate the number but =
I
>>>> can't think of anything better than that for now.
>>>>
>>>> I need to sleep on this for now but let me know if anyone has any
>>>> better 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
>>>>> miner 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
>>>>> that use OP_PRANDOM from the prying eyes of miners. However, since th=
ere 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 randomn=
ess is
>>>>> a must. Every miner would effectively need to be bribed to ensure con=
trol
>>>>> over the results of the random numbers, which is already very unlikel=
y. 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
>>
>>
>

--001a1140c338443b750533977e9a
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Missing link to paper: <a href=3D"https://arxiv.org/abs/16=
05.04559">https://arxiv.org/abs/1605.04559</a><br><br>Another relevant pape=
r:<br><br><div style=3D"font-family:sans-serif"><font size=3D"2">On Bitcoin=
 as a public randomness source</font></div><div style=3D"font-size:16.6043p=
x;font-family:sans-serif"><font size=3D"2">Joseph Bonneau, Jeremy Clark, an=
d Steven Goldfeder<br></font></div><a href=3D"https://eprint.iacr.org/2015/=
1015.pdf">https://eprint.iacr.org/2015/1015.pdf</a><br></div><div class=3D"=
gmail_extra"><br><div class=3D"gmail_quote">On Tue, May 24, 2016 at 11:30 A=
M, Sergio Demian Lerner <span dir=3D"ltr">&lt;<a href=3D"mailto:sergio.d.le=
rner@gmail.com" target=3D"_blank">sergio.d.lerner@gmail.com</a>&gt;</span> =
wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;bord=
er-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr">Bitcoin Beacon pa=
per relevant here<br><br>Basically is suggest using deciding a random bit o=
n the majority 1s or 0s of lsb bits taken from last block hashes.<br><br>Id=
do Bentov=E2=88=97 Technion, Ariel Gabizon,=C2=A0 David Zuckerman<br><br>We=
 examine a protocol =CF=80beacon that outputs unpredictable and publicly ve=
rifiable 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 insta=
ntiated via Bitcoin under sensible assumptions; in particular we consider a=
n adversary with an arbitrarily large initial budget who may not operate at=
 a loss indefinitely.<br>In case the adversary has an infinite budget, we p=
rovide an impossibility result that stems from the similarity between the B=
itcoin model and Santha-Vazirani sources. We also give a hybrid protocol th=
at combines trusted parties and a Bitcoin-based beacon.<br></div><div class=
=3D"HOEnZb"><div class=3D"h5"><div class=3D"gmail_extra"><br><div class=3D"=
gmail_quote">On Sun, May 22, 2016 at 10:30 AM, Jeremy via bitcoin-dev <span=
 dir=3D"ltr">&lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" t=
arget=3D"_blank">bitcoin-dev@lists.linuxfoundation.org</a>&gt;</span> wrote=
:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-le=
ft:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div class=3D"gmail_ex=
tra">nack -- not secure.=C2=A0<br><br>OP_PRANDOM also adds extra validation=
 overhead on a block potentially composed of transactions all spending an O=
P_PRANDOM output from all different blocks.<br><br>I do agree that random n=
umbers are highly desirable though.<br><br>I think it would be much better =
for these use cases to add OP_XOR back and then use something like Blum&#39=
;s fair coin-flipping over the phone. OP_XOR may have other uses too.<br><b=
r>I have a write-up from a while back which does Blum&#39;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 emai=
l bounced 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 href=3D"https://twitter.com/JeremyRubin" target=3D"_blank"></a></div></d=
iv></div>
</div><div><div>
<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">&lt;<a href=3D"mailto:bitcoin-dev@li=
sts.linuxfoundation.org" target=3D"_blank">bitcoin-dev@lists.linuxfoundatio=
n.org</a>&gt;</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 &lt;<a href=3D"mailto:bitcoin-=
dev@lists.linuxfoundation.org" target=3D"_blank">bitcoin-dev@lists.linuxfou=
ndation.org</a>&gt; 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&#39;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&#39;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&#39;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&#39;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">&lt;<a href=3D"mailto:jl2012@xbt.hk=
" target=3D"_blank">jl2012@xbt.hk</a>&gt;</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" 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></blockquote></div><br></div>

--001a1140c338443b750533977e9a--