use super::super::NonIdentityEccPoint;
use super::{X, Y, Z};
use crate::utilities::bool_check;
use halo2_proofs::{
circuit::{Region, Value},
plonk::{
Advice, Column, ConstraintSystem, Constraints, Error, Expression, Selector, VirtualCells,
},
poly::Rotation,
};
use pasta_curves::{arithmetic::FieldExt, pallas};
#[derive(Copy, Clone, Debug, Eq, PartialEq)]
pub(crate) struct DoubleAndAdd {
pub(crate) x_a: Column<Advice>,
pub(crate) x_p: Column<Advice>,
pub(crate) lambda_1: Column<Advice>,
pub(crate) lambda_2: Column<Advice>,
}
impl DoubleAndAdd {
pub(crate) fn x_r(
&self,
meta: &mut VirtualCells<pallas::Base>,
rotation: Rotation,
) -> Expression<pallas::Base> {
let x_a = meta.query_advice(self.x_a, rotation);
let x_p = meta.query_advice(self.x_p, rotation);
let lambda_1 = meta.query_advice(self.lambda_1, rotation);
lambda_1.square() - x_a - x_p
}
#[allow(non_snake_case)]
pub(crate) fn Y_A(
&self,
meta: &mut VirtualCells<pallas::Base>,
rotation: Rotation,
) -> Expression<pallas::Base> {
let x_a = meta.query_advice(self.x_a, rotation);
let lambda_1 = meta.query_advice(self.lambda_1, rotation);
let lambda_2 = meta.query_advice(self.lambda_2, rotation);
(lambda_1 + lambda_2) * (x_a - self.x_r(meta, rotation))
}
}
#[derive(Copy, Clone, Debug, Eq, PartialEq)]
pub(crate) struct Config<const NUM_BITS: usize> {
pub(super) q_mul_1: Selector,
pub(super) q_mul_2: Selector,
pub(super) q_mul_3: Selector,
pub(super) z: Column<Advice>,
pub(super) double_and_add: DoubleAndAdd,
pub(super) y_p: Column<Advice>,
}
impl<const NUM_BITS: usize> Config<NUM_BITS> {
pub(super) fn configure(
meta: &mut ConstraintSystem<pallas::Base>,
z: Column<Advice>,
x_a: Column<Advice>,
x_p: Column<Advice>,
y_p: Column<Advice>,
lambda_1: Column<Advice>,
lambda_2: Column<Advice>,
) -> Self {
meta.enable_equality(z);
meta.enable_equality(lambda_1);
let config = Self {
q_mul_1: meta.selector(),
q_mul_2: meta.selector(),
q_mul_3: meta.selector(),
z,
double_and_add: DoubleAndAdd {
x_a,
x_p,
lambda_1,
lambda_2,
},
y_p,
};
config.create_gate(meta);
config
}
fn create_gate(&self, meta: &mut ConstraintSystem<pallas::Base>) {
let x_r = |meta: &mut VirtualCells<pallas::Base>, rotation: Rotation| {
self.double_and_add.x_r(meta, rotation)
};
let y_a = |meta: &mut VirtualCells<pallas::Base>, rotation: Rotation| {
self.double_and_add.Y_A(meta, rotation) * pallas::Base::TWO_INV
};
let for_loop = |meta: &mut VirtualCells<pallas::Base>,
y_a_next: Expression<pallas::Base>| {
let one = Expression::Constant(pallas::Base::one());
let z_cur = meta.query_advice(self.z, Rotation::cur());
let z_prev = meta.query_advice(self.z, Rotation::prev());
let x_a_cur = meta.query_advice(self.double_and_add.x_a, Rotation::cur());
let x_a_next = meta.query_advice(self.double_and_add.x_a, Rotation::next());
let x_p_cur = meta.query_advice(self.double_and_add.x_p, Rotation::cur());
let y_p_cur = meta.query_advice(self.y_p, Rotation::cur());
let lambda1_cur = meta.query_advice(self.double_and_add.lambda_1, Rotation::cur());
let lambda2_cur = meta.query_advice(self.double_and_add.lambda_2, Rotation::cur());
let y_a_cur = y_a(meta, Rotation::cur());
let k = z_cur - z_prev * pallas::Base::from(2);
let bool_check = bool_check(k.clone());
let gradient_1 = lambda1_cur * (x_a_cur.clone() - x_p_cur) - y_a_cur.clone()
+ (k * pallas::Base::from(2) - one) * y_p_cur;
let secant_line = lambda2_cur.clone().square()
- x_a_next.clone()
- x_r(meta, Rotation::cur())
- x_a_cur.clone();
let gradient_2 = lambda2_cur * (x_a_cur - x_a_next) - y_a_cur - y_a_next;
std::iter::empty()
.chain(Some(("bool_check", bool_check)))
.chain(Some(("gradient_1", gradient_1)))
.chain(Some(("secant_line", secant_line)))
.chain(Some(("gradient_2", gradient_2)))
};
meta.create_gate("q_mul_1 == 1 checks", |meta| {
let q_mul_1 = meta.query_selector(self.q_mul_1);
let y_a_next = y_a(meta, Rotation::next());
let y_a_witnessed = meta.query_advice(self.double_and_add.lambda_1, Rotation::cur());
Constraints::with_selector(q_mul_1, Some(("init y_a", y_a_witnessed - y_a_next)))
});
meta.create_gate("q_mul_2 == 1 checks", |meta| {
let q_mul_2 = meta.query_selector(self.q_mul_2);
let y_a_next = y_a(meta, Rotation::next());
let x_p_cur = meta.query_advice(self.double_and_add.x_p, Rotation::cur());
let x_p_next = meta.query_advice(self.double_and_add.x_p, Rotation::next());
let y_p_cur = meta.query_advice(self.y_p, Rotation::cur());
let y_p_next = meta.query_advice(self.y_p, Rotation::next());
let x_p_check = x_p_cur - x_p_next;
let y_p_check = y_p_cur - y_p_next;
Constraints::with_selector(
q_mul_2,
std::iter::empty()
.chain(Some(("x_p_check", x_p_check)))
.chain(Some(("y_p_check", y_p_check)))
.chain(for_loop(meta, y_a_next)),
)
});
meta.create_gate("q_mul_3 == 1 checks", |meta| {
let q_mul_3 = meta.query_selector(self.q_mul_3);
let y_a_final = meta.query_advice(self.double_and_add.lambda_1, Rotation::next());
Constraints::with_selector(q_mul_3, for_loop(meta, y_a_final))
});
}
#[allow(clippy::type_complexity)]
pub(super) fn double_and_add(
&self,
region: &mut Region<'_, pallas::Base>,
offset: usize,
base: &NonIdentityEccPoint,
bits: &[Value<bool>],
acc: (X<pallas::Base>, Y<pallas::Base>, Z<pallas::Base>),
) -> Result<(X<pallas::Base>, Y<pallas::Base>, Vec<Z<pallas::Base>>), Error> {
assert_eq!(bits.len(), NUM_BITS);
let (x_p, y_p) = (base.x.value().cloned(), base.y.value().cloned());
let (x_a, y_a) = (acc.0.value().cloned(), acc.1.value().cloned());
x_a.zip(y_a)
.zip(x_p.zip(y_p))
.error_if_known_and(|((x_a, y_a), (x_p, y_p))| {
(x_p.is_zero_vartime() && y_p.is_zero_vartime())
|| (x_a.is_zero_vartime() && y_a.is_zero_vartime())
|| (x_p == x_a)
})?;
{
self.q_mul_1.enable(region, offset)?;
let offset = offset + 1;
for idx in 0..(NUM_BITS - 1) {
self.q_mul_2.enable(region, offset + idx)?;
}
self.q_mul_3.enable(region, offset + NUM_BITS - 1)?;
}
let (mut x_a, mut y_a, mut z) = {
let z = acc.2.copy_advice(|| "starting z", region, self.z, offset)?;
let x_a = acc.0.copy_advice(
|| "starting x_a",
region,
self.double_and_add.x_a,
offset + 1,
)?;
let y_a = acc.1.copy_advice(
|| "starting y_a",
region,
self.double_and_add.lambda_1,
offset,
)?;
(x_a, y_a.value().cloned(), z)
};
let offset = offset + 1;
let mut zs: Vec<Z<pallas::Base>> = Vec::with_capacity(bits.len());
for (row, k) in bits.iter().enumerate() {
let z_val = z
.value()
.zip(k.as_ref())
.map(|(z_val, k)| pallas::Base::from(2) * z_val + pallas::Base::from(*k as u64));
z = region.assign_advice(|| "z", self.z, row + offset, || z_val)?;
zs.push(Z(z.clone()));
region.assign_advice(|| "x_p", self.double_and_add.x_p, row + offset, || x_p)?;
region.assign_advice(|| "y_p", self.y_p, row + offset, || y_p)?;
let y_p = y_p
.zip(k.as_ref())
.map(|(y_p, k)| if !k { -y_p } else { y_p });
let lambda1 = y_a
.zip(y_p)
.zip(x_a.value())
.zip(x_p)
.map(|(((y_a, y_p), x_a), x_p)| (y_a - y_p) * (x_a - x_p).invert());
region.assign_advice(
|| "lambda1",
self.double_and_add.lambda_1,
row + offset,
|| lambda1,
)?;
let x_r = lambda1
.zip(x_a.value())
.zip(x_p)
.map(|((lambda1, x_a), x_p)| lambda1.square() - x_a - x_p);
let lambda2 =
lambda1
.zip(y_a)
.zip(x_a.value())
.zip(x_r)
.map(|(((lambda1, y_a), x_a), x_r)| {
y_a * pallas::Base::from(2) * (x_a - x_r).invert() - lambda1
});
region.assign_advice(
|| "lambda2",
self.double_and_add.lambda_2,
row + offset,
|| lambda2,
)?;
let x_a_new = lambda2.square() - x_a.value() - x_r;
y_a = lambda2 * (x_a.value() - x_a_new) - y_a;
let x_a_val = x_a_new;
x_a = region.assign_advice(
|| "x_a",
self.double_and_add.x_a,
row + offset + 1,
|| x_a_val,
)?;
}
let y_a = region.assign_advice(
|| "y_a",
self.double_and_add.lambda_1,
offset + NUM_BITS,
|| y_a,
)?;
Ok((X(x_a), Y(y_a), zs))
}
}