Mathematical Cryptography, zkSNARKs
Notes $\mathbb F_p$ is a Finite Field. We use an Elliptic Curve $E(\mathbb F_p)$ over this field. The order of the curve is $q$ & the discrete log problem is hard in the Group of the Curve. When we sample any random numbers in this post, please assume it’s sampled from $\mathbb F_q$. The Prover is $\mathcal P$ & the Verifier $\mathcal V$. Prerequisites Pedersen Commitments The basic Pedersen…
Prerequisites, Primitives & Notations Bitcoin Transactions Before getting into Monero, let’s first see how Bitcoin (BTC) transactions work. In BTC, every wallet has an Elliptic Curve Public-Private Key Pair. Let $G$ be the Generator of the Elliptic Curve used by BTC. If $x$ is someone’s private key, then $P = xG$ is his public key. Let’s dive into a transaction between Alice & Bob. Alice rents an…
Groth16 is a zkSNARK protocol introduced by Jens Groth in 2016 & it saw an early application in ZCash. Its proof size is among the smallest (consisting of only three elliptic curve elements) and it is also the fastest to verify
The Sum-Check Protocol $g$ is a $v$-variate polynomial defined over a Field $\mathbb F$. \[\\ u = \sum_{x_1 \in \lbrace 0,1 \rbrace} \sum_{x_2 \in \lbrace 0,1 \rbrace} ... \sum_{x_v \in \lbrace 0,1 \rbrace} g(x_1, x_2, ..., x_v) - (Eq\space I) \\\] The above equation sums $g$ over all possible Boolean inputs. The Prover ($\mathcal P$) claims that the sum is $u$. The Sum-Check protocol allows…
Prerequisite Topics Note: The target audience for this post is someone with a basic knowledge of zkSNARKs in general without knowing much about $\mathcal{P} \mathfrak{lon}\mathcal{K}$. Here is a post about an older SNARK - Groth16 . Elliptic Curve Pairings $\mathcal{P} \mathfrak{lon}\mathcal{K}$ uses Elliptic Curve Pairings. If you aren’t familiar with Pairings, here is an introduction to Elliptic…
Like every SNARK, in $\mathcal{P} \mathfrak{lon}\mathcal{K}$, we have to check if Gate Constraints are satisfied. Other than this, there are also Copy Constraints which have to be checked. Consider the following Circuit & it’s trace for witness $x = 4$ The vectors $a$, $b$ & $c$ here would be $a = [4, 16, 4, 68]$ $b = [4,4,64,5]$ $c = [16,64,68,73]$ As shown by the coloured lines in the trace…
Multiplicative Subgroup Q: Why does $\mathcal{P} \mathfrak{lon}\mathcal{K}$ use a multiplicative subgroup? A: There are multiple reasons why $\mathcal{P} \mathfrak{lon}\mathcal{K}$ uses a multiplicative subgroup $(1)\space$ Every element of a finite field is a root of unity . A Finite Field $\mathbb F_p$ has a multiplicative subgroup of order $n$ only if $n$ divides $p-1$. All primitive roots of…
The Prover wants to prove to the Verifier that she knows the solution to a particular equation without revealing the solution itself. In order for her to do this, in the Pinnochio & Groth16 zkSNARKs, she has to first transform the equation into the QAP (Quadratic Arithmetic Program) form. This post explains only the conversion part of these zkSNARKs. This post is based on Vitalik Buterin’s write…
Introduction Commitment schemes are fundamental components of many cryptographic protocols. A secure commitment scheme allows a committer to publish a value, called the commitment, which binds her to a message (binding) without revealing it (hiding). Later, she may open the commitment and reveal the committed message to a verifier, who can check that the message is consistent with the commitment.…
Why Elliptic Curve Cryptography? Q. Why does modern cryptography prefer the discrete log problem over the additive group of points on an Elliptic Curve defined over a Finite Field rather than integer factorization or the discrete log problem over the multiplicative group of a Finite Field? A. A cryptographic algorithm is said to have a security level of $n$ bits if the best known attack can break…