No I am interested more in whether you can do it without a banking interface, but fully backed in bitcoins with full public auditability..  It seemed to me that this could work with the sequence of bootstrap via existing exchange for price feed, and then p2p self-contained market trading synthetic USD backed and hedged by BTC and BTC denominated options, the trade itself setting its own price.

Adam

I believe there is a description/footnote/reference from chapter 3 of Brands PhD thesis/MIT press book "rethinking public key infrastructures", which is available for free download.  Its a component of ZK range proofs or ZK less than.

http://www.credentica.com/the_mit_pressbook.html

I'll write it up presently otherwise.  (Going to be AFK for a bit).

Adam

Aye, aye I'm getting there give me a chance

The existing ZKP of less than use proof of a bit being 0 or 1 as a building block (thats why they are inefficient, they do that dozens of times depending on the ranges).  ie to prove x <= 5 = 101b modulo for illustration n=257 (9bit prime) they prove x=000000101b the prove first that x<100b by proving the top 6 bits are 0, and then the prove that xG-4G=01b <= 1 by proving the top 8 bits of xG-4G are 0.

Adam

Unlike currently you would have to communicate fee explicitly and have it validate as the inputs summing to the output.  (It is shown in my second post where f is communicated while inputs a,b and outputs x (spend) and c (change) are in encrypted form and yet it can be audited that A+B=X+C+fG.

Adam

So if you assume the existence of a ZK proof of knowledge of x (with syntax x_i is the i'th bit of x starting from 0 for the LSB) then ZKPoK{(x):x_i=0} then we can check two most significant bits are 0 with ZKPoK{(x):x_255=0 and x_254=0} by using it twice.

This proof will work on values in some group, we use EC instance of schnorr group (like DSA, same keys, parameters, but simpler signature; DSA is a Schnorr signature variant that offers no advantages over the original AFAIK and many disadvantages that I mentioned in OP).  So we will call the value x where the top two bits must be 0 x_255 = x_254 = 0, and x_{253...x202} are the value in satoshis (same as existing precision) and the remaining values of x_{201..x0} are the private key.

xG will be public and is also the coin public key (slightly different from an existing bitcoin address public key).  Now people can verify that encrypted input values (A,B) add up to encrypted output values (X,C) and fee f, where X is encrypted spend, C is encrypted change and f is fee because A=aG, and A+B=X+C+fG because aG+bG=xG+cG+fG.  This enforces that a+b mod n = x+c+f mod n.  The sender must include ZKPoK{(a,b):a_255 = a_254 = 0}.  The sender must also encrypt x and send it to the recipient so that he can prove information about it when he in turn spends it.  f is public because anyone must be able to collect it and attach it to their address via a mining event.

When the recipient spends xG he will have to similarly prove that x_255 = x_254 = 0.

The reason we need two bits is because n is not a power of two.  Say for simplicity we say n = 250.  Now imagine a=3, b=1, but we have to watch out for fraud by adding n because a+b+n = 254, a+b+n mod n = 4, and x=127,c=126,f=1 so checking only the top bit one could forge value by n as a+b+n = x+c+f mod n   3+1 = 127+126+1 mod 250.  The attacker has increased his value by 250 (minus 1 fee) without using any values with msb != 0.  If we prove top two bits are 0 then we can prevent this attack for up to 3 inputs.  (Because 3*64<250; but not 4 input because 4*64>250).  So for greater than 3 inputs we also prove each intermediate calculation in a 3-ary expression tree also has two msbits=0.  eg where Z(x) is short hand for ZKPoK{(x):x_255=0 and x_254=0}, Z(a),Z(b),Z(c),Z(a+b+c),Z(d),Z(e),Z(f),Z(d+e+f),Z(g),Z(h),Z(i),Z(g+h+i),Z((a+b+c)+(d+e+f)+(g+h+i)) so as mentioned i OP there must be k+log3(k) pair of proofs for k inputs (pair because there is one for x_255=0 and one for x_254).

Finally notice that proving knowledge is a kind of signature so in principle you could pay to another persons existing balance, with their approval, rather than transfer control of a value to a new address.  ie say that your recipient already has a balance y and you want to add x to it for them, you disclose x to them (by encrypting it for their public key say) and then they can add it and therefore you can replace coin addresses by existing balances to save on signatures and keys.

eg ZKPoK[Y]{(a,b,x,y,c),f:a+b=x+c+f and Z(a) and Z(b) and Z(y)}, E(x)

where [Y] indicates an auxiliary signature of some information combined with the PoK.  So the sender is binding his spend of X to say it can be added to existing balance Y (where the sender does not know y). 

Now the block validation will allow the recipient to replace his balance with Y'=Y+X=(x+y)G.  As the sender encrypts the value x for the recipient he can now make onwards transfers.

Taint mixing is also possible (though not that cheaply at scale) by spending dust to some number of other users as a kind of ring-transfer.  (A ring-signature is a scheme where you can implicate without their permission other signers as possible originators of a signature where the originator wants to hide their identity among possible authors).  So thats a bit like coinjoin but you dont need the active collaboration of the other users.  If the E(values) are offchain (eg direct to the recipient) the recipient may or may not even be able to use the extra value, if he doesnt know the dust value (he can reject it by referring only to his previous balance, but that does not disprove that he could still have it in reserve - its hard to prove a negative.)  We could alternatively attach it to the chain (at some size cost) maybe even encrypted with proof that the recipient could decrypt it.  (It is easy to prove xG=xH where H=yG, y unknown to the prover, so EC Egamal could do a provably decryptable value, in which case the software can incorporate the coin and block the owner from using earlier versions).

(dust is a value as now that is considered small, but because x_{202..0} is random by the sender and not computable without DL ability it has to be communicated to the recipient in order to be of value to them).

With mining the original coin is of known value 25 bitcoins (and no dust), however the recipient can still spend it securely without people working out his current balance by elimination by keeping dust as change (which he may never spend as it is has truly negligible fractional nano satoshi values.)

Adam

I have been researching this for a few months on and off, because it seems like an interesting construct in its own right, a different aspect of payment privacy (eg from a user perspective or for auditable but commercially sensitive information if we expect commercial entities to use smart-contracts) but also that other than its obvious direct use it may enable the realization of some features that we have not thought of yet, or perhaps improve the efficiency of zerocoin like ideas (I dont see how yet, but it seems related).

The starting point is it is known in the literature that you can do additively homomorphic encryption, and there are also zero-knowldge proofs of less than.  (Proving E(a)+E(b)=E(a+b) is not enough you also have to prove that the attacker did not add n to his balance during the process as the addition is modulo n, the order of the group, not normal arithmetic.)  Its more efficient to do less than a power of 2, but arbitrary values are possible by composition (all values are buildable from power of 2 ranges after all).

Both of these (homomorphic add and ZK less than proofs) are based on established conservative crypto assumptions, however the generic ZKP of less than is big (number of digital signature sized proofs proportional to log(v) where v=log2(n/vmax)+1 = log2(n)-log2(vmax)+1, so in bitcoin log2(n) = 256, and vmax depends on the encoding, but there are 21million BTC < 2^51 satoshis.  And potentially also slow as it involves verifying v signatures.

Originally I was thinking that will work out to be embarrasingly slow and big (something like zerocoin) so I held of discussing if and until i could find a practical efficient method.  There is also an efficient approximate less than ZKP by Berry Schoenmakers (that he never bothered to write in a paper, natch).  However that seemed to me to be more non-standard assumption based on choosing non standard p & q for the Schnorr group and to also not work over elliptic curves and so not ECDSA (only Schnorr, of which DSA is a variant).

However finally I think I saw the missing step that the way bitcoin uses and validates coin values you only need to prove the two most significant bits of each coin is 0, and use an encoding which sets vmax<2^254 (ie increase bitcoin precision from 51 to 254 bits, less significant extra bits beyond the < 2^51 satoshis are the private key.  That gives encoding for 203 bits of security which is greater than the security of ECDSA over P256 which offers security of 128 bits.

And so there is then finally a non-embarrassing efficiency way to do it with EC-Schnorr signatures at the cost of only 2 ECS sigs (same cost and size as ECDSA) per input and output where #input < 4 and #output <4.  For #input>3 you nee to also show eg ZKPoK{(a+b+c,d):a+b+c<2^254,d<2^254} and same if #output>3.  So 2k+2log3(k) signatures for k inputs or outputs.  (3 because 2^254*3<n but 2^254*4>n.)

Btw there are good reasons to use ECS over ECDSA IMO its still conservative and simpler and anyway DSA is based on it.  Because its simpler (no *k^-1 step) its more flexible and easily supports multiparty (n of n) and even threshold signatures (k of n) which allows multisig in the space of one ECS signature (and without even disclosing the existance of k of n nor how big k or n is even), there are some arguments that ECS is more secure than ECDSA in its assumptions about hash properties.  To do multiparty with ECDSA is a research topic, even multiparty DSA is ridiculously complex and depends on the security of a homomorphic encryption instance big enough to hold temporary results involving powers of q eg the paillier cryptosystem with big keys, and threshold DSA on the even more complex Damgard-Jurik extended Paillier scheme.  The flexibility of ECS makes it more flexible for many things, eg the zero knowledge selective disclosure and blinding certification features of Brands certificates based on the representation problem (which is a kind of generalization of Pederson commitments, which is itself a generalization of schnorr).  There are a huge number of things you can do with Brands certificates towards smart contracts that preserve the privacy of the attributes of a person relying on smart contract by using ZK proofs of boolean formulae etc.  

Also for the cost of an extra signature per value you can even have unconditional value privacy.  (Ie a hypothetical all powerful entity able to perform discrete log with minimal effort still cannot tell how much money  you paid).  This is because like OTP all possible values are equally possible, eg with a pederson commitment two base points G, H then xG+yH there are n possible solutions for all possible values of x and y (where x is a secret key and y is a value you prove things about).  The powerful adversary can just solve and find all the possibilities but your public  recorded ZKPs do not show which x value you knew, nor which y was the value you transferred.

Will post more crypto level details and perhaps an openSSL based implementation presently.

Adam

Hi

It occurred to me that one should be able to bootstrap a synthetic USD (or EUR etc) based only on an authenticated feed for the BTCUSD exchange rate (maybe validated against public order book, ideally with p2p blockchain settlement so you know MtGox et al aren't hacked or manipulating the rate) using conventional synthetic commodity financial mechanisms.

How synthetic commodities work is that it is possible to create eg synthetic gold or synthetic stock index without buying the underlying asset, with a matched option pair with exercise price at the current asset price: sell a call option to give away the rights to any upside, and use the proceeds to buy a put option for downside insurance (plus some commission/spread cost).  There are two types of options: american options (which can be exercised at anytime before expiry) and european options (which can only be exercised on the maturity date).  Other potential building blocks include CFDs (contract for difference).  Synthetic commodities work and are used in the financial world, the cost of creating them over buying the underlying asset is small provided there is a deep, liquid market in the options, and similarly they can track the underlying price closely with the same assumptions.  Now options have expiry dates, however the synthetic can be made ongoing by replacing expired, or exercised (in your disfavor) call options.  You do not actually lose in these events.  Similarly you can sell your synthetic back to bitcoin early at a small cost by reselling the put you bought (if not execised in as part of the sale) and buying back the call you sold.

Anyway read about how synthetic assets are created it in a financial reference tutorial or whatever.

The point for bitcoin is a liquid market in BTC denominated BTCUSD options you can hold BTC, and spend a few basis points/year to convert that into a synthetic USD holding (with enough option liquidity).

Such a liquid options market would have a second beneficial value for BTC in that people argue it would stabilize the BTCUSD exchange rate.

I cant imagine I'm the first to think of this, and I suspect bitshare and maybe mastercoin may be saying the same thing, however their financial terminology was non-standard to the point I couldnt understand if this is what they were saying for sure or not.

I would think smart-contracts can be written for the necessary options, so that the whole affair is digital and block chain settled and hence publicly auditable.  We do need more auditable block chain settled exchanges so that we can audit the BTCUSD order book directly, but that is something that needs to happen anyway.

Once you have a BTC backed synthetic USD with smart-contract options, you can do atomic trades for BTC.  Perhaps once it boot straps a bit you dont even need BTCUSD exchanges, you can p2p atomically and publicly auditably swap BTC for synthetic USD which trade itself can auditably define the exchange rate.

Of course I welcome any real financial wizards (or other) comments.

Adam

Got it.  So we have a slightly improved solution, except that its vulnerable to mutable signatures until those are fixed.

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

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

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

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

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.


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

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

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