A polynomial is a fundamental concept in algebra, expressed as a linear combination of variables and coefficients, denoted as:
\[p(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_d x^d\]
where \( a_i \) are the coefficients, and \( d \) is the degree of the polynomial. Polynomials are widely used in mathematics, physics, and engineering, playing a particularly central role in cryptography. Their composability and simple algebraic properties make them foundational to many cryptographic techniques and protocols.
In cryptography, especially in coding theory, zero-knowledge proofs, and encryption algorithms, polynomials are critical. For instance, in Reed-Solomon (RS) encoding, polynomials are used to encode data into codewords, facilitating error detection and correction. The algebraic properties of polynomials ensure that even if data is affected by noise during transmission, the original data can be recovered through decoding, which is vital for maintaining data integrity.
Moreover, during the preprocessing phase of zero-knowledge proofs, arithmetic circuits are often reduced to polynomial representations. Polynomial operations are performed interactively in protocols like PIOP (Polynomial Interactive Oracle Proofs) to prove the correctness of specific equations. The operability and complexity of polynomials ensure the robustness of cryptographic systems while allowing efficient computation and verification.
Low-degree polynomials are highly significant in cryptography, particularly in zero-knowledge proofs and verifiable computation. Their simplicity and computational efficiency make them extremely practical in proof systems. One key goal of proof systems is to verify the correctness of complex computations quickly. Low-degree polynomials significantly reduce computational costs in this context.
For instance, in zk-SNARKs (Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge), low-degree polynomials are used for generating and verifying proofs. Their low degree ensures that verifiers can efficiently validate computation results without revealing the underlying data. This low-degree property not only accelerates the verification process but also minimizes resource consumption during verification.
Additionally, in Reed-Solomon codes, low-degree testing is crucial for verifying whether a polynomial remains low-degree, ensuring data integrity and enabling error detection and correction during transmission. The robustness and reliability of low-degree polynomials make them indispensable tools in proof systems.
In summary, the simplicity and efficiency of low-degree polynomials make them critical for building secure, high-performance proof systems. By leveraging low-degree polynomials, proof systems can ensure security, improve computational efficiency, and reduce system complexity, demonstrating superior performance in real-world applications.
A group is a set with a binary operation defined on it that satisfies specific properties. For example, modular arithmetic under \( \mod p \) can be abstracted into a finite field \( \mathbb{F}_p \), where the elements are non-negative integers \( 0, 1, \dots, p-1 \). This section focuses on the concepts of groups and finite fields.
A group is an algebraic structure consisting of a set and a binary operation on the set. A group \( G \) must satisfy the following properties:
Example: Modular Group \( \mathbb{Z}_{17}^* \)
Consider the set \( \mathbb{Z}_{17}^* = \{1, 2, 3, \dots, 16\} \) with multiplication modulo 17. For any \( a, b \in \mathbb{Z}_{17}^* \), the operation \( ab \mod 17 \) still belongs to \( \mathbb{Z}_{17}^* \). This set forms a group under multiplication, with the identity element being 1 and the inverse being the multiplicative inverse.
A finite field is a field with a finite number of elements, usually denoted as \( \mathbb{F}_q \), where \( q \) is a prime or a power of a prime. In a finite field, addition and multiplication each form a group.
Example: Field \( \mathbb{F}_{17} \)
Consider the finite field \( \mathbb{F}_{17} = \{0, 1, 2, \dots, 16\} \). In this field, addition and multiplication each form groups. For instance, the multiplicative inverse of 5 is 7, as \( 5 \times 7 \equiv 1 \mod 17 \).
A subgroup is a subset of a group that itself forms a group under the same operation. Let \( G \) be a group and \( H \) be a non-empty subset of \( G \). If \( H \) is closed under the operation of \( G \) and satisfies all four group properties, then \( H \) is called a \textbf{subgroup} of \( G \).
Example: Coset in the Multiplicative Group Modulo 17 \( \left( \mathbb{Z}_{17}^* \right)
Consider a subgroup \( H = \{1, 4, 16\} \) of \( \mathbb{Z}_{17}^* \). This set is closed under multiplication modulo 17 and satisfies all group properties, making it a valid subgroup.
A coset is a way to partition a group using its subgroups. Let \( H \) be a subgroup of a group \( G \). For any element \( g \in G \), the left coset \( gH \) and the right coset \( Hg \) are defined as:
- Left Coset: \( gH = \{ gh \mid h \in H \} \)
- Right Coset: \( Hg = \{ hg \mid h \in H \} \)
Example: Coset in the Multiplicative Group Modulo 17 \( \left( \mathbb{Z}_{17}^* \right) \)
For an element 3 in \( \mathbb{Z}_{17}^* \) and the subgroup \( H = \{1, 4, 16\} \), the left coset \( 3H = \{3, 12, 14\} \) represents a partition of the subgroup into different equivalence classes.
Cyclic groups and roots of unity are commonly used concepts in zero-knowledge proofs. Their definitions and specific examples are as follows:
A cyclic group is a group that can be generated by a single element. If there exists an element \( g \in G \) such that every element in \( G \) can be expressed as a power of \( g \), i.e., \( G = \{ g^n \mid n \in \mathbb{Z} \} \), then \( G \) is called a cyclic group.
Example: Cyclic Group in \( \mathbb{Z}_{17}^* \)
In \( \mathbb{Z}_{17}^* \), the element 3 can generate a cyclic group:
\[\{ 3^0, 3^1, 3^2, \dots, 3^{15} \} = \{ 1, 3, 9, 10, 13, 5, 15, 11, 16, 14, 8, 7, 4, 12, 2, 6 \}\]
A root of unity is a complex number that, when raised to a specific positive integer power \( n \), equals 1. Specifically, a root of unity satisfies \( g^n = 1 \). The set of \( n \)-th roots of unity forms a cyclic group under multiplication in the complex plane.
Example: Root of Unity in \( \mathbb{F}_{17} \)
In the finite field \( \mathbb{F}_{17} \), the element 3 is a primitive root, meaning \( 3^{16} \equiv 1 \mod 17 \) and \( 3^k \) generates all non-zero elements of \( \mathbb{F}_{17} \), forming a cyclic group.
Additionally, we introduce several theorems:
In FRI (Fast Reed-Solomon Interactive Oracle Proofs of Proximity), large primes such as \( p = 2^{64} - 2^{32} + 1 \) are typically chosen. These primes are known as Goldilocks primes. As previously mentioned, if a cyclic subgroup has order \( n \) (i.e., containing \( n \) elements), then \( n \) must divide \( p-1 \).
For \( p = 2^{64} - 2^{32} + 1 \), we have \( p-1 = 2^{64} - 2^{32} \). Therefore, a cyclic subgroup can have an order \( n = 2, 2^2, 2^3, \dots, 2^{32} \). FRI can perform low-degree tests on powers of 2, perfectly matching a complete binary tree with \( 2^k \) leaf nodes.
Reed-Solomon (RS) codes are a class of non-binary linear error-correcting codes widely used in various applications such as CDs, satellite communications, QR codes, and hard drives for error detection and correction. Given a set of size \( n \) where \( n > d \), an RS code operates on a degree \( d \) polynomial \( p(X) \) to construct a codeword of length \( n \), defined as follows:
Given a degree \( d \) polynomial \( p(X) \) and a set of size \( n \):
$Ω = \{ω, ω^2, ..., ω^n\}$
The RS encoding is defined as $ \{p(\omega^i)\}_{i \in [n]} $
FRI is primarily used to check whether a given polynomial \( f \) exceeds a maximum degree \( d \). It leverages the three main properties of RS codes mentioned above to iteratively reduce the problem of verifying the degree of \( f \) to checking whether a folded polynomial \( f_{\text{fold}} \) has a degree at most \( \frac{d}{2} \), ultimately reducing it to a constant-level verification problem. We will focus on the execution flow and underlying principles of FRI in subsequent sections.
During the execution of FRI, the prover must first commit to a polynomial \( P \). When opening specific points of \( P \), the prover must simultaneously provide the Merkle path for that point as a Merkle Proof.
The above figure illustrates the Merkle commitment of a polynomial \( P(X) \) over \( X = \{1, 2, 3, 4, 5, 6, 7, 8\} \). The Merkle tree is built starting from the leaf nodes, where typically the hash of two adjacent child nodes forms the parent node. This process recurses upwards. The specific Merkle tree construction in the figure is as follows:
1. Generate First-Level Intermediate Nodes:
- Start with the 8 leaf nodes \( P_1, P_2, P_3, P_4, P_5, P_6, P_7, P_8 \).
- Perform hashing on adjacent leaf nodes to generate four intermediate nodes:
\[\begin{gather*}A_1 = \text{Hash}(P_1, P_2) \\A_2 = \text{Hash}(P_3, P_4) \\A_3 = \text{Hash}(P_5, P_6) \\A_4 = \text{Hash}(P_7, P_8)\end{gather*}\]
2. Generate Second-Level Intermediate Nodes: - Perform hashing on the first-level intermediate nodes to generate two higher-level nodes: \[ B_1 = \text{Hash}(A_1, A_2) \] \[ B_2 = \text{Hash}(A_3, A_4) \]
3. Generate Root Node: - Finally, hash the second-level nodes to generate the root node: \[ \text{Root} = \text{Hash}(B_1, B_2) \]
In the diagram, the blue-highlighted nodes represent the Merkle Proof corresponding to opening \( P_1 \). The prover retains the entire tree (including all root and leaf nodes), while the verifier only retains the root node (in this example, the Root). If the prover wants to open \( P_1 \), they need to provide the corresponding Merkle path as follows:
1. Compute First-Level Hashes:
- Use \( P_1 \) and \( P_2 \) to compute \( A_1 \): \[ A_1 = \text{Hash}(P_1, P_2) \]
- During the proof process, \( P_2 \) is the first node that needs to be provided.
2. Compute Second-Level Hashes:
- Use \( A_1 \) and \( A_2 \) to compute \( B_1 \): \[ B_1 = \text{Hash}(A_1, A_2)\]
- During the proof process, \( A_2 \) is the second node that needs to be provided.
3. Compute Root Node:
- Use \( B_1 \) and \( B_2 \) to compute the root node: \[ \text{Root} = \text{Hash}(B_1, B_2) \]
- During the proof process, \( B_2 \) is the third node that needs to be provided.
In the figure, the blue-highlighted nodes are the Merkle Proof for opening \( P_1 \). The verifier only needs to recompute the hash functions on these Merkle Proof nodes and check if they match the Root to verify that \( P_1 \) is indeed part of the Merkle tree.
1. Low Computational Overhead: Only requires efficient operations like hash functions.
2. Small Proof Size: 2. Assuming a tree with \( d \) leaf nodes, only a proof of size \( \log d \) needs to be submitted.
Subscribe to the ZKM Blog to stay updated with the latest research by ZKM. If you have any questions, you can contact the ZKM team on discord: discord.com/invite/zkm
A polynomial is a fundamental concept in algebra, expressed as a linear combination of variables and coefficients, denoted as:
\[p(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_d x^d\]
where \( a_i \) are the coefficients, and \( d \) is the degree of the polynomial. Polynomials are widely used in mathematics, physics, and engineering, playing a particularly central role in cryptography. Their composability and simple algebraic properties make them foundational to many cryptographic techniques and protocols.
In cryptography, especially in coding theory, zero-knowledge proofs, and encryption algorithms, polynomials are critical. For instance, in Reed-Solomon (RS) encoding, polynomials are used to encode data into codewords, facilitating error detection and correction. The algebraic properties of polynomials ensure that even if data is affected by noise during transmission, the original data can be recovered through decoding, which is vital for maintaining data integrity.
Moreover, during the preprocessing phase of zero-knowledge proofs, arithmetic circuits are often reduced to polynomial representations. Polynomial operations are performed interactively in protocols like PIOP (Polynomial Interactive Oracle Proofs) to prove the correctness of specific equations. The operability and complexity of polynomials ensure the robustness of cryptographic systems while allowing efficient computation and verification.
Low-degree polynomials are highly significant in cryptography, particularly in zero-knowledge proofs and verifiable computation. Their simplicity and computational efficiency make them extremely practical in proof systems. One key goal of proof systems is to verify the correctness of complex computations quickly. Low-degree polynomials significantly reduce computational costs in this context.
For instance, in zk-SNARKs (Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge), low-degree polynomials are used for generating and verifying proofs. Their low degree ensures that verifiers can efficiently validate computation results without revealing the underlying data. This low-degree property not only accelerates the verification process but also minimizes resource consumption during verification.
Additionally, in Reed-Solomon codes, low-degree testing is crucial for verifying whether a polynomial remains low-degree, ensuring data integrity and enabling error detection and correction during transmission. The robustness and reliability of low-degree polynomials make them indispensable tools in proof systems.
In summary, the simplicity and efficiency of low-degree polynomials make them critical for building secure, high-performance proof systems. By leveraging low-degree polynomials, proof systems can ensure security, improve computational efficiency, and reduce system complexity, demonstrating superior performance in real-world applications.
A group is a set with a binary operation defined on it that satisfies specific properties. For example, modular arithmetic under \( \mod p \) can be abstracted into a finite field \( \mathbb{F}_p \), where the elements are non-negative integers \( 0, 1, \dots, p-1 \). This section focuses on the concepts of groups and finite fields.
A group is an algebraic structure consisting of a set and a binary operation on the set. A group \( G \) must satisfy the following properties:
Example: Modular Group \( \mathbb{Z}_{17}^* \)
Consider the set \( \mathbb{Z}_{17}^* = \{1, 2, 3, \dots, 16\} \) with multiplication modulo 17. For any \( a, b \in \mathbb{Z}_{17}^* \), the operation \( ab \mod 17 \) still belongs to \( \mathbb{Z}_{17}^* \). This set forms a group under multiplication, with the identity element being 1 and the inverse being the multiplicative inverse.
A finite field is a field with a finite number of elements, usually denoted as \( \mathbb{F}_q \), where \( q \) is a prime or a power of a prime. In a finite field, addition and multiplication each form a group.
Example: Field \( \mathbb{F}_{17} \)
Consider the finite field \( \mathbb{F}_{17} = \{0, 1, 2, \dots, 16\} \). In this field, addition and multiplication each form groups. For instance, the multiplicative inverse of 5 is 7, as \( 5 \times 7 \equiv 1 \mod 17 \).
A subgroup is a subset of a group that itself forms a group under the same operation. Let \( G \) be a group and \( H \) be a non-empty subset of \( G \). If \( H \) is closed under the operation of \( G \) and satisfies all four group properties, then \( H \) is called a \textbf{subgroup} of \( G \).
Example: Coset in the Multiplicative Group Modulo 17 \( \left( \mathbb{Z}_{17}^* \right)
Consider a subgroup \( H = \{1, 4, 16\} \) of \( \mathbb{Z}_{17}^* \). This set is closed under multiplication modulo 17 and satisfies all group properties, making it a valid subgroup.
A coset is a way to partition a group using its subgroups. Let \( H \) be a subgroup of a group \( G \). For any element \( g \in G \), the left coset \( gH \) and the right coset \( Hg \) are defined as:
- Left Coset: \( gH = \{ gh \mid h \in H \} \)
- Right Coset: \( Hg = \{ hg \mid h \in H \} \)
Example: Coset in the Multiplicative Group Modulo 17 \( \left( \mathbb{Z}_{17}^* \right) \)
For an element 3 in \( \mathbb{Z}_{17}^* \) and the subgroup \( H = \{1, 4, 16\} \), the left coset \( 3H = \{3, 12, 14\} \) represents a partition of the subgroup into different equivalence classes.
Cyclic groups and roots of unity are commonly used concepts in zero-knowledge proofs. Their definitions and specific examples are as follows:
A cyclic group is a group that can be generated by a single element. If there exists an element \( g \in G \) such that every element in \( G \) can be expressed as a power of \( g \), i.e., \( G = \{ g^n \mid n \in \mathbb{Z} \} \), then \( G \) is called a cyclic group.
Example: Cyclic Group in \( \mathbb{Z}_{17}^* \)
In \( \mathbb{Z}_{17}^* \), the element 3 can generate a cyclic group:
\[\{ 3^0, 3^1, 3^2, \dots, 3^{15} \} = \{ 1, 3, 9, 10, 13, 5, 15, 11, 16, 14, 8, 7, 4, 12, 2, 6 \}\]
A root of unity is a complex number that, when raised to a specific positive integer power \( n \), equals 1. Specifically, a root of unity satisfies \( g^n = 1 \). The set of \( n \)-th roots of unity forms a cyclic group under multiplication in the complex plane.
Example: Root of Unity in \( \mathbb{F}_{17} \)
In the finite field \( \mathbb{F}_{17} \), the element 3 is a primitive root, meaning \( 3^{16} \equiv 1 \mod 17 \) and \( 3^k \) generates all non-zero elements of \( \mathbb{F}_{17} \), forming a cyclic group.
Additionally, we introduce several theorems:
In FRI (Fast Reed-Solomon Interactive Oracle Proofs of Proximity), large primes such as \( p = 2^{64} - 2^{32} + 1 \) are typically chosen. These primes are known as Goldilocks primes. As previously mentioned, if a cyclic subgroup has order \( n \) (i.e., containing \( n \) elements), then \( n \) must divide \( p-1 \).
For \( p = 2^{64} - 2^{32} + 1 \), we have \( p-1 = 2^{64} - 2^{32} \). Therefore, a cyclic subgroup can have an order \( n = 2, 2^2, 2^3, \dots, 2^{32} \). FRI can perform low-degree tests on powers of 2, perfectly matching a complete binary tree with \( 2^k \) leaf nodes.
Reed-Solomon (RS) codes are a class of non-binary linear error-correcting codes widely used in various applications such as CDs, satellite communications, QR codes, and hard drives for error detection and correction. Given a set of size \( n \) where \( n > d \), an RS code operates on a degree \( d \) polynomial \( p(X) \) to construct a codeword of length \( n \), defined as follows:
Given a degree \( d \) polynomial \( p(X) \) and a set of size \( n \):
$Ω = \{ω, ω^2, ..., ω^n\}$
The RS encoding is defined as $ \{p(\omega^i)\}_{i \in [n]} $
FRI is primarily used to check whether a given polynomial \( f \) exceeds a maximum degree \( d \). It leverages the three main properties of RS codes mentioned above to iteratively reduce the problem of verifying the degree of \( f \) to checking whether a folded polynomial \( f_{\text{fold}} \) has a degree at most \( \frac{d}{2} \), ultimately reducing it to a constant-level verification problem. We will focus on the execution flow and underlying principles of FRI in subsequent sections.
During the execution of FRI, the prover must first commit to a polynomial \( P \). When opening specific points of \( P \), the prover must simultaneously provide the Merkle path for that point as a Merkle Proof.
The above figure illustrates the Merkle commitment of a polynomial \( P(X) \) over \( X = \{1, 2, 3, 4, 5, 6, 7, 8\} \). The Merkle tree is built starting from the leaf nodes, where typically the hash of two adjacent child nodes forms the parent node. This process recurses upwards. The specific Merkle tree construction in the figure is as follows:
1. Generate First-Level Intermediate Nodes:
- Start with the 8 leaf nodes \( P_1, P_2, P_3, P_4, P_5, P_6, P_7, P_8 \).
- Perform hashing on adjacent leaf nodes to generate four intermediate nodes:
\[\begin{gather*}A_1 = \text{Hash}(P_1, P_2) \\A_2 = \text{Hash}(P_3, P_4) \\A_3 = \text{Hash}(P_5, P_6) \\A_4 = \text{Hash}(P_7, P_8)\end{gather*}\]
2. Generate Second-Level Intermediate Nodes: - Perform hashing on the first-level intermediate nodes to generate two higher-level nodes: \[ B_1 = \text{Hash}(A_1, A_2) \] \[ B_2 = \text{Hash}(A_3, A_4) \]
3. Generate Root Node: - Finally, hash the second-level nodes to generate the root node: \[ \text{Root} = \text{Hash}(B_1, B_2) \]
In the diagram, the blue-highlighted nodes represent the Merkle Proof corresponding to opening \( P_1 \). The prover retains the entire tree (including all root and leaf nodes), while the verifier only retains the root node (in this example, the Root). If the prover wants to open \( P_1 \), they need to provide the corresponding Merkle path as follows:
1. Compute First-Level Hashes:
- Use \( P_1 \) and \( P_2 \) to compute \( A_1 \): \[ A_1 = \text{Hash}(P_1, P_2) \]
- During the proof process, \( P_2 \) is the first node that needs to be provided.
2. Compute Second-Level Hashes:
- Use \( A_1 \) and \( A_2 \) to compute \( B_1 \): \[ B_1 = \text{Hash}(A_1, A_2)\]
- During the proof process, \( A_2 \) is the second node that needs to be provided.
3. Compute Root Node:
- Use \( B_1 \) and \( B_2 \) to compute the root node: \[ \text{Root} = \text{Hash}(B_1, B_2) \]
- During the proof process, \( B_2 \) is the third node that needs to be provided.
In the figure, the blue-highlighted nodes are the Merkle Proof for opening \( P_1 \). The verifier only needs to recompute the hash functions on these Merkle Proof nodes and check if they match the Root to verify that \( P_1 \) is indeed part of the Merkle tree.
1. Low Computational Overhead: Only requires efficient operations like hash functions.
2. Small Proof Size: 2. Assuming a tree with \( d \) leaf nodes, only a proof of size \( \log d \) needs to be submitted.
Subscribe to the ZKM Blog to stay updated with the latest research by ZKM. If you have any questions, you can contact the ZKM team on discord: discord.com/invite/zkm
