sp1_hypercube/
septic_digest.rs

1//! Elliptic Curve digests with a starting point to avoid weierstrass addition exceptions.
2use crate::{septic_curve::SepticCurve, septic_extension::SepticExtension};
3use deepsize2::DeepSizeOf;
4use serde::{Deserialize, Serialize};
5use slop_algebra::{AbstractExtensionField, AbstractField, Field};
6use std::{iter::Sum, ops::Add};
7
8/// The x-coordinate for a curve point used as a starting cumulative sum for global permutation
9/// trace generation, derived from `sqrt(2)`.
10pub const CURVE_CUMULATIVE_SUM_START_X: [u32; 7] =
11    [0x1414213, 0x5623730, 0x9504880, 0x1688724, 0x2096980, 0x7856967, 0x1875376];
12
13/// The y-coordinate for a curve point used as a starting cumulative sum for global permutation
14/// trace generation, derived from `sqrt(2)`.
15pub const CURVE_CUMULATIVE_SUM_START_Y: [u32; 7] =
16    [2020310104, 1513506566, 1843922297, 2003644209, 805967281, 1882435203, 1623804682];
17
18/// The x-coordinate for a curve point used as a starting random point for digest accumulation,
19/// derived from `sqrt(3)`.
20pub const DIGEST_SUM_START_X: [u32; 7] =
21    [0x1732050, 0x8075688, 0x7729352, 0x7446341, 0x5058723, 0x6694280, 0x5253810];
22
23/// The y-coordinate for a curve point used as a starting random point for digest accumulation,
24/// derived from `sqrt(3)`.
25pub const DIGEST_SUM_START_Y: [u32; 7] =
26    [1095433104, 7540207, 1124564165, 2035506693, 11121645, 102781365, 398772161];
27
28/// A global cumulative sum digest, a point on the elliptic curve that `SepticCurve<F>` represents.
29/// As these digests start with the `CURVE_CUMULATIVE_SUM_START` point, they require special summing
30/// logic.
31#[derive(Debug, Clone, Copy, Default, Serialize, Deserialize, PartialEq, Eq, Hash, DeepSizeOf)]
32#[repr(C)]
33pub struct SepticDigest<F>(pub SepticCurve<F>);
34
35impl<F: AbstractField> SepticDigest<F> {
36    #[must_use]
37    /// The zero digest, the starting point of the accumulation of curve points derived from the
38    /// scheme.
39    pub fn zero() -> Self {
40        SepticDigest(SepticCurve {
41            x: SepticExtension::<F>::from_base_fn(|i| {
42                F::from_canonical_u32(CURVE_CUMULATIVE_SUM_START_X[i])
43            }),
44            y: SepticExtension::<F>::from_base_fn(|i| {
45                F::from_canonical_u32(CURVE_CUMULATIVE_SUM_START_Y[i])
46            }),
47        })
48    }
49
50    #[must_use]
51    /// The digest used for starting the accumulation of digests.
52    pub fn starting_digest() -> Self {
53        SepticDigest(SepticCurve {
54            x: SepticExtension::<F>::from_base_fn(|i| F::from_canonical_u32(DIGEST_SUM_START_X[i])),
55            y: SepticExtension::<F>::from_base_fn(|i| F::from_canonical_u32(DIGEST_SUM_START_Y[i])),
56        })
57    }
58}
59
60impl<F: Field> SepticDigest<F> {
61    /// Checks that the digest is zero, the starting point of the accumulation.
62    pub fn is_zero(&self) -> bool {
63        *self == SepticDigest::<F>::zero()
64    }
65
66    /// Adds two digests, returning `None` if an incomplete curve addition is exceptional.
67    pub fn checked_add(self, rhs: Self) -> Option<Self> {
68        fn checked_add_incomplete<F: Field>(
69            lhs: SepticCurve<F>,
70            rhs: SepticCurve<F>,
71        ) -> Option<SepticCurve<F>> {
72            if lhs.x == rhs.x {
73                return None;
74            }
75            Some(lhs.add_incomplete(rhs))
76        }
77
78        let start = Self::starting_digest().0;
79        let zero = Self::zero().0;
80
81        let sum_a = checked_add_incomplete(start, self.0)?;
82        let sum_a = checked_add_incomplete(sum_a, zero.neg())?;
83        let sum_b = checked_add_incomplete(sum_a, rhs.0)?;
84        let sum_b = checked_add_incomplete(sum_b, zero.neg())?;
85        let result = checked_add_incomplete(sum_b, zero)?;
86        let result = checked_add_incomplete(result, start.neg())?;
87
88        Some(SepticDigest(result))
89    }
90}
91
92impl<F: Field> Add for SepticDigest<F> {
93    type Output = Self;
94
95    fn add(self, rhs: Self) -> Self {
96        let start = Self::starting_digest().0;
97
98        let sum_a = start.add_incomplete(self.0).sub_incomplete(Self::zero().0);
99        let sum_b = sum_a.add_incomplete(rhs.0).sub_incomplete(Self::zero().0);
100
101        let mut result = sum_b;
102        result.add_assign(SepticDigest::<F>::zero().0);
103        result.sub_assign(start);
104
105        SepticDigest(result)
106    }
107}
108
109impl<F: Field> Sum for SepticDigest<F> {
110    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
111        let start = SepticDigest::<F>::starting_digest().0;
112
113        // Computation order is start + (digest1 - offset) + (digest2 - offset) + ... + (digestN -
114        // offset) + offset - start.
115        let mut ret = iter.fold(start, |acc, x| {
116            let sum_offset = acc.add_incomplete(x.0);
117            sum_offset.sub_incomplete(SepticDigest::<F>::zero().0)
118        });
119
120        ret.add_assign(SepticDigest::<F>::zero().0);
121        ret.sub_assign(start);
122        SepticDigest(ret)
123    }
124}
125
126#[cfg(test)]
127mod test {
128    use crate::septic_curve::{CURVE_WITNESS_DUMMY_POINT_X, CURVE_WITNESS_DUMMY_POINT_Y};
129
130    use super::*;
131
132    use sp1_primitives::SP1Field;
133    #[test]
134    fn test_const_points() {
135        let x: SepticExtension<SP1Field> = SepticExtension::from_base_fn(|i| {
136            SP1Field::from_canonical_u32(CURVE_CUMULATIVE_SUM_START_X[i])
137        });
138        let y: SepticExtension<SP1Field> = SepticExtension::from_base_fn(|i| {
139            SP1Field::from_canonical_u32(CURVE_CUMULATIVE_SUM_START_Y[i])
140        });
141        let point = SepticCurve { x, y };
142        assert!(point.check_on_point());
143        let x: SepticExtension<SP1Field> =
144            SepticExtension::from_base_fn(|i| SP1Field::from_canonical_u32(DIGEST_SUM_START_X[i]));
145        let y: SepticExtension<SP1Field> =
146            SepticExtension::from_base_fn(|i| SP1Field::from_canonical_u32(DIGEST_SUM_START_Y[i]));
147        let point = SepticCurve { x, y };
148        assert!(point.check_on_point());
149        let x: SepticExtension<SP1Field> = SepticExtension::from_base_fn(|i| {
150            SP1Field::from_canonical_u32(CURVE_WITNESS_DUMMY_POINT_X[i])
151        });
152        let y: SepticExtension<SP1Field> = SepticExtension::from_base_fn(|i| {
153            SP1Field::from_canonical_u32(CURVE_WITNESS_DUMMY_POINT_Y[i])
154        });
155        let point = SepticCurve { x, y };
156        assert!(point.check_on_point());
157    }
158
159    #[test]
160    fn test_checked_add_rejects_exceptional_intermediate() {
161        let lhs = SepticDigest::<SP1Field>::zero();
162        let intermediate = SepticDigest::<SP1Field>::starting_digest()
163            .0
164            .add_incomplete(lhs.0)
165            .sub_incomplete(SepticDigest::zero().0);
166
167        // This is a valid curve point, but adding it next would use equal x-coordinates and divide
168        // by zero in the incomplete addition formula.
169        assert!(intermediate.check_on_point());
170        assert_eq!(lhs.checked_add(SepticDigest(intermediate)), None);
171    }
172
173    #[test]
174    fn test_checked_add_matches_add() {
175        let lhs = SepticDigest::<SP1Field>::zero();
176        let rhs = SepticDigest::<SP1Field>::zero();
177
178        assert_eq!(lhs.checked_add(rhs), Some(lhs + rhs));
179    }
180}
sp1_hypercube/septic_digest.rs

sp1_hypercube/
septic_digest.rs
