🚀 MyZKP: Building Zero Knowledge Proof from Scratch in Rust

███╗   ███╗  ██╗   ██╗  ███████╗  ██╗  ██╗  ██████╗   🦀
████╗ ████║  ╚██╗ ██╔╝  ╚══███╔╝  ██║ ██╔╝  ██╔══██╗ 🦀
██╔████╔██║   ╚████╔╝     ███╔╝   █████╔╝   ██████╔╝ 
██║╚██╔╝██║    ╚██╔╝     ███╔╝    ██╔═██╗   ██╔═══╝    🦀
██║ ╚═╝ ██║     ██║     ███████╗  ██║  ██╗  ██║    🦀    
╚═╝     ╚═╝     ╚═╝     ╚══════╝  ╚═╝  ╚═╝  ╚═╝      🦀

MyZKP is a Rust implementation of zero-knowledge protocols built entirely from scratch! This project serves as an educational resource for understanding and working with zero-knowledge proofs.

⚠️ Warning: This repository is a work in progress and may contain bugs or inaccuracies. Contributions and feedback are welcome!

Index

🧮 Basic of Number Theory

• 📝 Computation Rule and Properties
• ⚙️ Semigroup, Group, Ring, and Field
• 🔢 Polynomials
• 🌐 Galois Field
• 📈 Elliptic Curve
• 🔗 Pairing
• 🤔 Useful Assumptions

🔒 Basic of zk-SNARKs

• ⚡ Arithmetization
• 🛠️ Proving Single Polynomial

🌟 Basic of zk-STARKs

• ✍️ TBD

💻 Basic of zkVM

• ✍️ TBD

🛠️ Code Reference

✨ Contributions are Welcome!

Feel free to submit issues or pull requests to enhance the project.

Basics of Number Theory

Computation Rule and Properties

Definition: Binary Operation

A mapping \(\circ: X \times X \rightarrow X\) is a binary operation on \(X\) if for any pair of elements \((x_1, x_2)\) in \(X\), \(x_1 \circ x_2\) is also in \(X\).

Example: Addition (+) on the set of integers is a binary operation. For example, \(5 + 3 = 8\), and both \(5, 3, 8\) are integers, staying within the set of integers.

Definition: Associative Property

A binary operation \(\circ\) is associative if \((a \circ b) \circ c = a \circ (b \circ c)\) for all \(a, b, c \in X\).

Example: Multiplication of real numbers is associative: \((2 \times 3) \times 4 = 2 \times (3 \times 4) = 24\). In a modular context, we also have addition modulo \(n\) being associative. For example, for \(n = 5\), \((2 + 3) \bmod 5 + 4 \bmod 5 = 2 + (3 \bmod 5 + 4) \bmod 5 = 4\).

Definition: Commutative Property

A binary operation \(\circ\) is commutative if \(a \circ b = b \circ a\) for all \(a, b \in X\).

Example: Addition modulo \(n\) is also commutative. For \(n = 7\), \(5 + 3 \bmod 7 = 3 + 5 \bmod 7 = 1\).

Semigroup, Group, Ring, and Field

Definition: Semigroup

A pair \((H, \circ)\), where \(H\) is a non-empty set and \(\circ\) is an associative binary operation on \(H\), is called a semigroup.

Example: The set of positive integers under multiplication modulo \(n\) forms a semigroup. For instance, with \(n = 6\), the elements \(\{1, 2, 3, 4, 5\}\) under multiplication modulo 6 form a semigroup, since multiplication modulo 6 is associative.

Definition: Abelian Semigroup

A semigroup whose operation is commutative is called an abelian semigroup.

Example: The set of natural numbers under addition modulo \(n\) forms an abelian semigroup. For \(n = 7\), addition modulo 7 is both associative and commutative, so it is an abelian semigroup.

Definition: Identity Element

An element \(e \in H\) is an identity element of \(H\) if it satisfies \(e \circ a = a \circ e = a\) for any \(a \in H\).

Example: 0 is the identity element for addition modulo \(n\). For example, \(0 + a \bmod 5 = a + 0 \bmod 5 = a\). Similarly, 1 is the identity element for multiplication modulo \(n\). For example, \(1 \times a \bmod 7 = a \times 1 \bmod 7 = a\).

Definition: Monoid

A semigroup with an identity element is called a monoid.

Example: The set of non-negative integers under addition modulo \(n\) forms a monoid. For \(n = 5\), the set \(\{0, 1, 2, 3, 4\}\) under addition modulo 5 forms a monoid with 0 as the identity element.

Definition: Inverse

For an element \(a \in H\), an element \(b \in H\) is an inverse of \(a\) if \(a \circ b = b \circ a = e\), where \(e\) is the identity element.

Example: In modulo \(n\) arithmetic (addition), the inverse of an element exists if it can cancel itself out to yield the identity element. In the set of integers modulo 7, the inverse of 3 is 5, because \(3 \times 5 \bmod 7 = 1\), where 1 is the identity element for multiplication.

Definition: Group

A monoid in which every element has an inverse is called a group.

Example: The set of integers modulo a prime \(p\) under multiplication forms a group (Can you prove it?). For instance, in \(\mathbb{Z}/5\mathbb{Z}\), every non-zero element \(\{1 + 5\mathbb{Z}, 2 + 5\mathbb{Z}, 3 + 5\mathbb{Z}, 4 + 5\mathbb{Z}\}\) has an inverse, making it a group.

Definition: Order of a Group

The order of a group is the number of elements in the group.

Example: The group of integers modulo 4 under addition has order 4, because the set of elements is \(\{0, 1, 2, 3\}\).

Definition: Ring

A triple \((R, +, \cdot)\) is a ring if \((R, +)\) is an abelian group, \((R, \cdot)\) is a semigroup, and the distributive property holds: \(x \cdot (y + z) = (x \cdot y) + (x \cdot z)\) and \((x + y) \cdot z = (x \cdot z) + (y \cdot z)\) for all \(x, y, z \in R\).

Example: The set of integers with usual addition and multiplication modulo \(n\) forms a ring. For example, in \(\mathbb{Z}/6\mathbb{Z}\), addition and multiplication modulo 6 form a ring.

Implementation:

#![allow(unused)]
fn main() {
use num_bigint::BigInt;
use num_traits::{One, Zero};
use std::fmt;
use std::ops::{Add, Mul, Neg, Sub};

pub trait Ring:
    Sized
    + Clone
    + PartialEq
    + fmt::Display
    + Add<Output = Self>
    + for<'a> Add<&'a Self, Output = Self>
    + Sub<Output = Self>
    + for<'a> Sub<&'a Self, Output = Self>
    + Mul<Output = Self>
    + for<'a> Mul<&'a Self, Output = Self>
    + Neg<Output = Self>
    + One
    + Zero
{
    // A ring is an algebraic structure with addition and multiplication
    fn add_ref(&self, rhs: &Self) -> Self;
    fn sub_ref(&self, rhs: &Self) -> Self;
    fn mul_ref(&self, rhs: &Self) -> Self;

    // Utility functions
    fn pow<M: Into<BigInt>>(&self, n: M) -> Self;
    fn get_value(&self) -> BigInt;
    fn from_value<M: Into<BigInt>>(value: M) -> Self;
    fn random_element(exclude_elements: &[Self]) -> Self;
}
}

Definition: Communicative Ring

A ring is called a commutative ring if its multiplication operation is commutative.

Example The set of real numbers under usual addition and multiplication forms a commutative ring.

Definition: Field

A commutative ring with a multiplicative identity element where every non-zero element has a multiplicative inverse is called a field.

Example The set of rational numbers under usual addition and multiplication forms a field.

Implementation:

#![allow(unused)]
fn main() {
pub trait Field: Ring + Div<Output = Self> + PartialEq + Eq + Hash {
    /// Computes the multiplicative inverse of the element.
    fn inverse(&self) -> Self;
    fn div_ref(&self, other: &Self) -> Self;
}
}

Definition: Residue Class

The residue class of \( a \) modulo \( m \), denoted as \( a + m\mathbb{Z} \), is the set \( \{b : b \equiv a \pmod{m}\} \).

Example: For \( m = 3 \), the residue class of 2 is \( 2 + 3\mathbb{Z} = \{\ldots, -4, -1, 2, 5, 8, \ldots\} \).

Definition: Inverse of Residue Class

We denote the set of all residue classes modulo \( m \) as \( \mathbb{Z} / m\mathbb{Z} \). We say that \( a + m\mathbb{Z} \) is invertible in \( \mathbb{Z} / m\mathbb{Z} \) if and only if there exists a solution for \( ax \equiv 1 \pmod{m} \).

Example: In \( \mathbb{Z}/5\mathbb{Z} \), \( 3 + 5\mathbb{Z} \) is invertible because \( \gcd(3, 5) = 1 \) (since \( 3\cdot2 \equiv 1 \pmod{5} \)). However, in \( \mathbb{Z}/6\mathbb{Z} \), \( 3 + 6\mathbb{Z} \) is not invertible because \( \gcd(3, 6) = 3 \neq 1 \).

Lemma 2.2.1

If \( a \) and \( b \) are coprime, the residues of \( a \), \( 2a \), \( 3a \), ..., \( (b-1)a \) modulo \( b \) are all distinct.

Proof: Suppose, for contradiction, that there exist \( x, y \in \{1, 2, \dots, b-1\} \) with \( x \neq y \) such that \( xa \equiv ya \pmod{b} \). Then \( (x-y)a \equiv 0 \pmod{b} \), implying \( b \mid (x-y)a \). Since \( a \) and \( b \) are coprime, we must have \( b \mid (x-y) \). However, \( |x-y| < b \), so this is only possible if \( x = y \), contradicting our assumption. Therefore, all residues must be distinct.

Theorem 2.2.2

For any integers \( a \) and \( b \), the equation \( ax + by = 1 \) has a solution in integers \( x \) and \( y \) if and only if \( a \) and \( b \) are coprime.

Proof:

• (\( \Rightarrow \)) Suppose \( a \) and \( b \) are not coprime, let \( d = \gcd(a,b) > 1 \). Then \( d \mid a \) and \( d \mid b \), so \( d \mid (ax + by) \) for any integers \( x \) and \( y \). Thus, \( ax + by \neq 1 \) for any \( x \) and \( y \).
• (\( \Leftarrow \)) Suppose \( a \) and \( b \) are coprime. By the previous lemma, the residues of \( a \), \( 2a \), ..., \( (b-1)a \) modulo \( b \) are all distinct. Therefore, there exists an \( m \in \{1, 2, ..., b-1\} \) such that \( ma \equiv 1 \pmod{b} \). This means there exists an integer \( n \) such that \( ma = bn + 1 \), or equivalently, \( ma - bn = 1 \).

Theorem: Bézout's Identity

For any integers \( a \) and \( b \), we have: \( a\mathbb{Z} + b \mathbb{Z} = \gcd(a, b)\mathbb{Z} \)

Proof:

This statement is equivalent to proving that \( ax + by = c \) has an integer solution if and only if \( c \) is a multiple of \( \gcd(a,b) \).

• (\( \Rightarrow \)) If \( ax + by = c \) for some integers \( x \) and \( y \), then \( \gcd(a,b) \mid a \) and \( \gcd(a,b) \mid b \), so \( \gcd(a,b) \mid (ax + by) = c \).
• (\( \Leftarrow \)) Let \( c = k\gcd(a,b) \) for some integer \( k \). We can write \( a = p\gcd(a,b) \) and \( b = q\gcd(a,b) \), where \( p \) and \( q \) are coprime. By the previous theorem, there exist integers \( m \) and \( n \) such that \( pm + qn = 1 \). Multiplying both sides by \( k\gcd(a,b) \), we get: \[ akm + bkn = c \] Thus, \( x = km \) and \( y = kn \) are integer solutions to \( ax + by = c \).

This theorem implies that for any integers \( a \), \( b \), and \( n \), the equation \( ax + by = n \) has an integer solution if and only if \( \gcd(a,b) \mid n \).

Theorem 2.2.3

\( a + m\mathbb{Z} \) is invertible in \( \mathbb{Z}/m\mathbb{Z} \) if and only if \( \gcd(a,m) = 1 \).

Proof:

• (\( \Rightarrow \)) Suppose \( a + m\mathbb{Z} \) is invertible in \( \mathbb{Z}/m\mathbb{Z} \). Then there exists an integer \( x \) such that \( ax \equiv 1 \pmod{m} \). Let \( g = \gcd(a,m) \). Since \( g \mid ax \) and \( g \mid (ax - 1) \), we must have \( g \mid 1 \), so \( g = 1 \).
• (\( \Leftarrow \)) Suppose \( \gcd(a,m) = 1 \). By Bézout's identity, there exist integers \( x \) and \( y \) such that \( ax + my = 1 \). Thus, \( x + m\mathbb{Z} \) is the multiplicative inverse of \( a + m\mathbb{Z} \) in \( \mathbb{Z}/m\mathbb{Z} \).

Definition: Residue Class Ring

\( (\mathbb{Z} / m \mathbb{Z}, +, \cdot) \) is a commutative ring where \( 1 + m \mathbb{Z} \) is the multiplicative identity element. This ring is called the residue class ring modulo \( m \).

Example: \( \mathbb{Z}/4\mathbb{Z} = \{0 + 4\mathbb{Z}, 1 + 4\mathbb{Z}, 2 + 4\mathbb{Z}, 3 + 4\mathbb{Z}\} \).

Definition: Primitive Residue Class

A residue class \( a + m\mathbb{Z} \) is called primitive if \( \gcd(a, m) = 1 \).

Example: In \( \mathbb{Z}/6\mathbb{Z} \), the primitive residue classes are \( 1 + 6\mathbb{Z} \) and \( 5 + 6\mathbb{Z} \).

Theorem 2.2.4

A residue ring \( \mathbb{Z} / m\mathbb{Z} \) is a field if and only if \( m \) is a prime number.

Proof: TBD

Example: For \( m = 5 \), \( \mathbb{Z}/5\mathbb{Z} = \{0 + 5\mathbb{Z}, 1 + 5\mathbb{Z}, 2 + 5\mathbb{Z}, 3 + 5\mathbb{Z}, 4 + 5\mathbb{Z}\} \) forms a field because 5 is a prime number, and every non-zero element has a multiplicative inverse.

Definition: Primitive Residue Class Group

The group of all primitive residue classes modulo \( m \) is called the primitive residue class group, denoted by \( (\mathbb{Z}/m\mathbb{Z})^{\times} \).

Example: For \( m = 8 \), the set of all primitive residue classes is \( (\mathbb{Z}/8\mathbb{Z})^{\times} = \{1 + 8\mathbb{Z}, 3 + 8\mathbb{Z}, 5 + 8\mathbb{Z}, 7 + 8\mathbb{Z}\} \). These are the integers less than 8 that are coprime to 8 (i.e., \(\gcd(a, 8) = 1\)).

Contrast this with \( m = 9 \). The primitive residue class group is \((\mathbb{Z}/9\mathbb{Z})^{\times} = \{1 + 9\mathbb{Z}, 2 + 9\mathbb{Z}, 4 + 9\mathbb{Z}, 5 + 9\mathbb{Z}, 7 + 9\mathbb{Z}, 8 + 9\mathbb{Z}\}\), as these are the integers less than 9 that are coprime to 9.

Definition: Euler's Totient Function

Euler's totient function \(\phi(m)\) is equal to the order of the primitive residue class group modulo \(m\), which is the number of integers less than \(m\) and coprime to \(m\).

Example: For \(m = 12\), \(\phi(12) = 4\) because there are 4 integers less than 12 that are coprime to 12: \({1, 5, 7, 11}\).

For \(m = 10\), \(\phi(10) = 4\), as there are also 4 integers less than 10 that are coprime to 10: \({1, 3, 7, 9}\).

Definition: Order of an Element within a Group

The order of \(g \in G\) is the smallest natural number \(e\) such that \(g^{e} = 1\). We denote it as \(\text{order}_g(g)\)or \(\text{order } g\).

Example: In \((\mathbb{Z}/7\mathbb{Z})^{\times}\), the element 3 has order 6 because \(3^6 \bmod 7 = 1\). In other words, \(3 \times 3 \times 3 \times 3 \times 3 \times 3 \bmod 7 = 1\), and 6 is the smallest such exponent.

Definition: Subgroup

A subset \(U \subseteq G\) is a subgroup of \(G\) if \(U\) itself is a group under the operation of \(G\).

Example: Consider \((\mathbb{Z}/8\mathbb{Z})^{\times} = \{1 + 8\mathbb{Z}, 3+ 8\mathbb{Z}, 5+ 8\mathbb{Z}, 7+ 8\mathbb{Z}\}\) under multiplication modulo 8. The subset \({1+ 8\mathbb{Z}, 7+ 8\mathbb{Z}}\) forms a subgroup because it satisfies the group properties: closed under multiplication, contains the identity element (1), and every element has an inverse (\(7 \times 7 \equiv 1 \bmod 8\)).

Definition: Subgroup Generated by \(g\)

The set \(\{g^{k} : k \in \mathbb{Z}\}\), for some element \(g \in G\), forms a subgroup of \(G\) and is called the subgroup generated by \(g\), denoted by \(\langle g \rangle\).

Example: Consider the group \((\mathbb{Z}/7\mathbb{Z})^{\times} = \{1+ 7\mathbb{Z}, 2+ 7\mathbb{Z}, 3+ 7\mathbb{Z}, 4+ 7\mathbb{Z}, 5+ 7\mathbb{Z}, 6+ 7\mathbb{Z}\}\) under multiplication modulo 7. If we take \(g = 3\), then \(\langle 3 +7\mathbb{Z} \rangle =\) \(\{3^1+7\mathbb{Z}, 3^2+7\mathbb{Z}, 3^3+7\mathbb{Z}, 3^4+7\mathbb{Z}, 3^5+7\mathbb{Z}, 3^6+7\mathbb{Z}\} \bmod 7 =\) \(\{3+7\mathbb{Z}, 2+7\mathbb{Z}, 6+7\mathbb{Z}, 4+7\mathbb{Z}, 5+7\mathbb{Z}, 1+7\mathbb{Z}\}\), which forms a subgroup generated by 3. This subgroup contains all elements of \((\mathbb{Z}/7\mathbb{Z})^{\times}\), making 3 a generator of the entire group.

If \(g\) has a finite order \(e\), we have that \(\langle g \rangle = \{g^{k}: 0 \leq k \leq e\}\), meaning \(e\) is the order of \(\langle g \rangle\).

Definition: Cyclic Group

A group \(G\) is called a cyclic group if there exists an element \(g \in G\) such that \(G = \langle g \rangle\). In this case, \(g\) is called a generator of \(G\).

Example: The group \((\mathbb{Z}/6\mathbb{Z})^{\times} = \{1+6\mathbb{Z}, 5+6\mathbb{Z}\}\) under multiplication modulo 6 is a cyclic group. In this case, both 1 and 5 are generators of the group because \(\langle 5 +6\mathbb{Z} \rangle = \{(5^1 \bmod 6)+6\mathbb{Z} = 5 +6\mathbb{Z}, (5^2 \bmod 6)+6\mathbb{Z} = 1+6\mathbb{Z}\}\). Since 5 generates all the elements of the group, \(G\) is cyclic.

Theorem 2.2.5

If \(G\) is a finite cyclic group, it has \(\phi(|G|)\)generators, and each generator has order \(|G|\).

Proof: TBD

Example: Consider the group \((\mathbb{Z}/8\mathbb{Z})^{\times} = \{1+8\mathbb{Z}, 3+8\mathbb{Z}, 5+8\mathbb{Z}, 7+8\mathbb{Z}\}\). This group is cyclic, and \(\phi(8) = 4\). The generators of this group are \(\{1+8\mathbb{Z}, 3+8\mathbb{Z}, 5+8\mathbb{Z}, 7+8\mathbb{Z}\}\), each of which generates the entire group when raised to successive powers modulo 8. Each generator has the same order, which is \(|G| = 4\).

Theorem 2.2.6

If \(G\) is a finite cyclic group, the order of any subgroup of \(G\) divides the order of \(G\).

Proof: TBD

Example: Consider the cyclic group \((\mathbb{Z}/6\mathbb{Z})^{\times} = \{1+6\mathbb{Z}, 5+6\mathbb{Z}\}\) under multiplication modulo 6. If we take the subgroup \(\langle 5+6\mathbb{Z} \rangle = \{1+6\mathbb{Z}, 5+6\mathbb{Z}\}\), this is a subgroup of order 2, and 2 divides the order of the original group, which is 6. This theorem generalizes this property: for any subgroup of a cyclic group, its order divides the order of the group.

Theorem: Fermat's Little Theorem

If \(\gcd(a, m) = 1\), then \(a^{\phi(m)} \equiv 1 \pmod{m}\).

Proof: TBD

Example: Take \(a = 2\) and \(m = 5\). Since \(\gcd(2, 5) = 1\), Fermat's Little Theorem tells us that \(2^{\phi(5)} = 2^4 \equiv 1 \bmod 5\). Indeed, \(2^4 = 16\) and \(16 \bmod 5 = 1\).

This theorem suggests that \(a^{\phi(m) - 1} + m \mathbb{Z}\) is the inverse residue class of \(a + m \mathbb{Z}\).

Theorem 2.2.7

The order of any element in a group divides the order of the group.

Proof: TBD

Example: In the group \((\mathbb{Z}/7\mathbb{Z})^{\times}\), consider the element \(3 + 7\mathbb{Z}\). The order of \(3 + 7\mathbb{Z}\) is 6, as \(3^6 \equiv 1 \bmod 7\). The order of the group itself is also 6, and indeed, the order of the element divides the order of the group.

Theorem: Generalization of Fermat's Little Theorem

For any element \(g \in G\), we have \(g^{|G|} = 1\).

Proof: TBD

Example: In the group \((\mathbb{Z}/7\mathbb{Z})^{\times}\), for any element \(g\), such as \(g = 3 + 7\mathbb{Z}\), we have \(3^6 \equiv 1 \bmod 7\). This holds for any \(g \in (\mathbb{Z}/7\mathbb{Z})^{\times}\) because the order of the group is 6. Thus, \(g^{|G|} = 1\) is satisfied.

Polynomials

Definition: Polynomial

A univariate polynomial over a commutative ring \(R\) with unity \(1\) is an expression of the form \(f(x) = a_n x^{n} + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0\), where \(x\) is a variable and coefficients \(a_0, \ldots, a_n\) belong to \(R\). The set of all polynomials over \(R\) in the variable \(x\) is denoted as \(R[x]\).

Example: In \(\mathbb{Z}[x]\), we have polynomials such as \(2x^3 + x + 1\), \(x\), and \(1\). In \(\mathbb{R}[x]\), we have polynomials like \(\pi x^2 - \sqrt{2}x + e\).

Implementation:

#![allow(unused)]
fn main() {
/// A struct representing a polynomial over a finite field.
#[derive(Debug, Clone, PartialEq)]
pub struct Polynomial<F: Field> {
    /// Coefficients of the polynomial in increasing order of degree.
    pub coef: Vec<F>,
}
}

Definition: Degree

The degree of a non-zero polynomial \(f(x) = a_n x^{n} + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0\), denoted as \(\deg f\), is the largest integer \(n\) such that \(a_n \neq 0\). The zero polynomial is defined to have degree \(-1\).

Example

• \(\deg(2x^3 + x + 1) = 3\)
• \(\deg(x) = 1\)
• \(\deg(1) = 0\)
• \(\deg(0) = -1\)

Implementation:

#![allow(unused)]
fn main() {
impl<F: Field> Polynomial<F> {
    /// Removes trailing zeroes from a polynomial's coefficients.
    fn trim_trailing_zeros(poly: Vec<F>) -> Vec<F> {
        let mut trimmed = poly;
        while trimmed.last() == Some(&F::zero(None)) {
            trimmed.pop();
        }
        trimmed
    }

    /// Returns the degree of the polynomial.
    pub fn degree(&self) -> isize {
        let trimmed = Self::trim_trailing_zeros(self.poly.clone());
        if trimmed.is_empty() {
            -1
        } else {
            (trimmed.len() - 1) as isize
        }
    }
}
}

Definition: Sum of Polynomials

For polynomials \(f(x) = \sum_{i=0}^n a_i x^i\) and \(g(x) = \sum_{i=0}^m b_i x^i\), their sum is defined as: \((f + g)(x) = \sum_{i=0}^{\max(n,m)} (a_i + b_i) x^i\), where we set \(a_i = 0\) for \(i > n\) and \(b_i = 0\) for \(i > m\).

Example: Let \(f(x) = 2x^2 + 3x + 1\) and \(g(x) = x^3 - x + 4\). Then, \((f + g)(x) = x^3 + 2x^2 + 2x + 5\)

Implementation:

#![allow(unused)]
fn main() {
impl<F: Field> Polynomial<F> {
    fn add_ref<'b>(&self, other: &'b Polynomial<F>) -> Polynomial<F> {
        let max_len = std::cmp::max(self.coef.len(), other.coef.len());
        let mut result = Vec::with_capacity(max_len);

        let zero = F::zero();

        for i in 0..max_len {
            let a = self.coef.get(i).unwrap_or(&zero);
            let b = other.coef.get(i).unwrap_or(&zero);
            result.push(a.add_ref(b));
        }
        Polynomial {
            coef: Self::trim_trailing_zeros(result),
        }
    }
}

impl<F: Field> Add for Polynomial<F> {
    type Output = Self;

    fn add(self, other: Self) -> Polynomial<F> {
        self.add_ref(&other)
    }
}
}

Definition: Product of polynomials

For polynomials \(f(x) = \sum_{i=0}^n a_i x^i\) and \(g(x) = \sum_{j=0}^m b_j x^j\), their product is defined as: \((fg)(x) = \sum_{k=0}^{n+m} c_k x^k\), where \(c_k = \sum_{i+j=k} a_i b_j\)

Example: Let \(f(x) = x + 1\) and \(g(x) = x^2 - 1\). Then, \((fg)(x) = x^3 + x^2 - x - 1\)

Implementation:

#![allow(unused)]
fn main() {
impl<F: Field> Polynomial<F> {
    fn mul_ref<'b>(&self, other: &'b Polynomial<F>) -> Polynomial<F> {
        if self.is_zero() || other.is_zero() {
            return Polynomial::<F>::zero();
        }
        let mut result = vec![F::zero(); (self.degree() + other.degree() + 1) as usize];

        for (i, a) in self.coef.iter().enumerate() {
            for (j, b) in other.coef.iter().enumerate() {
                result[i + j] = result[i + j].add_ref(&a.mul_ref(b));
            }
        }
        Polynomial {
            coef: Polynomial::<F>::trim_trailing_zeros(result),
        }
    }
}

impl<F: Field> Mul<Polynomial<F>> for Polynomial<F> {
    type Output = Self;

    fn mul(self, other: Polynomial<F>) -> Polynomial<F> {
        self.mul_ref(&other)
    }
}
}

Lemma 2.3.1

Let \(K\) be a field.

Let \(f, g \in K[x]\) be non-zero polynomials. Then, \(\deg(fg) = \deg f + \deg g\).

Example: Let \(f(x) = x^2 + 1\) and \(g(x) = x^3 - x\) in \(\mathbb{R}[x]\). Then, \(\deg(fg) = \deg(x^5 - x^3 + x^2 + 1) = 5 = 2 + 3 = \deg f + \deg g\)

Theorem 2.3.2

We can also define division in the polynomial ring \(K[x]\).

Let \(f, g \in K[x]\), with \(g \neq 0\). There exist unique polynomials \(q, r \in K[x]\) that satisfy \(f = qg + r\) and either \(\deg r < \deg g\) or \(r = 0\).

Proof TBD

\(q\) is called the quotient of \(f\) divided by \(g\), and \(r\) is called the remainder; we write \(r = f \bmod g\).

Example: In \(\mathbb{R}[x]\), let \(f(x) = x^3 + 2x^2 - x + 3\) and \(g(x) = x^2 + 1\). Then \(f = qg + r\) where \(q(x) = x + 2\) and \(r(x) = -3x + 1\).

Implementation:

#![allow(unused)]
fn main() {
impl<F: Field> Polynomial<F> {
    fn div_rem_ref<'b>(&self, other: &'b Polynomial<F>) -> (Polynomial<F>, Polynomial<F>) {
        if self.degree() < other.degree() {
            return (Polynomial::zero(), self.clone());
        }

        let mut remainder_coeffs = Self::trim_trailing_zeros(self.coef.clone());
        let divisor_coeffs = Self::trim_trailing_zeros(other.coef.clone());
        let divisor_lead_inv = divisor_coeffs.last().unwrap().inverse();

        let mut quotient = vec![F::zero(); self.degree() as usize - other.degree() as usize + 1];

        while remainder_coeffs.len() >= divisor_coeffs.len() {
            let lead_term = remainder_coeffs.last().unwrap().mul_ref(&divisor_lead_inv);
            let deg_diff = remainder_coeffs.len() - divisor_coeffs.len();
            quotient[deg_diff] = lead_term.clone();

            for i in 0..divisor_coeffs.len() {
                remainder_coeffs[deg_diff + i] = remainder_coeffs[deg_diff + i]
                    .sub_ref(&(lead_term.mul_ref(&divisor_coeffs[i])));
            }
            remainder_coeffs = Self::trim_trailing_zeros(remainder_coeffs);
        }

        (
            Polynomial {
                coef: Self::trim_trailing_zeros(quotient),
            },
            Polynomial {
                coef: remainder_coeffs,
            },
        )
    }
}

impl<F: Field> Div for Polynomial<F> {
    type Output = Self;

    fn div(self, other: Polynomial<F>) -> Polynomial<F> {
        self.div_rem_ref(&other).0
    }
}
}

Corollary

Let \(f \in K[x]\) be a non-zero polynomial, and \(a \in K\) such that \(f(a) = 0\). Then, there exists a polynomial \(q \in K[x]\) such that \(f(x) = (x - a)q(x)\). In other words, \((x - a)\) is a factor of \(f(x)\).

Example: Let \(f(x) = x^2 + 1 \in (\mathbb{Z}/2\mathbb{Z})[x]\). We have \(f(1) = 1^2 + 1 = 0\) in \(\mathbb{Z}/2\mathbb{Z}\), and indeed: \(x^2 + 1 = (x - 1)^2 = x^2 - 2x + 1 = x^2 + 1\) in \((\mathbb{Z}/2\mathbb{Z})[x]\)

Theorem: Lagrange Interpolation

A \(n\)-degre polynomial \(P(x)\) that goes through different \(n + 1\) points \(\{(x_1, y_1), (x_2, y_2), \cdots (x_{n + 1}, y_{n + 1})\}\) is uniquely represented as follows:

\[ P(x) = \sum^{n+1}_{i=1} y_i \frac{f_i(x)}{f_i(x_i)} \]

, where \(f_i(x) = \prod_{k \neq i} (x - x_k)\)

Proof TBD

Example: The quadratic polynomial that goes through \(\{(1, 0), (2, 3), (3, 8)\}\) is as follows:

\begin{align*} P(x) = 0 \frac{(x - 2)(x - 3)}{(1 - 2) (1 - 3)} + 3 \frac{(x - 1)(x - 3)}{(2 - 1) (2 - 3)} + 8 \frac{(x - 1)(x - 2)}{(3 - 1) (3 - 2)} = x^{2} - 1 \end{align*}

Note that Lagrange interpolation finds the lowest degree of interpolating polynomial for the given vector.

Implementation:

#![allow(unused)]
fn main() {
impl<F: Field> Polynomial<F> {
    pub fn interpolate(x_values: &[F], y_values: &[F]) -> Polynomial<F> {
        let mut lagrange_polys = vec![];
        let numerators = Polynomial::from_monomials(x_values);

        for j in 0..x_values.len() {
            let mut denominator = F::one();
            for i in 0..x_values.len() {
                if i != j {
                    denominator = denominator * (x_values[j].sub_ref(&x_values[i]));
                }
            }
            let cur_poly = numerators
                .clone()
                .div(Polynomial::from_monomials(&[x_values[j].clone()]) * denominator);
            lagrange_polys.push(cur_poly);
        }

        let mut result = Polynomial { coef: vec![] };
        for (j, lagrange_poly) in lagrange_polys.iter().enumerate() {
            result = result + lagrange_poly.clone() * y_values[j].clone();
        }
        result
    }
}
}

Proposition: Homomorphisms of Lagrange Interpolation

Let \(L(v)\) and \(L(w)\) be the polynomial resulting from Lagrange Interpolation on the output (\(y\)) vector \(v\) and \(w\) for the same inputs (\(x\)). Then, the following properties hold:

• Additivity: \(L(v + w) = L(v) + L(w)\) for any vectors \(v\) and \(w\)
• Scalar multiplication: \(L(\gamma v) = \gamma L(v)\) for any scalar \(\gamma\) and vector \(v\)

Proof

Let \(v = (v_1, \ldots, v_n)\) and \(w = (w_1, \ldots, w_n)\) be vectors, and \(x_1, \ldots, x_n\) be the interpolation points.

\begin{align*} L(v + w) &= \sum_{i=1}^n (v_i + w_i) \prod_{j \neq i} \frac{x - x_j}{x_i - x_j} = \sum_{i=1}^n v_i \prod_{j \neq i} \frac{x - x_j}{x_i - x_j} + \sum_{i=1}^n w_i \prod_{j \neq i} \frac{x - x_j}{x_i - x_j} = L(v) + L(w) \\ L(\gamma v) &= \sum_{i=1}^n (\gamma v_i) \prod_{j \neq i} \frac{x - x_j}{x_i - x_j} = \gamma \sum_{i=1}^n v_i \prod_{j \neq i} \frac{x - x_j}{x_i - x_j} = \gamma L(v) \end{align*}

Galois Field

We will now discuss the construction of finite fields with \(p^n\) elements, where \(p\) is a prime number and \(n\) is a positive integer. These fields are also known as Galois fields, denoted as \(GF(p^n)\). It is evident that \(\mathbb{Z}/p\mathbb{Z}\) is isomorphic to \(GF(p)\).

Definition: Irreducible Polynomial

A polynomial \(f \in (\mathbb{Z}/p\mathbb{Z})[X]\) of degree \(n\) is called irreducible over \(\mathbb{Z}/p\mathbb{Z}\) if it cannot be factored as a product of two polynomials of lower degree in \((\mathbb{Z}/p\mathbb{Z})[X]\).

Example: In \((\mathbb{Z}/2\mathbb{Z})[X]\):

• \(X^2 + X + 1\) is irreducible
• \(X^2 + 1 = (X + 1)^2\) is reducible

Implementation:

#![allow(unused)]
fn main() {
pub trait IrreduciblePoly<F: Field>: Debug + Clone + Hash {
    fn modulus() -> &'static Polynomial<F>;
}
}

Definition: Residue Class modulo a Polynomial

To construct \(GF(p^n)\), we use an irreducible polynomial of degree \(n\) over \(\mathbb{Z}/p\mathbb{Z}\).

For \(f, g \in (\mathbb{Z}/p\mathbb{Z})[X]\), the residue class of \(g \bmod f\) is the set of all polynomials \(h \in (\mathbb{Z}/p\mathbb{Z})[X]\) such that \(h \equiv g \pmod{f}\). This class is denoted as:

\[ g + f(\mathbb{Z}/p\mathbb{Z})[X] = \{g + hf : h \in (\mathbb{Z}/p\mathbb{Z})[X]\} \]

Example: In \((\mathbb{Z}/2\mathbb{Z})[X]\), with \(f(X) = X^2 + X + 1\), the residue classes \(\bmod f\) are:

• \(0 + f(\mathbb{Z}/2\mathbb{Z})[X] = \{0, X^2 + X + 1, X^2 + X, X^2 + 1, X^2, X + 1, X, 1\}\)
• \(1 + f(\mathbb{Z}/2\mathbb{Z})[X] = \{1, X^2 + X, X^2 + 1, X^2, X + 1, X, 0, X^2 + X + 1\}\)
• \(X + f(\mathbb{Z}/2\mathbb{Z})[X] = \{X, X^2 + 1, X^2, X^2 + X + 1, X + 1, 1, X^2 + X, 0\}\)
• \((X + 1) + f(\mathbb{Z}/2\mathbb{Z})[X] = \{X + 1, X^2, X^2 + X + 1, X^2 + X, 1, 0, X^2 + 1, X\}\)

These four residue classes form \(GF(4)\).

Implementation:

#![allow(unused)]
fn main() {
impl<M: ModulusValue + 'static, P: IrreduciblePoly<FiniteFieldElement<M>>>
    ExtendedFieldElement<M, P>
{
    pub fn new(poly: Polynomial<FiniteFieldElement<M>>) -> Self {
        let result = Self {
            poly: poly,
            _phantom: PhantomData,
        };
        result.reduce()
    }

    fn reduce(&self) -> Self {
        Self {
            poly: &self.poly.reduce() % P::modulus(),
            _phantom: PhantomData,
        }
    }

    pub fn degree(&self) -> isize {
        P::modulus().degree()
    }

    pub fn from_base_field(value: FiniteFieldElement<M>) -> Self {
        Self::new((Polynomial { coef: vec![value] }).reduce()).reduce()
    }
}

impl<M: ModulusValue + 'static, P: IrreduciblePoly<FiniteFieldElement<M>>> Field
    for ExtendedFieldElement<M, P>
{
    fn inverse(&self) -> Self {
        let mut lm = Polynomial::<FiniteFieldElement<M>>::one();
        let mut hm = Polynomial::zero();
        let mut low = self.poly.clone();
        let mut high = P::modulus().clone();

        while !low.is_zero() {
            let q = &high / &low;
            let r = &high % &low;
            let nm = hm - (&lm * &q);
            high = low;
            hm = lm;
            low = r;
            lm = nm;
        }

        Self::new(hm * high.coef[0].inverse())
    }

    fn div_ref(&self, other: &Self) -> Self {
        self.mul_ref(&other.inverse())
    }
}
}

Theorem:

If \(f \in (\mathbb{Z}/p\mathbb{Z})[X]\) is an irreducible polynomial of degree \(n\), then the residue ring \((\mathbb{Z}/p\mathbb{Z})[X]/(f)\) is a field with \(p^n\) elements, isomorphic to \(GF(p^n)\).

Proof (Outline) The irreducibility of \(f\) ensures that \((f)\) is a maximal ideal in \((\mathbb{Z}/p\mathbb{Z})[X]\), making the quotient ring a field. The number of elements is \(p^n\) because there are \(p^n\) polynomials of degree less than \(n\) over \(\mathbb{Z}/p\mathbb{Z}\).

This construction allows us to represent elements of \(GF(p^n)\) as polynomials of degree less than \(n\) over \(\mathbb{Z}/p\mathbb{Z}\). Addition is performed coefficient-wise modulo \(p\), while multiplication is performed modulo the irreducible polynomial \(f\).

Example: To construct \(GF(8)\), we can use the irreducible polynomial \(f(X) = X^3 + X + 1\) over \(\mathbb{Z}/2\mathbb{Z}\). The elements of \(GF(8)\) are represented by: \[ \{0, 1, X, X+1, X^2, X^2+1, X^2+X, X^2+X+1\} \] For instance, multiplication in \(GF(8)\): \[ (X^2 + 1)(X + 1) = X^3 + X^2 + X + 1 \equiv X^2 \pmod{X^3 + X + 1} \]

Implementation:

#![allow(unused)]
fn main() {
impl<M: ModulusValue + 'static, P: IrreduciblePoly<FiniteFieldElement<M>>> Ring
    for ExtendedFieldElement<M, P>
{
    fn add_ref(&self, other: &Self) -> Self {
        Self::new(&self.poly + &other.poly)
    }

    fn mul_ref(&self, other: &Self) -> Self {
        Self::new(&self.poly * &other.poly)
    }

    fn sub_ref(&self, other: &Self) -> Self {
        Self::new(&self.poly - &other.poly)
    }
}
}

Lemma: Schwartz - Zippel Lemma

Let \(\mathbb{F}\) be a field and \(P: F^m \rightarrow \mathbb{F}\) and \(Q: \mathbb{F}^m \rightarrow \mathbb{F}\) be two distinct multivariate polynomials of total degree at most \(n\). For any finite subset \(\mathbb{S} \subseteq \mathbb{F}\), we have:

\begin{align} Pr_{u \sim \mathbb{S}^{m}}[P(u) = Q(u)] \leq \frac{n}{|\mathbb{S}|} \end{align}

, where \(u\) is drawn uniformly at random from \(\mathbb{S}^m\).

Proof TBD

This lemma states that if \(\mathbb{S}\) is sufficiently large and \(n\) is relatively small, the probability that the two different polynomials return the same value for a randomly chosen input is negligibly small. In other words, if we observe \(P(u) = Q(u)\) for a random input \(u\), we can conclude with high probability that \(P\) and \(Q\) are identical polynomials.

Elliptic curve

Definition: Elliptic Curve

An elliptic curve \(E\) over a finite field \(\mathbb{F}_{p}\) is defined by the equation:

\begin{equation} y^2 = x^3 + a x + b \end{equation}

, where \(a, b \in \mathbb{F}_{p}\) and the discriminant \(\Delta_{E} = 4a^3 + 27b^2 \neq 0\).

Implementation:

#![allow(unused)]
fn main() {
pub trait EllipticCurve: Debug + Clone + PartialEq {
    fn get_a() -> BigInt;
    fn get_b() -> BigInt;
}

#[derive(Debug, Clone, PartialEq)]
pub struct EllipticCurvePoint<F: Field, E: EllipticCurve> {
    pub x: Option<F>,
    pub y: Option<F>,
    _phantom: PhantomData<E>,
}
}

Definition: \(\mathbb{F}_{p}\)-Rational Point

An \(\mathbb{F}_{p}\)-rational point on an elliptic curve \(E\) is a point \((x, y)\) where both \(x\) and \(y\) are elements of \(\mathbb{F}_{p}\) and satisfy the curve equation, or the point at infinity \(\mathcal{O}\).

Example: For \(E: y^2 = x^3 + 3x + 4\) over \(\mathbb{F}_7\), the \(\mathbb{F}_{7}\)-rational points are: \(\{(0, 2), (0, 5), (1, 1), (1, 6), (2, 2), (2, 5), (5, 1), (5, 6), \mathcal{O}\}\)

Definition: The point at infinity

The point at infinity denoted \(\mathcal{O}\), is a special point on the elliptic curve that serves as the identity element for the group operation. It can be visualized as the point where all vertical lines on the curve meet.

Implementation:

#![allow(unused)]
fn main() {
impl<F: Field, E: EllipticCurve> EllipticCurvePoint<F, E> {
    pub fn point_at_infinity() -> Self {
        EllipticCurvePoint {
            x: None,
            y: None,
            _phantom: PhantomData,
        }
    }

    pub fn is_point_at_infinity(&self) -> bool {
        self.x.is_none() || self.y.is_none()
    }
}
}

Definition: Addition on Elliptic Curve

For an elliptic curve \(E: y^2 = x^3 + ax + b\), the addition of points \(P\) and \(Q\) to get \(R = P + Q\) is defined as follows:

• If \(P = \mathcal{O}\), \(R = Q\).

• If \(Q = \mathcal{O}\), \(R = P\).

• Otherwise, let \(P = (x_P, y_P), Q = (x_Q, y_Q)\). Then:

  • If \(y_P = -y_Q\), \(R = \mathcal{O}\)
  • If \(y_P \neq -y_Q\), \(R = (x_R = \lambda^2 - x_P - x_Q, y_R = \lambda(x_P - x_R) - y_P)\), where \(\lambda = \) \( \begin{cases} \frac{y_P - y_Q}{x_P - x_Q} \quad &\hbox{If } (x_P \neq x_Q) \\ \frac{3^{2}_{P} + a}{2y_P} \quad &\hbox{Otherwise} \end{cases}\)

Example: On \(E: y^2 = x^3 + 2x + 3\) over \(\mathbb{F}_{7}\), let \(P = (5, 1)\) and \(Q = (4, 4)\). Then, \(P + Q = (0, 5)\), where \(\lambda = \frac{1 - 4}{5 - 4} \equiv 4 \bmod 7\).

Implementation:

#![allow(unused)]
fn main() {
impl<F: Field, E: EllipticCurve> EllipticCurvePoint<F, E> {
    pub fn add_ref(&self, other: &Self) -> Self {
        if self.is_point_at_infinity() {
            return other.clone();
        }
        if other.is_point_at_infinity() {
            return self.clone();
        }

        if self.x == other.x && self.y == other.y {
            return self.double();
        } else if self.x == other.x {
            return Self::point_at_infinity();
        }

        let slope = self.line_slope(&other);
        let x1 = self.x.as_ref().unwrap();
        let y1 = self.y.as_ref().unwrap();
        let x2 = other.x.as_ref().unwrap();
        let y2 = other.y.as_ref().unwrap();

        let new_x = slope.mul_ref(&slope).sub_ref(&x1).sub_ref(&x2);
        let new_y = ((-slope.clone()).mul_ref(&new_x)) + (&slope.mul_ref(&x1).sub_ref(&y1));
        assert!(new_y == -slope.clone() * &new_x + slope.mul_ref(&x2).sub_ref(&y2));

        Self::new(new_x, new_y)
    }
}

impl<F: Field, E: EllipticCurve> Add for EllipticCurvePoint<F, E> {
    type Output = Self;

    fn add(self, other: Self) -> Self {
        self.add_ref(&other)
    }
}
}

Definition: Mordell-Weil Group

The Mordell-Weil group of an elliptic curve \(E\) is the group of rational points on \(E\) under the addition operation defined above.

Example: For \(E: y^2 = x^3 + x + 6\) over \(\mathbb{F}_{11}\), the Mordell-Weil group is the set of all \(\mathbb{F}_{11}\)-rational points on \(E\) with the elliptic curve addition operation.

Definition: Group Order

The group order of an elliptic curve \(E\) over \(\mathbb{F}_{p}\), denoted \(\#E(\mathbb{F}_{p})\), is the number of \(\mathbb{F}_{p}\)-rational points on \(E\), including the point at infinity.

Example: For \(E: y^2 = x^3 + x + 6\) over \(\mathbb{F}_{11}\), \(\#E(\mathbb{F}_{11}) = 13\).

Theorem: Hasse-Weil

Let \(\#E(\mathbb{F}_{p})\) be the group order of the elliptic curve \(E\) over \(\mathbb{F}_{p}\). Then:

\begin{equation} p + 1 - 2 \sqrt{p} \leq \#E \leq p + 1 + 2 \sqrt{p} \end{equation}

Example: For an elliptic curve over \(\mathbb{F}_{23}\), the Hasse-Weil theorem guarantees that:

\begin{equation*} 23 + 1 - 2 \sqrt{23} \simeq 14.42 \#E(\mathbb{F}_{23}) \geq 23 + 1 + 2 \sqrt{23} \simeq 33.58 \end{equation*}

Definition: Point Order

The order of a point \(P\) on an elliptic curve is the smallest positive integer \(n\) such that \(nP = \mathcal{O}\) (where \(nP\) denotes \(P\) added to itself \(n\) times). We also denote the set of points of order \(n\), also called \textit{torsion} group, by

\begin{equation} E[n] = \{P \in E: [n]P = \mathcal{O}\} \end{equation}

Example: On \(E: y^2 = x^3 + 2x + 2\) over \(\mathbb{F}_{17}\), the point \(P = (5, 1)\) has order 18 because \(18P = \mathcal{O}\), and no smaller positive multiple of \(P\) equals \(\mathcal{O}\).

The intuitive view is that if you continue to add points to themselves (doubling, tripling, etc.), the lines drawn between the prior point and the next point will eventually become more vertical. When the line becomes vertical, it does not intersect the elliptic curve at any finite point. In elliptic curve geometry, a vertical line is considered to "intersect" the curve at a special place called the "point at infinity," This point is like a north pole in geographic terms: no matter which direction you go, if the line becomes vertical (reaching infinitely high), it converges to this point.

Definition: Field Extension

Let \(F\) and \(L\) be fields. If \(F \subseteq L\) and the operations of \(F\) are the same as those of \(L\), we call \(L\) a field extension of \(F\). This is denoted as \(L/F\).

A field extension \(L/F\) naturally gives \(L\) the structure of a vector space over \(F\). The dimension of this vector space is called the degree of the extension.

Examples:

• \(\mathbb{C}/\mathbb{R}\) is a field extension with basis \(\{1, i\}\) and degree 2.
• \(\mathbb{R}/\mathbb{Q}\) is an infinite degree extension.
• \(\mathbb{Q}(\sqrt{2})/\mathbb{Q}\) is a degree 2 extension with basis \(\{1, \sqrt{2}\}\).

Definition: Algebraic Extension

A field extension \(L/K\) is called algebraic if every element \(\alpha \in L\) is algebraic over \(K\), i.e., \(\alpha\) is the root of some non-zero polynomial with coefficients in \(K\).

For an algebraic element \(\alpha \in L\) over \(K\), we denote by \(K(\alpha)\) the smallest field containing both \(K\) and \(\alpha\).

Example:

• \(\mathbb{C}/\mathbb{R}\) is algebraic: any \(z = a + bi \in \mathbb{C}\) is a root of \(x^2 - 2ax + (a^2 + b^2) \in \mathbb{R}[x]\).
• \(\mathbb{Q}(\sqrt[3]{2})/\mathbb{Q}\) is algebraic: \(\sqrt[3]{2}\) is a root of \(x^3 - 2 \in \mathbb{Q}[x]\).
• \(\mathbb{R}/\mathbb{Q}\) is not algebraic (a field extension that is not algebraic is called \textit{transcendental}).

Definition: Field of Rational Functions

Let \(K\) be a field and \(X\) be indeterminate. The field of rational functions over \(K\), denoted \(K(X)\), is defined as:

\begin{equation*} K(X) = \left\{ \frac{f(X)}{g(X)} \middle|\ f(X), g(X) \in K[X], g(X) \neq 0 \right\} \end{equation*}

where \(K[X]\) is the ring of polynomials in \(X\) with coefficients in \(K\).

\(K(X)\) can be viewed as the field obtained by adjoining a letter \(X\) to \(K\). This construction generalizes to multiple variables, e.g., \(K(X,Y)\).

The concept of a function field naturally arises in the context of algebraic curves, particularly elliptic curves. Intuitively, the function field encapsulates the algebraic structure of rational functions on the curve.

We first construct the coordinate ring for an elliptic curve \(E: y^2 = x^3 + ax + b\). Consider functions \(X: E \to K\) and \(Y: E \to K\) that extract the \(x\) and \(y\) coordinates, respectively, from an arbitrary point \(P \in E\). These functions generate the polynomial ring \(K[X,Y]\), subject to the relation \(Y^2 = X^3 + aX + b\).

To put it simply, the function field is a field that consists of all functions that determine the value based on the point on the curve.

Definition: Coordinate Ring of an Elliptic Curve

The coordinate ring of an elliptic curve \(E: y^2 = x^3 + ax + b\) over a field \(K\) is defined as: \begin{equation} K[E] = K[X, Y]/(Y^2 - X^3 - aX - b) \end{equation}

In other words, we can view \(K[E]\) as a ring representing all polynomial functions on \(E\). Recall that \(K[X, Y]\) is the polynomial ring in two variables \(X\) and \(Y\) over the field K, meaning that it contains all polynomials in \(X\) and \(Y\) with coefficients from \(K\). Then, the notation \(K[X, Y]/(Y^2 - X^3 - aX - b)\) denotes the quotient ring obtained by taking \(K[X, Y]\) and "modding out" by the ideal \((Y^2 - X^3 - aX - b)\).

Example For example, for an elliptic curve \(E: y^2 = x^3 - x\) over \(\mathbb{Q}\), some elements of the coordinate ring \(\mathbb{Q}[E]\) include:

• Constants: \(3, -2, \frac{1}{7}, \ldots\)
• Linear functions: \(X, Y, 2X+3Y, \ldots\)
• Quadratic functions: \(X^2, XY, Y^2 (= X^3 - X), \ldots\)
• Higher-degree functions: \(X^3, X^2Y, XY^2 (= X^4 - X^2), \ldots\)

Definition: Function Field of an Elliptic Curve

Then, the function field is defined as follows:

Let \(E: y^2 = x^3 + ax + b\) be an elliptic curve over a field \(K\). The function field of \(E\), denoted \(K(E)\), is defined as: \begin{equation} K(E) = \left\{\frac{f}{g} ,\middle|, f, g \in K[E], g \neq 0 \right\} \end{equation} where \(K[E] = K[X, Y]/(Y^2 - X^3 - aX - b)\) is the coordinate ring of \(E\).

\(K(E)\) can be viewed as the field of all rational functions on \(E\).

Definition: Zero/Pole of a Function

Let \(h \in K(E)\) be a non-zero function. A point \(P \in E\) is called a zero of \(h\) if \(h(P) = 0\).

Let \(h \in K(E)\) be a non-zero function. A point \(P \in E\) is called a pole of \(h\) if \(h\) is not defined at \(P\) or, equivalently if \(1/h\) has a zero at \(P\).

Example Consider the elliptic curve \(E: Y^2 = X^3 - X\) over a field \(K\) of characteristic \(\neq 2, 3\). Let \(P_{-1} = (-1, 0)\), \(P_0 = (0, 0)\), and \(P_1 = (1, 0)\) be the points where \(Y = 0\).

• The function \(Y \in K(E)\) has three simple zeros: \(P_{-1}\), \(P_0\), and \(P_1\).
• The function \(X \in K(E)\) has a double zero at \(P_0\) (since \(P_0 = -P_0\)).
• The function \(X - 1 \in K(E)\) has a simple zero at \(P_1\).
• The function \(X^2 - 1 \in K(E)\) has two simple zeros at \(P_{-1}\) and \(P_1\).
• The function \(\frac{Y}{X} \in K(E)\) has a simple zero at \(P_{-1}\) and a simple pole at \(P_0\).

An important property of functions in \(K(E)\) is that they have the same number of zeros and poles when counted with multiplicity. This is a consequence of a more general result known as the Degree-Genus Formula.

Theorem: Degree-Genus Formula for Elliptic Curves

Let \(f \in K(E)\) be a non-zero rational function on an elliptic curve \(E\). Then:

\begin{equation} \sum_{P \in E} ord_{P(f)} = 0 \end{equation}

, where \(ord_{P(f)}\) denotes the order of \(f\) at \(P\), which is positive for zeros and negative for poles.

This theorem implies that the total number of zeros (counting multiplicity) equals the total number of poles for any non-zero function in \(K(E)\).

We now introduce a powerful tool for analyzing functions on elliptic curves: the concept of divisors.

Definition: Divisor of a Function on an Elliptic Curve

Let \(E: Y^2 = X^3 + AX + B\) be an elliptic curve over a field \(K\), and let \(f \in K(E)\) be a non-zero rational function on \(E\). The divisor of \(f\), denoted \(div(f)\), is defined as: \begin{equation} div(f) = \sum_{P \in E} ord_P(f) [P] \end{equation} , where \(ord_P(f)\) is the order of \(f\) at \(P\) (positive for zeros, negative for poles), and the sum is taken over all points \(P \in E\), including the point at infinity. This sum has only finitely many non-zero terms.

Note that this \(\sum_{P \in E}\) is a symbolic summation, and we do not calculate the concrete numerical value of a divisor.

Example Consider the elliptic curve \(E: Y^2 = X^3 - X\) over \(\mathbb{Q}\).

• For \(f = X\), we have \(div(X) = 2[(0,0)] - 2[\mathcal{O}]\).
• For \(g = Y\), we have \(div(Y) = [(1,0)] + [(0,0)] + [(-1,0)] - 3[\mathcal{O}]\).
• For \(h = \frac{X-1}{Y}\), we have \(div(h) = [(1,0)] - [(-1,0)]\).

Definition: Divisor on an Elliptic Curve

The concept of divisors can be extended to the elliptic curve itself:

A divisor \(D\) on an elliptic curve \(E\) is a formal sum \begin{equation} D = \sum_{P \in E} n_P [P] \end{equation} where \(n_P \in \mathbb{Z}\) and \(n_P = 0\) for all but finitely many \(P\).

Example On the curve \(E: Y^2 = X^3 - X\):

• \(D_1 = 3[(0,0)] - 2[(1,1)] - [(2,\sqrt{6})]\) is a divisor.
• \(D_2 = [(1,0)] + [(-1,0)] - 2[\mathcal{O}]\) is a divisor.
• \(D_3 = \sum_{P \in E[2]} [P] - 4[\mathcal{O}]\) is a divisor (where \(E[2]\) are the 2-torsion points).

To quantify the properties of divisors, we introduce two important metrics:

Definition: Degree/Sum of a Divisor

The degree of a divisor \(D = \sum_{P \in E} n_P [P]\) is defined as: \begin{equation} deg(D) = \sum_{P \in E} n_P \end{equation}

The sum of a divisor \(D = \sum_{P \in E} n_P [P]\) is defined as: \begin{equation} Sum(D) = \sum_{P \in E} n_P P \end{equation} where \(n_P P\) denotes the point addition of \(P\) to itself \(n_P\) times in the group law of \(E\).

Example For the divisors in the previous example:

• \(deg(D_1) = 3 - 2 - 1 = 0\)
• \(deg(D_2) = 1 + 1 - 2 = 0\)
• \(deg(D_3) = 4 - 4 = 0\)
• \(Sum(D_2) = (1,0) + (-1,0) - 2\mathcal{O} = \mathcal{O}\) (since \((1,0)\) and \((-1,0)\) are 2-torsion points)

Theorem

The following theorem characterizes divisors of functions and provides a criterion for when a divisor is the divisor of a function:

Let \(E\) be an elliptic curve over a field \(K\).

• If \(f, f' \in K(E)\) are non-zero rational functions on \(E\) with \(div(f) = div(f')\), then there exists a non-zero constant \(c \in K^*\) such that \(f = cf'\).
• A divisor \(D\) on \(E\) is the divisor of a rational function on \(E\) if and only if \(deg(D) = 0\) and \(Sum(D) = \mathcal{O}\).

Example On \(E: Y^2 = X^3 - X\):

• The function \(f = \frac{Y}{X}\) has \(div(f) = [(1,0)] + [(-1,0)] - 2[(0,0)]\). Note that \(deg(div(f)) = 0\) and \(Sum(div(f)) = (1,0) + (-1,0) - 2(0,0) = \mathcal{O}\).
• The divisor \(D = 2[(1,1)] - [(2,\sqrt{6})] - [(0,0)]\) has \(deg(D) = 0\), but \(Sum(D) \neq \mathcal{O}\). Therefore, \(D\) is not the divisor of any rational function on \(E\).

Pairing

Definition: Pairing

Let \(G_1\) and \(G_2\) be cyclic groups under addition, both of prime order \(p\), with generators \(P\) and \(Q\) respectively:

\begin{align} G_1 &= \{0, P, 2P, ..., (p-1)P\} \ G_2 &= \{0, Q, 2Q, ..., (p-1)Q\} \end{align}

Let \(G_T\) be a cyclic group under multiplication, also of order \(p\). A pairing is a map \(e: G_1 \times G_2 \rightarrow G_T\) that satisfies the following bilinear property:

\begin{equation} e(aP, bQ) = e(P, Q)^{ab} \end{equation} for all \(a, b \in \mathbb{Z}_p\).

Imagine \(G_1\) represents length, \(G_2\) represents width, and \(G_T\) represents area. The pairing function \(e\) is like calculating the area: If you double the length and triple the width, the area becomes six times larger: \(e(2P, 3Q) = e(P, Q)^{6}\)

Definition: The Weil Pairing

The Weil pairing is one of the bilinear pairings for elliptic curves. We begin with its formal definition.

Let \(E\) be an elliptic curve and \(n\) be a positive integer. For points \(P, Q \in E[n]\), where \(E[n]\) denotes the \(n\)-torsion subgroup of \(E\), we define the Weil pairing \(e_n(P, Q)\) as follows:

Let \(f_P\) and \(f_Q\) be rational functions on \(E\) satisfying: \begin{align} div(f_P) &= n[P] - n[\mathcal{O}] \ div(f_Q) &= n[Q] - n[\mathcal{O}] \end{align}

Then, for an arbitrary point \(S \in E\) such that \(S \notin \{\mathcal{O}, P, -Q, P-Q\}\), the Weil pairing is given by:

\begin{equation} e_n(P, Q) = \frac{f_P(Q + S)}{f_P(S)} /\ \frac{f_Q(P - S)}{f_Q(-S)} \end{equation}

We introduce a crucial theorem about a specific rational function on elliptic curves to construct the functions required for the Weil pairing.

Theorem

Let \(E\) be an elliptic curve over a field \(K\), and let \(P = (x_P, y_P)\) and \(Q = (x_Q, y_Q)\) be non-zero points on \(E\). Define \(\lambda\) as:

\begin{equation} \lambda = \begin{cases} \hbox{slope of the line through \(P\) and \(Q\)} &\quad \hbox{if \(P \neq Q\)} \\ \hbox{slope of the tangent line to \(E\) at \(P\)} &\quad \hbox{if \(P = Q\)} \\ \infty &\quad \hbox{if the line is vertical} \end{cases} \end{equation}

Then, the function \(g_{P,Q}: E \to K\) defined by: \begin{equation} g_{P,Q} = \begin{cases} \frac{y - y_P - \lambda(x - x_P)}{x + x_P + x_Q - \lambda^2} &\quad \hbox{if } \lambda \neq \infty \\ x - x_P &\quad \hbox{if } \lambda = \infty \end{cases} \end{equation} has the following divisor:

\begin{equation} div(g_{P,Q}) = [P] + [Q] - [P + Q] - [\mathcal{O}] \end{equation}

Proof: We consider two cases based on the value of \(\lambda\).

Case 1: \(\lambda \neq \infty\)

Let \(y = \lambda x + v\) be the line through \(P\) and \(Q\) (or the tangent line at \(P\) if \(P = Q\)). This line intersects \(E\) at three points: \(P\), \(Q\), and \(-P-Q\). Thus, \begin{equation} div(y - \lambda x - v) = [P] + [Q] + [-P - Q] - 3[\mathcal{O}] \end{equation} Vertical lines intersect \(E\) at points and their negatives, so: \begin{equation} div(x - x_{P+Q}) = [P + Q] + [-P - Q] - 2[\mathcal{O}] \end{equation} It follows that \(g_{P,Q} = \frac{y - \lambda x - v}{x - x_{P+Q}}\) has the desired divisor.

Case 2: \(\lambda = \infty\)

In this case, \(P + Q = \mathcal{O}\), so we want \(g_{P,Q}\) to have divisor \([P] + [-P] - 2[\mathcal{O}]\). The function \(x - x_P\) has this divisor. \end{proof}

Theorem: Miller's Algorithm

Let \(m \geq 1\) and write its binary expansion as: \begin{equation} m = m_0 + m_1 \cdot 2 + m_2 \cdot 2^2 + \cdots + m_{n-1} \cdot 2^{n-1} \end{equation} where \(m_i \in \{0, 1\}\) and \(m_{n-1} \neq 0\).

The following algorithm, using the function \(g_{P,Q}\) defined in the previous theorem, returns a function \(f_P\) whose divisor satisfies:

\begin{equation} div(f_P) = m[P] - m[P] - (m - 1)[\mathcal{O}] \end{equation}

===========================

Miller's Algorithm

1. Set \(T = P\) and \(f = 1\)
2. For \(i \gets n-2 \cdots 0\) do
3.     Set \(f = f^2 \cdot g_{T, T}\)
4.     Set \(T = 2T\)
5.     If \(m_i = 1\) then
6.         Set \(f = f \cdot g_{T, P}\)
7.         Set \(T = T + P\)
8.     End if
9. End for
10. Return \(f\)

===========================

Proof: TBD

Implementation:

#![allow(unused)]
fn main() {
pub fn get_lambda<F: Field, E: EllipticCurve>(
    p: &EllipticCurvePoint<F, E>,
    q: &EllipticCurvePoint<F, E>,
    r: &EllipticCurvePoint<F, E>,
) -> F {
    let p_x = p.x.as_ref().unwrap();
    let p_y = p.y.as_ref().unwrap();
    let q_x = q.x.as_ref().unwrap();
    // let q_y = q.y.clone().unwrap();
    let r_x = r.x.as_ref().unwrap();
    let r_y = r.y.as_ref().unwrap();

    if (p == q && *p_y == F::zero()) || (p != q && *p_x == *q_x) {
        return r_x.sub_ref(&p_x);
    }
    let slope = p.line_slope(&q);
    let numerator = (r_y.sub_ref(&p_y)).sub_ref(&slope.mul_ref(&(r_x.sub_ref(&p_x))));
    let denominator = r_x
        .add_ref(&p_x)
        .add_ref(&q_x)
        .sub_ref(&slope.mul_ref(&slope));
    return numerator / denominator;
}

pub fn miller<F: Field, E: EllipticCurve>(
    p: &EllipticCurvePoint<F, E>,
    q: &EllipticCurvePoint<F, E>,
    m: &BigInt,
) -> (F, EllipticCurvePoint<F, E>) {
    if p == q {
        return (F::one(), p.clone());
    }

    let mut f = F::one();
    let mut t = p.clone();

    for i in (0..(m.bits() - 1)).rev() {
        f = (f.mul_ref(&f)) * (get_lambda(&t, &t, &q));
        t = t.add_ref(&t);
        if m.bit(i) {
            f = f * (get_lambda(&t, &p, &q));
            t = t.add_ref(&p);
        }
    }

    (f, t)
}
}

Assumptions

Assumption: Discrete Logarithm Problem

Let \(G\) be a finite cyclic group of order \(n\), with \(\gamma\) as its generator and \(1\) as the identity element. For any element \(\alpha \in G\), there is currently no known efficient (polynomial-time) algorithm to compute the smallest non-negative integer \(x\) such that \(\alpha = \gamma^{x}\).

The Discrete Logarithm Problem can be thought of as a one-way function. It's easy to compute \(g^{x}\) given \(g\) and \(x\), but it's computationally difficult to find \(x\) given \(g\) and \(g^{x}\).

Assumption: Elliptic Curve Discrete Logarithm Problem

Let \(E\) be an elliptic curve defined over a finite field \(\mathbb{F}_q\), where \(q\) is a prime power. Let \(P\) be a point on \(E\) of point order \(n\), and let \(\langle P \rangle\) be the cyclic subgroup of \(E\) generated by \(P\). For any element \(Q \in \langle P \rangle\), there is currently no known efficient (polynomial-time) algorithm to compute the unique integer \(k\), \(0 \leq k < n\), such that \(Q = kP\).

This assumption is an elliptic curve version of the Discrete Logarithm Problem.

Assumption: Knowledge of Exponent Assumption

Let \(G\) be a cyclic group of prime order \(q\) with generator \(g \in G\). For any probabilistic polynomial-time algorithm \(\mathcal{A}\) that outputs:

\begin{equation} \mathcal{A}(g, g^x) = (h, h') \quad s.t. \quad h' = h^x \end{equation} , there exists an efficient extractor \(\mathcal{E}\) such that: \begin{equation} \mathcal{E}(\mathcal{A}, g, g^x) = y \quad s.t. \quad h = g^y \end{equation}

This assumption states that if \(\mathcal{A}\) can compute the pair \((g^y, g^{xy})\) from \((g, g^x)\), then \(\mathcal{A}\) must "know" the value \(y\), in the sense that \(\mathcal{E}\) can extract \(y\) from \(\mathcal{A}\)'s internal state. The Knowledge of Exponent Assumption is useful for constructing verifiable exponential calculation algorithms. Consider a scenario where Alice has a secret value \(a\), and Bob has a secret value \(b\). Bob wants to obtain \(g^{ab}\). This can be achieved through the following protocol:

Verifiable Exponential Calculation Algorithm

1. Bob sends \((g, g'=g^{b})\) to Alice
2. Alice sends \((h=g^{a}, h'=g'^{a})\) to Bob
3. Bob checks \(h^{b} = h'\).

Thanks to the Discrete Logarithm Assumption and the Knowledge of Exponent Assumption, the following properties hold:

• Bob cannot derive \(a\) from \((h, h')\).
• Alice cannot derive \(b\) from \((g, g')\).
• Alice cannot generate \((t, t')\) such that \(t \neq h\) and \(t^{b} = t'\).
• If \(h^{b} = h'\), Bob can conclude that \(h\) is the power of \(g\).

Basics of zk-SNARK

Arithmetization

The ultimate goal of Zero-Knowledge Proofs (ZKP) is to allow the prover to demonstrate their knowledge to the verifier without revealing any additional information. This knowledge typically involves solving complex problems, such as finding a secret input value that corresponds to a given public hash. ZKP protocols usually convert these statements into polynomial constraints. This process is often called arithmetization.

To make the protocol flexible, we need to encode this knowledge in a specific format, and one common approach is using Boolean circuits. It's well-known that problems in P (those solvable in polynomial time) and NP (those where the solution can be verified in polynomial time) can be represented as Boolean circuits. This means adopting Boolean circuits allows us to handle both P and NP problems.

However, Boolean circuits are often large and inefficient. Even a simple operation, like adding two 256-bit integers, can require hundreds of Boolean operators. In contrast, arithmetic circuits—essentially systems of equations involving addition, multiplication, and equality—offer a much more compact representation. Additionally, any Boolean circuit can be converted into an arithmetic circuit. For instance, the Boolean expression \(z = x \land y\) can be represented as \(x(x-1) = 0\), \(y(y-1) = 0\), and \(z = xy\) in an arithmetic circuit. Furthermore, as we'll see in this section, converting arithmetic circuits into polynomial constraints allows for much faster evaluation.

Rank-1 Constraint System (R1CS)

There are many formats to represent arithmetic circuits, and one of the most popular ones is R1CS (Rank-1 Constraint System), which represents arithmetic circuits as a set of equality constraints, each involving only one multiplication. In an arithmetic circuit, we call the concrete values assigned to the variables within the constraints witness. We first provide the formal definition of R1CS as follows:

Definition: R1CS

An R1CS structure \(\mathcal{S}\) consists of:

• Size bounds \(m, d, \ell \in \mathbb{N}\) where \(d > \ell\)
• Three matrices \(O, L, R \in \mathbb{F}^{m \times d}\) with at most \(\Omega(\max(m, d))\) non-zero entries in total

An R1CS instance includes a public input \(p \in \mathbb{F}^\ell\), while an R1CS witness is a vector \(w \in \mathbb{F}^{d - \ell - 1}\). A structure-instance tuple \((S, p)\) is satisfied by a witness \(w\) if: \begin{equation} (L \cdot v) \circ (R \cdot v) - O \cdot v = \mathbf{0} \end{equation} where \(v = (1, w, p) \in \mathbb{F}^d\), \(\cdot\) denotes matrix-vector multiplication, and \(\circ\) is the Hadamard product.

The intuitive interpretation of each matrix is as follows:

• \(L\): Encodes the left input of each gate
• \(R\): Encodes the right input of each gate
• \(O\): Encodes the output of each gate
• The leading 1 in the assignment vector allows for constant terms

Single Multiplication

Let's consider a simple example where we want to prove \(z = x \cdot y\), with \(z = 3690\), \(x = 82\), and \(y = 45\).

• Assignment vector: \((1, z, x, y) = (1, 3690, 82, 45)\)
• Number of witnesses: \(m = 4\)
• Number of constraints: \(d = 1\)

The R1CS constraint for \(z = x \cdot y\) is satisfied when:

\begin{align*} &(\begin{bmatrix} 0 & 0 & 1 & 0 \end{bmatrix} \cdot v) \circ (\begin{bmatrix} 0 & 0 & 0 & 1 \end{bmatrix} \cdot v) - \begin{bmatrix} 0 & 1 & 0 & 0 \end{bmatrix} \cdot v \\ =&(\begin{bmatrix} 0 & 0 & 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} 1 \\ 3690 \\ 82 \\ 45 \end{bmatrix}) \circ (\begin{bmatrix} 0 & 0 & 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 \\ 3690 \\ 82 \\ 45 \end{bmatrix}) - \begin{bmatrix} 0 & 1 & 0 & 0 \end{bmatrix} \cdot \begin{bmatrix} 1 \\ 3690 \\ 82 \\ 45 \end{bmatrix} \\ =& 82 \cdot 45 - 3690 \\ =& 3690 - 3690 \\ =& 0 \end{align*}

This example demonstrates how R1CS encodes a simple multiplication constraint:

• \(L = \begin{bmatrix} 0 & 0 & 1 & 0 \end{bmatrix}\) selects \(x\) (left input)
• \(R = \begin{bmatrix} 0 & 0 & 0 & 1 \end{bmatrix}\) selects \(y\) (right input)
• \(O = \begin{bmatrix} 0 & 1 & 0 & 0 \end{bmatrix}\) selects \(z\) (output)

Multiple Constraints

Let's examine a more complex example: \(r = a \cdot b \cdot c \cdot d\). Since R1CS requires that each constraint contain only one multiplication, we need to break this down into multiple constraints:

\begin{align*} z_1 &= a \cdot b \\ z_2 &= c \cdot d \\ r &= z_1 \cdot z_2 \end{align*}

Note that alternative representations are possible, such as \(z_1 = ab, z_2 = z_1c, r = z_2d\). In this example, we use 7 variables \((r, a, b, c, d, z_1, z_2)\), so the dimension of the assignment vector will be \(m = 8\) (including the constant 1). We have three constraints, so \(n = 3\). To construct the matrices \(L\), \(R\), and \(O\), we can interpret the constraints as linear combinations:

\begin{align*} z_1 &= (0 \cdot 1 + 0 \cdot r + 1 \cdot v + 0 \cdot b + 0 \cdot c + 0 \cdot d + 0 \cdot z_1 + 0 \cdot z_2) \cdot b \\ z_2 &= (0 \cdot 1 + 0 \cdot r + 0 \cdot v + 0 \cdot b + 1 \cdot c + 0 \cdot d + 0 \cdot z_1 + 0 \cdot z_2) \cdot d \\ r &= (0 \cdot 1 + 0 \cdot r + 0 \cdot v + 0 \cdot b + 0 \cdot c + 0 \cdot d + 1 \cdot z_1 + 0 \cdot z_2) \cdot z_2 \end{align*}

Thus, we can construct \(L\), \(R\), and \(O\) as follows:

\begin{equation*} L = \begin{bmatrix} 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{bmatrix} \end{equation*} \begin{equation*} R = \begin{bmatrix} 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix} \end{equation*} \begin{equation*} O = \begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix} \end{equation*}

Where the columns in each matrix correspond to \((1, r, a, b, c, d, z_1, z_2)\).

Addition with a Constant

Let's examine the case \(z = x \cdot y + 3\). We can represent this as \(-3 + z = x \cdot y\). For the assignment vector \((1, z, x, y)\), we have:

\begin{align*} L &= \begin{bmatrix} 0 & 0 & 1 & 0 \end{bmatrix} \\ R &= \begin{bmatrix} 0 & 0 & 0 & 1 \end{bmatrix} \\ O &= \begin{bmatrix} -3 & 1 & 0 & 0 \end{bmatrix} \end{align*}

Note that the constant 3 appears in the \(O\) matrix with a negative sign, effectively moving it to the left side of the equation

Multiplication with a Constant

Now, let's consider \(z = 3x^2 + y\). The requirement of "one multiplication per constraint" doesn't apply to multiplication with a constant, as we can treat it as repeated addition.

\begin{align*} L &= \begin{bmatrix} 0 & 0 & 3 & 0 \end{bmatrix} \\ R &= \begin{bmatrix} 0 & 0 & 1 & 0 \end{bmatrix} \\ O &= \begin{bmatrix} 0 & 1 & 0 & -1 \end{bmatrix} \end{align*}

Implementation:

#![allow(unused)]
fn main() {
fn dot<F: Field>(a: &Vec<F>, b: &Vec<F>) -> F {
    let mut result = F::zero();
    for (a_i, b_i) in a.iter().zip(b.iter()) {
        result = result + a_i.clone() * b_i.clone();
    }
    result
}

#[derive(Debug, Clone)]
pub struct R1CS<F: Field> {
    pub left: Vec<Vec<F>>,
    pub right: Vec<Vec<F>>,
    pub out: Vec<Vec<F>>,
    pub m: usize,
    pub d: usize,
}

impl<F: Field> R1CS<F> {
    pub fn new(left: Vec<Vec<F>>, right: Vec<Vec<F>>, out: Vec<Vec<F>>) -> Self {
        let d = left.len();
        let m = if d == 0 { 0 } else { left[0].len() };
        R1CS {
            left,
            right,
            out,
            m,
            d,
        }
    }

    pub fn is_satisfied(&self, a: &Vec<F>) -> bool {
        let zero = F::zero();
        self.left
            .iter()
            .zip(self.right.iter())
            .zip(self.out.iter())
            .all(|((l, r), o)| dot(&l, &a) * dot(&r, &a) - dot(&o, &a) == zero)
    }
}
}

Quadratic Arithmetic Program (QAP)

Recall that the prover aims to demonstrate knowledge of a witness \(w\) without revealing it. This is equivalent to knowing a vector \(a\) that satisfies \((L \cdot v) \circ (R \cdot v) = O \cdot v\), where \(\circ\) denotes the Hadamard (element-wise) product. However, evaluating this equivalence directly requires \(\Omega(d)\) operations, where \(d\) is the number of rows. To improve efficiency, we can convert this matrix comparison to a polynomial comparison, leveraging the Schwartz-Zippel Lemma, which allows us to check polynomial equality with \(\Omega(1)\) evaluations.

Equivalence of Matrices

Let's consider a simpler example to illustrate this concept. Suppose we want to test the equivalence \(Av = Bu\), where:

\begin{align*} A = \begin{bmatrix} 2 & 5 \\ 3 & 1 \\ \end{bmatrix}, B = \begin{bmatrix} 4 & 1 \\ 2 & 3 \\ \end{bmatrix}, v = \begin{bmatrix} 3 \\ 1 \end{bmatrix}, u = \begin{bmatrix} 2 \\ 2 \end{bmatrix} \end{align*}

The equivalence check can be represented as:

\begin{equation*} \begin{bmatrix} 2 \\ 3 \end{bmatrix} \cdot 3 + \begin{bmatrix} 5 \\ 1 \end{bmatrix} \cdot 1 = \begin{bmatrix} 4 \\ 2 \end{bmatrix} \cdot 2 + \begin{bmatrix} 1 \\ 3 \end{bmatrix} \cdot 2 \end{equation*}

This matrix-vector equality check is equivalent to the following polynomial equality check:

\begin{equation*} 3 \cdot \lambda([(1, 2), (2, 3)]) + 1 \cdot \lambda([(1, 5), (2, 1)]) = 2 \cdot \lambda([(1, 4), (2, 2)]) + 2 \cdot \lambda([(1, 1), (2, 3)]) \end{equation*}

where \(\lambda\) denotes Lagrange Interpolation. In \(\mathbb{F}_{11}\) (field with 11 elements), we have:

\begin{align*} \lambda([(1, 2), (2, 3)]) &= x + 1 \\ \lambda([(1, 5), (2, 1)]) &= 7x + 9 \\ \lambda([(1, 4), (2, 2)]) &= 9x + 6 \\ \lambda([(1, 1), (2, 3)]) &= 2x + 10 \end{align*}

The Schwartz-Zippel Lemma states that we need only one evaluation at a random point to check the equivalence of polynomials with high probability.

Back to R1CS

Let's thinks about how we can leverage the above method for the verification of R1CS. First, we can construct the interpolated polynomials for \(L \cdot v\), \(R \cdot v\), and \(O \cdot v\), denoted as \(\ell(x)\), \(r(x)\), and \(o(x)\), repectively, as follows:

\begin{align*} \ell(x) &= \sum^{d}_{i=1} v_i \ell_i(x) \quad \hbox{,where } \ell_i(x) := \lambda([(1, L_i,_1), (2, L_i,_2), \cdots,(m, L_i,_m)]) \\ r(x) &= \sum^{d} _{i=1} v_i r_i(x) \quad \hbox{,where } r_i(x) := \lambda([(1, R_i,_1), (2, R_i,_2), \cdots,(m, R_i,_m)]) \\ o(x) &= \sum^{d} _{i=1} v_i o_i(x) \quad \hbox{,where } o_i(x) := \lambda([(1, O_i,_1), (2, O_i,_2), \cdots,(m, O_i,_m)]) \end{align*}

However, the homomorphic property for multiplication doesn't hold for Lagrange Interpolation. While \(\ell(x)\), \(r(x)\), and \(o(x)\) are of degree at most \(m-1\), \(\ell(x) \cdot r(x)\) is of degree at most \(2m-2\). Thus, we don't have \(\ell(x) \cdot r(x) = o(x)\).

To address this discrepancy, we introduce a degree \(m\) polynomial \(t(x) = \prod_{i=1}^{m} (x - i)\). Given the constituion of the interpolated equations, we have that \(\forall{x} \in \{1,\cdots, d\}\) \(\ell(x) \cdot r(x) = o(x)\). This implies the following:

\begin{equation} \forall{x} \in \{1,\cdots, m\} \quad \ell(x) \cdot r(x) - o(x) = 0 \end{equation}

Thus, we can factorize \(\ell(x) \cdot r(x) - o(x)\) into the product of \(t(x)\) and an appripriate polynomial \(h(x)\) such that \(\ell(x) \cdot r(x) - o(x) = t(x)h(x)\).

Then, we can then rewrite the equation as:

\begin{equation} \ell(x) \cdot r(x) = o(x) + h(x) \cdot t(x) \end{equation}

This formulation allows us to maintain the desired polynomial relationships while accounting for the degree differences.

Implementation:

#![allow(unused)]
fn main() {
#[derive(Debug, Clone)]
pub struct QAP<'a, F: Field> {
    pub r1cs: &'a R1CS<F>,
    pub t: Polynomial<F>,
}

impl<'a, F: Field> QAP<'a, F> {
    fn new(r1cs: &'a R1CS<F>) -> Self {
        QAP {
            r1cs: r1cs,
            t: Polynomial::<F>::from_monomials(
                &(1..=r1cs.d).map(|i| F::from_value(i)).collect::<Vec<F>>(),
            ),
        }
    }

    fn generate_polynomials(&self, a: &Vec<F>) -> (Polynomial<F>, Polynomial<F>, Polynomial<F>) {
        let left_dot_products = self
            .r1cs
            .left
            .iter()
            .map(|v| dot(&v, &a))
            .collect::<Vec<F>>();
        let right_dot_products = self
            .r1cs
            .right
            .iter()
            .map(|v| dot(&v, &a))
            .collect::<Vec<F>>();
        let out_dot_products = self
            .r1cs
            .out
            .iter()
            .map(|v| dot(&v, &a))
            .collect::<Vec<F>>();

        let x = (1..=self.r1cs.m)
            .map(|i| F::from_value(i))
            .collect::<Vec<F>>();
        let left_interpolated_polynomial = Polynomial::<F>::interpolate(&x, &left_dot_products);
        let right_interpolated_polynomial = Polynomial::<F>::interpolate(&x, &right_dot_products);
        let out_interpolated_polynomial = Polynomial::<F>::interpolate(&x, &out_dot_products);
        (
            left_interpolated_polynomial,
            right_interpolated_polynomial,
            out_interpolated_polynomial,
        )
    }
}
}

Proving Single Polynomial

Before dealing with all of \(\ell(x)\), \(r(x)\), and \(o(x)\) at once, we design a protocol that allows the Prover \(\mathcal{A}\) to convince the Verifier \(\mathcal{B}\) that \(\mathcal{A}\) knows a specific polynomial. Let's denote this polynomial of degree \(n\) with coefficients in a finite field as:

\begin{equation} P(x) = c_0 + c_1 x + c_2 x^{2} + \cdots c_n x^{n} \end{equation}

Assume \(P(x)\) has \(n\) roots, \(a_1, a_2, \ldots, a_n \in \mathbb{F}\), such that \(P(x) = (x - a_1)(x - a_2)\cdots(x - a_n)\). The Verifier \(\mathcal{B}\) knows \(m < n\) roots of \(P(x)\), namely \(a_1, a_2, \ldots, a_m\). Let \(T(x) = (x - a_1)(x - a_2)\cdots(x - a_m)\). Note that the Prover also knows \(T(x)\).

The Prover's objective is to convince the Verifier that \(\mathcal{A}\) knows a polynomial \(H(x) = \frac{P(x)}{T(x)}\).

Naive Approach

The simplest approach to prove that \(\mathcal{A}\) knows \(H(x)\) is as follows:

Protocol:

• \(\mathcal{B}\) sends all possible values in \(\mathbb{F}\) to \(\mathcal{A}\).
• \(\mathcal{A}\) computes and sends all possible outputs of \(H(x)\) and \(P(x)\).
• \(\mathcal{B}\) checks whether \(H(a)T(a) = P(a)\) holds for any \(a\) in \(\mathbb{F}\).

This protocol is highly inefficient, requiring \(\mathcal{O}(|\mathbb{F}|)\) evaluations and communications.

Implementation:

#![allow(unused)]
fn main() {
pub struct Prover<F: Field> {
    pub p: Polynomial<F>,
    pub t: Polynomial<F>,
    pub h: Polynomial<F>,
}

pub struct Verifier<F: Field> {
    pub t: Polynomial<F>,
    pub known_roots: Vec<F>,
}

impl<F: Field> Prover<F> {
    pub fn new(p: Polynomial<F>, t: Polynomial<F>) -> Self {
        let h = p.clone() / t.clone();
        Prover { p, t, h }
    }

    pub fn compute_all_values(&self, modulus: i128) -> (HashMap<F, F>, HashMap<F, F>) {
        let mut h_values = HashMap::new();
        let mut p_values = HashMap::new();

        for i in 0..modulus {
            let x = F::from_value(i);
            h_values.insert(x.clone(), self.h.eval(&x));
            p_values.insert(x.clone(), self.p.eval(&x));
        }

        (h_values, p_values)
    }
}

impl<F: Field> Verifier<F> {
    pub fn new(known_roots: Vec<F>) -> Self {
        let t = Polynomial::from_monomials(&known_roots);
        Verifier { t, known_roots }
    }

    pub fn verify(&self, h_values: &HashMap<F, F>, p_values: &HashMap<F, F>) -> bool {
        for (x, h_x) in h_values {
            let t_x = self.t.eval(x);
            let p_x = p_values.get(x).unwrap();
            if h_x.clone() * t_x != *p_x {
                return false;
            }
        }
        true
    }
}

pub fn naive_protocol<F: Field>(prover: &Prover<F>, verifier: &Verifier<F>, modulus: i128) -> bool {
    // Step 1: Verifier sends all possible values (implicitly done by Prover computing all values)

    // Step 2: Prover computes and sends all possible outputs
    let (h_values, p_values) = prover.compute_all_values(modulus);

    // Step 3: Verifier checks whether H(a)T(a) = P(a) holds for any a in F
    verifier.verify(&h_values, &p_values)
}
}

\(+\) Schwartz-Zippel Lemma

Instead of evaluating polynomials at all values in \(\mathbb{F}\), we can leverage the Schwartz-Zippel Lemma: if \(H(s) = \frac{P(s)}{T(s)}\) or equivalently \(H(s)T(s) = P(s)\) for a random element \(s\), we can conclude that \(H(x) = \frac{P(x)}{T(x)}\) with high probability. Thus, the Prover \(\mathcal{A}\) only needs to send evaluations of \(P(s)\) and \(H(s)\) for a random input \(s\) received from \(\mathcal{B}\).

Protocol:

• \(\mathcal{B}\) draws random \(s\) from \(\mathbb{F}\) and sends it to \(\mathcal{A}\).
• \(\mathcal{A}\) computes \(h = H(s)\) and \(p = P(s)\) and send them to \(\mathcal{B}\).
• \(\mathcal{B}\) checks whether \(p = t h\), where \(t\) denotes \(T(s)\).

This protocol is efficient, requiring only a constant number of evaluations and communications.

Implementation:

#![allow(unused)]
fn main() {
pub struct Prover<F: Field> {
    pub p: Polynomial<F>,
    pub t: Polynomial<F>,
    pub h: Polynomial<F>,
}

pub struct Verifier<F: Field> {
    pub t: Polynomial<F>,
}

impl<F: Field> Prover<F> {
    pub fn new(p: Polynomial<F>, t: Polynomial<F>) -> Self {
        let h = p.clone() / t.clone();
        Prover { p, t, h }
    }

    pub fn compute_values(&self, s: &F) -> (F, F) {
        let h_s = self.h.eval(s);
        let p_s = self.p.eval(s);
        (h_s, p_s)
    }
}

impl<F: Field> Verifier<F> {
    pub fn new(t: Polynomial<F>) -> Self {
        Verifier { t }
    }

    pub fn generate_challenge(&self) -> F {
        F::random_element(&[])
    }

    pub fn verify(&self, s: &F, h: &F, p: &F) -> bool {
        let t_s = self.t.eval(s);
        h.clone() * t_s == *p
    }
}

pub fn schwartz_zippel_protocol<F: Field>(prover: &Prover<F>, verifier: &Verifier<F>) -> bool {
    // Step 1: Verifier generates a random challenge
    let s = verifier.generate_challenge();

    // Step 2: Prover computes and sends h and p
    let (h, p) = prover.compute_values(&s);

    // Step 3: Verifier checks whether p = t * h
    verifier.verify(&s, &h, &p)
}
}

Vulnerability:

However, it is vulnerable to a malicious prover who could send an arbitrary value \(h'\) and the corresponding \(p'\) such that \(p' = h't\).

#![allow(unused)]
fn main() {
// Simulating a malicious prover
pub struct MaliciousProver<F: Field> {
    t: Polynomial<F>,
}

impl<F: Field> MaliciousProver<F> {
    pub fn new(t: Polynomial<F>) -> Self {
        MaliciousProver { t }
    }

    pub fn compute_malicious_values(&self, s: &F) -> (F, F) {
        let h_prime = F::random_element(&[]);
        let t_s = self.t.eval(s);
        let p_prime = h_prime.clone() * t_s;
        (h_prime, p_prime)
    }
}

pub fn malicious_schwartz_zippel_protocol<F: Field>(
    prover: &MaliciousProver<F>,
    verifier: &Verifier<F>,
) -> bool {
    // Step 1: Verifier generates a random challenge
    let s = verifier.generate_challenge();

    // Step 2: Malicious Prover computes and sends h' and p'
    let (h_prime, p_prime) = prover.compute_malicious_values(&s);

    // Step 3: Verifier checks whether p' = t * h'
    verifier.verify(&s, &h_prime, &p_prime)
}

}

\(+\) Discrete Logarithm Assumption

To address this vulnerability, the Verifier must hide the randomly chosen input \(s\) from the Prover. This can be achieved using the discrete logarithm assumption: it is computationally hard to determine \(s\) from \(\alpha\), where \(\alpha = g^s \bmod p\). Thus, it's safe for the Verifier to send \(\alpha\), as the Prover cannot easily derive \(s\) from it.

An interesting property of polynomial exponentiation is:

\begin{align} g^{P(x)} &= g^{c_0 + c_1 x + c_2 x^{2} + \cdots c_n x^{n}} = g^{c_0} (g^{x})^{c_1} (g^{(x^2)})^{c_2} \cdots (g^{(x^n)})^{c_n} \end{align}

Instead of sending \(s\), the Verifier can send \(g\) and \(\alpha_{i} = g^{(s^i)}\) for \(i = 1, \cdots n\). BE CAREFUL THAT \(g^{(s^i)} \neq (g^s)^i\). The Prover can still evaluate \(g^p = g^{P(s)}\) using these powers of \(g\):

\begin{equation} g^{p} = g^{P(s)} = g^{c_0} \alpha_{1}^{c_1} (\alpha_{2})^{c_2} \cdots (\alpha_{n})^{c_n} \end{equation}

Similarly, the Prover can evaluate \(g^h = g^{H(s)}\). The Verifier can then check \(p = ht \iff g^p = (g^h)^t\).

Protocol:

• \(\mathcal{B}\) randomly draw \(s\) from \(\mathbb{F}\).
• \(\mathcal{B}\) computes and sends \(\{\alpha, \alpha_2, ..., \alpha_{n}\}\), where \(\alpha_i= g^{(s^{i})}\).
• \(\mathcal{A}\) computes and sends \(u = g^{p}\) and \(v = g^{h}\).
• \(\mathcal{B}\) checks whether \(u = v^{t}\).

This approach prevents the Prover from obtaining \(s\) or \(t = T(s)\), making it impossible to send fake \((h', p')\) such that \(p' = h't\).

#![allow(unused)]
fn main() {
pub struct Prover<F: Field> {
    pub p: Polynomial<F>,
    pub t: Polynomial<F>,
    pub h: Polynomial<F>,
}

pub struct Verifier<F: Field> {
    t: Polynomial<F>,
    s: F,
    g: F,
}

impl<F: Field> Prover<F> {
    pub fn new(p: Polynomial<F>, t: Polynomial<F>) -> Self {
        let h = p.clone() / t.clone();
        Prover { p, t, h }
    }

    pub fn compute_values(&self, alpha_powers: &[F]) -> (F, F) {
        let g_p = self.p.eval_with_powers(alpha_powers);
        let g_h = self.h.eval_with_powers(alpha_powers);
        (g_p, g_h)
    }
}

impl<F: Field> Verifier<F> {
    pub fn new(t: Polynomial<F>, generator: i128) -> Self {
        let mut rng = rand::thread_rng();
        let s = F::from_value(rng.gen_bigint_range(
            &BigInt::zero(),
            &BigInt::from(std::u64::MAX),
        ));
        let g = F::from_value(generator);
        Verifier { t, s, g }
    }

    pub fn generate_challenge(&self, max_degree: usize) -> Vec<F> {
        let mut alpha_powers = vec![];
        for i in 0..(max_degree + 1) {
            alpha_powers.push(
                self.g
                    .pow(self.s.clone().pow(i.to_bigint().unwrap()).get_value()),
            );
        }
        alpha_powers
    }

    pub fn verify(&self, u: &F, v: &F) -> bool {
        let t_s = self.t.eval(&self.s);
        u == &v.pow(t_s.get_value())
    }
}

pub fn discrete_log_protocol<F: Field>(prover: &Prover<F>, verifier: &Verifier<F>) -> bool {
    // Step 1 & 2: Verifier generates a challenge
    let max_degree = prover.p.degree();
    let alpha_powers = verifier.generate_challenge(max_degree as usize);

    // Step 3: Prover computes and sends u = g^p and v = g^h
    let (u, v) = prover.compute_values(&alpha_powers);

    // Step 4: Verifier checks whether u = v^t
    verifier.verify(&u, &v)
}
}

Vulnerability:

However, this protocol still has a flaw. Since the Prover can compute \(g^t = \alpha_{c_1}(\alpha_2)^{c_2}\cdots(\alpha_m)^{c_m}\), they could send fake values \(((g^{t})^{z}, g^{z})\) instead of \((g^p, g^h)\) for an arbitrary value \(z\). The verifier's check would still pass, and they could not detect this deception.

#![allow(unused)]
fn main() {
// Simulating a malicious prover
pub struct MaliciousProver<F: Field> {
    t: Polynomial<F>,
}

impl<F: Field> MaliciousProver<F> {
    pub fn new(t: Polynomial<F>) -> Self {
        MaliciousProver { t }
    }

    pub fn compute_malicious_values(&self, alpha_powers: &[F]) -> (F, F) {
        let g_t = self.t.eval_with_powers(alpha_powers);
        let z = F::random_element(&[]);
        let g = &alpha_powers[0];
        let fake_v = g.pow(z.get_value());
        let fake_u = g_t.pow(z.get_value());
        (fake_u, fake_v)
    }
}

pub fn malicious_discrete_log_protocol<F: Field>(
    prover: &MaliciousProver<F>,
    verifier: &Verifier<F>,
) -> bool {
    // Step 1 & 2: Verifier generates a challenge
    let max_degree = prover.t.degree() as usize;
    let alpha_powers = verifier.generate_challenge(max_degree as usize);

    // Step 3: Malicious Prover computes and sends fake u and v
    let (fake_u, fake_v) = prover.compute_malicious_values(&alpha_powers);

    // Step 4: Verifier checks whether u = v^t (which will pass for the fake values)
    verifier.verify(&fake_u, &fake_v)
}
}

\(+\) Knowledge of Exponent Assumption

To address the vulnerability where the verifier \(\mathcal{B}\) cannot distinguish if \(v (= g^h)\) from the prover is a power of \(\alpha_i = g^{(s^i)}\), we can employ the Knowledge of Exponent Assumption. This approach involves the following steps:

• \(\mathcal{B}\) sends both \(\alpha_i\) and \(\alpha'_i = \alpha_i^r\) for a new random value \(r\).
• The prover returns \(a = (\alpha_i)^{c_i}\) and \(a' = (\alpha'_i)^{c_i}\) for \(i = 1, ..., n\).
• \(\mathcal{B}\) can conclude that \(a\) is a power of \(\alpha_i\) if \(a^r = a'\).

Based on this assumption, we can design an improved protocol:

Protocol:

• \(\mathcal{B}\) randomly selects \(s\) and \(r\) from field \(\mathbb{F}\).
• \(\mathcal{B}\) computes and sends \(\{\alpha_1, \alpha_2, ..., \alpha_{n}\}\) and \(\{\alpha'_1, \alpha'_2, ..., \alpha'_{n}\}\), where \(\alpha_i = g^{(s^i)}\) and \(\alpha' = \alpha_{r} = g^{(s^{i})r}\).
• \(\mathcal{A}\) computes and sends \(u = g^{p}\), \(v = g^{h}\), and \(w = g^{p'}\), where \(g^{p'} = g^{P(sr)}\).
• \(\mathcal{B}\) checks whether \(u^{r} = w\).
• \(\mathcal{B}\) checks whether \(u = v^{t}\).

The prover can compute \(g^{p'} = g^{P(sr)} = \alpha'^{c_1} (\alpha'^{2})^{c_2} \cdots (\alpha'^{n})^{c_n}\) using powers of \(\alpha'\). This protocol now satisfies the properties of a SNARK: completeness, soundness, and efficiency.

Implementation:

#![allow(unused)]
fn main() {
pub struct Prover<F: Field> {
    pub p: Polynomial<F>,
    pub t: Polynomial<F>,
    pub h: Polynomial<F>,
}

pub struct Verifier<F: Field> {
    t: Polynomial<F>,
    s: F,
    r: F,
    g: F,
}

impl<F: Field> Prover<F> {
    pub fn new(p: Polynomial<F>, t: Polynomial<F>) -> Self {
        let h = p.clone() / t.clone();
        Prover { p, t, h }
    }

    pub fn compute_values(&self, alpha_powers: &[F], alpha_prime_powers: &[F]) -> (F, F, F) {
        let g_p = self.p.eval_with_powers(alpha_powers);
        let g_h = self.h.eval_with_powers(alpha_powers);
        let g_p_prime = self.p.eval_with_powers(alpha_prime_powers);
        (g_p, g_h, g_p_prime)
    }
}

impl<F: Field> Verifier<F> {
    pub fn new(t: Polynomial<F>, generator: i128) -> Self {
        let mut rng = rand::thread_rng();
        let s = F::from_value(rng.gen_bigint_range(
            &BigInt::zero(),
            &BigInt::from(std::u64::MAX),
        ));
        let r = F::from_value(rng.gen_bigint_range(
            &BigInt::zero(),
            &BigInt::from(std::u64::MAX),
        ));
        let g = F::from_value(generator);
        Verifier { t, s, r, g }
    }

    pub fn generate_challenge(&self, max_degree: usize) -> (Vec<F>, Vec<F>) {
        let mut alpha_powers = vec![];
        let mut alpha_prime_powers = vec![];

        for i in 0..(max_degree + 1) {
            alpha_powers.push(
                self.g
                    .pow(self.s.clone().pow(i.to_bigint().unwrap()).get_value()),
            );
            alpha_prime_powers.push(alpha_powers.last().unwrap().pow(self.r.get_value()));
        }

        (alpha_powers, alpha_prime_powers)
    }

    pub fn verify(&self, u: &F, v: &F, w: &F) -> bool {
        let t_s = self.t.eval(&self.s);
        let u_r = u.pow(self.r.clone().get_value());

        // Check 1: u^r = w
        let check1 = u_r == *w;

        // Check 2: u = v^t
        let check2 = *u == v.pow(t_s.get_value());

        check1 && check2
    }
}

pub fn knowledge_of_exponent_protocol<F: Field>(
    prover: &Prover<F>,
    verifier: &Verifier<F>,
) -> bool {
    // Step 1 & 2: Verifier generates a challenge
    let max_degree = std::cmp::max(prover.p.degree(), prover.h.degree()) as usize;
    let (alpha_powers, alpha_prime_powers) = verifier.generate_challenge(max_degree + 1);

    // Step 3: Prover computes and sends u = g^p, v = g^h, and w = g^p'
    let (u, v, w) = prover.compute_values(&alpha_powers, &alpha_prime_powers);

    // Step 4 & 5: Verifier checks whether u^r = w and u = v^t
    verifier.verify(&u, &v, &w)
}
}

\(+\) Zero Knowledge

To transform the above protocol into a zk-SNARK, we need to ensure that the verifier cannot learn anything about \(P(x)\) from the prover's information. This is achieved by having the prover obfuscate all information with a random secret value \(\delta\):

Protocol:

• \(\mathcal{B}\) randomly selects \(s\) and \(r\) from field \(\mathbb{F}\).
• \(\mathcal{B}\) computes and sends \(\{\alpha_1, \alpha_2, ..., \alpha_{n}\}\) and \(\{\alpha_1', \alpha'_2, ..., \alpha'_{n}\}\), where \(\alpha_i = g^{(s^{i})}\) and \(\alpha_i' = \alpha_i^{r} = g^{(s^{i})r}\).
• \(\mathcal{A}\) randomly selects \(\delta\) from field \(\mathbb{F}\).
• \(\mathcal{A}\) computes and sends \(u' = (g^{p})^{\delta}\), \(v' = (g^{h})^{\delta}\), and \(w' = (g^{p'})^{\delta}\).
• \(\mathcal{B}\) checks whether \(u'^{r} = w'\).
• \(\mathcal{B}\) checks whether \(u' = v'^{t}\).

By introducing the random value \(\delta\), the verifier can no longer learn anything about \(p\), \(h\), or \(w\), thus achieving zero knowledge.

Implementation:

#![allow(unused)]
fn main() {
pub struct Prover<F: Field> {
    pub p: Polynomial<F>,
    pub t: Polynomial<F>,
    pub h: Polynomial<F>,
}

pub struct Verifier<F: Field> {
    t: Polynomial<F>,
    s: F,
    r: F,
    g: F,
}

impl<F: Field> Prover<F> {
    pub fn new(p: Polynomial<F>, t: Polynomial<F>) -> Self {
        let h = p.clone() / t.clone();
        Prover { p, t, h }
    }

    pub fn compute_values(&self, alpha_powers: &[F], alpha_prime_powers: &[F]) -> (F, F, F) {
        let mut rng = rand::thread_rng();
        let delta = F::from_value(rng.gen_bigint_range(
            &BigInt::zero(),
            &BigInt::from(std::u64::MAX),
        ));

        let g_p = self.p.eval_with_powers(alpha_powers);
        let g_h = self.h.eval_with_powers(alpha_powers);
        let g_p_prime = self.p.eval_with_powers(alpha_prime_powers);

        let u_prime = g_p.pow(delta.get_value());
        let v_prime = g_h.pow(delta.get_value());
        let w_prime = g_p_prime.pow(delta.get_value());

        (u_prime, v_prime, w_prime)
    }
}

impl<F: Field> Verifier<F> {
    pub fn new(t: Polynomial<F>, generator: i128) -> Self {
        let mut rng = rand::thread_rng();
        let s = F::from_value(rng.gen_bigint_range(
            &BigInt::zero(),
            &BigInt::from(std::u64::MAX),
        ));
        let r = F::from_value(rng.gen_bigint_range(
            &BigInt::zero(),
            &BigInt::from(std::u64::MAX),
        ));
        let g = F::from_value(generator);
        Verifier { t, s, r, g }
    }

    pub fn generate_challenge(&self, max_degree: usize) -> (Vec<F>, Vec<F>) {
        let mut alpha_powers = vec![];
        let mut alpha_prime_powers = vec![];

        for i in 0..(max_degree + 1) {
            alpha_powers.push(
                self.g
                    .pow(self.s.clone().pow(i.to_bigint().unwrap()).get_value()),
            );
            alpha_prime_powers.push(alpha_powers.last().unwrap().pow(self.r.get_value()));
        }

        (alpha_powers, alpha_prime_powers)
    }

    pub fn verify(&self, u_prime: &F, v_prime: &F, w_prime: &F) -> bool {
        let t_s = self.t.eval(&self.s);
        let u_prime_r = u_prime.pow(self.r.clone().get_value());

        // Check 1: u'^r = w'
        let check1 = u_prime_r == *w_prime;

        // Check 2: u' = v'^t
        let check2 = *u_prime == v_prime.pow(t_s.get_value());

        check1 && check2
    }
}

pub fn zk_protocol<F: Field>(prover: &Prover<F>, verifier: &Verifier<F>) -> bool {
    // Step 1 & 2: Verifier generates a challenge
    let max_degree = std::cmp::max(prover.p.degree(), prover.h.degree()) as usize;
    let (alpha_powers, alpha_prime_powers) = verifier.generate_challenge(max_degree + 1);

    // Step 3 & 4: Prover computes and sends u' = (g^p)^δ, v' = (g^h)^δ, and w' = (g^p')^δ
    let (u_prime, v_prime, w_prime) = prover.compute_values(&alpha_powers, &alpha_prime_powers);

    // Step 5 & 6: Verifier checks whether u'^r = w' and u' = v'^t
    verifier.verify(&u_prime, &v_prime, &w_prime)
}
}

\(+\) Non-interactivity

The previously described protocol requires each verifier to generate unique random values, which becomes inefficient when a prover needs to demonstrate knowledge to multiple verifiers. To address this, we aim to eliminate the interaction between the prover and verifier. One effective solution is the use of a trusted setup.

Protocol (Trusted Setup):

• Secret Seed: A trusted third party generates the random values \(s\) and \(r\)
• Proof Key: Provided to the prover
  • \(\{\alpha_1, \alpha_2, ..., \alpha_{n}\}\), where \(\alpha_{i} = g^{(s^i)}\)
  • \(\{\alpha'_1, \alpha'_2, ..., \alpha'_{n}\}\), where \(\alpha_i' = g^{(s^{i})r}\)
• Verification Key: Distributed to verifiers
  • \(g^{r}\)
  • \(g^{T(s)}\)
• After distribution, the original \(s\) and \(r\) values are securely destroyed.

Then, the non-interactive protocol consists of two main parts: proof generation and verification.

Protocol (Proof):

• \(\mathcal{A}\) receives the proof key
• \(\mathcal{A}\) randomly selects \(\delta\) from field \(\mathbb{F}\).
• \(\mathcal{A}\) broadcast the proof \(\pi = (u' = (g^{p})^{\delta}, v' = (g^{h})^{\delta}, w' = (g^{p'})^{\delta})\)

Since \(r\) is not shared and already destroyed, the verifier \(\mathcal{B}\) cannot calculate \(u'^{r}\) to check \(u'^{r} = w'\). Instead, the verifier can use a paring with bilinear mapping; \(u'^{r} = w'\) is equivalent to \(e(u' = (g^{p})^{\delta}, g^{r}) = e(w'=(g^{p'})^{\delta}, g)\).

Protocol (Verification):

• \(\mathcal{B}\) receives the verification key.
• \(\mathcal{B}\) receives the proof \(\pi\).
• \(\mathcal{B}\) checks whether \(e(u', g^{r}) = e(w', g)\).
• \(\mathcal{B}\) checks whether \(u' = v'^{t}\).

Implementation:

#![allow(unused)]
fn main() {
pub struct ProofKey {
    alpha: Vec<G1Point>,
    alpha_prime: Vec<G1Point>,
}

pub struct VerificationKey {
    g_r: G2Point,
    g_t_s: G2Point,
}

pub struct Proof {
    u_prime: G1Point,
    v_prime: G1Point,
    w_prime: G1Point,
}

pub struct TrustedSetup {
    proof_key: ProofKey,
    verification_key: VerificationKey,
}

impl TrustedSetup {
    pub fn generate(g1: &G1Point, g2: &G2Point, t: &Polynomial<Fq>, n: usize) -> Self {
        let mut rng = rand::thread_rng();
        let s = Fq::from_value(rng.gen_bigint_range(&BigInt::zero(), &BigInt::from(std::u32::MAX)));
        let r = Fq::from_value(rng.gen_bigint_range(&BigInt::zero(), &BigInt::from(std::u32::MAX)));

        let mut alpha = Vec::with_capacity(n);
        let mut alpha_prime = Vec::with_capacity(n);

        let mut s_power = Fq::one();
        for _ in 0..1 + n {
            alpha.push(g1.clone() * s_power.clone().get_value());
            alpha_prime.push(g1.clone() * (s_power.clone() * r.clone()).get_value());
            s_power = s_power * s.clone();
        }

        let g_r = g2.clone() * r.clone().get_value();
        let g_t_s = g2.clone() * t.eval(&s).get_value();

        TrustedSetup {
            proof_key: ProofKey { alpha, alpha_prime },
            verification_key: VerificationKey { g_r, g_t_s },
        }
    }
}

pub struct Prover {
    pub p: Polynomial<Fq>,
    pub h: Polynomial<Fq>,
}

impl Prover {
    pub fn new(p: Polynomial<Fq>, t: Polynomial<Fq>) -> Self {
        let h = p.clone() / t;
        Prover { p, h }
    }

    pub fn generate_proof(&self, proof_key: &ProofKey) -> Proof {
        let mut rng = rand::thread_rng();
        let delta =
            Fq::from_value(rng.gen_bigint_range(&BigInt::zero(), &BigInt::from(std::u32::MAX)));

        let g_p = self.p.eval_with_powers_on_curve(&proof_key.alpha);
        let g_h = self.h.eval_with_powers_on_curve(&proof_key.alpha);
        let g_p_prime = self.p.eval_with_powers_on_curve(&proof_key.alpha_prime);

        Proof {
            u_prime: g_p * delta.get_value(),
            v_prime: g_h * delta.get_value(),
            w_prime: g_p_prime * delta.get_value(),
        }
    }
}

pub struct Verifier {
    pub g1: G1Point,
    pub g2: G2Point,
}

impl Verifier {
    pub fn new(g1: G1Point, g2: G2Point) -> Self {
        Verifier { g1, g2 }
    }

    pub fn verify(&self, proof: &Proof, vk: &VerificationKey) -> bool {
        // Check e(u', g^r) = e(w', g)
        let pairing1 = optimal_ate_pairing(&proof.u_prime, &vk.g_r);
        let pairing2 = optimal_ate_pairing(&proof.w_prime, &self.g2);
        let check1 = pairing1 == pairing2;

        // Check e(u', g^t) = e(v', g)
        let pairing3 = optimal_ate_pairing(&proof.u_prime, &self.g2);
        let pairing4 = optimal_ate_pairing(&proof.v_prime, &vk.g_t_s);
        let check2 = pairing3 == pairing4;

        check1 && check2
    }
}

pub fn non_interactive_zkp_protocol(
    prover: &Prover,
    verifier: &Verifier,
    setup: &TrustedSetup,
) -> bool {
    let proof = prover.generate_proof(&setup.proof_key);
    verifier.verify(&proof, &setup.verification_key)
}
}

Bringing It All Together

Let's recap the previous sections. First, the relationship between the inputs and outputs of any program can be expressed as a rank-one constraint system (R1CS) as follows:

\[ (L \cdot v) \circ (R \cdot v) - O \cdot v = 0
\]

, where \(v\) is the concatenation of all inputs, outputs, and intermediate values. This allows us to transform the statement, "I know the input values \(x\) that make the program returns the output values \(y\)", into "I know \(v\), whose outputs components are \(y\), that satisfies the constraint system corresponding to the program".

Then, instead of separately checking each constraint (which corresponds to a row in the R1CS matrix), we can convert this into a more efficient polynomial-equivalence test.

First Protocol Idea

The simplest protocol, based on the previous chapter, is as follows:

Protocol (Setup)

• Interpolated Polynomial: Construct \(\{\ell_i, r_i, o_i\}_{i\in[d]}\) from \(L\), \(R\), and \(O\), respectively.
• Target Polynomial: \(t(x) = (x-1)(x-2) \cdots (x-m)\)
• Secret Seed: A trusted party generates the random value \(s\) and \(\alpha\).
• Proof Key: Provided to the prover
  • \(\{g^{\ell_i(s)},g^{r_i(s)},g^{o_i(s)}\}_{i\in[d]}\)
  • \(\{g^{\alpha \ell_i(s)},g^{\alpha r_i(s)},g^{\alpha o_i(s)}\}_{i\in[d]}\)
  • \(\{g^{(s^j)}\}_{j\in[m]}\)
• Verification Key:
  • \(g^{t(s)}\)
  • \(g^{\alpha}\)
• After distribution, the original \(s\) and \(\alpha\) values are securely destroyed.

Both the proof key and the verification key are publicly available, enabling anyone to generate and verify proofs based on the target program.

Protocol (Proving)

• Run the program to obtain the assignment vector \(v\).
• Compute the linear-combinations of polynomials
  • \(\ell(x) = \sum_{i=1}^{d} v_i \ell_{i}(x)\)
  • \(r(x) = \sum_{i=1}^{d} v_i r_{i}(x)\)
  • \(o(x) = \sum_{i=1}^{d} v_i o_{i}(x)\)
• Compute \(h(x) = \frac{\ell(x) r(x) - o(x)}{t(x)}\)
• Evaluate each polynomial at \(s\).
  • \(g^{\ell(s)} = \prod^{d}_{i=1} (g^{\ell_i(s)})^{v_i} \)
  • \(g^{r(s)} = \prod^{d}_{i=1} (g^{r_i(s)})^{v_i} \)
  • \(g^{o(s)} = \prod^{d}_{i=1} (g^{o_i(s)})^{v_i} \)
• Evaluate the shifted polynomials at \(s\).
  • \(g^{\alpha \ell(s)} = \prod^{d}_{i=1} (g^{\alpha \ell_i(s)})^{v_i} \)
  • \(g^{\alpha r(s)} = \prod^{d}_{i=1} (g^{\alpha r_i(s)})^{v_i} \)
  • \(g^{\alpha o(s)} = \prod^{d}_{i=1} (g^{\alpha o_i(s)})^{v_i} \)
• Compute \(g^{h(s)}\) from \(\{g^{(s^j)}\}_{j\in[m]}\)
• Proof: \((g^{\ell(s)}, g^{r(s)}, g^{o(s)}, g^{\alpha \ell(s)}, g^{\alpha r(s)}, g^{\alpha o(s)}, g^{h(s)})\)

Protocol (Verification)

• Parse the proof as \((g^{\ell}, g^r, g^o, g^{\ell'}, g^{r'}, g^{o'}, g^{h})\)
• Check the polynomial restrictions
  • \(e(g^{\ell}, g^{\alpha}) = e(g^{\ell'}, g)\)
  • \(e(g^{r}, g^{\alpha}) = e(g^{r'}, g)\)
  • \(e(g^{o}, g^{\alpha}) = e(g^{o'}, g)\)
• Verify validity of the proof
  • \(e(g^{\ell}, g^{r}) = e(g^t,g^h) \cdot e(g^o, g)\)

Vulnerability

A critical issue with this protocol is that the checks may pass even if \(g^{\ell}\) is computed not from \(\{g^{\ell_i(s)}\}_{i \in [d]}\) but from \(\{g^{r_i(s)}\} _{i \in [d]}\), \(\{g^{o_i(s)}\} _{i \in [d]}\), or their combinations. The same issue applies to \(g^{r}\) and \(g^{o}\).

For example, if the prover sends \((g^{r(s)}, g^{\ell(s)}, g^{o(s)}, g^{\alpha r(s)}, g^{\alpha \ell(s)}, g^{\alpha o(s)}, g^{h(s)})\) as the proof, all the verification checks still pass, even although the proved statement differs from the original one.

Second Protocol: Non-Interchangibility

To address the interchangeability issue, the next protocol uses distinct the different \(\alpha\)-shift for \(\ell\), \(r\), and \(o\).

Protocol (Setup)

• Interpolated Polynomial: Construct \(\{\ell_i, r_i, o_i\}_{i\in[d]}\) from \(L\), \(R\), and \(O\), respectively.
• Target Polynomial: \(t(x) = (x-1)(x-2) \cdots (x-m)\)
• Secret Seed: A trusted party generates the random value \(s\), \(\alpha_{\ell}\), \(\alpha_r\), and \(\alpha_o\).
• Proof Key (for the prover):
  • \(\{g^{\ell_i(s)},g^{r_i(s)},g^{o_i(s)}\}_{i\in[d]}\)
  • \(\{g^{\alpha_{\ell} \ell_i(s)},g^{\alpha_{r} r_i(s)},g^{\alpha_{o} o_i(s)}\}_{i\in[d]}\)
  • \(\{g^{(s^j)}\}_{j\in[m]}\)
• Verification Key (public):
  • \(g^{t(s)}\)
  • \(g^{\alpha_{\ell}}\), \(g^{\alpha_{r}}\), \(g^{\alpha_{o}}\)
• After distribution, the original \(s\), \(\alpha_{\ell}\), \(\alpha_r\), and \(\alpha_o\) values are securely destroyed.

Protocol (Proving)

• Execute the program and get the assignment \(v\).
• Compute the linear-combinations of polynomials
  • \(\ell(x) = \sum_{i=1}^{d} v_i \ell_{i}(x)\)
  • \(r(x) = \sum_{i=1}^{d} v_i r_{i}(x)\)
  • \(o(x) = \sum_{i=1}^{d} v_i o_{i}(x)\)
• Compute \(h(x) = \frac{\ell(x) r(x) - o(x)}{t(x)}\)
• Evaluate each polynomial at \(s\).
  • \(g^{\ell(s)} = \prod^{d}_{i=1} (g^{\ell_i(s)})^{v_i} \)
  • \(g^{r(s)} = \prod^{d}_{i=1} (g^{r_i(s)})^{v_i} \)
  • \(g^{o(s)} = \prod^{d}_{i=1} (g^{o_i(s)})^{v_i} \)
• Evaluate each shifted polynomial at \(s\).
  • \(g^{\alpha_{\ell} \ell(s)} = \prod^{d}_{i=1} (g^{\alpha _{\ell} \ell_i(s)})^{v_i} \)
  • \(g^{\alpha_{r} r(s)} = \prod^{d}_{i=1} (g^{\alpha _{r} r_i(s)})^{v_i} \)
  • \(g^{\alpha_{o} o(s)} = \prod^{d}_{i=1} (g^{\alpha _{o} o_i(s)})^{v_i} \)
• Calculate \(g^{h(s)}\) from \(\{g^{(s^j)}\}_{j\in[m]}\)
• Proof: \((g^{\ell(s)}, g^{r(s)}, g^{o(s)},\) \(g^{\alpha_{\ell} \ell(s)}, g^{\alpha_{r} r(s)}, g^{\alpha_{o} o(s)},\) \(g^{h(s)})\)

Protocol (Verification)

• Parse proof as \((g^{\ell}, g^r, g^o, g^{\ell'}, g^{r'}, g^{o'}, g^{h})\)
• Check polynomial restrictions
  • \(e(g^{\ell}, g^{\alpha_{\ell}}) = e(g^{\ell'}, g)\)
  • \(e(g^{r}, g^{\alpha_{r}}) = e(g^{r'}, g)\)
  • \(e(g^{o}, g^{\alpha_{o}}) = e(g^{o'}, g)\)
• Validity check
  • \(e(g^{\ell}, g^{r}) = e(g^t,g^h) \cdot e(g^o, g)\)

Vulnerability

This protocol resolves interchangeability but does not enforce consistency acros \(\ell\), \(r\), and \(o\). Variables \(v_i\) can still take different values in each polynoimal because verification checks are performed separately.

Thrid Protocol: Variable Consistency

To achive the variable consistency, we employ a checksum mechanism. Specifically, we first draw a new random value \(\beta\) and define the checksum of \(v_i\) as \(g^{\beta(\ell_{i}(s) + r_i(s) + o_i(s))}\). Let \(v _{\ell, i}\), \(v _{r,i}\), \(v _{o,i}\), and \(v _{\beta,i}\) denote the \(i\)-th value of the assignment vectors for \(\ell\), \(r\), \(o\) and the checksum, respectively. If all of them are the same, the following equation holds:

\[ e(g^{v _{\ell, i} \ell_i(s)} g^{v _{r, i} r_i(s)} g^{v _{o, i} o_i(s)}, g^{\beta}) = e(g^{v _{\beta, i} \beta(\ell _{i}(s) + r _{i}(s) + o _{i}(s))}, g) \]

Unfortunately, this condition is not strictly equivalent. For example, consider the case where \(\ell_i(x) = r_i(x)\). In this scenario, we have:

\begin{align*} &\beta(v _{\ell, i} \ell_i(s) + v _{r, i} r_i(s) + v _{o, i} o_i(s)) = v _{\beta, i} \beta (\ell _{i}(s) + r _{i}(s) + o _{i}(s)) \\ \iff &\beta(v _{\ell, i} \ell_i(s) + v _{r, i} \ell_i(s) + v _{o, i} o_i(s)) = v _{\beta, i} \beta (2\ell _{i}(s) + o _{i}(s)) \end{align*}

This equation holds for arbitrary \(v _{r,i}\) and \(v _{o,i}\) if we set \(v _{\beta, i} = v _{o, i}\) and \(v _{\ell, i} = 2 v _{o, i} - v _{r, i}\).

To address this issue, we use distinct different \(\beta\) values for \(\ell\), \(r\) and \(o\). The consistency check then verifies the following equation:

\[ e(g^{v _{\ell, i} \ell _{i}(s)}, g^{\beta _{\ell}}) \cdot e(g^{v _{r, i} r _{i}(s)}, g^{\beta _{r}}) \cdot e(g^{v _{o, i} o _{i}(s)}, g^{\beta _{o}}) = e(g^{v _{\beta, i}(\beta _{\ell} \ell _{i}(s) + \beta _{r} r _{i}(s) + \beta _{o} o _{i}(s))}, g)
\]

The new protocol using the above variable-consistency check is as follows:

Protocol (Setup)

• Interpolated Polynomial: Construct \(\{\ell_i, r_i, o_i\}_{i\in[d]}\) from \(L\), \(R\), and \(O\), respectively.
• Target Polynomial: \(t(x) = (x-1)(x-2) \cdots (x-m)\)
• Secret Seed: A trusted party generates the random value \(s\), \(\alpha_{\ell}\), \(\alpha_r\), \(\alpha_o\), \(\beta_{\ell}\), \(\beta_{r}\), and \(\beta_{o}\).
• Consistency Polynomial: \(\{g^{\beta _{\ell} \ell _{i}(s) + \beta _{r} r _{i}(s) + \beta _{o} o _{i}(s)}\} _{i \in [d]}\)
• Proof Key: Provided to the prover
  • \(\{g^{\ell_i(s)},g^{r_i(s)},g^{o_i(s)}\}_{i\in[d]}\)
  • \(\{g^{\alpha_{\ell} \ell_i(s)},g^{\alpha_{r} r_i(s)},g^{\alpha_{o} o_i(s)}\}_{i\in[d]}\)
  • \(\{g^{(s^j)}\}_{j\in[m]}\)
• Verification Key:
  • \(g^{t(s)}\)
  • \(g^{\alpha_{\ell}}\), \(g^{\alpha_{r}}\), \(g^{\alpha_{o}}\)
  • \(g^{\beta_{\ell}}, g^{\beta_{r}}, g^{\beta_{o}}\)
• After distribution, the original \(s\), \(\alpha_{\ell}\), \(\alpha_r\), and \(\alpha_o\) values are securely destroyed.

Protocol (Proving)

• Execute the program and get the assignment vector \(v\).
• Compute the linear-combinations of polynomials
  • \(\ell(x) = \sum_{i=1}^{d} v_i \ell_{i}(x)\)
  • \(r(x) = \sum_{i=1}^{d} v_i r_{i}(x)\)
  • \(o(x) = \sum_{i=1}^{d} v_i o_{i}(x)\)
• Compute \(h(x) = \frac{\ell(x) r(x) - o(x)}{t(x)}\)
• Evaluate each polynomial at \(s\):
  • \(g^{\ell(s)} = \prod^{d}_{i=1} (g^{\ell_i(s)})^{v_i} \)
  • \(g^{r(s)} = \prod^{d}_{i=1} (g^{r_i(s)})^{v_i} \)
  • \(g^{o(s)} = \prod^{d}_{i=1} (g^{o_i(s)})^{v_i} \)
• Evaluate each shifted polynomial at \(s\):
  • \(g^{\alpha_{\ell} \ell(s)} = \prod^{d}_{i=1} (g^{\alpha _{\ell} \ell_i(s)})^{v_i} \)
  • \(g^{\alpha_{r} r(s)} = \prod^{d}_{i=1} (g^{\alpha _{r} r_i(s)})^{v_i} \)
  • \(g^{\alpha_{o} o(s)} = \prod^{d}_{i=1} (g^{\alpha _{o} o_i(s)})^{v_i} \)
• Evaluate each consistency polynomial at \(s\):
  • \(g^{z(s)} = \prod^{d}_{i=1} (g^{\beta _{\ell} \ell _{i}(s) + \beta _{r} r _{i}(s) + \beta _{o} o _{i}(s)})^{v _{i}}\)
• Calculate \(g^{h(s)}\) from \(\{g^{(s^j)}\}_{j\in[m]}\)
• Proof: \((\) \(g^{\ell(s)}, g^{r(s)}, g^{o(s)}, g^{\alpha_{\ell} \ell(s)}, g^{\alpha_{r} r(s)}, g^{\alpha_{o} o(s)}, g^{h(s)},\) \(g^{z(s)}\) \()\)

Protocol (Verification)

• Parse proof as \((g^{\ell}, g^r, g^o, g^{\ell'}, g^{r'}, g^{o'}, g^{h}, g^{z})\)
• Check polynomial restrictions
  • \(e(g^{\ell}, g^{\alpha_{\ell}}) = e(g^{\ell'}, g)\)
  • \(e(g^{r}, g^{\alpha_{r}}) = e(g^{r'}, g)\)
  • \(e(g^{o}, g^{\alpha_{o}}) = e(g^{o'}, g)\)
• Check variable consistency
  • \(e(g^{\ell}, g^{\beta _{\ell}}) \cdot e(g^{r}, g^{\beta _{r}}) \cdot e(g^{o}, g^{\beta _{o}}) = e(g^{z}, g)\)
• Validity check
  • \(e(g^{\ell}, g^{r}) = e(g^t,g^h) \cdot e(g^o, g)\)

Vulnerability

Despite these checks, the protocol is vulnerable to malleability. Specifically, a malicious prover can exploit the polynomial restriction check to introduce arbitrary constants, altering the proof witout detection.

Recall that the verifier validates whether the submitted \(g^{\ell}\) is actually calculated by \(\{g^{\ell _i(s)}\} _{i \in [d]}\) by checking \(e(g^{\ell}, g^{\alpha _{\ell}}) = e(g^{\ell'}, g)\). However, this process is not sound. Recall that the verification key is publicaly available, and the prover knows both of \(g^{\alpha _{\ell}}\) and \(g^{\beta _{\ell}}\). Here, suppose the prover submits \(g^{\ell} g^{c}\) and \(g^{\ell'} (g^{\alpha _{\ell}})^{c}\) insteads of \(g^{\ell}\) and \(g^{\ell'}\), where \(c\) is a constatn value. Then, the polynomial restriction check still passes:

\[ e(g^{\ell} g^{c}, g^{\alpha _{\ell}}) = e(g^{\alpha _{\ell} \ell + \alpha _{\ell} c}, g) = e(g^{\ell'}g^{\alpha _{\ell}c}, g) = e(g^{\ell'} (g^{\alpha _{\ell}})^{c}, g) \]

In addition, if the prover submits \(g^{z} (g^{\beta _{\ell}})^{c}\) as the checksum, it also passes the polynomial checksum verification:

\[ e(g^{\ell} g^{c}, g^{\beta _{\ell}}) \cdot e(g^{r}, g^{\beta _{r}}) \cdot e(g^{o}, g^{\beta _{o}}) = e(g^{z} (g^{\beta _{\ell}})^{c}, g) \]

This phenomenon also can occur for \(r\) and \(o\).

Forth Protocol: Non-Malleability

One way to surrogate the above malleability is hiding \(g^{\beta _{\ell}}\), \(g^{\beta _{r}}\), and \(g^{\beta _{o}}\) by powering them with a new random value \(\eta\).

Protocol (Setup)

• Interpolated Polynomial: Construct \(\{\ell_i, r_i, o_i\}_{i\in[d]}\) from \(L\), \(R\), and \(O\), respectively.
• Target Polynomial: \(t(x) = (x-1)(x-2) \cdots (x-m)\)
• Secret Seed: A trusted party generates the random value \(s\), \(\alpha_{\ell}\), \(\alpha_r\), \(\alpha_o\), \(\beta_{\ell}\), \(\beta_{r}\), \(\beta_{o}\), and \(\eta\).
• Consistency Polynomial: \(\{g^{\beta _{\ell} \ell _{i}(s) + \beta _{r} r _{i}(s) + \beta _{o} o _{i}(s)}\} _{i \in [d]}\)
• Proof Key: Provided to the prover
  • \(\{g^{\ell_i(s)},g^{r_i(s)},g^{o_i(s)}\}_{i\in[d]}\)
  • \(\{g^{\alpha_{\ell} \ell_i(s)},g^{\alpha_{r} r_i(s)},g^{\alpha_{o} o_i(s)}\}_{i\in[d]}\)
  • \(\{g^{(s^j)}\}_{j\in[m]}\)
• Verification Key:
  • \(g^{t(s)}\)
  • \(g^{\alpha_{\ell}}\), \(g^{\alpha_{r}}\), \(g^{\alpha_{o}}\)
  • \(g^{\beta_{\ell} \eta}, g^{\beta_{r} \eta}, g^{\beta_{o} \eta}\)
• After distribution, the original \(s\), \(\alpha_{\ell}\), \(\alpha_r\), and \(\alpha_o\) values are securely destroyed.

Protocol (Proving)

• Execute the program and get the assignment vector \(v\).
• Compute the linear-combinations of polynomials
  • \(\ell(x) = \sum_{i=1}^{d} v_i \ell_{i}(x)\)
  • \(r(x) = \sum_{i=1}^{d} v_i r_{i}(x)\)
  • \(o(x) = \sum_{i=1}^{d} v_i o_{i}(x)\)
• Compute \(h(x) = \frac{\ell(x) r(x) - o(x)}{t(x)}\)
• Evaluate each polynomial at \(s\):
  • \(g^{\ell(s)} = \prod^{d}_{i=1} (g^{\ell_i(s)})^{v_i} \)
  • \(g^{r(s)} = \prod^{d}_{i=1} (g^{r_i(s)})^{v_i} \)
  • \(g^{o(s)} = \prod^{d}_{i=1} (g^{o_i(s)})^{v_i} \)
• Evaluate each shifted polynomial at \(s\):
  • \(g^{\alpha_{\ell} \ell(s)} = \prod^{d}_{i=1} (g^{\alpha _{\ell} \ell_i(s)})^{v_i} \)
  • \(g^{\alpha_{r} r(s)} = \prod^{d}_{i=1} (g^{\alpha _{r} r_i(s)})^{v_i} \)
  • \(g^{\alpha_{o} o(s)} = \prod^{d}_{i=1} (g^{\alpha _{o} o_i(s)})^{v_i} \)
• Evaluate each consistency polynomial at \(s\):
  • \(g^{z(s)} = \prod^{d}_{i=1} (g^{\beta _{\ell} \ell _{i}(s) + \beta _{r} r _{i}(s) + \beta _{o} o _{i}(s)})^{v _{i}}\)
• Calculate \(g^{h(s)}\) from \(\{g^{(s^j)}\}_{j\in[m]}\)
• Proof: \((\) \(g^{\ell(s)}, g^{r(s)}, g^{o(s)}, g^{\alpha_{\ell} \ell(s)}, g^{\alpha_{r} r(s)}, g^{\alpha_{o} o(s)}, g^{h(s)},\) \(g^{z(s)}\) \()\)

Protocol (Verification)

• Parse proof as \((g^{\ell}, g^r, g^o, g^{\ell'}, g^{r'}, g^{o'}, g^{h}, g^{z})\)
• Check polynomial restrictions
  • \(e(g^{\ell}, g^{\alpha_{\ell}}) = e(g^{\ell'}, g)\)
  • \(e(g^{r}, g^{\alpha_{r}}) = e(g^{r'}, g)\)
  • \(e(g^{o}, g^{\alpha_{o}}) = e(g^{o'}, g)\)
• Check variable consistency
  • \(e(g^{\ell}, g^{\beta _{\ell} \eta}) \cdot e(g^{r}, g^{\beta _{r} \eta}) \cdot e(g^{o}, g^{\beta _{o} \eta}) = e(g^{z}, g^{\eta})\)
• Validity check
  • \(e(g^{\ell}, g^{r}) = e(g^t,g^h) \cdot e(g^o, g)\)

Fifth Protocol: Pinocchio

The above protocol introduces four expensive pairing operations. To make it faster, Pinocchio protocl randomizes the generators.

Protocol (Setup)

• Interpolated Polynomial: Construct \(\{\ell_i, r_i, o_i\}_{i\in[d]}\) from \(L\), \(R\), and \(O\), respectively.
• Target Polynomial: \(t(x) = (x-1)(x-2) \cdots (x-m)\)
• Secret Seed: A trusted party generates the random value \(s\), \(\alpha_{\ell}\), \(\alpha_r\), \(\alpha_o\), \(\beta_{\ell}\), \(\beta_{r}\), \(\beta_{o}\), \(\eta\), \(\rho _{\ell}\), and \(\rho _{r}\), and set \(\rho _{o} = \rho _{\ell} \rho _{r}\).
• Randized Generators: \(g _{\ell} = g^{\rho _{\ell}}\), \(g _{r} = g^{\rho _{r}}\), and \(g _{o} = g^{\rho _{o}}\)
• Consistency Polynomial: \(\{g^{\beta _{\ell} \ell _{i}(s) + \beta _{r} r _{i}(s) + \beta _{o} o _{i}(s)}\} _{i \in [d]}\)
• Proof Key: Provided to the prover
  • \(\{g_{\ell}^{\ell_i(s)},g_{r}^{r_i(s)},g_{o}^{o_i(s)}\}_{i\in[d]}\)
  • \(\{g_{\ell}^{\alpha_{\ell} \ell_i(s)},g_{r}^{\alpha_{r} r_i(s)},g_{o}^{\alpha_{o} o_i(s)}\}_{i\in[d]}\)
  • \(\{g^{(s^j)}\}_{j\in[m]}\)
• Verification Key:
  • \(g_{o}^{t(s)}\)
  • \(g^{\alpha_{\ell}}\), \(g^{\alpha_{r}}\), \(g^{\alpha_{o}}\)
  • \(g^{\beta_{\ell} \eta}, g^{\beta_{r} \eta}, g^{\beta_{o} \eta}\)
• After distribution, the original \(s\), \(\alpha_{\ell}\), \(\alpha_r\), and \(\alpha_o\) values are securely destroyed.

Protocol (Proving)

• Execute the program and get the assignment vector \(v\).
• Compute the linear-combinations of polynomials
  • \(\ell(x) = \sum_{i=1}^{d} v_i \ell_{i}(x)\)
  • \(r(x) = \sum_{i=1}^{d} v_i r_{i}(x)\)
  • \(o(x) = \sum_{i=1}^{d} v_i o_{i}(x)\)
• Compute \(h(x) = \frac{\ell(x) r(x) - o(x)}{t(x)}\)
• Evaluate each polynomial at \(s\):
  • \(g^{\ell(s)} = \prod^{d}_{i=1} (g^{\ell_i(s)})^{v_i} \)
  • \(g^{r(s)} = \prod^{d}_{i=1} (g^{r_i(s)})^{v_i} \)
  • \(g^{o(s)} = \prod^{d}_{i=1} (g^{o_i(s)})^{v_i} \)
• Evaluate each shifted polynomial at \(s\):
  • \(g^{\alpha_{\ell} \ell(s)} = \prod^{d}_{i=1} (g^{\alpha _{\ell} \ell_i(s)})^{v_i} \)
  • \(g^{\alpha_{r} r(s)} = \prod^{d}_{i=1} (g^{\alpha _{r} r_i(s)})^{v_i} \)
  • \(g^{\alpha_{o} o(s)} = \prod^{d}_{i=1} (g^{\alpha _{o} o_i(s)})^{v_i} \)
• Evaluate each consistency polynomial at \(s\):
  • \(g^{z(s)} = \prod^{d}_{i=1} (g _{\ell}^{\beta _{\ell} \ell _{i}(s)} \cdot g _{r}^{\beta _{r} r _{i}(s)} \cdot g _{o}^{\beta _{o} o _{i}(s)})^{v _{i}}\)
• Calculate \(g^{h(s)}\) from \(\{g^{(s^j)}\}_{j\in[m]}\)
• Proof: \((\) \(g^{\ell(s)}, g^{r(s)}, g^{o(s)}, g^{\alpha_{\ell} \ell(s)}, g^{\alpha_{r} r(s)}, g^{\alpha_{o} o(s)}, g^{h(s)},\) \(g^{z(s)}\) \()\)

Protocol (Verification)

• Parse proof as \((g^{\ell}, g^r, g^o, g^{\ell'}, g^{r'}, g^{o'}, g^{h}, g^{z})\)
• Check polynomial restrictions
  • \(e(g _{\ell}^{\ell}, g^{\alpha _{\ell}}) = e(g _{\ell}^{\ell'}, g)\)
  • \(e(g _{r}^{r}, g^{\alpha _{r}}) = e(g _{r}^{r'}, g)\)
  • \(e(g _{o}^{o}, g^{\alpha _{o}}) = e(g _{o}^{o'}, g)\)
• Check variable consistency
  • \(e(g _{\ell}^{\ell} \cdot g _{r}^{r} \cdot g _{o}^{o}) = e(g^{z}, g^{\eta})\)
• Validity check
  • \(e(g^{\ell}, g^{r}) = e(g^t,g^h) \cdot e(g^o, g)\)

This protocol reduces two pairing operations.