arkworks-rs/algebra

In version 0.3, `multi_scalar_mul` output is incorrect if scalar exceeds curve order.

guidovranken opened this issue · 1 comments

Summary of Bug

If VariableBaseMSM::multi_scalar_mul is called with a scalar that exceeds the curve order, the output will not be correct. The scalar is not or incorrectly reduced. Compare to regular point mul which handles this correctly.

Version

0.3.0

Steps to Reproduce

use ark_ff::PrimeField;
use ark_ff::biginteger::BigInteger256;
use ark_ff::biginteger::BigInteger384;
use ark_ec::msm::VariableBaseMSM;
use ark_ec::AffineCurve;
use ark_ec::ProjectiveCurve;
fn main() {                                                                                                
    let s: [u64; 4] = [ 
        0x025607A7919D793F,
        0xBDF7228F3A3DBD99,
        0x68D0564B14693662,
        0xAF6DD88BB87CB4AC];
    let point = ark_bls12_381::G1Affine::prime_subgroup_generator();
    let scalar = BigInteger256::new(s);
    assert!(
        point.mul(scalar).into_affine() ==
        VariableBaseMSM::multi_scalar_mul(&[point], &[scalar]).into_affine());
}

In v0.4, the reduction happens in PrimeField::into_bigint at https://github.com/arkworks-rs/algebra/blob/master/ec/src/scalar_mul/variable_base/mod.rs#L22 PrimeField::BigInt behaves this way, which maybe important somewhere.