si_commitment_scheme/
polynomial.rs

1//! Blake3-based polynomial commitments.
2//!
3//! A simple polynomial commitment scheme using Blake3 to commit to
4//! coefficient vectors, with evaluation proofs.
5
6use blake3::Hasher;
7use std::vec::Vec;
8
9/// A polynomial represented by its coefficients (degree d has d+1 coefficients).
10#[derive(Debug, Clone, PartialEq)]
11pub struct Polynomial {
12    /// Coefficients from lowest degree to highest.
13    pub coeffs: Vec<u64>,
14}
15
16impl Polynomial {
17    /// Create a new polynomial from coefficients.
18    pub fn new(coeffs: Vec<u64>) -> Self {
19        Self { coeffs }
20    }
21
22    /// Create the zero polynomial.
23    pub fn zero() -> Self {
24        Self { coeffs: vec![0] }
25    }
26
27    /// Evaluate the polynomial at a given point.
28    pub fn evaluate(&self, x: u64) -> u64 {
29        let mut result = 0u64;
30        let mut power = 1u64;
31        for &coeff in &self.coeffs {
32            result = result.wrapping_add(coeff.wrapping_mul(power));
33            power = power.wrapping_mul(x);
34        }
35        result
36    }
37
38    /// Degree of the polynomial.
39    pub fn degree(&self) -> usize {
40        if self.coeffs.is_empty() {
41            return 0;
42        }
43        let mut deg = self.coeffs.len() - 1;
44        while deg > 0 && self.coeffs[deg] == 0 {
45            deg -= 1;
46        }
47        deg
48    }
49
50    /// Number of coefficients.
51    pub fn len(&self) -> usize {
52        self.coeffs.len()
53    }
54
55    /// Whether the polynomial is empty.
56    pub fn is_empty(&self) -> bool {
57        self.coeffs.is_empty()
58    }
59}
60
61/// A Blake3-based polynomial commitment.
62#[derive(Debug, Clone)]
63pub struct PolynomialCommitment {
64    /// The commitment hash (32 bytes).
65    pub hash: [u8; 32],
66}
67
68impl PolynomialCommitment {
69    /// Commit to a polynomial by hashing its coefficients.
70    pub fn commit(poly: &Polynomial) -> Self {
71        let mut hasher = Hasher::new();
72        for &coeff in &poly.coeffs {
73            hasher.update(&coeff.to_le_bytes());
74        }
75        let hash = *hasher.finalize().as_bytes();
76        Self { hash }
77    }
78
79    /// Create an evaluation proof: hash of (commitment, x, y).
80    pub fn create_eval_proof(&self, x: u64, y: u64) -> EvalProof {
81        let mut hasher = Hasher::new();
82        hasher.update(&self.hash);
83        hasher.update(&x.to_le_bytes());
84        hasher.update(&y.to_le_bytes());
85        let proof_hash = *hasher.finalize().as_bytes();
86        EvalProof {
87            x,
88            y,
89            proof: proof_hash,
90        }
91    }
92
93    /// Verify an evaluation proof.
94    pub fn verify_eval(&self, proof: &EvalProof, poly: &Polynomial) -> bool {
95        let expected_y = poly.evaluate(proof.x);
96        if expected_y != proof.y {
97            return false;
98        }
99        let expected_proof = self.create_eval_proof(proof.x, proof.y);
100        expected_proof.proof == proof.proof
101    }
102}
103
104/// An evaluation proof for a polynomial commitment.
105#[derive(Debug, Clone)]
106pub struct EvalProof {
107    /// The evaluation point.
108    pub x: u64,
109    /// The claimed evaluation result.
110    pub y: u64,
111    /// The proof hash.
112    pub proof: [u8; 32],
113}
114
115#[cfg(test)]
116mod tests {
117    use super::*;
118
119    #[test]
120    fn polynomial_evaluation() {
121        // p(x) = 3 + 2x + x^2
122        let poly = Polynomial::new(vec![3, 2, 1]);
123        assert_eq!(poly.evaluate(0), 3);
124        assert_eq!(poly.evaluate(1), 6);
125        assert_eq!(poly.evaluate(2), 11);
126    }
127
128    #[test]
129    fn polynomial_degree() {
130        let poly = Polynomial::new(vec![3, 2, 1]);
131        assert_eq!(poly.degree(), 2);
132        let zero = Polynomial::zero();
133        assert_eq!(zero.degree(), 0);
134    }
135
136    #[test]
137    fn commit_deterministic() {
138        let poly = Polynomial::new(vec![1, 2, 3]);
139        let c1 = PolynomialCommitment::commit(&poly);
140        let c2 = PolynomialCommitment::commit(&poly);
141        assert_eq!(c1.hash, c2.hash);
142    }
143
144    #[test]
145    fn commit_different_polys() {
146        let p1 = Polynomial::new(vec![1, 2, 3]);
147        let p2 = Polynomial::new(vec![3, 2, 1]);
148        let c1 = PolynomialCommitment::commit(&p1);
149        let c2 = PolynomialCommitment::commit(&p2);
150        assert_ne!(c1.hash, c2.hash);
151    }
152
153    #[test]
154    fn eval_proof_verifies() {
155        let poly = Polynomial::new(vec![3, 2, 1]);
156        let comm = PolynomialCommitment::commit(&poly);
157        let y = poly.evaluate(5);
158        let proof = comm.create_eval_proof(5, y);
159        assert!(comm.verify_eval(&proof, &poly));
160    }
161
162    #[test]
163    fn eval_proof_wrong_y_fails() {
164        let poly = Polynomial::new(vec![3, 2, 1]);
165        let comm = PolynomialCommitment::commit(&poly);
166        let proof = comm.create_eval_proof(5, 999);
167        assert!(!comm.verify_eval(&proof, &poly));
168    }
169}
si_commitment_scheme/polynomial.rs

si_commitment_scheme/
polynomial.rs
