Introducing the SIEVE Circuit-IR: Basics
Written: , Published: , Author: Kimberlee Model, Tags: SIEVE IR, Circuit-IR, v2.1.0,
The DARPA SIEVE Program has been developing the SIEVE Intermediate Representation for about three years, and we recently achieved our second public release: the Circuit Intermediate Representation. As one of the primary developers of it, team Wizkit will again blog about its development and workings. Today we’ll start a series overviewing the SIEVE Circuit Intermediate Representation (Circuit-IR) language and semantics, and of course our own WizToolKit library for this revision of the Circuit-IR.
An Intermediate Representation (IR) is a term borrowed from the field of programming language development, a sensible borrow for what is essentially "programmable cryptography". Typically, an IR is the representation of a program within a compiler: a common understanding of the program between the frontend (which handles the input language) and backend (which outputs machine code). In the SIEVE Program, some teams have developed frontends which accept various input languages, while other teams have developed backends which prove statements in Zero Knowledge, rather than emitting machine code. The SIEVE Circuit-IR is a common understanding of ZK statements between SIEVE frontends and backends.
Throughout this series "IR" will refer specifically to the SIEVE Circuit-IR.
Although this post is about a revision to the SIEVE IR, we don’t expect you to have read prior posts in order to read this one. You can (and probably should) read this post as if you’ve never heard of the SIEVE IR before. We do expect you to have a basic familiarity with Zero-Knowledge Proofs (ZK) and finite field arithmetic in GF(p).
The Zero Knowledge Setting
In Zero Knowledge we have two parties: the prover and the verifier. The prover has some secret and wishes to convince the verifier that some falsifiable fact about their secret is true, without revealing the secret. For example, a company may have a user database which the wish to keep secret to protect the privacy of their patrons. But regulators may wish to inspect the user database to ensure that the company doesn’t collect information about children below the age of 13. Instead of opening up and showing their user database to the regulators, the company can make a zero knowledge proof stating that each user’s age is greater than 13.
This example illustrates all the fundamental components of the inputs to a ZK Proof. The prover has a private input — their user database. The prover and verifier both know a public input — the threshold age of 13 (new regulations could change this to 12 or 14, for example). Most importantly there is a relation which connects both inputs to form some falsifiable fact: that each user’s age is greater than the threshold.
The Circuit
The SIEVE-IR’s relation is based on circuits — gates connected by wires.
Most gates produce one output wire, specifying a wire number for it to be referenced as inputs to subsequent gates.
Gates have the form $output ← @operation($inputs…);, with the output wire on the left of an arrow, followed by an operation and a parenthesized list of inputs.
Wire numbers are prefixed with a $, operations with an @, and numeric constants, where allowed, are surrounded by angle brackets (<12345>).
Wire numbers are often consecutive, but do not need to be.
Let’s introduce each gate through a quick example. We’ll prove that a triangle is a right triangle using the Pythagorean Theorem. Three side-lengths will be used to prove that a2 + b2 = c2.
Input Gates and Input Streams
The first kind of gate you’ll encounter is an "input" gate.
The IR represents the circuit’s public and private inputs using streams — sequences of values which the circuit may access one at at time.
The IR has one stream for private inputs and another for public ones.
The $n <- @public(); and $n <- @private(); gates will read the next wire from a stream and assign it to a wire.
In our example, let’s read two public legs and the hypotenuse from the private input stream.
$0 <- @public(); // leg a $1 <- @public(); // leg b $2 <- @private(); // hypotenuse c
The streams themselves are simply lists of values, preceded by a little bit of header information (the IR version, a public or private keyword, the prime field).
| Public Input Stream | Private Input Stream |
|---|---|
@version 2.1.0; public_input; @type field 127; @begin <3>; // leg a <4>; // leg b @end |
@version 2.1.0; private_input; @type field 127; @begin <5>; // hypotenuse c @end |
Arithmetic Gates
Arithmetic gates are the main workers of all circuits.
The @mul and @add input two wires and output either their product or sum.
We can use @mul to square each input, and @add to add A and B.
$3 <- @mul($0, $0); // A**2 $4 <- @mul($1, $1); // B**2 $5 <- @mul($2, $2); // C**2 $6 <- @add($3, $4); // A**2 + B**2
Built into the IR, we can only compare wires to 0, not to each other.
Therefore, we must rewrite A2 + B2 = C2 to become A2 + B2 - C2 = 0.
To perform subtraction in the IR we multiply the right operand by P - 1 — -1 in a finite field — and then use addition.
To multiply by a constant we use the $output <- @mulc($input, <constant>); gate.
$7 <- @mulc($5, <126>); // If our prime is 127, then 126 == -1 $8 <- @add($6, $7); // A**2 + B**2 - C**2
Assert Zero
The last gate we need is @assert_zero($input);.
This gate proves that a wire is (or is not) equal to zero.
@assert_zero($8);
Putting this together, along with a header (again the IR version, a public or private keyword, the prime field) we get the following circuit.
@version 2.1.0; public_input; @type field 127; @begin $0 <- @public(); // leg A $1 <- @public(); // leg B $2 <- @private(); // hypotenuse C $3 <- @mul($0, $0); // A**2 $4 <- @mul($1, $1); // B**2 $5 <- @mul($2, $2); // C**2 $6 <- @add($3, $4); // A**2 + B**2 $7 <- @mulc($5, <126>); // If our prime is 127, then 126 == -1 $8 <- @add($6, $7); // A**2 + B**2 - C**2 @assert_zero($8); @end
WizToolKit
You can give these circuits a try with WizToolKit’s wtk-firealarm tool.
WizToolKit is a library for working with the SIEVE IR, and the wtk-firealarm tool runs proofs in the Non-ZK setting — good for testing, debugging, and trying things out.
You can download WizToolKit and install with make && sudo make install.
If you’re a ZK backend developer you can have a look at our integration tutorials and backend starter code. Regardless of whether or not you develop ZK backends, you can take a look at some of our test circuit generators.
Conclusion
This post showed off the basics of using the SIEVE Circuit-IR.
-
The numbered wiring system to connect gates,
-
Accepting inputs from public and private streams,
-
And using arithmetic gates to define a relation.
In upcoming posts we’ll take a look at more aspects of the IR: multi field circuits/field switching, its type system, and how functions can be defined to increase scalability.