(DRAFT) Garbled Circuits for Three-Party Computation Imagine a group of people have some private data, and they want to jointly compute a function of their private data, without sharing any of the data. Maybe they want to know the median of their salaries, without anyone revealing their own. Maybe a group of doctors wants to collaborate on a statistical study, without sharing any data about individual patients. This is the problem that multiparty computation solves. If you haven't thought about this before, you'll want to start with the special case of two-party computation, which rests on Yao's garbled circuits protocol and a technique called oblivious transfer. This post by Gubsheep walks you through understanding how you would discover the protocol on your own. If you just want to see the protocol, Vitalik's post is also very good. In this post I'm going to explain how to upgrade two-party computation to handle computations between three (or more) people, still using the basic idea of garbled circuits. For this post, we're going to assume that all three parties carry out the protocol honestly... One could ask for stronger security guarantees. There are lots of different 3PC protocols, with different tradeoffs among security and complexity. There are also lots of good ideas that we won't get into in this blog post -- for example, "cut-and-choose". A three-party version of oblivious transfer

Yan X Zhang and Aard Vark (with thanks to Yi Sun, Jonathan Wang, Lev Soukhanov, Nicolas Mohnblatt) :::warning This hasn't been checked. Use at your own risk. ::: Nova introduced a folding scheme for R1CS circuits. A folding scheme is a way to aggregate multiple satisfying witnesses to a constraint system (in Nova's case, an R1CS circuit), so that multiple verifications can be combined into one. Under the hood, folding works by taking a random linear combination of the witnesses; the R1CS equations need to be generalized to "relaxed R1CS" constraints, which are stable under linear combination.

Yan X Zhang and Aard Vark (with thanks to Yi Sun, Jonathan Wang, Lev Soukhanov, Nicolas Mohnblatt) :::warning This hasn't been checked. Use at your own risk. ::: Halo2 introduced a ZK lookup scheme, building on the ideas of Plookup. Given two vectors of numbers (actually, elements of some large finite field $\mathbb{F}$) $A = (a_1, \ldots, a_m)$ and $S = (s_1, \ldots, s_n)$, a lookup argument is an argument that :::success