sp1_ntt_gadget/
lib.rs

1//! # SP1 NTT Gadget
2//!
3//! High-performance NTT/INTT implementation for **Dilithium (ML-DSA-65)** verification
4//! in SP1 zkVM with **60-bit soundness** Polynomial Identity Check (PIC).
5//!
6//! ## Features
7//!
8//! - 🔐 **CRYSTALS-Dilithium Compatible**: 100% compatible with FIPS 204 (ML-DSA-65)
9//! - ⚡ **Optimized Montgomery Arithmetic**: Constant-time operations
10//! - 🛡️ **60-bit Soundness**: 4-challenge PIC with Fiat-Shamir
11//! - 🔧 **SP1 zkVM Ready**: Native precompile syscall integration
12//! - 📦 **no_std Compatible**: Works in embedded/zkVM environments
13//!
14//! ## Quick Start
15//!
16//! ### Basic NTT/INTT
17//!
18//! ```rust
19//! use sp1_ntt_gadget::{ntt::forward::ntt, ntt::inverse::intt, params::N};
20//!
21//! let mut coeffs = [0u32; N];
22//! coeffs[0] = 42;
23//! coeffs[1] = 59;
24//!
25//! // Forward NTT
26//! let original = coeffs;
27//! ntt(&mut coeffs);
28//!
29//! // Inverse NTT (roundtrip)
30//! intt(&mut coeffs);
31//!
32//! assert_eq!(coeffs, original);
33//! ```
34//!
35//! ### Verified NTT (with PIC)
36//!
37//! ```rust
38//! use sp1_ntt_gadget::{ntt::forward::ntt, pic::verifier::verify_ntt_simple, params::N};
39//!
40//! let mut coeffs = [0u32; N];
41//! for i in 0..N {
42//!     coeffs[i] = (i as u32 * 12345) % 8_380_417;
43//! }
44//!
45//! let original = coeffs;
46//! ntt(&mut coeffs);
47//!
48//! // Verify NTT correctness (60-bit soundness)
49//! let context = b"my-application-context";
50//! assert!(verify_ntt_simple(&original, &coeffs, context).is_ok());
51//! ```
52//!
53//! ## Security
54//!
55//! - **Soundness**: 60-bit (NUM_CHALLENGES=4, each ~15-bit security)
56//! - **Side-channel Resistance**: Constant-time Montgomery arithmetic
57//! - **Tested**: 132,731+ fuzzing iterations, 104 unit tests
58//!
59//! ## Parameters
60//!
61//! | Parameter | Value | Description |
62//! |-----------|-------|-------------|
63//! | **Q** | 8,380,417 | Dilithium prime (q ≡ 1 mod 512) |
64//! | **N** | 256 | Polynomial degree |
65//! | **NUM_CHALLENGES** | 4 | PIC challenges (60-bit soundness) |
66//!
67//! ## Module Structure
68//!
69//! ```text
70//! ┌─────────────────────────────────────────────────────────────┐
71//! │                    SP1 NTT Gadget                           │
72//! ├─────────────────┬─────────────────┬─────────────────────────┤
73//! │    params       │     ntt/        │        pic/             │
74//! │  (constants)    │ (NTT/INTT ops)  │  (verification)         │
75//! │                 │                 │                         │
76//! │  Q, ZETAS,      │ forward.rs      │  challenge.rs           │
77//! │  MONT_R, etc.   │ inverse.rs      │  verifier.rs            │
78//! │                 │ montgomery.rs   │                         │
79//! ├─────────────────┼─────────────────┼─────────────────────────┤
80//! │   validation/   │   precompile/   │                         │
81//! │ (input check)   │ (SP1 syscalls)  │                         │
82//! └─────────────────┴─────────────────┴─────────────────────────┘
83//! ```
84//!
85//! ## References
86//!
87//! - [FIPS 204 (ML-DSA) Specification](https://csrc.nist.gov/pubs/fips/204/final)
88//! - [CRYSTALS-Dilithium Reference](https://github.com/pq-crystals/dilithium)
89//! - [SP1 zkVM Documentation](https://docs.succinct.xyz/)
90
91#![cfg_attr(not(test), no_std)]
92#![deny(unsafe_code)]
93#![warn(missing_docs)]
94#![warn(clippy::all)]
95
96pub mod params;
97
98// Phase 1: Core NTT operations
99pub mod ntt;
100
101// Phase 2: PIC verification
102pub mod pic;
103
104// Phase 2: Input validation
105pub mod validation;
106
107// Phase 3: SP1 precompile integration
108pub mod precompile;
109
110// Re-exports for convenience
111pub use params::{N, Q, NUM_CHALLENGES, DOMAIN_SEP};
112pub use ntt::{ntt, intt};
113pub use pic::{derive_challenges, verify_ntt, verify_ntt_simple, VerificationError};
114pub use validation::{validate_coefficients, ValidationError};
115pub use precompile::{
116    NttInput, NttOutput,
117    execute_ntt_with_verification, execute_intt, execute_roundtrip,
118    ntt_syscall, intt_syscall,
119    NTT_PRECOMPILE_ID, INTT_PRECOMPILE_ID,
120};
sp1_ntt_gadget/lib.rs

sp1_ntt_gadget/
lib.rs
