algebra
algebra copied to clipboard
In version 0.3, `multi_scalar_mul` output is incorrect if scalar exceeds curve order.
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.