Transparent Zero-Knowledge Proofs With Zilch
Zilch is a framework that implements Scalable and Transparent (i.e., no need for trusted setup) ARguments of Knowledge (STARKs). Zilch consists of two main components: a front-end and a back-end.
1) The front-end consists of the ZeroJava programming language, a subset of Java designed for zero-knowledge arguments, and a compiler for translating the ZeroJava code to zMIPS assembly instructions; zMIPS is our extension to the MIPS ISA to support programming ZKPs.
2) The back-end translates the zMIPS assembly instructions to arithmetic circuits and generates ZKPs for verifying the evaluation of these circuits. The back-end builds upon the ZKP constructions of the zkSTARK library and extends the programming model of libSTARK to the zMIPS abstract machine.
1) Zilch Front-End
ZeroJava Language & Compiler
ZeroJava is a custom subset of Java tailored to zero-knowledge proofs. It is possible to compile ZeroJava programs to byte code with a Java compiler if the ZK-specific instructions are omitted. ZeroJava abstains from features of Java that complicate the run-time system, such as exceptions and multi-threading.
ZeroJava is object-oriented, like Java. The basic types of ZeroJava are
int for integer,
boolean for logical values, and
int for arrays of integers. Classes contain attributes and methods with arguments and return type of basic or class types. ZeroJava supports single inheritance but not interfaces and function overloading (i.e., each method name must be unique). In addition, all methods are inherently polymorphic; meaning that a method can be defined in a subclass if it has the same return type and arguments as in the parent. Fields in the base and derived class are allowed to have the same names and are essentially different fields. All ZeroJava methods are
public and all fields
protected, which means that a class method cannot access fields of another class, with the exception of its parent. A class's own methods can be called via
this. Local variables are defined only at the beginning of a method and local variables shadow fields of the surrounding class with the same name.
In ZeroJava, the
new operator calls a default void constructor. In addition, there are no inner classes and there are no static methods or fields. A ZeroJava program begins with a special main class which does not have fields and methods and contains the
main method (i.e.,
public static void main(String args)). After the main class, other classes may be defined that can have fields and methods.
int arrays, ZeroJava supports the assignment and lookup (
) operators, as well as the
array.length expression, which returns the size of the array. ZeroJava supports
if code blocks as well as ternary operators. The assignment
A a = new B(); when
B extends A is correct, and the same applies when a method expects a parameter of type
A and a
B instance is given instead. Finally, ZeroJava supports comments like Java, where the delimiter
// is used for a single line comment and delimiters
*/ are used for a block of lines.
ZeroJava also supports seven built-in functions tailored to proving zero-knowledge arguments, shown in Table I. More specifically, the
Prover.answer(int res) function call immediately terminates the computation and returns the value
res . The
System.exit(int) method can be used to terminate the execution of a ZeroJava program and at the same time return a status code for debugging purposes. The
PublicTape.read() statements return the next word that is placed in the private and public tape, respectively. Similarly, the
PrivateTape.seek(int n) and
PublicTape.seek(int n) statements return the
n’th word from the private and public tape, respectively.
ZeroJava Example 1: In code-snippet 1, we demonstrate a ZeroJava program that implements Wegner’s efficient algorithm to compute the Hamming weight of a secret number and then compares it with a public threshold.
This example highlights various features of ZeroJava, such as reading from the public and the private tapes, performing loops, as well as applying arithmetic, logical, and bitwise operations. Besides, a potential application of this algorithm could be to compute the Hamming weight of a private RSA exponent in zero-knowledge and convince a verifier that it is greater than a threshold; this offers additional assurance against certain attacks (e.g., birthday attacks on RSA private exponents with low Hamming weight).
ZeroJava Example 2: Another very popular example is the zero-knowledge range proof (ZKRP). Determining interest rates (e.g., when applying for a mortgage) may require disclosing the credit score of the applicant. ZKRP enables determining interest rates or loan eligibility while maintaining the privacy of credit scores. Similarly, ZKRP enables proving that an account has enough available balance for a transaction, or that an individual is older than 18 years and younger than 65 years without disclosing the exact age.
In this example (shown in code-snippet 2), the prover wants to prove that their secret value (e.g.,
val) lies within a range (e.g.,
min <= val <= max) without revealing what the value of
val is. Thus, Zilch uses the public tape to put
max range values, whereas it reads the secret
val value from the private tape. Finally, Zilch returns
true if the
val is within the public range or
ZeroJava allows the developer to express the range queries either using the procedural programming paradigm (i.e., in the example shown in code-snippet 2) or the using the object-oriented programming paradigm as shown in code-snippet 3. In this case, the method to determine if a secret number is within the public range is a class method and is invoked by instantiating a class object.
The ZeroJava compiler is open-source on https://github.com/TrustworthyComputing/ZeroJava-compiler and includes these examples (e.g., hamming distance and range query) and more.
2) Zilch Back-End
zMIPS Instruction Set Architecture
zMIPS is our extension to the MIPS ISA to support programming ZKPs. The front-end of Zilch translates ZeroJava programs into zMIPS instructions, which are in turn consumed by the Zilch back-end to generate the final proof.
Table II shows the zMIPS ISA which includes arithmetic, bitwise, comparisons, load/store, and I/O operations. Zilch allows developers to both use the ZeroJava compiler or program their applications directly in zMIPS.
For instance, the zero-knowledge range proof example that we previously studied can be expressed in zMIPS directly as shown in the code snippet on the left.
The Zilch framework is open-source on https://github.com/TrustworthyComputing/Zilch.
The Zilch framework builds upon the zk-STARK constructions and enhances its programming model by utilizing the ZeroJava compiler and zMIPS ISA. More details about how zk-STARK works are provided in the following post series:
- Vitalik Buterin’s blog series on zk-STARKs:
- STARKs, part 1: Proofs with Polynomials
- STARKs, part 2: Thank Goodness it’s FRI-day
- STARKs, part 3: Into the Weeds
2. StarkWare’s STARK Math blog series:
- STARK Math: The Journey Begins
- Arithmetization I
- Arithmetization II
- Low Degree Testing
- A Framework for Efficient STARKs
More details about how the Zilch framework and ZeroJava compiler work can be found on:
D. Mouris and N. G. Tsoutsos, “Zilch: A Framework for Deploying Transparent Zero-Knowledge Proofs,” in IEEE Transactions on Information Forensics and Security (TIFS), 2021, DOI: 10.1109/TIFS.2021.3074869
— Dimitris Mouris