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

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

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

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.

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

Oops, fixed.


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

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

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.

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

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.

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

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

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.

Interesting points

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.

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

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

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?

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

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.