Medium Website

Mathematical Background

Let's dive into a high-level overview of the mathematical foundations and principles of zk-STARKs.

  1. Algebraic Normal Form (ANF)

    The core of zk-STARKs lies in polynomials. Polynomials are an efficient way to express and compute complex mathematical concepts. A polynomial in Algebraic Normal Form (ANF) is a sum of monomials where each variable is to the power of 0 or 1.

  2. Error-Correcting Codes

    zk-STARKs use error-correcting codes to enable efficient testing of proximity to a code. Reed-Solomon codes are used due to their property of maximum distance separability.

  3. Fast Fourier Transform (FFT)

    The FFT allows efficient evaluation of a polynomial at multiple points. Given a polynomial P(x) and a set of points {x1, x2, …, xn}, the FFT computes the values {P(x1), P(x2), …, P(xn)}.

  4. The Merkle Tree

    The Merkle tree is a data structure used to authenticate large amounts of data. It builds a binary tree with hashes of data at the leaves and hashes of child nodes in the parent nodes.

  5. Interactive Oracle Proofs (IOPs) and the Sumcheck Protocol

    An IOP is a protocol in which a prover and a verifier exchange messages, and the prover uses oracles (objects that can respond to queries about a large dataset) to provide proofs. The sumcheck protocol is a specific type of IOP that allows the prover to convince the verifier that a sum over a polynomial is correct.

  6. FRI Protocol

    The Fast Reed-Solomon Interactive (FRI) protocol allows the prover to convince the verifier that a received word is close to a codeword of a Reed-Solomon code. This enables the verifier to authenticate the values of a polynomial at many points without receiving the entire polynomial.

Steps of the zk-STARKs Protocol

  1. Commitment Phase

    In this phase, the prover commits to a trace of the computation, which is essentially a table where each row represents a step in the computation. The trace is converted into polynomial form and authenticated using a Merkle tree.

  2. Query Phase

    The verifier selects a set of random query points and sends them to the prover. The prover evaluates the polynomials at the query points and sends the results back.

  3. Answer Phase

    The prover constructs proof polynomials from the query results and sends these to the verifier. The verifier checks the proofs using the FRI protocol.

zk-STARKs and Privacy

While zk-STARKs provide strong privacy guarantees, it's important to note that they are "transparent" but not "succinct" in the way zk-SNARKs are. The proof sizes and computational costs are larger, but this is the trade-off for removing the need for a trusted setup.

zk-STARKs are an exciting development in the field of cryptography, with many potential applications in areas such as blockchain technology where they can be used for efficient, secure, and private transactions.

Please note that this is a simplified overview of a very complex subject. For a deeper understanding of the mathematical foundations of zk-STARKs, I recommend the following resources:

  1. Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, Michael Riabzev (2018). Fast Reed-Solomon Interactive Oracle Proofs of Proximity. https://eccc.weizmann.ac.il/report/2018/134/

  2. Eli Ben-Sasson, Alessandro Chiesa, Michael Riabzev, Nicholas Spooner, Madars Virza, Nicholas P. Ward (2019). Aurora: Transparent Succinct Arguments for R1CS. https://eprint.iacr.org/2019/601.pdf

  3. Vitalik Buterin. Exploring Elliptic Curve Pairings. https://vitalik.ca/general/2017/01/14/exploring-elliptic-curve-pairings.html

  4. Alessandro Chiesa, Michael A. Forbes (2018). IOPs from Algebraic Error-Correcting Codes. https://eprint.iacr.org/2018/280.pdf

    Let's dive into a high-level overview of the mathematical foundations and principles of zk-STARKs.

    1. Algebraic Normal Form (ANF)

      The core of zk-STARKs lies in polynomials. Polynomials are an efficient way to express and compute complex mathematical concepts. A polynomial in Algebraic Normal Form (ANF) is a sum of monomials where each variable is to the power of 0 or 1.

    2. Error-Correcting Codes

      zk-STARKs use error-correcting codes to enable efficient testing of proximity to a code. Reed-Solomon codes are used due to their property of maximum distance separability.

    3. Fast Fourier Transform (FFT)

      The FFT allows efficient evaluation of a polynomial at multiple points. Given a polynomial P(x) and a set of points {x1, x2, …, xn}, the FFT computes the values {P(x1), P(x2), …, P(xn)}.

    4. The Merkle Tree

      The Merkle tree is a data structure used to authenticate large amounts of data. It builds a binary tree with hashes of data at the leaves and hashes of child nodes in the parent nodes.

    5. Interactive Oracle Proofs (IOPs) and the Sumcheck Protocol

      An IOP is a protocol in which a prover and a verifier exchange messages, and the prover uses oracles (objects that can respond to queries about a large dataset) to provide proofs. The sumcheck protocol is a specific type of IOP that allows the prover to convince the verifier that a sum over a polynomial is correct.

    6. FRI Protocol

      The Fast Reed-Solomon Interactive (FRI) protocol allows the prover to convince the verifier that a received word is close to a codeword of a Reed-Solomon code. This enables the verifier to authenticate the values of a polynomial at many points without receiving the entire polynomial.

    Steps of the zk-STARKs Protocol

    1. Commitment Phase

      In this phase, the prover commits to a trace of the computation, which is essentially a table where each row represents a step in the computation. The trace is converted into polynomial form and authenticated using a Merkle tree.

    2. Query Phase

      The verifier selects a set of random query points and sends them to the prover. The prover evaluates the polynomials at the query points and sends the results back.

    3. Answer Phase

      The prover constructs proof polynomials from the query results and sends these to the verifier. The verifier checks the proofs using the FRI protocol.

    zk-STARKs and Privacy

    While zk-STARKs provide strong privacy guarantees, it's important to note that they are "transparent" but not "succinct" in the way zk-SNARKs are. The proof sizes and computational costs are larger, but this is the trade-off for removing the need for a trusted setup.

    zk-STARKs are an exciting development in the field of cryptography, with many potential applications in areas such as blockchain technology where they can be used for efficient, secure, and private transactions.

Deep Dive:

  1. Polynomials and the Fast Fourier Transform

    In zk-STARKs, computations are represented as polynomials. A polynomial is a mathematical expression involving a sum of powers in one or more variables multiplied by coefficients. For example, f(x) = ax^3 + bx^2 + cx + d.

    zk-STARKs often require evaluating a polynomial at multiple points, which is where the Fast Fourier Transform (FFT) comes in. The FFT is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT), in a highly efficient manner.

    The DFT is given by the formula: X(k) = Σ[n=0 to N-1] x(n) * exp(-j*2*pi*k*n/N), where x(n) is the input signal, N is the total number of samples, k ranges from 0 to N-1, and j is the square root of -1.

  2. Error-Correcting Codes and Reed-Solomon Codes

    Error-Correcting Codes (ECCs) are used to detect and correct errors introduced during the transmission of data in noisy communication channels. Reed-Solomon codes, a specific type of ECC, are used in zk-STARKs because they are Maximum Distance Separable (MDS) codes, meaning they have the highest error tolerance possible.

    Reed-Solomon codes are defined over finite fields (also known as Galois fields). Let's denote a finite field as GF(q), where q is a prime power. A Reed-Solomon code RS(n, k) over GF(q) is a linear code that consists of all codewords (f(α1), f(α2), ..., f(αn)), where f(x) is a polynomial of degree < k, and α1, α2, ..., αn are distinct elements in GF(q).

  3. Interactive Oracle Proofs (IOPs) and the Sumcheck Protocol

    The zk-STARK protocol involves an interaction between a prover and a verifier. The prover wants to prove they know a solution to a certain problem without revealing the solution itself. The prover and verifier communicate through Interactive Oracle Proofs (IOPs).

    The sumcheck protocol is a crucial part of this. The protocol lets a prover convince a verifier that a sum of evaluations of a polynomial P(x) of degree d over a finite field F is correct, where the sum is taken over all points in a set H of size h.

    The sumcheck protocol proceeds in d+1 rounds. In each round i (from d to 0), the prover sends a univariate polynomial g_i(x) of degree d+1-i to the verifier. The verifier then chooses a random point r_i in F and sends it to the prover. This process continues until i=0, and the prover finally sends the constant g_0 to the verifier.

  4. FRI Protocol

    The Fast Reed-Solomon Interactive (FRI) protocol is used to reduce the problem of testing proximity to the Reed-Solomon code to testing proximity to a lower degree Reed-Solomon code.

    Here's a high-level overview of the FRI protocol:

    a. The prover wants to convince the verifier that a received word w is close to a codeword of a Reed-Solomon code.

    b. The prover commits to the evaluations of a polynomial P(x).

    c. The verifier sends a random point α and requests the value P(α).

    d. The prover replies with P(α).

    e. The prover and verifier then execute the sumcheck protocol, where the prover convinces the verifier that P(α) is the correct evaluation of P(x) at α.

    f. The verifier checks the received values with the committed values.

Previouszk-STARKSNextBuilding Blocks of zk-STARKS

Last updated

Logo