Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id C54AC8CC for ; 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 ; Tue, 24 May 2016 14:37:15 +0000 (UTC) Received: by mail-it0-f54.google.com with SMTP id z189so46104181itg.0 for ; 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: References: From: Sergio Demian Lerner Date: Tue, 24 May 2016 11:36:35 -0300 Message-ID: To: Jeremy , Bitcoin Protocol Discussion 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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 >> >> >> 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 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
Missing link to paper: https://arxiv.org/abs/1605.04559

Another relevant pape= r:

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

On Tue, May 24, 2016 at 11:30 A= M, Sergio Demian Lerner <sergio.d.lerner@gmail.com> = wrote:
Bitcoin Beacon pa= per relevant here

Basically is suggest using deciding a random bit o= n the majority 1s or 0s of lsb bits taken from last block hashes.

Id= do Bentov=E2=88=97 Technion, Ariel Gabizon,=C2=A0 David Zuckerman

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.
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.

On Sun, May 22, 2016 at 10:30 AM, Jeremy via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote= :
nack -- not secure.=C2=A0

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.

I do agree that random n= umbers 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 interested.= No fork needed, but of course it is more limited and broken in a number of= ways.=C2=A0

(sorry to those of you seeing this twice, my first emai= l bounced the list)


On Fri, May 20, 2016 at 2:32 PM, Eric Martin= dale via bitcoin-dev <bitcoin-dev@lists.linuxfoundatio= n.org> wrote:
Matthew,
You should take a look at OP_DETERMINISTICRANDOM [1] from= the Elements Project.=C2=A0 It aims to achieve a similar goal.

Code= is in the `alpha` branch [2].

On Fri, May 20, 201= 6 at 8:29 AM Matthew Roberts via bitcoin-dev <bitcoin-dev@lists.linuxfou= ndation.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 bloc= k hash to produce a single number but the direction that this is going in d= oesn't seem ideal.

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.

I need to sleep on this for now but let me kn= ow 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 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.



_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev

_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev



_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev



--001a1140c338443b750533977e9a--