* [bitcoin-dev] BIP: OP_PRANDOM @ 2016-05-20 10:57 Matthew Roberts 2016-05-20 11:34 ` Johnson Lau 0 siblings, 1 reply; 8+ messages in thread From: Matthew Roberts @ 2016-05-20 10:57 UTC (permalink / raw) To: bitcoin-dev [-- Attachment #1: Type: text/plain, Size: 2553 bytes --] == Background OP_PRANDOM is a new op code for Bitcoin that pushes a pseudo-random number to the top of the stack based on the next N block hashes. The source of the pseudo-random number is defined as the XOR of the next N block hashes after confirmation of a transaction containing the OP_PRANDOM encumbered output. When a transaction containing the op code is redeemed, the transaction receives a pseudo-random number based on the next N block hashes after confirmation of the redeeming input. This means that transactions are also effectively locked until at least N new blocks have been found. == Rational Making deterministic, verifiable, and trustless pseudo-random numbers available for use in the Script language makes it possible to support a number of new smart contracts. OP_PRANDOM would allow for the simplistic creation of purely decentralized lotteries without the need for complicated multi-party computation protocols. Gambling is also another possibility as contracts can be written based on hashed commitments, with the winner chosen if a given commitment is closest to the pseudo-random number. OP_PRANDOM could also be used for cryptographically secure virtual asset management such as rewards in video games and in other applications. == 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. There is however another issue: since the random numbers are based on a changing blockchain, its problematic to use the next immediate block hashes before the state is “final.” A safe default for accepting the blockchain state as final would need to be agreed upon beforehand, otherwise you could have multiple random outputs becoming valid simultaneously on different forks. A simple solution is not to reveal any commitments before the chain height surpasses a certain point but this might not be an issue since only one version will eventually make it into the final chain anyway -- though it is something to think about. == Outro I'm not sure how secure this is or whether its a good idea so posting it here for feedback Thoughts? [-- Attachment #2: Type: text/html, Size: 3317 bytes --] ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [bitcoin-dev] BIP: OP_PRANDOM 2016-05-20 10:57 [bitcoin-dev] BIP: OP_PRANDOM Matthew Roberts @ 2016-05-20 11:34 ` Johnson Lau 2016-05-20 14:30 ` James MacWhyte 2016-05-20 15:05 ` Matthew Roberts 0 siblings, 2 replies; 8+ messages in thread From: Johnson Lau @ 2016-05-20 11:34 UTC (permalink / raw) To: Matthew Roberts, bitcoin-dev [-- Attachment #1: Type: text/plain, Size: 673 bytes --] 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. [-- Attachment #2: Type: text/html, Size: 1194 bytes --] ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [bitcoin-dev] BIP: OP_PRANDOM 2016-05-20 11:34 ` Johnson Lau @ 2016-05-20 14:30 ` James MacWhyte 2016-05-20 15:05 ` Matthew Roberts 1 sibling, 0 replies; 8+ messages in thread From: James MacWhyte @ 2016-05-20 14:30 UTC (permalink / raw) To: Johnson Lau, Bitcoin Protocol Discussion, Matthew Roberts [-- Attachment #1: Type: text/plain, Size: 1074 bytes --] Matthew, Other than gambling, do you have any specific examples of how this could be useful? On Fri, May 20, 2016, 20:34 Johnson Lau via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> 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 > [-- Attachment #2: Type: text/html, Size: 1849 bytes --] ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [bitcoin-dev] BIP: OP_PRANDOM 2016-05-20 11:34 ` Johnson Lau 2016-05-20 14:30 ` James MacWhyte @ 2016-05-20 15:05 ` Matthew Roberts 2016-05-20 18:32 ` Eric Martindale 1 sibling, 1 reply; 8+ messages in thread From: Matthew Roberts @ 2016-05-20 15:05 UTC (permalink / raw) To: Johnson Lau; +Cc: bitcoin-dev [-- Attachment #1: Type: text/plain, Size: 1401 bytes --] 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. > > > [-- Attachment #2: Type: text/html, Size: 2059 bytes --] ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [bitcoin-dev] BIP: OP_PRANDOM 2016-05-20 15:05 ` Matthew Roberts @ 2016-05-20 18:32 ` Eric Martindale 2016-05-22 13:30 ` Jeremy 0 siblings, 1 reply; 8+ messages in thread From: Eric Martindale @ 2016-05-20 18:32 UTC (permalink / raw) To: Matthew Roberts, Bitcoin Protocol Discussion, Johnson Lau [-- Attachment #1: Type: text/plain, Size: 2061 bytes --] 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 > [-- Attachment #2: Type: text/html, Size: 3350 bytes --] ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [bitcoin-dev] BIP: OP_PRANDOM 2016-05-20 18:32 ` Eric Martindale @ 2016-05-22 13:30 ` Jeremy 2016-05-24 14:30 ` Sergio Demian Lerner 0 siblings, 1 reply; 8+ messages in thread From: Jeremy @ 2016-05-22 13:30 UTC (permalink / raw) To: Eric Martindale, Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 3226 bytes --] 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 > > [-- Attachment #2: Type: text/html, Size: 5423 bytes --] ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [bitcoin-dev] BIP: OP_PRANDOM 2016-05-22 13:30 ` Jeremy @ 2016-05-24 14:30 ` Sergio Demian Lerner 2016-05-24 14:36 ` Sergio Demian Lerner 0 siblings, 1 reply; 8+ messages in thread From: Sergio Demian Lerner @ 2016-05-24 14:30 UTC (permalink / raw) To: Jeremy, Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 4663 bytes --] 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: 7194 bytes --] ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [bitcoin-dev] BIP: OP_PRANDOM 2016-05-24 14:30 ` Sergio Demian Lerner @ 2016-05-24 14:36 ` Sergio Demian Lerner 0 siblings, 0 replies; 8+ messages in thread From: Sergio Demian Lerner @ 2016-05-24 14:36 UTC (permalink / raw) To: Jeremy, Bitcoin Protocol Discussion [-- 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 --] ^ permalink raw reply [flat|nested] 8+ messages in thread
end of thread, other threads:[~2016-05-24 14:37 UTC | newest] Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2016-05-20 10:57 [bitcoin-dev] BIP: OP_PRANDOM Matthew Roberts 2016-05-20 11:34 ` Johnson Lau 2016-05-20 14:30 ` James MacWhyte 2016-05-20 15:05 ` Matthew Roberts 2016-05-20 18:32 ` Eric Martindale 2016-05-22 13:30 ` Jeremy 2016-05-24 14:30 ` Sergio Demian Lerner 2016-05-24 14:36 ` Sergio Demian Lerner
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox