search

markkurossi / mpc

Secure Multi-Party Computation (MPC) with Go. This project implements secure two-party computation with Garbled circuit protocol.
https://www.markkurossi.com/mpcl/index.html
MIT License
110 stars 22 forks source link

Why the evaluator can use the original boolean circuit? #24

Closed faderer closed 6 months ago

faderer commented 6 months ago

Hello developer, From my understanding, the garbler only sends the garbled circuit, encoding information, and decoding information to the evaluator. However, in evaluator.go and eval.go the evaluator directly uses the original circuit to compute the output. Is there any template I can use to modify the algorithm?

markkurossi commented 6 months ago

There are two modes of operation:

In the first mode, both garbler and evaluator construct the binary circuit from the input .mpcl file. The circuit compilation is deterministic so they will have the same circuit in memory (another alternative is that they load a pre-compiled circuit). Next, the garbler garbles the circuit and sends the garbled truth tables to the evaluator. Since garbler and evaluator share the circuit, there is not need to transmit the circuit itself. The evaluator iterates over all gates, and based on the gate type, it performs the computation (Free XOR, Half AND, Row reduction). Even though garbler and evaluator share the circuit (the algorithm), the computation is done over the garbled gates. This mode requires the circuits to be in memory i.e. the amount of useable memory limits the size of the programs being computed.

In the second mode (./garbled -stream) the garbler streams the circuit to the evaluator. The streaming happens on the SSA assembly level and the garbler creates the circuits for each SSA assembly operand on-demand. The garbler sends the circuit and garbled truth tables to the evaluator which performs the circuit evaluation. This mode requires less memory; garbler and evaluator have only the active "computation" in memory and as soon as a wire value is used the last time, its memory can be recycled for new wires.