Quick access to articles on this page:
more on the next page...
By now there's already a number of great explanation for Plonk's permutation argument (e.g. my own here, zcash's). But if it still causes you trouble, maybe read this visual explanation first.
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.
I already wrote about the linearization technique of plonk here and here. But there's a more generalized and high-level view to understand it, as it's being used in many protocols (e.g. Shplonk) as well.
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!
As a security consultant you're most of the time forced to do something that no developers do: you're forced to become an expert in a codebase without writing a single line of code, and that in a short amount of time.
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!
Check out https://blog.zksecurity.xyz/posts/internship-2025/
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!
I tried to record a few short videos these last months (eventhough the last one is quite long). You might enjoy some of them:
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
If you have missed me, I was in different places on the Internet and in real life. Here are three whiteboard sessions on different aspects of zero-knowledge:
Years ago, naive me lost a lot of money because he was too stingy to hire a financial advisor, and too lazy to do some basic research. Hopefully you don't make the same mistakes. It took me a while to post this because, I didn't know if I should, I didn't understand the trouble I was in really, and I felt really dumb at the time.
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 guess I don't post that much about the startup I cofounded more than a year ago, so this is a good opportunity to release a short note for the curious people who read this blog!
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.
