Author Topic: Blockchain RNG with DPOS  (Read 14438 times)

0 Members and 1 Guest are viewing this topic.

Offline Troglodactyl

  • Hero Member
  • *****
  • Posts: 960
    • View Profile
Can there be known numbers where S1,S2 have the same HASH(S)? If yes, delegates can use this to cheat. Say the number is SH. Say I always publish SH and choose S1 or S2 to reveal if I'm the last one in the round. How can I reduce this risk?

This is technically possible, but is cost/time prohibitive.  The entire BTC proof of work system is basically based on how impossible it would be to do this sort of thing.

Offline zhangweis

  • Sr. Member
  • ****
  • Posts: 305
    • View Profile
Can there be known numbers where S1,S2 have the same HASH(S)? If yes, delegates can use this to cheat. Say the number is SH. Say I always publish SH and choose S1 or S2 to reveal if I'm the last one in the round. How can I reduce this risk?
Weibo:http://weibo.com/zhangweis

Offline bytemaster

I believe refusing to reveal should be punished very harshly.  There could be huge economic gain here.  If you are playing a game with a 50/50 proposition and wager 10 BTC.  If I am a delegate and do this when it will be my turn to reveal then my 10 BTC which had 0 expectation, now has 5 BTC expectation (at cost of refusing to reveal punishment).  This can be done in multiple small wagers.  This type of ability will attract nefarious delegates if the barrier to entry is low.

On the other hand if my delegate server goes down during the wrong time I don't want to be kicked off my position as a delegate..  Is there some way a delegate could give their S to another delegate to avoid the situation where they are removed from being a delegate due to network/server fault ?  Some form of redundancy?  I'd hate to lose all the investment towards being a delegate due to at technical glitch. (Possibly server redundancy?)

This also opens up a counter-exploit where someone can be DDOS'd into preventing their S revelation. How can the network decide intent !?

This last revealer aspect may have some underlying truth/law where you basically can not make RNG 100% fair.  I have thought about this stuff before and it always seems to come down to some variation on the problem.

EDIT -

There is another thought I had.  It might very well be that the volume of RNG relying transactions on any given block could be measured.  This volume could be weighed in the punishment phase.  If i refuse to reveal and there was a 10x spike in wagers, then well...  that looks a lot worse than if the volume of transactions relying on the RNG is typical.  Using this sort of technology you could use game-theory type stuff in the punishment phase and might have an alternative workable solution.

It seems like a doubling of the odds for a cheating delegate is difficult to avoid.  Anything that results in a 'redo' is a problem.  If we separate the RND generation from the block headers and move it into the transactions then even missing a block is not grounds for failing to reveal.  This can mean termination for the delegate if they fail to broadcast a valid transaction.

That said, lets look at the financial incentives:
1) A delegate that has 2x the odds, can profit anytime the wager more than their earnings from being a delegate on any game of chance with a better return than 50%.    So in the case of a lottery, a delegate would play every round and eventually they will win the jackpot and make a profit.  The cost of winning the jack pot on average will require 50% of the jackpot size contributed.  So if the lottery is $1M then the delegate would have to put in 500K on average to win the $1M.     For large jackpots this isn't much of a problem and for small jackpots the cost of failing to produce your hidden secret is enough to get you fired from a higher paying job.

2) For large lottery jackpots you will probably just want to rely on a BTC block header.... being dependent upon bitcoin for RNG poses some problems such as RNG speed, but has the benefit of being the most secure RNG we could hope for. 
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 gamey

  • Hero Member
  • *****
  • Posts: 2253
    • View Profile
I believe refusing to reveal should be punished very harshly.  There could be huge economic gain here.  If you are playing a game with a 50/50 proposition and wager 10 BTC.  If I am a delegate and do this when it will be my turn to reveal then my 10 BTC which had 0 expectation, now has 5 BTC expectation (at cost of refusing to reveal punishment).  This can be done in multiple small wagers.  This type of ability will attract nefarious delegates if the barrier to entry is low.

On the other hand if my delegate server goes down during the wrong time I don't want to be kicked off my position as a delegate..  Is there some way a delegate could give their S to another delegate to avoid the situation where they are removed from being a delegate due to network/server fault ?  Some form of redundancy?  I'd hate to lose all the investment towards being a delegate due to at technical glitch. (Possibly server redundancy?)

This also opens up a counter-exploit where someone can be DDOS'd into preventing their S revelation. How can the network decide intent !?

This last revealer aspect may have some underlying truth/law where you basically can not make RNG 100% fair.  I have thought about this stuff before and it always seems to come down to some variation on the problem.

EDIT -

There is another thought I had.  It might very well be that the volume of RNG relying transactions on any given block could be measured.  This volume could be weighed in the punishment phase.  If i refuse to reveal and there was a 10x spike in wagers, then well...  that looks a lot worse than if the volume of transactions relying on the RNG is typical.  Using this sort of technology you could use game-theory type stuff in the punishment phase and might have an alternative workable solution.

« Last Edit: April 19, 2014, 07:11:44 pm by gamey »
I speak for myself and only myself.

Offline HackFisher

  • Moderator
  • Hero Member
  • *****
  • Posts: 883
    • View Profile
Oh... I see what problem you are solving...  I think it would add extra complexity with little benefit.   If a new delegate comes on line then you are trusting 1 out of 99 to be honest instead of 1 in100.

If the delegate candidate generation is not so deterministric, this certainty of unknow S could help prevent attack, this depend on the delegate ecosystem, will the candidates most likely being fresh?

I agree with you that it add complexity but the benefit could be little.

来自我的 GT-N7100 上的 Tapatalk

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

Oh... I see what problem you are solving...  I think it would add extra complexity with little benefit.   If a new delegate comes on line then you are trusting 1 out of 99 to be honest instead of 1 in100. 

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

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.

Offline HackFisher

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

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

  • Hero Member
  • *****
  • Posts: 4001
    • View Profile
  • BitShares: nikolai
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 zhangweis

  • Sr. Member
  • ****
  • Posts: 305
    • View Profile
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.
Weibo:http://weibo.com/zhangweis

Offline bytemaster

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 HackFisher

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

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 zhangweis

  • Sr. Member
  • ****
  • Posts: 305
    • View Profile
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.
Weibo:http://weibo.com/zhangweis