Crate sp1_ntt_gadget

Crate sp1_ntt_gadget 

Source
Expand description

§SP1 NTT Gadget

High-performance NTT/INTT implementation for Dilithium (ML-DSA-65) verification in SP1 zkVM with 60-bit soundness Polynomial Identity Check (PIC).

§Features

  • 🔐 CRYSTALS-Dilithium Compatible: 100% compatible with FIPS 204 (ML-DSA-65)
  • ⚡ Optimized Montgomery Arithmetic: Constant-time operations
  • 🛡️ 60-bit Soundness: 4-challenge PIC with Fiat-Shamir
  • 🔧 SP1 zkVM Ready: Native precompile syscall integration
  • 📦 no_std Compatible: Works in embedded/zkVM environments

§Quick Start

§Basic NTT/INTT

use sp1_ntt_gadget::{ntt::forward::ntt, ntt::inverse::intt, params::N};

let mut coeffs = [0u32; N];
coeffs[0] = 42;
coeffs[1] = 59;

// Forward NTT
let original = coeffs;
ntt(&mut coeffs);

// Inverse NTT (roundtrip)
intt(&mut coeffs);

assert_eq!(coeffs, original);

§Verified NTT (with PIC)

use sp1_ntt_gadget::{ntt::forward::ntt, pic::verifier::verify_ntt_simple, params::N};

let mut coeffs = [0u32; N];
for i in 0..N {
    coeffs[i] = (i as u32 * 12345) % 8_380_417;
}

let original = coeffs;
ntt(&mut coeffs);

// Verify NTT correctness (60-bit soundness)
let context = b"my-application-context";
assert!(verify_ntt_simple(&original, &coeffs, context).is_ok());

§Security

  • Soundness: 60-bit (NUM_CHALLENGES=4, each ~15-bit security)
  • Side-channel Resistance: Constant-time Montgomery arithmetic
  • Tested: 132,731+ fuzzing iterations, 104 unit tests

§Parameters

ParameterValueDescription
Q8,380,417Dilithium prime (q ≡ 1 mod 512)
N256Polynomial degree
NUM_CHALLENGES4PIC challenges (60-bit soundness)

§Module Structure

┌─────────────────────────────────────────────────────────────┐
│                    SP1 NTT Gadget                           │
├─────────────────┬─────────────────┬─────────────────────────┤
│    params       │     ntt/        │        pic/             │
│  (constants)    │ (NTT/INTT ops)  │  (verification)         │
│                 │                 │                         │
│  Q, ZETAS,      │ forward.rs      │  challenge.rs           │
│  MONT_R, etc.   │ inverse.rs      │  verifier.rs            │
│                 │ montgomery.rs   │                         │
├─────────────────┼─────────────────┼─────────────────────────┤
│   validation/   │   precompile/   │                         │
│ (input check)   │ (SP1 syscalls)  │                         │
└─────────────────┴─────────────────┴─────────────────────────┘

§References

Re-exports§

pub use params::N;
pub use params::Q;
pub use params::NUM_CHALLENGES;
pub use params::DOMAIN_SEP;
pub use ntt::ntt;
pub use ntt::intt;
pub use pic::derive_challenges;
pub use pic::verify_ntt;
pub use pic::verify_ntt_simple;
pub use pic::VerificationError;
pub use validation::validate_coefficients;
pub use validation::ValidationError;
pub use precompile::NttInput;
pub use precompile::NttOutput;
pub use precompile::execute_ntt_with_verification;
pub use precompile::execute_intt;
pub use precompile::execute_roundtrip;
pub use precompile::ntt_syscall;
pub use precompile::intt_syscall;
pub use precompile::NTT_PRECOMPILE_ID;
pub use precompile::INTT_PRECOMPILE_ID;

Modules§

ntt
NTT (Number Theoretic Transform) operations
params
Dilithium NTT Constants for ML-DSA-65 (FIPS 204)
pic
Polynomial Identity Check (PIC) module
precompile
SP1 Precompile Integration Module
validation
Input validation module