On the left of this diagram you can see the table created by the three wires (or columns) of Plonk, with some added colors for cells that are wired to one another. As you can see, the values in the cells are valid: they respect the wiring (two cells that are wired must have the same values). Take a look at it and then read the next paragraph for an explanation of what's happening on the right:

On the right, you can see how we encode a permutation on the columns and rows to obtain a new table that, if the wiring was respected, should be the exact same table but with a different ordering.

The ordering will be eliminated in the permutation argument of Plonk, which will just check that both tables contain the same rows.

To encode the tables, we use two techniques illustrated in this diagram:

The first one is to use different cosets (i.e. completely distinct sets of points) to represent the different columns and rows. This is most likely the more confusing step of the permutation and so I've illustrated it with what it does in essence (assign a unique "index" that we can use to refer to each value).

The second one is simply to compress multiple columns with a challenge. (This technique is used in lookups as well when lookup tables have multiple columns.)

The following permutation circuit is then implemented:

def pos(col, row):
    return cosets[col] * row

def tuple(col, row, separator, value):
    return pos(col, row) * separator + value

# ((0, i), a[i]) * ((1, i), b[i]) * ((2, i), c[i]) 
def f(row, registers, challenges):
    return tuple(0, row, challenges[BETA], registers[0][row]) * tuple(1, row, challenges[BETA], registers[1][row]) * tuple(2, row, challenges[BETA], registers[2][row])

# (perm(0, i), a[i]) * (perm(1, i), b[i]) * (perm(2, i), c[i]) 
def g(row, registers, challenges):
    col0, row0 = circuit_permutation(0, row)
    col1, row1 = circuit_permutation(1, row)
    col2, row2 = circuit_permutation(2, row)
    return tuple(col0, row0, challenges[BETA], registers[0][row]) * tuple(col1, row1, challenges[BETA], registers[1][row]) * tuple(col2, row2, challenges[BETA], registers[2][row])

Z = 4

def compute_accumulator(row, registers, challenges):
    # z[-1] = 1
    if row == -1: 
        assert registers[Z][row] == 1
        return

    # z[0] = 1
    if row == 0: 
        assert registers[Z][row] == 1

    # z[i+1] = z[i] * f[i] / g[i]
    registers[Z][row+1] = registers[Z][row] * f(row, registers, challenges) / g(row, registers, challenges)

where the circuit is an AIR circuit built iteratively. That is, it was iteratively built on top of the first 3 registers. This means that the first 3 registers are now read-only (the left, right, and output registers of Plonk), whereas the fourth register (Z) can be written to. Since it's an AIR, things can be read at and written to at different adjacent rows, but as there is a cost to pay we only use that ability to write to the next adjacent row of the Z register.

To understand why the circuit looks like this, read the real explanation.

Imagine you have the following check that you want to do:

$$f(x) \cdot g(x) \cdot h(x) + 3 \cdot m(x) + 7 = 0$$

but some of these polynomials contain secret data, what you do is that you use commitments instead:

$$[f(x)] \cdot [g(x)] \cdot [h(x)] + 3 \cdot [m(x)] + 7 \cdot [1] = [0]$$

now it looks like we could do the check within the commitments and it could work.

The problem is that we can't multiply commitments, we can only do linear operations with commitments! That is, operations that preserves scaling and addition.

So we give up trying to do the check within the commitments, and we instead perform the check in the clear! That is, we try to perform the following check at a random point $z$ (this is secure thanks to Schwartz-Zippel):

$$f(z) \cdot g(z) \cdot h(z) + 3 \cdot m(z) + 7 = 0$$

To do that, we can simply ask a prover to produce evaluations at $z$ (accompanied with evaluation proofs) for each of the commitments.

Note that this leaks some information about each committed polynomials, so usually to preserve zero-knowledge you'd have to blind these polynomials

But Plonk optimizes this by saying: we don't need to evaluate everything, we can just evaluate some of the commitments to obtain a partial evaluation. For example, we can just evaluate $f$ and $g$ to obtain the following linear combination of commitments:

$$ f(z) \cdot g(z) \cdot [h] + 3 \cdot [m] + 7 \cdot [1] $$

This semantically represents a commitment to the partial evaluation of a polynomial at a point $z$. And at this point we can just produce an evaluation proof that this committed polynomial evaluates to 0 at the point $\textbf{z}$.

Since we are already verifying evaluation proofs (here of $f$ and $g$ at $z$), we can simply add another evaluation proof to check to that list (and benefit from some batching technique that makes it look like a single check).

That's it, when you're stuck trying to verify things using commitments, just evaluate things!

But let me say that it's of course not entirely true that you should not write code. I actually think part of understanding something deeply means playing with it. Researchers know that very well, as they spend a lot of their time implementing the papers they're trying to understand, asking themselves questions about the subject they're studying ("what would happen if I look in a mirror while traveling at the speed of light?"), doing written exercises like we used to do in Math classes. So as a consultant, you of course benefit from playing with the code you're looking at.

But that's not what I want to talk about today. What I want to talk about is how flawed the top-down approach is. I know it very well because this is how I audited code for way too long. And it's only when I realized, looking at the people that were inspiring me throughout my career, that the pros don't do that. The pros do bottom-up.

What's wrong with top-down though? I think the problem is that it's a trap and a time sink that brings very little benefit. The ROI is rapidly diminishing as you usually do very little deep work when surveying things from a high-level point of view, and can easily get the feeling of being busy when really what you're doing is spending time learning about things that won't matter eventually.

What matters is the core, the actual nitty gritty details, the algorithms implemented. What I've seen every talented engineer do when they want to dive into some code is to spend a lot of time in one place, focusing on understanding and mastering a self-contained part of the codebase.

Once they understand it, then they move to another part of the code, increasing their scope and their understanding of the project. By doing that several time, you quickly realize you know more than everybody, including some of the developers behind the code you're looking at. Not only that, it is only when you do that deep work in one place that you can accumulate real knowledge and that you end up finding good bugs.

Perhaps a last note on the top-down approach: it's a much more relaxed and rewarding process. You can really feel like you're never really learning important knowledge when you spent too much time at a high-level, and you can also easily feel overwhelmed that you'll never have the time to look at everything.

This is very human: if you could see any large project from a bird’s-eye view, you would quickly get discouraged and want to give up before even starting. Imagine a marathon runner visualizing the entirety of what they have to run while they're running their first 10 minutes. This is what they tell you not to do!

The bottom-up approach gives you the illusion that the scope you're looking at is not that big, and so as you focus on what's in front of you you can be more productive by not being distracted by the enormity of the project. And it's more fun as well!

This is somehow related but I've always thought that telling you all about the context of a story instead of showing it to you, in books or in movies, is lazy writing. I've always criticized the long textual intros of StarWars movies that take that idea to the extreme, and I've never understood why they kept that gimmick in all other StarWars movies in spite of being the IP's signature is also one of its worse features. That's an extreme top-down approach! Boring!

Looking for an internship in ZK, MPC, FHE, and post-quantum cryptography? Interested in working with AI, formal verification, and TEEs? We are always looking for talented peeps to join our team and do interesting research!

• 15 Tips And Tricks On Learning Really Hard Things
• Vlog #3 - How I ended up starting a startup
• Vlog #2 - Getting into a habit of working out
• Vlog #1 - Navigating the Ups and Downs of Startup Life

I dropped the "vlog" on the last one (that's 45min long!) so you don't feel like you're wasting your time listening to me. The second one is a bit shameful to me because my habit of working out has dwindled down dramatically and I'm now fighting to preserve it while enduring the long winter of New York :D

• Proof is in the Pudding 02: zkTLS
• Proof is in the Pudding 01: Arithmetization
• ZK Whiteboard Sessions - S2M1: What is Zero-Knowledge (like, actually)?

Disclaimer: if you are in this situation don't just trust me, do your own research and hire your own financial advisor.

It all started when some of my coworkers at Facebook warned me that when the financial year came to an end, they realized that they still owed dozens of thousands of dollars in taxes. This might sound like an outrageous number, but one might think that it's also OK as "if you earn more it's normal to pay more taxes". Years later, when this happened to me, I realized that I could almost have ended up in debt.

Let me explain: stocks or tokens that you receive as payment is paper money, but not for the IRS. For the government it's worth as much as the "fair market value" of that stock or token at the moment your employer sends it to you. For the government, it's like income in USD, so they'll still tax you on that even if you haven't converted these in USD yourself.

Let me give you an example: your company has a token that's worth 1,000,000 USD. They send you 1 token, which the IRS will see as an event of you receiving one million dollars of income. In that moment, if you don't sell, or if you're too slow to sell, and the price drops to 1 USD, you're still going to owe the IRS one million dollars.

What's tricky is that even if you decide to sell the stock/token directly, its fair market value (however you decide to calculate it) can be highly uncorrelated to the price you sell it at. That's because tokens are known to be fairly volatile, and (if you're lucky) especially during the time it takes to receive and then sell it.

If that's not enough, you also pay taxes (called capital gain taxes) when you sell and convert to USD, and these are going to be high if you do it within a year (they'll be taxed like income).

OK but usually, you don't have to care too much about that, because your company will withhold for you, meaning that they will sell some stock/token to cover for your taxes before sending you the rest. But it is sometimes not enough! Especially if they think you're in some specific tax bracket. It seems like if you're making too little, you'll be fine, and if you're making too much, you'll be fine too. But if you're in the middle, chances are that your company won't withhold enough for you, and you'll be responsible to sell some on reception of the stock/token to cover for taxes later (if you're a responsible human being).

By the time I realized that, my accountant on the phone was telling me that I had to sell all the tokens I had left to cover for taxes. The price had crashed since I had received them.

That year was not a great year. At the same time I was happy that while I did not make any money, I also had not lost any. Can you imagine if I had to take loans to cover for my taxes?

The second lesson is that when you sign a grant which dictates how you'll "vest" some stock/token over time, you can decide to pay taxes at that point in time on the value the stock/token already has. This is called an 83b form and it only makes sense if you're vesting, and if you're still within the month after you signed the grant. If the stock/token hasn't launched, this most likely means that you can pay a very small amount of taxes up front. Although I should really disclaim that I'm not financially literate (as you can see) and so you shouldn't just trust me on that.

I posted a retrospect on the main blog of zkSecurity: A Year of ZK Security, but more time has passed since and here's how things are looking like.

We've had a good stream of clients, and we are now much more financially stable. We've managed to ramp up the team so that we stop losing work opportunities due to lack of availability on our side (we're now 15 engineers, interns included). Not only is the founding team quite the dream team, but the team we created are made of people more qualified than me, so we have a good thing going on.

Everybody seems to have quite a different background, some people are more focused on research, others are stronger devs, and others are CTFs people wearing the security hat. So much so that our differing interests have led us to expand to more than just auditing ZK. We now do development, formal verification work, and design/research work as well. We also are not solely looking at ZK anymore, but at advanced cryptography in general. Think consensus protocols, threshold cryptography, MPC, FHE, etc.

Perhaps naming the company "zk"security was a mistake :) but at least we made a name for ourselves in a smaller market, and are now expanding to more markets!

That's it.

It all started from a clever pun "succinct non-interactive argument of knowledge" and ended up with weird consequences as not every new scheme was deemed "succinct". So much so that naming branched (STARKs are "scalable" and not "succinct") or some schemes can't even be called anything. This is mostly because succinct not only means really small proofs, but also really small verifier running time.

If we were to classify verifier running time between the different schemes it usually goes like this:

• KZG (used in Groth16 and Plonk): super fast
• FRI (used in STARKs): fast
• Bulletproof (used in kimchi): somewhat fast

Using the almost-standardized categorization, only the first one can be called a SNARK, the second one is usually called a STARK, and I'm not even sure how we call the third one, a NARK?

But does it really make sense to reserve SNARK to the first scheme? It turns out people are using all three schemes because they are all dope and fast(er) than running the program by yourself. Since SNARK has become the main term for general-purpose zero-knowledge proofs, then let's just use that!

I'm not the only one that wants to call STARKs and bulletproofs SNARKs, Justin Thaler also makes that point here:

the “right” definition of succinct should capture any protocol with qualitatively interesting verification costs – and by “interesting,” I mean anything with proof size and verifier time that is smaller than the associated costs of the trivial proof system. By “trivial proof system,” I mean the one in which the prover sends the whole witness to the verifier, who checks it directly for correctness

If you didn't know, slashing is the act of punishing malicious validators in BFT consensus protocols by taking away tokens. Often tokens that were deposited and locked by the validators themselves in order to participate in the consensus protocol. Perhaps the first time that this concept of slashing appeared was in Tendermint? But I'm not sure.

In the article they make the point that BFT consensus protocols need slashing, and are less secure without it. This is an interesting claim as there's a number of BFT consensus protocols that are running without slashing (perhaps a majority of them?)

Slashing is mostly applied to safety violations (a fork of the state of the network) that can be proved. This is often done by witnessing two conflicting messages being signed by the same node in the protocol (often called equivocation). Any "forking attack" that want to be successful will require a threshold (usually a third) of the nodes signing conflicting messages.

Slashing only affects nodes that still have stake in the system, meaning that forking old history to target a node that’s catching up (without a checkpoint) doesn’t get affected by slashing (what we call long-range attacks). The post argues that we need to separate the cost-of-corruption from the profit-from-corruption and seem to only assume that the cost-of-corruption is always the full stake of all attackers, in which case this analysis only makes sense in attacks aiming at forking the tip/head of the blockchain.

The post present a new model, the Corruption-Analysis model, in order to analyze slashing. They accompany the model with the following table that showcases the different outcomes of an attack in a protocol that does not have slashing:

Briefly, it shows that (in the bottom-left corner) failed attacks don't really have a cost as attackers keep their stake (S) and potentially get paid (B1) to do the attack. On the other hand it shows that (in the top-right corner) people will likely punish everyone in case of an attack by mass selling and taking the token price down to $0$ (an implied feature they call token toxicity).

On the other hand, this is the table they show once slashing is integrated:

As one can see, the bottom-left corner and the top-right corner have changed: a failed attack now has a cost, and a successful attack almost doesn't have one anymore. Showing that slashing is strictly better than not slashing.

While this analysis is great to read, I'm not sure I fully agree with it. First, where did the "token toxicity" go in the case of a successful attack? I would argue that a successful attack would impact the protocol in similar ways. Perhaps not as intensely, as as soon as the attack is detected the attackers would lose their stake and not be able to perform another attack, but still this would show that the economic security of the network is not good enough and people would most likely lose their trust in the token.

Second, is the case where the attack was not successful really a net improvement? My view is that failed attacks generally happen due to accidents rather than legitimate attempts, as an attacker would most likely succeed if they had enough to perform an attack. And indeed, I believe all of the slashing events we've seen were all accidents, and no successful BFT attacks was ever witnessed (slashing or no slashing). (That being said, there are cases where an attacker might have difficulties properly isolating a victim's node, in which case it might be harder to always be successful at performing the attack. This really depends on the protocol and on the power of the adversary.)

In addition, attacks are all different. The question of who is targeted matters: if the victim reacts, how long does it take them to punish the attackers and publish the equivocation proofs? Does the protocol has a long-enough unstaking period to give the victim time to punish them? And if a third of the network is Byzantine, can they prevent the slashing from happening anyway by censoring transactions or something? Or worst case, can they kill the liveness of the network instead of getting slashed, punishing everyone and not just them (up until a hard fork occurs)?

Food for thought, but this shows that slashing is still quite hard to model. After all, it's a heuristic, and not a mechanism that you will find in any BFT protocol whitepaper. As such, it is part of the overall economic security of the deployed protocol and has to be measured via both its upsides and downsides.

For example, you can sort of make these generalization and explain most modern general-purpose ZKP systems with them:

• They all use a polynomial commitment scheme (PCS). Thank humanity for that abstraction. The PCS is the core engine of any proof system as it dictates how to commit to vectors of values, how large the proofs will be, how heavy the work of the verifier will be, etc.
• Their constraint systems are basically all acting on execution trace tables, where columns can be seen as registers in a CPU and the rows are the values in these registers at different moments in time. R1CS has a single column, both AIR and plonkish have as many columns as you want.
• They all reduce these columns to polynomials, and then use the fact that for some polynomial $f$ that should vanish on some points ${w_0, w_1, \cdots}$ then we have that $f(x) = [(x - w_0)(x-w_1)\cdots] \cdot q(x)$ for some $q(x)$
• And we can easily check the previous identity by checking it at a single random point (which is highly secure thanks to what Schartz and Zippel said a long time ago)
• They also all use the fact that proving that several identities are correct (e.g. $a_i = b_i$ for all $i$) is basically the same as proving that their random linear combination is the same (i.e. $\sum_i r_i (a_i - b_i) = 0$), which allows us to "compress" checks all over the place in these systems.

Knowing these 4-5 points will get you a very long way. For example, you should be able to quickly understand how STARKs work.

Having said that, I more recently noticed another pattern that is used all over the place by all these proof systems, yet is never really abstracted away, the interactive arithmetization pattern (for lack of a better name). Using this concept, you can pretty much see AIR, Plonkish, and a number of protocols in the same way: they're basically constraint systems that are iteratively built using challenges from a verifier.

Thinking about it this way, the difference between STARK's AIR and Plonks' plonkish arithmetization is now that one (Plonk) has fixed columns that can be preprocessed and the other doesn't. The permutation of Plonk is now nothing special, the write-once memory of Cairo is nothing special as well, they're both interactive arithmetizations.

Let's look at plonk as a table, where the left table is the one that is fixed at compilation time, and the right one is the execution trace that is computed at runtime when a prover runs the program it wants to prove:

One can see the permutation argument of plonk as an extra circuit, that requires 1) the first circuit to be ran and 2) a challenge from the verifier, in order to be secure.

As a diagram, it would look like this:

Now, one could see the write-once memory primitive of Cairo in the same way (which I explained here), or the lookup arguments of a number of proof systems in the same way.

For example, the log-derivative lookup argument used in protostar (and in most protocols nowadays) looks like this. Notice that:

• in step 4 the execution trace of the main circuit is sent
• in step 6 the verifier sends a challenge back
• and in step 7 the prover sends the execution trace of the second circuit (that implements a lookup circuit) using the challenge

As such, the point I really want to make is that a number of ZKP primitives and interaction steps can be seen as an interactive process to construct a super constraint system from a number of successive constraint system iterated on top of each other. Where constraint system means "optionally some new fixed columns, some new runtime columns, and some constraints on all the tables including previous tables". That's it.

Perhaps we should call these iterative constraint systems.

Using Schwartz-Zippel with no multiplication

First, let me say that there's typically two types of "nice" polynomial commitment schemes that people use with elliptic curves: Pedersen commitments and KZG commitments.

Pedersen commitments are basically hidden random linear combinations of the coefficients of a polynomial. That is, if your polynomial is $f(x) = \sum c_i \cdot x^i$ your commitment will look like $[\sum r_i \cdot c_i] G$ for some base point $G$ and unknown random values $r_i$. This is both good and bad: since we have access to the coefficients we can try to use them to evaluate a polynomial from its commitment, but since it's a random linear combination of them things can get ugly.

On the other hand, KZG commitments can be seen as hidden evaluations of your polynomials. For the same polynomial $f$ as above, a KZG commitment of $f$ would look like $[f(s)]G$ for some unknown random point $s$. Not knowing $s$ here is much harder than not knowing the values $r_i$ in Pedersen commitments, and this is why KZG usually requires a trusted setup whereas Pedersen doesn't.

In the rest of this post we'll use KZG commitments to prove identities.

Let's use $[a]$ to mean "commitment of the polynomial $a(x)$", then you can easily check that $a(x) = b(x)$ knowing only the commitments to $a(x)$ and $b(x)$ by checking that $[a] = [b]$ or $[a] - [b] = [0]$. This is because of the Schwartz-Zippel (S-Z) lemma which tells us that checking this identity at a random point is convincing with high-enough probability.

When multiplication with scalars is required, then things are fine. As you can do $i \cdot [a]$ to obtain $[i \cdot a]$, checking that $i \cdot a = j \cdot b$ is as simple as checking that $i \cdot [a] - j \cdot [b] = [0]$.

This post is about explaining how pairing helps us when we want to check an identity that involves multiplying $a$ and $b$ together.

Using elliptic curve pairings for a single multiplication

It turns out that elliptic curve pairings allow us to perform a single multiplication. Meaning that once things get multiplied, they move to a different planet where things can only get added together and compared. No more multiplications.

Pairings give you this function $e$ which allows you to move things in the exponent like this: $e([a], [b]) = e([1], [1])^{ab}$. Where, remember, $ab$ is the multiplication of the two polynomials evaluated at a random point: $a(s) \cdot b(s)$.

As such, if you wanted to check something like this for example: $a \cdot b = c + 3$ with commitments only, you could check the following pairings:

$$ e([a], [b]) = e([c] + 3 [1], [1]) $$ By the way, the left argument and the right argument of a pairing are often in different groups for "reasons". So we usually write things like this:

$$ e([a]_1, [b]_2) = e([c]_1 + 3 [1]_1, [1]_2) $$ And so it is important to have commitments in the right groups if you want to be able to construct your polynomial identity check.

Evaluations can help with more than one multiplication

But what if you want to check something like $a \cdot b \cdot c = d + 4$? Are we doomed?

We're not! One insight that plonk brought to me (which potentially came from older papers, I don't know, I'm not an academic, leave me alone), is that you can reduce the number of multiplication with "this one simple trick". Let me explain...

A typical scenario includes you wanting to check an identity like this one:

$$a(x) \cdot b(x) \cdot c(x) = d(x)$$

and you have KZG commitments to all three polynomials $[a], [b], [c]$. (So in other words, hidden evaluations of these polynomials at the same unknown random point $s$)

You can't compute the commitment of the left-hand side because you can't perform the multiplication of the three commitments.

The trick is to evaluate (using KZG) the previous identity at a different point, let's say $\zeta$, and pre-evaluate (using KZG as well) as many polynomials as you can to $\zeta$ to reduce the number of multiplications down to 0.

Note: that is, if we want to check that $a(x) - b(x) = 0$ is true, and we want to use S-Z to do that at some point $\zeta$, then we can pre-evaluate $a$ (or $b$) and check the following identity $a(\zeta) - b(x) = 0$ at some point $\zeta$ instead.

More precisely, we'll choose to pre-evaluate $b(\zeta) = \bar{b}$ and $c(\zeta) = \bar{c}$, for example. This means that we'll have to produce a quotient polynomial $q_b$ and $q_c$ such that:

1. $b(s) - \bar{b} = (s - \zeta) \cdot q_b(s)$
2. $c(s) - \bar{c} = (s - \zeta) \cdot q_c(s)$

which means that the verifier will have to perform the following two pairings (after having been sent the evaluation $\bar{b}$ and $\bar{c}$ in the clear):

1. $e([b]_1 - \bar{b} \cdot [1]_1, [1]_2) = e([x]_1 - \zeta \cdot [1]_1, [q_b]_2)$
2. $e([c]_1 - \bar{c} \cdot [1]_1, [1]_2) = e([x]_1 - \zeta \cdot [1]_1, [q_c]_2)$

Then, they'll be able to check the first identity at $\zeta$ and use $\bar{b}$ and $\bar{c}$ in place of the commitments $[b]$ and $[c]$. The verifier check will look like the following pairing (after receiving a commitment $[q]$ from the prover): $$e( \bar{b} \cdot \bar{c} \cdot [a]_1 - [d] - 0, [1]_2) = e([x]_1 - \zeta \cdot [1]_1, [q]_2)$$ which proves using KZG that $a(\zeta)b(\zeta)c(\zeta) - d(\zeta) = 0$ (which proves that the identity checks out with high probability thanks to S-Z).

Aggregating all the KZG evaluation proofs

In the previous explanation, we actually perform 3 KZG evaluation proofs instead of one:

• $2$ pairings that are KZG evaluation proofs that pre-evaluate different polynomials from the main check at some random point $\zeta$.
• $1$ pairing that evaluates the main identity at $\zeta$, after it was linearized to get rid of any multiplication of commitments.

Pairings can be aggregated by simply creating a random linear combinations of the pairings. That is, with some random values $r_i$ we can aggregate the checks where the left-hand side is: $$ b(s) - \bar{b} + r_1 (c(s) - \bar{c}) + r_2 (\bar{b} \cdot \bar{c} \cdot a(s) - d(s) - 0]) $$ and the right-hand side is: $$ = (s - \zeta) \cdot q_b(s) + r_1 ((s - \zeta) \cdot q_c(s)) + r_2 ((s - \zeta) \cdot q(s))$$

Multiset equality check

Suppose that you have two ordered sets) of values $D = {d_1, d_2, d_3, d_4}$ and $E = {e_1, e_2, e_3, e_4}$, and that you want to check that they contain the same values. That is, you want to check that there exists a permutation of the elements of $D$ (or $E$) such that the multisets (sets where some values can repeat) are the same, but you don't care about which permutation exactly gets you there. You're willing to accept ANY permutation.

$${d_1, d_2, d_3, d_4} = \text{some_permutation}({e_1, e_2, e_3, e_4})$$ For example, it could be that re-ordering $E$ as ${e_2, e_3, e_1, e_4}$ gives us exactly $D$.

Trick 1: multiply things to reduce to a single value

One way to do perform our multiset equality check is to compare the product of elements on both sides:

$$d_1 \cdot d_2 \cdot d_3 \cdot d_4 = e_1 \cdot e_2 \cdot e_3 \cdot e_4$$

If the two sets contain the same values then our identity checks out. But the reverse is not true, and thus this scheme is not secure.

Can you see why?

For example, $D = (1, 1, 1, 15)$ and $E = (3, 5, 1, 1)$ are obviously different multisets, yet the product of their elements will match!

Trick 2: use polynomials, because maybe it will help...

What we can do to fix this issue is to encode the values of each lists as roots of two polynomials:

• $d(x) = (x - d_1)(x - d_2)(x - d_3)(x - d_4)$
• $e(x) = (x - e_1)(x - e_2)(x - e_3)(x - e_4)$

These two polynomials are equal if they have the same roots with the same multiplicities (meaning that if a root repeats, it must repeat the same number of times).

Trick 3: optimize polynomial identities with Schwartz-Zippel

Now is time to use the Schwartz-Zippel lemma to optimize the comparison of polynomials! Our lemma tells us that if two polynomials are equal, then they are equal on all points, but if two polynomials are not equal, then they differ on MOST points.

So one easy way to check that they match with high probability is to sample a random evaluation point, let's say some random $\gamma$. Then evaluate both polynomials at that random point $\gamma$ to see if their evaluations match: $$(\gamma - d_1)(\gamma - d_2)(\gamma - d_3)(\gamma - d_4) = (\gamma - e_1)(\gamma - e_2)(\gamma - e_3)(\gamma - e_4)$$

Permutation check

The previous check is not useful for wiring different cells within some execution trace. There is no specific "permutation" being enforced. So we can't use it as in in plonk to implement our copy constraints.

Trick 4: random linear combinations to encode tuples

To enforce a permutation, we can compare tuples of elements instead! For example, let's say we want to enforce that $E$ must be re-ordered using the permutation $(1 3 2) (4)$ in cycle notation. Then we would try to do the following identity check: $$ ((1, d_1), (2, d_2), (3, d_3), (4, d_4)) = ((2, e_1), (3, e_2), (1, e_3), (4, e_4)) $$ Here, we are enforcing that $d_1$ is equal to $e_3$, and that $d_2$ is equal to $e_1$, etc. This allows us to re-order the elements of $E$: $$ ((1, d_1), (2, d_2), (3, d_3), (4, d_4)) = ((1, e_3), (2, e_1), (3, e_2), (4, e_4)) $$ But how can we encode our tuples into the polynomials we've seen previously? The trick is to use a random linear combination! (And that is often the answer in a bunch of ZK protocol.)

So if we want to encode $(2, d_2)$ in an equation, for example, we write $2 + \beta \cdot d_2$ for some random value $\beta$.

Note: The rationale behind this idea is still due to Schwartz-Zippel: if you have two tuples $(a,b)$ and $(a', b')$ you know that the polynomials $a + x \cdot b$ is the same as the polynomial $a' + x \cdot b'$ if $a = a'$ and $b = b'$, or if you have $x = \frac{a' - a}{b - b'}$ . If $x$ is chosen at random, the probability that it is exactly that value is $\frac{1}{N}$ with $N$ the size of your sampling domain (i.e. the size of your field) which is highly unlikely.

So now we can encode the previous lists of tuples as these polynomials:

• $d(x, y) = (1 + y \cdot d_1 - x)(2 + y \cdot d_2 - x)(3 + y \cdot d_3 - x)(4 + y \cdot d_4 - x)$
• $e(x, y) = (2 + y \cdot e_1 - x)(3 + y \cdot e_2 - x)(1 + y \cdot e_3 - x)(4 + y \cdot e_4 - x)$

And then reduce both polynomials to a single value by sampling random values for $x$ and $y$. Which gives us:

• $(1 + \beta \cdot d_1 - \gamma)(2 + \beta \cdot d_2 - \gamma)(3 + \beta \cdot d_3 - \gamma)(4 + \beta \cdot d_4 - \gamma)$
• $(2 + \beta \cdot e_1 - \gamma)(3 + \beta \cdot e_2 - \gamma)(1 + \beta \cdot e_3 - \gamma)(4 + \beta \cdot e_4 - \gamma)$

If these two values match, with overwhelming probability we have that the two polynomials match and thus our permutation of $E$ matches $D$.

Wiring within a single execution trace column

Let's now see how we can use the (optimized) checks we've learn previously in plonk. We will first learn how to wire cells of a single execution trace column, and in the next section we will expand this to three columns (as vanilla Plonk uses three columns).

Take some moment to think about how can we use the previous stuff.

The answer is to see the execution trace as your list $E$, and then see if it is equal to a fixed permutation of it ($D$). Note that this permutation is decided when you write your circuit, and precomputed into the verifier key in Plonk.

Remember that the formula we're trying to check is the following for some random $\beta$ and $\gamma$, and for some permutation function $\sigma$ that we defined:

$$ \prod_{i=1} (i + \beta \cdot d[i] - \gamma) = \prod_{i=1} (\sigma(i) + \beta \cdot e[i] - \gamma) $$

Trick 5: write a circuit for the permutation check

To enforce the previous check, we will write a mini-circuit (yes an actual circuit!) which will progressively accumulate the result of dividing the left-hand side with the right-hand side. This circuit only requires one variable/register we'll call $z$ (and so it will add a new column $z$ in our execution trace) which will start with the initial value 1 and will end with the following value:

$$ \prod_{i=1} \frac{i+\beta \cdot d[i] - \gamma}{\sigma(i) + \beta \cdot e[i] - \gamma} = 1 $$

Let's rewrite it using only the first wire/column $a$ of Plonk, and using our generator $\omega$ as index in our tuples (because this is how we handily index things in Plonk):

$$ \prod_{i=1} \frac{\omega^i+\beta \cdot a[i] - \gamma}{\sigma(\omega^i) + \beta \cdot a[i] - \gamma} = 1 $$

We can then constrain the last value to be equal to 1, which will enforce that the two polynomials encoding our list of value and its permutation are equal (with overwhelming probability).

In plonk, a gate can only access variables/registers from the same row. So we will use the following extra gate (reordering the previous equation, as we can't divide in a circuit) throughout the circuit:

$$ z[i+1] \cdot (\sigma(i) + \beta \cdot a[i] - \gamma) = z[i] \cdot (i + \beta \cdot a[i] - \gamma) $$ Now, how do we encode this gate in the circuit? The astute eye will have noticed that we are using a cell of the next row ($z[i+1]$) which we haven't done in Plonk so far.

Trick 6: you're in a multiplicative subgroup, remember?

Enforcing things across rows is actually possible in plonk because we encode our polynomials in a multiplicative subgroup of our field! Due to this, we can reach for the next value(s) by multiplying an evaluation point with the subgroup's generator.

That is, values are encoded in our polynomials at evaluation points $\omega, \omega^2, \omega^3, \cdots$, and so multiplying an evaluation point by $\omega$ (the generator) brings you to the next cell in an execution trace.

As such, the verifier will later try to enforce that the following identity checks out in the multiplicative subgroup:

$$ z(x \cdot \omega) \cdot (\sigma(x) + \beta \cdot a(x) - \gamma) = z(x) \cdot (x + \beta \cdot a(x) - \gamma) $$

Note: This concept was generalized in turboplonk, and is used extensively in the AIR arithmetization (used by STARKs). This is also the reason why in Plonk we have to evaluate the $z$ polynomial at $\zeta \omega$.

There will also be two additional gates: one that checks that the initial value is 1, and one that check that the last value is 1, both applied only to their respective rows. One trick that Plonk uses is that the last value is actually obtained in the last row. As last_value + 1 = 0 in our multiplicative subgroup, we have that $z[\text{last_value} + 1] = z[0]$ is constrained automatically. As such, checking that $z[0] = 1$ is enough.

You can see these two gates added to the vanilla plonk gate in the computation of the quotient polynomial $t$ in plonk. Take a look at this screenshot of the round 3 of the protocol, and squint really hard to ignore the division by $Z_H(X)$, the powers of $\alpha$ being used to aggregate the different gate checks, and the fact that $b$ and $c$ (the other wires/columns) are used:

The first line in the computation of $t$ is the vanilla plonk gate (that allows you to do multiplication and addition); the last line constrains that the first value of $z$ is $1$; and the other lines encode the permutation gate as I described (again, if you ignore the terms involving $b$ and $c$).

Trick 7: create your execution trace in steps

There's something worthy of note: the extra execution trace column $z$ contains values that use other execution trace columns. For this reason, the other execution trace columns must be fixed BEFORE anything is done with the permutation column $z$.

In Plonk, this is done by waiting for the prover to send commitments of $a$, $b$, and $c$ to the verifier, before producing the random challenges $\beta$ and $\gamma$ that will be used by the prover to produce the values of $z$.

Wiring multiple execution trace columns

The previous check only works within the cells of a single execution trace, how does Plonk generalizes this to several execution trace columns?

Remember: we indexed our first execution trace column with the values of our circuit domain (that multiplicative subgroup), we simply have to find a way to index the other columns with distinct values.

Trick 8: use cosets

A coset is simply a set that is the same size as another set, but that is completely disjoint from that set. Handily, a coset is also defined as something that's very easy to compute if you know a subgroup: just multiply it with some element $k$.

Since we want a similar-but-different set from the elements of our multiplicative subgroup, we can use cosets!

Plonk produces the values $k_1$ and $k_2$ (which can be the values $2$ and $3$, for example), which when multiplied with the values of our multiplicative subgroup (${\omega, \omega^2, \omega^3, \cdots}$) produces a different set of the same size. It's not a subgroup anymore, but who cares!

We now have to create three different permutations, one for each set, and each permutation can point to the index of any of the sets.

It was a lot of fun and I hope that some people are inspired to try to break it :)

We're using the challenge to hire people who are interested in doing security work in the ZK space, so if that interests you, or if you purely want a new challenge, try it out here: https://github.com/zksecurity/zkBank

And of course, since this is an active wargame) please do not release your own solution or write up!

So as requested, I made a number of videos to explain what zkBitcoin is.