Re: [bitcoin-dev] BIP: OP_PRANDOM

[Sergio Demian Lerner <sergio.d.lerner@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 5114 bytes --]

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∗ Technion, Ariel Gabizon,  David Zuckerman
>
> We examine a protocol πbeacon that outputs unpredictable and publicly
> verifiable randomness, meaning that the output is unknown at the time that
> πbeacon starts, yet everyone can verify that the output is close to uniform
> after πbeacon terminates. We show that πbeacon can be instantiated 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
>> 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.
>>
>> (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/interpreter.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 produce a
>>>> single number but the direction that this is going in doesn'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 of the number so you have to throw
>>>> away a valid POW if it doesn't give you the hash you want. I suppose its
>>>> 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.
>>>>>
>>>>>
>>>>> == 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/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
>>
>>
>

[-- Attachment #2: Type: text/html, Size: 8116 bytes --]