path: root/6e/416a9b6b13e3b1f9c490fb1974e996a1f8d6f8

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">&lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D=
"_blank">bitcoin-dev@lists.linuxfoundation.org</a>&gt;</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&#39;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&#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 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">&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">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--