Zero-knowledge in Risc-V virtual machine

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: N = 4  
- Primitive 4th root of unity: ω = 4  
  - ω⁰ = 1  
  - ω¹ = 4  
  - ω² = 16 ≡ -1  
  - ω³ = 13 (mod 17)

**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):
  - Hash of position 0 (left)
  - Hash of H23 (right)

The verifier can then recompute the hashes layer by layer and check if they match 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.

---

### 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.

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)