Bitshares Play FAQ

[FreeTrade]

Yes,  agree, I think I missed the bright ideas from bytemaster.

How about the ticket transactions vote for some from BOD, and not too many so could easy be collected.

Yes, I think while finding a trustworthy entity to make the draw might be workable, a problem it introduces is that the entity might be leant on (by government or criminals). So some decentralized way to choose a trusted agent would be important if going this way.

[HackFisher]

This means I would probably stick with letting the BOD do the drawing because they have a 99% uptime guarantee and are generally trusted.   As long as a single one is honest you are ok.

Think this is probably the best approach put forward so far, but still feels like there might be a better trustless solution.

Yes,  agree, I think I missed the bright ideas from bytemaster.

How about the ticket transactions vote for some from BOD, and not too many so could easy be collected.

Just some ideas from here: http://www.dc.uba.ar/inv/tesis/licenciatura/2010/lerner

How about this way:
When the block round of ticket purchase begins, all the participants select fixed number of players out from BOD, this player provide hash/pubkey together with this block.

After the block is done, the next block these player could publish the priv_keys to generate the random number for that ticket purchase block.
The key point is that, the players are fixed and 99% online, so would be very easy for collecting, BOD thus act as CO-PRNGP Player service.

The leaving problem is only how will the tickets choose limit number the players,  e.g. top 10 voted. all might be too many for collecting.

CO-PRNGP algorithm from that paper:
1) Each player i :
1.1) Chooses a random number ri := RandomNumber(csprng-seed-bit-length)
1.2) Computes cri := H(ri)MPF – Sergio Demian Lerner 44/83
1.3) Broadcasts cri (a commitment to ri )
2) Each player i:
2.1) Broadcasts ri
2.2) For each j, verifies that cri := H(ri)
2.3) Computes S = H(r1;r2;..;rn)
2.4) Uses S as seed for a common CSPRNG.
2.5) Use CSPRNG to generate the symmetric algorithm (CGC) common parameters.
2.6) Uses the CSPRNG to generate c distinct suitable encodings of the real cards in a deck to be
used as open cards. The generated cards are saved in the Open-Deck list.
2.7) Computes dhi := H(Open-Deck).
3) The first player broadcasts dh1.
4) Everybody verifies having computed dhi equal to dh1. If a player detects a mismatch, the protocol aborts

[FreeTrade]

This means I would probably stick with letting the BOD do the drawing because they have a 99% uptime guarantee and are generally trusted.   As long as a single one is honest you are ok.

Think this is probably the best approach put forward so far, but still feels like there might be a better trustless solution.

[HackFisher]

I think there is a natural balance, that's the philosophy.

If we are going to really distribute the randomness ahead of time, that is not enough for us to get that randomness,  we still need to depend on the randomness process of collecting/communicate them later.

Got one advantage, but lose the another one.

[HackFisher]

Well, if I'm an attacker, I can participant as 10 participants and choose not to reveal some of their S. In this way, I'm trying to collide the result. As the target range is relatively small, there're chances that I can win. Furthermore, if I failed, I can choose to publish all the S in the last second. The surety bond can't prevent this. We need to find a firm way to [require "all participants that participate in step 1 must also participate in step 2"].

Yes, if the firm way to [require "all participants that participate in step 1 must also participate in step 2"] is found, then there is no need for participants observation, all honest nodes will check/valid the result according to ticket purchase block(step 1).

[zhangweis]

Well, if I'm an attacker, I can participant as 10 participants and choose not to reveal some of their S. In this way, I'm trying to collide the result. As the target range is relatively small, there're chances that I can win. Furthermore, if I failed, I can choose to publish all the S in the last second. The surety bond can't prevent this. We need to find a firm way to [require "all participants that participate in step 1 must also participate in step 2"].

[HackFisher]

I'm not sure my calculation is right:

Given that the probability space of the lottery Game is N. Given that no requires that all participants that participate in step 1 must also participate in step 2, we need a role to observe who did participate, which could be a bad miner.

Suppose there is one attacker(miner or who select all the publish S in step 3) , and who have several secrets(S) total to M for selection/combination, There will be 2^M attempts. The probability of collision failure is ( (N-1)/N ) ^ |2^M|, which could be very small, in another word, the attacker could probably attack successfully.

Then, if the last trustee is introduced, who can selective publish their only one secret(which mean he only have 2 attempt to collision) at last. Now we have two entity in RNG, miner and trustee, we still should guarantee that bad miner and trustee are not collude.


So the perfect way might be to require "all participants that participate in step 1 must also participate in step 2", which could really distribute the entities who do *not* have the attempt to collude.

[bytemaster]

I mean prepare multiple S values for the same hash(S). But as I mentioned later, if it maybe same difficult as collide a private key for a bitcoin address. So just ignore the previous reply if it's same difficult as bitcoin address hashing.

Roger.. yes this would be sha2 or perhas 512 since bitcoin has weakened sha235

[zhangweis]

I mean prepare multiple S values for the same hash(S). But as I mentioned later, if it maybe same difficult as collide a private key for a bitcoin address. So just ignore the previous reply if it's same difficult as bitcoin address hashing.

[bytemaster]

I am not sure what you mean by collusion in step 2... in step 2 the only attack is 'not revealing your number'... which if we cause this step to reset to step 1 unless everyone reveals then you cannot gain anything.  The most you can do is go another round.   However, if everyone who failed to reveal their number paid those that did from a surety bond then you could delay the selection on the winner, but you could not force yourself to get a win.

It would be annoying, but profitable for the network to collect these surety bonds and it would be costly on the attacker to 'keep it up' long term. 

This means I would probably stick with letting the BOD do the drawing because they have a 99% uptime guarantee and are generally trusted.   As long as a single one is honest you are ok. 

[zhangweis]

Maybe I was wrong if the hash collision is as difficult as bitcoin address hashing. In that case it's easier just to collide for an address with large amount bitcoin. If that's true, I think the way you describe will work perfectly.

[zhangweis]

Now we just have the problem of the last trustee having 64 entries into the RNG and thus selectively publishing his secret.   It seems the only way to prevent cheating is for all participants that participate in step 1 must also participate in step 2 or else lose a surety bond.   If not every participates in phase 2 then the process must restart.   

This means that an attacker could delay the selection of the Random Number so long as they were willing to give up their bond.   

Yes, I meant collision in step 2. As the number to be generated is in a limited range, I think it'll be achieved for an ASIC. To make things worse, the cheater can collide before hand preparing several S1,S2,S3 for the same hash. To prevent this, we may need to use current block's hash in step 3 to avoid prepared collision. Also I doubt surety bond would work. On the one hand, it's too little compared with what the cheater can get. It can avoid loosing anything by publishing the original S in the last second if collision failed. On the other hand, for an honest node, it's too much if any delay happens like network issue or computer issue.

[bytemaster]

I think the entire process can be boiled down to the following process without a BOD.

1) Anyone who wishes to contribute to the Random Number Generation process publishes the hash of their secret  HASH(S).
2) After all HASH(S) has been published all participants have an opportunity to publish S
3) After all participants are given an opportunity to publish their S,   HASH( S[0...N] ) is calculated as the chosen random number.

Anyone concerned about the randomness of the result can participate in the process by publishing two transactions.  Everyone else can simply choose to trust that the others are not colluding.   If there is even one honest individual in the batch then it is secure.   If all of the BOD contribute to the process then it can be assumed that there is a high probability that at least one of them is honest. 

In this way everyone who wants it to be provably fair 'for certain' can know for sure that it was fair if they pay the minimum transaction fee.  Everyone else can simply trust that it is fair and take the risk that everyone else is colluding against them.   Given the value of the network is derived from the fairness of this, the BOD is financial stake in the network, and anyone can prove it fair for their own use I suspect it is a perfect system from a fairness perspective.   It also allocates the cost of making sure it is provably secure to those who care about it the most.

It's much simpler than POW and I like it.
But as it is hash, there might be risk of last publishing person colliding his own hash for different S. HASH(S[0...N]) will make it a bit more difficult but it still can be done if you have huge computation power like ASIC. I think we can require signing using private key instead of hash which is more secure.

The last person cannot do anything because the committed to their value of S... they can choose to reveal or not to reveal but they cannot change the value.  That is why it is a 3 step process.   A SHA256(S) is just as secure or more so than a signature for this application.   No amount of mining can help the attacker here.   

If you wanted to 'attack' then you could publish a whole bunch of entries into the RNG algorithm and selectively reveal... your secrets to generate different outcomes.    Given the combinatorics of the situation I suppose someone that made 64 submissions could have 2^64 different attempts at manipulating the outcome.   To mitigate this particular type of manipulation the trustee reveals their secret last.   

Now we just have the problem of the last trustee having 64 entries into the RNG and thus selectively publishing his secret.   It seems the only way to prevent cheating is for all participants that participate in step 1 must also participate in step 2 or else lose a surety bond.   If not every participates in phase 2 then the process must restart.   

This means that an attacker could delay the selection of the Random Number so long as they were willing to give up their bond.   


 

[zhangweis]

I think the entire process can be boiled down to the following process without a BOD.

1) Anyone who wishes to contribute to the Random Number Generation process publishes the hash of their secret  HASH(S).
2) After all HASH(S) has been published all participants have an opportunity to publish S
3) After all participants are given an opportunity to publish their S,   HASH( S[0...N] ) is calculated as the chosen random number.

Anyone concerned about the randomness of the result can participate in the process by publishing two transactions.  Everyone else can simply choose to trust that the others are not colluding.   If there is even one honest individual in the batch then it is secure.   If all of the BOD contribute to the process then it can be assumed that there is a high probability that at least one of them is honest. 

In this way everyone who wants it to be provably fair 'for certain' can know for sure that it was fair if they pay the minimum transaction fee.  Everyone else can simply trust that it is fair and take the risk that everyone else is colluding against them.   Given the value of the network is derived from the fairness of this, the BOD is financial stake in the network, and anyone can prove it fair for their own use I suspect it is a perfect system from a fairness perspective.   It also allocates the cost of making sure it is provably secure to those who care about it the most.

It's much simpler than POW and I like it.
But as it is hash, there might be risk of last publishing person colliding his own hash for different S. HASH(S[0...N]) will make it a bit more difficult but it still can be done if you have huge computation power like ASIC. I think we can require signing using private key instead of hash which is more secure.

[bytemaster]

I think the entire process can be boiled down to the following process without a BOD.

1) Anyone who wishes to contribute to the Random Number Generation process publishes the hash of their secret  HASH(S).
2) After all HASH(S) has been published all participants have an opportunity to publish S
3) After all participants are given an opportunity to publish their S,   HASH( S[0...N] ) is calculated as the chosen random number.

Anyone concerned about the randomness of the result can participate in the process by publishing two transactions.  Everyone else can simply choose to trust that the others are not colluding.   If there is even one honest individual in the batch then it is secure.   If all of the BOD contribute to the process then it can be assumed that there is a high probability that at least one of them is honest. 

In this way everyone who wants it to be provably fair 'for certain' can know for sure that it was fair if they pay the minimum transaction fee.  Everyone else can simply trust that it is fair and take the risk that everyone else is colluding against them.   Given the value of the network is derived from the fairness of this, the BOD is financial stake in the network, and anyone can prove it fair for their own use I suspect it is a perfect system from a fairness perspective.   It also allocates the cost of making sure it is provably secure to those who care about it the most.