fair coin toss with no extortion and no need to trust a third party

[adam3us]

[EDIT: ignore this message it is assuming the old locktime semantics and so is incorrect]

There are mistakes in this version, with reference to my original ref https://bitcointalk.org/index.php?topic=277048.20 specifically

1. Alice and Bob wish to do a fair coin toss where each of them inputs X coins and the winner gets the 2X coins.

2. Alice picks some random secret A1 and sends a private message to Bob with the value A2=SHA256(A1).

3. Bob picks some random secret B1 and sends a private message to Alice with the value  B2=SHA256(B1).

Step 3 is redundant Bob reveals it in step 4 so there is no need to privately send B2 to Alice.

4. Bob creates a "bet" transaction that takes as input 2X of his own coins, and can be spent by: [Alice's signature + Bob's signature] OR [SHA256(A)==A2 AND SHA256(B)==B2 AND (((A xor B) mod 2 == 0, and Alice's signature) OR ((A xor B) mod 2 == 1, and Bob's signature)))]

Bob must broadcast this bet already at this stage.

Agreed except neither OP_XOR nor OP_MOD are enabled.  Can be done probably most simply with (C syntax) !(a && b)||(a||b) (aka infix bitscript OP_NOT(a OP_BOOLAND b) OP_BOOLAND (a OP_BOOLOR b)) or alternatively if (a+b<=2 && a!=b) { ... } (aka a OP_ADD b OP_LESTHANOREQUAL(2) OP_BOOLAND a OP_NUMNOTEQUAL b). btw you see what I mean about using the script notation - even with infix it is terrible!

5. Bob asks Alice to signs a "refund_bet" transaction which spends his 2X coins to an address that he controls, and has locktime of (say) 20 blocks into the future.

Not necessary Bob signs his own bet transaction?

6. Bob broadcasts the "bet" transaction to the Bitcoin network.

No Bob should broadcast his bet transaction before asking alice to do anything (other than provide A2=SHA1(A1) without disclosing A1.)

7. Alice creates a "reveal" transaction that takes as input X of her own coins, and can be spent by: [Alice's signature + Bob's signature] OR [SHA256(B)==B2 and Bob's signature]

Correct but Alice must broadcast this transaction now without requiring anything further from Bob.

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).

I think you have put an extra redundant interlock in here which is not stated in 7.  Bob has to reveal B to Alice and the world, simply to start the game (cash the bet transaction from Alice).

9. Alice broadcasts the "reveal" transaction to the Bitcoin network.

10. Bob redeems the "reveal" transaction by revealing B1 (when he is confident enough that the "reveal" transaction won't be reversed).

11. Alice redeems the "bet" transaction if she won, otherwise she sends A1 to Bob so that he could redeem the "bet" transaction without waiting for the locktime to expire.

It works with Bitcoin as it is now, but whitelisting OP_XOR would make it a little more efficient.

Unless you have OP_BOOLXOR (logical xor ^^ in C syntax, which C lacks) I dont think it helps as you can do i with != (aka OP_NUMNOTEQUAL) if you anyway have to check a+b<=2.

Adam

[1714044782]

1714044782

[adam3us]

Bob writes a transaction that pays into some kind of escrow (TxA). Before announcing the transaction (or taking some other irreversible action, like a reveal) Bob asks Alice to sign a locked refund of that transaction (TxB). Alice signs the locked refund, and then Bob announces the escrow payment (or begins the non-reversible action).

Before the escrow payment confirms, however, Alice announces a  (or one of the many other permissible mutations).  This changes the TXID.  Alice may also have some helpful miners that have agreed to mine the mutant, though this isn't essential.

If TxA' gets mined instead of TxA then TxB will be invalid and so no refund exists.

I think iddo made a mistake in his his write up in presuming the TxA is privately communicated to Bob.  That is not the case: Bob must wait until he sees TxA arrive the broadcast channel before revealing B (simultaneously with cashing Alices $1 bet) to start the game.

In the protocol here, you could refuse to reveal until TxA is confirmed.

Correct, and thats what the protocol requires (though I think iddo's variant does not).

But if Bob broadcasts TxA without a refund already existing, Alice can just walk away and leave bob stuck at that point. "HaHa"

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.

Refer to https://bitcointalk.org/index.php?topic=277048.20

There is no extortion attack.  Mutating TxA or TxB also does not allow any reneging, nor extortion beyond the normal race or 51% attacks that apply to all bitcoin transactions. 

I know this fair bet is a long running problem which have not quite worked because in most variants the loser has to do some thing active to admit he lost, and so he can hostile abort.  But I think I have all eventualities covered via the pay conditional 2x first trick as it reverses the burden so only the winner has to do something active.  Take a look tell me if you see a flaw.

Alice and Bob need to connect to the network using ToR if they are doing 0-commitment games or using some other mechanism to be assured that the other player is not controlling their network or racing them to gain an edge.  (eg maintain connections to a sufficiently large number of large miners to see if they received the transaction).

Note with the introduction of LOCK(txid) I described earlier in this thread I believe you could make this game such that even a successful race/network attack can not take your bet without starting the game, because it would make the bet transactions atomic with each other.  But they could still play normally, but try to abort if they lost by network attack (as described above - try to ensure only you get the payment).

mutant version of TxA,  TxA' which is TxA but it has the S value in the ECDSA signature replaced by S - secp256k1_order

quibble you mean n-s; s-n would be negative, and ECDSA signature verification is defined to verify r and s are in [1,n-1].  (And n-s works because r=[-kG]x = [kG]x ie the x coordinate is the same for k and -k because of the x-axis symmetry of elliptic curves, and s = k^-1(H(m)+rd) where d is the private scalar from Q=dG, and (-k)^-1 = -k^-1, so hence swapping s for -s, -s = n-s.

Adam

[iddo]

No Bob should broadcast his bet transaction before asking alice to do anything (other than provide A2=SHA1(A1) without disclosing A1.)

The locktime support in Bitcoin is quite basic, please read Greg Maxwell's explanation on how it works:
https://bitcointalk.org/index.php?topic=193281.msg2060451#msg2060451
The technical specification is at: https://en.bitcoin.it/wiki/Protocol_specification#tx
And then please review my description of your improved protocol again, to see if there are any mistakes.

It works with Bitcoin as it is now, but whitelisting OP_XOR would make it a little more efficient.

Unless you have OP_BOOLXOR (logical xor ^^ in C syntax, which C lacks) I dont think it helps as you can do i with != (aka OP_NUMNOTEQUAL) if you anyway have to check a+b<=2.

I meant OP_XOR to get the result of the bet in the MSB, and then use OP_GREATERTHAN to compare with a constant (mentioned in post #13 here).

[iddo]

If TxA' gets mined instead of TxA then TxB will be invalid and so no refund exists.

In the protocol here, you could refuse to reveal until TxA is confirmed. But if Bob broadcasts TxA without a refund already existing, Alice can just walk away and leave bob stuck at that point. "HaHa"

BTW, practically speaking, how easy is it to pull off this attack in the current state of the Bitcoin network? The attacker cannot change the fees in the transaction that he mutates, so he could make a separate transaction that pays the miners to replace TxA with TxA' in their memory pool, but there would be nothing that binds this separate transaction to TxA', i.e. the miners could just grab the payment that was given to them in the separate transaction and ignore TxA' ? If the attackers doesn't try to bribe the miners, and instead simply tries to to broadcast TxA' after TxA was broadcasted and thus revealed, what'd be his chances to win the race? There's that IEEE paper that claimed that the average propagation time in Bitcoin is about 12 seconds, so this attack can be practical?

[Mike Hearn]

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.

Usually you can make protocols that work with both forms so it could work across a transition. You set the sequence numbers of the nLockTimed transaction to zero so if it were to be broadcast, it could be replaced with the other tx.

By the way, it's a bit off topic but with respect to mutability, I worked with Ben Reeves to fix blockchain.info+iPhone app so it no longer is generating negative S values. Or rather, the app still does generate them, but they get mutated server side to be of canonical form. Fixing this halved the number of pending transactions from b.i literally overnight.

[adam3us]

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.

I was presuming locktime means just what you said: you broadcast the time-locked transaction and the message order is determined then in terms of double spends, but it is not placed in blocks for mining, but rather held until locktime criteria are met.  (And it may or may not be updatable depending on the value of the latest sequence number).

I'm taking it that was changed, temporarily.  Is there a description of what actually is currently working?  I looked around in the wiki and forum posts referred by iddo, but I do not see it.

Adam

[gmaxwell]

Please remember that our current form of nLockTime is a broken and crippled version of what it was meant to be.

I don't think that the protocols discussed are hurt in the slightest by nodes not accepting and relaying locked transactions. Am I missing something?

For that matter, I'm not sure of any protocols at all that are hurt by nlocktime not being relayed prematurely— other than potentially requiring a separate communications channel—, so I don't think that the relaying of nLockTime will ever be restored.

The anti-dos/prioritization behavior that Gavin wants to change to is in the opposite direction: not allowing the relay of transactions which do not have immediate prospects of being mined (even if they're locked). I've had some concerns about that making attacks easier, but I seemed to stand alone. Perhaps you ought to comment on that point if you think that relaying and mempooling transactions which cannot be mined for many blocks is a desirable outcome.

BTW, practically speaking, how easy is it to pull off this attack in the current state of the Bitcoin network? The attacker cannot change the fees in the transaction that he mutates, so he could make a separate transaction that pays the miners to replace TxA with TxA' in their memory pool, but there would be nothing that binds this separate transaction to TxA', i.e. the miners could just grab the payment that was given to them in the separate transaction and ignore TxA' ? If the attackers doesn't try to bribe the miners, and instead simply tries to to broadcast TxA' after TxA was broadcasted and thus revealed, what'd be his chances to win the race? There's that IEEE paper that claimed that the average propagation time in Bitcoin is about 12 seconds, so this attack can be practical?

This attack has been seen in the wild: people using it to "rerole" losing bets on gambling sites that based win/loss in txid. I can't tell how often it was effective in relative terms since I don't know at what rate it was being performed, but it was clearly successful a fair amount of the time and the gambling site started delaying their responses for transactions with non-trivial value.  Someone attempting this would be successful with some non-negligible rate.

Of course, the mutability will be fixed eventually. So I don't think this undermines your protocol in the long run, but it may be a reason to not use it in earnest soon.

I'm taking it that was changed, temporarily.  Is there a description of what actually is currently working?  I looked around in the wiki and forum posts referred by iddo, but I do not see it.

They just won't be relayed or included until they are almost locked (IIRC we allow them one block ahead? I may be misremembering). You can still share them and replace them via unicast, of course, but the Bitcoin network won't facilitate it.

Though not the goal, non-relaying them simplifies some protocols where you need to create a precomputed refund, since you don't have to go through the effort of doing whatever is required to get a replacement accepted.

[Mike Hearn]

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.

[User705]

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. 

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.

[adam3us]

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).

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:

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

[adam3us]

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:

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

[iddo]

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.

[adam3us]

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

[oleganza]

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.

[jgarzik]

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.

[gmaxwell]

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.

[Peter Todd]

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.

[Mike Hearn]

With the original design, of course it was not a problem for timelocked transactions to be in the mempool because they were replaceable.

[socrates1024]

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.

[User705]

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?