Marlin ZK-SNARK简易教程

Marlin是一个零知识简洁证明（Zero Knowledge Succinct Non Interactive Argument of Knowledge, ZK-SNARK）系统，它能够对满足一阶限制系统（Rank One Constraint System，R1CS）条件的表达进行零知识证明.

R1CS是指满足以下条件的变量：
$$<A, W>\cdot <B, W> = <C, W>$$
其中$W$为变量向量（variable vector）其包括隐私变量（witness）和公共变量（public input）. $<\cdot,\cdot>$表示两个向量之间的内积. $A,B,C$表示$W$中变量对应的线性组合系数. ZK-SNARK的目的就是在保护隐私变量的情况下，仅使用公共变量证明存在隐私变量使得上述R1CS限制系统成立.

举个例子，考虑如下二元一次方程：
$$x-y+3z^2=out$$
其中$out$任意常数. 假设我们需要向第三方证明自己知道存在$(x,y,z)$上述表达式成立，但是又不想泄漏$(x,y,z)$的值，这时我们可以使用Marlin（或者任何其他ZK-SNARK系统）来达到这一点. 由于Marlin采用的是R1CS限制系统，我们首先要将其改写成R1CS表示形式：
$$w_1 + y = x \\ 3z^2=w_2 \\ w_1+w_2=1$$
然后我们可以提取出所有变量如下：
$$W=(x,y,z,w_1,w_2,one,out)$$
其中$one$表示常数1，但是这里为了满足R1CS条件，我们将其看作为一个变量. 对于变量$W$，显然有三个R1CS限制条件，其分别对应相应的三个方程. 于是我们可以提取线形组合向量如下如下：
$$A = \begin{pmatrix} 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 3 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ \end{pmatrix} B = \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{pmatrix} C = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{pmatrix}$$
显然对于矩阵$A,B,C$，其每一个行向量与$W$的内积都对对应于一个相应的限制条件.

代码实现

Marilin提供了Rust代码实现，因此我们可以使用Rust来验证我们之前的结果. 具体代码如下：

/* 导入相关数据库 */
use ark_ff::Field;
use ark_relations::{
    lc,
    r1cs::{ConstraintSynthesizer, ConstraintSystemRef, SynthesisError},
};
use ark_marlin::Marlin;
use ark_bls12_381::{Bls12_381, Fr};
use ark_poly::univariate::DensePolynomial;
use ark_poly_commit::marlin_pc::MarlinKZG10;
use blake2::Blake2s;
/* 简化函数名称 */
type MultiPC = MarlinKZG10<Bls12_381, DensePolynomial<Fr>>;
type MarlinInst = Marlin<Fr, MultiPC, Blake2s>

/* 定义目标代数Circuit表示方法 */
#[derive(Copy, Clone)]
struct DummyCircuit<F: Field> {
    x: Option<F>,
    y: Option<F>,
    z: Option<F>,
    num_constraints: usize, // 限制个数，在我们的例子中为3
    num_variables: usize,  // 变量个数，在我们的例子中为7
}

impl<ConstraintF: Field> ConstraintSynthesizer<ConstraintF> for DataQualityCircuit<ConstraintF> {
    fn generate_constraints(
        self,
        cs: ConstraintSystemRef<ConstraintF>,
    ) -> Result<(), SynthesisError> {
    /** 添加变量，其中witness_variable为隐私变量，input_variable为公共变量，在进行验证时输入 **/
        let x = cs.new_witness_variable(|| self.x.ok_or(SynthesisError::AssignmentMissing))?;
        let y = cs.new_witness_variable(|| self.y.ok_or(SynthesisError::AssignmentMissing))?;
        let z = cs.new_witness_variable(|| self.z.ok_or(SynthesisError::AssignmentMissing))?;
        let w1 = cs.new_witness_variable(|| {
            let mut x = self.x.ok_or(SynthesisError::AssignmentMissing)?;
            let y = self.y.ok_or(SynthesisError::AssignmentMissing)?;
            x.sub_assign(&y);
            Ok(x)
        })?;
        let w2 = cs.new_witness_variable(|| {
            let mut z = self.z.ok_or(SynthesisError::AssignmentMissing)?;
            let three = ConstraintF::one() + ConstraintF::one() + ConstraintF::one();
            z.mul_assign(&three);

            Ok(z)
        })?;
        let one = cs.new_witness_variable(|| Ok(ConstraintF::one()))?;
        let out = cs.new_input_variable(|| {
            let mut x = self.x.ok_or(SynthesisError::AssignmentMissing)?;
            let y = self.y.ok_or(SynthesisError::AssignmentMissing)?;
            x.sub_assign(&y);
            let mut z = self.z.ok_or(SynthesisError::AssignmentMissing)?;
            let three = ConstraintF::one() + ConstraintF::one() + ConstraintF::one();
            z.mul_assign(&three);

            x += &z;

            Ok(x)
        })?;
        /** 生成相应的限制条件，其中lc()!生成一个全新的零向量，与其相加的tuple分别为(系数，变量)，其将W中对应位置的变量加上系数 **/
        let three = ConstraintF::one() + ConstraintF::one() + ConstraintF::one();
        cs.enforce_constraint(lc!() + (ConstraintF::one(), y) + (ConstraintF::one(), w1), lc!() + (ConstraintF::one(), one), lc!() + (ConstraintF::one(), x))?;
        cs.enforce_constraint(lc!() + (three, one), lc!() + (ConstraintF::one(), z), lc!() + (ConstraintF::one(), w2))?;
        cs.enforce_constraint(lc!() + (ConstraintF::one(), w1) + (ConstraintF::one(), w2), lc!() + (ConstraintF::one(), one), lc!() + (ConstraintF::one(), out))?;

        Ok(())
    }
}

上述Rust代码实现了对于之前实例所表示的限制条件. 接着我们来进行测试

#[test]
fn test_dummy_circuit() {
    let rng = &mut ark_std::test_rng();

    let universal_srs = MarlinInst::universal_setup(3, 7, 3, rng).unwrap();
    let circ = DummyCircuit {
        x: Some(Fr::from(100u128)),
        y: Some(Fr::from(0u128)),
        z: Some(Fr::from(25u128)),
        num_constraints: 3,
        num_variables: 7,
    };
    let (index_pk, index_vk) = MarlinInst::index(&universal_srs, circ.clone()).unwrap();
    println!("Called index");

    let proof = MarlinInst::prove(&index_pk, circ, rng).unwrap();
    println!("Called prover");

    /** verify第二个为公共参数，在我们的例子中为out，可以发现其为175 **/
    assert!(MarlinInst::verify(&index_vk, &[Fr::from(175u128)], &proof, rng).unwrap());
    assert!(!MarlinInst::verify(&index_vk, &[Fr::from(176u128)], &proof, rng).unwrap());
}

使用cargo test -- -- test_dummy进行测试，可以发现程序通过了测试. 证明我们的确知道存在$x,y,z$且$x-y+3z^2=175$并且并不会泄漏$x,y,z$的值.