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"><<a href=3D"mailto:sergio.d.le= rner@gmail.com" target=3D"_blank">sergio.d.lerner@gmail.com</a>></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"><<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" t= arget=3D"_blank">bitcoin-dev@lists.linuxfoundation.org</a>></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'= ;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'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"><<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" 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--