Investigate no-std epic to see what else needs to be done

[richardpringle]

See epic o1-labs/mina-rust#1978

[richardpringle]

Investigation: no-std work needed in proof-systems

Context

The upstream epic (mina-rust #1978) aims to make the Pickles verifier run in zkVMs (Risc0/SP1) for cross-chain proof verification. Multiple teams have requested this. The work in this repo is to make the kimchi verifier (and its transitive dependencies) compile under no_std.

The strategy is: add a default-on std feature (or parallel/prover where appropriate) to each crate, feature-gate std-only code behind it, and provide sequential/core/alloc fallbacks for the verifier path.

A tracking issue for the kimchi crate specifically exists at #3518.

---

Crates already no-std compatible

• mina-curves (curves/) - no rayon, no std imports
• mina-poseidon (poseidon/) - already declares #![no_std] with extern crate alloc, no rayon. Only blocker is its dependency on o1-utils
• groupmap - already declares #![no_std] with extern crate alloc, only depends on ark-ec/ark-ff

Crates needing work

o1-utils (utils/)

rayon (feature-gate behind parallel, default-on):

• evaluations.rs: par_iter_mut in scale(), square(), pow()
• dense_polynomial.rs: par_iter_mut in scale()

std imports (replace with core/alloc):

• bitwise_operations.rs: std::cmp → core::cmp
• foreign_field.rs: std::fmt, std::ops → core::fmt, core::ops
• field_helpers.rs: std::ops::Neg, std::result::Result → core equivalents
• serialization.rs: std::io::BufReader — feature-gate behind std
• lazy_cache.rs: std::sync::Once — replace with spin::Once or similar no-std alternative

internal-tracing

std imports:

• lib.rs: std::time::SystemTime in time_to_micros() and now_micros() — these are used in production code
• std::rc::Rc, std::cell::RefCell, std::fmt in the enabled feature macro

Recommendation: feature-gate the entire tracing implementation behind std. A no-std verifier doesn't need runtime tracing.

poly-commitment

rayon (feature-gate behind parallel, default-on) — heavily used in verification-relevant code:

• commitment.rs: into_par_iter in multi_scalar_mul() (MSM verification)
• ipa.rs: par_iter in SRS::verify(), opening verification; also prover-only code in create_parallel(), commit_non_hiding(), open()
• combine.rs: par_iter/par_iter_mut in batch_add_assign_no_branch(), batch_add_assign(), batch_endo_in_place(), batch_negate_in_place(), batch_double_in_place(), affine_window_combine*(), window_combine()
• utils.rs: par_iter_mut in combine_polys(), polynomial evaluation; par_iter in batch_dlog_accumulator_check()

std imports:

• hash_map_cache.rs: Arc<Mutex<HashMap>> for Lagrange basis caching — feature-gate behind std, provide a no-caching or pre-computed fallback for no-std
• precomputed_srs.rs: std::fs, std::io, HashMap — feature-gate behind std (SRS loading from filesystem)
• lagrange_basis.rs: std::env, std::fs, LazyLock — feature-gate behind std (file-based cache)
• commitment.rs, ipa.rs, kzg.rs, combine.rs: std::ops, std::cmp, std::iter → core equivalents

kimchi

rayon (feature-gate behind parallel, default-on):

• prover.rs: multiple into_par_iter/par_iter_mut — prover-only, entire file can be gated behind prover feature
• circuits/expr.rs: ~15 uses of par_iter/par_iter_mut/into_par_iter for expression evaluation — used by verifier, needs sequential fallback
• circuits/constraints.rs: par_iter/into_par_iter for constraint evaluation — used by verifier
• lagrange_basis_evaluations.rs: into_par_iter for chunk evaluation — used by verifier
• circuits/polynomials/permutation.rs: multiple par_iter/into_par_iter — prover-only

std imports (verifier-critical files):

• verifier.rs: std::fmt::Debug → core::fmt::Debug
• verifier_index.rs: std::fs, std::io, std::path — feature-gate file I/O behind std; std::sync::Arc → alloc::sync::Arc
• circuits/expr.rs: std::collections::{HashMap, HashSet} → hashbrown or alloc equivalents
• circuits/constraints.rs: std::sync::Arc → alloc::sync::Arc
• circuits/berkeley_columns.rs: std::collections::HashMap → hashbrown
• alphas.rs: std::collections::HashMap → hashbrown; std::thread and std::env are test-only

Prover-only modules (gate behind prover feature, which implies std):

• prover.rs
• bench.rs
• snarky/ module
• circuits/polynomials/permutation.rs (prover functions)

---

Feature gate structure

Each crate gets one or more of:

• std (default-on): enables std::fs, std::io, std::sync::Mutex, std::time, HashMap/HashSet from std, and other std-only functionality
• parallel (default-on, implies std): enables rayon and parallel iterators
• prover (kimchi only, default-on, implies parallel + std): enables prover modules

A no-std verifier build uses --no-default-features (possibly with alloc).

Testing

• cargo check --no-default-features --target wasm32-unknown-unknown for each crate to verify no-std compilation
• cargo check and cargo test with defaults for std regression
• Integration test: verify a kimchi proof with --no-default-features

[richardpringle]

Progress update

PRs open for the first three dependency crates:

• o1-utils: [no-std]: o1-utils #3522 (CI green, awaiting review)
• internal-tracing: [no-std]: internal-tracing #3523 (CI green, awaiting review)
• poly-commitment: [no-std]: poly-commitment #3524 (CI green, awaiting review)

Kimchi itself (#3518) is next once these land.