Topic: Distributed gambling https://blockchain.info/tx-index/96964833 (Read 2288 times)

Working in bitcoin is unbearable.
C++ is a terrible language for doing this in. I have been writing my own currencies from scratch in python.

I will make a currency that allows scripts which depend on the hash of the next block.
Winning the game is like trying to guess whether the hash of the next block is even or odd.

I think that every currency should have 1 feature, and do it very well.
There is no reason to make currencies that accomplish so many things as bitcoin tries to accomplish.

OP_MOD and all the other "disabled" opcodes like it were not disabled, they were permanently removed.

They will only be added again if Bitcoin undergoes a soft-fork similar to the P2SH one. If you want that to happen, I suggest you contact Warren Togami and myself instead and write a patch for Litecoin to implement these opcodes.

As for the protocol itself:

You also have the problem that the probability of each player's win is not equally distributed in the common case that the domain size is not evenly divisible by N (as you showed in the single bit example).

I suggest a protocol based on Fiege's leader election protocol. It's a non cryptographic protocol that can be adapted in a crypto context.

The basic protocol:

Let N players choose random numbers. Consider N bins formed by taking each number modulo N, ie:

r_i is in b_0 iff r_i mod N = 0,
r_i is in b_1 iff r_i mod N = 1,
and so forth...

For a round, the chosen bin is the bin with the _smallest_ size, if such a bin uniquely exists. If bin i is chosen, then player i wins.

While Fiege solves this for the boundary cases such as multiple minimal sized bins existing (which is solved by multiple rounds), or the case that N<3, in the context of bitcoin and the blockchain transaction, some other adaptations need to be made. I believe it is possible, but since I'm working on other bitcoin things at the moment, I haven't worked through it. Most are related to the fact that the numbers themselves need to be obscured during the signing process and yet be usable in determining the winner.

Assuming you can do OP_MOD, then you can count the cardinality of each bin to find the chosen bin in coin scrypt.

I agree, you need MOD in order to do this, which itself would imply that integer multiplication and division be enabled also. It should be relatively safe to enable these ops, since these are relatively riskless (compared to floating point) in terms of clients computing different values on the same operation.

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/96964833
This 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