paper: Secure Multiparty Computations on BitCoin

[socrates1024]

This neat paper was recently posted on the cryptography e-print server;
http://eprint.iacr.org/2013/784

The main idea is that Bitcoin can be used to provide "fairness" for arbitrary multi-party computations. Fairness means that if one party interrupts the protocol (e.g., by playing dead, or unplugging their computer and not sending any more messages after some point), the outcome is still "tolerable" to the other (honest) parties. This fairness property is not generally impossible for pure multiparty computations, and typically requires some kind of trusted third party as a mediator. Bitcoin's function as a timestamp server can replace this third party, and "tolerable" is interpreted (in a compelling way) as the the interrupting party forfeits some security deposit.

This generalizes the hash-lock transaction techniques, used in e.g., Iddo's two player coin-flip lottery protocol, the mixing transaction from the Bitter-to-Better paper, and CoinSwap.

[1715376431]

1715376431

[1715376431]

1715376431

[1715376431]

1715376431

[Mike Hearn]

Well, this is very cool. I especially like that they used bitcoinj to make the prototype I wonder if they would open source it?

I thought from the title that this was some generic way to run any arbitrary Yao-style circuit integrated with Bitcoin, but it seems less ambitious - though I think the multi-party lottery scheme still rates as the most advanced usage of script yet found in the wild.

Does someone want to summarise their protocol? It's something that should be on the Contracts page, IMHO, but I found their paper to be highly obfuscated (they invented their own notation for scripts and things) and right now it's 1am and I can't concentrate enough to turn what they're doing back into something more understandable.

[moderate]

I think the multi-party lottery scheme still rates as the most advanced usage of script yet found in the wild.

Whoa! Where is that experiment described ?

[Mike Hearn]

What experiment? That transaction comes from the paper that the thread is about.

[socrates1024]

Does someone want to summarise their protocol?

This paper has a clever solution to the problem we were stuck on in Iddo's coinflip protocol, which relies on curently-disabled op codes.

The problem is only due to an incidental quirk in Bitcoin's scripting language anyway, so it's clever rather than fundamental. Iddo's hashlocked lottery protocol requires each party to select an arbitrary number, and a deterministic function of those numbers is used to decide the winner. The problem is the script language doesn't let us do math (like OP_ADD) on larger-than-4-byte numbers, and more than 4 bytes of randomness are needed for it to be very safe/fair. The solution they propose is to use OP_SIZE to effectively compress a large string down to a small math-friendly number.

The key step goes like this: each player selects a random number i, in the range 0, 1, ..., N (for an N-player lottery). Then, they select random string s with 20+i bytes. The commitment is the hash of s, and to reveal it you do "{s} OP_SIZE OP_DUP {20} {20+n} OP_WITHIN OP_VERIFY {20} OP_SUB" in the script to get out just "i".

[Mike Hearn]

I thought iddo/adams protocol only worked for the two party case?

[socrates1024]

I thought iddo/adams protocol only worked for the two party case?

Yes but generalizing it to multiple parties (as in the paper) is trivial.
The only substantial way it improves on iddo's is using OP_SIZE to be compatible with existing opcodes. 

[socrates1024]

One big problem with the N-way lottery protocol in this paper is that it requires an extremely steep security deposit. Each player wagers only 1 coin, but has to additionally deposit N(N-1) coins. In total, only N coins are wagered, but O(N³) coins are escrowed for fairness. They argue (and I agree with it) that this is the best that can be done... for a one round protocol!

I claim that we can improve on this, having exactly the same payoff structure and security, and deposits only of size N. The caveat is that it requires log₂ N rounds. The protocol is a tournament bracket. Each player commits to log₂ N random numbers. In first round, player 0 plays a 50/50 coinflip game with player 1, player 2 plays with player 3, etc. If a player reveals their random secret, they can immediately exit the game and get their deposit back. If they win, they go on to the next round. If one player in a match does not reveal their secret, then their deposit is forfeited.

[edit]I actually have no idea how to pull this off. Seems impossible to me at the moment.

[jedunnigan]

They just published a follow up paper. I haven't had a chance to dig through it, looks interesting so far: https://eprint.iacr.org/2013/837.pdf