Home

Following 1 and some modern notations, I aim to describe a formal definition of a $3$-step interactive $\Sigma$-protocol with formal proofs. So: For an NP relation $\mathcal{R}$ a $\Sigma$-protocol is a $3$-step protocol between the Prover and the Verifier consisting of three algorithms $\sigma_{com}, \sigma_{resp}, \sigma_{ver}$ with respec...

The purpose of a memory checking protocol is to allow a verifier to audit a large, untrusted memory transcript using only a small proof. The prover logs every read and write operation, generating a proof that guarantees both the correctness of the final memory state and the consistency of all operations. While most popular zkVMs use fairly stand...

The $GF(2^n)$ field First of all, let’s examine what a $GF(2^n)$ field is: it is a finite field with $2^n$ elements that is built as a field extension of $GF(2)$ using some polynomial $P(x)$ with degree $n$. It has basis $\mathcal{B} = {x^i}\big|_{0}^{n-1}$. It also has the following properties: $GF(2^n)$ is a field with characteristic $2$...

The Bulletproofs protocol when appeared made some kind of revolution in ZK world, especially in anonymous transactions where range proofs are the most complicated and important part to validate correct transfer. Today, may protocols rely on Bulletproofs of Bulletproofs+ (more advanced version) to enable range-proofs. Additionally, Bulletproofs p...

File download: Dark White Here I’m not going to describe the general definition of zk-SNARK or any related terms. Instead, I’ll try to help reader to understand the underling math of one of the first popular and novel zk-SNARK protocols called a Pinocchio protocol appeared in 2013. Special thanks to Anton Levochko and ZK-DL lectur...

Commitment Vortex has much in common with Ligero (frankly speaking, it has been built using Ligero idea). So, imagine we have a list of polynomials $f_0,\dots,f_{k-1}$. We want to commit them and evaluate at the same point at the same time. We describe each polynomial as vector $a_i$ where \[f_i(x) = \sum_{j=0}^{n-1} x^j\cdot a_{i,j}\] For si...

To commit to an $\ell$-variate multilinear polynomial $f(x)$ we assume it (as equivalent) to represent as a list of elements where each element at the position $i$ equals to $f(\tilde{i})$ where $\tilde{i}$ represents a bit string equivalent to the $i$ value. Then, we reorganize this list into the matrix $M$ of size $2^{\ell_0} \times 2^{\ell_1}...

Using KoalaBear field Linea and Gnark aim to operate over the koalabear field (over prime modulus 2^31 - 2^24 + 1). The usage of this field as the proving field (outer field) in modern proving backends may require implementing a field extension that increases the field size to ~128 bits. The goal they aim to achieve — enable the usage of fie...