Pointproofs 学习笔记3——代码解析

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语言封装。