Topic: fair coin toss with no extortion and no need to trust a third party - page 4. (Read 15677 times)

So setup as before using your example, first both parties create a multi-input coin with a game script plus a lock-time refund in case of failure (1 btc each in and 1btc each change and payment after lock-time).

Then normal interactive proof is A->B: witness (w), B->A: challenge (c), A->B response (r)

1. A->B: w=H(a), SIG(A,w) for random a
2. B->A: c=H(b,w,SIG(A,w)),SIG(B,c) for random b
[optional 3. A->B: r=a TEST(a+b mod n > n/2)]

If we say that the signature 2. is valid already and B can claim the winnings just by providing c of the given form and his signature (which verification goes in the original script).  This default win script clause is chosen so it proves who went first because the challenge includes the witness (which includes a signature from A), and the challenge is itself signed by B.

Then we allow an override (higher priority OR or a separable BUT clause) which says A can claim he won instead if he can show that is the case (eg a+b mod n > n/2).

This overcomes the problem that A coming last has an incentive to abort if he loses and wait for the lock-time to return his funds.  If he aborts he already lost.  As he lost his incentive to cheat, he may instead (non-hacked game clients) could actually reveal preimage a even if he lost.  If A does not reveal losing preimages B may elect to not play further games.  The motivation to want preimage a to be revealed normally anyway is that it starts the confirmation clock rolling earlier if users want confirmations, and even with 0-confirmation users probably want to have assurance they won before betting more.

Adam

Can you please elaborate? How would the winner of the bet be chosen if only one party commits?

I should say that the two advantageous properties of the OP are (1) it works with Bitcoin as it is now so there's no need to fork the Bitcoin protocol, and (2) bets of relatively small amounts can be instant because 0-confirmations security is enough.

If we don't care for these two properties, then I think that we can have a much more simple protocol by adding to the Bitcoin scripting language an opcode that puts on the stack the hash of the block in which the transaction resides. This way the script can access a pseudorandom value that neither Alice nor Bob can control, and the winner of the bet can be selected according to (say) the LSB of this value. If Alice has say 10% of the total hashpower then the best that she can do is not to broadcast the block that she solved if its LSB would cause her to lose the bet, i.e. 90% of the total hashpower is working to generate a fair coin toss, 5% of the total hashpower is working to generate a coin toss where Alice wins the bet, and 5% of the total hashpower doesn't participate.

The basic problem of a fair coin toss seems relatively straight-forward.  The hard part is to stop the loser reneging by aborting.  Iddo may or may not have a solution by locking up a multiple of the bet, and making the coin unspendable by forcing the spend to reveal something useful to the other party unlocking.

But I have a simpler more generic new idea - let the committing party win by default, the loser if he loses has nothing to do, and if he wins he overrides the committing party.  It would require the introduction of the concept of an override (like this signature wins, but this signature can override it).

Advantages: less rounds, no extra funds, and script simplicity/clarity.  I would say bitcoin (or perhaps a cryptographically exchange rate locked altcoin) should implement the override concept as it then allows fair games to be defined easily.

Adam

I don't want to further derail the discussion, as this is interesting. But there is a specific site that allows basically a fair coin toss with zero or no house edge. PeerBet. Just limit the raffle to 2 people, and set the amount. Both Alice and Bob now have 50% chance of winning or losing.

Just to clarify, when you play against a centralized service such as SatoshiDice or Just-Dice, there is no third party, i.e. if we use the same terminology then the centralized service is Alice and you are Bob. When these centralized services proclaim that they are "provably fair", they neglect to mention that their protocol only gives "security with aborts", i.e. it's fair only under the assumption that the parties don't abort. So if you bet a very large amount X by supplying your seed that's supposed to be hashed with the preimage of the public value that the centralized server published, then the centralized server can claim "technical error, our data was lost, please try again" instead of revealing the preimage in case it sees that it'd lose. Granted, the reputation of these centralized services is important to them so they wouldn't try to pull this trick, but on the other hand there's a house edge (i.e. it's not a fair coin) because these centralized services are suppose to generate a profit.

The purpose of this protocol is to allow two individuals Alice and Bob to do an atomic fair coin toss, meaning that if either Alice or Bob aborts then nothing happens (i.e. they both retain the X coins that they started with), and if both of them follow the protocol then one of them receives the 2X coins and the other loses, with equal probability. Using an escrow/dealer as you suggested is unneeded, and entails risks. When the amount X of the bet is relatively small then this entire protocol can be instant (0-confirmations security), and when X is relatively large then the parties can wait for the Bitcoin network to generate one or more blocks, according to the security level that they wish to have. This basic protocol could be used on some centralized gambling site where the centralized site just allows individuals to play with each other, or the centralized site can play against an individual in a completely secure way. BTW because Alice and Bob commit a secret that consists of many bits, we can easily do bets with a biased coin where the party who has the worse odds would win the larger amount.

By trying to cheat, Alice puts herself at risk: what if Bob won't play along and let *her* lose her deposit. The first person who breaks the delicate balance of trust increases his own risk. This balance is maintained best when neither party knows much about another (Alice should not know if it was Bob's last money and he is desperate to recover it).

It could work even better when Alice and Bob are completely automated programs with predefined timeouts (leading to deposit destruction). If you try to cheat by modifying your program, you'll simply lose your money — there is nobody to negotiate with. This principle can be used for two nice applications:

1. Automatic coin mixing: your wallet connects to random other wallets, establishes a contract and then they exchange some coins. Both nodes before accepting coins, do their own statistical analysis and may reject a coin if one node doesn't like it. Misbehaving nodes are punished automatically by destruction of the deposit. Since attacker does not really know who he'll be trolling by wasting his own money, it makes very little sense to do so in the first place.

2. Instant payment network based on mesh of nodes that exchange/propagate IOUs from Alice to Bob via Carl and David. Each node has contracts based on bilateral deposits, so nodes come to agreements completely automatically and anonymously. If the debt from one node to another becomes greater than, say, 30% of the deposit, a real blockchain transaction must be created towards the creditor to clear the balance. Misbehaving nodes risk losing more money than they owe. Network could be kept pretty decentralized because big fat nodes with many connections would have to have a lot of money locked up.

Someone has to make an easy to use, practical solution to this. Until then, problems like these keep us "escrow/gambling/sales" people employed.

If they send the coins to me, it's not stealing. (plus, they won't send it without a "contract".)

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.

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.

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.

My suggestion:

1. Alice and Bob each lock up 3x the amount of bet using special insurance transaction: https://bitcointalksearch.org/topic/contracts-without-trust-and-third-parties-273539

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.

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!

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.


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.

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.

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.

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.

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.

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.

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

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

So are you gonna try implementing it?

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