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

zinc_poly/univariate/
binary_ref.rs
