Polynomial commitment scheme based on IPA

[cliraa]

trafficstars

Polynomial commitment scheme based on IPA

Description

A folder was created within 'commitments' where everything related to the new polynomial commitment scheme is located.

Type of change

• [x] New feature

Checklist

• [x] Linked to Github Issue

[unbalancedparentheses]

@diegokingston have you checked this?

[MauroToscano]

This is not ready for merging, I'm moving it to a draft

[cliraa]

Hello! I just updated the files. Among the changes made, we can find:

• [x] The change in the name from 'identity_point' to 'neutral_element'.

• [x] Use of Fiat-Shamir for challenges construction.

• [x] Removal of some imported libraries.

• [x] Proper naming according to Rust practices.

• [x] SRS (Structured Reference String) was added for the creation of some values.

• [x] And more tests were added (using 2 elliptic curves, BLS12381 and BN254).

This is a Polynomial Commitment Scheme described in the Halo paper.

Usage examples can be found in the tests 'test_inner_product_argument_proof_bn254_curve' and 'test_inner_product_argument_proof_bls12381_curve' in the ipa.rs file.

Here is an example:

// Initial values.

// M: will be a constant used to establish the amount of limbs later on.
// gen: the generator used.
// d: the number of terms that the polynomial has.

// With this we create the variable 'ipa'.

const M: usize = 4;
let gen = BN254Curve::generator();
let d = 8;
let mut ipa = IPA::new(d, gen.clone());

//Polynomial to use.
let a = Polynomial::new(&[
    FE_2::from(1 as u64),
    FE_2::from(2 as u64),
    FE_2::from(3 as u64),
    FE_2::from(4 as u64),
    FE_2::from(5 as u64),
    FE_2::from(6 as u64),
    FE_2::from(7 as u64),
    FE_2::from(8 as u64),
]);

// Its coefficients.
let coef_a = a.clone().coefficients;

// Blinding factor used in the commitment:
let r = generate_random_element();

// The commitment is calculated as follows:
// P = 〈a, G〉 + [r]H
// where H is a point on the elliptic curve
// and G is a vector of points on the elliptic curve. These values are calculated in the SRS.
let _p = ipa
    .commit(&a, r.clone(), neutral_element_bn254_curve())
    .unwrap();

// Generation of challenges (_u and u) using Fiat-Shamir.

// - In the case of _u:

// Initially, we generate a vector (Vec<u8>) using randomness.
// Then, this vector is used together with the generator to create a point on an elliptic curve using 'build_group_challenge'.

// - And regarding u:

// We generate another vector (Vec<u8>) using randomness, 
// which is used in 'build_field_challenge' to create a Field Element.

let mut rng = rand::thread_rng();
let vector: Vec<u8> = (0..32).map(|_| rng.gen::<u8>()).collect();
let _u = build_group_challenge::<Fr_2, M, BN254Curve>(vector, gen);

// Calculation of k.
let k = (f64::from(ipa.d as u32).log2()) as usize;

let mut u: Vec<FE_2> = vec![FE_2::zero(); k];
for j in 0..k {
    let mut rng = rand::thread_rng();
    let vector: Vec<u8> = (0..32).map(|_| rng.gen::<u8>()).collect();
    u[j] = build_field_challenge(vector);
}

// x will be used to construct vector b.
let x = FE_2::from(3 as u64);
let b = powers_of(&x.clone(), ipa.d.try_into().unwrap());

// Calculation of v using inner product.
let v = inner_product_field(&coef_a, &b).unwrap();

// Open the challenges.
let proof = ipa
    .open(&coef_a, &b, &u, &_u, neutral_element_bn254_curve())
    .unwrap();

// Verification.
let verif = ipa
    .verify_open(
        &x,
        &v,
        &_p,
        &proof,
        &r,
        &u,
        &_u,
        neutral_element_bn254_curve(),
    )
    .unwrap();
assert!(verif);

I believe the README.md would look quite nice by including a usage example as described above. The README.md is not included yet, but if there is no problem, I can create it soon.

[codecov-commenter]

Codecov Report

All modified and coverable lines are covered by tests :white_check_mark:

Comparison is base (601ab67) 94.55% compared to head (c8856c6) 94.53%.

Additional details and impacted files

@@            Coverage Diff             @@
##             main     #743      +/-   ##
==========================================
- Coverage   94.55%   94.53%   -0.03%     
==========================================
  Files         154      154              
  Lines       34587    34587              
==========================================
- Hits        32705    32696       -9     
- Misses       1882     1891       +9     

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

[diegokingston]

We are not going to add IPA at the moment, so I will be closing this. If it gets back in the roadmap, we'll reopen