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: Blockchain RNG with DPOS  (Read 2388 times)

0 Members and 1 Guest are viewing this topic.

Offline bytemaster

Blockchain RNG with DPOS
« on: April 13, 2014, 09:15:33 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.
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 HackFisher

  • Moderator
  • Hero Member
  • *****
  • Posts: 883
    • View Profile
Re: Blockchain RNG with DPOS
« Reply #1 on: April 14, 2014, 03:41:18 PM »
 +5%, simple and beautiful...

So, if we require the least security level of "even one of the 100 delegates is honest then the resulting R is truly random", I think we should draw the jackpots using 100th block's R when there are 100 blocks following since ticket purchase transactions are accepted, right?

Is "Block[HEAD].revealed_secret" the S[n-1] generated by HEAD's delegate in last round (each round 100 delegates' blocks)? Brilliant!

Thanks.
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 amencon

  • Sr. Member
  • ****
  • Posts: 231
    • View Profile
Re: Blockchain RNG with DPOS
« Reply #2 on: April 16, 2014, 12:43:10 AM »
So if I understand correctly, assuming one delegate is honest out of 100, this should give us a steady stream of random numbers to use every 15-30 seconds?

What would this random number look like (depends on hash function used?) and how would it be applied to various games?

For instance in a simple lotto how would you correlate a winning ticket with the random number hash streamed by the delegates?

Looks promising, thanks.

Offline toast

Re: Blockchain RNG with DPOS
« Reply #3 on: April 16, 2014, 12:51:30 AM »
So if I understand correctly, assuming one delegate is honest out of 100, this should give us a steady stream of random numbers to use every 15-30 seconds?

What would this random number look like (depends on hash function used?) and how would it be applied to various games?

For instance in a simple lotto how would you correlate a winning ticket with the random number hash streamed by the delegates?

Looks promising, thanks.

The most basic version has the RNG give you, say, 128 random bits, but you can always use it to seed a pre-determined PRNG to get as many bits as you need.
For a basic lottery ticket: To get a ticket that is valid for one block and has probability p of winning you just define a winner to be any ticket with (block_hash XOR ticket_purchase_tx_hash < p*(2^128)).

Do not use this post as information for making any important decisions. The only agreements I ever make are informal and non-binding. Take the same precautions as when dealing with a compromised account, scammer, sockpuppet, etc.

Offline bytemaster

Re: Blockchain RNG with DPOS
« Reply #4 on: April 16, 2014, 12:55:15 AM »
So if I understand correctly, assuming one delegate is honest out of 100, this should give us a steady stream of random numbers to use every 15-30 seconds?

What would this random number look like (depends on hash function used?) and how would it be applied to various games?

For instance in a simple lotto how would you correlate a winning ticket with the random number hash streamed by the delegates?

Looks promising, thanks.

RANDOM_NUMBER would be a SHA256 hash (32 bytes)

HASH(RANDOM_NUMBER+TICKET_NUMBER) % (TOTAL_TICKET_SALES/YOUR_TICKET_PRICE)  would produce a range from 0 to your probability of winning.   If you purchased 1% of the tickets then it would be from 0 to 100

If the number produced is 0 then you win... otherwise you lose.

« Last Edit: April 16, 2014, 01:07:00 AM by bytemaster »
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 amencon

  • Sr. Member
  • ****
  • Posts: 231
    • View Profile
Re: Blockchain RNG with DPOS
« Reply #5 on: April 16, 2014, 02:44:10 AM »
Excellent, thanks Toast and Byte.

Offline zhangweis

  • Sr. Member
  • ****
  • Posts: 283
    • View Profile
Re: Blockchain RNG with DPOS
« Reply #6 on: April 17, 2014, 02:15:05 PM »
What is the punishment if one delegate doesn't reveal S (by not producing the block in his turn)? Seems the punishment is just like I don't produce block in time? If I'm a delegate which participants the RNG generation, I can publish HASH(S). But if later I found the generated RNG is not the one I wanted, I just don't reveal S and I can have second chance to get another RNG. If I control more than 1 delegates, it's easier and more chances for me to change resulting RNG in this way.
BTC:15hCQrFMpSxcTSDVYgchajEqGF15XqW1M9
Weibo:http://weibo.com/zhangweis

Offline bytemaster

Re: Blockchain RNG with DPOS
« Reply #7 on: April 17, 2014, 04:17:06 PM »
What is the punishment if one delegate doesn't reveal S (by not producing the block in his turn)? Seems the punishment is just like I don't produce block in time? If I'm a delegate which participants the RNG generation, I can publish HASH(S). But if later I found the generated RNG is not the one I wanted, I just don't reveal S and I can have second chance to get another RNG. If I control more than 1 delegates, it's easier and more chances for me to change resulting RNG in this way.

1) Only the last delegate of 100 gets this opportunity to 'take it or leave it', so one could say their odds are 2x better than everyone else.
2) By choosing not to produce a block they risk getting fired and they lose guaranteed profits in the future.
3) What this means is that a dishonest delegate would only not produce a block if they were sure to win.
4) If the lottery only pays out 50% to the jackpot (giving the other 50% to charity) then the most this dishonest delegate could do is break even.

If an attacker can gain control of the last N delegates before the drawing then they would be able to improve their odds by 2^N. 

To solve all of these problems a given round is either all or nothing.  Either all 100 delegates report in or no random number is generated. 
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 HackFisher

  • Moderator
  • Hero Member
  • *****
  • Posts: 883
    • View Profile
Re: Blockchain RNG with DPOS
« Reply #8 on: April 17, 2014, 04:32:23 PM »
If one delegate choose to not produce one block(or its produced block is invalid), will it be fired at once during current producing block, or be fired next round?

If the delegate is fired, the random number still be valid giving that "at least one of previous 99 honest delegates are honest". I think delegate should have it's real related entity (e.g a website), so that once of the entity's delegate get fired, all of the entity's other delegate will be influenced.

And there should not be too many delegate belong to one entity.
« Last Edit: April 17, 2014, 04:37:30 PM by HackFisher »
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: Blockchain RNG with DPOS
« Reply #9 on: April 17, 2014, 05:05:13 PM »
We could relax the all delegate requirement and just require the last 25. 


Sent from my iPhone using Tapatalk
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 zhangweis

  • Sr. Member
  • ****
  • Posts: 283
    • View Profile
Re: Blockchain RNG with DPOS
« Reply #10 on: April 18, 2014, 10:15:37 AM »
If an attacker can gain control of the last N delegates before the drawing then they would be able to improve their odds by 2^N. 

To solve all of these problems a given round is either all or nothing.  Either all 100 delegates report in or no random number is generated.

Well, I have an easier and a more secure idea to solve this. The problem here is that there's no randomness in choosing next miner. This can be easily solved by using generated number [HASH(S1,...S100)] to decide next miner. Say the miner index is M. If the designated miner doesn't produce block in time, miner (M+1)%100 will be designated. Maybe we can use previous 99 S to generate another number to improve the randomness.

It's relatively easier to abandon a number that i don't want(by not producing a block) but difficult or even impossible to generate a number i want. All a cheater can do is just another dice. Thus next miner to generate block(M) is difficult/impossible to control. This ensures every one of 100 has the equal chance to produce a block.

I strongly suggest to apply this to dpos itself. Let's take exchange for example. If I controll M, M+1, M+2, I can manipulate the market(price) for several minutes by excluding some transactions. If next miner M is decided by RGN, the worst I can do is to exclude some transactions for less than a minute and I don't even know when I can do this. This reduces the risk of delegates' controlling blocks very much.
From user point of view, next miner is known when this block is retrieved. Thus this doesn't sacrify efficiency and the wallet/network still knows who to send the transaction to.
BTC:15hCQrFMpSxcTSDVYgchajEqGF15XqW1M9
Weibo:http://weibo.com/zhangweis

Offline toast

Re: Blockchain RNG with DPOS
« Reply #11 on: April 18, 2014, 02:20:00 PM »
We discussed this yesterday a little bit. It has several benefits but it makes resolving forks more complicated.
Do not use this post as information for making any important decisions. The only agreements I ever make are informal and non-binding. Take the same precautions as when dealing with a compromised account, scammer, sockpuppet, etc.

Offline HackFisher

  • Moderator
  • Hero Member
  • *****
  • Posts: 883
    • View Profile
Re: Blockchain RNG with DPOS
« Reply #12 on: April 19, 2014, 01:16:16 PM »
I mean if one delegate refuses to reveal S in time, it also means that it refuses to produce block in time, it should be punished by being fired immediately, and be replaced by another candidate delegate. (It could be the candidate's first time or not, if first time, S=0). If the delegates could be updated more often, it could be bettor...

If one entity have control to X continuous delegates, after the other (100-X) delegates reveal S, then it could calculate out the possible 2^X values in 100th block, 2^(X-1) values in 99th block ... 1 value in current block.

Given that the required interval block count between ticket purchase and draw is V.

The delegate can only precisely attack by purchasing selective tickets in the next (X - 1) blocks, with V=1. the maximum X is 100. If we assume that there no such entity can manipulate all  100 delegate in period. Then we can avoid this precise attack by requiring that the jackpots drawing block should after 100 blocks since purchase (V=100).

The left problem are the odds the bad entity can get, but this advantage is partial, they still need to buy a lot amount of tickets to win. I think the expectation gain of the odds are relatively smaller to their ming revenue, and the delegate/entity could gain bad reputation because of this.
« Last Edit: April 19, 2014, 01:29:24 PM by HackFisher »
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 HackFisher

  • Moderator
  • Hero Member
  • *****
  • Posts: 883
    • View Profile
Re: Blockchain RNG with DPOS
« Reply #13 on: April 19, 2014, 02:19:39 PM »
We can improve candidates by require that any delegate mush provide their init H(S) when registering, so delegate will choose to reveal their S instead of 0 for the first time to produce block.

Given that delegate which refuse to produce block will be fired immediately, we can conclude that if the next candidate are not manipulate by bad delegate, this delegate can not attack then.
« Last Edit: April 19, 2014, 02:22:25 PM by HackFisher »
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: Blockchain RNG with DPOS
« Reply #14 on: April 19, 2014, 04:18:45 PM »
We can improve candidates by require that any delegate mush provide their init H(S) when registering, so delegate will choose to reveal their S instead of 0 for the first time to produce block.

Given that delegate which refuse to produce block will be fired immediately, we can conclude that if the next candidate are not manipulate by bad delegate, this delegate can not attack then.

A delegate has many such S and reveals a new one every 30 minutes.   Initial registration of delegates is irrelevant for this.
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.

 

Google+