Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 171FF905 for ; 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 ; Tue, 24 May 2016 14:31:11 +0000 (UTC) Received: by mail-ig0-f177.google.com with SMTP id bi2so53352486igb.0 for ; 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: References: From: Sergio Demian Lerner Date: Tue, 24 May 2016 11:30:30 -0300 Message-ID: To: Jeremy , Bitcoin Protocol Discussion 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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 > > > 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 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
Bitcoin Beacon paper relevant here

Basically is sug= gest 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 Gabizo= n,=C2=A0 David Zuckerman

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

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

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.

I do agree that random numbers a= re highly desirable though.

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.

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 email boun= ced the list)

<= /div>

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


--089e01536be47b7bf805339768c7--