Bitcoin Forum
December 02, 2021, 03:51:58 PM *
News: Latest Bitcoin Core release: 22.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: paper: Secure Multiparty Computations on BitCoin  (Read 2160 times)
socrates1024
Full Member
***
Offline Offline

Activity: 126
Merit: 108


Andrew Miller


View Profile
December 02, 2013, 10:31:22 PM
Last edit: December 02, 2013, 11:29:04 PM by gmaxwell
 #1

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.

amiller on freenode / 19G6VFcV1qZJxe3Swn28xz3F8gDKTznwEM
[my twitter] [research@umd]
I study Merkle trees, credit networks, and Byzantine Consensus algorithms.
1638460318
Hero Member
*
Offline Offline

Posts: 1638460318

View Profile Personal Message (Offline)

Ignore
1638460318
Reply with quote  #2

1638460318
Report to moderator
1638460318
Hero Member
*
Offline Offline

Posts: 1638460318

View Profile Personal Message (Offline)

Ignore
1638460318
Reply with quote  #2

1638460318
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
Mike Hearn
Legendary
*
expert
Offline Offline

Activity: 1526
Merit: 1033


View Profile
December 03, 2013, 12:02:19 AM
 #2

Well, this is very cool. I especially like that they used bitcoinj to make the prototype Smiley 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
Member
**
Offline Offline

Activity: 98
Merit: 10

nearly dead


View Profile
December 03, 2013, 03:43:31 AM
 #3


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
Legendary
*
expert
Offline Offline

Activity: 1526
Merit: 1033


View Profile
December 03, 2013, 10:46:43 AM
 #4

What experiment? That transaction comes from the paper that the thread is about.
socrates1024
Full Member
***
Offline Offline

Activity: 126
Merit: 108


Andrew Miller


View Profile
December 04, 2013, 05:37:19 AM
 #5

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

amiller on freenode / 19G6VFcV1qZJxe3Swn28xz3F8gDKTznwEM
[my twitter] [research@umd]
I study Merkle trees, credit networks, and Byzantine Consensus algorithms.
Mike Hearn
Legendary
*
expert
Offline Offline

Activity: 1526
Merit: 1033


View Profile
December 04, 2013, 10:50:10 AM
 #6

I thought iddo/adams protocol only worked for the two party case?
socrates1024
Full Member
***
Offline Offline

Activity: 126
Merit: 108


Andrew Miller


View Profile
December 04, 2013, 05:28:59 PM
 #7

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. 

amiller on freenode / 19G6VFcV1qZJxe3Swn28xz3F8gDKTznwEM
[my twitter] [research@umd]
I study Merkle trees, credit networks, and Byzantine Consensus algorithms.
socrates1024
Full Member
***
Offline Offline

Activity: 126
Merit: 108


Andrew Miller


View Profile
December 06, 2013, 06:02:07 PM
Last edit: December 07, 2013, 01:52:40 AM by socrates1024
 #8

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(N3) 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 log2 N rounds. The protocol is a tournament bracket. Each player commits to log2 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.

amiller on freenode / 19G6VFcV1qZJxe3Swn28xz3F8gDKTznwEM
[my twitter] [research@umd]
I study Merkle trees, credit networks, and Byzantine Consensus algorithms.
jedunnigan
Sr. Member
****
Offline Offline

Activity: 279
Merit: 250


View Profile
December 21, 2013, 07:43:54 AM
 #9

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
Pages: [1]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!