Aug 30, 2021

6 min read

Transparent Zero-Knowledge Proofs With Zilch

Deploying STARKs easier

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.

**Overview of the Zilch Framework:** Using the ZeroJava compiler, the Prover provides the assembly code to Zilch along with the private and public inputs. The Prover and the Verifier interact over a limited number of rounds and the verifier either accepts the proof (i.e., she is convinced) or rejects it.

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.

For 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 while, 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 /* and */ 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 PrivateTape.read() and 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 Examples

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.

Code-snippet 1: ZeroJava program to prove that a secret number has a Hamming weight that is greater than 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.

Code-snippet 2: Zero-knowledge range query implemented in ZeroJava.

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 min and 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 false, otherwise.

Code-snippet 3: Object-oriented zero-knowledge range query implemented in ZeroJava.

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:

2. StarkWare’s STARK Math blog series:

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