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

[Dabs]

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.

[Mike Hearn]

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

[adam3us]

Nice! In step (3) it should be "v (LOCK(time) ^ SIG(A))"

Oops, fixed.

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.

Correct. 

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

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

use regular script form instead of inventing new notations for transactions?

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?

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.

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

[adam3us]

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

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

[Dabs]

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.

[adam3us]

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

Maybe there would be a structured (financial) product use case where different payouts are made depending on the outcome.  

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

[adam3us]

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.

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

[Dabs]

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.

[iddo]

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.

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.

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

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

[gmaxwell]

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.

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

[iddo]

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.

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

[User705]

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.

[gmaxwell]

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.

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

But are you referring to a different danger here?

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.

[User705]

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?

[gmaxwell]

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

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.

[iddo]

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.

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

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"

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.

[gmaxwell]

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

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.

[User705]

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.

[User705]

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

[Dabs]

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