零知识证明 - 深入理解powersoftau

powersoftau，采用MPC以及随机Beacon，完成可信设置。通过POK算法实现可验证的密钥对，并建立和上一个参与方计算结果的绑定。参与可信设置的人数可扩展，并且参与方只需要按照顺序一个个的进行指定的计算即可。协调方在接收到某个参与方的计算后，验证后，发送给下一个参与方。

学习区块链技术的小伙伴不知道有没有同样的体验，每天脑袋都在膨胀，每天都有很多新鲜的知识需要学习总结。最近有些空闲时间看了看 powersoftau。了解零知识证明算法的小伙伴的都知道，在利用某些零知识证明算法之前，需要可信设置。Groth16 算法针对不同的电路需要单独的可信设置，生成 CRS。PLONK 算法是 Univeral 的零知识证明算法，针对不同的电路，在电路规模不超过一定范围的情况下，只需要一次可信设置。如何让多个参与方安全地进行可信设置，生成零知识证明的可信参数，就是 powersoftau 解决的事情。

powersoftau，采用 MPC 以及随机 Beacon，完成可信设置。

目前开源的 powersoftau 采用的是 2017 发表的论文：

Scalable Multi-party Computation for zk-SNARK Parameters in the Random Beacon Model

参与方/协调方

整个可信设置由参与方（player）以及协调方（coordinator）组成。协调方将前一个参与方生成的数据发送给下一个参与方。在所有参与方计算完成后，协调方再通过公开随机 Beacon 参与计算生成最后的参数。

协调方，并不需要可信第三方，因为协调方通过公开随机 Beacon 生成的参数是可以验证的。所谓的公开随机 Beacon，是在某个时间点之前并不知道的随机性数据，并且在同一个时间点后，所有人都可以验证随机数据。

Phase1/Pahse2

论文的第二章给出了整个协议的大体思路。假设 Alice 和 Bob 是两个参与方，整个协议逻辑上分成两步：Phase1 和 Phase2。

Phase1 计算出某个多项式项的 tau 对应的值。Phase2 计算出整个多项式对应的值。注意这些值都是有限域上的点。简单的说，Phase1 提供单个项的 MPC 的计算结果，Phase2 提供多项组合的 MPC 的计算结果。Phase1 和 Phase2 计算流程类似，参与方一个个的接着做。整个协议涉及两个基本计算：CONSISTENT 和 POK。

CONSISTENT

CONSISTENT 用来检查两个配对函数的结果是否相等。

检查 A，B，C 是否满足 e(A,B) = e(C1,C2)，记为：consistent(A-B; C)。

POK

POK - proof of knowledge。

参数 alpha 是知识（knowledge）。为了证明知道知识 alpha，先计算出 r（alpha 对应的 G1 上的点和公共字符串 v），并生成 G2 上的点。通过提供 alpha 在 G1 上的点以及 alpha*r，可以证明知道知识 alpha。证明可以通过配对函数进行验证。

论文的第四章给出了整个协议的定义。电路被抽象成两个结构：一个结构是计算过程只有乘除的电路部分，一个结构是组合部分。

对一个电路，证明的计算过程如下：

1(a) - 对电路中的每个输入，进行 POK 的证明。注意 v 是上一层的结果计算生成。

1(b) - 在上一参与者计算结果的基础上，计算当前参与者的计算结果。其中 M 是电路的多项式函数。

2 - 应用随机 Beacon

相对于计算过程，验证过程也比较清晰：

验证 POK 证明，验证 M 的计算是否正确。

论文的第 6/7 章，详细给出了 Groth16 算法参数的生成过程。感兴趣的小伙伴，可以自行查看。

源代码分析

powersoftau 在 GitHub 上有多个项目，大同小异。以 matter labs 的代码为例，分析一下代码逻辑。

https://github.com/matter-labs/powersoftau

这个项目实现 Groth16 算法的可信设置，支持 BN256 以及 BLS12_381 曲线。特别注意的是，这个项目只实现了 Phase1，组合的部分（Phase2）这个项目并不涉及。

accumulator.rs 和 batched_accumulator.rs 顾名思义，累加器，多个参与者的计算结果的“累加”。bin 目录下实现多个程序，实现计算（包括随机 Beacon 的应用计算），验证计算等等。parameters.rs 是参数配置。bn256/small_bn256/bls12_381 是对应曲线的参数配置。keypair.rs 实现了公钥和私钥的管理。utils.rs 实现了一些辅助函数。先从 keypair 说起。

keypair

keypair 实现 PublicKey 和 PrivateKey 密钥对。私钥比较直接，包括 tau，alpha 以及 beta：

pub struct PrivateKey {
 pub tau: E::Fr,
 pub alpha: E::Fr,
 pub beta: E::Fr
}

私钥是随机生成的。公钥相对复杂一些：

pub struct PublicKey {
 pub tau_g1: (E::G1Affine, E::G1Affine),
 pub alpha_g1: (E::G1Affine, E::G1Affine),
 pub beta_g1: (E::G1Affine, E::G1Affine),
 pub tau_g2: E::G2Affine,
 pub alpha_g2: E::G2Affine,
 pub beta_g2: E::G2Affine
}

针对 tau，alpha 以及 beta，生成 G1/G2 对应的点。三者的计算方式一致。详细看一下 tau 对应的公钥的生成过程：

 let mut op = |x: E::Fr, personalization: u8| {
        // Sample random g^s
        let g1_s = E::G1::rand(rng).into_affine();
        // Compute g^{s*x}
        let g1_s_x = g1_s.mul(x).into_affine();
        // Compute BLAKE2b(personalization | transcript | g^s | g^{s*x})
        let h: generic_array::GenericArray<u8, U64> = {
            let mut h = Blake2b::default();
            h.input(&[personalization]);
            h.input(digest);
            h.input(g1_s.into_uncompressed().as_ref());
            h.input(g1_s_x.into_uncompressed().as_ref());
            h.result()
        };
        // Hash into G2 as g^{s'}
        let g2_s: E::G2Affine = hash_to_g2::<E>(h.as_ref()).into_affine();
        // Compute g^{s'*x}
        let g2_s_x = g2_s.mul(x).into_affine();

        ((g1_s, g1_s_x), g2_s_x)
    };

g1_s 是在 G1 随机生成的点，g1_s_x 是 x* g1_s。g2_s 的生成依赖一个 digest 信息和 g1_s 的点。也就是说，在知道 g1_s 和 g1_s_x 的点以及 digest 信息的情况下，所有人都可以推算出来。g2_s_x 是 x* g_s。

其中 digest 信息是前一个参与者计算结果的 hash，具体计算在 bin 代码解释时详细描述。因为在知道 g1_s，g1_s_x 和 digest 的情况下，g2_s 可以推算出来。所以，公钥信息只要这三个点就足够：((g1_s, g1_s_x), g2_s_x)。

accumulator

Accumulator 负责将多个参与方生成的“参数”信息“累加”起来。所有的参数信息都清晰的描述在注释中：

pub struct Accumulator<E: Engine, P: PowersOfTauParameters> {
    /// tau^0, tau^1, tau^2, ..., tau^{TAU_POWERS_G1_LENGTH - 1}
    pub tau_powers_g1: Vec<E::G1Affine>,
    /// tau^0, tau^1, tau^2, ..., tau^{TAU_POWERS_LENGTH - 1}
    pub tau_powers_g2: Vec<E::G2Affine>,
    /// alpha * tau^0, alpha * tau^1, alpha * tau^2, ..., alpha * tau^{TAU_POWERS_LENGTH - 1}
    pub alpha_tau_powers_g1: Vec<E::G1Affine>,
    /// beta * tau^0, beta * tau^1, beta * tau^2, ..., beta * tau^{TAU_POWERS_LENGTH - 1}
    pub beta_tau_powers_g1: Vec<E::G1Affine>,
    /// beta
    pub beta_g2: E::G2Affine,
    /// Keep parameters here
    pub parameters: P
}

注意 tau 在 G1 和 G2 上的点的个数不一样，分别是 TAU_POWERS_G1_LENGTH 和 TAU_POWERS_LENGTH。这两个宏的计算方式定义在 parameters.rs 中：

const TAU_POWERS_LENGTH: usize = (1 << Self::REQUIRED_POWER)
const TAU_POWERS_G1_LENGTH: usize = (Self::TAU_POWERS_LENGTH << 1) - 1;

Accumulator 主要提供了两个函数 transform 和 verify_transform 函数。transform 函数在现有 Accumulator 的基础上叠加目前的 PrivateKey 的计算。

pub fn transform(&mut self, key: &PrivateKey<E>)
{
 ...
       batch_exp::<E, _>(&mut self.tau_powers_g1, &taupowers[0..], None);
        batch_exp::<E, _>(&mut self.tau_powers_g2, &taupowers[0..P::TAU_POWERS_LENGTH], None);
        batch_exp::<E, _>(&mut self.alpha_tau_powers_g1, &taupowers[0..P::TAU_POWERS_LENGTH], Some(&key.alpha));
        batch_exp::<E, _>(&mut self.beta_tau_powers_g1, &taupowers[0..P::TAU_POWERS_LENGTH], Some(&key.beta));
        self.beta_g2 = self.beta_g2.mul(key.beta).into_affine();
  ...
}

其中 taupowers 是 tau^0, tau^1...tau^(TAU_POWERS_G1_LENGTH)的计算结果。

verify_transform 验证 transform 的计算是否正确。验证需要提供需要验证的计算之前的 Accmulator 和之后的 Accumlator，公钥信息以及 digest 信息。以 tau 的计算为例，解释相关逻辑：

pub fn verify_transform<E: Engine, P: PowersOfTauParameters>(before: &Accumulator<E, P>, after: &Accumulator<E, P>, key: &PublicKey<E>, digest: &[u8]) -> bool

在计算出 g2_s 的基础上（包括 g1_s，g1_s_x 和 digest 信息），首先验证公钥信息是否正确：

if !same_ratio(key.tau_g1, (tau_g2_s, key.tau_g2)) {

验证公钥信息，就是 POK 的验证过程。

接着检查 tau^0 是否为 1：

// Check the correctness of the generators for tau powers
if after.tau_powers_g1[0] != E::G1Affine::one() {
    return false;
}
if after.tau_powers_g2[0] != E::G2Affine::one() {
    return false;
}

验证 tau 的计算是否正确：

if !same_ratio((before.tau_powers_g1[1], after.tau_powers_g1[1]), (tau_g2_s, key.tau_g2)) {

验证 tau 的其他幂次对应的点计算是否正确：

if !same_ratio(power_pairs(&after.tau_powers_g1), (after.tau_powers_g2[0], after.tau_powers_g2[1])) {
   return false;
}
if !same_ratio(power_pairs(&after.tau_powers_g2), (after.tau_powers_g1[0], after.tau_powers_g1[1])) {
   return false;
}

power_pairs 是有个有意思的设计。为了验证所有的幂次对应的点计算是否正确，power_pairs 将所有的幂次对应的点乘以单独的随机数，并错位累加。一次验证就能保证多个点是幂次递增关系。

bin 实现整个可信设置的协议，包括四种操作：1/new(创建初始的 Accumulator) 2/ compute (贡献一次参数计算) 3/ verify (验证一次参加计算) 4/ beacon（贡献随机 beacon 的参数计算）。

重点梳理一下 compute 和 verify 的逻辑，其他逻辑类似。逻辑分别实现在 compute_constrainted.rs 和 verify_transform_constrainted.rs。

compute 接受 challenge 文件，生成 response 文件。verify 接受 challenge 文件，上一次的 response 文件，生成 new_challenge。

前一个 challenge 的 hash 值是作为下一个参与方生成密钥对的 digest。某一个参与方生成的参数以及公钥信息会作为 response，也是下一个参与方的 challenge。因为上一个 challenge 的 hash 用于验证下一次的公钥的验证，从而确定了参与方的顺序。

整个协议的流程如下：

new -> compute -> (verify) compute ... -> (verify) compute -> (verify) beacon

总结：

powersoftau，采用 MPC 以及随机 Beacon，完成可信设置。通过 POK 算法实现可验证的密钥对，并建立和上一个参与方计算结果的绑定。参与可信设置的人数可扩展，并且参与方只需要按照顺序一个个的进行指定的计算即可。协调方在接收到某个参与方的计算后，验证后，发送给下一个参与方。

• 发表于 5天前
• 阅读 ( 66 )
• 学分 ( 3 )
• 分类：零知识证明