A homomorphism is a structure-preserving map between two algebraic structures that allows us to perform operations on transformed data while maintaining the relationships with the original data.
This article is the sixth in our series of mathematical prerequisites for understanding zero-knowledge (ZK) proofs. Understanding homomorphisms is crucial because it allows us to perform computations on encrypted or committed data without revealing the original values, making zero-knowledge proofs possible.
This article will cover what homomorphisms are, why they're necessary for zero-knowledge proofs, and go through some examples.
A homomorphism is a function between two algebraic structures (like groups, rings, or fields) that preserves the operations of those structures.
Think of a homomorphism as a "translator" that converts elements from one mathematical world to another while keeping all the relationships intact.
More formally, let $(G, \circ)$ and $(H, \star)$ be two groups. (Recall: this notation means that we are defining a group with the sets $G$ and $H$ and binary operators $\circ$ and $\star$ respectively.) A function which maps elements from the set $G$ and $H$, $\phi: G \to H$ is called a group homomorphism if for all elements $a, b \in G$:
$$\phi(a \circ b) = \phi(a) \star \phi(b)$$
This means that, if we first apply the group operation $\circ$ to $a$ and $b$ and then map it to the set $H$ using the function $\phi$, this is equivalent to applying $\phi$ to the elements $a$ and $b$ individually and then operating on the results using $\star$.
The homomorphism $\phi$ preserves the group operation.
Why does this matter? It allows us to perform operations on transformed data while maintaining the relationships from the original data. Exactly what we need for zero-knowledge proofs!
When the function $\phi: G \to H$ is a group homomorphism, several important properties automatically follow:
Note: For additive groups, this becomes $\phi(na) = n[\phi(a)]$
And these properties being preserved show that the algebraic structure itself is completely preserved under the transformation!
Let's look at some examples to illustrate different types of homomorphism and really understand what we mean by a “homomorphism”:
Let’s take the exponential function $\exp$. This function is a homomorphism between the set of real numbers under addition $(\mathbb{R}, +)$ to the set of positive real numbers under multiplication $(\mathbb{R}^+, \cdot)$.
Or mathematically:
$$\exp: (\mathbb{R}, +) \to (\mathbb{R}^+, \cdot)$$
Where \exp is defined as \exp(x) = e^x and is a group homomorphism because for all x, y \in \mathbb{R}:
$$\exp(x + y) = e^{x+y} = e^x \cdot e^y = \exp(x) \cdot \exp(y)$$
This shows that addition in the real numbers corresponds exactly to multiplication in the positive real numbers. Test it yourself: take any two real numbers, add them, and then take the exponent, the result will be equal to taking the exponent and then multiplying the results.
$$\exp(-3 + 5) = e^{-3+5}=e^{-3}\cdot e^5 = \exp(-3) \cdot \exp(5)$$
Consider the function $f$: modular reduction by $n$. It maps elements from the set of integers, $\mathbb{Z}$ which forms a ring under addition and multiplication, to the set of integers modulo $n$, $\mathbb{Z}/n\mathbb{Z}$.
Mathematically, we say:
$$f: \mathbb{Z} \to \mathbb{Z}/n\mathbb{Z}$$
Where $f$ is defined as $f(a) = a \bmod n$
This is a ring homomorphism because it preserves both operations:
This maps integers $a$ and $b$ to their equivalence classes modulo $n$.
Note: We call it a ring homomorphism because $\mathbb{Z}$ is a ring (not a field), since most integers don't have multiplicative inverses.
In zero-knowledge proof systems, homomorphisms enable you to prove knowledge of secret information without revealing it.
PLONK uses homomorphic commitment schemes where:
The homomorphic structure is what enables the "magic" of ZK proofs.
Private inputs can be transformed into public “commitments” via homomorphisms, AKA these commitment functions. Then, the relationships between private values become relationships between public values, which allows complex computations to be verified through simple algebraic checks on these public values.
In PLONK, we don't just commit to individual numbers, instead, we commit to polynomials. These polynomials encode the complex computations and constraints from our original problem, e.g., I know the inputs $x$ and $y$ that satisfy the constraints $2x + y = 0$ and $y > 0$.
AND the polynomial operations are naturally homomorphic as well:
This means that when we commit to polynomials, we can perform polynomial arithmetic on the commitments themselves and this corresponds directly to the underlying data the polynomial encodes, enabling complex proof systems while maintaining zero-knowledge.
Polynomials are a topic we'll revisit in a future article, so if you feel lost, don’t worry. This is simply a teaser of how everything will link together.
Homomorphisms let you "move" problems from the secret world to the public world. They do this by preserving the mathematical relationships that need to be proven while keeping private values secret.
In our next article, we'll explore elliptic curves: what they are and the properties that make them extremely useful in cryptography. The homomorphic properties of elliptic curves over finite fields (don’t worry, we will explain what this means in the following article) make them useful in cryptographic signatures and zero-knowledge proofs!
