Bacoor Logo.png

Rock-scissors-paper game with Two-round protocol: When concurrency is not a factor of the game.

March 7, 2018

 

Image source: 

https://dribbble.com/shots/2193123-Rock-Paper-Scissors by Sacha Jerrems.

 

Rock-scissors-paper game is a well-known game in the world. When two people play this game, the important thing is that both of them have to disclose their choice concurrently. However, it seems infeasible to create something concurrent with smart contract and make it work.

This case study is good for brainstorming Ethereum Privacy and in my point of view, Ethereum Privacy will be the next challenge of Ethereum community after Ethereum Scalability.

 

The game

In Rock-scissors-paper game, concurrency helps two people, who try to compete the other, to hide their choice and be impossible to change it when disclosed. In summary, we need a protocol that assures 2 factors:

  1. Two competitors cannot gain any knowledge about the choices in advance.

  2. At disclosing phase, two competitors cannot change their choice.

Fortunately, Two-round protocol is the solution we are looking for. Two-round protocol has two main phases. The first one, submitting phase, each member of game must submit their hash of choice and wait for the competitor submitting. Coming to disclosing phase, only when 2 competitors submitted their hash of choice, that they can submit their raw choice which is without any encryptions. Both of them must calculate again the hash of the other’s choice to make sure it not changed.

 

As you can see, submitting phase helps 2 competitors take the proof of competitor’s choice without any knowledge about the real choice. Finally, the disclosing phase is the phase that verifies the choice and decides who would win.

At this moment, if you pay attention, you will see that it owns a big problem here.

Problem: Assume the choice is presented as a string and has three values which are ‘rock’, ‘scissors’ , ‘paper’. So the hashes (Keccak256) of them are:

 

https://gist.githubusercontent.com/sontuphan/c79a17a7d1cacfbb0a35353043b7a0f1/raw/a0151e090498e9a43a35928f7a787a1868497be2/hashValue.js

 

 

The hash is actually irreversible but the number of values is too small, so they can make a bruteforce attack easily.

 

For example, Victor — victim — is the first person submit his hash of choice in submitting phase and Alice — attacker — tries to guess Victor’s choice and make a choice to compete Victor. Assuming that Victor chose ‘rock’ and submitted: 10977e4d68108… to smart contract. Alice just waits for Victor submitting, gets Victor’s hash, looks for value correspond with the hash. Alice is feasible to know that Victor’s choice is ‘rock’ and then she submits hash of ‘paper’ to compete Victor.

The case above is just a warming-up before I bring you the main course as following, so that you can come to understand how fun of Ethereum Privacy is.

 

Privacy problem of Rock-scissors-paper game

To solve this problem, we need a thing that completely hides the choices but still assures unchangeable. It may have a lot of solutions but in this article I just have presented two solutions I got.

 

One solution is based on mathematic and it uses modulo in detail. One solution is based on an idea used in zkSNARK, it uses secret number but noticing it not a zkSNARK instance.

 

The solution is based on mathematic

Let’s change a little bit about the game. We won’t use ‘rock’, ‘scissors’ and ‘paper’ to present the choices any more. Instead of that, we will use n with mod(3) = {0, 1, 2} as {‘rock’, ‘scissors’, ‘paper’} respectively. And the important thing that n is a secret-random number.

Assume that Victor wanna choose ‘rock’, in order to do that he has to choose random n so that n mod(3) = 0.

 

For example:
n = 13714425016816510474524816299716591239769767123746972631
n mod(3) = 0

 

In submitting phase, Victor hashes n and submits this hash to smart contract. Obviously, Alice has no idea which number Victor chose and submitted by bruceforce attack. To verify Victor’s choice, Alice just only gets Victor’s n at disclosing phase and make a verification.

 

In submitting phase, Victor hashes n and submits this hash to smart contract. Obviously, there’s no chance for Alice to find out which number Victor chose and submitted by bruteforce attack. To verify Victor’s choice, Alice only need to get Victor’s n at disclosing phase then make a verification.

 

The solution is based on secret number

If you have never gotten any knowledge about zkSNARK, you should make sure to read my previous article here.

(And the idea using secret number is in “Zero-knowledge proof with a game for computers” part.)

 

In this solution we don’t need to change the original game but we would change the protocol.

 

Every time Victor or Alice want to submit their hash of choice, they have to pick a secret-random number s and then the hash now is the hash of combination of the choice and s. At disclosing phase, Victor and Alice have to disclose secret-random number s as well as their choice to be possible to verify each other.

 

For example:

https://gist.githubusercontent.com/sontuphan/b70bafb0e21fcef401a551d7b0120b31/raw/feb082d714a330ee771b3a939080e9a5cbbaeeca/hashOfCombination.js

 

 

As you can see, it is infeasible to Alice bruteforce the secret number which Victor chose.

 

In other case, what’s happen if Victor want to change his choice? When Victor change his choice, he also find another secret number s so that new hash of combination is the same as submitted hash of original combination. Theoretically, it is impossible to Victor as well.

 

Conclusion

Generally, we got stuck just because we still think in a box. We may focus too much on concurrency and forget concurrency is just like a solution in real life for two original requirements of the game.

 

In addition, privacy is not only needed to medical documents, KYC systems… but also even games on blockchain. In every field, privacy is existed in a different form but the importance of privacy is undeniable.

 

 

Share on Facebook
Share on Twitter
Please reload

Please reload

Copyright © 2019 Bacoor Inc. All rights reserved.