BitShares Forum
Other => Graveyard => DAC PLAY => Topic started by: bytemaster 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.
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:
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.
-
+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.
-
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.
-
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)).
-
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.
-
Excellent, thanks Toast and Byte.
-
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.
-
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.
-
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.
-
We could relax the all delegate requirement and just require the last 25.
Sent from my iPhone using Tapatalk (http://tapatalk.com/m?id=1)
-
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.
-
We discussed this yesterday a little bit. It has several benefits but it makes resolving forks more complicated.
-
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.
-
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.
-
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.
-
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.
-
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
-
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.
-
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.
-
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?
-
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.
-
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.
Surprising that the answer in short is No.
http://crypto.stackexchange.com/questions/3049/are-there-any-known-collisions-for-the-sha-2-family-of-hash-functions (http://crypto.stackexchange.com/questions/3049/are-there-any-known-collisions-for-the-sha-2-family-of-hash-functions)
-
@HackFisher
I give you a PM
-
@HackFisher
I give you a PM
Yes, ebit, I understand you, and just waited and checked the http://www1.agsexplorer.com/ (http://www1.agsexplorer.com/). It seems that it did happened.
You know that like BTC, this transaction are recorded on the blockchain, and no one has the power to change it technically. And as it's being part of contract and being a special case with large amount PTS, I think and suggest you might need help from the community and AGS foundation. I can not respond to your PM now.
-
@HackFisher
I give you a PM
Yes, ebit, I understand you, and just waited and checked the http://www1.agsexplorer.com/ (http://www1.agsexplorer.com/). It seems that it did happened.
You know that like BTC, this transaction are recorded on the blockchain, and no one has the power to change it technically. And as it's being part of contract and being a special case with large amount PTS, I think ans suggest you might need help from the community and AGS foundation. I can not respond to your PM now.
Thanks very much.
-
every delegate just create one block in the period of 100 blocks ? if one delegate create two block in latest 100 blocks ?
-
every delegate just create one block in the period of 100 blocks ? if one delegate create two block in latest 100 blocks ?
it's deterministic with dpos, not probabilistic like with proof of work. So it is fixed that 100 blocks are created by hundred delegates.
-
every delegate just create one block in the period of 100 blocks ? if one delegate create two block in latest 100 blocks ?
it's deterministic with dpos, not probabilistic like with proof of work. So it is fixed that 100 blocks are created by hundred delegates.
Right.
-
We discussed this yesterday a little bit. It has several benefits but it makes resolving forks more complicated.
Do you mean http://bitshares.org/documentation/group__dpos.html#dpos_conflict_resolution ?
I guess there won't be much differences between randomness one and 1,2,3,4 one.
Let's say the next miner is decided by RGN(N-2) % 100 and the results are like [2,3,1]. In this case, A,B,C is [2,3,1] and all the same rules in that doc work with [A:2,B:3,C:1] just like [A:1,B:2,C:3]. Notice that I used N-2 which means that it's already decided when current block is not generated yet and the next miner can be ready waiting to resolve the conflicts when it happens. In the worst case, we can use N-100 but I think N-3 could be fine as the possibility of both miners are down is low and in that case the next miner (decided by RGN of last 99) just picks up.
Edit:
In case that one miner doesn't produce block, it's just like ranking changes because we need to choose next next miner by using RNG of last 99. So there's really not much differences between the two from conflict resolving point of view.
-
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.
We can run a delegate for lotto DAC by generating random number from btc blockchain, combined with lotto block header.
People may vote for that delegate if people think this is necessary.
-
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.
We can run a delegate for lotto DAC by generating random number from btc blockchain, combined with lotto block header.
People may vote for that delegate if people think this is necessary.
As soon as you combine data with the bitcoin header you re-introduce the problem of optionality.
-
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.
We can run a delegate for lotto DAC by generating random number from btc blockchain, combined with lotto block header.
People may vote for that delegate if people think this is necessary.
As soon as you combine data with the bitcoin header you re-introduce the problem of optionality.
I mean it is not a built-in mechanism in this DAC, just an option or suggestion for someone to run such a delegate as one of the 100 more delegates. I might be a good strategy for the delegate operator, since each delegate need to publish secret anyway, why not choose a public random seed which can be validated and trusted by the voters?
-
I get your point of optionality that the btc chain delegate's secret is already public once btc block is out, 10 min is enough for a bts round of 100 delegates, so it is meaning less. :(
-
We can not use btc block hash because of its long interval, other choice might be feasible, e.g. using other public feeds like gold price with frequent updates, although more centralized and less pow.
-
You could use the data/entropy from outside the DPOS system that is easily verified then have the delegates arrive at a consensus over that number ?
I can't speak for the difficulty of the code, but if you were to rely on a certain block # from the bitcoin chain and then have your DAC wait for 100 confirmations of the external data then you'd be ok ?
I guess that would require the DPOS delegates have the ability to read and post the btc data/hash/entropy to their own blocks, but I think it could work.
Although it would open you up to being cheated by a btc mining pool. Seems silly, but if you are trying to avoid cheating with large prizes then even this needs to be considered. I suppose a hash of multiple BTC blocks, similar to the basic RNG functionality proposed for DPOS might work ? THen of course it becomes hard for people to verify without a high level of technical knowledge.
-
We discussed this yesterday a little bit. It has several benefits but it makes resolving forks more complicated.
Do you mean http://bitshares.org/documentation/group__dpos.html#dpos_conflict_resolution ?
I guess there won't be much differences between randomness one and 1,2,3,4 one.
Let's say the next miner is decided by RGN(N-2) % 100 and the results are like [2,3,1]. In this case, A,B,C is [2,3,1] and all the same rules in that doc work with [A:2,B:3,C:1] just like [A:1,B:2,C:3]. Notice that I used N-2 which means that it's already decided when current block is not generated yet and the next miner can be ready waiting to resolve the conflicts when it happens. In the worst case, we can use N-100 but I think N-3 could be fine as the possibility of both miners are down is low and in that case the next miner (decided by RGN of last 99) just picks up.
Edit:
In case that one miner doesn't produce block, it's just like ranking changes because we need to choose next next miner by using RNG of last 99. So there's really not much differences between the two from conflict resolving point of view.
@bytemaster, I think we can still introduce randomness into next miner decision and this can prevent most cases of miner cheating.