Author [EN] [ZH] [ES] [PT] [IT] [DE] [FR] [NL] [TR] [SR] [AR] [RU] [EN] [ZH] [ES] [PT] [IT] [DE] [FR] [NL] [TR] [SR] [AR] [RU] [EN] [ZH] [ES] [PT] [IT] [DE] [FR] [NL] [TR] [SR] [AR] [RU] Topic: Distributed Random Number Generation  (Read 947 times)

Offline FreeTrade

  • Board Moderator
  • Hero Member
  • *****
  • Posts: 700
    • View Profile
Distributed Random Number Generation
« on: August 30, 2014, 10:25:56 AM »

Here's my proposal for generating fair random numbers in a distributed manner. I'll explain with a worked example with the smallest number of participants - three.

Three brothers, Jack, Bobby and Teddy agree to have a random draw to choose which one of them wins a prize, but they are in different locations.

They each create a public/private key pair and publish the public keys.

Each brother signs an agreed string with his private key, the resulting signature is his secret. The hash of the concatenated three secrets is used as a seed to generate the random number.

We want to guard against the possibility that one brother has access to the result before he has revealed his secret, enabling him to discard his secret and prevent the result from becoming known.

Round 1.

Step 1. Limited Disclosure
Jack sends his secret to Bobby. Bobby sends his secret to Teddy. Teddy sends his secret to Jack.

Step 2. Vouching
Bobby vouches that Jack has disclosed to him. Teddy vouches for Bobby. Jack vouches for Teddy.

Round 2 (Final Round for 3)
Step 1. Limited Disclosure
Jack sends his secret to Teddy. Bobby sends his secret to Jack. Teddy sends his secret to Bobby.

All three brothers now have all three secrets and can generate the random number.

Let's say Teddy waits in the final round to receive Jack's secret, generates the random number, doesn't like it and doesn't send his secret to Bobby. Bobby can always request Teddy's secret from Jack. As long as a majority are not dishonest or in collusion, the random number generated is fair, and there is no optionality problem.

For DPOS, you'd probably want to use it in combination with the existing chain of delegates - so the block would be generated first with the existing method, and then the random number is generated by N previous delegates. It should be possible to expand to N delegates, using a number of rounds of disclosure and vouching. For 101 delegates, the first round might involve each delegate disclosing to 10 other delegates, followed by vouching, followed by 10 more etc

« Last Edit: August 30, 2014, 10:31:36 AM by FreeTrade »
“People should be more sophisticated? How are you gonna get that done?” - Jerry Seinfeld reply to Bill Maher

Offline ssjpts

Re: Distributed Random Number Generation
« Reply #1 on: September 02, 2014, 04:21:03 PM »
good
新浪微博:剑指未来BTS
BTC:1Bc7gRGotktBmnNFr3BUUM22HFXCCTyxor
BTSX ID:loves,集大众之爱,待到BTS 500刀,10%回退给捐赠者,10%用于运营,剩余80%用于爱心事业和BTS宣传推广。

Offline xeroc

  • Board Moderator
  • Hero Member
  • *****
  • Posts: 11962
  • ChainSquad GmbH
    • View Profile
    • ChainSquad GmbH
  • BTS: xeroc
  • GitHub: xeroc
Re: Distributed Random Number Generation
« Reply #2 on: September 02, 2014, 04:39:28 PM »
For 101 delegates, the first round might involve each delegate disclosing to 10 other delegates, followed by vouching, followed by 10 more etc
Puh... nice idea .. but for 101 delegates that's > 10 time slots each with 10 transactions containing the secrets for a SINGLE random number .. assuming that this should happen ON the blockchain that would result in a delay of >100sec plus the costs for 100! transactions .. am I wrong?

besides that the scheme sounds solid .. somehow reminds me of ring signatures ;-)
Give BitShares a try! Use the http://testnet.bitshares.eu provided by http://bitshares.eu powered by ChainSquad GmbH

Offline Shentist

  • Board Moderator
  • Hero Member
  • *****
  • Posts: 1605
    • View Profile
    • metaexchange
  • BTS: shentist
Re: Distributed Random Number Generation
« Reply #3 on: September 02, 2014, 04:58:56 PM »
For 101 delegates, the first round might involve each delegate disclosing to 10 other delegates, followed by vouching, followed by 10 more etc
Puh... nice idea .. but for 101 delegates that's > 10 time slots each with 10 transactions containing the secrets for a SINGLE random number .. assuming that this should happen ON the blockchain that would result in a delay of >100sec plus the costs for 100! transactions .. am I wrong?

besides that the scheme sounds solid .. somehow reminds me of ring signatures ;-)

but only if you look from the startingpoint. let's assume that the numbers and secrets productesed all the time so you can all the time generate a number. so the secrets are distibuted in the past and the secrets could be shared in the next block.

Offline FreeTrade

  • Board Moderator
  • Hero Member
  • *****
  • Posts: 700
    • View Profile
Re: Distributed Random Number Generation
« Reply #4 on: September 02, 2014, 06:19:40 PM »
Puh... nice idea .. but for 101 delegates that's > 10 time slots each with 10 transactions containing the secrets for a SINGLE random number .. assuming that this should happen ON the blockchain that would result in a delay of >100sec plus the costs for 100! transactions .. am I wrong?

besides that the scheme sounds solid .. somehow reminds me of ring signatures ;-)

I was thinking of it as a general solution to distributed random number generation - so no need for it to be on the block chain. As long as there is some way to protect against a sybil attack, it might be applicable for a range of uses. But where you have 101 delegates already lined up, that seems like the ideal circumstance. 
“People should be more sophisticated? How are you gonna get that done?” - Jerry Seinfeld reply to Bill Maher


Offline HackFisher

  • Moderator
  • Hero Member
  • *****
  • Posts: 883
    • View Profile
Re: Distributed Random Number Generation
« Reply #6 on: September 20, 2014, 03:15:50 AM »
How to handle failing to disclose or vouching cases if applied to DPOS?

And the process seems requiring transaction to communicate, right?
Anything said on these forums does not constitute an intent to create a legal obligation or contract between myself and anyone else.   These are merely my opinions and I reserve the right to change them at any time.

Offline roadscape

Re: Distributed Random Number Generation
« Reply #7 on: September 20, 2014, 05:38:18 AM »
IIRC, how it works right now is all 101 delegates provide a random hash. These are concatenated and hashed again to produce a random seed.

As long as at least one delegate is honestly random, the result can be trusted to be truly random.
http://cryptofresh.com  |  witness: roadscape

Offline gamey

  • Hero Member
  • *****
  • Posts: 2252
    • View Profile
Re: Distributed Random Number Generation
« Reply #8 on: September 20, 2014, 06:51:52 AM »
IIRC, how it works right now is all 101 delegates provide a random hash. These are concatenated and hashed again to produce a random seed.

As long as at least one delegate is honestly random, the result can be trusted to be truly random.

The problem is if I am a player on the network and collude with the network, the result can be determined before the block is revealed.  So players & a delegate can collude to get a lot of free-plays.
I speak for myself and only myself.

Offline BTSdac

Re: Distributed Random Number Generation
« Reply #9 on: September 24, 2014, 10:25:29 AM »
 the random rely on same input by people , a attaker can try to chage himself input many times to get the random he want , after the konw other`s input.
« Last Edit: September 24, 2014, 10:31:13 AM by BTSdac »
github.com :pureland
BTS2.0 API :ws://139.196.37.179:8091
BTS2.0 API 数据源ws://139.196.37.179:8091

Offline FreeTrade

  • Board Moderator
  • Hero Member
  • *****
  • Posts: 700
    • View Profile
Re: Distributed Random Number Generation
« Reply #10 on: October 07, 2014, 11:27:22 AM »
How to handle failing to disclose or vouching cases if applied to DPOS?

And the process seems requiring transaction to communicate, right?

Participants must either vouch or 'blame' other participants. Where a participant is 'blamed' for not revealing a key where he was required to do, the participants must restart the random number generation.

The process requires communication - perhaps messages on the network, but doesn't require those messages to be stored as transactions.
“People should be more sophisticated? How are you gonna get that done?” - Jerry Seinfeld reply to Bill Maher

 

Google+