commonware_math/
synthetic.rs

1//! Synthetic linear combinations of free generators and concrete points.
2//!
3//! A [`Synthetic`] stores a linear combination where some terms reference
4//! abstract generators (identified by `u32` indices) and others carry
5//! concrete points. Generators are supplied later via [`Synthetic::eval`] to
6//! produce a concrete group element.
7//!
8//! Scaling multiplies all weights. Addition merges the free terms (adding
9//! weights at matching indices) and concatenates the concrete terms.
10//!
11//! # Usage
12//!
13//! ```rust
14//! # #[cfg(feature = "arbitrary")]
15//! # {
16//! # use commonware_math::{algebra::{Additive, CryptoGroup, Ring, Space}, test::{F, G}, synthetic::Synthetic};
17//! # use commonware_parallel::Sequential;
18//! // Symbolic generators G_0, G_1.
19//! let [g0, g1] = Synthetic::<F, G>::generators_array();
20//!
21//! // Build 2*G_0 + 3*G_1.
22//! let expr = (g0 * &F::from(2u64)) + &(g1 * &F::from(3u64));
23//!
24//! // Evaluate with concrete points.
25//! // In practice, use independent generators (e.g. from hash_to_group)
26//! // rather than scaling a single one.
27//! let a = G::generator();
28//! let b = a * &F::from(5u64);
29//! let result = expr.eval(&[a, b], &Sequential);
30//! assert_eq!(result, (a * &F::from(2u64)) + &(b * &F::from(3u64)));
31//! # }
32//! ```
33
34use crate::algebra::{Additive, Object, Ring, Space};
35#[cfg(not(feature = "std"))]
36use alloc::{collections::BTreeMap, vec::Vec};
37use commonware_parallel::{Sequential, Strategy};
38use core::{
39    cmp::Ordering,
40    ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign},
41};
42#[cfg(feature = "std")]
43use std::collections::BTreeMap;
44
45/// A linear combination of free generators and concrete points.
46///
47/// Free terms are indexed by `u32` and bound later via [`Self::eval`].
48/// Concrete terms carry their point directly.
49#[derive(Clone, Debug)]
50pub struct Synthetic<F, G> {
51    free: BTreeMap<u32, F>,
52    concrete: Vec<(F, G)>,
53}
54
55impl<F, G> Default for Synthetic<F, G> {
56    fn default() -> Self {
57        Self {
58            free: Default::default(),
59            concrete: Default::default(),
60        }
61    }
62}
63
64impl<F, G> Synthetic<F, G> {
65    /// Construct from known weighted points.
66    pub fn concrete(weighted_points: impl IntoIterator<Item = (F, G)>) -> Self {
67        Self {
68            concrete: weighted_points.into_iter().collect(),
69            ..Default::default()
70        }
71    }
72
73    /// The maximum free generator index, or `None` if there are no free terms.
74    pub fn max_free_index(&self) -> Option<u32> {
75        self.free.keys().next_back().copied()
76    }
77
78    /// Apply `f` to every weight (free and concrete).
79    fn for_each_weight(&mut self, mut f: impl FnMut(&mut F)) {
80        self.free.values_mut().for_each(&mut f);
81        self.concrete.iter_mut().for_each(|(w, _)| f(w));
82    }
83
84    /// Yield symbolic generators `G_0, G_1, G_2, ...` with unit weight.
85    pub fn generators() -> impl Iterator<Item = Self>
86    where
87        F: Ring,
88    {
89        (0u32..).map(|i| {
90            let mut out = Self::default();
91            out.free.insert(i, F::one());
92            out
93        })
94    }
95
96    /// Return `[G_0, G_1, ..., G_{N-1}]` as symbolic generators with unit weight.
97    pub fn generators_array<const N: usize>() -> [Self; N]
98    where
99        F: Ring,
100    {
101        let mut iter = Self::generators();
102        core::array::from_fn(|_| iter.next().expect("generators is infinite"))
103    }
104}
105
106impl<F: Additive, G: Space<F>> Synthetic<F, G> {
107    /// Evaluate, substituting concrete generators for the free indices.
108    ///
109    /// `generators[i]` provides the point for free index `i`.
110    ///
111    /// # Panics
112    ///
113    /// Panics if `generators` does not contain an entry for every free index.
114    pub fn eval(self, generators: &[G], strategy: &impl Strategy) -> G {
115        let total = self.free.len() + self.concrete.len();
116        let mut points = Vec::with_capacity(total);
117        let mut weights = Vec::with_capacity(total);
118        for (idx, weight) in self.free {
119            points.push(generators[idx as usize].clone());
120            weights.push(weight);
121        }
122        for (weight, point) in self.concrete {
123            points.push(point);
124            weights.push(weight);
125        }
126        G::msm(&points, &weights, strategy)
127    }
128}
129
130impl<F: Additive, G: Space<F>> PartialEq for Synthetic<F, G> {
131    fn eq(&self, other: &Self) -> bool {
132        let zero = F::zero();
133        let mut lhs = self.free.iter().peekable();
134        let mut rhs = other.free.iter().peekable();
135        let free_equal = core::iter::from_fn(|| {
136            let ordering = match (lhs.peek().copied(), rhs.peek().copied()) {
137                (Some((li, _)), Some((ri, _))) => li.cmp(ri),
138                (Some(_), None) => Ordering::Less,
139                (None, Some(_)) => Ordering::Greater,
140                (None, None) => return None,
141            };
142            Some(match ordering {
143                Ordering::Equal => (lhs.next().map(|(_, w)| w), rhs.next().map(|(_, w)| w)),
144                Ordering::Less => (lhs.next().map(|(_, w)| w), None),
145                Ordering::Greater => (None, rhs.next().map(|(_, w)| w)),
146            })
147        })
148        .all(|(lw, rw)| lw.unwrap_or(&zero) == rw.unwrap_or(&zero));
149        if !free_equal {
150            return false;
151        }
152
153        let size = self.concrete.len() + other.concrete.len();
154        let mut points = Vec::with_capacity(size);
155        let mut weights = Vec::with_capacity(size);
156        for (weight, point) in &self.concrete {
157            points.push(point.clone());
158            weights.push(weight.clone());
159        }
160        for (weight, point) in &other.concrete {
161            points.push(point.clone());
162            weights.push(-weight.clone());
163        }
164        G::msm(&points, &weights, &Sequential) == G::zero()
165    }
166}
167
168impl<F: Additive, G: Space<F>> Eq for Synthetic<F, G> {}
169
170impl<F: Additive, G: Space<F>> Object for Synthetic<F, G> {}
171
172impl<'a, F: Additive, G: Space<F>> AddAssign<&'a Self> for Synthetic<F, G> {
173    fn add_assign(&mut self, rhs: &'a Self) {
174        for (idx, weight) in &rhs.free {
175            self.free
176                .entry(*idx)
177                .and_modify(|existing| *existing += weight)
178                .or_insert_with(|| weight.clone());
179        }
180        self.concrete.extend(rhs.concrete.iter().cloned());
181    }
182}
183
184impl<'a, F: Additive, G: Space<F>> Add<&'a Self> for Synthetic<F, G> {
185    type Output = Self;
186
187    fn add(mut self, rhs: &'a Self) -> Self::Output {
188        self += rhs;
189        self
190    }
191}
192
193impl<'a, F: Additive, G: Space<F>> SubAssign<&'a Self> for Synthetic<F, G> {
194    fn sub_assign(&mut self, rhs: &'a Self) {
195        for (idx, weight) in &rhs.free {
196            self.free
197                .entry(*idx)
198                .and_modify(|existing| *existing -= weight)
199                .or_insert_with(|| -weight.clone());
200        }
201        self.concrete.extend(
202            rhs.concrete
203                .iter()
204                .cloned()
205                .map(|(weight, point)| (-weight, point)),
206        );
207    }
208}
209
210impl<'a, F: Additive, G: Space<F>> Sub<&'a Self> for Synthetic<F, G> {
211    type Output = Self;
212
213    fn sub(mut self, rhs: &'a Self) -> Self::Output {
214        self -= rhs;
215        self
216    }
217}
218
219impl<F: Additive, G: Space<F>> Neg for Synthetic<F, G> {
220    type Output = Self;
221
222    fn neg(mut self) -> Self::Output {
223        self.for_each_weight(|w| *w = -core::mem::replace(w, F::zero()));
224        self
225    }
226}
227
228impl<F: Additive, G: Space<F>> Additive for Synthetic<F, G> {
229    fn zero() -> Self {
230        Self::default()
231    }
232}
233
234impl<'a, F: Space<F>, G: Space<F>> MulAssign<&'a F> for Synthetic<F, G> {
235    fn mul_assign(&mut self, rhs: &'a F) {
236        self.for_each_weight(|w| *w *= rhs);
237    }
238}
239
240impl<'a, F: Space<F>, G: Space<F>> Mul<&'a F> for Synthetic<F, G> {
241    type Output = Self;
242
243    fn mul(mut self, rhs: &'a F) -> Self::Output {
244        self *= rhs;
245        self
246    }
247}
248
249impl<F: Space<F>, G: Space<F>> Space<F> for Synthetic<F, G> {}
250
251#[cfg(any(test, feature = "arbitrary"))]
252impl<'a, F: arbitrary::Arbitrary<'a>, G: arbitrary::Arbitrary<'a>> arbitrary::Arbitrary<'a>
253    for Synthetic<F, G>
254{
255    fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
256        let len: usize = u.int_in_range(0..=8)?;
257        let free: BTreeMap<u32, F> = (0..len)
258            .map(|_| Ok((u.int_in_range(0..=32u32)?, u.arbitrary()?)))
259            .collect::<arbitrary::Result<_>>()?;
260        Ok(Self {
261            free,
262            concrete: u.arbitrary()?,
263        })
264    }
265}
266
267#[commonware_macros::stability(ALPHA)]
268#[cfg(any(test, feature = "fuzz"))]
269pub mod fuzz {
270    use super::*;
271    use crate::{
272        algebra::test_suites,
273        test::{F, G},
274    };
275    use arbitrary::{Arbitrary, Unstructured};
276    use commonware_parallel::Sequential;
277
278    #[derive(Debug, Arbitrary)]
279    pub enum Plan {
280        EvalMatchesMsm(Vec<F>, Vec<(F, G)>),
281        EvalIsLinear(Synthetic<F, G>, Synthetic<F, G>, Vec<G>),
282        FuzzAdditive,
283        FuzzSpaceRing,
284    }
285
286    fn cover_generators(
287        u: &mut Unstructured<'_>,
288        virtuals: &[&Synthetic<F, G>],
289        mut gens: Vec<G>,
290    ) -> arbitrary::Result<Vec<G>> {
291        let needed = virtuals
292            .iter()
293            .filter_map(|v| v.max_free_index())
294            .max()
295            .map_or(0, |m| m as usize + 1);
296        while gens.len() < needed {
297            gens.push(u.arbitrary()?);
298        }
299        Ok(gens)
300    }
301
302    impl Plan {
303        pub fn run(self, u: &mut Unstructured<'_>) -> arbitrary::Result<()> {
304            match self {
305                Self::EvalMatchesMsm(free_weights, concrete) => {
306                    let mut expr = Synthetic::<F, G>::zero();
307                    let mut gen_iter = Synthetic::<F, G>::generators();
308                    for w in &free_weights {
309                        expr += &(gen_iter.next().unwrap() * w);
310                    }
311                    expr += &Synthetic::concrete(concrete.iter().cloned());
312
313                    let gens: Vec<G> = (0..free_weights.len())
314                        .map(|_| u.arbitrary())
315                        .collect::<arbitrary::Result<_>>()?;
316
317                    let mut points = Vec::with_capacity(free_weights.len() + concrete.len());
318                    let mut weights = Vec::with_capacity(free_weights.len() + concrete.len());
319                    for (i, w) in free_weights.into_iter().enumerate() {
320                        points.push(gens[i]);
321                        weights.push(w);
322                    }
323                    for (w, p) in &concrete {
324                        points.push(*p);
325                        weights.push(*w);
326                    }
327
328                    assert_eq!(
329                        expr.eval(&gens, &Sequential),
330                        G::msm(&points, &weights, &Sequential)
331                    );
332                }
333                Self::EvalIsLinear(lhs, rhs, generators) => {
334                    let gens = cover_generators(u, &[&lhs, &rhs], generators)?;
335                    let lhs_eval = lhs.clone().eval(&gens, &Sequential);
336                    let rhs_eval = rhs.clone().eval(&gens, &Sequential);
337                    assert_eq!((lhs + &rhs).eval(&gens, &Sequential), lhs_eval + &rhs_eval);
338                }
339                Self::FuzzAdditive => {
340                    test_suites::fuzz_additive::<Synthetic<F, G>>(u)?;
341                }
342                Self::FuzzSpaceRing => {
343                    test_suites::fuzz_space_ring::<F, Synthetic<F, G>>(u)?;
344                }
345            }
346            Ok(())
347        }
348    }
349
350    #[test]
351    fn test_fuzz() {
352        commonware_invariants::minifuzz::test(|u| u.arbitrary::<Plan>()?.run(u));
353    }
354}
355
356#[cfg(test)]
357mod test {
358    use super::*;
359    use crate::{
360        algebra::CryptoGroup,
361        test::{F, G},
362    };
363
364    #[test]
365    fn generators_array_tracks_indices() {
366        let empty = Synthetic::<F, G>::zero();
367        assert_eq!(empty.max_free_index(), None);
368
369        let [g0, g1, g2] = Synthetic::<F, G>::generators_array();
370        assert_eq!(g0.max_free_index(), Some(0));
371        assert_eq!(g1.max_free_index(), Some(1));
372        assert_eq!(g2.max_free_index(), Some(2));
373    }
374
375    #[test]
376    fn equality_handles_zero_free_weights_and_concrete_terms() {
377        let [g0] = Synthetic::<F, G>::generators_array();
378        let zero_weight = g0 * &F::zero();
379        assert_eq!(Synthetic::<F, G>::zero(), zero_weight);
380
381        let point = G::generator();
382        let concrete = Synthetic::concrete([(F::from(3u64), point)]);
383        assert_eq!(concrete.clone(), concrete);
384        assert_ne!(concrete, Synthetic::zero());
385    }
386}
commonware_math/synthetic.rs

commonware_math/
synthetic.rs
