🚀 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!

📚 About MyZKP

MyZKP is a growing library that provides:

• A step-by-step guide to the theoretical foundations of ZKPs, including number theory, elliptic curves, and field arithmetic.
• Implementation of core primitives for ZKP protocols.
• A solid base for developers and researchers to learn, experiment, or build their own ZKP-based systems.

💡 Whether you're a cryptography enthusiast, a Rustacean, or a student, MyZKP is for you!

📖 Educational Modules

🧮 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
• 🐍 Bringing It All Together: SNARK

🌟 Basic of zk-STARKs

• ✍️ TBD

💻 Basic of zkVM

• ✍️ TBD

🛠️ Code Reference

🤝 Contributions are Welcome!

We welcome your ideas, feedback, and contributions!

💡 Here are ways to contribute:

1. Report Issues: Found a bug or have a suggestion? Open an issue!
2. Submit Pull Requests: Have code improvements? Feel free to submit them.
3. Write Documentation: Help us make the educational modules clearer.

Basics of Number Theory

To effectively understand and implement ZKP protocols, a solid grasp of number theory concepts is essential. Topics such as rings, groups, fields, modular arithmetic, polynomials, elliptic curves, and pairings are foundational to these protocols.

In this tutorial, we’ll cover these fundamental ideas, highlight their key properties, and demonstrate their implementation from scratch in Rust. 🦀 Whether you're new to these concepts or looking for a refresher, this section will help you build a strong foundation. If you're already an expert, feel free to skip ahead! 🚀

🧠 Key Concepts You Will Learn

1. ✨ Computational Rules: Associative and Commutative Properties
2. 🧮 Integer Arithmetic: Modular Operations, Euler’s Totient Function, and Fermat’s Little Theorem
3. 🔗 Groups, Rings, and Fields: Semigroups, Subgroups, Cyclic Groups, Galois Fields, and Field Extensions
4. 🖋️ Polynomials: Basic Operations, Lagrange Interpolation, and Schwartz–Zippel Lemma
5. 🕊️ Elliptic Curves: Basic Operations, Hasse–Weil Theorem, Zeros and Poles of Functions, and Divisors of Functions
6. ♾️ Pairings: Weil Pairing, Ate Pairing, and Miller’s Algorithm
7. 🔑 Assumptions: Discrete Logarithm Problem and Knowledge of Exponent Assumption

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

zk-SNARK stands for "Zero-Knowledge Succinct Non-Interactive ARgument of Knowledge". It's a cryptographic proof protocol that allows one party (the prover) to convince an another party (the verifier) that they possess certain information, without even revealing the information itself.

In this tutorial, we will gradually implement two of the most popular zk-SNARK protocols: Pinocchio and Groth16. The structure of this guide closely follows the excellent tutorial by, Petkus, Maksym. "Why and how zk-snark works.", as well as the fantastic eBook "The RareSkills Book of Zero Knowledge".

Key Components of zk-SNARKs

• Zero-Knowledge: The prover demonstrates the validity of a statement without revealing any additional information.
• Succinct: Proofs are small in size, and verification is computationally efficient.
• Non-Interactive: Requires no back-and-forth between the prover and verifier.

How zk-SNARKs Work

zk-SNARKs rely on polynomial equations as cryptographic puzzles. The prover generates a proof based on these equations, which are designed to be solvable only by someone with the required knowledge. The verifier can easily check the validity of the proof without accessing the underlying data. Randomness plays a key role in ensuring each proof is unique and secure.

Applications of zk-SNARKs

• Private Transactions: Users can prove they have sufficient funds without revealing their account balance or transaction history7.
• Anonymous Voting: Voters can prove they've voted without disclosing their choice7.
• Blockchain and Smart Contracts: Enhancing privacy and scalability in blockchain networks.
• Identity Verification: Proving identity without revealing personal information.
• Secure Financial Transactions: Enabling confidential financial operations.
• Data Privacy in Healthcare: Protecting sensitive medical information while allowing necessary verifications.

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)}\).

First Protocol: 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 Prover1<F: Field> {
    pub p: Polynomial<F>,
    pub t: Polynomial<F>,
    pub h: Polynomial<F>,
}

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

impl<F: Field> Prover1<F> {
    pub fn new(p: Polynomial<F>, t: Polynomial<F>) -> Self {
        let h = p.clone() / t.clone();
        Prover1 { 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> Verifier1<F> {
    pub fn new(known_roots: Vec<F>) -> Self {
        let t = Polynomial::from_monomials(&known_roots);
        Verifier1 { 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: &Prover1<F>,
    verifier: &Verifier1<F>,
    modulus: i128,
) -> bool {
    // Step 1: Verifier1 sends all possible values (implicitly done by Prover1 computing all values)

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

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

Second Protocol: 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 Prover2<F: Field> {
    pub p: Polynomial<F>,
    pub t: Polynomial<F>,
    pub h: Polynomial<F>,
}

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

impl<F: Field> Prover2<F> {
    pub fn new(p: Polynomial<F>, t: Polynomial<F>) -> Self {
        let h = p.clone() / t.clone();
        Prover2 { 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> Verifier2<F> {
    pub fn new(t: Polynomial<F>) -> Self {
        Verifier2 { 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: &Prover2<F>, verifier: &Verifier2<F>) -> bool {
    // Step 1: Verifier2 generates a random challenge
    let s = verifier.generate_challenge();

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

    // Step 3: Verifier2 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 MaliciousProver2<F: Field> {
    t: Polynomial<F>,
}

impl<F: Field> MaliciousProver2<F> {
    pub fn new(t: Polynomial<F>) -> Self {
        MaliciousProver2 { 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: &MaliciousProver2<F>,
    verifier: &Verifier2<F>,
) -> bool {
    // Step 1: Verifier2 generates a random challenge
    let s = verifier.generate_challenge();

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

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

Third Protocol: 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 \(\gamma\), where \(\gamma = g^s \bmod q\). Thus, it's safe for the Verifier to send \(\gamma\), 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 \(\gamma_{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} \gamma_{1}^{c_1} \gamma_{2}^{c_2} \cdots \gamma_{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 \(\{\gamma_1, \gamma_2, ..., \gamma_{n}\}\), where \(\gamma_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\).

Implementation:

Suppose we are working in a finite field (\mathbb{F}_q) derived from a prime number (q). It’s important to note that

\[g^{c_0} \cdot (g^{s^{1} \bmod q})^{c_1} \cdots (g^{s^{n} \bmod q})^{c_n} \bmod q \]

is not equal to

\[g^{c_0 + c_1 s^{1} + c_2 s^{2} + \cdots c_n s^{n}} \bmod q\]

However, directly calculating \(s^i\) without taking modulo results in too large values to handle. To address this, we leverage Fermat's Little Theorem, which states that for a prime \(q\):

\[a^{b \bmod q - 1} \bmod q\]

Following this principle, our implementation computes \(s^i\) modulo \(q - 1\) to keep the values manageable.

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

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

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

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

impl<F: Field> Verifier3<F> {
    pub fn new(t: Polynomial<F>, generator: i128) -> Self {
        let s = F::random_element(&[]);
        let g = F::from_value(generator);
        Verifier3 { t, s, g }
    }

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

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

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

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

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

Vulnerability:

However, this protocol still has a flaw. Since the Prover can compute \(g^t\) from \(\gamma _1, \cdots \gamma _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 MaliciousProver3<F: Field> {
    t: Polynomial<F>,
}

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

    pub fn compute_malicious_values(&self, s_powers: &[F]) -> (F, F) {
        let g_t = self.t.eval_with_powers(s_powers);
        let z = F::random_element(&[]);
        let g = &s_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: &MaliciousProver3<F>,
    verifier: &Verifier3<F>,
) -> bool {
    // Step 1 & 2: Verifier3 generates a challenge
    let max_degree = prover.t.degree() as usize;
    let s_powers = verifier.generate_challenge(max_degree as usize);

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

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

Forth Protocol: 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 \(\gamma_i = g^{(s^i)}\), we can employ the Knowledge of Exponent Assumption. This approach involves the following steps:

• \(\mathcal{B}\) sends both \(\gamma_i\) and \(\gamma'_i = \gamma_i^r\) for a new random value \(r\).
• The prover returns \(a = (\gamma_i)^{c_i}\) and \(a' = (\gamma'_i)^{c_i}\) for \(i = 1, ..., n\).
• \(\mathcal{B}\) can conclude that \(a\) is a power of \(\gamma_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 \(\{\gamma_1, \gamma_2, ..., \gamma_{n}\}\) and \(\{\gamma'_1, \gamma'_2, ..., \gamma'_{n}\}\), where \(\gamma_i = g^{(s^i)}\) and \(\gamma' = \gamma_{r} = g^{(s^{i})r}\).
• \(\mathcal{A}\) computes and sends \(u = g^{p}\), \(v = g^{h}\), and \(w = g^{p'}\), where \(g^{p'} = g^{rP(s)}\).
• \(\mathcal{B}\) checks whether \(u^{r} = w\).
• \(\mathcal{B}\) checks whether \(u = v^{t}\).

The prover can compute \(g^{p'} = g^{rP(s)} = g^{c_0} (\gamma_{1})'^{c_1} (\gamma'_{2})^{c_2} \cdots (\gamma_{n}')^{c_n}\). This protocol now satisfies the properties of a SNARK: completeness, soundness, and efficiency.

Implementation:

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

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

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

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

impl<F: Field> Verifier4<F> {
    pub fn new(t: Polynomial<F>, generator: i128) -> Self {
        let s = F::random_element(&[]);
        let r = F::random_element(&[]);
        let g = F::from_value(generator);
        Verifier4 { t, s, r, g }
    }

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

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

        (s_powers, s_prime_powers)
    }

    pub fn verify(&self, u: &F, v: &F, w: &F) -> bool {
        let t_s = self.t.eval_m1(&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: &Prover4<F>,
    verifier: &Verifier4<F>,
) -> bool {
    // Step 1 & 2: Verifier4 generates a challenge
    let max_degree = std::cmp::max(prover.p.degree(), prover.h.degree()) as usize;
    let (s_powers, s_prime_powers) = verifier.generate_challenge(max_degree + 1);

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

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

Fifth Protocol: 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 \(\{\gamma_1, \gamma_2, ..., \gamma_{n}\}\) and \(\{\gamma_1', \gamma'_2, ..., \gamma'_{n}\}\), where \(\gamma_i = g^{(s^{i})}\) and \(\gamma_i' = \gamma_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 Prover5<F: Field> {
    pub p: Polynomial<F>,
    pub t: Polynomial<F>,
    pub h: Polynomial<F>,
}

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

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

    pub fn compute_values(&self, s_powers: &[F], s_prime_powers: &[F]) -> (F, F, F) {
        let delta = F::random_element(&[]);

        let g_p = self.p.eval_with_powers(s_powers);
        let g_h = self.h.eval_with_powers(s_powers);
        let g_p_prime = self.p.eval_with_powers(s_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> Verifier5<F> {
    pub fn new(t: Polynomial<F>, generator: i128) -> Self {
        let s = F::random_element(&[]);
        let r = F::random_element(&[]);
        let g = F::from_value(generator);
        Verifier5 { t, s, r, g }
    }

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

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

        (s_powers, s_prime_powers)
    }

    pub fn verify(&self, u_prime: &F, v_prime: &F, w_prime: &F) -> bool {
        let t_s = self.t.eval_m1(&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: &Prover5<F>, verifier: &Verifier5<F>) -> bool {
    // Step 1 & 2: Verifier5 generates a challenge
    let max_degree = std::cmp::max(prover.p.degree(), prover.h.degree()) as usize;
    let (s_powers, s_prime_powers) = verifier.generate_challenge(max_degree + 1);

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

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

Sixth Protocol: 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.

Specifically, we let a thrid trusted party generate the secret seeds, which neither the prover nor the verifier can access. However, this prevents the verifier \(\mathcal{B}\) from calculating \(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)\).

In this tutorial, we adopt the optimal ate pairing, which is an asynmetric pairing and uses two different cyclic groups derived from elliptic curves; \(e(g_1^a, g_2^b) = e(g_1^{ab}, g_2) = e(b_1, g_2^{ab})\), where \(g_1\) and \(g_2\) are the generators of two different cyclic groups.

Protocol (Trusted Setup):

• Secret Seed: A trusted third party generates the random values \(s\) and \(r\)
• Proof Key: Provided to the prover
  • \(\{\gamma_1, \gamma_2, ..., \gamma_{n}\}\), where \(\gamma_{i} = g_1^{(s^i)}\)
  • \(\{\gamma'_1, \gamma'_2, ..., \gamma'_{n}\}\), where \(\gamma_i' = g_1^{(s^{i})r}\)
• Verification Key: Distributed to verifiers
  • \(g_2^r\)
  • \(g_2^t := g_2^{T(s)}\)
• After distribution, the original secret seeds 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_1^{p})^{\delta}, v' = (g_1^{h})^{\delta}, w' = (g_1^{p'})^{\delta})\)

Protocol (Verification):

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

Implementation:

This tutorial utilize elliptic curves called BN128 for pairing:

• First Group:

  • Curve: \(Y^2 = x^3 + 3\) over the finite field \(\mathbb{F}_{q}\), where \(q\) is defined as 21888242871839275222246405745257275088696311157297823662689037894645226208583.
  • Generator \(\mathscr{g}_1 := (1, 2)\)

• Second Group:

  • Curve: \(Y^2 = x^3 + 3\) over the finite field \(\mathbb{F} _{q^2}\)
  • Modulus polynomial for \(\mathbb{F} _{q^2}\): \(x^2 + 1\)
  • Generator \(\mathscr{g}_2\) := (11559732032986387107991004021392285783925812861821192530917403151452391805634x + 10857046999023057135944570762232829481370756359578518086990519993285655852781, 4082367875863433681332203403145435568316851327593401208105741076214120093531x + 8495653923123431417604973247489272438418190587263600148770280649306958101930)

The orders of two groups are \(\omega := \) 21888242871839275222246405745257275088548364400416034343698204186575808495617. Thus, we evaluate the polynomials over the finite field \(\mathbb{F}_{\omega}\).

In the context of elliptic curves, the power of a generator corresponds to the multiplication of an elliptic curve point. This property is reflected in the ate pairing on BN128, which satisfies:

\[ e(a \mathscr{g}_1, b \mathscr{g}_2) = e(ab \mathscr{g}_1, \mathscr{g}_2) = e(\mathscr{g}_1, ab\mathscr{g}_2)
\]

#![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 fn setup(
    g1: &G1Point,
    g2: &G2Point,
    t: &Polynomial<FqOrder>,
    n: usize,
) -> (ProofKey, VerificationKey) {
    let s = FqOrder::random_element(&[]);
    let r = FqOrder::random_element(&[]);

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

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

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

    (
        ProofKey { alpha, alpha_prime },
        VerificationKey { g_r, g_t_s },
    )
}

pub fn prove(p: &Polynomial<FqOrder>, t: &Polynomial<FqOrder>, proof_key: &ProofKey) -> Proof {
    let h = p.clone() / t.clone();
    let delta = FqOrder::random_element(&[]);

    let g_p = p.eval_with_powers_on_curve(&proof_key.alpha);
    let g_h = h.eval_with_powers_on_curve(&proof_key.alpha);
    let g_p_prime = 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 fn verify(g2: &G2Point, proof: &Proof, vk: &VerificationKey) -> bool {
    // Check e(u', rG_2) = e(w', G_2)
    let pairing1 = optimal_ate_pairing(&proof.u_prime, &vk.g_r);
    let pairing2 = optimal_ate_pairing(&proof.w_prime, g2);
    let check1 = pairing1 == pairing2;

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

    check1 && check2
}
}

Bringing It All Together: SNARK

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:

\[ \ell(x) \cdot r(x) = o(x) + h(x) \cdot t(x) \]

In this tutorial, we use symmetric pairing to formulate each protocol for simplicity, where the first and second arguments are in the same group, while the actual implementation adopts an asymmetric pairing, similar to the final protocol in the previous chapter

First Protocol: Naive Approach

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 secret seeds 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),\quad r(x) = \sum_{i=1}^{d} v_i r_{i}(x),\quad o(x) = \sum_{i=1}^{d} v_i o_{i}(x)\)
• Compute the quotient polynomial:
  • \(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} ,\quad g^{r(s)} = \prod^{d} _{i=1} (g^{r_i(s)})^{v_i} ,\quad 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} ,\quad g^{\alpha r(s)} = \prod^{d} _{i=1} (g^{\alpha r _i(s)})^{v _i} ,\quad 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),\quad e(g^{r}, g^{\alpha}) = e(g^{r'}, g),\quad 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)\)

Implementation

#![allow(unused)]
fn main() {
#[derive(Debug, Clone)]
pub struct ProofKey1 {
    g1_ell_i_vec: Vec<G1Point>,
    g2_r_i_vec: Vec<G2Point>,
    g1_o_i_vec: Vec<G1Point>,
    g1_alpha_ell_i_vec: Vec<G1Point>,
    g2_alpha_r_i_vec: Vec<G2Point>,
    g1_alpha_o_i_vec: Vec<G1Point>,
    g1_sj_vec: Vec<G1Point>,
}

#[derive(Debug, Clone)]
pub struct VerificationKey1 {
    g1_alpha: G1Point,
    g2_alpha: G2Point,
    g2_t_s: G2Point,
}

#[derive(Debug, Clone)]
pub struct Proof1 {
    g1_ell: G1Point,
    g2_r: G2Point,
    g1_o: G1Point,
    g1_ell_prime: G1Point,
    g2_r_prime: G2Point,
    g1_o_prime: G1Point,
    g1_h: G1Point,
}

pub fn setup(g1: &G1Point, g2: &G2Point, qap: &QAP<FqOrder>) -> (ProofKey1, VerificationKey1) {
    let s = FqOrder::random_element(&[]);
    let alpha = FqOrder::random_element(&[]);

    (
        ProofKey1 {
            g1_ell_i_vec: generate_challenge_vec(g1, &qap.ell_i_vec, &s),
            g2_r_i_vec: generate_challenge_vec(g2, &qap.r_i_vec, &s),
            g1_o_i_vec: generate_challenge_vec(g1, &qap.o_i_vec, &s),
            g1_alpha_ell_i_vec: generate_alpha_challenge_vec(g1, &qap.ell_i_vec, &s, &alpha),
            g2_alpha_r_i_vec: generate_alpha_challenge_vec(g2, &qap.r_i_vec, &s, &alpha),
            g1_alpha_o_i_vec: generate_alpha_challenge_vec(g1, &qap.o_i_vec, &s, &alpha),
            g1_sj_vec: generate_s_powers(g1, &s, qap.m),
        },
        VerificationKey1 {
            g1_alpha: g1 * alpha.get_value(),
            g2_alpha: g2 * alpha.get_value(),
            g2_t_s: g2 * qap.t.eval(&s).sanitize().get_value(),
        },
    )
}

pub fn prove(assignment: &Vec<FqOrder>, proof_key: &ProofKey1, qap: &QAP<FqOrder>) -> Proof1 {
    Proof1 {
        g1_ell: accumulate_curve_points(&proof_key.g1_ell_i_vec, assignment),
        g2_r: accumulate_curve_points(&proof_key.g2_r_i_vec, assignment),
        g1_o: accumulate_curve_points(&proof_key.g1_o_i_vec, assignment),
        g1_ell_prime: accumulate_curve_points(&proof_key.g1_alpha_ell_i_vec, assignment),
        g2_r_prime: accumulate_curve_points(&proof_key.g2_alpha_r_i_vec, assignment),
        g1_o_prime: accumulate_curve_points(&proof_key.g1_alpha_o_i_vec, assignment),
        g1_h: get_h(qap, assignment).eval_with_powers_on_curve(&proof_key.g1_sj_vec),
    }
}

pub fn verify(
    g1: &G1Point,
    g2: &G2Point,
    proof: &Proof1,
    verification_key: &VerificationKey1,
) -> bool {
    let pairing1 = optimal_ate_pairing(&proof.g1_ell, &verification_key.g2_alpha);
    let pairing2 = optimal_ate_pairing(&proof.g1_ell_prime, &g2);
    if pairing1 != pairing2 {
        return false;
    }

    let pairing3 = optimal_ate_pairing(&verification_key.g1_alpha, &proof.g2_r);
    let pairing4 = optimal_ate_pairing(&g1, &proof.g2_r_prime);
    if pairing3 != pairing4 {
        return false;
    }

    let pairing5 = optimal_ate_pairing(&proof.g1_o, &verification_key.g2_alpha);
    let pairing6 = optimal_ate_pairing(&proof.g1_o_prime, &g2);
    if pairing5 != pairing6 {
        return false;
    }

    let pairing7 = optimal_ate_pairing(&proof.g1_ell, &proof.g2_r);
    let pairing8 = optimal_ate_pairing(&proof.g1_h, &verification_key.g2_t_s);
    let pairing9 = optimal_ate_pairing(&proof.g1_o, &g2);

    pairing7 == pairing8 * pairing9
}
}

#![allow(unused)]
fn main() {
pub fn generate_challenge_vec<F1: Field, F2: Field, E: EllipticCurve>(
    point: &EllipticCurvePoint<F1, E>,
    poly_vec: &[Polynomial<F2>],
    s: &F2,
) -> Vec<EllipticCurvePoint<F1, E>> {
    poly_vec
        .iter()
        .map(|poly| point.mul_ref(poly.eval(s).sanitize().get_value()))
        .collect()
}

pub fn generate_alpha_challenge_vec<F1: Field, F2: Field, E: EllipticCurve>(
    point: &EllipticCurvePoint<F1, E>,
    poly_vec: &[Polynomial<F2>],
    s: &F2,
    alpha: &F2,
) -> Vec<EllipticCurvePoint<F1, E>> {
    poly_vec
        .iter()
        .map(|poly| point.mul_ref((alpha.mul_ref(&poly.eval(s).sanitize())).get_value()))
        .collect()
}

pub fn generate_s_powers<F1: Field, F2: Field, E: EllipticCurve>(
    point: &EllipticCurvePoint<F1, E>,
    s: &F2,
    m: usize,
) -> Vec<EllipticCurvePoint<F1, E>> {
    let mut powers = Vec::with_capacity(m + 1);
    let mut current = F2::one();
    for _ in 0..=m {
        powers.push(point.mul_ref(current.get_value()));
        current = current * s.clone();
    }
    powers
}

pub fn accumulate_curve_points<F1: Field, F2: Field, E: EllipticCurve>(
    g_vec: &[EllipticCurvePoint<F1, E>],
    assignment: &[F2],
) -> EllipticCurvePoint<F1, E> {
    g_vec.iter().zip(assignment.iter()).fold(
        EllipticCurvePoint::<F1, E>::point_at_infinity(),
        |acc, (g, &ref a)| acc + g.mul_ref(a.get_value()),
    )
}

pub fn accumulate_polynomials<F: Field>(
    poly_vec: &[Polynomial<F>],
    assignment: &[F],
) -> Polynomial<F> {
    poly_vec
        .iter()
        .zip(assignment.iter())
        .fold(Polynomial::<F>::zero(), |acc, (poly, &ref a)| {
            acc + poly.clone() * a.clone()
        })
}

pub fn get_h<F: Field>(qap: &QAP<F>, assignment: &Vec<F>) -> Polynomial<F> {
    let ell = accumulate_polynomials(&qap.ell_i_vec, assignment);
    let r = accumulate_polynomials(&qap.r_i_vec, assignment);
    let o = accumulate_polynomials(&qap.o_i_vec, assignment);
    (ell * r - o) / qap.t.clone()
}
}

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^{\ell(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 secret seeds 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),\quad r(x) = \sum_{i=1}^{d} v_i r_{i}(x),\quad o(x) = \sum_{i=1}^{d} v_i o_{i}(x)\)
• Compute the quotient polynomial:
  • \(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} ,\quad g^{r(s)} = \prod^{d} _{i=1} (g^{r_i(s)})^{v_i} ,\quad 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)\), \(\quad \) \(e(g^{r}, g^{\alpha_{r}}) = e(g^{r'}, g)\), \(\quad \) \(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)\)

Implementation

#![allow(unused)]
fn main() {
#[derive(Debug, Clone)]
pub struct ProofKey2 {
    g1_ell_i_vec: Vec<G1Point>,
    g2_r_i_vec: Vec<G2Point>,
    g1_o_i_vec: Vec<G1Point>,
    g1_alpha_ell_i_vec: Vec<G1Point>,
    g2_alpha_r_i_vec: Vec<G2Point>,
    g1_alpha_o_i_vec: Vec<G1Point>,
    g1_sj_vec: Vec<G1Point>,
}

#[derive(Debug, Clone)]
pub struct VerificationKey2 {
    g2_alpha_ell: G2Point,
    g1_alpha_r: G1Point,
    g2_alpha_o: G2Point,
    g2_t_s: G2Point,
}

#[derive(Debug, Clone)]
pub struct Proof2 {
    g1_ell: G1Point,
    g2_r: G2Point,
    g1_o: G1Point,
    g1_ell_prime: G1Point,
    g2_r_prime: G2Point,
    g1_o_prime: G1Point,
    g1_h: G1Point,
}

pub fn setup(g1: &G1Point, g2: &G2Point, qap: &QAP<FqOrder>) -> (ProofKey2, VerificationKey2) {
    let s = FqOrder::random_element(&[]);
    let alpha_ell = FqOrder::random_element(&[]);
    let alpha_r = FqOrder::random_element(&[]);
    let alpha_o = FqOrder::random_element(&[]);

    (
        ProofKey2 {
            g1_ell_i_vec: generate_challenge_vec(g1, &qap.ell_i_vec, &s),
            g2_r_i_vec: generate_challenge_vec(g2, &qap.r_i_vec, &s),
            g1_o_i_vec: generate_challenge_vec(g1, &qap.o_i_vec, &s),
            g1_alpha_ell_i_vec: generate_alpha_challenge_vec(g1, &qap.ell_i_vec, &s, &alpha_ell),
            g2_alpha_r_i_vec: generate_alpha_challenge_vec(g2, &qap.r_i_vec, &s, &alpha_r),
            g1_alpha_o_i_vec: generate_alpha_challenge_vec(g1, &qap.o_i_vec, &s, &alpha_o),
            g1_sj_vec: generate_s_powers(g1, &s, qap.m),
        },
        VerificationKey2 {
            g2_alpha_ell: g2 * alpha_ell.get_value(),
            g1_alpha_r: g1 * alpha_r.get_value(),
            g2_alpha_o: g2 * alpha_o.get_value(),
            g2_t_s: g2 * qap.t.eval(&s).sanitize().get_value(),
        },
    )
}

pub fn prove(assignment: &Vec<FqOrder>, proof_key: &ProofKey2, qap: &QAP<FqOrder>) -> Proof2 {
    Proof2 {
        g1_ell: accumulate_curve_points(&proof_key.g1_ell_i_vec, assignment),
        g2_r: accumulate_curve_points(&proof_key.g2_r_i_vec, assignment),
        g1_o: accumulate_curve_points(&proof_key.g1_o_i_vec, assignment),
        g1_ell_prime: accumulate_curve_points(&proof_key.g1_alpha_ell_i_vec, assignment),
        g2_r_prime: accumulate_curve_points(&proof_key.g2_alpha_r_i_vec, assignment),
        g1_o_prime: accumulate_curve_points(&proof_key.g1_alpha_o_i_vec, assignment),
        g1_h: get_h(qap, assignment).eval_with_powers_on_curve(&proof_key.g1_sj_vec),
    }
}

pub fn verify(
    g1: &G1Point,
    g2: &G2Point,
    proof: &Proof2,
    verification_key: &VerificationKey2,
) -> bool {
    let pairing1 = optimal_ate_pairing(&proof.g1_ell, &verification_key.g2_alpha_ell);
    let pairing2 = optimal_ate_pairing(&proof.g1_ell_prime, &g2);
    if pairing1 != pairing2 {
        return false;
    }

    let pairing3 = optimal_ate_pairing(&verification_key.g1_alpha_r, &proof.g2_r);
    let pairing4 = optimal_ate_pairing(&g1, &proof.g2_r_prime);
    if pairing3 != pairing4 {
        return false;
    }

    let pairing5 = optimal_ate_pairing(&proof.g1_o, &verification_key.g2_alpha_o);
    let pairing6 = optimal_ate_pairing(&proof.g1_o_prime, &g2);
    if pairing5 != pairing6 {
        return false;
    }

    let pairing7 = optimal_ate_pairing(&proof.g1_ell, &proof.g2_r);
    let pairing8 = optimal_ate_pairing(&proof.g1_h, &verification_key.g2_t_s);
    let pairing9 = optimal_ate_pairing(&proof.g1_o, &g2);

    pairing7 == pairing8 * pairing9
}
}

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.

#![allow(unused)]
fn main() {
pub fn inconsistent_variable_attack(
    assignment_ell: &Vec<FqOrder>,
    assignment_r: &Vec<FqOrder>,
    assignment_o: &Vec<FqOrder>,
    proof_key: &ProofKey2,
    qap: &QAP<FqOrder>,
) -> Proof2 {
    let ell = accumulate_polynomials(&qap.ell_i_vec, assignment_ell);
    let r = accumulate_polynomials(&qap.r_i_vec, assignment_r);
    let o = accumulate_polynomials(&qap.o_i_vec, assignment_o);
    let h = (ell * r - o) / qap.t.clone();

    Proof2 {
        g1_ell: accumulate_curve_points(&proof_key.g1_ell_i_vec, assignment_ell),
        g2_r: accumulate_curve_points(&proof_key.g2_r_i_vec, assignment_r),
        g1_o: accumulate_curve_points(&proof_key.g1_o_i_vec, assignment_o),
        g1_ell_prime: accumulate_curve_points(&proof_key.g1_alpha_ell_i_vec, assignment_ell),
        g2_r_prime: accumulate_curve_points(&proof_key.g2_alpha_r_i_vec, assignment_r),
        g1_o_prime: accumulate_curve_points(&proof_key.g1_alpha_o_i_vec, assignment_o),
        g1_h: h.eval_with_powers_on_curve(&proof_key.g1_sj_vec),
    }
}
}

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}\).
• 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]}\)
  • \(\{g^{\beta _{\ell} \ell _{i}(s) + \beta _{r} r _{i}(s) + \beta _{o} o _{i}(s)}\} _{i \in [d]}\)
• 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 secret seeds 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),\quad r(x) = \sum_{i=1}^{d} v_i r_{i}(x),\quad o(x) = \sum_{i=1}^{d} v_i o_{i}(x)\)
• Compute the quotient polynomial:
  • \(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} ,\quad g^{r(s)} = \prod^{d} _{i=1} (g^{r_i(s)})^{v_i} ,\quad 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),\quad e(g^{r}, g^{\alpha_{r}}) = e(g^{r'}, g),\quad 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)\)

Implementation

#![allow(unused)]
fn main() {
#[derive(Debug, Clone)]
pub struct ProofKey3 {
    g1_ell_i_vec: Vec<G1Point>,
    g2_r_i_vec: Vec<G2Point>,
    g1_o_i_vec: Vec<G1Point>,
    g1_alpha_ell_i_vec: Vec<G1Point>,
    g2_alpha_r_i_vec: Vec<G2Point>,
    g1_alpha_o_i_vec: Vec<G1Point>,
    g1_sj_vec: Vec<G1Point>,
    g1_checksum_vec: Vec<G1Point>,
}

#[derive(Debug, Clone)]
pub struct VerificationKey3 {
    g2_alpha_ell: G2Point,
    g1_alpha_r: G1Point,
    g2_alpha_o: G2Point,
    g2_beta_ell: G2Point,
    g1_beta_r: G1Point,
    g2_beta_o: G2Point,
    g2_t_s: G2Point,
}

#[derive(Debug, Clone)]
pub struct Proof3 {
    g1_ell: G1Point,
    g2_r: G2Point,
    g1_o: G1Point,
    g1_ell_prime: G1Point,
    g2_r_prime: G2Point,
    g1_o_prime: G1Point,
    g1_h: G1Point,
    g1_z: G1Point,
}

pub fn setup(g1: &G1Point, g2: &G2Point, qap: &QAP<FqOrder>) -> (ProofKey3, VerificationKey3) {
    let s = FqOrder::random_element(&[]);
    let alpha_ell = FqOrder::random_element(&[]);
    let alpha_r = FqOrder::random_element(&[]);
    let alpha_o = FqOrder::random_element(&[]);
    let beta_ell = FqOrder::random_element(&[]);
    let beta_r = FqOrder::random_element(&[]);
    let beta_o = FqOrder::random_element(&[]);

    let mut g1_checksum_vec = Vec::with_capacity(qap.d);

    for i in 0..qap.d {
        let ell_i_s = qap.ell_i_vec[i].eval(&s).sanitize();
        let r_i_s = qap.r_i_vec[i].eval(&s).sanitize();
        let o_i_s = qap.o_i_vec[i].eval(&s).sanitize();
        g1_checksum_vec.push(
            g1.mul_ref(
                ((beta_ell.mul_ref(&ell_i_s))
                    .add_ref(&beta_r.mul_ref(&r_i_s))
                    .add_ref(&beta_o.mul_ref(&o_i_s)))
                .get_value(),
            ),
        );
    }

    (
        ProofKey3 {
            g1_ell_i_vec: generate_challenge_vec(g1, &qap.ell_i_vec, &s),
            g2_r_i_vec: generate_challenge_vec(g2, &qap.r_i_vec, &s),
            g1_o_i_vec: generate_challenge_vec(g1, &qap.o_i_vec, &s),
            g1_alpha_ell_i_vec: generate_alpha_challenge_vec(g1, &qap.ell_i_vec, &s, &alpha_ell),
            g2_alpha_r_i_vec: generate_alpha_challenge_vec(g2, &qap.r_i_vec, &s, &alpha_r),
            g1_alpha_o_i_vec: generate_alpha_challenge_vec(g1, &qap.o_i_vec, &s, &alpha_o),
            g1_sj_vec: generate_s_powers(g1, &s, qap.m),
            g1_checksum_vec: g1_checksum_vec,
        },
        VerificationKey3 {
            g2_alpha_ell: g2 * alpha_ell.get_value(),
            g1_alpha_r: g1 * alpha_r.get_value(),
            g2_alpha_o: g2 * alpha_o.get_value(),
            g2_beta_ell: g2 * beta_ell.get_value(),
            g1_beta_r: g1 * beta_r.get_value(),
            g2_beta_o: g2 * beta_o.get_value(),
            g2_t_s: g2 * qap.t.eval(&s).sanitize().get_value(),
        },
    )
}

pub fn prove(assignment: &Vec<FqOrder>, proof_key: &ProofKey3, qap: &QAP<FqOrder>) -> Proof3 {
    Proof3 {
        g1_ell: accumulate_curve_points(&proof_key.g1_ell_i_vec, assignment),
        g2_r: accumulate_curve_points(&proof_key.g2_r_i_vec, assignment),
        g1_o: accumulate_curve_points(&proof_key.g1_o_i_vec, assignment),
        g1_ell_prime: accumulate_curve_points(&proof_key.g1_alpha_ell_i_vec, assignment),
        g2_r_prime: accumulate_curve_points(&proof_key.g2_alpha_r_i_vec, assignment),
        g1_o_prime: accumulate_curve_points(&proof_key.g1_alpha_o_i_vec, assignment),
        g1_h: get_h(qap, assignment).eval_with_powers_on_curve(&proof_key.g1_sj_vec),
        g1_z: accumulate_curve_points(&proof_key.g1_checksum_vec, assignment),
    }
}

pub fn verify(
    g1: &G1Point,
    g2: &G2Point,
    proof: &Proof3,
    verification_key: &VerificationKey3,
) -> bool {
    let pairing1 = optimal_ate_pairing(&proof.g1_ell, &verification_key.g2_alpha_ell);
    let pairing2 = optimal_ate_pairing(&proof.g1_ell_prime, &g2);
    if pairing1 != pairing2 {
        return false;
    }

    let pairing3 = optimal_ate_pairing(&verification_key.g1_alpha_r, &proof.g2_r);
    let pairing4 = optimal_ate_pairing(&g1, &proof.g2_r_prime);
    if pairing3 != pairing4 {
        return false;
    }

    let pairing5 = optimal_ate_pairing(&proof.g1_o, &verification_key.g2_alpha_o);
    let pairing6 = optimal_ate_pairing(&proof.g1_o_prime, &g2);
    if pairing5 != pairing6 {
        return false;
    }

    let pairing7 = optimal_ate_pairing(&proof.g1_ell, &proof.g2_r);
    let pairing8 = optimal_ate_pairing(&proof.g1_h, &verification_key.g2_t_s);
    let pairing9 = optimal_ate_pairing(&proof.g1_o, &g2);

    if pairing7 != pairing8 * pairing9 {
        return false;
    }

    let pairing10 = optimal_ate_pairing(&proof.g1_ell, &verification_key.g2_beta_ell);
    let pairing11 = optimal_ate_pairing(&verification_key.g1_beta_r, &proof.g2_r);
    let pairing12 = optimal_ate_pairing(&proof.g1_o, &verification_key.g2_beta_o);
    let pairing13 = optimal_ate_pairing(&proof.g1_z, &g2);

    pairing10 * pairing11 * pairing12 == pairing13
}
}

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\).
• 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]}\)
  • \(\{g^{\beta _{\ell} \ell _{i}(s) + \beta _{r} r _{i}(s) + \beta _{o} o _{i}(s)}\} _{i \in [d]}\)
• Verification Key:
  • \(g^{t(s)}, g^{\alpha_{\ell}},g^{\alpha_{r}},g^{\alpha_{o}}\) \(,g^{\eta}, g^{\beta_{\ell} \eta}, g^{\beta_{r} \eta}, g^{\beta_{o} \eta}\)
• After distribution, the original secret seeds 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),\quad r(x) = \sum_{i=1}^{d} v_i r_{i}(x),\quad o(x) = \sum_{i=1}^{d} v_i o_{i}(x)\)
• Compute the quotient polynomial:
  • \(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} ,\quad g^{r(s)} = \prod^{d} _{i=1} (g^{r_i(s)})^{v_i} ,\quad 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),\quad e(g^{r}, g^{\alpha_{r}}) = e(g^{r'}, g),\quad 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)\)

Implementation

#![allow(unused)]
fn main() {
#[derive(Debug, Clone)]
pub struct ProofKey4 {
    g1_ell_i_vec: Vec<G1Point>,
    g2_r_i_vec: Vec<G2Point>,
    g1_o_i_vec: Vec<G1Point>,
    g1_alpha_ell_i_vec: Vec<G1Point>,
    g2_alpha_r_i_vec: Vec<G2Point>,
    g1_alpha_o_i_vec: Vec<G1Point>,
    g1_sj_vec: Vec<G1Point>,
    g1_checksum_vec: Vec<G1Point>,
}

#[derive(Debug, Clone)]
pub struct VerificationKey4 {
    g2_alpha_ell: G2Point,
    g1_alpha_r: G1Point,
    g2_alpha_o: G2Point,
    g2_beta_ell_eta: G2Point,
    g1_beta_r_eta: G1Point,
    g2_beta_o_eta: G2Point,
    g2_t_s: G2Point,
    g2_eta: G2Point,
}

#[derive(Debug, Clone)]
pub struct Proof4 {
    g1_ell: G1Point,
    g2_r: G2Point,
    g1_o: G1Point,
    g1_ell_prime: G1Point,
    g2_r_prime: G2Point,
    g1_o_prime: G1Point,
    g1_h: G1Point,
    g1_z: G1Point,
}

pub fn setup(g1: &G1Point, g2: &G2Point, qap: &QAP<FqOrder>) -> (ProofKey4, VerificationKey4) {
    let s = FqOrder::random_element(&[]);
    let alpha_ell = FqOrder::random_element(&[]);
    let alpha_r = FqOrder::random_element(&[]);
    let alpha_o = FqOrder::random_element(&[]);
    let beta_ell = FqOrder::random_element(&[]);
    let beta_r = FqOrder::random_element(&[]);
    let beta_o = FqOrder::random_element(&[]);
    let eta = FqOrder::random_element(&[]);

    let mut g1_checksum_vec = Vec::with_capacity(qap.d);

    for i in 0..qap.d {
        let ell_i_s = qap.ell_i_vec[i].eval(&s).sanitize();
        let r_i_s = qap.r_i_vec[i].eval(&s).sanitize();
        let o_i_s = qap.o_i_vec[i].eval(&s).sanitize();
        g1_checksum_vec.push(
            g1.mul_ref(
                ((beta_ell.mul_ref(&ell_i_s))
                    .add_ref(&beta_r.mul_ref(&r_i_s))
                    .add_ref(&beta_o.mul_ref(&o_i_s)))
                .get_value(),
            ),
        );
    }

    (
        ProofKey4 {
            g1_ell_i_vec: generate_challenge_vec(g1, &qap.ell_i_vec, &s),
            g2_r_i_vec: generate_challenge_vec(g2, &qap.r_i_vec, &s),
            g1_o_i_vec: generate_challenge_vec(g1, &qap.o_i_vec, &s),
            g1_alpha_ell_i_vec: generate_alpha_challenge_vec(g1, &qap.ell_i_vec, &s, &alpha_ell),
            g2_alpha_r_i_vec: generate_alpha_challenge_vec(g2, &qap.r_i_vec, &s, &alpha_r),
            g1_alpha_o_i_vec: generate_alpha_challenge_vec(g1, &qap.o_i_vec, &s, &alpha_o),
            g1_sj_vec: generate_s_powers(g1, &s, qap.m),
            g1_checksum_vec: g1_checksum_vec,
        },
        VerificationKey4 {
            g2_alpha_ell: g2 * alpha_ell.get_value(),
            g1_alpha_r: g1 * alpha_r.get_value(),
            g2_alpha_o: g2 * alpha_o.get_value(),
            g2_beta_ell_eta: (g2 * beta_ell.get_value()) * eta.get_value(),
            g1_beta_r_eta: (g1 * beta_r.get_value()) * eta.get_value(),
            g2_beta_o_eta: (g2 * beta_o.get_value()) * eta.get_value(),
            g2_t_s: g2 * qap.t.eval(&s).sanitize().get_value(),
            g2_eta: g2 * eta.get_value(),
        },
    )
}

pub fn prove(assignment: &Vec<FqOrder>, proof_key: &ProofKey4, qap: &QAP<FqOrder>) -> Proof4 {
    Proof4 {
        g1_ell: accumulate_curve_points(&proof_key.g1_ell_i_vec, assignment),
        g2_r: accumulate_curve_points(&proof_key.g2_r_i_vec, assignment),
        g1_o: accumulate_curve_points(&proof_key.g1_o_i_vec, assignment),
        g1_ell_prime: accumulate_curve_points(&proof_key.g1_alpha_ell_i_vec, assignment),
        g2_r_prime: accumulate_curve_points(&proof_key.g2_alpha_r_i_vec, assignment),
        g1_o_prime: accumulate_curve_points(&proof_key.g1_alpha_o_i_vec, assignment),
        g1_h: get_h(qap, assignment).eval_with_powers_on_curve(&proof_key.g1_sj_vec),
        g1_z: accumulate_curve_points(&proof_key.g1_checksum_vec, assignment),
    }
}

pub fn verify(
    g1: &G1Point,
    g2: &G2Point,
    proof: &Proof4,
    verification_key: &VerificationKey4,
) -> bool {
    let pairing1 = optimal_ate_pairing(&proof.g1_ell, &verification_key.g2_alpha_ell);
    let pairing2 = optimal_ate_pairing(&proof.g1_ell_prime, &g2);
    if pairing1 != pairing2 {
        return false;
    }

    let pairing3 = optimal_ate_pairing(&verification_key.g1_alpha_r, &proof.g2_r);
    let pairing4 = optimal_ate_pairing(&g1, &proof.g2_r_prime);
    if pairing3 != pairing4 {
        return false;
    }

    let pairing5 = optimal_ate_pairing(&proof.g1_o, &verification_key.g2_alpha_o);
    let pairing6 = optimal_ate_pairing(&proof.g1_o_prime, &g2);
    if pairing5 != pairing6 {
        return false;
    }

    let pairing7 = optimal_ate_pairing(&proof.g1_ell, &proof.g2_r);
    let pairing8 = optimal_ate_pairing(&proof.g1_h, &verification_key.g2_t_s);
    let pairing9 = optimal_ate_pairing(&proof.g1_o, &g2);

    if pairing7 != pairing8 * pairing9 {
        return false;
    }

    let pairing10 = optimal_ate_pairing(&proof.g1_ell, &verification_key.g2_beta_ell_eta);
    let pairing11 = optimal_ate_pairing(&verification_key.g1_beta_r_eta, &proof.g2_r);
    let pairing12 = optimal_ate_pairing(&proof.g1_o, &verification_key.g2_beta_o_eta);
    let pairing13 = optimal_ate_pairing(&proof.g1_z, &verification_key.g2_eta);

    pairing10 * pairing11 * pairing12 == pairing13
}
}

Fifth Protocol: Pinocchio

The above protocol requires 13 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\), \(\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}}\)
• 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]}\)
  • \(\{g _{\ell}^{\beta \ell _{i}(s)} \cdot g _{r}^{\beta r _{i}(s)} \cdot g _{o}^{\beta o _{i}(s)}\} _{i \in [d]}\)
• Verification Key:
  • \(g _{o}^{t(s)}\) \(, g^{\alpha _{\ell}}, g^{\alpha _{r}}, g^{\alpha _{o}}, g^{\eta}\) \(,g^{\beta \eta}\)
• After distribution, the original secret seeds 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),\quad r(x) = \sum_{i=1}^{d} v_i r_{i}(x),\quad o(x) = \sum_{i=1}^{d} v_i o_{i}(x)\)
• Compute the quotient polynomial:
  • \(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}^{\ell_i(s)})^{v _i} ,\quad g^{r(s)} = \prod^{d} _{i=1} (g _{r}^{r_i(s)})^{v_i} ,\quad g^{o(s)} = \prod^{d} _{i=1} (g _{o}^{o _i(s)})^{v _i} \)
• Evaluate each shifted polynomial at \(s\):
  • \(g^{\alpha _{\ell} \ell(s)} = \prod^{d} _{i=1} (g _{\ell}^{\alpha _{\ell} \ell _i(s)})^{v _i} ,g^{\alpha _{r} r(s)} = \prod^{d} _{i=1} (g _{r}^{\alpha _{r} r _i(s)})^{v _i} ,g^{\alpha _{o} o(s)} = \prod^{d} _{i=1} (g _{o}^{\alpha _{o} o _i(s)})^{v _i} \)
• Evaluate each consistency polynomial at \(s\):
  • \(g^{z(s)} = \prod^{d}_{i=1} (g _{\ell}^{\beta \ell _{i}(s)} \cdot g _{r}^{\beta r _{i}(s)} \cdot g _{o}^{\beta 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}^{\ell}, g _{r}^r, g _{o}^o, g _{\ell}^{\ell'}, g _{r}^{r'}, g _{o}^{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}, g^{\beta \eta}) = e(g^{z}, g^{\eta})\)
  • (Alternative for the asymmetric pairing: \(e(g _{\ell}^{\ell} \cdot g _{o}^{o}, g^{\beta \eta}) \cdot e(g^{\beta \eta}, g _{r}^{r}) = e(g^{z}, g^{\eta})\))
• Validity check
  • \(e(g _{\ell}^{\ell}, g _{r}^{r}) = e(g _{o}^t,g^h) \cdot e(g _{o}^o, g)\)

This protocol reduces two pairing operations when using symmetric pairings. However, with asymmetric pairings, one additional pairing is required because \(g _{r}^{r}\) is derived from the generator of the second group, \(\mathscr{g} _2\), while \(g _{\ell}^{\ell}\) annd \(g _{o}^{o}\) are derived from the generator of the first group, \(\mathscr{g} _1\).

Implementation

#![allow(unused)]
fn main() {
#[derive(Debug, Clone)]
pub struct ProofKey5 {
    g1_ell_i_vec: Vec<G1Point>,
    g2_r_i_vec: Vec<G2Point>,
    g1_o_i_vec: Vec<G1Point>,
    g1_alpha_ell_i_vec: Vec<G1Point>,
    g2_alpha_r_i_vec: Vec<G2Point>,
    g1_alpha_o_i_vec: Vec<G1Point>,
    g1_sj_vec: Vec<G1Point>,
    g1_checksum_vec: Vec<G1Point>,
}

#[derive(Debug, Clone)]
pub struct VerificationKey5 {
    g2_alpha_ell: G2Point,
    g1_alpha_r: G1Point,
    g2_alpha_o: G2Point,
    g1_beta_eta: G1Point,
    g2_beta_eta: G2Point,
    g2_t_s: G2Point,
    g2_eta: G2Point,
}

#[derive(Debug, Clone)]
pub struct Proof5 {
    g1_ell: G1Point,
    g2_r: G2Point,
    g1_o: G1Point,
    g1_ell_prime: G1Point,
    g2_r_prime: G2Point,
    g1_o_prime: G1Point,
    g1_h: G1Point,
    g1_z: G1Point,
}

pub fn setup(g1: &G1Point, g2: &G2Point, qap: &QAP<FqOrder>) -> (ProofKey5, VerificationKey5) {
    let s = FqOrder::random_element(&[]);
    let alpha_ell = FqOrder::random_element(&[]);
    let alpha_r = FqOrder::random_element(&[]);
    let alpha_o = FqOrder::random_element(&[]);
    let beta = FqOrder::random_element(&[]);
    let eta = FqOrder::random_element(&[]);
    let rho_ell = FqOrder::random_element(&[]);
    let rho_r = FqOrder::random_element(&[]);
    let rho_o = rho_ell.mul_ref(&rho_r);

    let g1_ell = g1 * rho_ell.get_value();
    let g1_r = g1 * rho_r.get_value();
    let g2_r = g2 * rho_r.get_value();
    let g1_o = g1 * rho_o.get_value();
    let g2_o = g2 * rho_o.get_value();

    let mut g1_checksum_vec = Vec::with_capacity(qap.d);

    for i in 0..qap.d {
        let ell_i_s = qap.ell_i_vec[i].eval(&s).sanitize();
        let r_i_s = qap.r_i_vec[i].eval(&s).sanitize();
        let o_i_s = qap.o_i_vec[i].eval(&s).sanitize();
        g1_checksum_vec.push(
            &g1_ell * beta.mul_ref(&ell_i_s).get_value()
                + &g1_r * beta.mul_ref(&r_i_s).get_value()
                + &g1_o * beta.mul_ref(&o_i_s).get_value(),
        );
    }

    (
        ProofKey5 {
            g1_ell_i_vec: generate_challenge_vec(&g1_ell, &qap.ell_i_vec, &s),
            g2_r_i_vec: generate_challenge_vec(&g2_r, &qap.r_i_vec, &s),
            g1_o_i_vec: generate_challenge_vec(&g1_o, &qap.o_i_vec, &s),
            g1_alpha_ell_i_vec: generate_alpha_challenge_vec(
                &g1_ell,
                &qap.ell_i_vec,
                &s,
                &alpha_ell,
            ),
            g2_alpha_r_i_vec: generate_alpha_challenge_vec(&g2_r, &qap.r_i_vec, &s, &alpha_r),
            g1_alpha_o_i_vec: generate_alpha_challenge_vec(&g1_o, &qap.o_i_vec, &s, &alpha_o),
            g1_sj_vec: generate_s_powers(&g1, &s, qap.m),
            g1_checksum_vec: g1_checksum_vec,
        },
        VerificationKey5 {
            g2_alpha_ell: g2 * alpha_ell.get_value(),
            g1_alpha_r: g1 * alpha_r.get_value(),
            g2_alpha_o: g2 * alpha_o.get_value(),
            g1_beta_eta: g1 * beta.get_value() * eta.get_value(),
            g2_beta_eta: g2 * beta.get_value() * eta.get_value(),
            g2_t_s: g2_o * qap.t.eval(&s).sanitize().get_value(),
            g2_eta: g2 * eta.get_value(),
        },
    )
}

pub fn prove(assignment: &Vec<FqOrder>, proof_key: &ProofKey5, qap: &QAP<FqOrder>) -> Proof5 {
    Proof5 {
        g1_ell: accumulate_curve_points(&proof_key.g1_ell_i_vec, assignment),
        g2_r: accumulate_curve_points(&proof_key.g2_r_i_vec, assignment),
        g1_o: accumulate_curve_points(&proof_key.g1_o_i_vec, assignment),
        g1_ell_prime: accumulate_curve_points(&proof_key.g1_alpha_ell_i_vec, assignment),
        g2_r_prime: accumulate_curve_points(&proof_key.g2_alpha_r_i_vec, assignment),
        g1_o_prime: accumulate_curve_points(&proof_key.g1_alpha_o_i_vec, assignment),
        g1_h: get_h(qap, assignment).eval_with_powers_on_curve(&proof_key.g1_sj_vec),
        g1_z: accumulate_curve_points(&proof_key.g1_checksum_vec, assignment),
    }
}

pub fn verify(
    g1: &G1Point,
    g2: &G2Point,
    proof: &Proof5,
    verification_key: &VerificationKey5,
) -> bool {
    let pairing1 = optimal_ate_pairing(&proof.g1_ell, &verification_key.g2_alpha_ell);
    let pairing2 = optimal_ate_pairing(&proof.g1_ell_prime, &g2);
    if pairing1 != pairing2 {
        return false;
    }

    let pairing3 = optimal_ate_pairing(&verification_key.g1_alpha_r, &proof.g2_r);
    let pairing4 = optimal_ate_pairing(&g1, &proof.g2_r_prime);
    if pairing3 != pairing4 {
        return false;
    }

    let pairing5 = optimal_ate_pairing(&proof.g1_o, &verification_key.g2_alpha_o);
    let pairing6 = optimal_ate_pairing(&proof.g1_o_prime, &g2);
    if pairing5 != pairing6 {
        return false;
    }

    let pairing7 = optimal_ate_pairing(&proof.g1_ell, &proof.g2_r);
    let pairing8 = optimal_ate_pairing(&proof.g1_h, &verification_key.g2_t_s);
    let pairing9 = optimal_ate_pairing(&proof.g1_o, &g2);

    if pairing7 != pairing8 * pairing9 {
        return false;
    }

    let pairing10 = optimal_ate_pairing(
        &proof.g1_ell.add_ref(&proof.g1_o),
        &verification_key.g2_beta_eta,
    );
    let pairing11 = optimal_ate_pairing(&verification_key.g1_beta_eta, &proof.g2_r);
    let pairing12 = optimal_ate_pairing(&proof.g1_z, &verification_key.g2_eta);

    pairing10 * pairing11 == pairing12
}
}