Fundamental Objects
Last updated
Last updated
In this subsection we will introduce these mathematical objects: groups and fields. These are the most fundamental mathematical building blocks used in zkSNARKs. In cryptography, we work mainly with values from a field or a group. By constraining the numbers and types of numbers to those in groups and fields, we are able to derive many interesting tools and properties like verifiable computation and security guarantees.
But before we get to groups and fields, we need to talk about modular arithmetic.
Modular arithmetic is where we take positive, whole numbers and put an upper limit, where reaching the upper limit gets you back to 0, like a clock. It allows us to make a thing finite. Rather than going to infinity, there is an upper limit that takes you back to the start
For example if we make 5 the upper limit, then 5 will be akin to 0. If we were to count with this arithmetic, starting at 0, it would go 0, 1, 2, 3, 4, 0, 1, ...
So what happens if we do addition here? We will have to 'loop back' to get numbers between and . For example if we do we get , but that is not in the range we specified since is the upper bound. What we do here is keep removing until we are in our range. Since we have that . To be even clearer, we should write to also indicate that is the upper limit.
Also . Or more accurately, , where the new equals sign and name indicate to us that we are doing modular arithmetic.
Similarly with multiplication, if we had , we have that and , so .
Groups are relatively simple objects. A group consists of three things: a set, a binary operation, and an identity element. Let's go through each of those and then come back to this definition.
A set is any collection, such as or . We will primarily be interested in sets that contain numbers.
A binary operation is some operation that takes in two things and outputs a third, for example addition is a binary operation: . We are only interested in addition and multiplication, so if we ever mention a binary operation you can just think of addition or multiplication.
An identity element is any element (from our set) that, in simple words, makes the operation do nothing. Since we are only interested in addition and multiplication, the identity element of addition is ; when we add to anything we get back the same number. For example, . Similarly, for multiplication the identity element would be 1.
We can't put any set, binary operation and identity element together to get a group. Groups will require every element in the set to have an inverse. What that means is that if addition is our operation, then for every number in the set (call that number ), there must exist some other number in the set (call it ) such that . For example, if then there must be some such that . The additive inverse is how we get to 0 (the identity element for addition).
You may think that is the number that we must add to to get to , but since we are in modular groups, this is not the whole picture. If we are working , then . Thus is the number we add to to get (if we are working ).
And if multiplication is our operation, then we need to get to so for every number in the set there must be another number in the set such that . Let’s go back to our example in where . In this case , so is the inverse of when multiplying.
Now for the actual definition: A group consists of a set, a binary operation, and an identity element on the binary operation; moreover, every element in the set must have an inverse element that is also in the set.
Would the modular set with addition be a group? Well we have a set, a binary operation and an identity element (), so we just need to check that every element in the set can be added to another element in the set to get . Let’s check:
(so that is true for and )
(so that is true for and ).
Great, we have a group!
What about the same set but with multiplication where 1 is the identity element? Well let’s check:
(so that solves and )
(that solves , it is its own inverse)
That just leaves us to find a multiplicative inverse for , some element that when multiplied by returns . But we learnt at school that anything multiplied by gives us back . So definitely does not have an inverse; hence it is not a group.
However, if we remove from the set, then all the remaining elements have an inverse, meaning that we have a group!
We can write groups like so , where the numbers in the curly brackets are the set, the is the binary operation, and is the identity element. Our second example was .
It will be useful to remember that we are primarily interested in groups whose set size is prime. For example , , and are prime numbers, but , or aren't. We are interested in prime sized groups for security reasons; you don't need to understand why, but it would be good to remember.
Both fields and groups are used all over cryptography. Fields are similar to groups. In fact, fields are basically two groups smushed together.
A field consists of a set, but it has two binary operations (addition and multiplication), and two identity elements (one for each binary operation, and in our case). Every element must have an inverse for both binary operations. The only exception is . The element does not need to have a multiplicative inverse because it does not have a multiplicative inverse.
In the examples above working with the set , we showed that every element had an additive inverse. In the same set, every element except had a multiplicative inverse.
Now, if we smush the addition group and multiplication group together, we would get a field. We could write this field as similar to our notation for groups, but more commonly we will write this as . Whenever you see this you should understand it to be a field where addition and multiplication are the 2 binary operations, with as the additive inverse and as the multiplicative inverse. The number, in this case, represents what the set will be; the numbers to .
would be the same but with numbers ( to ). We will see fields like this a lot in cryptography, but usually they will be absolutely huge, containing something like numbers (roughly the number of protons predicted to exist in our observable universe).