🍟Chips! Fish sold separately

In this section, we need to go over the idea of a chip; its name should allow you to infer some things, such as that this item is a component that will allow certain operations.

Embedding gates in equations

Let's quickly recap some elements of the original plonk proof system.

Plonk manages to represent both addition gates and multiplication gates within the same equation (using $s$ to represent the selectors)

$$l\cdot s_l + r\cdot s_r + (l\cdot r)\cdot s_m - o\cdot s_o + s_c + PI = 0.$$

This single equation allows us to selectively do addition or multiplication in particular rows by setting the selector values appropriately (it also allows other things like public inputs as well). We have in effect embedded two different gates into this single equation. For example by setting $(s_m,s_o)=(1,1)$ and all other selectors (things of the form $s_i$) to 0, we turn this into a multiplication gate because it reduces to

$$(l\cdot r)-o=0,$$

so the output $o$ must equal the product.

Halo2 allows us to decide what equation we want to use for ourselves, and this gives us a lot of wiggle room to make a system more specific to what we want to achieve. For example maybe we only want multiplication gates, or maybe we want to include other types of gates such as a lookup gate.

Chips are going to be components where we choose an equation like the above and create relevant structs - it will be the code representation of the idea.

Chips

Okay, so the last sentence about chips was true but slightly misleading. We are going to choose the equation we want, but we don't directly include it in the code for some time. In the meantime, we need to create some columns, and the equation we chose determines how many columns we need and what type they should be.

So in the above equation $r$ would need its own column and its type would be advice because we have a value that depends on the circuit's inputs. The column of $s_r$ would be of type fixed because it never changes, it helps represent the structure of the circuit in that it is on when we do addition - and in a specific zk circuit the gate arrangement is always the same.

And finally public inputs in $PI$ would want a column of type instance.

Column type	Purpose
Advice	Witness values, i.e. wire values that are dependent on the circuit's input
Instance	Public input values
Fixed	Circuit hardcoded constants, such as selector values or constants
Selector	Okay this isn't actually a column type. This is essentially a 'spiced up' fixed column

Now that we have all the columns and their types prepared for each item we want to go into the equation we selected, we first have to write them in code and wrap them in a struct that can generically be called _Config, for example ArithmeticConfig.

Note: it would be good to point out here that these columns will all be the same length, and since we can put them side by side we can think of them as columns of some table. The reason for mentioning this is we often use the nomenclature of table, and you will see others talk about this system from that perspective.

Next we want to wrap this struct in another struct with marker: PhantomData for reasons we shouldn't worry about now because there are more valuable aspects to focus on first. We can generically call this new struct _Chip, for example ArithmeticChip. Yes, we do indeed have a chip now!

Time to give the chip some functionality. We have to tell the code how to combine the columns in the right way to create the gates we want; in effect we are telling the code how to combine the columns so as to emulate the equation we chose. We will do this via a trait we will implement on our chip.

Gates from traits

We will need to define a trait (let's refer to it as the composer trait), within which we will have the functions for the types of gates we want (and perhaps some other functionality like expose_public or copy depending on how we design things). When creating this trait we should be doing so with the knowledge of the config and the equation we are trying to emulate.

We are going to have to dig into how to actually implement these trait functions, but that will require us to cover a lot more ground. For now, let's wrap up our new knowledge with a straightforward code lab.