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.

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?

Can you please elaborate? How would the winner of the bet be chosen if only one party commits?

I should say that the two advantageous properties of the OP are (1) it works with Bitcoin as it is now so there's no need to fork the Bitcoin protocol, and (2) bets of relatively small amounts can be instant because 0-confirmations security is enough.

If we don't care for these two properties, then I think that we can have a much more simple protocol by adding to the Bitcoin scripting language an opcode that puts on the stack the hash of the block in which the transaction resides. This way the script can access a pseudorandom value that neither Alice nor Bob can control, and the winner of the bet can be selected according to (say) the LSB of this value. If Alice has say 10% of the total hashpower then the best that she can do is not to broadcast the block that she solved if its LSB would cause her to lose the bet, i.e. 90% of the total hashpower is working to generate a fair coin toss, 5% of the total hashpower is working to generate a coin toss where Alice wins the bet, and 5% of the total hashpower doesn't participate.

Just to clarify, when you play against a centralized service such as SatoshiDice or Just-Dice, there is no third party, i.e. if we use the same terminology then the centralized service is Alice and you are Bob. When these centralized services proclaim that they are "provably fair", they neglect to mention that their protocol only gives "security with aborts", i.e. it's fair only under the assumption that the parties don't abort. So if you bet a very large amount X by supplying your seed that's supposed to be hashed with the preimage of the public value that the centralized server published, then the centralized server can claim "technical error, our data was lost, please try again" instead of revealing the preimage in case it sees that it'd lose. Granted, the reputation of these centralized services is important to them so they wouldn't try to pull this trick, but on the other hand there's a house edge (i.e. it's not a fair coin) because these centralized services are suppose to generate a profit.

The purpose of this protocol is to allow two individuals Alice and Bob to do an atomic fair coin toss, meaning that if either Alice or Bob aborts then nothing happens (i.e. they both retain the X coins that they started with), and if both of them follow the protocol then one of them receives the 2X coins and the other loses, with equal probability. Using an escrow/dealer as you suggested is unneeded, and entails risks. When the amount X of the bet is relatively small then this entire protocol can be instant (0-confirmations security), and when X is relatively large then the parties can wait for the Bitcoin network to generate one or more blocks, according to the security level that they wish to have. This basic protocol could be used on some centralized gambling site where the centralized site just allows individuals to play with each other, or the centralized site can play against an individual in a completely secure way. BTW because Alice and Bob commit a secret that consists of many bits, we can easily do bets with a biased coin where the party who has the worse odds would win the larger amount.

This doesn't solve the possible extortion scenarios. For example if Alice loses then she can say that she's only willing to pay x/2 coins instead of the x coins that she lost in the bet, and if Bob doesn't agree then he loses the 3x coins that he locked. Another example is that Alice simply aborts after your step (1) and tells Bob to send her (say) 0.1 coins or else his 3x coins will be locked forever.

I now edited step (10) of the OP to clarify that the only risk with this protocol is that the "Reveal2" transaction will be reversed. I guess that it's too optimistic to expect that we could have a 0-confirmations protocol with absolutely no risk involved, but any improvements are of course welcome.


Cool. If you prefer to lay it out in a public thread or in the mailing-list or in wiki then maybe more people would begin to implement this kind of protocols. If it's better to do it in private then maybe that can work well too, I'll email this thread now to the persons that I discussed it with.

I see, OP_XOR is also disabled so we cannot xor and then get the MSB by using OP_GREATERTHAN to compare with a constant. I guess that we can do nested if/else to get the MSB via OP_GREATERTHAN for each of the secrets of Alice and Bob, though your suggestion to hash the two secrets and then do a single comparison is probably more simple.

I'll be honored if it gets added to the contracts wiki, if everyone agrees that there isn't anything unsound here It can be contrasted to the theoretical result that says that any coin toss protocol in R rounds will have 1/R bias, but with a Bitcoin-based protocol it's not so surprising that we can do better when we have a blackbox that lets both parties lock funds and be refunded after a timeout unless some other condition holds.

About implementing it, this idea came up in a conversation after a Bitcoin meetup that Meni organized last month, where there seemed to be an interest in implemented a gambling system that doesn't involve a 3rd-party like SatoshiDice, so we can eliminate the house edge. The person who asked Meni and myself regarding whether it can be done sounded excited about it, so maybe he would like to code it. I'll try to ask.

With regard to reading the LSB, there's OP_MOD in the Bitcoin script language that could be used, no?

About the possibility that the transaction would take longer to confirm than the locktime timeouts, note that (unlike your similar suggestion in post #6 here) there is no symmetry between the "Reveal1" transaction of step ( 6 ) and the "Reveal2" transaction of step ( 8 ), so if Alice insists that the "Reveal2" transaction will be mined into a block before she signs and broadcasts her "Reveal1" transaction then we're safe in the sense that the bet is atomic, i.e. either both parties reveal their committed bit, or nothing happens and both parties get their refund. In practice it should be enough for Alice just to see that Bob broadcasted the "Reveal2" transaction, assuming that neither Alice nor Bob control a significant enough amount of the hashpower and that the transaction uses a standard fee (I suppose that it's possible to try to bribe the miners, though I don't really see how to do it under the assumption that the hashpower is decentralized). Edit: this is now mentioned in step (10) of the OP. With 0-confirms it could be easy enough to reverse "Reveal2" and maybe shouldn't even be considered a "bribe", and I remember that we had discussions on more sophisticated bribe attacks (for example link).

bump

You need a preimage attack on the hash function where the preimage is a valid pubkey for which you know the corresponding privkey. There are about 2^256 pubkeys and 2^160 hashed addresses, so the attacker has to find one ECDSA keypair as the preimage out of about 2^96 possible candidates.

It's true to say that if the hash function is resistant to preimage attacks then we have 160 bits of security, compared to the 128 bits of security of ECDSA with 256 bit security parameter. But saying that the attacker must break both the hash function and ECDSA is too strong.

I'm not sure that in general it's completely true that a side-channel attack on a hash function like SHA512 involves only non-memory access, because the input to the hash function probably resides in memory, so there might be side-channel attacks that involve cache misses etc., though I suspect that in this case you're right because the input is short (privkey + hash of the message), and even if there was a possible danger here then there are probably side-channel resistance techniques to mitigate the risk.

More importantly, in the specific case of ECDSA it's enough to recover the output of k=hash(privkey, msg) rather than the input (privkey, msg) because if k leaks then the privkey also leaks. Therefore, it doesn't really matter if we use deterministic signatures via k=hash(privkey, msg) or random signatures via e.g. k=hash(privkey xor random, msg) because carrying out a side-channel attack that recovers the output of the hash function should be much easier than carrying out a side-channel attack that recovers the input to the hash function.

And more generally, side-channels attacks against symmetric crypto primitives like AES and SHA2 are a lot more difficult than side-channel attacks on public-key/asymmetric crypto primitives, so the risk of possible side-channel attacks on either the input or the output of SHA512 are probably not so significant.

Maybe there should be a parameter (on by default as in OpenSSL ?) to toggle the protection from side-channels attacks, and if the user wishes to have the best possible protection then he could specify via this parameter that the input to the hash function should be masked with randomness, which would imply random signatures because it cannot be unmasked.

I'm not sure if we're missing anything interesting here, so it'd be a good idea to consult with experts on side-channel attacks before having deterministic signatures as the default.

I'm probably missing something here, but it seems to me that the argument that you're giving is similar to what Colin Percival had in mind, though you're interpreting it in the opposite way than he, and I don't exactly understand your argument yet.

I think that the concern is that there might be side-channel attacks on the hash function (heat as in your example, acoustic noise, timing, etc.) that may recover the input that it's invoked with. On the other hand, while it is true that the privkey and K are also used in the next calculations that finally derive the signature, those calculations can be masked in order to protect from such side-channel attacks (like multiplying k by a fresh random value before calculating k^{-1} and then unmasking). For the hash function, there's no way to do these masking tricks, hence the concern?

I suppose that it's a good idea that deterministic signatures would be a user configurable option, but the important question still remains regarding whether the default behavior should be deterministic or random.

Other than this supposed protection from side-channel attacks, does anyone know if there are any other advantages or practical use cases for random signatures (as is obviously the case with random encryption so that it'd be semantically secure) ?

I don't see why K==d is more indicative of a faulty RNG than the infamous K==11 ? Are you seriously suggesting that we should test here whether we're dealing with RNG that always returns the same value, or is there something else that I'm missing?

Huh? You're describing how to carry out one particular attack that succeeds with probability 2^{-n} where n=order(G), but that's always the case, i.e. you can always carry out an attack that succeeds with probability 2^{-n} simply by guessing d (or k).
The checks that you mentioned in your first sentence are done to avoid invalid values and to have uniform probability over the range of valid values, k==d is valid and therefore it shouldn't be excluded as a potential value.

Your type-3 appears to inferior to type-1: with type-1 there's one master secret, and in case that master secret leaks then all the other privkeys in your wallet also leak, but in the case that certain privkeys themselves leak the all the other privkeys don't leak. With your type-3, for efficiency the user's client may opt to store many seed[n] values, and if any of those seed[n] leak, then all the subsequent privkeys leak too. And just like with type-1, with your type-3 wallet if the master secret leaks then the entire wallet leaks. You haven't explicitly tried to claim what's the supposed advantage of type-3 over type-1, but maybe what you had in mind is that in order to generate the next privkey the user wouldn't need to access the most sensitive piece of data which is the master secret, and will only need to access the seed[n-1] data instead, We have discussed similar properties here before. If you think that your type-3 has any advantage over type-1, please describe with precise details how the client software is supposed to retrieve an arbitrary privkey[k] without access to the master secret. Do you propose to have multiple layers of encryption every time that a new seed is derived?


If SHA2 is pseudorandom then it's infeasible to figure out chaincodes from the pubkeys. The more tricky question is whether you could carry out a related-key attack after seeing many signatures, and the answer is "no".
In practical settings, the issue that concerned us is that if you're running a listening-only server that doesn't have access to the privkeys but does have access to chaincodes, and your server is compromised, so if an attacker could obtain a single privkey from another source (not from the listening-only server because that server doesn't even know the privkeys) then all the privkeys in your wallet will leak. Our solution is to use type-1 derivation for the root of the branch that the listening-server would be using, so that any leakage of privkeys will be confined only to that branch, and the user is advised to store privkeys that control high amounts of coins in different "cold storage" branches.

Hard to forbid or impossible to forbid? Instead of OP_CHECKSCIP, can there be a way to incorporate SCIP into Bitcoin scripts in a way that disallows covenants?

I failed to understand (for example I have no idea why you said "lie about their time"), could you please try to explain the above in a way that might be more clear?

One thing that I can see is that the Bitcoin script language could be extended to include a new opcode (unrelated to SCIP) that puts on the stack the timestamp of the block in which this transaction resides, and similarly an opcode that puts on the stack the timestamp of the previous block (relative to the block in which this transaction resides), and then bind the SCIP program to use these two public inputs, and the SCIP program would be completely trivial i.e. it would just check the difference between its two inputs. So except for enforcing the covenant, SCIP isn't needed here, because the regular Bitcoin script can directly check the condition on the difference between the two timestamp values.

Another thing that I can see is that the specified SCIP program (verification key) will have the hash of the genesis block (or a more recent checkpoint block hash) hardcoded into it, and will receive non-public input which is the all the next blocks, and the SCIP program checks that the entire hash chain is valid, and fetches the timestamp value from the last block that it hashed. But this way you can only fetch the timestamp of the previous block, not the current block?

Yes you only need give a hash to the sender.
I meant that if the user wishes to take advantage of the key homomorphism property of ECDSA/BIP32, he can give the sender the account numbers of his smartphone and laptop accounts, and then the sender could generate fresh addresses by himself, instead of asking the user for a new address every time. We've discussed use cases for this, start for example at https://bitcointalk.org/index.php?topic=19137.msg1496121#msg1496121

I tried to convince Meni that it cannot easily be done if the party that learns the outcome first can abort and hence bias the result, though it can still be done via gradual release techniques.

So, any comments on this Bitcoin-based coin toss scheme? Anyone?