1  # alphavm-algorithms/snark/varuna
 2  
 3  `varuna` is a Rust module that implements a
 4  <p align="center">
 5  <b>preprocessing zkSNARK for R1CS</b><br>
 6  with<br>
 7  <b>universal and updatable SRS</b>
 8  </p>
 9  
10  ## Overview
11  
12  A zkSNARK with **preprocessing** achieves succinct verification for arbitrary computations, as opposed to only for structured computations.
13  Informally, in an offline phase, one can preprocess the desired computation to produce a short summary of it; subsequently, in an online phase, this summary can be used to check any number of arguments relative to this computation.
14  
15  The preprocessing zkSNARKs in this library rely on a structured reference string (SRS), which contains system parameters required by the argument system to produce/validate arguments.
16  The SRS in this library is **universal**, which means that it supports (deterministically) preprocessing any computation up to a given size bound.
17  The SRS is also **updatable**, which means that anyone can contribute a fresh share of randomness to it, which facilitates deployments in the real world.
18  
19  The construction in this library obtains a preprocessing zkSNARK with a universal and updatable SRS by combining two ingredients:
20  * an **algebraic holographic proof**
21  * a **polynomial commitment scheme**
22  
23  ## Profiling
24  
25  This library is instrumented with profiling infrastructure that prints detailed traces of execution time. To enable this, compile with `cargo build --features profiler`.
26  
27  ## Benchmarks
28  
29  Benchmarks were run on a machine with an Intel Xeon 6136 CPU running at 3.0 GHz.
30  
31  ### Running time compared to Groth16 
32  
33  The graphs below compare the running time, in single-thread execution, of Marlin's indexer, prover, and verifier algorithms with the corresponding algorithms of [Groth16][groth16] (the state of the art in preprocessing zkSNARKs for R1CS with circuit-specific SRS) as implemented in [`groth16`](https://github.com/scipr-lab/zexe/tree/master/groth16).
34  We evaluate Marlin's algorithms when instantiated with the PC scheme from [[CHMMVW20]][marlin] (denoted "M-AHP w/ PC of [[CHMMVW20]][marlin]"), and the PC scheme from [[MBKM19]][sonic] (denoted "M-AHP w/ PC of [[MBKM19]][sonic]").
35  
36  <p align="center">
37  <img hspace="20" src="https://user-images.githubusercontent.com/3220730/82859703-52546100-9ecc-11ea-8f9d-ec2fb10f042d.png" width="45%" alt = "Indexer">
38  <img hspace="20" src="https://user-images.githubusercontent.com/3220730/82859705-52ecf780-9ecc-11ea-84cc-99eda9f13d6a.png" width="45%" alt = "Prover">
39  </p>
40  <p align="center">
41  <img src="https://user-images.githubusercontent.com/3220730/82859701-52546100-9ecc-11ea-8422-877080662073.png" width="45%" alt = "Verifier">
42  </p>
43  
44  ### Multi-threaded performance
45  
46  The following graphs compare the running time of Marlin's prover when instantiated with the PC scheme from [[CHMMVW20]][marlin] (left) and the PC scheme from [[MBKM19]][sonic] (right) when executed with a different number of threads.
47  
48  <p align="center">
49  <img hspace="20" src="https://user-images.githubusercontent.com/3220730/82859700-51bbca80-9ecc-11ea-9fe1-53a611693dd1.png" width="45%" alt = "Multi-threaded scaling of Marlin AHP with the PC scheme from [CHMMVW20]">
50  <img hspace="20" src="https://user-images.githubusercontent.com/3220730/82859698-51233400-9ecc-11ea-8a32-37379116e828.png" width="45%" alt = "Multi-threaded scaling of Marlin AHP with the PC scheme from [MBKM19]">
51  </p>