That's it, I made it, I can finally retire now.
https://zeroknowledge.fm/290-2/
This week, Anna and Guillermo chat with David Wong, author of the Real-World Cryptography book, and a cofounder zksecurity.xyz – an auditing firm focused on Zero Knowledge technology.
They chat about what first got him interested in cryptography, his early work as a security consultant, his work on the Facebook crypto project and the Mina project, zksecurity.xyz, auditing techniques and their efficacy in a ZK context, what common bugs are found in ZK code, and much more.
My first public report (since I left NCC Group) is out. It was work I did for zksecurity, auditing the Penumbra circuits. You can read it here: https://penumbra.zone/blog/2023-audits
It should be quite interesting to read as we found double spending and double voting issues. It's also nice because there are two reports in the post, one from us (zksecurity) and one from my previous team over at NCC Group =)
I wrote a thing that got quite the traction on the internet, which is merely a summary of something awesome that someone else found.
You can read it here: https://www.zksecurity.xyz/blog/posts/nova-attack/
the first paragraph to give you an idea:
Last week, a strange paper (by Wilson Nguyen et al.) came out: Revisiting the Nova Proof System on a Cycle of Curves. Its benign title might have escaped the attention of many, but within its pages lied one of the most impressive and devastating attack on a zero-knowledge proof (ZKP) system that we’ve ever seen. As the purpose of a ZKP system is to create a cryptographic proof certifying the result of a computation, the paper demonstrated a false computation result accompanied with a valid proof.
Someone was asking the following question on [Plonk}():
If you also looked at Plonk and wanted and were wondering the same, here's a short answer. If you do not care about PlonK, feel free to ignore this post. If you care about PlonK, but are starting from the very beginning, then just check my series of videos on PlonK.
First, there's different things going on in this picture. The best way to understand what's going on is to understand them individually.
The first step is a random challenge from the verifier in the interactive version of the protocol. Since we're in the non-interactive version, we've replaced the messages of the verifier by calls to a random oracle. This technique to convert an interactive protocol into a non-interactive one is very famous and used all over the place, it's called Fiat-Shamir.
Because we rely on a random oracle, proofs have to state that they are in the random oracle model, and some people don't like that too much because in the real world you end up instantiating these random oracles with hash functions (which are non-ideal constructions). So some people like protocols better when they don't rely on random oracles. In practice, if your hash function is thought to behave like a random oracle (e.g. SHA-3), then you're all good.
Fiat-Shamir'ing an interactive protocol only works if the protocol is a public-coin protocol, which PlonK is. Public-coin here means that the messages of the verifier are random values (coin tosses) that are public (outsiders can look at them and this won't affect the security of the protocol).
Another interesting point in that picture is that we're hashing the whole transcript, which is something you need to do in order to avoid a large class of ambiguity attacks. Protocols often forget to specify this correctly and a number of attacks have been found on PlonKish protocols due to that. See Weak Fiat-Shamir Attacks on Modern Proof Systems for more detail.
The second step is to compute the linearization of the composition polynomial. The composition polynomial is a term I stole from STARKs but I like it. It's THE polynomial, the one that combines all the checks. In PlonK this means the polynomial that combines checks for all the gates of the circuits and the wiring (permutation).
I'm not going to explain too much about the linearization because I already have a post on it here. But to recap, linearizing is when you evaluate parts of your polynomial. So anything that's evaluated at $z$ is linearized. And anything that has a bar above it (e.g. $\bar{a}$) is linearized as well. Note that the prover could evaluate everything if they wanted to, which would let the verifier compute the entire check "in the clear". But doing that means that the proof is larger, and there are more evaluation proofs to aggregate. It's a tradeoff, that might pay off if you also want to implement recursive zero-knowledge proofs (which require a verifier implemented in a circuit).
We're looking at the prover side in this picture. While the verifier does symmetrical things to the prover, the prover's job here is to form the composition polynomial and to prove that it evaluates to 0 on a number of points (or that it "vanishes on some domain"). So to do that, it has to prove that it is equal to the vanishing polynomial $Z_H$ times some quotient $t(X)$. If you don't understand that, you can read this other post I have on the subject.
The final piece of the puzzle to understand that equation is that we can simplify the $f(X) = Z_H(x) t(x)$ check using Maller's optimization which I talk about here. This is why we subtract our composition polynomial with $Z_H(X) \cdot t(X)$ and this is also why we linearize the vanishing polynomial by evaluating it at $Z_H(z)$.
Once we have formed the polynomial which checks that the composition polynomial is equal to the vanishing polynomial times some quotient ($f = Z_H \cdot t$) then we have to evaluate this at a random point. We already know the random point $z$, which we've already used to evaluate some parts of the polynomial (during the linearization). The equation you see in the picture is how you compute a KZG evaluation proof. If you don't know that you can check my article on KZG.
Note also that there are many evaluation proofs that are aggregated together using a random linear combination. This is a common technique to aggregate multiple KZG evaluation proofs (and the verifier will have to compute the same random linear combination on the other side to verify the aggregation). In order to be more efficient (at the cost of tiny amount of security loss) we use 6 powers of $v$ instead of using 6 random values.
In the polynomial above, within the composition polynomial you might have noticed the value $\bar{z_{\omega}}$. It is the permutation polynomial $Z$ evaluated at $z \omega$. The only explanation I have of why you need that is in my video on the permutation of PlonK. Since the evaluation point ($z \omega$) is different from the first evaluation proof, we need a separate evaluation proof for that one (unfortunately).
The output is the pair of evaluation proofs. That's it!
Today, along with my two other cofounders Gregor Mitscha-Baude and Brandon Kase we are launching www.zksecurity.xyz an auditing platform for zero-knowledge applications.
Smart contracts have been at the source of billions of dollars of loss (see our previous project https://dasp.co). Nobody is sheltered from bugs. ZK smart contracts will have bugs, some devastating. Let's be proactive when it comes to zkApps!
In the coming month we'll be posting more about the kind of bugs that we have found in the space, from ZKP systems' bugs to frontend compiler bugs to application bugs. If you're looking for real experts to audit your ZK stack, you now have the ones behind zkSecurity.
We're a mix of engineers & researchers who have been working in the smart contract and ZK field before you were born (jk). On top of that, we've also been in the security consulting industry for a while, so we're professionals ;)
Stay tuned for more blogposts on http://zksecurity.xyz and reach out to me if you need an audit :)
Also, the launch blogpost is much more interesting than this one. Go read it here: Private delegated computation is here, and there will be bugs!
In the 5th episode of this series I interview Arik Sosman (our very first guest!) in order to learn more about Bitcoin transactions. Specifically, how the Bitcoin scripting language works, and what UTXOs are!
Pascal Paillier released his asymmetric encryption algorithm in 1999, which had the particularity of being homomorphic for the addition. (And unlike RSA, the homomorphism was secure.)
Homomorphic encryption, if you haven't heard of it, is the ability to operate on the ciphertext without having to decrypt it. If that still doesn't ring a bell, check my old blogpost on the subject. In this post I will just explain the intuition behind the scheme, for a less formal overview check Lange's excellent video.
Paillier's scheme is only homomorphic for the addition, which is still useful enough that it's been used in different kind of cryptographic protocols. For example, cryptdb was using it to allow some types of updates on encrypted database rows. More recently, threshold signature schemes have been using Paillier's scheme as well.
The actual algorithm
As with any asymmetric encryption scheme, you have the good ol' key gen, encryption, and decryption algorithms:
Key generation. Same as with RSA, you end up with a public modulus $N = pq$ where $p$ and $q$ are two large primes.
Encryption. This is where it gets weird, encryption looks more like a Pedersen commitment (which does not allow decryption). To encrypt, sample a random $r$ and produce the ciphertext as:
$$(N+1)^m \cdot r^N \mod{N^2}$$
where $m$ is the message to be encrypted. My thought at this point was "WOOT. A message in the exponent? How will we decrypt?"
Decryption. Retrieve the message from the ciphertext $c$ as
$$\frac{c^{\varphi(N)} -1}{N} \cdot \varphi(N)^{-1} \mod{N^2}$$
Wait, what? How is this recovering the message which is currently the discrete logarithm of $(N+1)^m$?
How decryption works
The trick is in expanding this exponentiation (using the Binomial expansion).
The relevant variant of the Binomial formula is the following:
$$(1+x)^n = \binom{n}{0}x^0 + \binom{n}{1}x^1 + \cdots + \binom{n}{n} x^n$$
where $\binom{a}{b} = \frac{a!}{b!(a-b)!}$
So in our case, if we only look at $(N+1)^m$ we have:
$$
\begin{align}
(N+1)^m &= \binom{m}{0} + \binom{m}{1} N + \binom{m}{2} N^2 + \cdots + \binom{m}{m} N^m \\
&= \binom{m}{0} + \binom{m}{1} N \mod{N^2}\\
&= 1 + m \cdot N \mod{N^2}
\end{align}
$$
Tada! Our message is now back in plain sight, extracted from the exponent. Isn't this magical?
This is of course not exactly what's happening. If you really want to see the real thing, read the next section, otherwise thanks for reading!
The deets
If you understand that, you should be able to reverse the actual decryption:
$$
\begin{align}
c^{\varphi(N)} &= ((N+1)^m \cdot r^N)^{\varphi(N)}\\
&= (N+1)^{m\cdot\varphi(N)} \cdot r^{N\varphi(N)} \mod{N^2}
\end{align}
$$
It turns out that the $r^{N\varphi(N)} = 1 \mod{N^2}$ because $N\varphi(N)$ is exactly the order of our group modulo $N^2$. You can visually think about why by looking at my fantastic drawing:
On the other hand, we get something similar to what I've talked before:
$$
(N+1)^{m\varphi(N)} = (1 + mN)^\varphi(N) = 1 + m\varphi(N)N \mod{N^2}
$$
Al that is left is to cancel the terms that are not interesting to us, and we get the message back.
