The hunting of the zk-SNARK: Homomorphic Hidings

Erik Brauer · Tue 16 Feb 2021

But the judge said he never had summed up before; so the Snark undertook it instead, and summed it so well that it came to far more than the Witnesses ever had said!

 –Lewis Carroll

Zero-knowledge succinct non-interactive arguments of knowledge are often seen as black boxes by many, due to the sheer complexity of their inner workings and the math involved in constructing these intricate machines. However, like in any complex system, breaking it down into its standalone parts reveals their underlying simplicity and the beauty of how they work together.

At Iomete Labs, we’re building privacy solutions for blockchains by utilizing zero–knowledge proofs, namely zk–SNARKs. So, in our first blogpost I want to shed some light on one of the central mathematical abstractions behind this technology, which we call homomorphic hiding functions. At the end a small cheatsheet is provided as well, in hopes that the reader will find it useful.

(Note: So far the cheatsheet is only covering QAP-based SNARK constructions with the Pinocchio and Groth16 Protocols, hence the reader is encouraged to look into newer protocols as well as the more recent advances in Bulletproofs and STARKs which require no trusted setup.)

On Homomorphisms

The first concept I want to introduce is what’s called a Homomorphism. In essence it’s a “structure-preserving map”, which means that it preserves the algebraic structure between the input and output sets of a given function. Its definition is as follows:

\(\phi(f_i(a_1,…,a_{m})) = g_i(\phi(a_1),…,\phi(a_{m}))\)

where \(\phi\) is the homomorphic function and \(f_i\) and \(g_i\) represent operations over numbers \(a_1\) to \(a_m\). A classic example for a homomorphism is the exponential function \(y(x) = e^x\). Given the operations \(+\) and \(\cdot\), we can see that the exponential function indeed satisfies our definition from above:

\(e^{x+y} = e^x \cdot e^y \: \: \forall x,y \in \mathbb{R}\)

So now that we have defined this, how is it actually useful for SNARKs?

Homomorphic Hidings

The underlying scheme of every modern cryptographic algorithm are so-called “trapdoor functions”, also known as one-way functions. They are similar to a trapdoor in the sense that they’re easy to compute in one direction, yet very hard to compute in the opposite direction without additional information. Cryptographically secure hash functions, such as SHA–2, are a prominent example of these.

For zk-SNARKs we introduce a weak version of hiding commitments called “Homomorphic Hidings” (HH). They are trapdoor functions with the additional properties of collision-resistance (if \(x\) and \(y\) are different \(E(x)\) can never be equal to \(E(y)\)) and the ability to preserve algebraic structures, i.e. they’re homomorphic.

Using our above example we can define the Homomorphic Hiding \(E(x)=e^x\). However, the exponential function is not one-way, as it’s easy to compute \(x\) given \(E(x)\) just by calculating its logarithm. To achieve the “hiding” property we first need to confine our numbers to the cyclic group \(\mathbb{Z}_p^*\), which we define as:

\(\mathbb{Z}_p^* = \{0,1,…,p–1\}\)

for a (very large) prime number \(p\). Hence, every operation we describe on this set will be calculated modulo p, for example: \(2 \cdot 3 = 1 \text{ (mod } 5)\) for a \(p = 5\). The discrete logarithm problem is assumed to be hard in this set, i.e. it’s difficult to compute the input given the output of our function. Next we also need to adjust the function itself by replacing euler’s constant \(e\) with a generator \(g\) of \(\mathbb{Z}_p^*\), which is an element from the set with which we can generate the whole set itself. With this, we can construct our Homomorphic Hiding:

\(E(x) = g^x \: \: \forall x \in \mathbb{Z}_{p–1}\)

We now have a trapdoor function that supports addition, as \(E(x+y) = g^{x+y \text{ mod p}–1} = g^x\cdot g^y = E(x)\cdot E(y).\) It also effectively hides a users inputs \(x\) if the user is only transmitting \(E(x)\). Note however, that in real world use-cases, the HH relies on Tate-Reduced pairings over elliptic curves as well as additional randomness that is applied to the commitments (more on that can be found in the cheatsheet).

A cartoon example

Now suppose Alice makes a claim to Bob that she knows a solution to the equation \(x+y = 11\). The HH is both known to them, and it’s defined as \(E(x) = 2^x\) over the group \(\{1,…,5\}\) (Note that this HH does not satisfy all of the properties mentioned above and is only used here for didactic purposes). One solution that satisfies the equation according to Alice could be \(x = 5\) and \(y = 6\). The protocol for Alice proving her claim without revealing her “witness”, i.e. her inputs to Bob would be as follows:

  1. Alice computes \(\textstyle E(x) = E(5) = 2\) and \(E(y) = E(6) = 4\) and sends only the outputs to Bob.

  2. Bob computes \(E(x+y) = E(x)\cdot E(y) = 4 \cdot 2 = 3\). (this is where the homomorphic property comes into play)

  3. Bob also computes \(E(11) = 3\) and sees that \(E(x+y) = E(11)\). Thus, he accepts Alice’s claim and can verify it without knowing its inputs.

With all of this, we have constructed our first protocol for a simple zero knowledge proof. Note that it’s obviously not secure in any way, nor is it truly zero-knowledge, since Alice can easily create fake proofs and Bob is able to reverse engineer the inputs without great effort. To deal with these issues and make the whole scheme non-interactive and succinct we need to introduce more parts to our protocol, which are documented on the cheatsheet available for download here: zk-SNARKs Cheatsheet