openvm_pairing_circuit/pairing_chip/
miller_double_and_add_step.rs

Help
1use std::{
2    cell::RefCell,
3    rc::Rc,
4    sync::{Arc, Mutex},
5};
6
7use openvm_algebra_circuit::Fp2;
8use openvm_circuit::{arch::VmChipWrapper, system::memory::OfflineMemory};
9use openvm_circuit_derive::InstructionExecutor;
10use openvm_circuit_primitives::var_range::{
11    SharedVariableRangeCheckerChip, VariableRangeCheckerBus,
12};
13use openvm_circuit_primitives_derive::{Chip, ChipUsageGetter};
14use openvm_mod_circuit_builder::{
15    ExprBuilder, ExprBuilderConfig, FieldExpr, FieldExpressionCoreChip,
16};
17use openvm_pairing_transpiler::PairingOpcode;
18use openvm_rv32_adapters::Rv32VecHeapAdapterChip;
19use openvm_stark_backend::p3_field::PrimeField32;
20
21// Input: two AffinePoint<Fp2>: 4 field elements each
22// Output: (AffinePoint<Fp2>, UnevaluatedLine<Fp2>, UnevaluatedLine<Fp2>) -> 2*2 + 2*2 + 2*2 = 12 field elements
23#[derive(Chip, ChipUsageGetter, InstructionExecutor)]
24pub struct MillerDoubleAndAddStepChip<
25    F: PrimeField32,
26    const INPUT_BLOCKS: usize,
27    const OUTPUT_BLOCKS: usize,
28    const BLOCK_SIZE: usize,
29>(
30    pub  VmChipWrapper<
31        F,
32        Rv32VecHeapAdapterChip<F, 2, INPUT_BLOCKS, OUTPUT_BLOCKS, BLOCK_SIZE, BLOCK_SIZE>,
33        FieldExpressionCoreChip,
34    >,
35);
36
37impl<
38        F: PrimeField32,
39        const INPUT_BLOCKS: usize,
40        const OUTPUT_BLOCKS: usize,
41        const BLOCK_SIZE: usize,
42    > MillerDoubleAndAddStepChip<F, INPUT_BLOCKS, OUTPUT_BLOCKS, BLOCK_SIZE>
43{
44    pub fn new(
45        adapter: Rv32VecHeapAdapterChip<F, 2, INPUT_BLOCKS, OUTPUT_BLOCKS, BLOCK_SIZE, BLOCK_SIZE>,
46        config: ExprBuilderConfig,
47        offset: usize,
48        range_checker: SharedVariableRangeCheckerChip,
49        offline_memory: Arc<Mutex<OfflineMemory<F>>>,
50    ) -> Self {
51        let expr = miller_double_and_add_step_expr(config, range_checker.bus());
52        let core = FieldExpressionCoreChip::new(
53            expr,
54            offset,
55            vec![PairingOpcode::MILLER_DOUBLE_AND_ADD_STEP as usize],
56            vec![],
57            range_checker,
58            "MillerDoubleAndAddStep",
59            false,
60        );
61        Self(VmChipWrapper::new(adapter, core, offline_memory))
62    }
63}
64
65// Ref: openvm_pairing_guest::miller_step
66pub fn miller_double_and_add_step_expr(
67    config: ExprBuilderConfig,
68    range_bus: VariableRangeCheckerBus,
69) -> FieldExpr {
70    config.check_valid();
71    let builder = ExprBuilder::new(config, range_bus.range_max_bits);
72    let builder = Rc::new(RefCell::new(builder));
73
74    let mut x_s = Fp2::new(builder.clone());
75    let mut y_s = Fp2::new(builder.clone());
76    let mut x_q = Fp2::new(builder.clone());
77    let mut y_q = Fp2::new(builder.clone());
78
79    // λ1 = (y_s - y_q) / (x_s - x_q)
80    let mut lambda1 = y_s.sub(&mut y_q).div(&mut x_s.sub(&mut x_q));
81    let mut x_sq = lambda1.square().sub(&mut x_s).sub(&mut x_q);
82    // λ2 = -λ1 - 2y_s / (x_{s+q} - x_s)
83    let mut lambda2 = lambda1
84        .neg()
85        .sub(&mut y_s.int_mul([2, 0]).div(&mut x_sq.sub(&mut x_s)));
86    let mut x_sqs = lambda2.square().sub(&mut x_s).sub(&mut x_sq);
87    let mut y_sqs = lambda2.mul(&mut (x_s.sub(&mut x_sqs))).sub(&mut y_s);
88
89    x_sqs.save_output();
90    y_sqs.save_output();
91
92    let mut b0 = lambda1.neg();
93    let mut c0 = lambda1.mul(&mut x_s).sub(&mut y_s);
94    b0.save_output();
95    c0.save_output();
96
97    let mut b1 = lambda2.neg();
98    let mut c1 = lambda2.mul(&mut x_s).sub(&mut y_s);
99    b1.save_output();
100    c1.save_output();
101
102    let builder = builder.borrow().clone();
103    FieldExpr::new(builder, range_bus, false)
104}
105
106#[cfg(test)]
107mod tests {
108    use halo2curves_axiom::bn256::G2Affine;
109    use openvm_circuit::arch::testing::{VmChipTestBuilder, BITWISE_OP_LOOKUP_BUS};
110    use openvm_circuit_primitives::bitwise_op_lookup::{
111        BitwiseOperationLookupBus, SharedBitwiseOperationLookupChip,
112    };
113    use openvm_ecc_guest::AffinePoint;
114    use openvm_instructions::{riscv::RV32_CELL_BITS, LocalOpcode};
115    use openvm_mod_circuit_builder::test_utils::{biguint_to_limbs, bn254_fq_to_biguint};
116    use openvm_pairing_guest::{
117        bn254::BN254_MODULUS, halo2curves_shims::bn254::Bn254, pairing::MillerStep,
118    };
119    use openvm_pairing_transpiler::PairingOpcode;
120    use openvm_rv32_adapters::{rv32_write_heap_default, Rv32VecHeapAdapterChip};
121    use openvm_stark_backend::p3_field::FieldAlgebra;
122    use openvm_stark_sdk::p3_baby_bear::BabyBear;
123    use rand::{rngs::StdRng, SeedableRng};
124
125    use super::*;
126
127    type F = BabyBear;
128    const NUM_LIMBS: usize = 32;
129    const LIMB_BITS: usize = 8;
130    const BLOCK_SIZE: usize = 32;
131
132    #[test]
133    #[allow(non_snake_case)]
134    fn test_miller_double_and_add() {
135        let mut tester: VmChipTestBuilder<F> = VmChipTestBuilder::default();
136        let bitwise_bus = BitwiseOperationLookupBus::new(BITWISE_OP_LOOKUP_BUS);
137        let bitwise_chip = SharedBitwiseOperationLookupChip::<RV32_CELL_BITS>::new(bitwise_bus);
138        let adapter = Rv32VecHeapAdapterChip::<F, 2, 4, 12, BLOCK_SIZE, BLOCK_SIZE>::new(
139            tester.execution_bus(),
140            tester.program_bus(),
141            tester.memory_bridge(),
142            tester.address_bits(),
143            bitwise_chip.clone(),
144        );
145        let mut chip = MillerDoubleAndAddStepChip::new(
146            adapter,
147            ExprBuilderConfig {
148                modulus: BN254_MODULUS.clone(),
149                limb_bits: LIMB_BITS,
150                num_limbs: NUM_LIMBS,
151            },
152            PairingOpcode::CLASS_OFFSET,
153            tester.range_checker(),
154            tester.offline_memory_mutex_arc(),
155        );
156
157        let mut rng0 = StdRng::seed_from_u64(2);
158        let Q = G2Affine::random(&mut rng0);
159        let Q2 = G2Affine::random(&mut rng0);
160        let inputs = [
161            Q.x.c0, Q.x.c1, Q.y.c0, Q.y.c1, Q2.x.c0, Q2.x.c1, Q2.y.c0, Q2.y.c1,
162        ]
163        .map(bn254_fq_to_biguint);
164
165        let Q_ecpoint = AffinePoint { x: Q.x, y: Q.y };
166        let Q_ecpoint2 = AffinePoint { x: Q2.x, y: Q2.y };
167        let (Q_daa, l_qa, l_sqs) = Bn254::miller_double_and_add_step(&Q_ecpoint, &Q_ecpoint2);
168        let result = chip
169            .0
170            .core
171            .expr()
172            .execute_with_output(inputs.to_vec(), vec![]);
173        assert_eq!(result.len(), 12); // AffinePoint<Fp2> and 4 Fp2 coefficients
174        assert_eq!(result[0], bn254_fq_to_biguint(Q_daa.x.c0));
175        assert_eq!(result[1], bn254_fq_to_biguint(Q_daa.x.c1));
176        assert_eq!(result[2], bn254_fq_to_biguint(Q_daa.y.c0));
177        assert_eq!(result[3], bn254_fq_to_biguint(Q_daa.y.c1));
178        assert_eq!(result[4], bn254_fq_to_biguint(l_qa.b.c0));
179        assert_eq!(result[5], bn254_fq_to_biguint(l_qa.b.c1));
180        assert_eq!(result[6], bn254_fq_to_biguint(l_qa.c.c0));
181        assert_eq!(result[7], bn254_fq_to_biguint(l_qa.c.c1));
182        assert_eq!(result[8], bn254_fq_to_biguint(l_sqs.b.c0));
183        assert_eq!(result[9], bn254_fq_to_biguint(l_sqs.b.c1));
184        assert_eq!(result[10], bn254_fq_to_biguint(l_sqs.c.c0));
185        assert_eq!(result[11], bn254_fq_to_biguint(l_sqs.c.c1));
186
187        let input1_limbs = inputs[0..4]
188            .iter()
189            .map(|x| {
190                biguint_to_limbs::<NUM_LIMBS>(x.clone(), LIMB_BITS)
191                    .map(BabyBear::from_canonical_u32)
192            })
193            .collect::<Vec<_>>();
194
195        let input2_limbs = inputs[4..8]
196            .iter()
197            .map(|x| {
198                biguint_to_limbs::<NUM_LIMBS>(x.clone(), LIMB_BITS)
199                    .map(BabyBear::from_canonical_u32)
200            })
201            .collect::<Vec<_>>();
202
203        let instruction = rv32_write_heap_default(
204            &mut tester,
205            input1_limbs,
206            input2_limbs,
207            chip.0.core.air.offset + PairingOpcode::MILLER_DOUBLE_AND_ADD_STEP as usize,
208        );
209
210        tester.execute(&mut chip, &instruction);
211        let tester = tester.build().load(chip).load(bitwise_chip).finalize();
212        tester.simple_test().expect("Verification failed");
213    }
214}
openvm_pairing_circuit/pairing_chip/miller_double_and_add_step.rs

openvm_pairing_circuit/pairing_chip/
miller_double_and_add_step.rs
