Pointcheval-Sanders (PS) signatures
tl;dr: Pointcheval-Sanders (PS) is the coolest most versatile signature scheme I know of!
How to verify a Groth16 VK was generated from some R1CS
tl;dr:
Inspired by a tweet1, we explore whether, given (1) an R1CS and (2) some “powers-of-$\tau$”, we could construct a cryptographic proof that a Groth16 VK was derived from them.
This should make it more efficient for folks to ensure that an on-chain VK corresponds to some published ZK circuit code (e.g., circom).
Nonetheless, this is not suf...
Circom
tl;dr: My current sense: circom is still in its early days.
First, it lacks an ability to write correctness tests natively in its own language (as opposed to JavaScript testing frameworks).
Second, it gives no mechanism for developers to ascertain soundness of their templates.
(In its defense, the only such mechanism is a formal verification fra...
Groth16
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...
Polynomial differentiation tricks
tl;dr: This post describes some useful differentiation tricks when dealing with polynomials in cryptography.
Quadratic Arithmetic Programs (QAPs) and Rank-1 Constraint Systems (R1CS)
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...
(Defining) zero-knowledge proofs
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...
NP relations
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...
62 post articles, 8 pages.