Last week, Marcel presented a study group on secure computation using bitcoin. In a secure multi-party computation (MPC) protocol, several players interact to compute a function of their inputs, without revealing the inputs to each other. These days MPC is a huge area of research in cryptography and there always tends to be several interesting papers at the big conferences.
One fundamental issue that is often overlooked in MPC is fairness. A protocol is said to be fair if it is impossible for a malicious player to abort the protocol early and learn the result of the computation, before the other players have managed to do so. In general this is impossible to achieve, as the first player to learn the result can usually just abort instead of passing this on to the other players [1]. However, using the power of the bitcoin network, fairness can be enforced for any function.
One fundamental issue that is often overlooked in MPC is fairness. A protocol is said to be fair if it is impossible for a malicious player to abort the protocol early and learn the result of the computation, before the other players have managed to do so. In general this is impossible to achieve, as the first player to learn the result can usually just abort instead of passing this on to the other players [1]. However, using the power of the bitcoin network, fairness can be enforced for any function.
Bitcoin transactions
A transaction in the blockchain typically contains: [2]
- value
- previous transaction ID
- in-script: outputs signature on current transaction
- out-script: verifies signature from next transaction's in-script
- (timelock)
The value and previous transaction ID are self-explanatory; the two scripts provide the key functionality. For a normal bitcoin transaction, the in-script outputs a signature on the current transaction, and the out-script is used to verify the signature from the in-script of the next transaction using the appropriate public key.
The key point is that the in-script and out-script are not just a signature and a public key. They are pieces of code written in a (very simple) scripting language [3], so can actually be used to do something entirely different!
- value
- previous transaction ID
- in-script: outputs signature on current transaction
- out-script: verifies signature from next transaction's in-script
- (timelock)
The value and previous transaction ID are self-explanatory; the two scripts provide the key functionality. For a normal bitcoin transaction, the in-script outputs a signature on the current transaction, and the out-script is used to verify the signature from the in-script of the next transaction using the appropriate public key.
The key point is that the in-script and out-script are not just a signature and a public key. They are pieces of code written in a (very simple) scripting language [3], so can actually be used to do something entirely different!
The final, optional item in a transaction is a timelock: this can be used to indicate a time, before which the transaction may not be added to the ledger.
Timed Commitment
A fundamental building block for fair secure computation using bitcoin transactions is timed commitment, which functions as a normal cryptographic commitment, except the committer must pay a penalty if they do not open it within a set time period. The Committer, C, sends a standard commitment to the receiver, R, and posts an initial commitment transaction to the blockchain:
Commit
in-script: (output signature as normal)
out-script: check sigC AND (opening OR sigR)
Here the out-script verifies that the next transaction was signed by C (the committer), and also that the next transaction either contains the required decommitment information, opening, or was signed by R (the receiver). This means that either of the following two transactions may be added to Commit in the blockchain:
Open
in: sigC, opening
out: C
Fuse
in: sigC, sigR
out: R
timelock
Commit
in-script: (output signature as normal)
out-script: check sigC AND (opening OR sigR)
Here the out-script verifies that the next transaction was signed by C (the committer), and also that the next transaction either contains the required decommitment information, opening, or was signed by R (the receiver). This means that either of the following two transactions may be added to Commit in the blockchain:
Open
in: sigC, opening
out: C
Fuse
in: sigC, sigR
out: R
timelock
The Fuse transaction must be created (and signed by both parties) at the start and given to the Receiver. Once Commit has been posted, the Commiter must post the Open transaction, with the relevant decommitment information, before the timelock expires, at which point the receiver can post Fuse to gain their reward if Open hasn't been added.
Fair MPC using Mutual Commitment
Similarly to the timed commitment protocol above, a *mutual commitment* between any number of parties can be created. Here every party must commit to something, and is penalised if they do not decommit within the time period. Adapting this to MPC is quite straightforward. At the end of a typical MPC protocol, every party will hold a *share* of the result, which must be revealed so that everyone can reconstruct the result. Mutual commitment guarantees that everyone will reveal their share, or pay the penalty.
Clearly using bitcoin doesn't quite guarantee fairness in the traditional sense; it is still possible for a player to abort, just at a high monetary cost. But in a model with rational adversaries, if the penalty is set appropriately then this seems a reasonable solution.
Clearly using bitcoin doesn't quite guarantee fairness in the traditional sense; it is still possible for a player to abort, just at a high monetary cost. But in a model with rational adversaries, if the penalty is set appropriately then this seems a reasonable solution.
Further reading:
The first paper we discussed, on timed commitment and secure lotteries without a trusted third party.
The second paper, on fairness in two-party computation.
Another recent paper on fairness and MPC.
[1] See Enrique's blog post for details of a nice, recent work that characterizes situations where fairness is possible.
[2] This is probably not entirely accurate, I recommend the bitcoin wiki for a more thorough description.
[3] The Script language is a simple stack machine, deliberately not Turing-Complete so that non-terminating scripts can be detected easily.
No comments:
Post a Comment