ark_ec/scalar_mul/variable_base/
stream_pippenger.rs

1//! A space-efficient implementation of Pippenger's algorithm.
2use ark_ff::{PrimeField, Zero};
3
4use ark_std::{borrow::Borrow, vec::*};
5use hashbrown::HashMap;
6
7use super::{DefaultHasher, VariableBaseMSM};
8
9/// Struct for the chunked Pippenger algorithm.
10pub struct ChunkedPippenger<G: VariableBaseMSM> {
11    scalars_buffer: Vec<<G::ScalarField as PrimeField>::BigInt>,
12    bases_buffer: Vec<G::MulBase>,
13    result: G,
14    buf_size: usize,
15}
16
17impl<G: VariableBaseMSM> ChunkedPippenger<G> {
18    /// Initialize a chunked Pippenger instance with default parameters.
19    pub fn new(max_msm_buffer: usize) -> Self {
20        Self {
21            scalars_buffer: Vec::with_capacity(max_msm_buffer),
22            bases_buffer: Vec::with_capacity(max_msm_buffer),
23            result: G::zero(),
24            buf_size: max_msm_buffer,
25        }
26    }
27
28    /// Initialize a chunked Pippenger instance with the given buffer size.
29    pub fn with_size(buf_size: usize) -> Self {
30        Self {
31            scalars_buffer: Vec::with_capacity(buf_size),
32            bases_buffer: Vec::with_capacity(buf_size),
33            result: G::zero(),
34            buf_size,
35        }
36    }
37
38    /// Add a new (base, scalar) pair into the instance.
39    #[inline(always)]
40    pub fn add<B, S>(&mut self, base: B, scalar: S)
41    where
42        B: Borrow<G::MulBase>,
43        S: Borrow<<G::ScalarField as PrimeField>::BigInt>,
44    {
45        self.scalars_buffer.push(*scalar.borrow());
46        self.bases_buffer.push(*base.borrow());
47        if self.scalars_buffer.len() == self.buf_size {
48            self.result.add_assign(G::msm_bigint(
49                self.bases_buffer.as_slice(),
50                self.scalars_buffer.as_slice(),
51            ));
52            self.scalars_buffer.clear();
53            self.bases_buffer.clear();
54        }
55    }
56
57    /// Output the final Pippenger algorithm result.
58    #[inline(always)]
59    pub fn finalize(mut self) -> G {
60        if !self.scalars_buffer.is_empty() {
61            self.result +=
62                G::msm_bigint(self.bases_buffer.as_slice(), self.scalars_buffer.as_slice());
63        }
64        self.result
65    }
66}
67
68/// Hash map struct for Pippenger algorithm.
69pub struct HashMapPippenger<G: VariableBaseMSM> {
70    buffer: HashMap<G::MulBase, G::ScalarField, core::hash::BuildHasherDefault<DefaultHasher>>,
71    result: G,
72    buf_size: usize,
73}
74
75impl<G: VariableBaseMSM> HashMapPippenger<G> {
76    /// Produce a new hash map with the maximum msm buffer size.
77    pub fn new(max_msm_buffer: usize) -> Self {
78        Self {
79            buffer: HashMap::with_capacity_and_hasher(
80                max_msm_buffer,
81                core::hash::BuildHasherDefault::<DefaultHasher>::default(),
82            ),
83            result: G::zero(),
84            buf_size: max_msm_buffer,
85        }
86    }
87
88    /// Add a new (base, scalar) pair into the hash map.
89    #[inline(always)]
90    pub fn add<B, S>(&mut self, base: B, scalar: S)
91    where
92        B: Borrow<G::MulBase>,
93        S: Borrow<G::ScalarField>,
94    {
95        // update the entry, guarding the possibility that it has been already set.
96        let entry = self
97            .buffer
98            .entry(*base.borrow())
99            .or_insert(G::ScalarField::zero());
100        *entry += *scalar.borrow();
101        if self.buffer.len() == self.buf_size {
102            let bases = self.buffer.keys().cloned().collect::<Vec<_>>();
103            let scalars = self
104                .buffer
105                .values()
106                .map(|s| s.into_bigint())
107                .collect::<Vec<_>>();
108            self.result += G::msm_bigint(&bases, &scalars);
109            self.buffer.clear();
110        }
111    }
112
113    /// Update the final result with (base, scalar) pairs in the hash map.
114    #[inline(always)]
115    pub fn finalize(mut self) -> G {
116        if !self.buffer.is_empty() {
117            let bases = self.buffer.keys().cloned().collect::<Vec<_>>();
118            let scalars = self
119                .buffer
120                .values()
121                .map(|s| s.into_bigint())
122                .collect::<Vec<_>>();
123
124            self.result += G::msm_bigint(&bases, &scalars);
125        }
126        self.result
127    }
128}
ark_ec/scalar_mul/variable_base/stream_pippenger.rs

ark_ec/scalar_mul/variable_base/
stream_pippenger.rs
