Hey guys, I was referred here by gmaxwell. I have come up with a similar protocol although I'm not sure it is implementable in Bitcoin script. One noticeable difference is that mine was designed to support arbitrary odds/payouts. I haven't had time to study the protocol proposed here in detail but it seems quite similar to mine (will comment here when I do). https://bitcointalksearch.org/topic/trustless-gambling-scheme-893077
By the way, has anyone worked on an implementation of this? I'm not sure the increased security would make up for the inconvenience of having to wait for block confirmations for the average gambler (except maybe for large bets).
Topic: fair coin toss with no extortion and no need to trust a third party (Read 15664 times)
December 15, 2014, 09:46:29 PM
January 16, 2014, 03:04:56 PM
Here is my attempt to build a script that accomplishes the goal without using disabled op_codes.
Any advice for me?
signature can look like these:
sigA sigB 1
sigA B A 0
sigB B A 0
op_if
2 2 op_checkmultisigverify
op_else
op_2dup op_sha256 hash(A) op_equalverify sha256 hash(B) op_equalverify op_add op_RIPE160 0a '7ff2' 8x('00')
op_lessthan
op_if
op_else
op_endif
op_checksig
op_endif
63
52 52 ad
67
6e a8 88 a8 88 93 a6 0a 7f f2 00 00 00 00 00 00 00 00
9f
63
67
68
ac
68
Any advice for me?
signature can look like these:
sigA sigB 1
sigA B A 0
sigB B A 0
op_if
2
op_else
op_2dup op_sha256 hash(A) op_equalverify sha256 hash(B) op_equalverify op_add op_RIPE160 0a '7ff2' 8x('00')
op_lessthan
op_if
op_else
op_endif
op_checksig
op_endif
63
52
67
6e a8
9f
63
67
68
ac
68
January 16, 2014, 11:38:32 AM
If 2 people collude, they can always take the 3rd person's money.
We need to enable op_mod
https://bitcointalksearch.org/topic/distributed-gambling-httpsblockchaininfotx-index96964833-418769
We need to enable op_mod
https://bitcointalksearch.org/topic/distributed-gambling-httpsblockchaininfotx-index96964833-418769
December 05, 2013, 07:42:49 PM
So the random numbers are part of the blockchain transaction? How would it work with 3 people?
For N people, every draws a random number between 0 and N-1, you add up all the numbers, and mod by N to determine the winner. The result is uniformly distributed between 0 and N-1, if even one party chooses their number randomly.
December 05, 2013, 07:18:17 PM
Can you describe the process in a plainer way, like to a redneck. It appears that 3 equal inputs ended up in one of the input addresses. It solved the unequal contribution issue but from where does the external coin flip/lottery component comes from?
I can try... but it is a little tricky, so it may take a few attempts before we get a great description.Two people each bet 1 coin, commit to random numbers, and also post an additional 1 coin security deposit. When they both reveal their committed random numbers, the numbers are xor'ed and one of them is chosen as a winner, and gets both coins, and both players get their security deposit back. The only tricky thing is that you need some way to make sure both players actually *do* reveal their random number, rather than just disappearing. This is why the security deposit is important - the *only* way to get your security deposit back is to reveal your random number and finish the game - if you don't do this, the other player gets the security deposit *and* the prize.
How was that? Clear?
December 05, 2013, 06:07:23 PM
Now, can you CoinSwap-ify your protocol so that in the case where everyone plays honestly the fact that they just used a coinflip is not visible in the blockchain? 
December 05, 2013, 04:20:56 PM
Can you describe the process in a plainer way, like to a redneck. It appears that 3 equal inputs ended up in one of the input addresses. It solved the unequal contribution issue but from where does the external coin flip/lottery component comes from?
I can try... but it is a little tricky, so it may take a few attempts before we get a great description.Two people each bet 1 coin, commit to random numbers, and also post an additional 1 coin security deposit. When they both reveal their committed random numbers, the numbers are xor'ed and one of them is chosen as a winner, and gets both coins, and both players get their security deposit back. The only tricky thing is that you need some way to make sure both players actually *do* reveal their random number, rather than just disappearing. This is why the security deposit is important - the *only* way to get your security deposit back is to reveal your random number and finish the game - if you don't do this, the other player gets the security deposit *and* the prize.
How was that? Clear?
December 05, 2013, 03:31:42 PM
Can you describe the process in a plainer way, like to a redneck. It appears that 3 equal inputs ended up in one of the input addresses. It solved the unequal contribution issue but from where does the external coin flip/lottery component comes from?
December 05, 2013, 02:52:48 PM
So, now that the remaining challenges with this protocol have all been solved by academic researchers at University of Warsaw, (see this thread and this paper), and in fact they have demonstrated a real live execution of the 3-player lottery game using Bitcoin transactions (see https://blockchain.info/tx-index/96964833), let's actually build this as a game!
I hereby promise to chip in 0.1btc as a bounty for building an interface (web-based, or even command line script) for two or more players to do the fair coin flip described in the paper.
I hereby promise to chip in 0.1btc as a bounty for building an interface (web-based, or even command line script) for two or more players to do the fair coin flip described in the paper.
September 28, 2013, 07:13:45 AM
With the original design, of course it was not a problem for timelocked transactions to be in the mempool because they were replaceable.
September 27, 2013, 02:59:09 PM
For anti-coercion refund transactions, you actually want them to _not_ be in the mempool... since having them in the mempool will block the legitimate spend. At one point I was going to submit a pull to make penultimate sequence unlocked transaction be non-relayable/mempoolable specifically for that reason, but then we went and made all unlocked transactions non-relayable/mempoolable.
Another example is the nLockTime'd transaction anti-DoS mechanism I proposed for CoinJoin:
For anti-DoS the act of broadcasting these messages can be made expensive by requiring the senders to include a nLockTime'd transaction spending a txin to a scriptPubKey the sender controls. Usually this txin would be used in the mix, although technically it doesn't have to be. The key idea here is that by broadcasting such a tx the sender is guaranteed to spend some tx fees somehow, either in the nLockTime'd tx, or in a different tx with the same txin. The actual amount of fees required per KB of data broadcast can be adjusted automatically by supply and demand.
September 27, 2013, 02:20:30 PM
For anti-coercion refund transactions, you actually want them to _not_ be in the mempool... since having them in the mempool will block the legitimate spend. At one point I was going to submit a pull to make penultimate sequence unlocked transaction be non-relayable/mempoolable specifically for that reason, but then we went and made all unlocked transactions non-relayable/mempoolable.
September 27, 2013, 01:57:18 PM
There is the current proposal for the mempool to be in the model of a very large block. I forget what number we bandied about on IRC -- perhaps (144 * 2 * 1MB) or (144*7*1MB).
For the sake of example, consider a mempool that models a 288MB block, representing anything that miners seem likely to confirm in the next 144*2 blocks.
This would permit the relay of transactions with lock times in the near future, as that would fit within the [proposed] existing mempool logic.
It does not enable the feature years in the future, but it does enable some.
For the sake of example, consider a mempool that models a 288MB block, representing anything that miners seem likely to confirm in the next 144*2 blocks.
This would permit the relay of transactions with lock times in the near future, as that would fit within the [proposed] existing mempool logic.
It does not enable the feature years in the future, but it does enable some.
September 27, 2013, 01:27:18 AM
Please remember that our current form of nLockTime is a broken and crippled version of what it was meant to be. Originally you could broadcast nLockTimed transactions and they would enter the memory pool and block double spends. The transactions could then be replaced using the sequence numbers. This is a better and more flexible system than the one we ended up with, but it got nixed as part of our broken anti-DoS strategy. Eventually the current anti-DoS strategy will be replaced with one that works, and at that point there won't be many (any?) reasons to keep the existing nLockTime behaviour.
Economically speaking, no one is paying for having transactions in memory pool. Today people store transactions very briefly just enough time to get them into block and support Bitcoin for free. The costs are low with great benefits (transactions are moved around quickly which gives value to everyone's bitcoins). However, once you allow some longer-outstanding transactions (say, weeks), then the cost rapidly increases while the marginal benefit decreases: there aren't that many contracts with lock time (and escrow-like contracts may not need quasi-protection against double spends like you describe was done originally). The problem is not in designing a good anti-DoS strategy, but in finding economical incentives to every node keep unconfirmed time-locked transactions for years. And reviewing whether it's really necessary. Also, the security of blocking double spends on mempool level is inherently low.
September 24, 2013, 06:20:33 PM
But that sounds fragile per my comment above: what if the user is using deterministic wallet, and/or does reuse keys. Many users do reuse keys as a matter of practice - eg tipjar addresses, static published addresses, vanity addresses etc. Does that mean that step 8 allows an hostile gambler to use Bob as a blind signature oracle, where he'll sign anything at all?
Well, even if the user does reuse keys in general, he will be safe if for each coin toss session he will generate a fresh key for the refund transaction, because the attacker could only ask him to do a blind signature with this fresh key.
Got it. So we have a slightly improved solution, except that its vulnerable to mutable signatures until those are fixed.
Adam
September 24, 2013, 04:38:47 PM
But that sounds fragile per my comment above: what if the user is using deterministic wallet, and/or does reuse keys. Many users do reuse keys as a matter of practice - eg tipjar addresses, static published addresses, vanity addresses etc. Does that mean that step 8 allows an hostile gambler to use Bob as a blind signature oracle, where he'll sign anything at all?
Well, even if the user does reuse keys in general, he will be safe if for each coin toss session he will generate a fresh key for the refund transaction, because the attacker could only ask him to do a blind signature with this fresh key.
September 24, 2013, 02:45:00 PM
Quote from: iddo
8. Alice asks Bob to signs a "refund_reveal" transaction which spends her X coins to an address that she controls, and has locktime of (say) 10 blocks into the future (if she exposes the entire "reveal" transaction rather than just the txid of the "reveal" transaction then she has to be confident enough here that the "bet" transaction won't be reversed, otherwise she would have to be confident enough that the "bet" transaction won't be reversed before doing the next step).
If Bob is not paying attention cant Alice trick him into signing over his life savings there? Signing a blank cheque to someone else's address without knowing whats in it. How does Bob know its not spending one of his own bitcoins (eg managed by a different client, but with the same private key imported)? Does the serialization make that obvious or partly disclosable? Otherwise that seems quite unsafe.
And now I understand iddo's previous comment on this type of attack earlier in this thread:
Quote from: iddo
Not sure if you mean something else than the danger of tricking the user to blindly sign a transaction that spends some other output that he controls instead of the supposed refund transaction. We have discussed it on IRC once (link (http://bitcoinstats.com/irc/bitcoin-dev/logs/2013/05/14#l1368497979)), where you explained that there's no danger if the user never re-uses the same pubkey more than once, if I understand correctly what you said is true because the attacker couldn't specify the user's pubkey in the transaction that spends the output (though the attacker could extract the pubkey from the signature afterwards, so if he could convince the user to sign again then the attack will succeed, assuming that they user had an output that's controlled by the same ECDSA key as the key that he used for the refund transaction). But are you referring to a different danger here?
But that sounds fragile per my comment above: what if the user is using deterministic wallet, and/or does reuse keys. Many users do reuse keys as a matter of practice - eg tipjar addresses, static published addresses, vanity addresses etc. Does that mean that step 8 allows an hostile gambler to use Bob as a blind signature oracle, where he'll sign anything at all?
Adam
September 24, 2013, 02:34:21 PM
I'll attempt to fully describe Adam's protocol here.
Please see if the language that I use is clear enough, and whether you agree that the risks of double-spending are pinpointed correctly (in step 8 and step 10).
Please see if the language that I use is clear enough, and whether you agree that the risks of double-spending are pinpointed correctly (in step 8 and step 10).
OK with my now more up to date understanding of locktime (thanks gmaxwell) I agree with your summary. Its a pity that locktime doesnt work as originally defined as I think it slightly simpler, and also it would've been nice if lock time was a boolean function (so one could directly write things like X OP_OR lock(time) ) but it seems you can fix it (in this case at least) with an additional round of signatures.
However I have a bit of a concern about this step:
Quote from: iddo
8. Alice asks Bob to signs a "refund_reveal" transaction which spends her X coins to an address that she controls, and has locktime of (say) 10 blocks into the future (if she exposes the entire "reveal" transaction rather than just the txid of the "reveal" transaction then she has to be confident enough here that the "bet" transaction won't be reversed, otherwise she would have to be confident enough that the "bet" transaction won't be reversed before doing the next step).
If Bob is not paying attention cant Alice trick him into signing over his life savings there? Signing a blank cheque to someone else's address without knowing whats in it. How does Bob know its not spending one of his own bitcoins (eg managed by a different client, but with the same private key imported)? Does the serialization make that obvious or partly disclosable? Otherwise that seems quite unsafe.
Adam
September 24, 2013, 12:10:42 PM
Correct me if I'm wrong or maybe gmaxwell can call me a redneck again but under this concept one party has to lock up double the coins of the other party don't they? Who would want to be that party? A bitcoin right now is worth more then a bitcoin 1000 blocks from now so some party will always be at a disadvantage even if it is a slight one.
Quote
No the protocol is that it happens in this sequence: 0. player A gives player B A2=H(A1), 1. $2 TxB bet broadcast, 2. $1 TxA play broadcast, 3. player B cashes TxA simultaneously revealing B1, 4. player A if she won (a+b<=2 && a xor b) can now cash TxB which relies on revealing A1, 5. player A if she lost should still reveal A1 to Bob so he can cancel early without waiting for the time lock.
Player A if won wins full value but if lost player B doesn't get full value unless player A does early release. September 24, 2013, 11:33:30 AM
Yeah, they're considered non standard so won't enter the memory pool and block double spends any more.
I'm OK with not relaying transactions that won't get mined any time soon, the point of contention being what should "immediately" mean. If you work backwards from how much memory the node is allowed to use, that's better, but I don't think we're close to that yet.
I'm OK with not relaying transactions that won't get mined any time soon, the point of contention being what should "immediately" mean. If you work backwards from how much memory the node is allowed to use, that's better, but I don't think we're close to that yet.
Jump to: