SuperMarlin : Adding Transparency to Marlin using 1k lines of code

We show a proof of concept for Marlin Zero Knowledge proving system, compiled with DARK polynomial commitment, based on class groups of unknown order. The resulting Supermarlin eliminates the need for a trusted setup (transparent). In this post we describe the technical details of the proof of concept and where to take it from here.

Acknowledgements: We extend our gratitude to Georgios Konstantopoulos who unlocked this entire project and in addition to Claudio Orlandi, Kobi Gurkan and Pratyush Mishra for (moral and) technical support.

Motivation

The motivation for us is two fold.

First, not many transparent zk-snarks implementations exist today. Adding another brick to this wall seems noble to us, hoping it will further encourage the exploration of this tech.

Second reason is to battle-test the KZen code base, and specifically our Class library. We invested heavily in implementing cryptography based on class groups of imaginary quadratic orders. We use some of these primitives in our MPC libraries which are core to our business of key management. Testing against more applications, like Marlin, makes the entire software stack more robust and encourages re-iteration on the implementation details.

The software stack

The software stack can be divided into libraries written by KZen and libraries written by Scipr-Lab as can be seen from the image below:

The libraries we used in the project

Scipr-Lab. Here we have 3 libraries:

• Zexe: a collection of crates that implement different parts of the zexe world. We rely mostly on the algebra and ff-fft crates.
• Poly-commit: A library for polynomial commitments.
• Marlin: Implementing Marlin zk-snark.

KZen. Here we have 2 libraries:

• Curv: library for general purpose elliptic curve cryptography.
• Class: library for class group based cryptographic primitives.

Unified stack and required changes

Thanks to brilliant software design by SCIPR-lab (see below), the integration with KZen code was natural, see diagram above. The most notable addition was an implementation of Scipr lab’s polynomial commitment traits for our Class Group library’s polynomial commitment implementation. This allows instantiating protocols which utilize polynomial commitments without a trusted setup.

This was made possible by:

• Adding an FFT-friendly curve to Curv. FFT-friendly means a curve with large two adicity. Jubjub for instance is not a good pick because it has two-adicity of 1. Therefore we chose to use Bls12–381. We used the library bls12–381 (blue box in the diagram) which provides fantastic API and documentation.
• Implementing a wrapper over Curv’s Prime Field element to satisfy Zexe’s Prime Field trait. This allows us to use any library which takes a Zexe Prime Field generic argument with Curv’s prime fields.
• Implementing a new Polynomial Commitment in Poly-commit. This is done using API calls to Class library

Overall the above changes sum up to less than 1000 lines of new code.

Observations on Marlin software stack

SCIPR-lab made their entire code abstract in such a way that there are exactly 3 Rust Traits we were required to implement to make Marlin become transparent: Field, PrimeField and PolynomialCommitment. Assuming one already has low level code for fields and for the polynomial commitment — this task becomes straight forward.

Importance of tests: In practice, we spent a lot of time debugging. FFT operations can be tested efficiently directly in Zexe. For testing the field itself, we needed to write some tests of our own in Zexe. There is of-course a generic test suite for fields however at least in our case we had some high level bugs that were not caught because of the unique way we introduced a new field, external to Zexe.

For example: when required to randomly select a field element, we call the Curv function for a random element which ignores the random number generator (RNG), simply because it was never needed. However, Marlin instantiates Fiat Shamir using the RNG and therefore it must be used when generating random field elements.

Observations on the Kzen stack

Curv proved again to be an easy interface to onboard new curves. However, Curv, in its current state, is not built to support Curves with pairings. While we needed only the scalar of bls12–381, Curv forces you to also choose a group element. We worked with G1, ignoring G2 and the pairing.

The Class library was used in this project for polynomial commitment and by that way also for Proof of Exponentiation (PoE). Both benefited a lot from this project. As an example, Class now has its own improved prime generation code with configurable number of Miller-Rabin rounds. Most importantly, our polynomial commitment scheme was proven easy to debug and robust to high level usage.

Next steps

The most burning issue is the performance. Luckily there is much to improve as the current version provides no optimizations:

Algorithmic optimizations:

• The DARK polynomial commitment paper, Section 4.5 is dedicated to optimization: evaluation at multiple points, evaluating multiple polynomials at the same point and so on.
• Our current PoE is also not optimized. For example, Algorithm 5 from the Wesolowski VDF paper can be utilized.

Software optimization:

• Enabling parallel computing / multithreading: PARI, which is the c library we use for class group operations is configured to support a single thread. The marlin stack is built with parallelization in mind and it is really easy to switch it on.
• Finding better ways to interface PARI: PARI is highly efficient as a stand alone library. PARI also keeps a huge API that can be consumed. An expert on PARI can probably work out better ways to translate PARI special types into Rust and KZen native.

Once optimizations are done we can move to proper benchmarks:

We wish to measure the key metrics for zk-snarks (size of proof, verification time etc.. ) and compare to other existing implementations, including KZG10 Marlin. Note that this will allow us to do an “apples to apples” comparison of the same Marlin implementation with various polynomial commitment schemes, giving us greater insight on the exact tradeoffs.

To conclude, any snark that utilizes Polynomial Commitments can enjoy different trade-offs and properties by switching the polynomial commitment. Specifically, we showed how Transparency property can be added to Marlin zk-snark.

The code is open source (KZen forked: zexe, poly-commit, marlin). We invite anyone to dig into the various levels of the joined stack and help us with the next steps.