openvm_pairing_circuit/pairing_chip/
miller_double_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: AffinePoint<Fp2>: 4 field elements
22// Output: (AffinePoint<Fp2>, Fp2, Fp2) -> 8 field elements
23#[derive(Chip, ChipUsageGetter, InstructionExecutor)]
24pub struct MillerDoubleStepChip<
25    F: PrimeField32,
26    const INPUT_BLOCKS: usize,
27    const OUTPUT_BLOCKS: usize,
28    const BLOCK_SIZE: usize,
29>(
30    VmChipWrapper<
31        F,
32        Rv32VecHeapAdapterChip<F, 1, 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    > MillerDoubleStepChip<F, INPUT_BLOCKS, OUTPUT_BLOCKS, BLOCK_SIZE>
43{
44    pub fn new(
45        adapter: Rv32VecHeapAdapterChip<F, 1, 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_step_expr(config, range_checker.bus());
52        let core = FieldExpressionCoreChip::new(
53            expr,
54            offset,
55            vec![PairingOpcode::MILLER_DOUBLE_STEP as usize],
56            vec![],
57            range_checker,
58            "MillerDoubleStep",
59            false,
60        );
61        Self(VmChipWrapper::new(adapter, core, offline_memory))
62    }
63}
64
65// Ref: https://github.com/openvm-org/openvm/blob/f7d6fa7b8ef247e579740eb652fcdf5a04259c28/lib/ecc-execution/src/common/miller_step.rs#L7
66pub fn miller_double_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
77    let mut three_x_square = x_s.square().int_mul([3, 0]);
78    let mut lambda = three_x_square.div(&mut y_s.int_mul([2, 0]));
79    let mut x_2s = lambda.square().sub(&mut x_s.int_mul([2, 0]));
80    let mut y_2s = lambda.mul(&mut (x_s.sub(&mut x_2s))).sub(&mut y_s);
81    x_2s.save_output();
82    y_2s.save_output();
83
84    let mut b = lambda.neg();
85    let mut c = lambda.mul(&mut x_s).sub(&mut y_s);
86    b.save_output();
87    c.save_output();
88
89    let builder = builder.borrow().clone();
90    FieldExpr::new(builder, range_bus, false)
91}
92
93#[cfg(test)]
94mod tests {
95    use openvm_circuit::arch::testing::{VmChipTestBuilder, BITWISE_OP_LOOKUP_BUS};
96    use openvm_circuit_primitives::bitwise_op_lookup::{
97        BitwiseOperationLookupBus, SharedBitwiseOperationLookupChip,
98    };
99    use openvm_ecc_guest::AffinePoint;
100    use openvm_instructions::{riscv::RV32_CELL_BITS, LocalOpcode};
101    use openvm_mod_circuit_builder::test_utils::{
102        biguint_to_limbs, bls12381_fq_to_biguint, bn254_fq_to_biguint,
103    };
104    use openvm_pairing_guest::{
105        bls12_381::{BLS12_381_LIMB_BITS, BLS12_381_MODULUS, BLS12_381_NUM_LIMBS},
106        bn254::{BN254_LIMB_BITS, BN254_MODULUS, BN254_NUM_LIMBS},
107        halo2curves_shims::{bls12_381::Bls12_381, bn254::Bn254},
108        pairing::MillerStep,
109    };
110    use openvm_pairing_transpiler::PairingOpcode;
111    use openvm_rv32_adapters::{rv32_write_heap_default, Rv32VecHeapAdapterChip};
112    use openvm_stark_backend::p3_field::FieldAlgebra;
113    use openvm_stark_sdk::p3_baby_bear::BabyBear;
114    use rand::{rngs::StdRng, SeedableRng};
115
116    use super::*;
117
118    type F = BabyBear;
119
120    #[test]
121    #[allow(non_snake_case)]
122    fn test_miller_double_bn254() {
123        use halo2curves_axiom::bn256::G2Affine;
124        const NUM_LIMBS: usize = 32;
125        const LIMB_BITS: usize = 8;
126        const BLOCK_SIZE: usize = 32;
127
128        let mut tester: VmChipTestBuilder<F> = VmChipTestBuilder::default();
129        let config = ExprBuilderConfig {
130            modulus: BN254_MODULUS.clone(),
131            limb_bits: BN254_LIMB_BITS,
132            num_limbs: BN254_NUM_LIMBS,
133        };
134        let bitwise_bus = BitwiseOperationLookupBus::new(BITWISE_OP_LOOKUP_BUS);
135        let bitwise_chip = SharedBitwiseOperationLookupChip::<RV32_CELL_BITS>::new(bitwise_bus);
136        let adapter = Rv32VecHeapAdapterChip::<F, 1, 4, 8, BLOCK_SIZE, BLOCK_SIZE>::new(
137            tester.execution_bus(),
138            tester.program_bus(),
139            tester.memory_bridge(),
140            tester.address_bits(),
141            bitwise_chip.clone(),
142        );
143        let mut chip = MillerDoubleStepChip::new(
144            adapter,
145            config,
146            PairingOpcode::CLASS_OFFSET,
147            tester.range_checker(),
148            tester.offline_memory_mutex_arc(),
149        );
150
151        let mut rng0 = StdRng::seed_from_u64(2);
152        let Q = G2Affine::random(&mut rng0);
153        let inputs = [Q.x.c0, Q.x.c1, Q.y.c0, Q.y.c1].map(bn254_fq_to_biguint);
154
155        let Q_ecpoint = AffinePoint { x: Q.x, y: Q.y };
156        let (Q_acc_init, l_init) = Bn254::miller_double_step(&Q_ecpoint);
157        let result = chip
158            .0
159            .core
160            .expr()
161            .execute_with_output(inputs.to_vec(), vec![]);
162        assert_eq!(result.len(), 8); // AffinePoint<Fp2> and two Fp2 coefficients
163        assert_eq!(result[0], bn254_fq_to_biguint(Q_acc_init.x.c0));
164        assert_eq!(result[1], bn254_fq_to_biguint(Q_acc_init.x.c1));
165        assert_eq!(result[2], bn254_fq_to_biguint(Q_acc_init.y.c0));
166        assert_eq!(result[3], bn254_fq_to_biguint(Q_acc_init.y.c1));
167        assert_eq!(result[4], bn254_fq_to_biguint(l_init.b.c0));
168        assert_eq!(result[5], bn254_fq_to_biguint(l_init.b.c1));
169        assert_eq!(result[6], bn254_fq_to_biguint(l_init.c.c0));
170        assert_eq!(result[7], bn254_fq_to_biguint(l_init.c.c1));
171
172        let input_limbs = inputs
173            .map(|x| biguint_to_limbs::<NUM_LIMBS>(x, LIMB_BITS).map(BabyBear::from_canonical_u32));
174
175        let instruction = rv32_write_heap_default(
176            &mut tester,
177            input_limbs.to_vec(),
178            vec![],
179            chip.0.core.air.offset + PairingOpcode::MILLER_DOUBLE_STEP as usize,
180        );
181
182        tester.execute(&mut chip, &instruction);
183        let tester = tester.build().load(chip).load(bitwise_chip).finalize();
184        tester.simple_test().expect("Verification failed");
185    }
186
187    #[test]
188    #[allow(non_snake_case)]
189    fn test_miller_double_bls12_381() {
190        use halo2curves_axiom::bls12_381::G2Affine;
191        const NUM_LIMBS: usize = 48;
192        const LIMB_BITS: usize = 8;
193        const BLOCK_SIZE: usize = 16;
194
195        let mut tester: VmChipTestBuilder<F> = VmChipTestBuilder::default();
196        let config = ExprBuilderConfig {
197            modulus: BLS12_381_MODULUS.clone(),
198            limb_bits: BLS12_381_LIMB_BITS,
199            num_limbs: BLS12_381_NUM_LIMBS,
200        };
201        let bitwise_bus = BitwiseOperationLookupBus::new(BITWISE_OP_LOOKUP_BUS);
202        let bitwise_chip = SharedBitwiseOperationLookupChip::<RV32_CELL_BITS>::new(bitwise_bus);
203        let adapter = Rv32VecHeapAdapterChip::<F, 1, 12, 24, BLOCK_SIZE, BLOCK_SIZE>::new(
204            tester.execution_bus(),
205            tester.program_bus(),
206            tester.memory_bridge(),
207            tester.address_bits(),
208            bitwise_chip.clone(),
209        );
210        let mut chip = MillerDoubleStepChip::new(
211            adapter,
212            config,
213            PairingOpcode::CLASS_OFFSET,
214            tester.range_checker(),
215            tester.offline_memory_mutex_arc(),
216        );
217
218        let mut rng0 = StdRng::seed_from_u64(12);
219        let Q = G2Affine::random(&mut rng0);
220        let inputs = [Q.x.c0, Q.x.c1, Q.y.c0, Q.y.c1].map(bls12381_fq_to_biguint);
221
222        let Q_ecpoint = AffinePoint { x: Q.x, y: Q.y };
223        let (Q_acc_init, l_init) = Bls12_381::miller_double_step(&Q_ecpoint);
224        let result = chip
225            .0
226            .core
227            .expr()
228            .execute_with_output(inputs.to_vec(), vec![]);
229        assert_eq!(result.len(), 8); // AffinePoint<Fp2> and two Fp2 coefficients
230        assert_eq!(result[0], bls12381_fq_to_biguint(Q_acc_init.x.c0));
231        assert_eq!(result[1], bls12381_fq_to_biguint(Q_acc_init.x.c1));
232        assert_eq!(result[2], bls12381_fq_to_biguint(Q_acc_init.y.c0));
233        assert_eq!(result[3], bls12381_fq_to_biguint(Q_acc_init.y.c1));
234        assert_eq!(result[4], bls12381_fq_to_biguint(l_init.b.c0));
235        assert_eq!(result[5], bls12381_fq_to_biguint(l_init.b.c1));
236        assert_eq!(result[6], bls12381_fq_to_biguint(l_init.c.c0));
237        assert_eq!(result[7], bls12381_fq_to_biguint(l_init.c.c1));
238
239        let input_limbs = inputs
240            .map(|x| biguint_to_limbs::<NUM_LIMBS>(x, LIMB_BITS).map(BabyBear::from_canonical_u32));
241
242        let instruction = rv32_write_heap_default(
243            &mut tester,
244            input_limbs.to_vec(),
245            vec![],
246            chip.0.core.air.offset + PairingOpcode::MILLER_DOUBLE_STEP as usize,
247        );
248
249        tester.execute(&mut chip, &instruction);
250        let tester = tester.build().load(chip).load(bitwise_chip).finalize();
251        tester.simple_test().expect("Verification failed");
252    }
253}
openvm_pairing_circuit/pairing_chip/miller_double_step.rs

openvm_pairing_circuit/pairing_chip/
miller_double_step.rs
