Dizk

<h1 align="center">DIZK</h1> <p align="center"> <a href="https://travis-ci.org/scipr-lab/dizk"><img src="https://travis-ci.org/scipr-lab/dizk.svg?branch=master"></a> <a href="https://github.com/scipr-lab/dizk/blob/master/AUTHORS"><img src="https://img.shields.io/badge/authors-SCIPR%20Lab-orange.svg"></a> <a href="https://github.com/scipr-lab/dizk/blob/master/LICENSE"><img src="https://img.shields.io/badge/license-MIT-blue.svg"></a> </p> <h4 align="center">Java library for distributed zero knowledge proof systems</h4>

DIZK (pronounced /'dizək/) is a Java library for distributed zero knowledge proof systems. The library implements distributed polynomial evaluation/interpolation, computation of Lagrange polynomials, and multi-scalar multiplication. Using these scalable arithmetic subroutines, the library provides a distributed zkSNARK proof system that enables verifiable computations of up to billions of logical gates, far exceeding the scale of previous state-of-the-art solutions.

The library is developed by SCIPR Lab and contributors (see AUTHORS file) and is released under the MIT License (see LICENSE file).

The library is developed as part of a paper called "DIZK: A Distributed Zero Knowledge Proof System".

WARNING: This is an academic proof-of-concept prototype. This implementation is not ready for production use. It does not yet contain all the features, careful code review, tests, and integration that are needed for a deployment!

Table of contents

• Directory structure
• Overview
• Build guide
• Profiler
• Benchmarks
• References
• License

Directory structure

The directory structure is as follows:

• src: Java directory for source code and unit tests
  • main/java: Java source code, containing the following modules:
    • algebra: fields, groups, elliptic curves, FFT, multi-scalar multiplication
    • bace: batch arithmetic circuit evaluation
    • common: standard arithmetic and Spark computation utilities
    • configuration: configuration settings for the Spark cluster
    • profiler: profiling infrastructure for zero-knowledge proof systems
    • reductions: reductions between languages (used internally)
    • relations: interfaces for expressing statement (relations between instances and witnesses) as various NP-complete languages
    • zk_proof_systems: serial and distributed implementations of zero-knowledge proof systems
  • test/java: Java unit tests for the provided modules and infrastructure

Overview

This library implements a distributed zero knowledge proof system, enabling scalably proving (and verifying) the integrity of computations, in zero knowledge.

A prover who knows the witness for an NP statement (i.e., a satisfying input/assignment) can produce a short proof attesting to the truth of the NP statement. This proof can then be verified by anyone, and offers the following properties.

• Zero knowledge - the verifier learns nothing from the proof besides the truth of the statement.
• Succinctness - the proof is small in size and cheap to verify.
• Non-interactivity - the proof does not require back-and-forth interaction between the prover and the verifier.
• Soundness - the proof is computationally sound (such a proof is called an argument).
• Proof of knowledge - the proof attests not just that the NP statement is true, but also that the prover knows why.

These properties comprise a zkSNARK, which stands for Zero-Knowledge Succinct Non-interactive ARgument of Knowledge. For formal definitions and theoretical discussions about these, see [BCCT12] [BCIOP13] and the references therein.

DIZK provides Java-based implementations using Apache Spark [Apa17] for:

1. Proof systems
   • A serial and distributed preprocessing zkSNARK for R1CS (Rank-1 Constraint Systems), an NP-complete language that resembles arithmetic circuit satisfiability. The zkSNARK is the protocol in [Gro16].
   • A distributed Merlin-Arthur proof system for evaluating arithmetic circuits on batches of inputs; see [Wil16].
2. Scalable arithmetic
   • A serial and distributed radix-2 fast Fourier transform (FFT); see [Sze11].
   • A serial and distributed multi-scalar multiplication (MSM); see [BGMW93] [Pip76] [Pip80].
   • A serial and distributed Lagrange interpolation (Lag); see [BT04].
3. Applications using the above zkSNARK for
   • Authenticity of photos on three transformations (crop, rotation, blur); see [NT16].
   • Integrity of machine learning models with support for linear regression and covariance matrices; see [Bis06] [Can69] [LRF97] [vW97].

Build guide

The library has the following dependencies:

• Java SE 8+
• Apache Maven
• Fetched from pom.xml via Maven:
  • Spark Core 2.10
  • Spark SQL 2.10
  • JUnit 4.11
  • Google Java Format
• Fetched via Git submodules:
  • spark-ec2

Why Java?

This library uses Apache Spark, an open-source cluster-computing framework that natively supports Java, Scala, and Python. Among these, we found Java to fit our goals because we could leverage its rich features for object-oriented programming and we could control execution in a (relatively) fine-grained way.

While other libraries for zero knowledge proof systems are written in low-level languages (e.g., libsnark is written in C++ and bellman in Rust), harnessing the speed of such languages in our setting is not straightforward. For example, we evaluated the possibility of interfacing with C (using native binding approaches like JNI and JNA), and concluded that the cost of memory management and process inferfacing resulted in a slower performance than from purely native Java execution.

Installation

Start by cloning this repository and entering the repository working directory:

git clone https://github.com/scipr-lab/dizk.git
cd dizk

Next, fetch the dependency modules:

git submodule init && git submodule update

Finally, compile the source code:

mvn compile

Docker

cd your_dizk_project_directory

docker build -t dizk-container .
docker run -it dizk-container bash

Testing

This library comes with unit tests for each of the provided modules. Run the tests with:

mvn test

Profiler

Using Amazon EC2, the profiler benchmarks the performance of serial and distributed zero-knowledge proof systems, as well as its underlying primitives. The profiler uses spark-ec2 to manage the cluster compute environment and a set of provided scripts for launch, profiling, and shutdown.

Spark EC2

To manage the cluster compute environment, DIZK uses spark-ec2@branch-2.0. spark-ec2 is a tool to launch, maintain, and terminate Apache Spark clusters on Amazon EC2.

To setup spark-ec2, run the following commands:

git clone https://github.com/amplab/spark-ec2.git
cd spark-ec2
git checkout branch-2.0
pwd

Remember where the directory for spark-ec2 is located, as this will need to be provided as an environment variable for the scripts as part of the next step.

Profiling scripts

To begin, set the environment variables required to initialize the profiler in init.sh. The profiling infrastructure will require access to an AWS account access key and secret key, which can be created with the instructions provided by AWS.

export AWS_ACCESS_KEY_ID={Insert your AWS account access key}
export AWS_SECRET_ACCESS_KEY={Insert your AWS account secret key}

export AWS_KEYPAIR_NAME="{Insert your AWS keypair name, e.g. spark-ec2-oregon}"
export AWS_KEYPAIR_PATH="{Insert the path to your AWS keypair .pem file, e.g. /Users/johndoe/Downloads/spark-ec2-oregon.pem}"

export AWS_REGION_ID={Insert your AWS cluster region choice, e.g. us-west-2}
export AWS_CLUSTER_NAME={Insert your AWS cluster name, e.g. spark-ec2}

export SPOT_PRICE={Insert your spot price for summoning an EC2 instance, e.g. 0.1}
export SLAVES_COUNT={Insert the number of EC2 instances to summon for the cluster, e.g. 2}
export INSTANCE_TYPE={Insert the instance type you would like to summon, e.g. r3.large}

export DIZK_REPO_PATH="{Insert the path to your local DIZK repository, e.g. /Users/johndoe/dizk}"
export SPARK_EC2_PATH="{Insert the path to your local spark-ec2 repository, e.g. /Users/johndoe/dizk/depends/spark-ec2}"

Next, start the profiler by running:

./launch.sh

The launch script uses spark-ec2 and the environment variables to setup the initial cluster environment. This process takes around 20-30 minutes depending on the choice of cluster configuration.

After the launch is complete, upload the DIZK JAR file to the master node and SSH into the cluster with the following command:

./upload_and_login.sh

Once you have successfully logged i