BitShares Forum

Other => Graveyard => DAC PLAY => Topic started by: FreeTrade on August 30, 2014, 10:25:56 am

Title: Distributed Random Number Generation
Post by: FreeTrade 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

Title: Re: Distributed Random Number Generation
Post by: ssjpts on September 02, 2014, 04:21:03 pm
good
Title: Re: Distributed Random Number Generation
Post by: xeroc 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 ;-)
Title: Re: Distributed Random Number Generation
Post by: Shentist 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.
Title: Re: Distributed Random Number Generation
Post by: FreeTrade 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. 
Title: Re: Distributed Random Number Generation
Post by: CLains on September 02, 2014, 07:07:33 pm
I am not in a position to grasp this stuff, but I am happy that you published it for everyone to see  +5%
Title: Re: Distributed Random Number Generation
Post by: HackFisher 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?
Title: Re: Distributed Random Number Generation
Post by: roadscape 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.
Title: Re: Distributed Random Number Generation
Post by: gamey 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.
Title: Re: Distributed Random Number Generation
Post by: BTSdac 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.
Title: Re: Distributed Random Number Generation
Post by: FreeTrade 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.