Author Topic: Distributed Random Number Generation  (Read 6362 times)

0 Members and 1 Guest are viewing this topic.

Offline FreeTrade

  • Board Moderator
  • Hero Member
  • *****
  • Posts: 700
    • View Profile
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

Offline BTSdac

  • Hero Member
  • *****
  • Posts: 1219
    • View Profile
  • BitShares: K1
 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 gamey

  • Hero Member
  • *****
  • Posts: 2253
    • View Profile
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 roadscape

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 HackFisher

  • Moderator
  • Hero Member
  • *****
  • Posts: 883
    • View Profile
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 CLains

  • Hero Member
  • *****
  • Posts: 2606
    • View Profile
  • BitShares: clains
I am not in a position to grasp this stuff, but I am happy that you published it for everyone to see  +5%

Offline FreeTrade

  • Board Moderator
  • Hero Member
  • *****
  • Posts: 700
    • View Profile
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 Shentist

  • Board Moderator
  • Hero Member
  • *****
  • Posts: 1601
    • View Profile
    • metaexchange
  • BitShares: shentist
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 xeroc

  • Board Moderator
  • Hero Member
  • *****
  • Posts: 12922
  • ChainSquad GmbH
    • View Profile
    • ChainSquad GmbH
  • BitShares: xeroc
  • GitHub: xeroc
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 ;-)

Offline ssjpts

  • Hero Member
  • *****
  • Posts: 538
    • View Profile
    • 中国BTC
  • BitShares: coolman
新浪微博:剑指未来BTS
BTC:1Bc7gRGotktBmnNFr3BUUM22HFXCCTyxor
BTSX ID:loves,集大众之爱,待到BTS 500刀,10%回退给捐赠者,10%用于运营,剩余80%用于爱心事业和BTS宣传推广。

Offline FreeTrade

  • Board Moderator
  • Hero Member
  • *****
  • Posts: 700
    • View Profile
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