Fibonacci (Single-AIR)

Fibonacci (Single-AIR)#

The Fibonacci program is the simplest instantiation of the OpenVM STARK protocol: a single AIR with 2 trace columns, 3 public values, and 5 constraints. It has no bus interactions (no LogUp phase).

Trace Structure#

The trace has 2 columns (left, right) and \(N\) rows (power of 2) (generate_fibonacci_trace):

Row

Left

Right

0

\(a\)

\(b\)

1

\(b\)

\(a + b\)

2

\(a + b\)

\(a + 2b\)

\(\vdots\)

\(\vdots\)

\(\vdots\)

\(N-1\)

\(F_{N-1}\)

\(F_N\)

All values are reduced modulo \(p\).

Public Values#

Three public values \([a, b, x]\) where (fibonacci_public_values):

  • \(a = \text{trace}[0][0]\) (initial left)

  • \(b = \text{trace}[0][1]\) (initial right)

  • \(x = \text{trace}[N-1][1]\) (final right = \(N\)-th Fibonacci number)

Constraints#

The AIR defines 5 constraint polynomials (eval_constraints):

#

Constraint

Selector

Purpose

1

\(L_0 \cdot (\ell_0 - a)\)

is_first_row

First left \(= a\)

2

\(L_0 \cdot (\ell_1 - b)\)

is_first_row

First right \(= b\)

3

\(T \cdot (n_0 - \ell_1)\)

is_transition

Next left \(=\) current right

4

\(T \cdot (n_1 - \ell_0 - \ell_1)\)

is_transition

Next right \(=\) sum

5

\(L_{N-1} \cdot (\ell_1 - x)\)

is_last_row

Last right \(= x\)

Where:

  • \(\ell_0, \ell_1\): current row’s left and right columns

  • \(n_0, n_1\): next row’s left and right columns

  • \(L_0, L_{N-1}, T\): domain selectors (see Primitives)

Each constraint has degree 2 (product of degree-1 selector and degree-1 expression). The quotient degree is \(d_Q = 2\), producing 2 quotient chunks.

Protocol Walkthrough#

For the test vector (fibonacci_stark.json, \(N = 256\), \(a = 1\), \(b = 1\)):

Stage 1: Witness Commitment#

  1. Generate 256-row trace: generate_fibonacci_trace(1, 1, 256).

  2. Coset LDE with blowup 2: extend 256 → 512 evaluations.

  3. Merkle commit → root \(r_1\) (8 base field elements).

  4. Absorb public values \([1, 1, F_{256}]\), preprocessed commits, \(r_1\), \(\log_2(256) = 8\) into transcript.

Stage 2: After-Challenge (LogUp)#

Skipped — Fibonacci has no bus interactions.

Stage Q: Quotient#

  1. Sample \(\alpha \leftarrow \mathcal{T}.\text{sample\_ext}()\).

  2. Create disjoint quotient domain of size \(256 \cdot 2 = 512\).

  3. Extend trace to quotient domain.

  4. Evaluate all 5 constraints at each quotient domain point.

  5. Accumulate: \(\text{acc}(x) = \alpha^4 C_1(x) + \alpha^3 C_2(x) + \alpha^2 C_3(x) + \alpha C_4(x) + C_5(x)\).

  6. Divide by \(Z_H(x)\) to get \(Q(x)\).

  7. Split into 2 chunks of 256 values each.

  8. Merkle commit → root \(r_Q\).

Evaluation + FRI#

  1. Sample \(\zeta \leftarrow \mathcal{T}.\text{sample\_ext}()\).

  2. Open main trace and quotient chunks at \(\zeta\) (and \(\zeta\omega\) for main).

  3. Run FRI commit + query phase.

Verification#

The verifier checks:

  • \(C_1(\zeta) = 0, \ldots, C_5(\zeta) = 0\) (after \(\alpha\)-folding)

  • \(\text{folded} \cdot Z_H(\zeta)^{-1} = Q(\zeta)\)

  • All Merkle proofs and FRI fold consistency.

Test Vectors#

The test suite verifies:

  • Prover: Python produces byte-identical proof to Rust (test_proof_binary_equivalence in test_stark_e2e.py).

  • Verifier: Python verifier accepts the Rust-generated proof (test_verify_valid_proof in test_verifier_e2e.py).

  • Failure detection: Corrupted quotient/main/PV/VK all rejected.