barretenberg
Loading...
Searching...
No Matches
scalar_multiplication.hpp
1#pragma once
2
3#include "./runtime_states.hpp"
4#include "barretenberg/ecc/curves/bn254/bn254.hpp"
5#include "barretenberg/ecc/curves/grumpkin/grumpkin.hpp"
6#include <cstddef>
7#include <cstdint>
8
9namespace barretenberg::scalar_multiplication {
10
11constexpr size_t get_num_buckets(const size_t num_points)
12{
13 const size_t bits_per_bucket = get_optimal_bucket_width(num_points / 2);
14 return 1UL << bits_per_bucket;
15}
16
83template <typename Curve> struct multiplication_thread_state {
84 typename Curve::Element* buckets;
85 const uint64_t* point_schedule;
86};
87
88template <typename Curve>
89void compute_wnaf_states(uint64_t* point_schedule,
90 bool* input_skew_table,
91 uint64_t* round_counts,
92 const typename Curve::ScalarField* scalars,
93 size_t num_initial_points);
94
95template <typename Curve>
96void generate_pippenger_point_table(typename Curve::AffineElement* points,
97 typename Curve::AffineElement* table,
98 size_t num_points);
99
100void organize_buckets(uint64_t* point_schedule, size_t num_points);
101
102inline void count_bits(const uint32_t* bucket_counts,
103 uint32_t* bit_offsets,
104 const uint32_t num_buckets,
105 const size_t num_bits)
106{
107 for (size_t i = 0; i < num_buckets; ++i) {
108 const uint32_t count = bucket_counts[i];
109 for (uint32_t j = 0; j < num_bits; ++j) {
110 bit_offsets[j + 1] += (count & (1U << j));
111 }
112 }
113 bit_offsets[0] = 0;
114 for (size_t i = 2; i < num_bits + 1; ++i) {
115 bit_offsets[i] += bit_offsets[i - 1];
116 }
117}
118
119template <typename Curve>
120uint32_t construct_addition_chains(affine_product_runtime_state<Curve>& state, bool empty_bucket_counts = true);
121
122template <typename Curve>
123void add_affine_points(typename Curve::AffineElement* points,
124 size_t num_points,
125 typename Curve::BaseField* scratch_space);
126
127template <typename Curve>
128void add_affine_points_with_edge_cases(typename Curve::AffineElement* points,
129 size_t num_points,
130 typename Curve::BaseField* scratch_space);
131
132template <typename Curve>
133void evaluate_addition_chains(affine_product_runtime_state<Curve>& state,
134 size_t max_bucket_bits,
135 bool handle_edge_cases);
136template <typename Curve>
137typename Curve::Element pippenger_internal(typename Curve::AffineElement* points,
138 typename Curve::ScalarField* scalars,
139 size_t num_initial_points,
140 pippenger_runtime_state<Curve>& state,
141 bool handle_edge_cases);
142
143template <typename Curve>
144typename Curve::Element evaluate_pippenger_rounds(pippenger_runtime_state<Curve>& state,
145 typename Curve::AffineElement* points,
146 size_t num_points,
147 bool handle_edge_cases = false);
148
149template <typename Curve>
150typename Curve::AffineElement* reduce_buckets(affine_product_runtime_state<Curve>& state,
151 bool first_round = true,
152 bool handle_edge_cases = false);
153
154template <typename Curve>
155typename Curve::Element pippenger(typename Curve::ScalarField* scalars,
156 typename Curve::AffineElement* points,
157 size_t num_initial_points,
158 pippenger_runtime_state<Curve>& state,
159 bool handle_edge_cases = true);
160
161template <typename Curve>
162typename Curve::Element pippenger_unsafe(typename Curve::ScalarField* scalars,
163 typename Curve::AffineElement* points,
164 size_t num_initial_points,
165 pippenger_runtime_state<Curve>& state);
166
167template <typename Curve>
168typename Curve::Element pippenger_without_endomorphism_basis_points(typename Curve::ScalarField* scalars,
169 typename Curve::AffineElement* points,
170 size_t num_initial_points,
171 pippenger_runtime_state<Curve>& state);
172
173// Explicit instantiation
174// BN254
175
176extern template void generate_pippenger_point_table<curve::BN254>(curve::BN254::AffineElement* points,
177 curve::BN254::AffineElement* table,
178 size_t num_points);
179
180extern template uint32_t construct_addition_chains<curve::BN254>(affine_product_runtime_state<curve::BN254>& state,
181 bool empty_bucket_counts = true);
182
183extern template void add_affine_points<curve::BN254>(curve::BN254::AffineElement* points,
184 const size_t num_points,
185 curve::BN254::BaseField* scratch_space);
186
187extern template void add_affine_points_with_edge_cases<curve::BN254>(curve::BN254::AffineElement* points,
188 const size_t num_points,
189 curve::BN254::BaseField* scratch_space);
190
191extern template void evaluate_addition_chains<curve::BN254>(affine_product_runtime_state<curve::BN254>& state,
192 const size_t max_bucket_bits,
193 bool handle_edge_cases);
194extern template curve::BN254::Element pippenger_internal<curve::BN254>(curve::BN254::AffineElement* points,
195 curve::BN254::ScalarField* scalars,
196 const size_t num_initial_points,
197 pippenger_runtime_state<curve::BN254>& state,
198 bool handle_edge_cases);
199
200extern template curve::BN254::Element evaluate_pippenger_rounds<curve::BN254>(
201 pippenger_runtime_state<curve::BN254>& state,
202 curve::BN254::AffineElement* points,
203 const size_t num_points,
204 bool handle_edge_cases = false);
205
206extern template curve::BN254::AffineElement* reduce_buckets<curve::BN254>(
207 affine_product_runtime_state<curve::BN254>& state, bool first_round = true, bool handle_edge_cases = false);
208
209extern template curve::BN254::Element pippenger<curve::BN254>(curve::BN254::ScalarField* scalars,
210 curve::BN254::AffineElement* points,
211 const size_t num_points,
212 pippenger_runtime_state<curve::BN254>& state,
213 bool handle_edge_cases = true);
214
215extern template curve::BN254::Element pippenger_unsafe<curve::BN254>(curve::BN254::ScalarField* scalars,
216 curve::BN254::AffineElement* points,
217 const size_t num_initial_points,
218 pippenger_runtime_state<curve::BN254>& state);
219
220extern template curve::BN254::Element pippenger_without_endomorphism_basis_points<curve::BN254>(
221 curve::BN254::ScalarField* scalars,
222 curve::BN254::AffineElement* points,
223 const size_t num_initial_points,
224 pippenger_runtime_state<curve::BN254>& state);
225
226// Grumpkin
227
228extern template void generate_pippenger_point_table<curve::Grumpkin>(curve::Grumpkin::AffineElement* points,
229 curve::Grumpkin::AffineElement* table,
230 size_t num_points);
231
232extern template uint32_t construct_addition_chains<curve::Grumpkin>(
233 affine_product_runtime_state<curve::Grumpkin>& state, bool empty_bucket_counts = true);
234
235extern template void add_affine_points<curve::Grumpkin>(curve::Grumpkin::AffineElement* points,
236 const size_t num_points,
237 curve::Grumpkin::BaseField* scratch_space);
238
239extern template void add_affine_points_with_edge_cases<curve::Grumpkin>(curve::Grumpkin::AffineElement* points,
240 const size_t num_points,
241 curve::Grumpkin::BaseField* scratch_space);
242
243extern template void evaluate_addition_chains<curve::Grumpkin>(affine_product_runtime_state<curve::Grumpkin>& state,
244 const size_t max_bucket_bits,
245 bool handle_edge_cases);
246extern template curve::Grumpkin::Element pippenger_internal<curve::Grumpkin>(
247 curve::Grumpkin::AffineElement* points,
248 curve::Grumpkin::ScalarField* scalars,
249 const size_t num_initial_points,
250 pippenger_runtime_state<curve::Grumpkin>& state,
251 bool handle_edge_cases);
252
253extern template curve::Grumpkin::Element evaluate_pippenger_rounds<curve::Grumpkin>(
254 pippenger_runtime_state<curve::Grumpkin>& state,
255 curve::Grumpkin::AffineElement* points,
256 const size_t num_points,
257 bool handle_edge_cases = false);
258
259extern template curve::Grumpkin::AffineElement* reduce_buckets<curve::Grumpkin>(
260 affine_product_runtime_state<curve::Grumpkin>& state, bool first_round = true, bool handle_edge_cases = false);
261
262extern template curve::Grumpkin::Element pippenger<curve::Grumpkin>(curve::Grumpkin::ScalarField* scalars,
263 curve::Grumpkin::AffineElement* points,
264 const size_t num_points,
265 pippenger_runtime_state<curve::Grumpkin>& state,
266 bool handle_edge_cases = true);
267
268extern template curve::Grumpkin::Element pippenger_unsafe<curve::Grumpkin>(
269 curve::Grumpkin::ScalarField* scalars,
270 curve::Grumpkin::AffineElement* points,
271 const size_t num_initial_points,
272 pippenger_runtime_state<curve::Grumpkin>& state);
273
274extern template curve::Grumpkin::Element pippenger_without_endomorphism_basis_points<curve::Grumpkin>(
275 curve::Grumpkin::ScalarField* scalars,
276 curve::Grumpkin::AffineElement* points,
277 const size_t num_initial_points,
278 pippenger_runtime_state<curve::Grumpkin>& state);
279
280} // namespace barretenberg::scalar_multiplication
barretenberg::scalar_multiplication::multiplication_thread_state
Definition: scalar_multiplication.hpp:83
Generated by doxygen 1.9.6