zinc_poly/univariate/
binary_ref.rs

1use crate::{
2    ConstCoeffBitWidth, EvaluatablePolynomial, EvaluationError, Polynomial,
3    univariate::{dense::DensePolynomial, prepare_projection},
4};
5use crypto_primitives::{FieldConfig, Wrapper, semiring::boolean::Boolean};
6use derive_more::{AsRef, Display, From};
7use num_traits::{CheckedAdd, CheckedMul, ConstOne, ConstZero, One, Zero};
8use rand::{distr::StandardUniform, prelude::*};
9use std::{
10    array,
11    hash::Hash,
12    marker::PhantomData,
13    ops::{Add, Deref, DerefMut, Mul},
14};
15use zinc_transcript::traits::{ConstTranscribable, GenTranscribable};
16use zinc_utils::{
17    from_ref::FromRef,
18    inner_product::{BooleanInnerProductAdd, InnerProduct, InnerProductError},
19    mul_by_scalar::MulByScalar,
20    named::Named,
21    projectable_to_field::ProjectableToField,
22};
23
24#[derive(AsRef, Clone, Debug, From, Default, Display, Hash, PartialEq, Eq)]
25#[repr(transparent)]
26pub struct BinaryRefPoly<const DEGREE_PLUS_ONE: usize>(DensePolynomial<Boolean, DEGREE_PLUS_ONE>);
27
28impl<const DEGREE_PLUS_ONE: usize> BinaryRefPoly<DEGREE_PLUS_ONE> {
29    #[inline(always)]
30    pub const fn inner(&self) -> &DensePolynomial<Boolean, DEGREE_PLUS_ONE> {
31        &self.0
32    }
33}
34
35impl<const DEGREE_PLUS_ONE: usize> From<BinaryRefPoly<DEGREE_PLUS_ONE>>
36    for DensePolynomial<Boolean, DEGREE_PLUS_ONE>
37{
38    #[inline(always)]
39    fn from(binary_poly: BinaryRefPoly<DEGREE_PLUS_ONE>) -> Self {
40        binary_poly.0
41    }
42}
43
44impl<const DEGREE_PLUS_ONE: usize> From<u32> for BinaryRefPoly<DEGREE_PLUS_ONE> {
45    #[inline(always)]
46    fn from(value: u32) -> Self {
47        // Keep masking enforced in a single place
48        Self::from(u64::from(value))
49    }
50}
51
52impl<const DEGREE_PLUS_ONE: usize> From<u64> for BinaryRefPoly<DEGREE_PLUS_ONE> {
53    #[inline(always)]
54    fn from(value: u64) -> Self {
55        // Bit `i` of `value` becomes the coefficient of `X^i`. Bits at
56        // positions `>= 64` are not present in `u64` and are therefore zero;
57        // bits at positions `>= DEGREE_PLUS_ONE` are dropped by virtue of
58        // the fixed-size coefficient array.
59        Self(DensePolynomial {
60            coeffs: array::from_fn(|i| Boolean::new(i < 64 && value & (1_u64 << i) != 0)),
61        })
62    }
63}
64
65impl<const DEGREE_PLUS_ONE: usize> BinaryRefPoly<DEGREE_PLUS_ONE> {
66    #[inline(always)]
67    pub fn new(coeffs: [Boolean; DEGREE_PLUS_ONE]) -> Self {
68        Self(DensePolynomial { coeffs })
69    }
70
71    /// Create a new polynomial with the given coefficients.
72    /// If the input has fewer than N+1 coefficients, the remaining slots will
73    /// be filled with zeros. If the input has more than N+1 coefficients,
74    /// it will panic.
75    #[inline(always)]
76    pub fn new_padded(coeffs: impl AsRef<[Boolean]>) -> Self {
77        Self(DensePolynomial::new_with_zero(coeffs, Boolean::ZERO))
78    }
79}
80
81impl<const DEGREE_PLUS_ONE: usize> Zero for BinaryRefPoly<DEGREE_PLUS_ONE> {
82    #[inline(always)]
83    fn zero() -> Self {
84        Self(DensePolynomial::new_with_zero([], Boolean::ZERO))
85    }
86
87    #[inline(always)]
88    fn is_zero(&self) -> bool {
89        self.0.iter().all(|c| c.is_zero())
90    }
91}
92
93impl<const DEGREE_PLUS_ONE: usize> One for BinaryRefPoly<DEGREE_PLUS_ONE> {
94    #[inline(always)]
95    fn one() -> Self {
96        Self(DensePolynomial::new_with_zero(
97            [Boolean::ONE],
98            Boolean::ZERO,
99        ))
100    }
101}
102
103impl<const DEGREE_PLUS_ONE: usize> Add<Self> for BinaryRefPoly<DEGREE_PLUS_ONE> {
104    type Output = Self;
105
106    fn add(self, _rhs: Self) -> Self::Output {
107        panic!("Binary polynomials addition is not defined")
108    }
109}
110
111impl<const DEGREE_PLUS_ONE: usize> Mul for BinaryRefPoly<DEGREE_PLUS_ONE> {
112    type Output = Self;
113
114    fn mul(self, _rhs: Self) -> Self::Output {
115        panic!("Binary polynomials multiplication is not defined")
116    }
117}
118
119impl<const DEGREE_PLUS_ONE: usize> Distribution<BinaryRefPoly<DEGREE_PLUS_ONE>>
120    for StandardUniform
121{
122    #[inline(always)]
123    fn sample<Gen: Rng + ?Sized>(&self, rng: &mut Gen) -> BinaryRefPoly<DEGREE_PLUS_ONE> {
124        let coeffs: [Boolean; DEGREE_PLUS_ONE] = rng.random();
125
126        // I didn't manage to delegate this one to
127        // `DensePolynomial::sample` because of unsatisfied
128        // traits.
129
130        BinaryRefPoly(DensePolynomial { coeffs })
131    }
132}
133
134//
135// Zip-specific traits
136//
137
138impl<const DEGREE_PLUS_ONE: usize> Polynomial<Boolean> for BinaryRefPoly<DEGREE_PLUS_ONE> {
139    const DEGREE_BOUND: usize = DensePolynomial::<Boolean, DEGREE_PLUS_ONE>::DEGREE_BOUND;
140}
141
142impl<R: Clone + Zero + One + CheckedAdd + CheckedMul, const DEGREE_PLUS_ONE: usize>
143    EvaluatablePolynomial<Boolean, R> for BinaryRefPoly<DEGREE_PLUS_ONE>
144{
145    type EvaluationPoint = R;
146
147    fn evaluate_at_point(&self, point: &R) -> Result<R, EvaluationError> {
148        if DEGREE_PLUS_ONE.is_one() {
149            return Ok(R::zero());
150        }
151
152        let result = self.0.coeffs[1..]
153            .iter()
154            .try_fold(
155                (self.0.coeffs[0].widen::<R>(), R::one()),
156                |(mut acc, mut pow), coeff| {
157                    pow = pow.checked_mul(point).ok_or(EvaluationError::Overflow)?;
158
159                    if *coeff.inner() {
160                        acc = acc.checked_add(&pow).ok_or(EvaluationError::Overflow)?;
161                    }
162
163                    Ok((acc, pow))
164                },
165            )?
166            .0;
167
168        Ok(result)
169    }
170}
171
172impl<const DEGREE_PLUS_ONE: usize> ConstCoeffBitWidth for BinaryRefPoly<DEGREE_PLUS_ONE> {
173    const COEFF_BIT_WIDTH: usize = DensePolynomial::<Boolean, DEGREE_PLUS_ONE>::COEFF_BIT_WIDTH;
174}
175
176impl<const DEGREE_PLUS_ONE: usize> Named for BinaryRefPoly<DEGREE_PLUS_ONE> {
177    fn type_name() -> String {
178        format!("BPoly<{}>", Self::DEGREE_BOUND)
179    }
180}
181
182impl<const DEGREE_PLUS_ONE: usize> GenTranscribable for BinaryRefPoly<DEGREE_PLUS_ONE> {
183    #[inline(always)]
184    fn read_transcription_bytes_exact(bytes: &[u8]) -> Self {
185        let value = u64::read_transcription_bytes_exact(bytes);
186        Self(DensePolynomial {
187            coeffs: array::from_fn(|i| Boolean::new(value & (1 << i) != 0)),
188        })
189    }
190
191    #[inline(always)]
192    fn write_transcription_bytes_exact(&self, buf: &mut [u8]) {
193        let mut value: u64 = 0;
194
195        self.0.coeffs.iter().enumerate().for_each(|(i, coeff)| {
196            if *coeff.inner() {
197                value |= 1 << i;
198            }
199        });
200
201        value.write_transcription_bytes_exact(buf);
202    }
203}
204
205impl<const DEGREE_PLUS_ONE: usize> ConstTranscribable for BinaryRefPoly<DEGREE_PLUS_ONE> {
206    const NUM_BYTES: usize = u64::NUM_BYTES;
207}
208
209impl<const DEGREE_PLUS_ONE: usize> FromRef<BinaryRefPoly<DEGREE_PLUS_ONE>>
210    for BinaryRefPoly<DEGREE_PLUS_ONE>
211{
212    #[inline(always)]
213    fn from_ref(poly: &BinaryRefPoly<DEGREE_PLUS_ONE>) -> Self {
214        poly.clone()
215    }
216}
217
218impl<const DEGREE_PLUS_ONE: usize> From<&BinaryRefPoly<DEGREE_PLUS_ONE>>
219    for BinaryRefPoly<DEGREE_PLUS_ONE>
220{
221    #[inline(always)]
222    fn from(value: &BinaryRefPoly<DEGREE_PLUS_ONE>) -> Self {
223        Self::from_ref(value)
224    }
225}
226
227impl<const DEGREE_PLUS_ONE: usize> BinaryRefPoly<DEGREE_PLUS_ONE> {
228    #[inline(always)]
229    pub fn iter(&self) -> std::slice::Iter<'_, Boolean> {
230        self.0.iter()
231    }
232
233    #[inline(always)]
234    pub fn iter_mut(&mut self) -> std::slice::IterMut<'_, Boolean> {
235        self.0.iter_mut()
236    }
237}
238
239impl<const DEGREE_PLUS_ONE: usize> Deref for BinaryRefPoly<DEGREE_PLUS_ONE> {
240    type Target = [Boolean];
241
242    #[inline(always)]
243    fn deref(&self) -> &Self::Target {
244        self.0.deref()
245    }
246}
247
248impl<const DEGREE_PLUS_ONE: usize> DerefMut for BinaryRefPoly<DEGREE_PLUS_ONE> {
249    #[inline(always)]
250    fn deref_mut(&mut self) -> &mut Self::Target {
251        self.0.deref_mut()
252    }
253}
254
255#[derive(Clone, Debug)]
256pub struct BinaryRefPolyInnerProduct<R, const DEGREE_PLUS_ONE: usize>(PhantomData<R>);
257
258impl<C, Rhs, Out, const DEGREE_PLUS_ONE: usize>
259    InnerProduct<C, BinaryRefPoly<DEGREE_PLUS_ONE>, Rhs, Out>
260    for BinaryRefPolyInnerProduct<Rhs, DEGREE_PLUS_ONE>
261where
262    Rhs: Clone,
263    Out: FromRef<Rhs> + CheckedAdd,
264{
265    #[inline(always)]
266    fn inner_product<const CHECK: bool>(
267        cfg: &C,
268        lhs: &BinaryRefPoly<DEGREE_PLUS_ONE>,
269        rhs: &[Rhs],
270        zero: Out,
271    ) -> Result<Out, InnerProductError> {
272        BooleanInnerProductAdd::inner_product::<CHECK>(cfg, &lhs.0.coeffs, rhs, zero)
273    }
274}
275
276impl<C, const DEGREE_PLUS_ONE: usize> ProjectableToField<C> for BinaryRefPoly<DEGREE_PLUS_ONE>
277where
278    C: FieldConfig + 'static,
279{
280    fn prepare_projection(cfg: &C, sampled_value: &C::Element) -> impl Fn(&Self) -> C::Element {
281        prepare_projection::<C, Self, _, DEGREE_PLUS_ONE>(cfg, sampled_value, |poly, i| {
282            *poly.0.coeffs[i].inner()
283        })
284    }
285}
286
287// This could've been more generic, but keeping implementation consistent with
288// `BinaryU64Poly`.
289impl<const DEGREE_PLUS_ONE: usize> MulByScalar<i64, DensePolynomial<i64, DEGREE_PLUS_ONE>>
290    for BinaryRefPoly<DEGREE_PLUS_ONE>
291{
292    fn mul_by_scalar<const CHECK: bool>(
293        self,
294        rhs: &i64,
295    ) -> Option<DensePolynomial<i64, DEGREE_PLUS_ONE>> {
296        let mut coeffs: [i64; DEGREE_PLUS_ONE] = [0_i64; DEGREE_PLUS_ONE];
297
298        coeffs.iter_mut().enumerate().for_each(|(i, out)| {
299            if *self.0.coeffs[i].inner() {
300                *out = *rhs;
301            }
302        });
303
304        Some(DensePolynomial { coeffs })
305    }
306}
307
308#[cfg(test)]
309mod tests {
310    use super::*;
311
312    #[test]
313    fn evaluate_is_correct() {
314        for i in 0..16 {
315            let poly = BinaryRefPoly::<4>::new_padded([
316                (i & 0b0001 != 0).into(),
317                (i & 0b0010 != 0).into(),
318                (i & 0b0100 != 0).into(),
319                (i & 0b1000 != 0).into(),
320            ]);
321
322            let result = poly.evaluate_at_point(&2).unwrap();
323
324            assert_eq!(result, i);
325        }
326    }
327
328    #[test]
329    fn transcribable() {
330        let original =
331            BinaryRefPoly::<4>::new_padded([true.into(), false.into(), true.into(), false.into()]);
332        let mut bytes = [0u8; BinaryRefPoly::<4>::NUM_BYTES];
333        assert_eq!(bytes.len(), u64::NUM_BYTES);
334
335        original.write_transcription_bytes_exact(&mut bytes);
336        let deserialized = BinaryRefPoly::<4>::read_transcription_bytes_exact(&bytes);
337        assert_eq!(original, deserialized);
338    }
339}
zinc_poly/univariate/binary_ref.rs

zinc_poly/univariate/
binary_ref.rs
