Groups and Fields

ZK-SNARKs are a complex beast, and it is hard to fully understand them. I have previously talked about them at a high level, but today I want to begin addressing their algebraic structure. The way to deal with this is the same we apply in everyday life: to create layers of abstraction so that we only deal with those things that are most relevant to our concerns at the time, and ignore the rest. 

When I go to work every day, I don’t have to worry how the trains are kept running on time (although, this being England, that doesn’t quite happen when it rains, when it snows, when it is summer, or when the leaves fall). I mostly don’t have to worry with how the supermarket shelves are replenished every day (once again, this being England, maybe that last bit will have turned into my main worry if you’re reading this past Brexit-day).

In computer terms, when I write a program I don’t have to worry with the networking stack; or how the Operating System schedules multiple tasks executing at the same time in my system. All of this is hidden behind convenient layers of abstraction, that just provide me with the service I need at the right level.

The same is true for Cryptography and in particular for ZK-SNARKs: you can grab a tool and simply use it to produce your keys and your proofs without worrying with the algebraic groups and elliptic-curves underneath. That is, until you have to program such a tool yourself.

Elliptic-Curve pairings

The magic maths powering ZK-SNARKs is usually that of Elliptic-Curve pairings. Much of the complexity in them comes from here: pairings are not easy, nor elliptic-curves, but by studying them in abstraction layers, this may become a little simpler. This post aims precisely to give you an understanding of pairings, in as easy a way as I can find, and start the task of breaching through them, piece by piece.

Abstraction Layers

First, let us divide this topic in successive levels and get a bird’s eye view:

• A pairing is a function that takes two points from sets S1 and S2 and maps them (pairs them) onto a third set S3. In order to be a pairing, this function must be bilinear, in some sense.
• The sets S1, S2 and S3 are actually groups. S1 is defined over a kind of mathematical object called an elliptic curve, while S2 and S3 are typically defined on other curves related to the first one.
• An elliptic curve is the set of points of a certain universe that satisfy a given equation. It’s really the same as a straight line, which is the set of points that satisfy an equation similar to y = mx + b, except that the curve equation is more complex.
• A group is actually a structure of a set S together with a single operation acting on the elements of S. This operation is well-defined for particular elliptic-curves defined for cryptographic use.
• The elements of these elliptic curves, on the other hand, must have a specific set of properties. In mathematical terms, they are members of a field, which is yet another kind of mathematical structure.

It is this complicated hierarchy that makes pairings (and therefore SNARKs) hard to understand. To summarize, building from the ground up:

• At the base, we have a field of elements.
• These elements are organized into a single elliptic curve, something like a line with a more complex shape.
• An operation (usually a kind of addition) is defined over this curve, so that its points will form a group.
• Two other curves and groups are derived from the first one
• A pairing is a particular bilinear function that takes an element from each of the first two groups and produces an element of the third.

The second and third groups are rather more complicated than the first, so I’ll start my explanation with the basic concepts, then increasing in complexity as I go (in later posts). This means that I can’t follow the hierarchy exactly, but I do it to try to go from the simpler to the more complex without introducing too much confusion too early.

Algebraic Structures: Groups

Let us start with groups then. A set is something people can easily understand: a collection of objects of the same kind without repetitions. For example,  take the set of all English words beginning with ‘A’, and call it A.

A group is a little more than that: it is a set on which we define an operation with some specific properties. Groups are one of the simpler examples of algebraic structures, which associate a set to one or more operations.

To take the previous example further, I can define the following operation, which I’ll call '+':

• +: take two words and join them together to form a third word. For example, ‘Aunt' + 'Annie' = 'AuntAnnie'.

The above set equipped with this operation can be written (A,+). Is that a group?

Let’s see. The first rule for a structure to be a group is that every pair of elements can be joined together with the operation to produce a third element in the group. (A,+) is not a group, then: ‘AuntAnnie’ is not a word. If we were to be a bit more lenient, and consider any word, English or not, to be in our set, then this property would be satisfied and we’d have to examine other properties. We’d find it to satisfy one of them (associativity), but not the others, and so would not be a group.

Group Axioms

I give you now an example of a group that is very familiar: the integer numbers, including 0 and the negatives, with normal addition. Call that (Z,+). I will list all the rules a group must comply with and how this structure matches them:

• Closure: any two elements joined by the operation must map to a third element in the group.
  • When you add two integers, you get another integer.
• Existence of Identity: there is a neutral element, known as identity: Adding the neutral to any element gives that element.
  • 0 is the neutral element. 0 + x = x + 0 = 0.
• Existence of inverse: every element has an inverse. When both are added, the result is the identity.
  • Think of any number, say 7. The inverse is the negative of that number, in this case, 7 + (-7) = 0.
• Associativity: the operation must be associative, that is, when you have a sequence of operations to execute you can do them in any order.
  • Example: 4 + 5 + 10 = (4 + 5) + 10 = 4 + (5 + 10).

Number of Elements in a Group

The last example I gave is an infinite group: there is never a “largest number” and so you can’t put a limit to how many elements exist in (Z,+). But a group can be finite, and have just a limited number of elements. Take the set of bits B = {0,1} and the operation ⊕ with the following rules:

• 0 ⊕ 0 = 0
• 0 ⊕ 1 = 1
• 1 ⊕ 0 = 1
• 1 ⊕ 1 = 0

You can check for yourself that all the properties above are satisfied. (B,+) must be a group, and because B only contains two elements, it is a finite group.

The number of elements in a group is called its ‘Order’. Infinite groups have infinite order.

Cyclic Group

A finite group can be cyclic. That means it has a generator element. If you start at any point and then apply the group operation with the generator as argument a certain number of times, you go around the whole group and end in the same place, like travelling around the world. An alternative definition that works better with infinite groups is that any element must be writable as a multiple of the generator, which corresponds to starting with the generator and then adding or subtracting itself a certain number of times.

Consider the familiar example of the hours in an analog clock, H = {1, ..., 12}, with the normal addition. If you add 12 hours to any time, you end in the same place. And from any time you can always choose a suitable number to add up to 12.

Because there are only 12 elements in this set, this is a finite group. Is it cyclic? You bet. If you start at any time, say 7, and add 1 each time, you will go through every hour in the clock. After 12 such steps, you are back at 7 again. The great thing about this is that even if you add 1 for a 1000 times, you will still be somewhere in your clock, between 1 and 12 hours. You can operate indefinitely. We say, in this case, that 1 is a generator of this group.

Is 2 a generator as well? No. If you start at any point on your group, and add 2 successively, after 6 steps you will be at the starting point again. You will have visited 6 of the hours in your clock, but the other 6 are unreachable. What about 3? You visit only 4 elements. And if you’re already thinking 1 is the only generator, I have news for you. 5 is a generator. 7 is too, and so is 11. For example, starting at 12 and adding 5 each time, we get: 12, 5, 10, 3, 8, 1, 6, 11, 4, 9, 2, 7, 12. In general, there can be several generators for a cyclic group, and they come in pairs: if x is a generator, -x is a generator too. Incidentally, 7 = -5 since 12 is the identity element.

Abelian Group

A group is called Abelian if its operation is commutative. That is, x operated on y is the same as y operated on x. All the examples I’ve shown here are Abelian, but that need not be the case. For a single example, the multiplication of matrices is not commutative so a group defined for these elements with this operation would not, in general, be Abelian.

On the other hand, every cyclic group is Abelian.

Fields

Now that you know about groups, let’s go to the next level: Fields.

Fields are an algebraic structure like groups, but with two operations instead of one, usually called addition and multiplication. For example (A, ⊕, ⊗). We can define a field in terms of groups. (A,⊕,⊗) is a field if:

• (A, ⊕) is an Abelian group, where the neutral element for the addition is called '0'.
• (A', ⊗) is an Abelian group, where the neutral element for the multiplication is called '1'.
• A* is the set A after having excluded '0'.
• multiplication is distributive over addition. That means: a ⊗ (b ⊕ c) = (a ⊗ b) ⊕ (a ⊗ c).

Naturally, fields can be finite or infinite depending on whether its set is finite or infinite.

So, what could be an example of a field? The most familiar and natural example is probably that of real numbers, with addition and multiplication as taught in high school. Another one is the field of rationals, that is, fractions of integer numbers. There are also finite fields, which are extremely important in cryptography, but I leave that for another post as this is enough maths for a single entry.

* * * * *

If this is the first time you hear about groups and fields, I hope the above will help you when you meet these terms in the wild. If you like what I write, please let me know. If you have any advice or corrections to make, don’t hesitate in contacting me. Send an email and I’ll reply. And if you like my content, you could always press ‘Like’ below and share my posts with your network.

I hope this helps you in your own journey, and that I’ll “see” you again around these parts again.