1. 引言

之前的系列博客有：

• 1）Pointproofs: Aggregating Proofs for Multiple Vector Commitments 学习笔记1中，主要对 Algorand团队Gorbunov等人2020年论文《Pointproofs: Aggregating Proofs for Multiple Vector Commitments》做了一个总体的梳理。
• 2）Pointproofs: Aggregating Proofs for Multiple Vector Commitments 学习笔记2中主要对该论文中的算法进行了相应的论证。

本博客，主要针对该论文算法的实现（基于bls12-381 curve），https://github.com/algorand/pointproofs，进行相应的梳理。

2. github.com/algorand/pointproofs 代码总体结构

• Cargo.toml：Cargo配置文件。

• benches：benchmark文件夹。
  - basic.rs：提供basic benchmarks，数据记录在benchmark.md文件。
  - bench_aggregation.rs：bench the cost for cross commitments aggregation和batch verification。
  - bench_mul.rs：bench the cost of sum of product vs doing it serialized。
  - extra.rs：extra benchmarks using parameters with pre-computation。
  - old_data.md：在MacOS 3.1GHz Intel Core i5的测试数据，最新的测试数据见benchmark.md。
  - benchmark_extra.md：AWS Intel® Xeon® CPU E5-2686 v4 @ 2.30 GHz服务器，分别对 n = 1024 n=1024 n=1024， n = 32768 n=32768 n=32768，以及proof in G1，proof in G2进行了bench。同时指出，new commitment和new proof的主要开销在sum of n product，对有无precompute进行了性能对比，当 n < 1024 n Result

  基本的思路为：当aggregate的commitment数为1时（即 ∣ l ∣ = 1 |l|=1 ∣l∣=1时），设置 t j ’ = 1 t_j’=1 tj​’=1。
  Input: a list of k commitments
  Input: a list of k * x indices, for which we need to generate t_j
  Input: Value: a list of k * x messages that is committed to
  Output: a list of k field elements
  Error: ciphersuite id not supported
  Error: lengths do no match
  Steps:
  a.tmp = {C | S | m[S]} for i \in [0 .. commit.len-1]
  b.digest = SHA512(tmp)
  c.for 0 Result

  总体的思路为：当aggregate后open的总位置数为1（即 ∣ S ∣ = 1 |S|=1 ∣S∣=1）时，设置 t i = 1 t_i=1 ti​=1或 t j , i = 1 t_{j,i}=1 tj,i​=1。
  Input: the commitment
  Input: a list of indices, for which we need to generate t_i
  Input: Value: the messages that is committed to
  Output: a list of field elements
  Error: ciphersuite id not supported
  Error: lengths do no match
  Steps:
  a.digest = SHA512(C | S | m[S])
  b.for 0 bool { VALID_CIPHERSUITE.contains(&csid) }

  • paramgen_from_seed：根据seed和csid生成public parameters——Prove key和Verify key。（该函数仅在测试环境下调用。实际生产部署时，应使用单独的https://github.com/algorand/pointproofs-paramgen crate 来生成Prove key和Verify key，以保证public parameters的安全性。）
    1）要求seed长度不低于32，否则报错ERR_SEED_TOO_SHORT。
    2）会check_ciphersuite，否则报错ERR_CIPHERSUITE。
    3） 0 < n < = 65536 0 (i + 27)) & 32; byte |= ((scalars[j][2] >> i) > (i + 29)) & 8; byte |= ((scalars[j][1] >> i) > (i + 31)) & 2; byte |= (scalars[j][0] >> i) & 1; res.add_assign_mixed(&pre[(j Result

    Input: a Commitment
    Input: a writable buffer
    Input: a flag whether to compress the group point or not; must be true
    Output: none
    Error: compression is false
    Error: ciphersuite is not supported
    Error: serialization fails
    Steps: convert | ciphersuite | commit | to bytes

    fn deserialize(reader: &mut R, compressed: bool) -> Result
    

    Input: a readeble buffer
    Input: a flag whether the group elements are expected to be compressed or not; must be true
    Output: a Commitment
    Error: compression is false
    Error: ciphersuite is not supported
    Error: encoded buffer has a different compressness than specified
    Error: deserialization fails
    Steps: convert bytes to | ciphersuite | commit |

    3.8 pointproofs_groups.rs

    主要定义了部分类型的重命名。

    3.9 prove.rs

    • new：生成单个位置index的proof。

    /// generate a new proof
    pub fn new(
        prover_params: &ProverParams,
        values: &[Blob],
        index: usize,
    ) -> Result
    

    Input: a ProverParams
    Input: a list of values to commit
    Input: the index for which the proof is generated
    Output: a new proof
    Error: ciphersuite is not supported
    Error: index out of range
    Error: values.length does not match n
    Steps:
    a.hash the values into scarlars
    b.proof = \prod prover_params.generators[n - index + i]^scalar[i] for i in range(n) except index (in implementation we implement it as for i in range(n) without exception, since the corresponding generator was already set to 0)

    • verify：验证单个位置的proof。

    /// Verify the proof
    pub fn verify(
        &self,
        verifier_params: &VerifierParams,
        com: &Commitment,
        value: Blob,
        index: usize,
    ) -> bool
    

    Input: self, the proof to be verified
    Input: a VerifierParams
    Input: the commitment
    Input: the value that proof is generated
    Input: index of the value in the value vector
    Output: if the proof is valid w.r.t. commit/values/index or not
    Steps:
    a.Compute t = hash_to_field_pointproofs(value)
    b.return e(com^{1/t}, veririer_params.generators[n-index-1]) * e(proof^{-1/t}, generator_of_g2) == gt_elt

    • update：更新单个位置的proof。

    /// For updating your proof when someone else's value changes
    /// Not for updating your own proof when your value changes -- because then the proof does not change!
    pub fn update(
        &mut self,
        prover_params: &ProverParams,
        proof_index: usize,
        changed_index: usize,
        value_before: Blob,
        value_after: Blob,
    ) -> Result
    

    Input: self, the proof to be updated
    Input: a ProverParams
    Input: proof_index, the index for which the proof is generated
    Input: changed_index, the index for which the proof will be updated
    Output: mutate self to a new proof
    Error: ciphersuite is not supported
    Error: index out of range
    Note: This function is used for updating your proof when someone else’s value changes. It is not for updating your own proof when your value changes – because then the proof does not change!
    Steps:
    a.hash value_before into old_scalar
    b.hash value_after into new_scalar
    c.proof = proof * prover_params.generators[changed_index + n - proof_index]^(new_scalar-old_scalar)

    • batch_new：同时生成多个位置的proof，不再逐个生成。

    /// generate a list of new proofs
    pub fn batch_new(
        prover_params: &ProverParams,
        values: &[Blob],
        indices: &[usize],
    ) -> Result
    

    Input: a ProverParam
    Input: a list of values to commit
    Input: a list of indices for which the proofs are generated
    Output: a list of proofs, each corresponding to an index
    Error: ciphersuite is not supported
    Error: index out of range
    Error: values.length does not match n
    Error: indices.length = 0 or indices.length > n
    Steps:
    a.hash the values into scarlars
    b.for j in 0…indices.len():
    b.a.proof[j] = \prod prover_params[n - indices[j] + i]^scalar[i] for i in range(n) except index
    (in implementation we implement it as for i in range(n) without exception, since the corresponding generator was already set to 1)

    3.10 c_api.rs

    c_api.rs 中实现的是rust接口函数的C语言封装。