If I am re-iterating old information, please point out somewhere where I can learn these things.
Alice and Bob want to each bet a bitcoin. They want one of them to win both bitcoins, and the other to get nothing.
Each person picks either a 1 or a 0 and writes it on a paper.
They show their papers to each other. If the sum is even, Alice wins. if the sum is odd, then Bob wins.
Now Alice and Bob are in different cities, but they still want to play their game.
Writing on a piece of paper doesn't work any more. they could lie about what the paper says over the phone.
Instead, Alice and Bob each hash their own guesses, and first share their hashes.
This makes it so that Alice and Bob cannot change their guesses later.
usually hashes are 1-way functions, so this would work. but in this situation, there are only 2 possible values that Bob and Alice could have chosen, either "1" or "0". So the hash function in this case is not a 1-way function, and it is possible to cheat at the game. (it is like using rainbow tables to crack a password, but the entire table is only 2 entries long)
Say Alice is on the phone with Bob, and Alice says "my number hashes to 5feceb66ffc86f38d952786c6d696c79c2dbc239dd4e91b46729d73a27fb57e9, what does your number hash to?"
Bob could look at that hash, and tell that it is the hash of 0, so bob knows to choose "1" to win.
We need to find a better way of hashing the number. A simple technique is for Bob and Alice to pick BIG NUMBERS. 23 digit numbers in base 256 for example.
We still check to see if the sum is odd or even to determine the winner.
Now when Alice says "my number hashes to 4464817f35f6dd2a3660ea727311c16430dc31710751825a70ee97072efca9d3, what does your number hash to?"
Bob has no way to tell that Alice's number is 14398798798985987987987 which is odd.
Unfortunately op_MOD is currently disabled. This famous transaction found a way around this problem:
https://blockchain.info/tx-index/96964833This solution requires that we have 3 players. This solution is bad, because any 2 of the players could collude to always win against the third person. If the other 2 players are the same person, then you will always lose
First each person selects a number from this list [0,1,2]
Call Alice's number A, Bob's B, and Carol's C.
If the three numbers sum to 0 or 3 or 6, then alice wins. if 1 or 4 then Bob wins. if 2 or 5 then Carol wins.
bob and alice come up with a 23 digit in base 256 shared secret that Carol does not know. call it AB
Alice and Carol come up with a 23 digit in base 256 shared secret that Bob does not know. call it AC
Carol and Bob come up with a 23 digit in base 256 shared secret that Alice does not know, call it BC
Alice computes HASH(A+AB-AC) and shares with the group. (A 1-way function!!)
Bob computes HASH(B+BC-AB) and shares with the group.
Carol computes HASH(C+AC-BC) and shares with the group.
(In order to insure that AB, AC, and BC are 23 digits long, we require that (A+AB-AC), (B+BC-AB) and (C+AC-BC) each be between 20 digits and 23 digits long.)
Notice that A+B+C=(A+AB-AC)+(B+BC-AB)+(C+AC-BC).
This is how the script is constructed: (I may have written pubkeys in reverse order?)
OP_SIZE OP_TUCK 20 23 OP_WITHIN OP_VERIFY OP_SHA256 HASH(A+AB-AC) OP_EQUALVERIFY OP_SWAP
//check that Alice's number has between 20 and 23 digits, then make sure it matches that hash that Alice shared earlier
OP_SIZE OP_TUCK 20 23 OP_WITHIN OP_VERIFY OP_SHA256 HASH(B+BC-AB) OP_EQUALVERIFY OP_ROT
//check Bob's number the same way
OP_SIZE OP_TUCK 20 23 OP_WITHIN OP_VERIFY OP_SHA256 HASH(C+AC-BC) OP_EQUALVERIFY
//Check Carol's number the same way
OP_ADD OP_ADD OP_16 OP_SUB OP_DUP OP_2 OP_GREATERTHAN OP_IF OP_3 OP_SUB OP_ENDIF OP_DUP OP_2 OP_GREATERTHAN OP_IF OP_3 OP_SUB OP_ENDIF
//Hard coding modulus base 3. domain=[0,1,2,3,4,5,6,7,8] range=[0,1,2]
Alice_pubkey Bob_pubkey Carol_pubkey OP_3 OP_ROLL OP_ROLL OP_3 OP_ROLL OP_SWAP OP_CHECKSIGVERIFY
This is how (I think) the script is signed:
winners_signature (C+AC-BC) (B+BC-AC) (A+AB-AC)
------------------------------------------------------------------------------
Why is this a bad solution?
What if Bob and Carol try to collude? Bob knows AB, and Carol knows AC, so they could try computing these numbers:
HASH(0+AB-AC)
HASH(1+AB-AC)
HASH(2+AB-AC)
one of these three will be equal to HASH(A+AB-AC), so Bob and Carol are able to work together to figure out what Alice had guessed.
(this is similar to using rainbow tables to crack a password, but the entire table is only 3 long.)
-------------------------------------------------------------------------------
How we can fix this problem:
PLEASE PLEASE enable op_MOD soon. There is no way to fit enough "OP_IF OP_3 OP_SUB OP_ENDIF" to get rid of the rainbow-tables style attack.
---------------------------------------------------------------------------
If you want to see more stuff like this: 1GbpRPE83Vjg73KFvTVZ4EnS2qNkiLY5TT
