Vitalik: Quick Start on Garbled Circuits

Note: The original author is Ethereum co-founder Vitalik Buterin.

Special thanks to Dankrad Feist for reviewing this article.

Garbled circuits is a very old and very simple cryptographic primitive. They are likely to be the simplest form of general-purpose Multiparty Computing (MPC).

Here are the general settings for the scenario:

• QKL123 market analysis | No turning point in the global epidemic, U.S. stock futures re-melt, Bitcoin linkage down (0323)
• Digital data verification platform Attestiv completes $ 2 million seed round financing, led by Castle Island Ventures
• Babbitt Column | Opinion: Bitcoin is a refuge fund, not a hedge fund

1. Suppose there are two parties, Alice and Bob. They want to calculate some functions f(alice_inputs, bob_inputs) , which need to get input from both parties. Both Alice and Bob want to know the result of computing the function f , but Alice doesn't want Bob to know her input, and Bob doesn't want Alice. Know his input. Ideally, they would not know anything except the output of f .
2. Alice performs a special process ("garbling") to encrypt the circuit that evaluates function f (meaning a set of AND, OR gates). She passes the input (also encrypted in a manner compatible with the encryption circuit) to Bob.
3. Bob uses a technique called "1-of-2 Oblivious Transfer" to learn the encrypted form of his input without letting Alice know which inputs he has obtained.
4. Bob runs the encryption circuit on the encrypted data, gets the answer, and passes it to Alice.

Additional cryptographic encapsulation can be used to protect the scheme to prevent Alice and Bob from sending wrong information and giving wrong answers to each other. For the sake of simplicity, we will not discuss these issues, although it can be said that "wrapping ZK-SNARK in everything" is one of the effective solutions (quite heavy and suboptimal!).

So how does the basic plan work? Let's start with the circuit:

This is an example of the simplest circuit, it actually does something: it is a two-digit adder. It enters two numbers in binary form, each number has two digits, and outputs a three-digit binary digit (that is, the sum).

Now let's encrypt the circuit. First, for each input, we randomly generate two "tags" (256-bit numbers): one representing the input as 0 and the other representing the input as 1. Then we do the same for each intermediate line, excluding the output line. Note that this data is not part of the "obfuscation" that Alice sends to Bob; so far, this is just a setting.

Now, for each gate in the circuit, we do the following. For each input combination, we include the output label in the "obfuscation" provided by Alice to Bob (or if the output label is the "final" output, the output is included directly). The input key that caused the output was hashed together to generate a key that was encrypted. For simplicity, our encryption algorithm can be enc(out, in1, in2) = out + hash(k, in1, in2) , where k is the index of the gate (it is the first gate in the circuit, the second ,The third?). If you know the labels of these two inputs, and you are garbling, then you can learn the labels of the corresponding output, because you only need to calculate the corresponding hash and subtract it.

This is the first XOR gate garbling:

Note that we directly include 0 and 1 (encrypted form), because the output of this XOR gate is directly the final output of the program. Now, let's look at the left-most AND gate:

Here, the output of the gate is only used as input to other gates, so we use labels instead of bits to hide these intermediate bits in the evaluator.

The confusion Alice will provide to Bob is just everything in the third column of each gate, and the rows of each gate are reordered (to avoid showing whether a given row corresponds to any 0 or 1 in a row). To help Bob understand which value to decrypt for each gate, we will use a specific order: for each gate, the first row becomes a row where both input labels are even, and the second row is the second The labels are odd, the first label in the third line is odd, and the two labels in the fourth line are both odd (we deliberately chose the earlier labels so that each gate has an even label on one output and the other output With odd labels on it). We obfuscate every other gate in the circuit in the same way.

In short, Alice sent Bob about four 256-bit numbers for each gate in the circuit. It turns out that 4 is far from optimal; for how to reduce the number of AND gates to 3 or even 2 and to reduce the number of XOR gates to zero, see some optimizations here . Note that these optimizations do depend on certain changes, and use XOR instead of addition and subtraction, although this should be done for security reasons.

When Bob receives the circuit, he asks Alice for a label corresponding to her input, and he uses a protocol called "1-of-2 dazed transmission" to Alice ) Ask for a label that corresponds to her input without revealing to Alice what his input is. Then he passed the gates in the circuit one by one, exposing the output line of each intermediate gate.

Suppose Alice's input is two left lines, she gives (0,1), and Bob's input is two right lines, he gives (1,1). Here's the labeled circuit again:

1. In the beginning, Bob knew the tags 6816, 3621, 4872, 5851;
2. Bob evaluates the first gate, he knows 6816 and 4872, so he can extract the output value corresponding to (1, 6816, 4872) (see the table above) and extract the first output bit 1;
3. Bob evaluates the second gate, he knows 6816 and 4872, so he can extract the output value corresponding to (2, 6816, 4872) (see the table above) and extract the label 5990;
4. Bob evaluates the third gate (exclusive OR gate), he knows he knows 3621 and 5851, and learns 7504;
5. Bob evaluates the fourth gate (or gate), he knows 3621 and 5851 and learns 6638;
6. Bob evaluates the fifth gate (AND gate), he knows 3621 and 5851 and learns 7684;
7. Bob evaluates the sixth gate (exclusive OR gate), he knows 5990 and 7504, and learns the second output bit 0;
8. Bob evaluates the seventh gate (AND gate), he knows 5990 and 6638, and learns 8674;
9. Bob evaluates the eighth gate (or gate), he knows 8674 and 7684, and learns the third output bit 1;

So Bob understands the output: 101. In binary, 10 + 11 is actually equal to 101 (in the circuit, the input and output bits are given in order from smallest to largest, which is why Alice's input 10 is represented in the circuit as (0, 1 ) Reason), so it worked!

Note that the use of addition is meaningless in obfuscation circuits, because Bob, who knows 101, can subtract his own input and get 101-11 = 10 (Alice's input), thereby undermining privacy . However, in general, obfuscation circuits can be used for irreversible calculations, so don't undermine privacy in this way (for example, one might think of a calculation where Alice's input and Bob's input are their personality test Answer, and the output is a bit that determines whether the algorithm thinks they are compatible; and this bit of information does not let Alice and Bob know each other's personal quiz answers.

1-of-2 oblivious transfer

Now let's talk more about 1-of-2 oblivious transfer, which is the technique Bob uses to get tags from Alice for his own input. The problem is this: Focusing on Bob's first input bit (the algorithm for the second input bit is the same), Alice has a label corresponding to 0 (6529) and a label corresponding to 1 (4872) tags. Bob has the input bits he wants: 1. Bob wants to learn the correct label (4872) without letting Alice know that his input bit is 1. The trivial solution (Alice only sends 6529 and 4872 to Bob) does not work, because Alice only wants to discard one of the two input tags. If Bob receives both input tags at the same time, It is possible to leak data that Alice does not want to give up.

Here is a simple protocol using elliptic curves:

1. Alice generates a random elliptic curve point H ;
2. Bob generates two points P1 and P2 , requiring P1 + P2 to be equal to H Bob chooses P1 or P2 as G * k (that is, the point where he knows the corresponding private key). Please note that the requirement of P1 + P2 = H ensures that Bob cannot generate P1 and P2 . This is because if Bob knows k1 and k2 , if P1 = G * k1 and P2 = G * k2 , then H = G *（k1 + k2） , so this means that Bob (Bob ) Can extract H的 discrete logarithm (or "corresponding private key") of H的 , which means that all parts of the elliptic curve cryptosystem are destroyed;
3. Alice confirms P1+P2=H and uses some standard public key encryption schemes (such as El-Gamal) to encrypt v1 under P1 and v2 under P2 . Bob can only decrypt one of these two values, because he knows the private key corresponding to at most one value （P1，P2） , and Alice does not know which one.

This solves the problem. Bob learns one of the two line labels (6529 or 4872) according to the input bits, but Alice does not know which label Bob has learned.

Application area

Garbled circuits have potential uses for many applications, not just 2-of-2 calculations. For example, you can use them for multiparty computations of arbitrary complexity, where any number of participants provide inputs that can run in a constant number of interactions. Creating an obfuscation circuit is completely parallel, and you can do multiple obfuscation gates at the same time.

Therefore, you can simply perform large-scale multiparty calculations, many of which calculate the garbling of all the gates in the circuit and publish the labels corresponding to their inputs. The label itself is random, so it will not reveal any information about the input, but anyone can perform the published obfuscation circuit and learn the output in "clear". For the latest examples of MPC protocols using garbling as a component, see here .

Multiparty computing is not the only application environment. In this case, this technique of splitting the calculation into parallel processable parts can operate on the secret data, and then perform the sequential part that can be explicitly run. This is useful, and Obfuscation is not the only technique to achieve this. In general, the literature on random coding includes many more complex techniques. This branch of mathematics is also useful in techniques such as function encryption and obfuscation.

We will continue to update Blocking; if you have any questions or suggestions, please contact us!