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

[Dabs]

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

[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

...

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.

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.

[iddo]

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.

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.

[Dabs]

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.

[adam3us]

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

[iddo]

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

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.

[adam3us]

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.

Can you please elaborate?

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

[Dabs]

I think what adam3us is saying is that at least one commits, therefore there can be no aborts. Otherwise, the one who aborts loses by default.

Sort of like a disconnection in poker. The software folds your hand if you disconnect or time out.

So it is in the player's best interest to follow through, win or lose.

[adam3us]

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.

Too slow, dice users dont want to wait 10minutes to find out if they won.

This way the script can access a pseudorandom value that neither Alice nor Bob can control

That is the desirable function (fair script RNG function), but its hard to get.  I think my proposal works and is faster, but yes it does fail the no bitcoin changes preferability you mention.  I think its central enough a use-case that maybe there is an argument for adding it anyway.

In terms of how close you can get with existing bitcoin scripts you can play around with lock-time but I dont see how you can solve both the loser aborts problem AND the extortion problem without entangling with a higher valued good behavior incentive as you proposed.

Adam

[iddo]

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

So in your step (2) Bob will broadcast to the Bitcoin network a transaction that references b,c,SIG(B,c),w,SIG(A,w) and spends the inputs of the bet, and if Alice wishes to win the bet then she has to broadcast to the Bitcoin network her competing transaction before Bob's transaction is included in a block, and her transaction will reference a,b,c,SIG(B,c),w,SIG(A,w) to show that TEST(a+b mod n > n/2) passes? And because of the special override op that the script specifies, the miners will respect Alice's transaction and remove Bob's transaction from their memory pool?

Isn't there a timing risk here, where Bob is lucky enough to have his transaction included in a solved block, before Alice managed to reveal that she has won? Maybe we can disallow anyone to spending Bob's output for several blocks and allow Alice to spend the inputs even after Bob's transaction was included in a block, but it's a little messy for the Bitcoin nodes to verify that?

[adam3us]

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

So in your step (2) Bob will broadcast to the Bitcoin network a transaction that references b,c,SIG(B,c),w,SIG(A,w) and spends the inputs of the bet, and if Alice wishes to win the bet then she has to broadcast to the Bitcoin network her competing transaction before Bob's transaction is included in a block, and her transaction will reference a,b,c,SIG(B,c),w,SIG(A,w) to show that TEST(a+b mod n > n/2) passes? And because of the special override op that the script specifies, the miners will respect Alice's transaction and remove Bob's transaction from their memory pool?

The clunkier method would only be used in the hostile "loser aborted" dispute connect scenario. 

Normally as I mentioned you can expect message 3 to always be sent.  These messages can be sent offline privately between the two players.  In normal play (non-hacked client) a single message can be broadcast to the network containing (a,b,c), and this is the normal bitcoin model of a first payment wins.

Isn't there a timing risk here, where Bob is lucky enough to have his transaction included in a solved block, before Alice managed to reveal that she has won? Maybe we can disallow anyone to spending Bob's output for several blocks and allow Alice to spend the inputs even after Bob's transaction was included in a block, but it's a little messy for the Bitcoin nodes to verify that?

What the BUT clause allows is to claim the win if the loser intentionally disconnects.  To avoid problems that you mention, as you also suggest, probably you would want to place a lock-time on the "loser aborted" win proceeds transaction.  The point is I have the proof he aborted in the form of his commitment and the absence of his reveal.  Now if the messages are offline there is one further permutation which is a false "loser aborted" (where party A did receive message 3 but falsely claims not to have) however that is easily remedied by the loser broadcasting message 3.

So I suppose one way of looking at this is it would be simpler if there were a built in mechanism to handle or encode an ABORT outcome to scripts.

I think the point is if there is no method to game the system the user other than DoS, time-wasting etc has no reason to attempt it, and the more efficient protocol can be used.

Adam

[adam3us]

Alright how about this for another tack.

1. A broadcast msg: INPUT(v),h(a), require-script(INPUT(2v),b,SIG(b),TEST(a+b mod n>n/2))
2. B->A private broadcast msg: INPUT(2v),b,SIG(B,b),TEST(a+b mod n>n/2)
3. [optional B broadcast msg: INPUT(2v),b,SIG(B,b)]

basically A broadcasts value v BTC, claimable by anyone who can satisfy the acceptance script.  The acceptance script has to provide a bitcoin transaction with input of 2v BTC, a challenge random value b, and a nested script that this payment must be made if a+b mod n>n/2.

So its like A offers the game round by broadcasting the payment to game script.  B claims the game payment but only by himself committing to 2x the value and a game with a matching script game.

Now there is definitionally no abort possibility because the loser has paid his losing fees up front, and the winner has the proof and aligned incentive to broadcast the claiming transaction.

[EDIT: actually I guess message 2 also has to be public, or input 2v is at risk of being double-spent.  So then message 2 needs a moderate lock-time so that if A loses, B can reclaim.]

The value 2v is not actually broadcast unless A wins it, and so does not tie up the input 2v unless accompanied by preimage b.  So a hostile A cannot achieve a DoS by broadcasting B's private message 2 if A lost.

There would not actually have to be a locktime on message 1 as the user can play himself and always win knowing a, and there being no house fee.

Can bitcoin scripts do the above protocol?

Adam

[iddo]

Isn't there a timing risk here, where Bob is lucky enough to have his transaction included in a solved block, before Alice managed to reveal that she has won? Maybe we can disallow anyone to spending Bob's output for several blocks and allow Alice to spend the inputs even after Bob's transaction was included in a block, but it's a little messy for the Bitcoin nodes to verify that?

What the BUT clause allows is to claim the win if the loser intentionally disconnects.  To avoid problems that you mention, as you also suggest, probably you would want to place a lock-time on the "loser aborted" win proceeds transaction.  The point is I have the proof he aborted in the form of his commitment and the absence of his reveal.  Now if the messages are offline there is one further permutation which is a false "loser aborted" (where party A did receive message 3 but falsely claims not to have) however that is easily remedied by the loser broadcasting message 3.

Since Bob should be able to spend the bet inputs if Alice aborts instead of revealing her committed random secret r=a, we could try to have a nicer option where Bob broadcasts to the Bitcoin network a transaction that must have some sort of locktime which specifies that the Bitcoin miners should keep this transaction in their memory pool and must not include it inside a solved block for the next few blocks, but Bob could still try to mine the block himself or bribe other miners to include his transaction. The thing is that there should be some point in time where it's valid for Bob's transaction to be included in a block, and therefore Bob could broadcast it just before that point in time. So in order to deal with the timing issue, it seems to me that we must allow Alice to spend the bet inputs even after the random value b that Bob chose (and hashed with w and signed) is included in a block. I'm still not sure what'd be the cleanest way to do it, maybe if Alice aborts then Bob should first broadcast some special "reveal" transaction that doesn't specify outputs, and either Alice or Bob could spend the bet inputs after this "reveal" transaction is included in a block. If I'm missing some simple observations and there are cleaner ways to handle the timing issue, please explain.

[Datto]

Interesting points

[iddo]

Hi Adam,

Your post #32 is a little unclear to me: when you say INPUT(2v) I think that you mean that those 2v consist of v that A supplied and v that B supplied (if it's 2v that only B supplies then A will win 2v while risking only v), so it's a bit confusing when you said that B is "committing to 2x the value", maybe I misunderstand?
As far as I know, Bitcoin scripts cannot access the amount of the inputs, in order to enforce this 2v requirement here.

You're saying that with your protocol(s) only one party commits, but we can view it as if B also commits, either by hashing its commitment with A's witness and signing (your post #27) or by just committing the needed coins and some signed value (your post #32), and if A aborts then the data that B committed allows him to win. In post #33 I'm concerned with a malicious B who tries to do a timing attack by broadcasting his data before A has a chance to claim that she won. I think that we must allow A the ability to win even after B's data was included in a block, which is a little messy in terms of what the Bitcoin nodes should verify (and if we add new syntax to Bitcoin scripts then we should beware of potential DoS attacks).

Intuitively, we cannot have a fair coin toss protocol that always works with 0-confirmations security, because we then don't use the PoW irreversibility property that Bitcoin gives us. The question is what's the best way to design a fair coin toss protocol so that the extra complexity of the needed transactions data is used only if the parties are dishonest (i.e. one of the parties aborts). This question is also relevant for the OP protocol, we can do there an instant bet by relying on irreversibility of the "bet","reveal1","reveal2" transactions with 0-confirmations, or the parties can wait for more confirmations as they please if the amount X of the bet is relateively large, but maybe there could be a better way to eliminate the "reveal1","reveal2" transactions when Alice and Bob are honest.

If it's not so important for the bet to be instant, then I still claim that an opcode that puts on the stack the hash of the block in which the transaction resides is the most elegant implementation. I suppose that such an opcode should return e.g. 0 if the transaction doesn't reside in a block yet, because I think that the Bitcoin protocol allows you to have a transaction that spends the output of another transaction where both of those transactions would reside in the same block, even though the Satoshi client disallows it. BTW if we do it for example with Litecoin instead of Bitcoin then the parties will know the result of the bet after 2.5 minutes instead of 10 minutes on average.

[adam3us]

1. A broadcast msg: INPUT(v),h(a), require-script(INPUT(2v),b,SIG(b),TEST(a+b mod n>n/2))
2. B broadcast msg: INPUT(2v),b,SIG(B,b),TEST(a+b mod n>n/2)
3. [optional A broadcast msg: INPUT(2v),b,SIG(B,b)]

it's a bit confusing when you said that B is "committing to 2x the value", maybe I misunderstand?

Well I mean just the value (not the specific coin or payment) and value 2v all supplied by B.  The observation is that a game with two inputs: 1.  v from A and 2. v from B where fairly either A or B claims 2v (double or quits) is the same financial and probability outcome as an alternative game where: 1 A conditionally pays B v, but 2. B can only claim the payment on condition (proven atomically to the block chain) that he fairly offered A a 50:50 chance at receiving 2v.  If A wins the bet, he gets 2v-v=v (B's 2v minus A's earlier paid v); if B wins the bet he keeps the v A offered upfront, as A lost (the preimage didnt meet the requirements).  Its a convenient alternative game structure because then there is no extortion attack as the loser doesnt need to send a message to reveal the fact that he lost.

As far as I know, Bitcoin scripts cannot access the amount of the inputs, in order to enforce this 2v requirement here.

Thats unfortunate.  I suppose generally its the output to a chosen address that matters.  (Inputs being subject to change, unless there is an extra transaction specially to make a 0 change payment).  I guess its still interesting in the sense that it would be good to look at the alternative candidate mechanisms that can most simply, immediately and fairly construct games for addition to the script language.

In post #33 I'm concerned with a malicious B who tries to do a timing attack by broadcasting his data before A has a chance to claim that she won.

The atomicity is probably not present either, ie you want the transaction "signature" claiming A's payment to itself atomically with that create a new transaction from B.  (Then I dont think there is any timing attack, I didnt fully think this atomicity requirement through in the original post).

(If the two transactions are atomic, in fact B could safely use the proceeds of claiming A's payment as one of the inputs to his own 2v payment, meaning that he is not fronting an extra v.)

Intuitively, we cannot have a fair coin toss protocol that always works with 0-confirmations security, because we then don't use the PoW irreversibility property that Bitcoin gives us.

Well it is true that with 0-confirmations bitcoin in general degrade to a network race rather than a mining race.  (Each party has an interest to double-spend his losing bets by having more and lower latency connections to hosts with high mining power; and simultaneously frustrating (eg DoS) his gambling opponent).

If it's not so important for the bet to be instant, then I still claim that an opcode that puts on the stack the hash of the block in which the transaction resides is the most elegant implementation.

I think a delay of more than a few seconds would kill the application.  People would sooner pay small house odds than wait minutes, which even litecoin parameters require.

Adam

[adam3us]

1. A broadcast msg: INPUT(v),h(a), require-script(INPUT(2v),b,SIG(b),TEST(a+b mod n>n/2))
2. B broadcast msg: INPUT(2v),b,SIG(B,b),TEST(a+b mod n>n/2)
3. [optional A broadcast msg: INPUT(2v),b,SIG(B,b)]

OK here's a better, and still round efficient, algorithm that doesnt require any new script features.  Same idea as before player B pays player A $2 with probability 0.5 and then player A pays player B $1 (with probability 1) in such a way that collecting the $1 requires player B to accept the game (reveal enough information to allow player A to claim the $2 with probability 0.5).

But we can do it without requiring atomic simultaneous scripts: just broadcast the $2 first, I think no bitcoin changes required.

1: A->B private msg: h(a)
2. B broadcast msg: $2,{(a'=h(a) ^ b'=h(b) ^ ((a+b>n/2 ^ SIG(A)) v (a+b<=n/2 ^ SIG(B)))) v LOCK(time) ^ SIG(B)}
3. A broadcast msg: $1,{(b'=h(b)^SIG(B)) v (LOCK(time) ^ SIG(A))}
4. B broadcast msg: b,SIG(B)
5. IF a+b>n/2 THEN
       A broadcast msg: a,b,SIG(A)
ELSE
       A->B private msg: a
       B broadcast msg: a,b,SIG(B)

So in words:

1. A sends B h(a),

2. B broadcasts a $2 payment payable to A if A can also show a such that a'=h(a) and show b st b'=h(b) (and of course provide a signature).  

3. A broadcasts a payment of $1 payable to B if B can also show b such that b'=h(b).

4. B cashes A's $1 payment from step 3, and therefore has to broadcast b, SIG(B), so accepting the game.

5. Now A knows b so he can find out if he won.  IF A won (a+b>n) THEN he can broadcast a,b,SIG(A) claiming B's $2 payment ELSE if B won, A should send B privately the value a, then B can reclaim his bet without waiting for the lock time.

There is no financial advantage for aborting as the game only starts proper after step 4 where B claims A's $1 conditional payment accepting the game.  A needs no further input from B to decide if he won or not, so if B aborts A can still claim his win.  If A aborts he loses by default (whether or not he actually would have won had a revealed a).

A should reveal a whether or not he wins because it avoids stalling the game waiting for LOCK(time), presuming that B will want to know if he won or not before playing another round.

Adam

[iddo]

OK here's a better, and still round efficient, algorithm that doesnt require any new script features.  Same idea as before player B pays player A $2 with probability 0.5 and then player A pays player B $1 (with probability 1) in such a way that collecting the $1 requires player B to accept the game (reveal enough information to allow player A to claim the $2 with probability 0.5).

But we can do it without requiring atomic simultaneous scripts: just broadcast the $2 first, I think no bitcoin changes required.

1: A->B private msg: h(a)
2. B broadcast msg: $2,{(a'=h(a) ^ b'=h(b) ^ ((a+b>n/2 ^ SIG(A)) v (a+b<=n/2 ^ SIG(B)))) v LOCK(time) ^ SIG(B)}
3. A broadcast msg: $1,{(b'=h(b)^SIG(B))vLOCK(time)}
4. B broadcast msg: b,SIG(B)
5. IF a+b>n/2 THEN
       A broadcast msg: a,b,SIG(A)
ELSE
       A->B private msg: a
       B broadcast msg: a,b,SIG(B)

So in words:

1. A sends B h(a),

2. B broadcasts a $2 payment payable to A if A can also show a such that a'=h(a) and show b st b'=h(b) (and of course provide a signature).  

3. A broadcasts a payment of $1 payable to B if B can also show b such that b'=h(b).

4. B cashes A's $1 payment from step 3, and therefore has to broadcast b, SIG(B), so accepting the game.

5. Now A knows b so he can find out if he won.  IF A won (a+b>n) THEN he can broadcast a,b,SIG(A) claiming B's $2 payment ELSE if B won, A should send B privately the value a, then B can reclaim his bet without waiting for the lock time.

There is no financial advantage for aborting as the game only starts proper after step 4 where B claims A's $1 conditional payment accepting the game.  A needs no further input from B to decide if he won or not, so if B aborts A can still claim his win.  If A aborts he loses by default (whether or not he actually would have won had a revealed a).

A should reveal a whether or not he wins because it avoids stalling the game waiting for LOCK(time), presuming that B will want to know if he won or not before playing another round.

Adam

Nice! In step (3) it should be "v (LOCK(time) ^ SIG(A))" where the locktime of step (3) is shorter than the locktime of step (2), therefore B cannot cheat by broadcasting the transaction of step (4) right before the locktime of step (2) expires.

This protocol has less communication complexity than my OP protocol, and also before the bet starts it only requires one party to possess 2X coins and the other party to possess X coins, unlike the OP protocol that requires each party to possess >3X coins. In terms of security, it behaves the same as the OP protocol, i.e. 0-confirmations security for relatively small instant bets, and if the parties wish to make sure that the transaction won't be reversed then they can wait for one or more block confirmations.

I'll wait a little for more comments in this thread in order to see that we're not missing anything, and then I'll edit the OP to mention that this protocol improves upon my OP protocol.

[Mike Hearn]

It's good to see the collaborative improvements here - inspiring.

One very tiny request - could you please use regular script form instead of inventing new notations for transactions? I found the non-words version of Adam's protocol a little hard to decipher. In my experience formal notation obfuscates as often as it enlightens.

What script forms would need to be whitelisted to allow for the second form?

By the way, fair warning, if you attempt to implement this expect some objections from people in the USA where various forms of online gambling are illegal. If you can find use cases for this protocol that aren't pure dice games, they might be easier to convince.

[extortion]

if there's no extortion involved, then its not fair to me