zinc_poly/univariate/
binary_ref.rs

1use crate::{
2    ConstCoeffBitWidth, EvaluatablePolynomial, EvaluationError, Polynomial,
3    univariate::{dense::DensePolynomial, prepare_projection},
4};
5use crypto_primitives::{PrimeField, Semiring, semiring::boolean::Boolean};
6use derive_more::{
7    Add, AddAssign, AsRef, Display, From, Mul, MulAssign, Product, Sub, SubAssign, Sum,
8};
9use num_traits::{CheckedAdd, CheckedMul, CheckedSub, ConstZero, One, Zero};
10use rand::{distr::StandardUniform, prelude::*};
11use std::{
12    array,
13    hash::Hash,
14    iter::{Product, Sum},
15    marker::PhantomData,
16    ops::{Add, AddAssign, Deref, DerefMut, Mul, MulAssign, Sub, SubAssign},
17};
18use zinc_transcript::traits::{ConstTranscribable, GenTranscribable};
19use zinc_utils::{
20    from_ref::FromRef,
21    inner_product::{BooleanInnerProductAdd, InnerProduct, InnerProductError},
22    mul_by_scalar::MulByScalar,
23    named::Named,
24    projectable_to_field::ProjectableToField,
25};
26
27#[derive(
28    Add,
29    AddAssign,
30    AsRef,
31    Clone,
32    Debug,
33    From,
34    Default,
35    Display,
36    Hash,
37    PartialEq,
38    Eq,
39    Mul,
40    MulAssign,
41    Sub,
42    SubAssign,
43    Sum,
44    Product,
45)]
46#[repr(transparent)]
47pub struct BinaryRefPoly<const DEGREE_PLUS_ONE: usize>(DensePolynomial<Boolean, DEGREE_PLUS_ONE>);
48
49impl<const DEGREE_PLUS_ONE: usize> BinaryRefPoly<DEGREE_PLUS_ONE> {
50    #[inline(always)]
51    pub const fn inner(&self) -> &DensePolynomial<Boolean, DEGREE_PLUS_ONE> {
52        &self.0
53    }
54}
55
56impl<const DEGREE_PLUS_ONE: usize> From<BinaryRefPoly<DEGREE_PLUS_ONE>>
57    for DensePolynomial<Boolean, DEGREE_PLUS_ONE>
58{
59    #[inline(always)]
60    fn from(binary_poly: BinaryRefPoly<DEGREE_PLUS_ONE>) -> Self {
61        binary_poly.0
62    }
63}
64
65impl From<u32> for BinaryRefPoly<32> {
66    fn from(value: u32) -> Self {
67        Self(DensePolynomial {
68            coeffs: array::from_fn(|i| Boolean::new(value & (1 << i) != 0)),
69        })
70    }
71}
72
73impl From<u64> for BinaryRefPoly<64> {
74    fn from(value: u64) -> Self {
75        Self(DensePolynomial {
76            coeffs: array::from_fn(|i| Boolean::new(value & (1 << i) != 0)),
77        })
78    }
79}
80
81impl<const DEGREE_PLUS_ONE: usize> BinaryRefPoly<DEGREE_PLUS_ONE> {
82    /// Create a new polynomial with the given coefficients.
83    /// If the input has fewer than N+1 coefficients, the remaining slots will
84    /// be filled with zeros. If the input has more than N+1 coefficients,
85    /// it will panic.
86    #[inline(always)]
87    pub fn new(coeffs: impl AsRef<[Boolean]>) -> Self {
88        Self(DensePolynomial::new(coeffs))
89    }
90
91    /// Create a new polynomial with the given coefficients.
92    /// If the input has fewer than N+1 coefficients, the remaining slots will
93    /// be filled with zeros. If the input has more than N+1 coefficients,
94    /// it will panic.
95    #[inline(always)]
96    pub fn new_padded(coeffs: impl AsRef<[Boolean]>) -> Self {
97        Self(DensePolynomial::new_with_zero(coeffs, Boolean::ZERO))
98    }
99}
100
101impl<const DEGREE_PLUS_ONE: usize> Zero for BinaryRefPoly<DEGREE_PLUS_ONE> {
102    #[inline(always)]
103    fn zero() -> Self {
104        Self(DensePolynomial::zero())
105    }
106
107    #[inline(always)]
108    fn is_zero(&self) -> bool {
109        self.0.is_zero()
110    }
111}
112
113impl<const DEGREE_PLUS_ONE: usize> One for BinaryRefPoly<DEGREE_PLUS_ONE> {
114    #[inline(always)]
115    fn one() -> Self {
116        Self(DensePolynomial::one())
117    }
118}
119
120impl<'a, const DEGREE_PLUS_ONE: usize> Add<&'a Self> for BinaryRefPoly<DEGREE_PLUS_ONE> {
121    type Output = Self;
122
123    #[allow(clippy::arithmetic_side_effects)]
124    #[inline(always)]
125    fn add(self, rhs: &'a Self) -> Self::Output {
126        Self(self.0 + rhs.0)
127    }
128}
129
130impl<'a, const DEGREE_PLUS_ONE: usize> Sub<&'a Self> for BinaryRefPoly<DEGREE_PLUS_ONE> {
131    type Output = Self;
132
133    #[allow(clippy::arithmetic_side_effects)]
134    #[inline(always)]
135    fn sub(self, rhs: &'a Self) -> Self::Output {
136        Self(self.0 - rhs.0)
137    }
138}
139
140impl<const DEGREE_PLUS_ONE: usize> Mul for BinaryRefPoly<DEGREE_PLUS_ONE> {
141    type Output = Self;
142
143    #[allow(clippy::arithmetic_side_effects)]
144    #[inline(always)]
145    fn mul(self, rhs: Self) -> Self::Output {
146        Self(self.0 * rhs.0)
147    }
148}
149
150impl<'a, const DEGREE_PLUS_ONE: usize> Mul<&'a Self> for BinaryRefPoly<DEGREE_PLUS_ONE> {
151    type Output = Self;
152
153    #[allow(clippy::arithmetic_side_effects)]
154    #[inline(always)]
155    fn mul(self, rhs: &'a Self) -> Self::Output {
156        Self(self.0 * rhs.0)
157    }
158}
159
160impl<'a, const DEGREE_PLUS_ONE: usize> AddAssign<&'a Self> for BinaryRefPoly<DEGREE_PLUS_ONE> {
161    #[inline(always)]
162    fn add_assign(&mut self, rhs: &'a Self) {
163        self.0.add_assign(&rhs.0);
164    }
165}
166
167impl<'a, const DEGREE_PLUS_ONE: usize> SubAssign<&'a Self> for BinaryRefPoly<DEGREE_PLUS_ONE> {
168    #[inline(always)]
169    fn sub_assign(&mut self, rhs: &'a Self) {
170        self.0.sub_assign(&rhs.0);
171    }
172}
173
174impl<const DEGREE_PLUS_ONE: usize> MulAssign for BinaryRefPoly<DEGREE_PLUS_ONE> {
175    #[inline(always)]
176    fn mul_assign(&mut self, rhs: Self) {
177        self.0.mul_assign(&rhs.0);
178    }
179}
180
181impl<'a, const DEGREE_PLUS_ONE: usize> MulAssign<&'a Self> for BinaryRefPoly<DEGREE_PLUS_ONE> {
182    #[inline(always)]
183    fn mul_assign(&mut self, rhs: &'a Self) {
184        self.0.mul_assign(&rhs.0);
185    }
186}
187
188impl<const DEGREE_PLUS_ONE: usize> CheckedAdd for BinaryRefPoly<DEGREE_PLUS_ONE> {
189    #[inline(always)]
190    fn checked_add(&self, other: &Self) -> Option<Self> {
191        Some(Self(self.0.checked_add(&other.0)?))
192    }
193}
194
195impl<const DEGREE_PLUS_ONE: usize> CheckedSub for BinaryRefPoly<DEGREE_PLUS_ONE> {
196    #[inline(always)]
197    fn checked_sub(&self, other: &Self) -> Option<Self> {
198        Some(Self(self.0.checked_sub(&other.0)?))
199    }
200}
201
202impl<const DEGREE_PLUS_ONE: usize> CheckedMul for BinaryRefPoly<DEGREE_PLUS_ONE> {
203    #[inline(always)]
204    fn checked_mul(&self, other: &Self) -> Option<Self> {
205        Some(Self(self.0.checked_mul(&other.0)?))
206    }
207}
208
209impl<'a, const DEGREE_PLUS_ONE: usize> Sum<&'a Self> for BinaryRefPoly<DEGREE_PLUS_ONE> {
210    #[inline(always)]
211    fn sum<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
212        Self(iter.map(|x| &x.0).sum())
213    }
214}
215
216impl<'a, const DEGREE_PLUS_ONE: usize> Product<&'a Self> for BinaryRefPoly<DEGREE_PLUS_ONE> {
217    #[inline(always)]
218    fn product<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
219        Self(iter.map(|x| &x.0).product())
220    }
221}
222
223impl<const DEGREE_PLUS_ONE: usize> Semiring for BinaryRefPoly<DEGREE_PLUS_ONE> {}
224
225impl<const DEGREE_PLUS_ONE: usize> Distribution<BinaryRefPoly<DEGREE_PLUS_ONE>>
226    for StandardUniform
227{
228    #[inline(always)]
229    fn sample<Gen: Rng + ?Sized>(&self, rng: &mut Gen) -> BinaryRefPoly<DEGREE_PLUS_ONE> {
230        let coeffs: [Boolean; DEGREE_PLUS_ONE] = rng.random();
231
232        // I didn't manage to delegate this one to
233        // `DensePolynomial::sample` because of unsatisfied
234        // traits.
235
236        BinaryRefPoly(DensePolynomial::new(coeffs))
237    }
238}
239
240//
241// Zip-specific traits
242//
243impl<const DEGREE_PLUS_ONE: usize> Polynomial<Boolean> for BinaryRefPoly<DEGREE_PLUS_ONE> {
244    const DEGREE_BOUND: usize = DensePolynomial::<Boolean, DEGREE_PLUS_ONE>::DEGREE_BOUND;
245}
246
247impl<R: Clone + Zero + One + CheckedAdd + CheckedMul, const DEGREE_PLUS_ONE: usize>
248    EvaluatablePolynomial<Boolean, R> for BinaryRefPoly<DEGREE_PLUS_ONE>
249{
250    type EvaluationPoint = R;
251
252    fn evaluate_at_point(&self, point: &R) -> Result<R, EvaluationError> {
253        if DEGREE_PLUS_ONE.is_one() {
254            return Ok(R::zero());
255        }
256
257        let result = self.0.coeffs[1..]
258            .iter()
259            .try_fold(
260                (self.0.coeffs[0].widen::<R>(), R::one()),
261                |(mut acc, mut pow), coeff| {
262                    pow = pow.checked_mul(point).ok_or(EvaluationError::Overflow)?;
263
264                    if coeff.inner() {
265                        acc = acc.checked_add(&pow).ok_or(EvaluationError::Overflow)?;
266                    }
267
268                    Ok((acc, pow))
269                },
270            )?
271            .0;
272
273        Ok(result)
274    }
275}
276
277impl<const DEGREE_PLUS_ONE: usize> ConstCoeffBitWidth for BinaryRefPoly<DEGREE_PLUS_ONE> {
278    const COEFF_BIT_WIDTH: usize = DensePolynomial::<Boolean, DEGREE_PLUS_ONE>::COEFF_BIT_WIDTH;
279}
280
281impl<const DEGREE_PLUS_ONE: usize> Named for BinaryRefPoly<DEGREE_PLUS_ONE> {
282    fn type_name() -> String {
283        format!("BPoly<{}>", Self::DEGREE_BOUND)
284    }
285}
286
287impl<const DEGREE_PLUS_ONE: usize> GenTranscribable for BinaryRefPoly<DEGREE_PLUS_ONE> {
288    #[inline(always)]
289    fn read_transcription_bytes_exact(bytes: &[u8]) -> Self {
290        let value = u64::read_transcription_bytes_exact(bytes);
291        Self(DensePolynomial {
292            coeffs: array::from_fn(|i| Boolean::new(value & (1 << i) != 0)),
293        })
294    }
295
296    #[inline(always)]
297    fn write_transcription_bytes_exact(&self, buf: &mut [u8]) {
298        let mut value: u64 = 0;
299
300        self.0.coeffs.iter().enumerate().for_each(|(i, coeff)| {
301            if coeff.inner() {
302                value |= 1 << i;
303            }
304        });
305
306        value.write_transcription_bytes_exact(buf);
307    }
308}
309
310impl<const DEGREE_PLUS_ONE: usize> ConstTranscribable for BinaryRefPoly<DEGREE_PLUS_ONE> {
311    const NUM_BYTES: usize = u64::NUM_BYTES;
312}
313
314impl<const DEGREE_PLUS_ONE: usize> FromRef<BinaryRefPoly<DEGREE_PLUS_ONE>>
315    for BinaryRefPoly<DEGREE_PLUS_ONE>
316{
317    #[inline(always)]
318    fn from_ref(poly: &BinaryRefPoly<DEGREE_PLUS_ONE>) -> Self {
319        poly.clone()
320    }
321}
322
323impl<const DEGREE_PLUS_ONE: usize> From<&BinaryRefPoly<DEGREE_PLUS_ONE>>
324    for BinaryRefPoly<DEGREE_PLUS_ONE>
325{
326    #[inline(always)]
327    fn from(value: &BinaryRefPoly<DEGREE_PLUS_ONE>) -> Self {
328        Self::from_ref(value)
329    }
330}
331
332impl<const DEGREE_PLUS_ONE: usize> BinaryRefPoly<DEGREE_PLUS_ONE> {
333    #[inline(always)]
334    pub fn iter(&self) -> std::slice::Iter<'_, Boolean> {
335        self.0.iter()
336    }
337
338    #[inline(always)]
339    pub fn iter_mut(&mut self) -> std::slice::IterMut<'_, Boolean> {
340        self.0.iter_mut()
341    }
342}
343
344impl<const DEGREE_PLUS_ONE: usize> Deref for BinaryRefPoly<DEGREE_PLUS_ONE> {
345    type Target = [Boolean];
346
347    #[inline(always)]
348    fn deref(&self) -> &Self::Target {
349        self.0.deref()
350    }
351}
352
353impl<const DEGREE_PLUS_ONE: usize> DerefMut for BinaryRefPoly<DEGREE_PLUS_ONE> {
354    #[inline(always)]
355    fn deref_mut(&mut self) -> &mut Self::Target {
356        self.0.deref_mut()
357    }
358}
359
360#[derive(Clone, Debug)]
361pub struct BinaryRefPolyInnerProduct<R, const DEGREE_PLUS_ONE: usize>(PhantomData<R>);
362
363impl<Rhs, Out, const DEGREE_PLUS_ONE: usize> InnerProduct<BinaryRefPoly<DEGREE_PLUS_ONE>, Rhs, Out>
364    for BinaryRefPolyInnerProduct<Rhs, DEGREE_PLUS_ONE>
365where
366    Rhs: Clone,
367    Out: FromRef<Rhs> + CheckedAdd,
368{
369    #[inline(always)]
370    fn inner_product<const CHECK: bool>(
371        lhs: &BinaryRefPoly<DEGREE_PLUS_ONE>,
372        rhs: &[Rhs],
373        zero: Out,
374    ) -> Result<Out, InnerProductError> {
375        BooleanInnerProductAdd::inner_product::<CHECK>(&lhs.0.coeffs, rhs, zero)
376    }
377}
378
379impl<F, const DEGREE_PLUS_ONE: usize> ProjectableToField<F> for BinaryRefPoly<DEGREE_PLUS_ONE>
380where
381    F: PrimeField + FromRef<F> + 'static,
382{
383    fn prepare_projection(sampled_value: &F) -> impl Fn(&Self) -> F + 'static {
384        prepare_projection::<F, Self, _, DEGREE_PLUS_ONE>(sampled_value, |poly, i| {
385            poly.0.coeffs[i].inner()
386        })
387    }
388}
389
390// This could've been more generic, but keeping implementation consistent with
391// `BinaryU64Poly`.
392impl<const DEGREE_PLUS_ONE: usize> MulByScalar<&i64, DensePolynomial<i64, DEGREE_PLUS_ONE>>
393    for BinaryRefPoly<DEGREE_PLUS_ONE>
394{
395    fn mul_by_scalar<const CHECK: bool>(
396        &self,
397        rhs: &i64,
398    ) -> Option<DensePolynomial<i64, DEGREE_PLUS_ONE>> {
399        let mut coeffs: [i64; DEGREE_PLUS_ONE] = [0_i64; DEGREE_PLUS_ONE];
400
401        coeffs.iter_mut().enumerate().for_each(|(i, out)| {
402            if self.0.coeffs[i].inner() {
403                *out = *rhs;
404            }
405        });
406
407        Some(DensePolynomial { coeffs })
408    }
409}
410
411#[cfg(test)]
412mod tests {
413    use super::*;
414
415    #[test]
416    fn evaluate_is_correct() {
417        for i in 0..16 {
418            let poly = BinaryRefPoly::<4>::new([
419                (i & 0b0001 != 0).into(),
420                (i & 0b0010 != 0).into(),
421                (i & 0b0100 != 0).into(),
422                (i & 0b1000 != 0).into(),
423            ]);
424
425            let result = poly.evaluate_at_point(&2).unwrap();
426
427            assert_eq!(result, i);
428        }
429    }
430
431    #[test]
432    fn transcribable() {
433        let original =
434            BinaryRefPoly::<4>::new([true.into(), false.into(), true.into(), false.into()]);
435        let mut bytes = [0u8; BinaryRefPoly::<4>::NUM_BYTES];
436        assert_eq!(bytes.len(), u64::NUM_BYTES);
437
438        original.write_transcription_bytes_exact(&mut bytes);
439        let deserialized = BinaryRefPoly::<4>::read_transcription_bytes_exact(&bytes);
440        assert_eq!(original, deserialized);
441    }
442}
zinc_poly/univariate/binary_ref.rs

zinc_poly/univariate/
binary_ref.rs
