Zero-knowledge in Risc-V virtual machine(zkVM)

Ethereum has thousands of nodes, each potentially running on different hardware and different operating systems. Once a transaction is executed, all nodes must arrive at exactly the same result — otherwise consensus cannot be reached.
Node A (Linux x86)        ┐
Node B (macOS ARM)   ├──► Same Smart Contract → Results must be bit-for-bit identical
Node C (Windows x64)  ┘

SP1 is a zero-knowledge virtual machine (zkVM) developed by Succinct Labs. It is designed to prove the correct execution of programs compiled for the RISC-V architecture.

https://github.com/succinctlabs/sp1

# SP1 NTT Calculation Guide (Smallest Clear Example)

**Settings**
- Prime modulus: p = 17
- Length run calculate times: N = 4
- Primitive 4th root of unity: ω = 4
  - ω⁰ = 1  
  - ω¹ = 4  
  - ω² = 16 ≡ -1  
  - ω³ = 13 (mod 17)

A(x)=1+2x+3x^2+4x^3
**Input (Time-domain coefficients):**  
a = [1, 2, 3, 4]**

---

## 1. Goal
Convert coefficient representation to point-value representation (frequency domain) by evaluating:  
A(ω⁰), A(ω¹), A(ω²), A(ω³) (mod 17)

---

## 2. Direct Evaluation (Verification)

| x (ω^i) | Computation A(x)                     | Result (mod 17) |
|---------|-------------------------------------------|-----------------------|
| 1        | 1 + 2 + 3 + 4                              | **10**                 |
| 4        | 1 + 2×4 + 3×16 + 4×64              | **7**                   |
| -1       | 1 - 2 + 3 - 4                                | **15**                 |
| 13      | 1 + 2×13 + 3×169 + 4×2197      | **6**                   |

**Frequency-domain result:** **[10, 7, 15, 6]**

---

## 3. DIT Butterfly Network Calculation (Used in SP1)

### Step 0: Bit-Reversal
Original indices → Bit-reversed order:  
**Input becomes [1, 3, 2, 4]**

---

### Step 1: Stage 1 (m=2, stride=1)
Twiddle factor: W₂ = -1 (only W₂⁰ = 1 used this stage)

| Group | Upper | Lower | t    | New Upper | New Lower |
|----------|----------|----------|-----|----------------|-----------------|
| 0-1      | 1         | 3        | 3    | 4                | 15               |
| 2-3      | 2         | 4        | 4    | 6                | 15               |

**After Stage 1:** **[4, 15, 6, 15]**

---

### Step 2: Stage 2 (m=4, stride=2)
Twiddle factor: W₄ = 4

| Group | Upper | Lower | W | t   | New Upper | New Lower |
|----------|----------|----------|----|----|-----------------|-----------------|
| 0-2      | 4         | 6         | 1  | 6 | 10                | 15               |
| 1-3      | 15       | 15       | 4  | 9  | 7                 | 6                 |

**Final Output (Frequency Domain):** **[10, 7, 15, 6]** ✅

---

## 4. Summary Table

| Position | Original | Bit-Reversed | After Stage 1 | Final Result |
|------------|------------|-------------------|-------------------|-----------------|
| 0           | 1            | 1                    | 4                   | **10**          |
| 1           | 2            | 3                    | 15                 | **7**            |
| 2           | 3            | 2                    | 6                   | **15**          |
| 3           | 4            | 4                    | 15                 | **6**            |

---

## 5. Role in SP1 zkVM
- Execution trace (e.g., register values over time) is a sequence of numbers like `[1,2,3,4]`  
- NTT converts it to point-value representation `[10,7,15,6]`  
- Point values enable polynomial constraints, FRI commitments, and finally STARK proof generation

**Key takeaway:**  
NTT is FFT over a finite field. It uses butterfly operations (add, subtract, multiply by twiddle factor) to efficiently transform from time domain to frequency domain.

# After NTT: How SP1 Generates and Verifies the STARK Proof

After performing the **NTT**, SP1 turns the execution trace into polynomials. It then uses **FRI** (Fast Reed-Solomon Interactive Oracle Proof of Proximity) — the most important compression technique in STARKs — to commit to these polynomials.

### Simplified Process
- Take the frequency-domain values (after NTT).
- Perform several more rounds of **NTT + random folding** (FRI folding).
- This process produces **Merkle Tree Roots** for the polynomials.

Imagine we have 3 important polynomials (real systems have more):
- **Trace Polynomial** — represents the execution trace
- **Constraint Polynomial** — checks if the execution follows the rules
- **Quotient Polynomial** — the result after division (used to prove constraints are zero)

Each polynomial is committed to, resulting in a **Merkle Root** (a single hash value).

**Example:**
- Trace Root: `0xABC123...`
- Constraint Root: `0xDEF456...`
- Quotient Root: `0x789XYZ...`

---

### What is Inside the Proof?

The generated proof mainly contains:
- All **Merkle Roots** (publicly shared)
- **FRI layer Merkle Proofs** (containing many left/right hashes)
- **Openings** at random challenge points
- Data for the low-degree test

### Merkle Tree & Hash Left/Right (Simple Example)

Assume we have 4 leaf values:

- L0 = hash(10)
- L1 = hash(7)
- L2 = hash(15)
- L3 = hash(6)

**First Layer:**
- H01 = hash(L0 + L1)   ← left = L0, right = L1
- H23 = hash(L2 + L3)   ← left = L2, right = L3

**Root:**
- Root = hash(H01 + H23)

---
When the verifier wants to confirm a specific value (e.g., the value at **position 1** is 7), the prover only needs to send:

- The value itself (`7`)
- The Merkle Proof (sibling hashes):
  - L0    (the hash of position 0, left sibling)
  - H23 (the hash of the right subtree)

The verifier can then recompute the hashes layer by layer as follows:
1. Compute L1 = hash(7)  
   (Calculate the leaf hash from the received value `7`)

2. Compute H01 = hash(L0 + L1)  
   (Combine the received L0 with the newly computed L1)

3. Compute Root = hash(H01 + H23)  
   (Combine the newly computed H01 with the received H23)

and check if the resulting Root matches the published Root.

This is why "**hash left / right**" is frequently mentioned — every Merkle proof provides the sibling (left or right) hash at each level.

---
## FRI Folding - Simple Numerical Example

### Round 1 Folding (4 points → 2 points)

**Step 1:** The Prover commits Layer 0 values as a Merkle Tree Root, then derives the random challenge:
**β = Hash(Merkle Root of Layer 0) = 5** (mod 17)

**Step 2:** The Prover folds each pair using the formula:

g(x^2) = [{f(x) + f(-x)}/2 + beta*{f(x) - f(-x)}/2x] mod 17

**Assigned domain for illustration:**
- Pair 1 (positions 0 & 1): x = 1, f(1) = 10, f(-1) = 7
- Pair 2 (positions 2 & 3): x = 2, f(2) = 15, f(-2) = 6

**Calculation - Pair 1 (x=1):**
- Sum = 10 + 7 = 17 ≡ 0 (mod 17)
- Diff = 10 - 7 = 3
- Sum/2 = 0
- Diff/(2x) = 3 × (2)^{-1} = 3 × 9 = 27 ≡ 10 (mod 17)
- β × (Diff/(2x)) = 5 × 10 = 50 ≡ 16 (mod 17)
- **New[0] = 0 + 16 = 16**

**Calculation - Pair 2 (x=2):**
- Sum = 15 + 6 = 21 ≡ 4 (mod 17)
- Diff = 15 - 6 = 9
- Sum/2 = 4 × 9 = 36 ≡ 2 (mod 17)
- Diff/(2x) = 9 × (4)^{-1} = 9 × 13 = 117 ≡ 15 (mod 17)
- β × (Diff/(2x)) = 5 × 15 = 75 ≡ 7 (mod 17)
- **New[1] = 2 + 7 = 9**

**Result after Round 1:** **[16, 9]**

---
### Round 2 Folding (2 points → 1 point)

**Step 1:** The Prover commits Layer 1 values as a Merkle Tree Root, then derives the next random challenge:
**β₂ = Hash(Merkle Root of Layer 1) = 8** (mod 17)

**Step 2:** Apply the same formula (using x' = 1 for illustration)

**Calculation:**
- f'(1) = 16, f'(-1) = 9
- Sum = 16 + 9 = 25 ≡ 8 (mod 17)
- Diff = 16 - 9 = 7
- Sum/2 = 8 × 9 = 72 ≡ 4 (mod 17)
- Diff/(2x') = 7 × 9 = 63 ≡ 12 (mod 17)
- β₂ × (Diff/(2x')) = 8 × 12 = 96 ≡ 11 (mod 17)
- **Final value = 4 + 11 = 15**

**Result after Round 2:** **15**

---
### Verifier Check

The Verifier does **not** need to unfold the values back to the original vector.
Instead, the verification process works as follows:

- During the folding phase, the **Prover** derives all random challenges using the
  Fiat-Shamir heuristic (non-interactive):
  - β₁ = Hash(Merkle Root of Layer 0)
  - β₂ = Hash(Merkle Root of Layer 1)
  - β₃ = Hash(Merkle Root of Layer 2), ...
  The Prover performs all folding independently, without interaction with the Verifier.

 - After all folding rounds are complete, the Verifier receives the full proof and:
  - Recomputes each β by applying the same Hash to the corresponding Merkle Root
  - Derives query positions via Fiat-Shamir (e.g., Hash of all commitments so far)
  - Checks the openings and Merkle proofs already included in the proof at those positions
  - Note: queried positions are linked across layers —
    querying position x in Layer 0 corresponds to x^2 in Layer 1, x^4 in Layer 2, etc.

- For each queried position, the Verifier checks whether the folding satisfies the correct formula:

  g(x^2) = [{f(x) + f(-x)}/2 + beta*{f(x) - f(-x)}/2x] mod 17

- Finally, the Verifier checks that the last (single) value is consistent with a
  low-degree polynomial.

**In this example, the final value is 15**, which is a constant (degree 0 polynomial).

FRI can prove the execution is correct because: if the Prover cheated (for example,
some constraint polynomial is not actually low-degree), then with high probability
the random queries will detect an inconsistency in at least one layer.

---
### Sending the Proof to Another Node

The Prover sends the following data to the Verifier:
json format
{
  "trace_root": "0xABC123...",
  "constraint_root": "0xDEF456...",
  "quotient_root": "0x789XYZ...",
  "fri_proofs": [ ...many layers, each with left/right hashes... ],
  "openings": { ...values at challenge points... },
  "proof_size": "Usually a few hundred KB"
}

How the Verifier Checks the Proof (Very Fast)Verify all Merkle Proofs are correct (recompute Roots using left/right hashes).
Perform the FRI low-degree test (confirm the polynomials are of low degree).
Check the Quotient Polynomial is correct (i.e., the Constraint Polynomial is zero at the required points).
If everything passes → Accept that "the execution is correct".

The entire verification process usually takes only a few milliseconds to tens of milliseconds — much faster than re-executing the original program.

download:
https://www.mediafire.com/file/xylhfe6okxm8cqb/ntt_fri.txt

note:
The Ethereum Virtual Machine (EVM) is the entry point for executing all "plugins" (smart contracts).
https://github.com/ethereum/go-ethereum/blob/master/core/vm/interpreter.go
func (evm *EVM) Run(contract *Contract, input []byte, readOnly bool) (ret []byte, err error)

next generation The Ethereum Virtual Machine (Risc-V) is the entry point for executing all "plugins" (smart contracts).
https://github.com/succinctlabs/sp1/blob/main/crates/sdk/src/blocking/prover/execute.rs
pub fn run(self) -> Result<(SP1PublicValues, ExecutionReport), ExecutionError>

"Plug-in" (smart contract) call function.
https://github.com/succinctlabs/sp1/blob/main/crates/core/executor/src/vm.rs
pub fn execute_ecall<RT>(rt: &mut RT, instruction: &Instruction,_code: SyscallCode)