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

[iddo]

Similarly to atomic cross-chain trading (link), I think that a fair coin toss (without the possibility of extortion) can be implemented by selecting the winner via the least significant bit of two committed secrets, as follows:

Edit: Adam Back's protocol in post #37 supersedes this protocol (see also post #49).

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 secret A1 and reveals to Bob the value A2=SHA256(A1), and Bob picks some secret B1 and reveals to Alice the value B2=SHA256(B1)

3. Alice creates a "bet" transaction that takes Alice's input of X coins and Bob's input of X coins, and can be spent by ((Alice's signature + Bob's signature) OR (LSB of (A1 xor B1) is 0, and Alice's signature) OR (LSB of (A1 xor B1) is 1, and Bob's signature)), I mean here that this "bet" transaction has A2 and B2 hardcoded in it, and (A1 xor B1) is computed using OP_SHA256 when the script is executed with the needed preimages.

4. Alice signs the refund transaction that spends those 2X coins back to addresses of Alice and Bob (so each gets X coins back), and has locktime of (say) 300 blocks into the future, and asks Bob to sign this refund transaction.

5. After Bob signs the refund transaction, Alice asks Bob to sign the "bet" transaction and broadcast the "bet" transaction to the Bitcoin network.

6. Alice creates a "Reveal1" transaction that takes as input (say) 3X of her own coins, and can be spent by ((Alice's signature + Bob's signature) OR (revealing some B that satisfies OP_SHA256(B)==B2, and Bob's signature))

7. Alice asks Bob to sign a refund transaction for "Reveal1" with locktime of (say) 100 blocks into the future.

8. Bob creates a "Reveal2" transaction that takes as input (say) 3X of his own coins, and can be spent by ((Alice's signature + Bob's signature) OR (revealing some A that satisfies OP_SHA256(A)==A2 and revealing some B that satisfies OP_SHA256(B)==B2, and Alice's signature))

9. Bob asks Alice to sign a refund transaction for "Reveal2" with locktime of (say) 200 blocks into the future.

10. Bob broadcasts his "Reveal2" transaction, and when Alice is confident enough that "Reveal2" will be mined into the blockchain she broadcasts her "Reveal1" transaction. Depending on the amount X of the bet, Alice can choose the appropriate confidence threshold. For example. if Alice doesn't wait for at least 1-confirmation then it might be risky because Bob could try to broadcast a conflicting transaction (after Alice broadcasts "Reveal1") with a higher fee that spends the 3X coins input of "Reveal2" to an address that he controls.

11. If Bob spends Alices's 3X coins via the transaction "Reveal1" in the next 100 blocks then he reveals his preimage B1

12. Now Alice can spend the transaction "Reveal2" in the next (at least) 100 blocks and thereby reveal her preimage A1, to get back the 3X coins that she lost.

13. Now the winner of the bet can spend the 2X coins to an address of his choice, in the next (at least) 100 blocks.


We can of course replace this 300 locktime number with a smaller number like 6 or whatever. If the client implements this protocol without a need for human intervention then short locktime numbers should be fine. Alice and Bob can broadcast all those transactions before any new blocks are mined, therefore if neither of them is malicious then the winner of the bet will be revealed instantly.

So, is it true that this protocol gives a fair coin toss with no possibilities for extortion and no need to trust a third party, or could someone spot any defects in it?
Maybe someone could come up with a more simple protocol that accomplishes the same goal?

[1714158361]

1714158361

[1714158361]

1714158361

[iddo]

bump

[Meni Rosenfeld]

I think that "fair coin toss" undersells what this is. You can easily do a fair coin toss, the problem this solves is having the loser pay a predetermined amount to the winner without possibility of reneging.

[iddo]

I tried to convince Meni that it cannot easily be done if the party that learns the outcome first can abort and hence bias the result, though it can still be done via gradual release techniques.

So, any comments on this Bitcoin-based coin toss scheme? Anyone?

[iddo]

bump

[gmaxwell]

As you note, the later to release could hold up if they see that they would lose.

I can see ways of compensating for this where disclosures happen one bit at a time so that one party never has more than 1 bit of knoweldge advantage, but those don't result in compact release scripts due to the need to structure the proof as a bit commitment list to prevent unfaithful execution during the reveal.

e.g. your commitment would need to be  H(...H(bit||H(bit||H(bit||nonce)))...)

Though even then it means that a party with a substantial computational advantage could still bias the outcome.


One possibility would be to bond the bet thusly (warning: this protocol is a freeking mess)

Alice and bob one to do a no-renig coinflip.

First alice and bob commit to secrets by sharing hashes of their secrets.

Alice writes a transaction which pays to multisig alice and bob
.. but before announcing, writes two refund transactions:
  One is lock-timed 100 blocks from now, and pays alice's coin to bob.
  The other is not lock-timed, but requires both alice's signature and the preimage to redeem.
After bob signs both of these alice announces the payment into the escrow.

Likewise, bob does the same with the roles reversed.

Now alice and bob do your coinflip transaction, with it's own refund, but the refund is locktimed 300 blocks from now.

If they do not release their secret in time to beat the refund they lose their starting bond.

[Meni Rosenfeld]

As you note, the later to release could hold up if they see that they would lose.

The loser could do this if they're not using iddo's protocol.

The point is that if they use iddo's protocol, the loser can't hold up because he has more tied up (which he'll lose if communications stop) than he has riding on the bet.

If you've found a flaw in the protocol, please share.

[gmaxwell]

The loser could do this if they're not using iddo's protocol.
The point is that if they use iddo's protocol, the loser can't hold up because he has more tied up (which he'll lose if communications stop) than he has riding on the bet.

Ah, I only saw the first three steps and accidentally scrolled past the rest. I went on to propose a spirituality similar protocol. I think thats fine (upto practical details, such as not being able to read the LSB in script; that it falls down if the transactions take longer to confirm than your timeouts, etc).

[Mike Hearn]

Nice one iddo. Perhaps we should add that to the contracts wiki page.

So are you gonna try implementing it?

[iddo]

The loser could do this if they're not using iddo's protocol.
The point is that if they use iddo's protocol, the loser can't hold up because he has more tied up (which he'll lose if communications stop) than he has riding on the bet.

Ah, I only saw the first three steps and accidentally scrolled past the rest. I went on to propose a spirituality similar protocol. I think thats fine (upto practical details, such as not being able to read the LSB in script; that it falls down if the transactions take longer to confirm than your timeouts, etc).

With regard to reading the LSB, there's OP_MOD in the Bitcoin script language that could be used, no?

About the possibility that the transaction would take longer to confirm than the locktime timeouts, note that (unlike your similar suggestion in post #6 here) there is no symmetry between the "Reveal1" transaction of step ( 6 ) and the "Reveal2" transaction of step ( 8 ), so if Alice insists that the "Reveal2" transaction will be mined into a block before she signs and broadcasts her "Reveal1" transaction then we're safe in the sense that the bet is atomic, i.e. either both parties reveal their committed bit, or nothing happens and both parties get their refund. In practice it should be enough for Alice just to see that Bob broadcasted the "Reveal2" transaction, assuming that neither Alice nor Bob control a significant enough amount of the hashpower and that the transaction uses a standard fee (I suppose that it's possible to try to bribe the miners, though I don't really see how to do it under the assumption that the hashpower is decentralized). Edit: this is now mentioned in step (10) of the OP. With 0-confirms it could be easy enough to reverse "Reveal2" and maybe shouldn't even be considered a "bribe", and I remember that we had discussions on more sophisticated bribe attacks (for example link).

[iddo]

Nice one iddo. Perhaps we should add that to the contracts wiki page.

So are you gonna try implementing it?

I'll be honored if it gets added to the contracts wiki, if everyone agrees that there isn't anything unsound here It can be contrasted to the theoretical result that says that any coin toss protocol in R rounds will have 1/R bias, but with a Bitcoin-based protocol it's not so surprising that we can do better when we have a blackbox that lets both parties lock funds and be refunded after a timeout unless some other condition holds.

About implementing it, this idea came up in a conversation after a Bitcoin meetup that Meni organized last month, where there seemed to be an interest in implemented a gambling system that doesn't involve a 3rd-party like SatoshiDice, so we can eliminate the house edge. The person who asked Meni and myself regarding whether it can be done sounded excited about it, so maybe he would like to code it. I'll try to ask.

[gmaxwell]

With regard to reading the LSB, there's OP_MOD in the Bitcoin script language that could be used, no?

Nope, disabled and re-enabling it would require a hardfork. (though it could be replaced with a soft fork and a v2 p2sh)
The best I think you can do now is hash the two secrets and compare to half way through the possible output space.

About the possibility that the transaction would take longer to confirm than the locktime timeouts, note that (unlike your similar suggestion in post #6 here) there is no symmetry between the "Reveal1" transaction of step ( 6 ) and the "Reveal2" transaction of step ( 8 )

I see.

(I suppose that it's possible to try to bribe the miners, though I don't really see how to do it under the assumption that the hashpower is decentralized).

This isn't a great assumption— http://blockorigin.pfoe.be/top.php —, but it's also not your problem. If that assumption fails hard enough the Bitcoins being bet lose their value anyways.

[iddo]

With regard to reading the LSB, there's OP_MOD in the Bitcoin script language that could be used, no?

Nope, disabled and re-enabling it would require a hardfork. (though it could be replaced with a soft fork and a v2 p2sh)
The best I think you can do now is hash the two secrets and compare to half way through the possible output space.

I see, OP_XOR is also disabled so we cannot xor and then get the MSB by using OP_GREATERTHAN to compare with a constant. I guess that we can do nested if/else to get the MSB via OP_GREATERTHAN for each of the secrets of Alice and Bob, though your suggestion to hash the two secrets and then do a single comparison is probably more simple.

[Mike Hearn]

You could also just re-enable the opcodes in a private testnet and explore the ideas there. It's not like OP_MOD or OP_XOR have some deep theoretical problems with them. It's just that nothing used them and someone found bugs in the implementation.

We know there'll be a hard fork at some point for various reasons. If there are thorough tests new opcodes can be activated then. But of course, if there's no useful application that needs them, it's much harder to argue for it.

It seems multiple people studied this protocol by now and there are no issues, so I'll add it in a few days if nobody else comes up with improvements.

This summer Matt and myself gained quite some experience of implementing complicated multi-step contracts protocols when we did the micropayment channels system in bitcoinj. You could use that work as a template. I'm happy to lay out how one might implement such a thing  using bitcoinj, if you like.

[iddo]

It seems multiple people studied this protocol by now and there are no issues, so I'll add it in a few days if nobody else comes up with improvements.

I now edited step (10) of the OP to clarify that the only risk with this protocol is that the "Reveal2" transaction will be reversed. I guess that it's too optimistic to expect that we could have a 0-confirmations protocol with absolutely no risk involved, but any improvements are of course welcome.

This summer Matt and myself gained quite some experience of implementing complicated multi-step contracts protocols when we did the micropayment channels system in bitcoinj. You could use that work as a template. I'm happy to lay out how one might implement such a thing  using bitcoinj, if you like.

Cool. If you prefer to lay it out in a public thread or in the mailing-list or in wiki then maybe more people would begin to implement this kind of protocols. If it's better to do it in private then maybe that can work well too, I'll email this thread now to the persons that I discussed it with.

[Mike Hearn]

Might as well do it here and copy/paste it elsewhere later. Here's the recipe we followed. You don't have to do it the same way, but we at least know this works. Be warning, it takes a lot of effort to do this stuff well.

• Firstly, we added the code to bitcoinj itself rather than a separate library. The advantage is, if/when it gets merged upstream the code will follow API changes and be maintained by me. The bitcoinj API isn't particularly unstable, but it's not frozen either. There's a protocols package where stuff related to non-core-P2P protocol stuff goes.
  
  
• We started with two state classes, one for the client (Alice) and one for the server (Bob). These classes implement a state machine. Here's the code: client / server. As you can see, these classes handle only core logic. They take and create high level objects from the core API, like TransactionSignature, ECKey and so on. There's an enum that is used to track what state the object is in and assertions that verify nothing is done out of order.
  
  
• Next, persistence. After all you don't want the protocol to die if your app crashes or terminates half way through. For that we used the wallet extension mechanism, so the data got stored in the same file as everything else. Extensions are just bags of bytes with some extra logic for things like printing themselves out for debugging purposes. The serialization format we used for this is protocol buffers, but of course you could also just use java serialisation (and in fact the first prototype Matt wrote did exactly that for convenience, but we changed it so it's easier to evolve over time). Code: Client / Server. We also put the code handling timeouts here, using a background thread that waits until the lock time is expired. But I think that's the wrong design and would have written it differently myself - the wallet already gets new block notifications and that's a kind of clock, so it could also trigger broadcasts of expired timelocked transactions that way. It could be changed, or done in the state objects instead.
  
  
• Next, defining a messaging protocol. We used protocol buffers for this because it's easy and brainless to define extensible and efficient protocols with good backwards compatibility and interop with other languages. Protocols I design these days all tend to look like this. You start with a wrapper message that has a type num and then optional fields for each kind of submessage. Protocol definition. Obviously once written the protoc compiler turns the definition into a giant Java class with inner classes for all the submessages, that takes care of serialisation. The message types typically mirror your state machine quite closely, with a few extras like version negotiation and error signalling.
  
  
• Now we bind all the pieces we made so far together (state machines, wallet extensions, protocol definition). This is fairly brainless boilerplate. You need to sanity check the messages as they may come from an attacker, expose event callback interfaces and so on. The protocol binding is itself a state machine, almost but not quite the same as the core state machine (it may include extra states like version management etc). Of course don't forget logging, thread safety, etc. One thing to note here is that we (still!) aren't talking directly to the network. Instead we require the user of the class to provide a callback object that receives formatted protocol buffers for sending, and provide a method that should be called when a message is received. The reason for this indirection is that it's often the case that you want to embed one of these protocols inside another protocol rather than run it raw. The details of how it fits into that higher level protocol may vary (e.g. embedding it inside an HTTP extension looks different to embedding into the control packets of a media streaming protocol).
  
  Client / Server.
  
  
• For demos and testing at least it's useful to actually be able to run it over a network. Fortunately this is mostly boilerplate too. There is a small subpackage in bitcoinj that runs non-blocking IO servers and clients to do this, but I wouldn't use it because it's all in the process of being refactored. I can send you a couple of simple classes that do blocking IO (thread per connection) that just serialise/deserialise length prefixed protocol buffers, it's trivial. So you make a class that accepts a server/port pair, and just a port to bind to on the server side, which just pump data into your lower level client/server classes. Then write a little server app that uses WalletAppKit to bring up P2P network connections, create an empty wallet, synchronise to the block chain, etc. You can do the same thing to write a little command line client app that talks to the server.
  
  Client / Server.
  
  
• It goes without saying that it's a good idea to have unit tests.
  
  
• Finally, of course a command line demo app is all well and good but not something that will get your system into actual widespread usage. For that you need a GUI that appeals to mere mortals. That GUI would need to run on every platform, allow users to load it up with money from a wallet, get their money back out again when they're tired of tossing coins, and ideally look nice as well. Last weekend I checked in a template wallet app that uses Java8 and the latest JavaFX which provides all those features. It's intended to be copy/pasted and used as a foundation for making coin tossing apps, internet radio tuners that spend micropayments, whatever. Code. Video of what it looks like here.

If you're thinking that's a lot of work, well, guess what .... programming is a lot of work!

[oleganza]

My suggestion:

1. Alice and Bob each lock up 3x the amount of bet using special insurance transaction: https://bitcointalk.org/index.php?topic=273539.0

2. Alice shows SHA256(X) to Bob.

3. Bob shows SHA256(Y) to Alice.

4. Then they share X and Y. If first bit of SHA256(X + Y) is 1, Alice wins. Otherwise, Bob wins.

5. Loser sends money to winner using normal transaction.

6. Repeat until they fed up. Then both unlock their deposit from step 1 and go home.

This scheme is super-flexible because they can establish real trust with locked deposit and then play with any rules imaginable without being limited by Bitcoin or anything.

[iddo]

My suggestion:

1. Alice and Bob each lock up 3x the amount of bet using special insurance transaction: https://bitcointalk.org/index.php?topic=273539.0

2. Alice shows SHA256(X) to Bob.

3. Bob shows SHA256(Y) to Alice.

4. Then they share X and Y. If first bit of SHA256(X + Y) is 1, Alice wins. Otherwise, Bob wins.

5. Loser sends money to winner using normal transaction.

6. Repeat until they fed up. Then both unlock their deposit from step 1 and go home.

This scheme is super-flexible because they can establish real trust with locked deposit and then play with any rules imaginable without being limited by Bitcoin or anything.

This doesn't solve the possible extortion scenarios. For example if Alice loses then she can say that she's only willing to pay x/2 coins instead of the x coins that she lost in the bet, and if Bob doesn't agree then he loses the 3x coins that he locked. Another example is that Alice simply aborts after your step (1) and tells Bob to send her (say) 0.1 coins or else his 3x coins will be locked forever.

[Dabs]

How much coins are we talking about that we want to avoid a third-party? Or is this just an academic exercise? For real world usage, just ask a third party. I'll gladly handle your coin toss for 1000 BTC.

Tipping the dealer is optional, but appreciated.

[gmaxwell]

How much coins are we talking about that we want to avoid a third-party? Or is this just an academic exercise? For real world usage, just ask a third party. I'll gladly

steal your coins. Because creating counter-party risk where none is required is absolutely what Bitcoin is about.

Wrong subforum. I tolerate the latest gambling schemes talk when they have some intersection with the actual Bitcoin protocol, software, or technology.  But when you respond telling people not to use technology and to just send you coin, I say— go try the service discussions subforum.