1use crate::{
2 loader::{
3 halo2::shim::{EccInstructions, IntegerInstructions},
4 EcPointLoader, LoadedEcPoint, LoadedScalar, Loader, ScalarLoader,
5 },
6 util::{
7 arithmetic::{CurveAffine, Field, FieldOps},
8 Itertools,
9 },
10};
11use std::{
12 cell::{Ref, RefCell, RefMut},
13 fmt::{self, Debug},
14 marker::PhantomData,
15 ops::{Add, AddAssign, Deref, Mul, MulAssign, Neg, Sub, SubAssign},
16 rc::Rc,
17};
18
19#[derive(Debug)]
21pub struct Halo2Loader<C: CurveAffine, EccChip: EccInstructions<C>> {
22 ecc_chip: RefCell<EccChip>,
23 ctx: RefCell<EccChip::Context>,
24 num_scalar: RefCell<usize>,
25 num_ec_point: RefCell<usize>,
26 _marker: PhantomData<C>,
27 #[cfg(test)]
28 #[allow(dead_code)]
29 row_meterings: RefCell<Vec<(String, usize)>>,
30}
31
32impl<C: CurveAffine, EccChip: EccInstructions<C>> Halo2Loader<C, EccChip> {
33 pub fn new(ecc_chip: EccChip, ctx: EccChip::Context) -> Rc<Self> {
36 Rc::new(Self {
37 ecc_chip: RefCell::new(ecc_chip),
38 ctx: RefCell::new(ctx),
39 num_scalar: RefCell::default(),
40 num_ec_point: RefCell::default(),
41 #[cfg(test)]
42 row_meterings: RefCell::default(),
43 _marker: PhantomData,
44 })
45 }
46
47 pub fn into_ctx(self) -> EccChip::Context {
49 self.ctx.into_inner()
50 }
51
52 pub fn take_ctx(&self) -> EccChip::Context {
54 self.ctx.take()
55 }
56
57 pub fn ecc_chip(&self) -> Ref<EccChip> {
59 self.ecc_chip.borrow()
60 }
61
62 pub fn scalar_chip(&self) -> Ref<EccChip::ScalarChip> {
64 Ref::map(self.ecc_chip(), |ecc_chip| ecc_chip.scalar_chip())
65 }
66
67 pub fn ctx(&self) -> Ref<EccChip::Context> {
69 self.ctx.borrow()
70 }
71
72 pub fn ctx_mut(&self) -> RefMut<'_, EccChip::Context> {
74 self.ctx.borrow_mut()
75 }
76
77 fn assign_const_scalar(self: &Rc<Self>, constant: C::Scalar) -> EccChip::AssignedScalar {
78 self.scalar_chip().assign_constant(&mut self.ctx_mut(), constant)
79 }
80
81 pub fn assign_scalar(self: &Rc<Self>, scalar: C::Scalar) -> Scalar<C, EccChip> {
83 let assigned = self.scalar_chip().assign_integer(&mut self.ctx_mut(), scalar);
84 self.scalar_from_assigned(assigned)
85 }
86
87 pub fn scalar_from_assigned(
89 self: &Rc<Self>,
90 assigned: EccChip::AssignedScalar,
91 ) -> Scalar<C, EccChip> {
92 self.scalar(Value::Assigned(assigned))
93 }
94
95 fn scalar(
96 self: &Rc<Self>,
97 value: Value<C::Scalar, EccChip::AssignedScalar>,
98 ) -> Scalar<C, EccChip> {
99 let index = *self.num_scalar.borrow();
100 *self.num_scalar.borrow_mut() += 1;
101 Scalar { loader: self.clone(), index, value: value.into() }
102 }
103
104 fn assign_const_ec_point(self: &Rc<Self>, constant: C) -> EccChip::AssignedEcPoint {
105 self.ecc_chip().assign_constant(&mut self.ctx_mut(), constant)
106 }
107
108 pub fn assign_ec_point(self: &Rc<Self>, ec_point: C) -> EcPoint<C, EccChip> {
110 let assigned = self.ecc_chip().assign_point(&mut self.ctx_mut(), ec_point);
111 self.ec_point_from_assigned(assigned)
112 }
113
114 pub fn ec_point_from_assigned(
116 self: &Rc<Self>,
117 assigned: EccChip::AssignedEcPoint,
118 ) -> EcPoint<C, EccChip> {
119 self.ec_point(Value::Assigned(assigned))
120 }
121
122 fn ec_point(self: &Rc<Self>, value: Value<C, EccChip::AssignedEcPoint>) -> EcPoint<C, EccChip> {
123 let index = *self.num_ec_point.borrow();
124 *self.num_ec_point.borrow_mut() += 1;
125 EcPoint { loader: self.clone(), index, value: value.into() }
126 }
127
128 fn add(
129 self: &Rc<Self>,
130 lhs: &Scalar<C, EccChip>,
131 rhs: &Scalar<C, EccChip>,
132 ) -> Scalar<C, EccChip> {
133 let output = match (lhs.value().deref(), rhs.value().deref()) {
134 (Value::Constant(lhs), Value::Constant(rhs)) => Value::Constant(*lhs + rhs),
135 (Value::Assigned(assigned), Value::Constant(constant))
136 | (Value::Constant(constant), Value::Assigned(assigned)) => {
137 Value::Assigned(self.scalar_chip().sum_with_coeff_and_const(
138 &mut self.ctx_mut(),
139 &[(C::Scalar::ONE, assigned)],
140 *constant,
141 ))
142 }
143 (Value::Assigned(lhs), Value::Assigned(rhs)) => {
144 Value::Assigned(self.scalar_chip().sum_with_coeff_and_const(
145 &mut self.ctx_mut(),
146 &[(C::Scalar::ONE, lhs), (C::Scalar::ONE, rhs)],
147 C::Scalar::ZERO,
148 ))
149 }
150 };
151 self.scalar(output)
152 }
153
154 fn sub(
155 self: &Rc<Self>,
156 lhs: &Scalar<C, EccChip>,
157 rhs: &Scalar<C, EccChip>,
158 ) -> Scalar<C, EccChip> {
159 let output = match (lhs.value().deref(), rhs.value().deref()) {
160 (Value::Constant(lhs), Value::Constant(rhs)) => Value::Constant(*lhs - rhs),
161 (Value::Constant(constant), Value::Assigned(assigned)) => {
162 Value::Assigned(self.scalar_chip().sum_with_coeff_and_const(
163 &mut self.ctx_mut(),
164 &[(-C::Scalar::ONE, assigned)],
165 *constant,
166 ))
167 }
168 (Value::Assigned(assigned), Value::Constant(constant)) => {
169 Value::Assigned(self.scalar_chip().sum_with_coeff_and_const(
170 &mut self.ctx_mut(),
171 &[(C::Scalar::ONE, assigned)],
172 -*constant,
173 ))
174 }
175 (Value::Assigned(lhs), Value::Assigned(rhs)) => Value::Assigned(
176 IntegerInstructions::sub(self.scalar_chip().deref(), &mut self.ctx_mut(), lhs, rhs),
177 ),
178 };
179 self.scalar(output)
180 }
181
182 fn mul(
183 self: &Rc<Self>,
184 lhs: &Scalar<C, EccChip>,
185 rhs: &Scalar<C, EccChip>,
186 ) -> Scalar<C, EccChip> {
187 let output = match (lhs.value().deref(), rhs.value().deref()) {
188 (Value::Constant(lhs), Value::Constant(rhs)) => Value::Constant(*lhs * rhs),
189 (Value::Assigned(assigned), Value::Constant(constant))
190 | (Value::Constant(constant), Value::Assigned(assigned)) => {
191 Value::Assigned(self.scalar_chip().sum_with_coeff_and_const(
192 &mut self.ctx_mut(),
193 &[(*constant, assigned)],
194 C::Scalar::ZERO,
195 ))
196 }
197 (Value::Assigned(lhs), Value::Assigned(rhs)) => {
198 Value::Assigned(self.scalar_chip().sum_products_with_coeff_and_const(
199 &mut self.ctx_mut(),
200 &[(C::Scalar::ONE, lhs, rhs)],
201 C::Scalar::ZERO,
202 ))
203 }
204 };
205 self.scalar(output)
206 }
207
208 fn neg(self: &Rc<Self>, scalar: &Scalar<C, EccChip>) -> Scalar<C, EccChip> {
209 let output = match scalar.value().deref() {
210 Value::Constant(constant) => Value::Constant(constant.neg()),
211 Value::Assigned(assigned) => Value::Assigned(IntegerInstructions::neg(
212 self.scalar_chip().deref(),
213 &mut self.ctx_mut(),
214 assigned,
215 )),
216 };
217 self.scalar(output)
218 }
219
220 fn invert(self: &Rc<Self>, scalar: &Scalar<C, EccChip>) -> Scalar<C, EccChip> {
221 let output = match scalar.value().deref() {
222 Value::Constant(constant) => Value::Constant(Field::invert(constant).unwrap()),
223 Value::Assigned(assigned) => Value::Assigned(IntegerInstructions::invert(
224 self.scalar_chip().deref(),
225 &mut self.ctx_mut(),
226 assigned,
227 )),
228 };
229 self.scalar(output)
230 }
231}
232
233#[derive(Clone, Debug)]
234pub enum Value<T, L> {
235 Constant(T),
236 Assigned(L),
237}
238
239impl<T, L> Value<T, L> {
240 fn maybe_const(&self) -> Option<T>
241 where
242 T: Copy,
243 {
244 match self {
245 Value::Constant(constant) => Some(*constant),
246 _ => None,
247 }
248 }
249
250 fn assigned(&self) -> &L {
251 match self {
252 Value::Assigned(assigned) => assigned,
253 _ => unreachable!(),
254 }
255 }
256}
257
258#[derive(Clone)]
260pub struct Scalar<C: CurveAffine, EccChip: EccInstructions<C>> {
261 loader: Rc<Halo2Loader<C, EccChip>>,
262 index: usize,
263 value: RefCell<Value<C::Scalar, EccChip::AssignedScalar>>,
264}
265
266impl<C: CurveAffine, EccChip: EccInstructions<C>> Scalar<C, EccChip> {
267 pub fn loader(&self) -> &Rc<Halo2Loader<C, EccChip>> {
269 &self.loader
270 }
271
272 pub fn into_assigned(self) -> EccChip::AssignedScalar {
274 match self.value.into_inner() {
275 Value::Constant(constant) => self.loader.assign_const_scalar(constant),
276 Value::Assigned(assigned) => assigned,
277 }
278 }
279
280 pub fn assigned(&self) -> Ref<EccChip::AssignedScalar> {
282 if let Some(constant) = self.maybe_const() {
283 *self.value.borrow_mut() = Value::Assigned(self.loader.assign_const_scalar(constant))
284 }
285 Ref::map(self.value.borrow(), Value::assigned)
286 }
287
288 fn value(&self) -> Ref<Value<C::Scalar, EccChip::AssignedScalar>> {
289 self.value.borrow()
290 }
291
292 fn maybe_const(&self) -> Option<C::Scalar> {
293 self.value().deref().maybe_const()
294 }
295}
296
297impl<C: CurveAffine, EccChip: EccInstructions<C>> PartialEq for Scalar<C, EccChip> {
298 fn eq(&self, other: &Self) -> bool {
299 self.index == other.index
300 }
301}
302
303impl<C: CurveAffine, EccChip: EccInstructions<C>> LoadedScalar<C::Scalar> for Scalar<C, EccChip> {
304 type Loader = Rc<Halo2Loader<C, EccChip>>;
305
306 fn loader(&self) -> &Self::Loader {
307 &self.loader
308 }
309
310 fn pow_var(&self, exp: &Self, max_bits: usize) -> Self {
311 let loader = self.loader();
312 let base = self.clone().into_assigned();
313 let exp = exp.clone().into_assigned();
314 let res = loader.scalar_chip().pow_var(&mut loader.ctx_mut(), &base, &exp, max_bits);
315 loader.scalar_from_assigned(res)
316 }
317}
318
319impl<C: CurveAffine, EccChip: EccInstructions<C>> Debug for Scalar<C, EccChip> {
320 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
321 f.debug_struct("Scalar").field("value", &self.value).finish()
322 }
323}
324
325impl<C: CurveAffine, EccChip: EccInstructions<C>> FieldOps for Scalar<C, EccChip> {
326 fn invert(&self) -> Option<Self> {
327 Some(self.loader.invert(self))
328 }
329}
330
331impl<C: CurveAffine, EccChip: EccInstructions<C>> Add for Scalar<C, EccChip> {
332 type Output = Self;
333
334 fn add(self, rhs: Self) -> Self::Output {
335 Halo2Loader::add(&self.loader, &self, &rhs)
336 }
337}
338
339impl<C: CurveAffine, EccChip: EccInstructions<C>> Sub for Scalar<C, EccChip> {
340 type Output = Self;
341
342 fn sub(self, rhs: Self) -> Self::Output {
343 Halo2Loader::sub(&self.loader, &self, &rhs)
344 }
345}
346
347impl<C: CurveAffine, EccChip: EccInstructions<C>> Mul for Scalar<C, EccChip> {
348 type Output = Self;
349
350 fn mul(self, rhs: Self) -> Self::Output {
351 Halo2Loader::mul(&self.loader, &self, &rhs)
352 }
353}
354
355impl<C: CurveAffine, EccChip: EccInstructions<C>> Neg for Scalar<C, EccChip> {
356 type Output = Self;
357
358 fn neg(self) -> Self::Output {
359 Halo2Loader::neg(&self.loader, &self)
360 }
361}
362
363impl<'b, C: CurveAffine, EccChip: EccInstructions<C>> Add<&'b Self> for Scalar<C, EccChip> {
364 type Output = Self;
365
366 fn add(self, rhs: &'b Self) -> Self::Output {
367 Halo2Loader::add(&self.loader, &self, rhs)
368 }
369}
370
371impl<'b, C: CurveAffine, EccChip: EccInstructions<C>> Sub<&'b Self> for Scalar<C, EccChip> {
372 type Output = Self;
373
374 fn sub(self, rhs: &'b Self) -> Self::Output {
375 Halo2Loader::sub(&self.loader, &self, rhs)
376 }
377}
378
379impl<'b, C: CurveAffine, EccChip: EccInstructions<C>> Mul<&'b Self> for Scalar<C, EccChip> {
380 type Output = Self;
381
382 fn mul(self, rhs: &'b Self) -> Self::Output {
383 Halo2Loader::mul(&self.loader, &self, rhs)
384 }
385}
386
387impl<C: CurveAffine, EccChip: EccInstructions<C>> AddAssign for Scalar<C, EccChip> {
388 fn add_assign(&mut self, rhs: Self) {
389 *self = Halo2Loader::add(&self.loader, self, &rhs)
390 }
391}
392
393impl<C: CurveAffine, EccChip: EccInstructions<C>> SubAssign for Scalar<C, EccChip> {
394 fn sub_assign(&mut self, rhs: Self) {
395 *self = Halo2Loader::sub(&self.loader, self, &rhs)
396 }
397}
398
399impl<C: CurveAffine, EccChip: EccInstructions<C>> MulAssign for Scalar<C, EccChip> {
400 fn mul_assign(&mut self, rhs: Self) {
401 *self = Halo2Loader::mul(&self.loader, self, &rhs)
402 }
403}
404
405impl<'b, C: CurveAffine, EccChip: EccInstructions<C>> AddAssign<&'b Self> for Scalar<C, EccChip> {
406 fn add_assign(&mut self, rhs: &'b Self) {
407 *self = Halo2Loader::add(&self.loader, self, rhs)
408 }
409}
410
411impl<'b, C: CurveAffine, EccChip: EccInstructions<C>> SubAssign<&'b Self> for Scalar<C, EccChip> {
412 fn sub_assign(&mut self, rhs: &'b Self) {
413 *self = Halo2Loader::sub(&self.loader, self, rhs)
414 }
415}
416
417impl<'b, C: CurveAffine, EccChip: EccInstructions<C>> MulAssign<&'b Self> for Scalar<C, EccChip> {
418 fn mul_assign(&mut self, rhs: &'b Self) {
419 *self = Halo2Loader::mul(&self.loader, self, rhs)
420 }
421}
422
423#[derive(Clone)]
425pub struct EcPoint<C: CurveAffine, EccChip: EccInstructions<C>> {
426 loader: Rc<Halo2Loader<C, EccChip>>,
427 index: usize,
428 value: RefCell<Value<C, EccChip::AssignedEcPoint>>,
429}
430
431impl<C: CurveAffine, EccChip: EccInstructions<C>> EcPoint<C, EccChip> {
432 pub fn into_assigned(self) -> EccChip::AssignedEcPoint {
434 match self.value.into_inner() {
435 Value::Constant(constant) => self.loader.assign_const_ec_point(constant),
436 Value::Assigned(assigned) => assigned,
437 }
438 }
439
440 pub fn assigned(&self) -> Ref<EccChip::AssignedEcPoint> {
442 if let Some(constant) = self.maybe_const() {
443 *self.value.borrow_mut() = Value::Assigned(self.loader.assign_const_ec_point(constant))
444 }
445 Ref::map(self.value.borrow(), Value::assigned)
446 }
447
448 fn value(&self) -> Ref<Value<C, EccChip::AssignedEcPoint>> {
449 self.value.borrow()
450 }
451
452 fn maybe_const(&self) -> Option<C> {
453 self.value().deref().maybe_const()
454 }
455}
456
457impl<C: CurveAffine, EccChip: EccInstructions<C>> PartialEq for EcPoint<C, EccChip> {
458 fn eq(&self, other: &Self) -> bool {
459 self.index == other.index
460 }
461}
462
463impl<C: CurveAffine, EccChip: EccInstructions<C>> LoadedEcPoint<C> for EcPoint<C, EccChip> {
464 type Loader = Rc<Halo2Loader<C, EccChip>>;
465
466 fn loader(&self) -> &Self::Loader {
467 &self.loader
468 }
469}
470
471impl<C: CurveAffine, EccChip: EccInstructions<C>> Debug for EcPoint<C, EccChip> {
472 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
473 f.debug_struct("EcPoint").field("index", &self.index).field("value", &self.value).finish()
474 }
475}
476
477impl<C: CurveAffine, EccChip: EccInstructions<C>> ScalarLoader<C::Scalar>
478 for Rc<Halo2Loader<C, EccChip>>
479{
480 type LoadedScalar = Scalar<C, EccChip>;
481
482 fn load_const(&self, value: &C::Scalar) -> Scalar<C, EccChip> {
483 self.scalar(Value::Constant(*value))
484 }
485
486 fn assert_eq(&self, _annotation: &str, lhs: &Scalar<C, EccChip>, rhs: &Scalar<C, EccChip>) {
487 self.scalar_chip().assert_equal(&mut self.ctx_mut(), &lhs.assigned(), &rhs.assigned());
488 }
489
490 fn sum_with_coeff_and_const(
491 &self,
492 values: &[(C::Scalar, &Scalar<C, EccChip>)],
493 constant: C::Scalar,
494 ) -> Scalar<C, EccChip> {
495 let values = values.iter().map(|(coeff, value)| (*coeff, value.assigned())).collect_vec();
496 self.scalar(Value::Assigned(self.scalar_chip().sum_with_coeff_and_const(
497 &mut self.ctx_mut(),
498 &values,
499 constant,
500 )))
501 }
502
503 fn sum_products_with_coeff_and_const(
504 &self,
505 values: &[(C::Scalar, &Scalar<C, EccChip>, &Scalar<C, EccChip>)],
506 constant: C::Scalar,
507 ) -> Scalar<C, EccChip> {
508 let values = values
509 .iter()
510 .map(|(coeff, lhs, rhs)| (*coeff, lhs.assigned(), rhs.assigned()))
511 .collect_vec();
512 self.scalar(Value::Assigned(self.scalar_chip().sum_products_with_coeff_and_const(
513 &mut self.ctx_mut(),
514 &values,
515 constant,
516 )))
517 }
518}
519
520impl<C: CurveAffine, EccChip: EccInstructions<C>> EcPointLoader<C> for Rc<Halo2Loader<C, EccChip>> {
521 type LoadedEcPoint = EcPoint<C, EccChip>;
522
523 fn ec_point_load_const(&self, ec_point: &C) -> EcPoint<C, EccChip> {
524 self.ec_point(Value::Constant(*ec_point))
525 }
526
527 fn ec_point_assert_eq(
528 &self,
529 _annotation: &str,
530 lhs: &EcPoint<C, EccChip>,
531 rhs: &EcPoint<C, EccChip>,
532 ) {
533 if let (Value::Constant(lhs), Value::Constant(rhs)) =
534 (lhs.value().deref(), rhs.value().deref())
535 {
536 assert_eq!(lhs, rhs);
537 } else {
538 let lhs = lhs.assigned();
539 let rhs = rhs.assigned();
540 self.ecc_chip().assert_equal(&mut self.ctx_mut(), lhs.deref(), rhs.deref());
541 }
542 }
543
544 fn multi_scalar_multiplication(
545 pairs: &[(&<Self as ScalarLoader<C::Scalar>>::LoadedScalar, &EcPoint<C, EccChip>)],
546 ) -> EcPoint<C, EccChip> {
547 assert!(!pairs.is_empty(), "multi_scalar_multiplication: pairs is empty");
548 let loader = &pairs[0].0.loader;
549
550 let (constant, fixed_base, variable_base_non_scaled, variable_base_scaled) =
551 pairs.iter().cloned().fold(
552 (C::identity(), Vec::new(), Vec::new(), Vec::new()),
553 |(
554 mut constant,
555 mut fixed_base,
556 mut variable_base_non_scaled,
557 mut variable_base_scaled,
558 ),
559 (scalar, base)| {
560 match (scalar.value().deref(), base.value().deref()) {
561 (Value::Constant(scalar), Value::Constant(base)) => {
562 constant = (*base * scalar + constant).into()
563 }
564 (Value::Assigned(_), Value::Constant(base)) => {
565 fixed_base.push((scalar, *base))
566 }
567 (Value::Constant(scalar), Value::Assigned(_))
568 if scalar.eq(&C::Scalar::ONE) =>
569 {
570 variable_base_non_scaled.push(base);
571 }
572 _ => variable_base_scaled.push((scalar, base)),
573 };
574 (constant, fixed_base, variable_base_non_scaled, variable_base_scaled)
575 },
576 );
577
578 let fixed_base_msm = (!fixed_base.is_empty())
579 .then(|| {
580 let fixed_base = fixed_base
581 .into_iter()
582 .map(|(scalar, base)| (scalar.assigned(), base))
583 .collect_vec();
584 loader.ecc_chip.borrow_mut().fixed_base_msm(&mut loader.ctx_mut(), &fixed_base)
585 })
586 .map(RefCell::new);
587 let variable_base_msm = (!variable_base_scaled.is_empty())
588 .then(|| {
589 let variable_base_scaled = variable_base_scaled
590 .into_iter()
591 .map(|(scalar, base)| (scalar.assigned(), base.assigned()))
592 .collect_vec();
593 loader
594 .ecc_chip
595 .borrow_mut()
596 .variable_base_msm(&mut loader.ctx_mut(), &variable_base_scaled)
597 })
598 .map(RefCell::new);
599 let output = loader.ecc_chip().sum_with_const(
600 &mut loader.ctx_mut(),
601 &variable_base_non_scaled
602 .into_iter()
603 .map(EcPoint::assigned)
604 .chain(fixed_base_msm.as_ref().map(RefCell::borrow))
605 .chain(variable_base_msm.as_ref().map(RefCell::borrow))
606 .collect_vec(),
607 constant,
608 );
609
610 loader.ec_point_from_assigned(output)
611 }
612}
613
614impl<C: CurveAffine, EccChip: EccInstructions<C>> Loader<C> for Rc<Halo2Loader<C, EccChip>> {}