Bitcoin Forum

Similarly to atomic cross-chain trading (link (https://bitcointalk.org/index.php?topic=193281.0)), 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 (https://bitcointalk.org/index.php?topic=277048.msg3210328#msg3210328) 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?

bump

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.

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?

bump

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.

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.

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

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

So are you gonna try implementing it?

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 (https://bitcointalk.org/index.php?topic=122291.0)).

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.

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

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

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 (https://code.google.com/p/bitcoinj/source/browse/core/src/main/java/com/google/bitcoin/protocols/channels/PaymentChannelClientState.java) / server (https://code.google.com/p/bitcoinj/source/browse/core/src/main/java/com/google/bitcoin/protocols/channels/PaymentChannelServerState.java). 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 (https://code.google.com/p/bitcoinj/source/browse/core/src/main/java/com/google/bitcoin/protocols/channels/StoredPaymentChannelClientStates.java) / Server (https://code.google.com/p/bitcoinj/source/browse/core/src/main/java/com/google/bitcoin/protocols/channels/StoredPaymentChannelServerStates.java). 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 (https://code.google.com/p/bitcoinj/source/browse/core/src/paymentchannel.proto). 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 (https://code.google.com/p/bitcoinj/source/browse/core/src/main/java/com/google/bitcoin/protocols/channels/PaymentChannelClient.java) / Server (https://code.google.com/p/bitcoinj/source/browse/core/src/main/java/com/google/bitcoin/protocols/channels/PaymentChannelServer.java).
  
  
• 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 (https://code.google.com/p/bitcoinj/source/browse/core/src/main/java/com/google/bitcoin/kits/WalletAppKit.java) 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 (https://code.google.com/p/bitcoinj/source/browse/examples/src/main/java/com/google/bitcoin/examples/ExamplePaymentChannelClient.java) / Server (https://code.google.com/p/bitcoinj/source/browse/examples/src/main/java/com/google/bitcoin/examples/ExamplePaymentChannelServer.java).
  
  
• It goes without saying that it's a good idea to have unit tests (https://code.google.com/p/bitcoinj/source/browse/core/src/test/java/com/google/bitcoin/protocols/channels/PaymentChannelStateTest.java).
  
  
• 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 (https://code.google.com/p/bitcoinj/source/browse/#git%2Fwallettemplate%2Fsrc%2Fmain%2Fjava%2Fwallettemplate). Video of what it looks like here (http://www.youtube.com/watch?v=0h_1pM_phuc&hd=1).

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

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.

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.

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. :P

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

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.

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.

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.

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

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.

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

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.

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


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

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?

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.


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

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

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.

Interesting points

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.

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.


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.


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


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


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

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

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.

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.

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

Flip a coin to determine who starts a game of basketball, soccer, pool, random olympic sport, who plays white in chess ... that the coin flip has value in and of itself is just a bonus.

You don't need to use this protocol unless you want money to be at stake. Nice try though.

Oops, fixed.


Correct. 


I dont think anything new needs to be enabled if this is up to date https://en.bitcoin.it/wiki/Script though it would be nicer to have OP_MOD enabled otherwise you have to implement OP_MOD using OP_LESSTHAN and OP_SUB and OP_IF / OP_ELSE (which is very easy but seems kind of stupid).  (if a > n or b > n then reject; endif; if a+b > n then if a+b-n > n/2 then true else if a+b >n1 then true; endif; endif VS if a+b mod n>n/2).

I do think it would be simple and useful to be able to be able to enforce an ordering on related transactions.  eg say LOCK(txid) meaning this transaction is not to be considered valid until the transaction with that txid has been accepted by the node.  That would be enough to prevent one of the network attacks on 0-confirmation games (that an opponent B cannot hack the other parties network to delete unfavorable messages - eg the relay of B's losing transaction, or the collection of A's win message (causing A to lose by default)).


Notation was troubling me.  You may notice even my notation changed between the two posts.

One problem is the literal script notation is terrible: reverse polish, stack language; long strings for standard operations like +, <.  Is there any mathematical version of that notation eg using C operators.  I was thinking maybe we could define one by applying mathematical PoK notation.  PoK[m]{(x):y=H(x) ^ SIG(A)} meaning a signature on message m with secret x, such that y = H(x) and a signature from public key A.  Or simply an infix rendering of the stack language using C syntax operators and functional notation?



Someone else posted some examples in the thread now I see.

Not my area but I strongly think bitcoin foundation should obtain some international legal advice on the best jurisdiction for the legal entity to be domiciled in.

Adam

Maybe there would be a structured (financial) product use case where different payouts are made depending on the outcome.  eg One I bought and both made and lost some money on: for a period of 3 years I am paid 9% interest on my capital, if 4 stock indexes remain above 50% of their opening value (nikkei, ftse etc).  If any index falls below 50% I end up owning that index.  As I recall it was also 50% capital guaranteed (I lose no more than 50% of my capital).

These products are sometimes made by investing 95% of the capital that compounds back up to 100% over the term to provide the capital guarantee, and then using the 5% to buy some leveraged derivatives to construct the potential upside.  But I think the above one needs a matching insurance buyer (they are buying insurance that the indices they invested in do not fall by more than 50%).  So for that kind of thing you need a collection of conditional, dependent (cant renege on your part after the other party made their commitment) and time limited contracts.

Smart contracts should allow such things without paying credit suisse et al 5% of capital upfront to write the contract.

Hence the analogous need to interlock the contract clauses relating to different events where different party has to pay out at various times.

There's no actual randomness in the above contract other than the markets.  Some of them might be really close to random events.  Maybe there is a case to make for products where you get to make a bet on some provably random element eg bet on 2 of 4 indices fairly chosen, just to spice up the financial product.

Anyway it doesnt seem to me that you could likely create a language that allows the above to be built but prevents a game of dice.  Maybe countries that allow financial gambling with OPM (other people's money) but not fair dice games can content themselves by making those bitstrings illegal for users in their jurisdiction.  We know how well that works, but if they say so.

(The general idea that iddo started with to require successive disclosures to proceed to the next protocol step is related to the interlock protocol).

Adam

Oh, hey, I just noticed your sig, Adam. You never know who you're talking to. Don't mind me, I'm just trying. Altho it seems you're the type of person who would do something to annoy some government just because you can.

Here's a better example, more directly related to the fair randomness aspect.  Fair lotteries for resources.  its relatively common for there to be economic situations where competing parties want a scarce resource, and other than an auction, sometimes lotteries are used (the bidding company pays some amount of money to get the frequency allocation, and the lottery winner gets the frequency).  Maybe there is a bid cost and a completion cost for the winning bidder various permutations possible.  Similarly lotteries have been used for domain management contract allocation.  

These situations can be potentially high value so it can be important that the contract is demonstrably fair, which means without the need to trust any third parties, and that area is one of the main strengths of smart contracts is to reduce the reliance on trusted third parties.  It removes intermediary fees, bribery, fraud, hostile contract breaking and so forth.

Adam

Not really ("annoy some government just because you can"), and in fact it could easily be counter-productive to pick a PR/media fight, so I am actually quite circumspect and deliberate, though I do find the stuff Jon Matonis writes pretty amusing.  You may remember Satoshi was annoyed that people were being encouraged to donate to wikileaks - he thought it was too early, though presumably he was not against the principle of political donation, just the premature risk.   Unlike some people I respect such logic , there is a time as well as a principle.

My comment was that government policies are usually on the wrong side of  progress and history.  Falkvinge wrote some good articles about such things.  In hindsight society can see the wrongness of previous misconceptions, bigotries, injustices etc. but its interesting to understand that analogous things are happening now, which in the future will equally be seen as short-sighted, archaic and stupid thinking.   Sometimes such things are not obvious to see as our thinking is coloured by language, PR, conventions etc.  I think historically government has been on the wrong side of most such problems.  Falkvinge suggets we're currently in one such rut around copyright policy, the concept that society could or should regulate copying of bitstrings or which bit strings are allowed.  Or the compatibility of such regulation with free speech, censorship free communication, privacy of communication, freedom of association and right to use encryption in the pursuit of such rights.

Adam

That reminds me, governments usually make public biddings for projects such as systems, infrastructure and equipment. The tendency is for the lowest bidder to win, regardless of quality. Or oddly, sometimes these things are already fixed and the bidding is just for show, with the unfortunate losers unaware they are wasting their time.

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

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

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

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.

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

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]

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

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.

Unfortunately no protocol which requires a blind refund transaction can be completely secure in the Bitcoin network as it exists today.

(The reason may be obvious to you if you think about it for a bit.  I'll gladly describe it, however, if no one else is aware of anyone currently using blind refund transactions right now.)

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?

Anyway, for the fair coin toss protocol, it's fine to have non-blind refunds, i.e. in step (5) Bob will send Alice the entire "bet" transaction, and Alice will create the "refund_bet" transaction on her own, sign it, and send it back to Bob.

The fair toss problem that requires either party to do something after the outcome is determined will never work because of both the bribe/extortion issue in frozen coins and also prisoners dilemma.  I'm a protocol newb so bear with me if what I say sounds stupid.  The way I see it is you have to remove both Bob and Alice from any type of auctions besides just the bet if you want this to work.  Is it possible for them to spend coins to a multisign address and then simultaneously sign two transactions from that address that reference an outside network event that determines the winner.  For example payment to Bob is valid if the next block hash is divisible by 2 and payment to Alice is valid if next block hash value isn't divisible by 2.  Both transactions are broadcast but only one gets included in the block after next block.

blah blah. Please read and understand the darn thread first!

Yes. I can't find any evidence of usage which would be imperiled by pointing it out— so:


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 mutant version of TxA,  TxA' which is TxA but it has the S value in the ECDSA signature replaced by S - secp256k1_order (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.

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"

Basically until all forums of mutability in transactions are fixed by blockchain rule no protocol which requires a refund exist before a transaction which can be confirmed is completely safe, because _anyone_ can change the txid of a transaction until its buried in the chain, and child transactions reference parents by TXID. :(  There are many kinds of mutability, we've been slowly chewing away at some of them by making them non-standard but we're still a long way away from the soft-forks which would start making mutability vulnerable protocols safe.

There's no need for the blah blah.  I'm pretty sure I prefaced this by saying I'm new at this.  I didn't know you can delay transactions.  What happens if you spend the coins from that address prior to that?  If I have the private key to an address from which a delayed transaction occurred can't I simply try to double spend it before the delay runs out?

Please spend some time reviewing and understanding the protocol listed here before commenting on it. If you don't understand what a particular step means, ask about that.

Otherwise you're just a redneck standing on the launch pad saying "This moon launch thing can't work— every rock I've seen thrown comes back down, even if bubba throws it, and bubba is super strong". :P

The whole idea of this thread is that it resolves the extortion risk you're commenting about. Thats the point. Maybe it fails to actually do that because of some really subtle detail, but people who are not new at this think otherwise.

I see, so I guess that the problem here is that the blockchain rule doesn't force S to be a value between 1 and secp256k1_order-1 :(


Right, I see. Bob already signed the transaction and if Alice can mutate it and thereby invalidate the refund then she can easily extort Bob, because the transaction locked coins that belonged only to Bob, and now without the key that Alice holds it's impossible to redeem these coins.

The current known sources of mutability:

OpenSSL will tolerate many different invalid forms of the DER encoding for the signatures. E.g. ones with extra bytes just stuff into the end, or where the values are coded as negative numbers. These are now not relayed or mined by current node versions, but they're still permitted in blocks.

S value can be flipped and still result in a valid signature. This is permitted everwhere with no inhibition and transactions are randomly in one form or another. The next version of Bitcoin-QT will always use the smaller value... but it will likely be years before this is fixed, especially because some client developers may refuse to adopt the canonical behavior.

ScriptSigs can have extra opcodes stuffed into them that do nothing. These are mostly not relayed or mind but they're still permitted in blocks.

ScriptSig pushes can be in non-canonical form. E.g. using a push type that allows larger values than was strictly needed.

We may be able to hasten fixing these things by defining a TX version 2 that has them all enforced and perform a soft fork fairly rapidly.  At least then legacy stuff wouldn't be broken by the fixes.

Haha that's exactly how I felt when I started reading about bitcoin and the whole signing transactions with crypto.  I admit I understand it conceptually but not actually.  However I do ok in real life and I can see that any time you spread out two party actions with varying time frames it doesn't matter the protocol one party will be at an advantage over the other and after that it's only a matter of exploiting the advantage with percentages.  If someone has to go 1st or sign 1st so to speak then their advantage is gone.  Also there is the issue of people valuing the coins differently.  Lets say a system exists where you have to honor the bet or lock up however many times coins indefinitely by both parties.  Well a business competitor to another business may very well be willing to do that if it drives the other out of the marketplace so you can't even assume that both parties will act logically because of possibly different values.

BTW where can I find out more about these delayed transactions?

@User705, I don't understand it completely, so I'm not even starting to comment on the scripts and details and transactions. I do understand, in a way that what they are attempting to do is possible, but tricky.

I also understand, it's a lot simpler to apply some faith to humanity, thus the existence of human escrow agents you can trust. However, programmers are programmers, geeks are geeks, they will find the solution to this problem and we are all the more better for it.

A bit OT, but the "Mental Poker" protocol is what gave birth to all sorts of crypto techniques that we use today.

[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


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


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!


Not necessary Bob signs his own bet transaction?

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


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


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



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

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.


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


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


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

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.


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

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?

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.

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

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 (https://github.com/gavinandresen/bitcoin-git/commit/378f9a253e158c8fcf9a03de1087ca5d794790de#L0R301): 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.

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.

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.

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.

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.  Player A if won wins full value but if lost player B doesn't get full value unless player A does early release.

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:


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

And now I understand iddo's previous comment on this type of attack earlier in this thread:


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

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

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.

There is the current proposal for the mempool to be in the model of a very large block.  I forget what number we bandied about on IRC -- perhaps (144 * 2 * 1MB) or (144*7*1MB).

For the sake of example, consider a mempool that models a 288MB block, representing anything that miners seem likely to confirm in the next 144*2 blocks. 

This would permit the relay of transactions with lock times in the near future, as that would fit within the [proposed] existing mempool logic.

It does not enable the feature years in the future, but it does enable some.

For 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:

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

So, now that the remaining challenges with this protocol have all been solved by academic researchers at University of Warsaw, (see this thread (https://bitcointalk.org/index.php?topic=355174.0) and this paper (http://eprint.iacr.org/2013/784)), 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 (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.

Can you describe the process in a plainer way, like to a redneck.  It appears that 3 equal inputs ended up in one of the input addresses.  It solved the unequal contribution issue but from where does the external coin flip/lottery component comes from?

I can try... but it is a little tricky, so it may take a few attempts before we get a great description.

Two people each bet 1 coin, commit to random numbers, and also post an additional 1 coin security deposit. When they both reveal their committed random numbers, the numbers are xor'ed and one of them is chosen as a winner, and gets both coins, and both players get their security deposit back. The only tricky thing is that you need some way to make sure both players actually *do* reveal their random number, rather than just disappearing. This is why the security deposit is important - the *only* way to get your security deposit back is to reveal your random number and finish the game - if you don't do this, the other player gets the security deposit *and* the prize.

How was that? Clear?

Now, can you CoinSwap (https://bitcointalk.org/index.php?topic=321228.0)-ify your protocol so that in the case where everyone plays honestly the fact that they just used a coinflip is not visible in the blockchain? :)

So the random numbers are part of the blockchain transaction?  How would it work with 3 people?

For N people, every draws a random number between 0 and N-1, you add up all the numbers, and mod by N to determine the winner. The result is uniformly distributed between 0 and N-1, if even one party chooses their number randomly.

If 2 people collude, they can always take the 3rd person's money.

We need to enable op_mod

https://bitcointalk.org/index.php?topic=418769.0

Here is my attempt to build a script that accomplishes the goal without using disabled op_codes.
Any advice for me?

signature can look like these:
sigA sigB 1
sigA B A 0
sigB B A 0

op_if
   2 <pubkey1> <pubkey2> 2 op_checkmultisigverify
op_else
   op_2dup op_sha256 hash(A) op_equalverify sha256 hash(B) op_equalverify op_add op_RIPE160 0a '7ff2' 8x('00')
   op_lessthan
   op_if
      <pubkey1>
   op_else
      <pubkey2>
   op_endif
   op_checksig
op_endif

63
  52 <pubkey1> <pubkey2> 52 ad
67
  6e a8 <hash(A)> 88 a8 <hash(B)> 88 93 a6 0a 7f f2 00 00 00 00 00 00 00 00
  9f
  63
    <pubkey1>
  67
    <pubkey2>
  68
  ac
68

Hey guys, I was referred here by gmaxwell. I have come up with a similar protocol although I'm not sure it is implementable in Bitcoin script. One noticeable difference is that mine was designed to support arbitrary odds/payouts. I haven't had time to study the protocol proposed here in detail but it seems quite similar to mine (will comment here when I do). https://bitcointalk.org/index.php?topic=893077.0 (https://bitcointalk.org/index.php?topic=893077.0)

By the way, has anyone worked on an implementation of this? I'm not sure the increased security would make up for the inconvenience of having to wait for block confirmations for the average gambler (except maybe for large bets).