2-party private binding computation using garbled circuits

What is this: 2-party computation that let 2 parties to compute agreed upon function with their private data forcing them to take some pre-defined on-chain action depending on the result of the computation. By using garbled circuit and some zkps, we can construct such scheme as publicly verifiable 2-party computation.

MPC Discussion

What is MPC (Secure multiparty computation)? Quick review.

MPC is a cryptographic schemes that enable multiple parties to jointly compute a function on their private inputs without revealing any information about their inputs to the other parties.

Parties: P_1, …, P_n
Secret Inputs: x_1, …, x_n
Evaluate: f(x_1, x_2, …, x_n)

Important requirements to consider

  • Correctness : Parties should get correct output
  • Security : Parties should not learn anything other than the output

General MPC Schemes

Linear Secret Sharing Scheme (LSSS) based MPC

Use additive homomorphism of secret sharing scheme, parties can compute addition and constant multiplication on secret shares. Multiplication requires additional values and opening of the intermediary values (Beaver's trick).
LSSS based MPC requires number of rounds of communication between parties based on circuit size. (Rounds complexity)

**Additive homomorphism
[x] denotes share of x

[x] + [y] = [x+y]
c * [x] = [c*x] where c is some constant value

**Beaver's trick
goal: calculate [x*y] from [x], [y]
preparation: pick three random a, b and c s.t. c = a * b for each multiplication gate and distribute as shares.

Now, every party has [x], [y], [a], [b], [c]
calculate [d] = [x] - [a], [e] = [y] - [b] locally.
Open [d] and [e] to reconstruct d and e from shares. But parties keep [a] and [b] keep private so that no one learns about your [x] and [y].
d = x - a, e = y - b

now,
[x*y] = d * [b] + e * [a] + [c] (+ de)
**(1 party in a network has this +de term if additive sharing scheme is used)

Garbled Circuit

2-party computation using encryption of a circuit gates and oblivious transfer. This scheme is efficient in 2-party settings. It requires only constant number of rounds communication.

Comparing to LSSS-based MPC, GC-based MPC requires only constant round of communication, but it requires more data size depending on the circuit.(Communication complexity)

Difficulty of n-party computation

n(>2)-party computation -> Efficiency of MPC degrades dramatically as number of parties increases. (LSSS-based, GC-based)

-> we focus on 2-party computation

Publicly verifiable (auditable) MPC

Normally, the result of multi party computation can be verified by the parties who joined the computation. (LSSS-based, GC-based)

There is a construction called publicly verifiable(auditable) MPC. In this construction, we generate additional transcript along with the computation to prove the correctness of the computation to public. Usin this proof, we can convince the output correctness to anybody even who did not joined the computation.

What is garbled circuit?

[Briefly explain garbled circuit]

Suppose Alice and Bob want to compute a function f on their secret inputs x_a and x_b.

  1. Alice encrypt circuit wires and gates with her inptus x_a so that Bob cannot learn about x_a

  1. Alice sends the encrypted circuit to Bob

  2. Bob evaluate the circuit using his private input x_b. In this step, he asks Alie decryption key of gates corresponding to his secret inputs using Oblivious Transfer.

In this way, 2-party securely compute on a certain function over their private inputs. With constant rounds of communication.

Private binding 2-party computation

Using garbled circuit, we can construct some interesting scheme called private binding computation.

What is it?

It's a 2-party computation using garbled circuit with binding property.
Binding property: the two parties are enforced to execute some pre-defined on-chain activity after evaluation of the garbled circuit.

How?

Create a circuit which produces signatures of both party under pre-defined condition. (for example, if price matches)

  1. Alice and Bob agree upon certain circuit.
  2. Both parties encrypt the circuit with their own private inputs.
  3. Generate zk proof of correct garbling of the circuit.
  4. Send the circuits and proof to each other.(exchange the encrypted circuits)
  5. Now, Alice has circuit which Bob encrypt with his private inputs and vice versa.
  6. Both parties evaluate the circuits.
  7. They get output in both sides and get output with signature if some condition holds.
  8. Create a zk proof of correct execution.
  9. Both party can submit transaction using the signature and proof to enforce some on-chain activity.

Example Applications

  • Fair swap tx execution after price matching
  • Use KYC ML model result on-chain
    • Machine learning with private model and private input

Discussion points

  • What are the potential applications we can build with this construction?
  • Is this binding property good thing for users? (Do users want this?)

Ideas

Framework for application for this construction

Use this template to create ideas of applications.

Example of fair token trading

IDEATION

Dark Forest Plugin for Private Collaboration

  • Alice inputs: own planet locations and intended direction of expansion.
  • Bob inputs: own planet locations and intended direction of expansion.
  • What circuit does: calculates the average distance of separation between players and a yes/no if the players are in route of expansion colision.
  • On-chain activity: (I´m not sure) gas to pay the coordination mechanism. No data should be public besides maybe initiating the MPC mechanism.

ZK Federated Learning ZK Federated Learning

Public ML model

  • Alice inputs: private health data A
  • Bob inputs: private health data B
  • What circuit does: trains model and proves it's with the correct data
  • On-chain activity:

MPC Correlation Finder

  • Alice inputs: health data
  • Bob inputs: location data
  • What circuit does: checks correlation of diseases with different parameters
  • On-chain activity:

Private KYC model inference

  • Alice (KYC provider) inputs: KYC machine learning model
  • Bob (citizen) inputs: id data(passport/id number/etc)
  • What circuit does: Evaluate the ML model using the id data and test if the id is valid or not.
  • On-chain activity: Issue certificate of having valid id data.

International Trade Negotiation

  • Alice inputs: production metrics, tariffs, quotas, goals
  • Bob inputs: production metrics, tariffs, quotas, goals
  • What circuit does: calculates if there is a match
  • On-chain activity:

Private auction

  • Alice (auction organizer) inputs: current auction price
  • Bob (auctioner) inputs: proposing a new auction
  • What circuit does: tells if it's higher than current or not
  • On-chain activity: execute trade at the end of the auctino
  • Alice inputs:
  • Bob inputs:
  • What circuit does:
  • On-chain activity:
  • Alice inputs:
  • Bob inputs:
  • What circuit does:
  • On-chain activity:
  • Alice inputs:
  • Bob inputs:
  • What circuit does:
  • On-chain activity:
  • Alice inputs:
  • Bob inputs:
  • What circuit does:
  • On-chain activity:

Challenges

  • Because of the OT’s asynchronisity, it’s hard to guarantee the fairness(liveness) even in 2pc using garbled circuit
    • identifiable abort in 2PC is hard. gradual release is much easier
  • Verifying the correct garbling of circuit
    • This can be done with zk proof
  • What is an performance bottleneck?
    • circuit size (how large circuit can be?) GC-based MPC requires big amount of data to download and upload. (data size)
  • Garbled Circuit requires binary circuit
Select a repo