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
67impl<F: Field> Add for SepticDigest<F> {
68    type Output = Self;
69
70    fn add(self, rhs: Self) -> Self {
71        let start = Self::starting_digest().0;
72
73        let sum_a = start.add_incomplete(self.0).sub_incomplete(Self::zero().0);
74        let sum_b = sum_a.add_incomplete(rhs.0).sub_incomplete(Self::zero().0);
75
76        let mut result = sum_b;
77        result.add_assign(SepticDigest::<F>::zero().0);
78        result.sub_assign(start);
79
80        SepticDigest(result)
81    }
82}
83
84impl<F: Field> Sum for SepticDigest<F> {
85    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
86        let start = SepticDigest::<F>::starting_digest().0;
87
88        // Computation order is start + (digest1 - offset) + (digest2 - offset) + ... + (digestN -
89        // offset) + offset - start.
90        let mut ret = iter.fold(start, |acc, x| {
91            let sum_offset = acc.add_incomplete(x.0);
92            sum_offset.sub_incomplete(SepticDigest::<F>::zero().0)
93        });
94
95        ret.add_assign(SepticDigest::<F>::zero().0);
96        ret.sub_assign(start);
97        SepticDigest(ret)
98    }
99}
100
101#[cfg(test)]
102mod test {
103    use crate::septic_curve::{CURVE_WITNESS_DUMMY_POINT_X, CURVE_WITNESS_DUMMY_POINT_Y};
104
105    use super::*;
106
107    use sp1_primitives::SP1Field;
108    #[test]
109    fn test_const_points() {
110        let x: SepticExtension<SP1Field> = SepticExtension::from_base_fn(|i| {
111            SP1Field::from_canonical_u32(CURVE_CUMULATIVE_SUM_START_X[i])
112        });
113        let y: SepticExtension<SP1Field> = SepticExtension::from_base_fn(|i| {
114            SP1Field::from_canonical_u32(CURVE_CUMULATIVE_SUM_START_Y[i])
115        });
116        let point = SepticCurve { x, y };
117        assert!(point.check_on_point());
118        let x: SepticExtension<SP1Field> =
119            SepticExtension::from_base_fn(|i| SP1Field::from_canonical_u32(DIGEST_SUM_START_X[i]));
120        let y: SepticExtension<SP1Field> =
121            SepticExtension::from_base_fn(|i| SP1Field::from_canonical_u32(DIGEST_SUM_START_Y[i]));
122        let point = SepticCurve { x, y };
123        assert!(point.check_on_point());
124        let x: SepticExtension<SP1Field> = SepticExtension::from_base_fn(|i| {
125            SP1Field::from_canonical_u32(CURVE_WITNESS_DUMMY_POINT_X[i])
126        });
127        let y: SepticExtension<SP1Field> = SepticExtension::from_base_fn(|i| {
128            SP1Field::from_canonical_u32(CURVE_WITNESS_DUMMY_POINT_Y[i])
129        });
130        let point = SepticCurve { x, y };
131        assert!(point.check_on_point());
132    }
133}
sp1_hypercube/septic_digest.rs

sp1_hypercube/
septic_digest.rs
