Home

tl;dr: Groth16 is one of the most popular general-purpose zkSNARK schemes. Although Groth16 is slower to prove than more recent zkSNARKs, it has the smallest proof size and the fastest verification time. This probably explains why it has seen such wide adoption in the cryptocurrency space. (Recently, WHIR[^ACFY24e] could hope to challenge its ve...

tl;dr: This post describes some useful differentiation tricks when dealing with polynomials in cryptography.

tl;dr: A quadratic arithmetic program (QAP), a Rank-1 Constraint System (R1CS), and an NP relation are equivalent ways of representing a hard problem (or computation) whose solution can be verified in polynomial-time. In particular, R1CS is just a reformulation of QAPs as linear equations and, these days, it is used widely when formalizing compu...

tl;dr: A zero-knowledge proof (ZKP) system for an NP relation $R$ allows a prover, who has a statement $\mathbf{x}$ and a witness $\mathbf{w}$ to convince a verifier, who only has the statement $\mathbf{x}$, that $R(\mathbf{x}; \mathbf{w}) = 1$. Importantly, the proof leaks nothing about the secret witness $\mathbf{w}$. (e.g., a ZKP can be used...

tl;dr: An NP relation $R(\mathbf{x}; \mathbf{w})$ is a formalization of an algorithm $R$ that verifies a solution $\mathbf{w}$ to a problem $\mathbf{x}$ (in time $\poly(|\mathbf{x}|+|\mathbf{w}|)$. For example, $\mathsf{Sudoku}(\mathbf{x}; \mathbf{w})$ verifies if $\mathbf{w}$ is a valid solution to the Sudoku puzzle $\mathbf{x}$. NP relations a...

tl;dr: We cover a few basic linear algebra concepts: vectors, matrices, matrix-vector products, vector dot products, Haddamard products, etc.

tl;dr: Do you want to sign (committed) field elements without relying on random oracles? Do you want to efficiently prove (in zero-knowledge) relations over your signed messages? BBS+ is here to help you! The BBS+ signature scheme is a transformation[^ASM08e] of the Boneh-Boyen-Shacham (BBS) group signature scheme[^BBS04] into a standalone sig...

This is some of the stuff I (plan to) read and think others could find useful. Blogroll Oded Goldreich’s essays blog.cr.yp.to David Wong’s Cryptologie Dcentralized thoughts Scott Aaronson Michael Nielsen Filippo Valsorda Craig Gidney Jeremy Kun Cryptography and (zero-knowledge) proof systems Cryptography 101, Alfred ...