Warning
Toyni was migrated from jonas089's Github Click here to see the past commit history.
Welcome to Toyni! This is an implementation of a STARK (Scalable Transparent Argument of Knowledge) proving system in Rust. While it's not yet a full zero-knowledge STARK, it provides a solid foundation for understanding how STARKs work.
Meet the amazing artist behind this creation, Kristiana Skrastina
Warning
This is a research project and hasn't been audited. Use at your own risk.
- For each randomly sampled point
x:- Verifier checks:
Q(x) * Z(x) == C(x) - Ensures that the execution trace satisfies all constraints
- This check is done once per point
- Not done across layers
- Merkle proof is optional (depends on how C(x) and Q(x) are committed)
- Verifier checks:
-
Purpose: Prove that
Q(x)is a low-degree polynomial -
Process:
- Start with evaluations of
Q(x)over the domain (Layer 0) - Recursively apply
fri_fold()to reduce degree at each layer - At each layer:
- Verifier checks Merkle proofs for sampled values
- Verifies that folding is consistent with previous layer
- Final layer should be constant or degree-1, checked directly
- Start with evaluations of
-
β Merkle proofs are checked at each FRI layer
-
β Folding correctness is verified at each layer
sequenceDiagram
participant Proof_Data
participant Constraint_Check
participant FRI_Protocol
participant FRI_Merkle_Commitment
participant FRI_Consistency
participant FRI_Layers
participant Accept_Proof
Proof_Data-->Constraint_Check: Check Q(x)Β·Z(x) == C(x)
Proof_Data-->FRI_Protocol: Begin FRI protocol
FRI_Protocol-->FRI_Merkle_Commitment: Verify Merkle proofs
FRI_Merkle_Commitment-->FRI_Consistency: Check folding inputs + Ξ²
FRI_Consistency-->FRI_Layers: Fold with Ξ²0..Ξ²n
FRI_Layers-->Accept_Proof: β
Accept Proof
Note
FRI folding equation: f_{i+1}(xΒ²) = (fα΅’(x) + fα΅’(βx) + Ξ²α΅’ Β· (fα΅’(x) β fα΅’(βx))) / 2
To achieve 128-bit soundness in STARK proofs, the total probability that a cheating prover is accepted must be less than 2β»ΒΉΒ²βΈ.
This involves carefully choosing parameters for:
- Constraint checks (
Q(x)evaluations) - FRI protocol (number of layers and queries per layer)
Example:
- If
L = 20layers βlogβ(20) β 4.3- Then:
m β 133queries per layer
Example:
- If
d / N = 1/4, thenlogβ(N/d) = 2- So:
n = 128 / 2 = 64spot checks
- If
d / N = 1/8, thenlogβ(N/d) = 3- So:
n = 128 / 3 β 43, but round up to be safe
Use n = 64β80 spot checks for strong 128-bit soundness across typical domain/degree ratios.
| Component | Suggested Value |
|---|---|
Constraint checks n |
64β80 |
FRI layers L |
logβ(N / degree of final poly) |
FRI queries m |
β₯ logβ(L) + 128 (e.g., 133) |
| Total soundness error | Ξ΅_total = Ξ΅_constraints + Ξ΅_fri β€ 2β»ΒΉΒ²βΈ |
| Check Type | Equation Checked | Merkle Proofs | Multiple Layers? |
|---|---|---|---|
| Constraint Check | Q(x) * Z(x) == C(x) |
Optional | β No |
| FRI Layer Check | Folding consistency, low-degree | β Yes | β Yes |
STARKs are a powerful cryptographic tool that enables proving the correct execution of a computation without revealing the underlying data. Think of it as a way to convince someone that you know the solution to a puzzle without actually showing them the solution. This property, known as zero-knowledge, is crucial for privacy-preserving applications in areas like financial transactions, voting systems, and private identity verification.
| Scalability | Transparency | Zero-Knowledge |
|---|---|---|
| β’ O(logΒ² n) proof size | β’ No trusted setup | β’ Privacy |
| β’ Fast verify | β’ Public parameters | β’ Confidentiality |
| β’ Efficient | β’ Data protection | |
| β’ Secure sharing |
| Financial | Identity | Computing |
|---|---|---|
| β’ Private payments | β’ Age verification | β’ Confidential computing |
| β’ Asset ownership | β’ Credential validation | β’ Private ML |
| β’ Secure MPC |
At its heart, Toyni consists of three main components working together:
| Virtual Machine | Constraint System | STARK Prover |
|---|---|---|
| β’ Executes programs | β’ Defines rules | β’ Generates proofs |
| β’ Creates traces | β’ Validates states | β’ Uses FRI protocol |
| Program Execution | Execution Trace | Verification |
|---|---|---|
| β’ Run program | β’ Record states | β’ Sample positions |
| β’ Track state | β’ Build constraints | β’ Check constraints |
| β’ Generate trace |
Here's a simple example that demonstrates how Toyni works. We'll create a program that proves a sequence of numbers increments by 1 each time:
fn test_valid_proof() {
let mut trace = ExecutionTrace::new(4, 1);
for i in 0..4 {
let mut row = HashMap::new();
row.insert("x".to_string(), i);
trace.insert_column(row);
}
let mut constraints = ConstraintSystem::new();
constraints.add_transition_constraint(
"increment".to_string(),
vec!["x".to_string()],
Box::new(|current, next| {
let x_n = Fr::from(*current.get("x").unwrap() as u64);
let x_next = Fr::from(*next.get("x").unwrap() as u64);
x_next - x_n - Fr::ONE
}),
);
constraints.add_boundary_constraint(
"starts_at_0".to_string(),
0,
vec!["x".to_string()],
Box::new(|row| Fr::from(*row.get("x").unwrap() as u64)),
);
let prover = StarkProver::new(&trace, &constraints);
let proof = prover.generate_proof();
let verifier = StarkVerifier::new(&constraints, trace.height as usize);
assert!(verifier.verify(&proof));
}This example demonstrates how Toyni can prove that a sequence of numbers follows a specific pattern (incrementing by 1) without revealing the actual numbers. The proof can be verified by anyone, but the actual values remain private.
STARKs achieve their security through a combination of domain extension and low-degree testing. Here's how it works:
| Domain Extension | Low-Degree Testing | Soundness Guarantees |
|---|---|---|
| β’ Extend domain | β’ FRI protocol | β’ Soundness error: (1/b)^q |
| β’ Blowup factor | β’ Polynomial degree | β’ Query complexity |
The security of a STARK proof relies on two key mechanisms:
-
Domain Extension (Blowup): The composition polynomial is evaluated over a domain that's
btimes larger than the original trace length, wherebis the blowup factor. -
Low-Degree Testing: The FRI protocol ensures that the polynomial being tested is close to a valid low-degree polynomial.
The soundness error (probability of accepting an invalid proof) is bounded by:
Pr[undetected cheat] = (1/b)^q
where:
bis the blowup factor (e.g., 8 in our example)qis the number of queries made by the verifier
This means that if a prover tries to cheat by modifying a fraction 1/b of the domain, the verifier will detect this with probability at least 1 - (1/b)^q. For example, with a blowup factor of 8 and 10 queries, the soundness error is at most (1/8)^10 β 0.0000001.
The codebase is organized into logical components:
| Math | VM | Library |
|---|---|---|
| β’ Polynomial | β’ Constraints | β’ Entry point |
| β’ Domain | β’ Trace | β’ Public API |
| β’ FRI | β’ Execution | β’ Documentation |
| β’ STARK |
| Constraint System | FRI Protocol | Mathematical Operations |
|---|---|---|
| β’ Transition constraints | β’ Low-degree testing | β’ Polynomial arithmetic |
| β’ Boundary constraints | β’ Interactive verification | β’ Field operations |
| β’ Quotient verification | β’ FRI folding layers | β’ Domain operations |
| β’ Merkle commitments | β’ Folding consistency checks | β’ Secure commitments |
| Zero-Knowledge | Fiat-Shamir Transform | Performance |
|---|---|---|
| β’ Trace privacy | β’ Deterministic hashing | β’ Parallel processing |
| β’ State protection | β’ Non-interactive proofs | β’ Batch verification |
| β’ Circuit-specific | β’ Secure randomness | β’ Optimized FRI |
While we have a working STARK implementation with quotient polynomial verification and FRI folding, there are still some components to implement:
- Fiat-Shamir Transform: Currently using random number generation instead of deterministic hashing, making the protocol interactive.
- Performance Optimizations: Need to implement parallel processing and batch verification for better scalability.
- Circuit-Specific Features: Add support for specialized circuits and optimizations.
- Basic STARK implementation with constraint checks
- FRI protocol with folding layers
- Merkle commitments for FRI layers
- Folding consistency verification
- Interactive verification protocol
- Fiat-Shamir transform implementation
- Performance optimizations
- Circuit-specific optimizations
- Zero-knowledge enhancements
- Parallel processing support
- Batch verification
- Circuit-specific optimizations
- Documentation improvements
STARKs achieve their security through a combination of domain extension, low-degree testing, and Merkle commitments. Here's how it works:
| Domain Extension | Low-Degree Testing | Merkle Commitments |
|---|---|---|
| β’ Extend domain | β’ FRI protocol | β’ Tree structure |
| β’ Blowup factor | β’ Polynomial degree | β’ Proof generation |
| β’ Soundness | β’ Folding checks | β’ Commitment verification |
The security of a STARK proof relies on three key mechanisms:
-
Domain Extension (Blowup): The composition polynomial is evaluated over a domain that's
btimes larger than the original trace length. -
Low-Degree Testing: The FRI protocol ensures that the polynomial being tested is close to a valid low-degree polynomial, with folding consistency checks at each layer.
-
Merkle Commitments: Each FRI layer is committed using a Merkle tree, ensuring the integrity of the folding process and enabling efficient verification.
The soundness error (probability of accepting an invalid proof) is bounded by:
Pr[undetected cheat] = (1/b)^q
where:
bis the blowup factor (e.g., 8 in our example)qis the number of queries made by the verifier
This means that if a prover tries to cheat by modifying a fraction 1/b of the domain, the verifier will detect this with probability at least 1 - (1/b)^q. For example, with a blowup factor of 8 and 10 queries, the soundness error is at most (1/8)^10 β 0.0000001.
We welcome contributions to Toyni! Our current focus is on implementing zero-knowledge properties and improving the overall system. We're particularly interested in:
- Implementing Merkle tree commitments and the Fiat-Shamir transform
- Adding comprehensive test coverage and security audits
- Improving documentation and adding more examples
- Optimizing performance and reducing proof sizes
