w3f-pcs 0.0.7

Collection of tools for augmenting polynomial commitment schemes
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

use ark_ec::{AdditiveGroup, AffineRepr, CurveGroup};
use ark_ff::{BigInteger, PrimeField, Zero};
use ark_std::vec::Vec;

pub fn naive_multiexp_affine<G: AffineRepr>(coeffs: &[G::ScalarField], bases: &[G]) -> G::Group {
    bases
        .iter()
        .zip(coeffs.iter())
        .map(|(b, &c)| b.mul(c))
        .sum()
}

/// Performs a small multi-exponentiation operation.
/// Uses the double-and-add algorithm with doublings shared across points.
// adopted from https://github.com/zcash/halo2/pull/20
pub fn small_multiexp_affine<G: AffineRepr>(coeffs: &[G::ScalarField], bases: &[G]) -> G::Group {
    let bytes_in_repr = <G::ScalarField as PrimeField>::BigInt::NUM_LIMBS * 8;
    let coeffs: Vec<_> = coeffs
        .iter()
        .map(|c| c.into_bigint().to_bytes_le())
        .collect();

    let mut acc = G::Group::zero();

    // for byte idx
    for byte_idx in (0..bytes_in_repr).rev() {
        // for bit idx
        for bit_idx in (0..8).rev() {
            acc.double_in_place();
            // for each coeff
            for coeff_idx in 0..coeffs.len() {
                let byte = coeffs[coeff_idx][byte_idx];
                if ((byte >> bit_idx) & 1) != 0 {
                    acc += &bases[coeff_idx];
                }
            }
        }
    }

    acc
}

pub fn small_multiexp_proj<G: CurveGroup>(coeffs: &[G::ScalarField], bases: &[G]) -> G {
    let bases = G::normalize_batch(bases);
    small_multiexp_affine(coeffs, &bases)
}

pub fn _small_multiexp_proj_2<G: CurveGroup>(coeffs: &[G::ScalarField], bases: &[G]) -> G {
    let bytes_in_repr = <G::ScalarField as PrimeField>::BigInt::NUM_LIMBS * 8;
    let coeffs: Vec<_> = coeffs
        .iter()
        .map(|c| c.into_bigint().to_bytes_le())
        .collect();

    let mut acc = G::zero();

    // for byte idx
    for byte_idx in (0..bytes_in_repr).rev() {
        // for bit idx
        for bit_idx in (0..8).rev() {
            acc.double_in_place();
            // for each coeff
            for coeff_idx in 0..coeffs.len() {
                let byte = coeffs[coeff_idx][byte_idx];
                if ((byte >> bit_idx) & 1) != 0 {
                    acc += bases[coeff_idx];
                }
            }
        }
    }

    acc
}