ZEXE分布式隐私计算

参考2019年2月发表的论文《Zexe: Enabling Decentralized Private Computation》，具体实现见代码库。

1. zexe中的algebra代数运算

zexe\algebra\src\curves中，对bls12_377、bls12_381、edwards_bls12、edwards_sw6、jubjub、mnt6、sw6等共7条曲线做了实现，同时对bls12_377、bls12_381和sw6做了bench测试。

1.1FixedBaseMSM运算

zexe/algebra/src/msm/fixed_base.rs中有： 1）get_mul_window_size根据多项式的阶 d d d(即num_scalars)来决定窗口的大小。

pub fn get_mul_window_size(num_scalars: usize) -> usize {
        if num_scalars < 32 {
            3
        } else {
            (f64::from(num_scalars as u32)).ln().ceil() as usize
        }
    }

2）get_window_table返回的为一个二维数组，列数为：2^{window}，行数为outerc=(scalar_size + window - 1) / window，其中的scalar_size为曲线的MODULUS_BITS。其中最后一列，除了前last_in_window个外，之后的均为零值。 [ 0 g 2 g 3 g 4 g . . . ( 2 w i n d o w − 1 ) g 0 ( 2 w i n d o w ) g 2 ∗ ( 2 w i n d o w ) g 3 ∗ ( 2 w i n d o w ) g 4 ∗ ( 2 w i n d o w ) g . . . ( 2 2 ∗ w i n d o w − 1 ) g . . . . . . . . . . . . . . . . . . . . . 0 ( 2 ( o u t e r c − 1 ) ∗ w i n d o w ) g 2 ∗ ( 2 ( o u t e r c − 1 ) ∗ w i n d o w ) g . . . ( l a s t _ i n _ w i n d o w − 1 ) ∗ ( 2 ( o u t e r c − 1 ) ∗ w i n d o w ) g 0 0 ] \begin{bmatrix} 0& g & 2g & 3g & 4g & ... & (2^{window}-1)g\\ 0& (2^{window})g & 2*(2^{window})g & 3*(2^{window})g & 4*(2^{window})g & ... & (2^{2*window}-1)g \\ ... & ... & ... & ... & ... & ... & ...\\ 0 & (2^{(outerc-1)*window})g & 2*(2^{(outerc-1)*window})g & ... & (last\_in\_window-1)*(2^{(outerc-1)*window})g & 0 & 0 \end{bmatrix} ⎣⎢⎢⎡00...0g(2window)g...(2(outerc−1)∗window)g2g2∗(2window)g...2∗(2(outerc−1)∗window)g3g3∗(2window)g......4g4∗(2window)g...(last_in_window−1)∗(2(outerc−1)∗window)g.........0(2window−1)g(22∗window−1)g...0⎦⎥⎥⎤

pub fn get_window_table(
        scalar_size: usize,
        window: usize,
        g: T,
    ) -> Vec{
        let in_window = 1 << window;
        let outerc = (scalar_size + window - 1) / window;
        let last_in_window = 1 << (scalar_size - (outerc - 1) * window);

        let mut multiples_of_g = vec![vec![T::zero(); in_window]; outerc];

        let mut g_outer = g;
        for outer in 0..outerc {
            let mut g_inner = T::zero();
            let cur_in_window = if outer == outerc - 1 {
                last_in_window
            } else {
                in_window
            };
            for inner in 0..cur_in_window {
                multiples_of_g[outer][inner] = g_inner;
                g_inner += &g_outer;
            }
            for _ in 0..window {
                g_outer.double_in_place();
            }
        }
        multiples_of_g
    }

3）multi_scalar_mul函数中采用了v.par_iter()（调用rayon库）并行计算，其中table为上面2）返回的二维数组multiples_of_g，v为一维数组（如 [ 1 , β , β 2 , β 3 , . . . , β d ] [1,\beta,\beta^2,\beta^3,...,\beta^d ] [1,β,β2,β3,...,βd]），对应返回的结果为 [ g , β g , β 2 g , β 3 g , . . . , β d g ] [g,\beta g,\beta^2 g,\beta^3 g,...,\beta^d g] [g,βg,β2g,β3g,...,βdg]。 windowed_mul以查表的方式从multiples_of_g中计算相应的scalar*g的值。

pub fn multi_scalar_mul(
        scalar_size: usize,
        window: usize,
        table: &[Vec],
        v: &[T::ScalarField],
    ) -> Vec{
        let outerc = (scalar_size + window - 1) / window;
        assert!(outerc <= table.len());

        v.par_iter().map(|e| Self::windowed_mul::(outerc, window, table, e)).collect::()
    }
    pub fn windowed_mul(
        outerc: usize,
        window: usize,
        multiples_of_g: &[Vec],
        scalar: &T::ScalarField,
    ) -> T {
        let mut scalar_val = scalar.into_repr().to_bits();
        scalar_val.reverse(); //将scalar转换为以big-endian形式表示，如为10，对应为1010

        let mut res = multiples_of_g[0][0];
        for outer in 0..outerc {
            let mut inner = 0usize;
            for i in 0..window {
                if outer * window + i < (::Params::MODULUS_BITS as usize)
                    && scalar_val[outer * window + i]
                {
                    inner |= 1 << i;
                }
            }
            res += &multiples_of_g[outer][inner];
        }
        res
    }

2. zexe的bench-utils

配置上--features print-trace，调用其提供的start_timer!和end_timer!等宏，可打印各个环节实际执行时间，非常实用。

3. zexe的crypto-primitives

zexe的crypto-primitives提供了三种commitment（blake2s、pedersen和injective_map）及相应的bench。 1）commitment

• blake2s为hash函数；
• pedersen为pedersen commitment；
• injective_map为在pedersen commitment的基础上，同时保证最终的commit点在curve上且在相应的prime order subgroup。

2）crh

• injective_map：
• pedersen：

3）merkle_tree

4）nizk

• gm17：
• groth16：

5）prf

• blake2s：

参考资料： [1] 2019年论文《Zexe: Enabling Decentralized Private Computation》