Arithmetic circuits

An arithmetic circuit consists of gates computing arithmetic operations like addition and multiplication, with wires connecting the gates. In our case, the circuit looks like this:

The bottom wires are the input wires, and the top wire is the output wire giving the result of the circuit computation on the inputs. As can be seen in the picture, we label the wires and gates of the circuit in a very particular way, that is needed for the next step of translating the circuit into a QAP: When the same outgoing wire goes into more than one gate, we still think of it as one wire – like w 1 in the example. We assume multiplication gates have exactly two input wires, which we call the left wire and right wire. We don’t label the wires going from an addition to multiplication gate, nor the addition gate; we think of the inputs of the addition gate as going directly into the multiplication gate. So in the example we think of w 1 and w 3 as both being right inputs of g 2 . A legal assignment for the circuit, is an assignment of values to the labeled wires where the output value of each multiplication gate is indeed the product of the corresponding inputs. So for our circuit, a legal assignment is of the form: ( c 1 , … , c 5 ) where c 4 = c 1 ⋅ c 2 and c 5 = c 4 ⋅ ( c 1 + c 3 ) . In this terminology, what Jennifer wants to prove is that she knows a legal assignment ( c 1 , … , c 5 ) such that c 5 = 7 . The next step is to translate this statement into one about polynomials using QAPs.