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: A question about random number of DPOS  (Read 424 times)

0 Members and 1 Guest are viewing this topic.

Offline BTSdac

A question about random number of DPOS
« on: April 07, 2015, 12:16:44 PM »

With DPOS we have 100 nodes that should have near 99.9% uptime which means we can reliably produce a secure random number assuming just 1 out 100 is honest.

Code: [Select]
struct Block
{
   hash  secret;  // HASH( S[n] ) where n is the index in the array of secrets generated by this delegate
   hash  revealed_secret; // S[n-1]
};

For each block add a header field containing   HASH(S[n]) where S[n] is a secret to be revealed next time this delegate produces a block.   Also include in the header S[n-1].

We now have a stream of secrets being revealed once per block (15 to 30 seconds)... from this stream of secrets we can generate the random number R for the block as:
Code: [Select]
if( first_block_produced_by_delegate ) then Block[HEAD].revealed_secret = 0
ASSERT( HASH( Block[HEAD].revealed_secret) == GetLastBlockProducedByDelegate(Block[HEAD].delegate_id).secret )
R = HASH( Block[HEAD].revealed_secret )
for( uint32_t i = 1; i < 100; ++i )
{
     R = HASH( Block[HEAD-i].revealed_secret + R) // where + is concat
}

R = random number generated this block...

Every R is calculated from secrets introduced by all 100 delegates that were revealed after they committed to them.  If even one of the 100 delegates is honest then the resulting R is truly random.
if a delegate I call delegate A is the in the end of one round , then he know what is he turn in next round, it is right ? and he have 1/101 chance that he is in the first turn in next round ,
I describe it as 
A|A .   "|" mean the the dividing line between rounds.
it mean delegate A can control the random number of first block of next round (1/101 chance). when this produce end block of previous round .
if one person control N delegates
they have big chance to control the random NO.
control the random NO first block in next round , describe it as   
A|N        chance is N/101

the base reason of this type attack is that , the interval between delegate publish the hash of secret random and reveal the secret hash.  if the interval is zero all the interval delegate are controlled by one person , then there is other random to influence the random,
« Last Edit: April 07, 2015, 02:06:13 PM by BTSdac »
github.com :pureland
BTS2.0 API :ws://139.196.37.179:8091
BTS2.0 API 数据源ws://139.196.37.179:8091

Offline bytemaster

Re: A question about random number of DPOS
« Reply #1 on: April 07, 2015, 12:58:13 PM »
You are correct, the delegate can exactly control that random number which I consider a bug for the purpose of gambling applications. 

Fundamentally any time a delegate gets two blocks in a row they can completely control the random number.

Off the top of my head the only way to prevent this is to divide delegates into groups "A and B" and alternate groups and then shuffle delegates in each group.  This way there is always at least 50 delegates between consecutive blocks. 
For the latest updates checkout my blog: http://bytemaster.bitshares.org
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 bytemaster

Re: A question about random number of DPOS
« Reply #2 on: April 07, 2015, 01:17:22 PM »
Send me a BTS account name and I'll send you a tip for this.  I started a bounty to produce the best algorithm that fixes this issue.

For the latest updates checkout my blog: http://bytemaster.bitshares.org
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 BTSdac

Re: A question about random number of DPOS
« Reply #3 on: April 07, 2015, 01:26:05 PM »
Send me a BTS account name and I'll send you a tip for this.  I started a bounty to produce the best algorithm that fixes this issue.
my name is K1, thank you very much , I actually  I have five methods maybe ( i don`t know) can  solve this  problem , I would find the man with good English help me translate it to English
« Last Edit: April 07, 2015, 01:29:16 PM by BTSdac »
github.com :pureland
BTS2.0 API :ws://139.196.37.179:8091
BTS2.0 API 数据源ws://139.196.37.179:8091

Offline BTSdac

Re: A question about random number of DPOS
« Reply #4 on: April 07, 2015, 01:35:36 PM »
1. before beginning of new round ,   produce delegate turn in the new round using old methods ,
2.check the min delegate interval between previous round and next round ,if the  delegate interval  is small than a constant no, I call N , then replace the place with max delegate interval
3.circle
I think if the N is not a big No. it would convergence rapidly
github.com :pureland
BTS2.0 API :ws://139.196.37.179:8091
BTS2.0 API 数据源ws://139.196.37.179:8091

Offline BTSdac

Re: A question about random number of DPOS
« Reply #5 on: April 07, 2015, 01:42:04 PM »
1.divide the 101 delegates to two groups Acc. to previous round turn ,  A group from 1-67, B group from 68-101,
2.select 33 delegates from A group by random and join them to B group
3. sort delegate turn A group by random ,and make it as 1-34 turn in new round , also sort  delegate turn B group by random and make it as 35-101 turn .

if delegate want to attack  the maybe need to control 33 delegates
github.com :pureland
BTS2.0 API :ws://139.196.37.179:8091
BTS2.0 API 数据源ws://139.196.37.179:8091

Offline BTSdac

Re: A question about random number of DPOS
« Reply #6 on: April 07, 2015, 01:54:53 PM »
1.delegate have to publish two hash of secret random , one is for next round ,and other is for next next round , when he first create a block .
2.delegate reveal the secret random ( its hash had been publish in previous previous round by him )  and publish a hash of secret random that would been reveal in next next round .
the min interval between one delegate publish the hash of secret random and reveal the secret is larger than 101 block ( all delegate)
so maybe he cannot attack as follow
A-2 | XXXXA-1 | A0
when the time is at A0, the hash of secret random that the delegate reveal was published in A-2 ( mean previous two round). so though in the A-1 A can know what turn he in next round , but he cannot change the secret random that its hash was was published in previous two round
github.com :pureland
BTS2.0 API :ws://139.196.37.179:8091
BTS2.0 API 数据源ws://139.196.37.179:8091

 

Google+