This article provides several examples of algebraic groups so that you can build an intuition for them.
A group is a set with:
We also discussed abelian groups. An abelian group has the additional requirement that the binary operator is commutative.
Now it’s time to discuss groups as a mathematical structure.
One confusing aspect of using integers under addition as an example of a group is that students often respond with, “but can’t you also multiply integers?”
Admittedly, this can be confusing. There are other algebraic structures, like rings and fields, that involve two binary operators. However, for now, think of a group as having one fixed and unchanging binary operator, and from the group’s perspective, any other possible binary operator either does not exist or isn’t a concern.
Here’s where it gets even more confusing. Sometimes binary operators are other binary operators in disguise.
For example, when dealing with groups that only have addition, sometimes writers casually refer to multiplication even though the group does not have that binary operator. What multiplication is in this context is really shorthand for repeating an addition operation a certain number of times.
The best way to get a feel for a group is to see a lot of them. Let’s do that.
Let our group be a set consisting of the number $\set{0}$ with the binary operator of addition. It is clear that the binary operator is closed and associative
$$ (0 + 0) + 0 = (0 + 0) + 0 $$
and each element has an identity and inverse.
This is not an interesting group, but it is the smallest valid you can create.
Note that a group cannot be empty because by definition it must contain an identity element.
As an exercise for the reader, show that the set $\set{1}$ with the binary operator $\times$ is a group.
Although reals ($\mathbb{R}$) under multiplication has an identity (the number $1$) and is closed and associative, they do not all have an inverse.
Real numbers are invertible by taking their multiplicative inverse $(1 / n)$, but zero, although a real number, cannot be inverted because $1/0$ is undefined and not a real number.
Strictly speaking, the inverse of $a$, is $b$ such that $ab = 1$. Here we are saying that if $a = 0$ there is no element in the set $b$ such that $ab = 1$.
Positive real numbers excluding zero are a group under multiplication however. Every element has an inverse ($1/n$), and the identity element is 1.
Exercise: Integers (positive and negative) are not a group under multiplication. Show which of the four requirements (closed, associative, existence of identity, all elements having an inverse) are not satisfied.
Let’s work it out:
Matrix addition is closed and associative. If you add an $n × m$ matrix of real numbers with another $n × m$ matrix of real numbers, you get an $n × m$ matrix of real numbers. The identity matrix is an $n × m$ matrix of all zeros the inverse of a matrix is that matrix multiplied by -1. Hey wait, we aren’t allowed to multiply by -1 right?
A group doesn’t require the inverse to be “computable using the group binary operator” only to exist. That is, we compute the inverse as multiplying each element by $-1$ even though multiplication by $-1$ is not a group operation.
If we define our operator for $n \times m$ matrices to be the Hadamard product (element-wise multiplication), this cannot be a group for the same reason discussed above. Specifically, the inverse is computed as the reciprocal of each element in the matrix, and if one of the elements is zero, then the inverse cannot be computed.
If we define our operator to be traditional matrix multiplication over square matrices, this may or may not be a group depending on the set definition, as we will see in section example 5.
This is actually a special case of the previous example, but let’s look at it through a different angle.
Consider the set of all real-valued $(x, y)$ points on a standard 2D plane.
Our binary operator is adding points together, for example $(1,1) + (2,2) = (3,3)$.
Our identity element is the origin, because adding with that will result in the same location of the other point.
The inverse of a point is simply the “mirror image” over the origin (with the $x$ and $y$ coordinates negated) because when you add a point to its inverse, they result in the origin.
By way of review, if a matrix has a non-zero determinant, then it is invertible. When a matrix of non-zero determinant is multiplied by another matrix of non-zero determinant, then the product also has a non-zero determinant. Actually, we can be more specific, if $A$, $B$, and $C$ are square matrices, and $AB = C$, then $\det(a) \times \det(b) = \det(c)$.
Let’s work through the definitions
Remember, a matrix with zero determinant cannot be inverted, so this set cannot have an inverse. In this case, we do not have an identity element because the identity matrix has determinant one. Since we have no identity element, this set and binary operator isn’t even a monoid, it’s a semigroup.
If we say “all polynomials with real coefficients of degree at most 7 under addition” this is a valid group.
Polynomials of a fixed upper-bounded degree under multiplication are not a group, because generally the degree gets larger when you multiply polynomials, hence the operator would not be closed.
Let’s take a prime number $7$.
Here, the identity is still $0$, because you add by $0$ and get the same number back.
In this situation, what would the inverse of $5$ be?
It would just be $2$, because $7 – 5 = 2$, or $5 + 2 \mod 7$ is zero (the identity).
Zero doesn’t have an inverse for this example.
If we omit the number $0$, then we have a group. The identity element is 1, and the inverse of an element $a$ is its modular inverse $a^{-1}$.
If two integer powers of $b$ are multiplied together, the result is the integer power of the product of the bases. For example, $2^3 \times 2^4 = 2^{3 + 4} = 2^7$. This works for arbitrary bases:
$$ b^x \times b^y = b^{x + y} $$
The identity element is $b^0$, which is $1$, and the inverse of $b^x$ is $b^{-x}$.
As the name suggests, a finite group has a finite number of elements in it. The set of all integers under addition is not finite, but addition of integers modulo a prime number is a finite group.
In zero knowledge proofs, we only use finite groups.
The order of a group is the number of elements in it.
A cyclic group is a group that has an element such that every element in the group can be “generated” by applying the binary operator repeatedly to that element, or to it’s inverse.
This is trivially true because $0 + 0 = 0$ generates every element in the group.
If we start with $1$ and add $1$ to itself repeatedly, we will generate every element in the group. For example:
$$ \begin{align*} &1 + 1 &= 2 \\ &1 + 1 + 1 &= 3 \\ &1 + 1 + 1 + 1 &= 4 \\ &1 + 1 + 1 + 1 + 1 &= 5 \\ &1 + 1 + 1 + 1 + 1 + 1 &= 6 \\ &1 + 1 + 1 + 1 + 1 + 1 + 1 &= 0 \\ &1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 &= 1 \\ \end{align*} $$
We have to be careful when picking the generator here, because, for example, $2$ won’t generate the whole group.
$$ \begin{align*} &2 * 2 &\equiv 4 \pmod 7 \\ &2 * 2 * 2 &\equiv 1 \pmod 7 \\ &2 * 2 * 2 * 2 &\equiv 2 \pmod 7 \\ &2 * 2 * 2 * 2 * 2 &\equiv 4 \pmod 7 \\ &…\ \end{align*} $$
We can see that $2$ can only generate $\set{1,2,4}$. However, if we pick $3$ as the generator, then we can generate the whole group.
$$ \begin{align*} 3 ^ 2 \equiv 2 \pmod 7 \\ 3 ^ 3 \equiv 6 \pmod 7 \\ 3 ^ 4 \equiv 4 \pmod 7 \\ 3 ^ 5 \equiv 5 \pmod 7 \\ 3 ^ 6 \equiv 1 \pmod 7 \\ 3 ^ 7 \equiv 3 \pmod 7 \\ &…\ \end{align*} $$
The reason why $3$ works and $2$ does not is because $3$ is a primitive root.
We can use the galois library to find primitive roots:
from galois import GF
GF7 = GF(7)
print(GF.primitive_elements)
# [3, 5]From the code output above, we can see that $5$ will also generate all the non-zero elements.
This one is a bit more subtle, but consider this:
In a cyclic group, every element in the group can be generated as $(g + g + … + g)$. Let’s arbitrarily pick an element $r$. Let’s partition this set of additions like so
$$ r = \underbrace{g + g + \dots + g}_\text{m times} + \underbrace{g + g + \dots + g}_\text{n times} $$
Because of associativity, we can add parenthesis
$$ r = \underbrace{(g + g + \dots + g)}_\text{m times} + \underbrace{(g + g + \dots + g)}_\text{n times} $$
Let $g$ added to itself $m$ times be $p$ and $g$ added to itself $n$ times be $q$. Therefore,
$$r = p + q$$
By associativity, we can repartition the original equation as follows (note that the $m$ and $n$ switched places!)
$$ r = \underbrace{(g + g + \dots + g)}_\text{n times} + \underbrace{(g + g + \dots + g)}_\text{m times} $$
And we get back:
$$r = q + p$$
Hence, if the group is cyclic, then the group is abelian.
Note that the converse of this statement isn’t true. Real numbers under addition are an abelian group, but they are not cyclic.
Cyclic groups don’t have to be arithmetic modulo some prime number, but these are the only cyclic groups we will be using in our discussion of zero knowledge proofs.
A group cannot have two identity elements. Don’t overthink this one, it’s derived by simple contradiction. Let’s say $\square$ is our binary operator and $e$ is our identity element.
Let’s say we have an alternative identity element $e’$. This means the following:
$$a \square a^{-1} = e \text{ and } a \square a^{-1} = e’$$
If we say $e≠e’$, then it must also be true that
$$a \square a^{-1} \neq a \square a^{-1}$$
But that is obviously a contradiction, hence identity elements must be unique.
Understanding group theory for the purpose of zero knowledge proofs is more of an exercise in vocabulary. When we say “inverse” or “identity” we want to you to immediately grasp what those mean.
Additionally, groups help us reason about very complex mathematical objects without understanding how they work. We’ve used familiar examples in this article, but later on we will deal with very unfamiliar objects such as elliptic curves over field extensions. Even though you don’t know what exactly that is, if we tell you it is a group, you already know a lot about what it is.
This article is part of a series on ZK proofs. See our ZK Book for the full series.
Originally Published August 1, 2023
The intuition behind elliptic curve digital signatures (ECDSA) This article explains how the ECDSA (Elliptic Curve Digital Signature Algorithm) works as well as why it works. We will incrementally “rediscover” the algorithm from first principles in this tutorial. Prerequisites We assume prior knowledge of Elliptic Curve Arithmetic Elliptic Curve Arithmetic in Finite Fields Digital Signature […]
Trusted Setup A trusted setup is a mechanism ZK-SNARKs use to evaluate a polynomial at a secret value. Observe that a polynomial $f(x)$ can be evaluated by computing the inner product of the coefficients with successive powers of $x$: For example, if $f(x)=3x^3+2x^2+5x+10$, then the coefficients are $[3,2,5,10]$ and we can compute the polynomial as […]
The Schwartz-Zippel Lemma and its application to Zero Knowledge Proofs Nearly all ZK-Proof algorithms rely on the Schwartz-Zippel Lemma to achieve succintness. The Schwartz-Zippel Lemma states that if we are given two polynomials $p(x)$ and $q(x)$ with degrees $d_p$ and $d_q$ respectively, and if $p(x) \neq q(x)$, then the number of points where $p(x)$ and […]
Building a Zero Knowledge Proof from an R1CS Given an arithmetic circuit encoded as a Rank 1 Constraint System, it is possible to create a ZK-proof of having a witness, albeit not a succinct one. This article describes how to accomplish that. A zero knowledge proof for an R1CS is accomplished by converting the witness […]