Halo源代码解析

1. compute_b()函数

cargo test test_compute_b -- --nocapture

test_compute_b测试函数基本流程如下： compute_b函数实际是计算的公式（假设 k = k= k=challenges.len()）： ( ( 1 C k − 1 + x C k − 1 ) ( 1 C k − 2 + x 2 C k − 2 ) ( 1 C k − 3 + x 4 C k − 3 ) ( 1 C k − 4 + x 8 C k − 4 ) . . . ( 1 C 0 + x 2 k C 0 ) ) ((\frac{1}{C_{k-1}}+xC_{k-1})(\frac{1}{C_{k-2}}+x^2C_{k-2})(\frac{1}{C_{k-3}}+x^4C_{k-3})(\frac{1}{C_{k-4}}+x^8C_{k-4})...(\frac{1}{C_{0}}+x^{2k}C_{0})) ((Ck−1​1​+xCk−1​)(Ck−2​1​+x2Ck−2​)(Ck−3​1​+x4Ck−3​)(Ck−4​1​+x8Ck−4​)...(C0​1​+x2kC0​))

pub fn compute_b(x: F, challenges: &[F], challenges_inv: &[F]) -> F {
    assert!(!challenges.is_empty());
    assert_eq!(challenges.len(), challenges_inv.len());
    if challenges.len() == 1 {
        return *challenges_inv.last().unwrap() + *challenges.last().unwrap() * x;
    } else {
        return (*challenges_inv.last().unwrap() + *challenges.last().unwrap() * x)
            * compute_b(
                x.square(),
                &challenges[0..(challenges.len() - 1)],
                &challenges_inv[0..(challenges.len() - 1)],
            );
    }
}

2. my_test_circuit()函数

cargo test my_test_circuit -- --nocapture

#[derive(Clone)]
pub struct Params {
    pub g: C, //为曲线C的one点。
    pub d: usize,
    pub n: usize,
    pub k: usize,
    pub generators: Vec, //为用于circuit的随机点序列。如用于commitment时的随机generator
    pub generators_xy: Vec,
}
	//随机从曲线C上选择2^k个point点。
	pub fn new(k: usize) -> Self {
        use crossbeam_utils::thread;

        assert!(k > 3);
        let d = 1  Self {
        let challenges_sq_packed = vec![F::from_u64(MAGIC); k];
        let challenges_sq_new: Vec = challenges_sq_packed
            .iter()
            .map(|v| get_challenge_scalar(*v))
            .collect();
        let challenges: Vec = challenges_sq_new
            .iter()
            .map(|v| v.sqrt().unwrap())
            .collect();
        let mut challenges_inv = challenges.clone();
        F::batch_invert(&mut challenges_inv);
        let b_one = compute_b(F::one(), &challenges, &challenges_inv);

        Deferred {
            x: F::one(),
            y_old: F::one(),
            y_cur: F::one(),
            y_new: F::one(),
            ky_opening: F::zero(),
            tx_positive_opening: F::zero(),
            tx_negative_opening: F::zero(),
            sx_cur_opening: F::zero(),
            rx_opening: F::zero(),
            rxy_opening: F::zero(),
            challenges_sq_packed_old: challenges_sq_packed.clone(),
            gx_old_opening: b_one,
            challenges_sq_packed_new: challenges_sq_packed.clone(),
            b_x: b_one,
            b_xy: b_one,
            b_y_old: b_one,
            b_y_cur: b_one,
            b_y_new: b_one,
        }
    }
    pub fn verify(&self, k: usize) -> bool {
        let (lhs, rhs) = self.compute(k);

        let correct_gx_old_opening = {
            let challenges_sq_old: Vec = self
                .challenges_sq_packed_old
                .iter()
                .map(|v| get_challenge_scalar(*v))
                .collect();

            let mut challenges = challenges_sq_old.clone();
            for a in &mut challenges {
                *a = a.sqrt().unwrap(); // TODO
            }

            let mut challenges_inv = challenges.clone();
            F::batch_invert(&mut challenges_inv);
            compute_b(self.x, &challenges, &challenges_inv)
        };

        // TODO: prover could have put a zero here
        let challenges_sq_new: Vec = self
            .challenges_sq_packed_new
            .iter()
            .map(|v| get_challenge_scalar(*v))
            .collect();

        let mut challenges = challenges_sq_new.clone();
        for a in &mut challenges {
            *a = a.sqrt().unwrap(); // TODO
        }
        let mut challenges_inv = challenges.clone();
        F::batch_invert(&mut challenges_inv);
        let b_x = compute_b(self.x, &challenges, &challenges_inv);
        let b_xy = compute_b(self.x * self.y_cur, &challenges, &challenges_inv);
        let b_y_old = compute_b(self.y_old, &challenges, &challenges_inv);
        let b_y_cur = compute_b(self.y_cur, &challenges, &challenges_inv);
        let b_y_new = compute_b(self.y_new, &challenges, &challenges_inv);

        lhs == rhs
            && correct_gx_old_opening == self.gx_old_opening
            && self.b_x == b_x
            && self.b_xy == b_xy
            && self.b_y_old == b_y_old
            && self.b_y_cur == b_y_cur
            && self.b_y_new == b_y_new
    }

get_challenge_scalar是将EC0和EC1两条曲线的点进行映射，根据博客Halo——zcash新的零知识证明机制，无需Trusted Setup2.1节可知，EC0和EC1的endomorphism特性： P*p_beta==E0(x*q_beta,y) Q*q_beta==E1(x_1*p_beta,y_1)

pub fn get_challenge_scalar(challenge: F1) -> F2 {
    let challenge = challenge.get_lower_128();

    let mut acc = F2::one();
    acc = acc + acc;
    acc = acc + F2::one();

    for i in 1..64 {
        let should_negate = (challenge >> (i * 2)) & 1 == 1;
        let should_endo = (challenge >> (i * 2 + 1)) & 1 == 1;

        acc = acc + &acc;
        if should_negate {
            acc = acc - &F2::one();
        } else {
            acc = acc + &F2::one();
        }

        if should_endo {
            acc = acc * &F2::BETA;
        }
    }

    acc
}

参考资料： [1] https://github.com/ebfull/halo/