Zk-Snarks has always been a black box to most ZK developers, and our motivation is to deconstruct the black box into its base level primitives, showcasing the various techniques that can be used to transform a much complex constraints problem into simpler univariate polynomials that are much easier and efficient to dealt with.

We implement cryptographic primitives to reduce a Zk-Snark circuit into a univariate polynomial eventually. We call it "Hello, Hypercube!" because a multilinear polynomial can be represented as points on a Boolean hypercube and reduced through evaluations on its partial sum (using sumcheck).

Univarization is a process used in polynomial interpolation. In a multilinear polynomial, there are multiple variables, each with a maximum of degree one. This can make the polynomial complex and difficult to work with, especially in the context of creating zero-knowledge proofs. With univarization, it transforms a multivariate polynomial into a univariate polynomial, which has only one variable. This allows us to take in a zkSnark construction in the form of a multivariate polynomial, transform it into a simpler polynomial using sumcheck, and finally apply univarization to the polynomial. There are different ways this can be done, where we implemented two of them (Logup+ and Gemini), and the third method ZeroMorph which we didn’t have time to implement. We are looking to benchmark the proving time and size eventually.

The full technical details of our work is described in the Github README.

Writing low-level polynomial constructions require making sure that the maths work. We use the arkworks library for dealing with polynomials, but many of the evaluations have to be hand-coded. Testing these maths and debugging across different layers to make sure they are bug-free are also challenging.

When working with univariate polynomials, we have to deal with them in both the integer domain and in the multiplicative subgroup domain, which is tough too.

We split the tasks where each of us write a different part, and writing low level primitives means that integrating them together is challenging even if the interface that we used is slightly different.

Discussion