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

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

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

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.

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?

The locktime support in Bitcoin is quite basic, please read Greg Maxwell's explanation on how it works:
https://bitcointalksearch.org/topic/m.2060451
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).

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

[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

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

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

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.

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.

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.

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.

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?

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.

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.

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.

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

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.

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.