# Introduction to Garbled Circuit and MPZ --- ## Prerequisite Knowledge * Cryptographic Hash Function * Secret Sharing Techniques * Additive Sharing * Polynomial Interpolation (Shamir) --- ## Agenda 1. General Introduction to MPC 2. Introduction to Garbled Circuit 3. Introduction to MPZ 4. Let's play with MPZ --- ## For ZKP people Something ZKP cannot do but MPC can do is you can have secrets from more than one party. > (As opposed to ZKP where only the Prover has secrets.) --- ## What is MPC (*Secure Multiparty Computation*) - mutually **distrustful** parties - jointly compute a **functionality** - keeping the inputs of the participants **private**. --- An **MPC functionality** can be specific or generic. --- ## Common specific MPCs - Threshold Signature, - Threshold Decryption, - Private Set Intersection, - Secure Aggregation, Median, - etc. --- ZKP is specific MPC of two parties (Prover and Verifier) - where only the Prover has secret input which is the witness - and the functionality simply checks the witness and instance pair --- ## How (generic) MPC works - a specific MPC protocol for a Virtual Machine (VM) functionality - the joint function is a common program - the private inputs as parameters to the program --- We can employ two approaches called Secret Sharing, and Garbled Circuit. --- **Secret Sharing** based MPC - the parties split the secret inputs into shares - send them to the other parties - can perform computation on the shares. - addition and multiplication by a scalar is free (can be done locally), - multiplication of two secret-shared values require interactions. --- ## How Garbled Circuit works <!-- Basic Garbled Circuit (Boolean version): https://hackmd.io/frMushaeSESma2OEdNseRQ --> <!-- ### Important excertps from the detailed version: --> <!-- #### Garbling a circuit > The goal of garbling is to obfuscate the boolean truth table of each gate. --> Two parties: the Garbler and the Evaluator --- ## The Garbler --- **Step 1: Pick random labels $W_0$, $W_1$ on each wire**  --- **Step 2: Encrypt truth table of each gate**  The garbled circuit = all encrypted gates We permute the rows to preserve secrecy. --- **Garbled encoding = one label per wire**  --- ## The Evaluator - learns only a wire label of its private input - and not both > as it may allow the Evaluator to extract Garbler's input via evaluating the GC in both cases $0$ and $1$. --- ## Oblivious Transfer  --- **Only one ciphertext per gate is decryptable**  Result of decryption = value on outgoing wire. --- ### And more! Advanced Garbled Circuit (Arithmetic version): https://hackmd.io/gdi44oLIQ8G9fXRHM5hl9Q --- ## Open research questions about MPC --- ## (or How do we put things together in the most suitable way?) --- ### Efficiency (the core computation component) Size of garbled circuits \# of hashes --- ### Programmability (how to describe an MPC program?) Various choices to program MPC https://github.com/rdragos/awesome-mpc  --- More in-depth analysis: https://github.com/MPC-SoK/frameworks (up to date 2015) --- ### Deployment (how are parties connected and interacted?) Peer to Peer (2 parties). Outsourced Servers. Fully connected network. --- ### Malicious Security (how robust is the MPC protocol?) If attacker is semi-honest s/he will follow the protocol, only trying to extract the secret inputs in some way! What if the attacker deviate from the protocol? --- ### Public Auditability (can a result of an MPC be verified?) Parties do MPC offchain, how they convince the onchain nodes to accept the result of the computation? > Not so much research in this aspect! --- ### MPC in Blockchain? Multiparty Binding Negotiation: https://hackmd.io/@tkmct/rkvQoKdx3 And more: https://hackmd.io/@tkmct/HJaqJ8Ngh --- # Introduction to MPZ and coding workshop --- # What is MPZ mpz is a collection of multi-party computation libraries written in Rust 🦀 https://github.com/privacy-scaling-explorations/mpz --- **MPZ is built for MPC functionalities used in TLS Notary** - PMS Key generation - TLS Encryption - TLS Decryption, MAC check [more detail here](https://docs.tlsnotary.org/mpc/key_exchange.html) ---  --- - Secure 2PC (Garbled Circuit for boolean circuit) - Arithmetic Circuit GC is under development (BMR16) - VM based API - Asymmetric Dual Execution VM (Implemented for TLSNotary) - You can build your own VM for GC - Dual execution VM - Cut-and-choose VM - VM using zk to prove integrity --- ## Introduction to MPZ --- 0. Preparation 1. Write your circuit 2. Garble the circuit 3. Run it 4. Use VM abstraction --- ## Install mpz Add mpz and related packages to Cargo.toml Because it's not published on crates.io, specify github url and revision.  --- ## How to write MPC circuit --- ## (Before diving in) Traditional boolean circuit expression [Bristol Fasion Circuit](https://homes.esat.kuleuven.be/~nsmart/MPC/)  --- - Load bristol fasion circuit in mpz - Use MPZ API to write boolean circuit - **(WIP)** Load circom circuit in mpz (arithmetic in near future. currently boolean circuit.) --- ## Load bristol fasion circuit in MPZ 1. Put your bristol fasion circuit in directory. 2. Load it from your code. ```rust! use mpz_circuit::{Circuit, ValueType}; let circ = Circuit::parse( "circuits/bristol/adder64_reverse.txt", &[ValueType::U64, ValueType::U64], &[ValueType::U64], ) .unwrap(); ``` --- ## Use MPZ circuit builder API Use CircuitBuilder to construct a circuit ```rust! use mpz_circuits::CircuitBuilder; // Construct builder struct let mut builder = CircuitBuilder::new(); // Define input in the circuit let a = builder.add_input::<u8>(); let b = builder.add_input::<u8>(); // Add operation in a circuit let c = a.wrapping_add(b); builder.add_output(c); // build the circuit let circ = builder.build().unwrap(); ``` --- ### DataTypes, Define inputs, outpus Define input with given type ```rust! // single bit input. let in_bit = builder.add_input::<bool>(); // each data types have corresponding number of wires. // ex.) in_u8 has 8 wires inside. let in_u8 = builder.add_input::<u8>(); let in_u16 = builder.add_input::<u16>(); let in_u32 = builder.add_input::<u32>(); let in_u64 = builder.add_input::<u64>(); // array of u8 whoes length is 16. let in_arr = builder.add_array_input::<u8; 16>(); ``` Define output ```rust! builder.add_output(z); ``` --- ### Add gates to your circuit --- #### Use predefined methods to add a gate **Wrapping add** ```rust! let a = builder.add_input::<u8>(); let b = builder.add_input::<u8>(); let c = a.wrapping_add(b); builder.add_output(c); ``` **Wrapping sub** ```rust! let c = a.wrapping_sub(b); ``` --- **Bit AND** ```rust! let c = a.bitand(b); ``` **Bit OR** ```rust! let c = a.bitor(b); ``` **Bit XOR** ```rust! let c = a.bitxor(b); ``` --- **Shift left** Shift left by 2 bits ```rust! let c = a.shl(2); ``` **Shift right** Shift right by 2 bits ```rust! let c = a.shr(2); ``` **Not** ```rust! let c = a.not(); ``` --- #### Define yourself Use macro to easily define custom bit operations. --- ##### Define custom circuit using trace macro. More detail [here](https://github.com/privacy-scaling-explorations/mpz/blob/dev/mpz-circuits/src/lib.rs#L27) ```rust! use mpz_circuits::{trace, evaluate, CircuitBuilder}; // Produce gates equivalent to bitxor. // generate bitxor_trace method used in main function. #[trace] fn bitxor(a: [u8; 16], b: [u8, 16]) -> [u8; 16] { std::array::from_fn(|i| a[i] ^ b[i]) } fn main() { let builder = CircuitBuilder::new(); let a = builder.add_array_input::<u8, 16>(); let b = builder.add_array_input::<u8, 16>(); let c = bitxor_trace(&mut builder.state(), a, b); // ... continue your code } ``` --- ##### Define gate with dependencies using dep macro. More detail [here](https://github.com/privacy-scaling-explorations/mpz/blob/dev/mpz-circuits/src/lib.rs#L60) ```rust! use mpz_circuits::{evaluate, trace, CircuitBuilder}; #[trace] fn bitxor(a: [u8; 16], b: [u8; 16]) -> [u8; 16] { std::array::from_fn(|i| a[i] ^ b[i]) } #[trace] fn bitand(a: [u8; 16], b: [u8; 16]) -> [u8; 16] { std::array::from_fn(|i| a[i] & b[i]) } #[trace] #[dep(bitxor, bitxor_trace)] #[dep(bitand)] fn bitxor_and(a: [u8; 16], b: [u8; 16]) -> [u8; 16] { bitxor(a, bitand(a, b)) } fn main() { let builder = CircuitBuilder::new(); let a = builder.add_array_input::<u8, 16>(); let b = builder.add_array_input::<u8, 16>(); let c = bitxor_and_trace(&mut builder.state(), a, b); /// ... continue your code } ``` --- ##### Combine circuits using `append` method ```rust! // Let's say adder is a circuit take two input and returns its addition. let adder = adder_circuit(); // circuit c <- a+b let builder = CircuitBuilder::new(); let a = builder.add_input::<u8>(); let b = builder.add_input::<u8>(); let c = a.wrapping_add(b); // This combines adder and c <- a+b circuit. // adder circuit takes a and c as inputs and add them together. let mut appended_outputs = builder.append(&adder, &[a.into(), c.into()]).unwrap(); // mark output wire let d = appended_outputs.pop().unwrap(); builder.add_output(d); let circ = builder.build().unwrap(); ``` --- ## How to run your circuit? 1. Build circuit 2. Generator garbles a circuit 3. Generator sends the circuit to evaluator 4. Evaluator receives coressponding labels from garbler via OT channel 5. Evaluator executes the circuit --- ### Prepare OT channels ```rust! // channel is OTChannel // pub trait Channel<T>: // futures::Stream<Item = Result<T, std::io::Error>> // + futures::Sink<T, Error = std::io::Error> // + Send // + Sync // + Unpin // { // } // pub type OTChannel = Box<dyn Channel<OTMessage>>; // Generator prepare OT sender let ot_send = Kos15IOSender::new(Box::new(channel)); // Evaluator prepare OT receiver let ot_recv = Kos15IOReceiver::new(Box::new(channel_2)); ``` --- ### Garble a circuit Generator has two important methods to be called. 1. `setup_inputs()`: setup input values. public inputs are sent directly. evaluator's private inputs are sent using OT. generator/mod.rs#L112 2. `generate()`: encrypt circuit and send it to evaluator. generator/mod.rs#L236 ```rust! use garble::Generator; let generator = Generator::new(config, encoder_seed); generator.setup_inputs(id, input_configs, sink, ot).await?; let result = generator.generate(circ, inputs, outputs, sink, hash).await?; ``` --- ### Evaluate a circuit Evaluator receives a garbled circuit and input via OT channel. Then evaluate the circuit. ```rust! use garble::Evaluator; let evaluator = Evaluator::new(config); // receive inputs encodings from generator via OT channel evaluator.setup_inputs(id, input_configs, stream, ot).await?; // evaluate a circuit. returns the encoded outputs of the evaluated circuit. let result = evaluator.evaluate(circ, inputs, outputs, stream).await?; ``` --- ### Wrap it all with VM abstraction There are several built-in traits that we can use to wrap all these protocol and make it looks like a multi-threaded virtual machine. --- MPZ provides the following traits for implementing MPC VM - VM trait : multi-threaded virtual machine trait. Enables spawning new thread. - Thread trait - Memory trait : Provides methods for interacting with values in memory. - Execute trait : Provides a method to execute a circuit. - Prove, Verify, Decode trait [Source code](https://github.com/privacy-scaling-explorations/mpz/blob/dev/garble/mpz-garble/src/lib.rs) --- Let's say you have VM implemented. ```rust! let vm = VM::new(someConfig); let mut executor = vm.new_thread("pms_thread"); let share_a = executor.new_private_input::<[u8; 32]>("pms/share_a", share_a)?; let share_b = executor.new_private_input::<[u8; 32]>("pms/share_b", share_b)?; let share_c = executor.new_private_input::<[u8; 32]>("pms/share_c", share_c)?; let share_d = executor.new_private_input::<[u8; 32]>("pms/share_d", share_d)?; let pms_1 = executor.new_output::<[u8; 32]>("pms/1")?; let pms_2 = executor.new_output::<[u8; 32]>("pms/2")?; let eq = executor.new_output::<[u8; 32]>("pms/eq")?; executor.execute( build_pms_circuit(), &[share_a, share_b, share_c, share_d], &[pms_1.clone(), pms_2, eq.clone()], ) .await?; ``` --- ### Example: DEAP VM [Document](https://docs.tlsnotary.org/mpc/deap.html) [Source code](https://github.com/privacy-scaling-explorations/mpz/tree/dev/garble/mpz-garble/src/protocol/deap) --- ## Future Development - Arithmetic Circuit based on BMR16 - Circom transpiler for MPC circuit - Public verifiability using zkp --- --- ## Workshop discussion points (Thursday) --- We ultimately want to understand: - How parties should be connected and interacted in MPC protocol - How efficient is sufficient for applications (and which ones)? - What is a suitable security model (parties and public blockchain nodes?) for each application? --- Workshop whiteboard [here](https://www.figma.com/file/B5B9WinPdBWCRxz8PycbuL/MPC-workshop-%40-MuChiangMai?type=whiteboard&node-id=0%3A1&t=5D6MNmz0qdVZMe0v-1). - MPC application ideas - Publicly Verifiability - Malicious security - Programmability