1. 引言

zkllvm-blueprint库的核心思想还是借鉴了https://github.com/scipr-lab/libsnark：

crypto3-zk库：为零知识密码学工具。当前仅支持SNARK系列的方案，未来将支持STARKs、IOP-based SNARKs、Bulletproofs等。
zkllvm-blueprint库：Blueprint库定义了Circuit components，供zkLLVM circuit compiler使用。

支持与crypto3-zk一起使用：
- blueprint模块负责生成constraint system的input data；
- crypto3-zk模块将blueprint的输出作为输入，用于生成证明。

circuit

由：

Blueprint 实例：对应电路本身、gates、constraints以及其它fixed expressions。
Blueprint assignment table
实例：包含了zk-SNARK系统所需的public和private assignments。

包含了：
- Blueprint public assignment table
- Blueprint private assignment table

组成。每个实例可包含一个或多个

Component

。

主要示例见：

https://github.com/NilFoundation/zkllvm-blueprint/blob/master/docs/usage.md

1.1 PLONK Component接口

Component

为state-less类型，包含了以下静态函数接口：

X::allocate_rows ：分配一定行数给指定的 Arithmetization table 。所需的行数由特定component的constexpr决定。
X::generate_circuit ：生成gate expressions、copy constraints、lookup constraints，并将其给特定的 Blueprint 。
- 会修改 Blueprint public assignment table 中的 Constant 或 Selector 列。
- 但不会使用或设置 Blueprint private assignment table 中的数据。
X::generate_assignments ：evaluate assignment values，并将其给特定的 Blueprint assignment table 。
- 仅有 generate_assignment 函数可管理修改 Blueprint private assignment table 中数据。
- 也可修改 Blueprint public assignment table 中数据。

具体为：

Function	Required Input	Can modify
`X::allocate_rows`	`Blueprint`	`Blueprint`
`X::generate_circuit`	`Blueprint` , `Component params` , `Allocated data (auxiliary data for the component re-use)` , `component start row`	`Blueprint` , `Allocated data`
`X::generate_assignments`	`Blueprint assignment table` , `Component params` , `component start row`	`Blueprint assignment table`

添加a component的流程为：

1）调用 allocate_rows 来获取 component 的start row。若该 component 为其它 component 内的一部分，则没必要调用该行数，应所allocated rows由主 component 决定。
2）调用 Blueprint assignment table::allocate_public_input 来给 Blueprint assignment table 分配public input。
3）调用 generate_circuit 来设置 Blueprint 的所有gates和constraints。在 generate_circuit 函数运行过程中，会修改 Allocated data 。
4）调用 generate_assignments 来设置 Blue assignment table 中的所有assignments。

2. Vitalik R1CS示例

详细可参看 Vitalik 博客Quadratic Arithmetic Programs: from Zero to Hero。

class test_component : public components::component<FieldType> {
    using field_type = FieldType;
    components::blueprint_variable<field_type> sym_1; //中间变量
    components::blueprint_variable<field_type> y; //中间变量
    components::blueprint_variable<field_type> sym_2; //中间变量
public:
    const components::blueprint_variable<field_type> out; //输出结果，为public input
    const components::blueprint_variable<field_type> x; //witness，为private input

    test_component(blueprint<field_type> &bp,
                const components::blueprint_variable<field_type> &out,
                const components::blueprint_variable<field_type> &x) : 
      components::component<field_type>(bp), out(out), x(x) {

      // Allocate variables to blueprint
      
      sym_1.allocate(this->bp); //分配中间变量
      y.allocate(this->bp); //分配中间变量
      sym_2.allocate(this->bp); //分配中间变量
    }

    void generate_gates() { //添加约束，生成电路。
      // x*x = sym_1
      this->bp.add_r1cs_constraint(snark::r1cs_constraint<field_type>(x, x, sym_1));

      // sym_1 * x = y
      this->bp.add_r1cs_constraint(snark::r1cs_constraint<field_type>(sym_1, x, y));

      // y + x = sym_2
      this->bp.add_r1cs_constraint(snark::r1cs_constraint<field_type>(y + x, 1, sym_2));

      // sym_2 + 5 = ~out
      this->bp.add_r1cs_constraint(snark::r1cs_constraint<field_type>(sym_2 + 5, 1, out));
    }

    void generate_assignments() { //为中间变量赋值
      this->bp.val(sym_1) = this->bp.val(x) * this->bp.val(x);
      this->bp.val(y) = this->bp.val(sym_1) * this->bp.val(x);
      this->bp.val(sym_2) = this->bp.val(y) + this->bp.val(x);
    }
};

int main(){

    using curve_type = curves::bls12<381>;
    using field_type = typename curve_type::scalar_field_type;
        
    // Create blueprint

    blueprint<field_type> bp;
    blueprint::value_type<field_type> out;
    blueprint::value_type<field_type> x;

    // Allocate variables

    out.allocate(bp); //分配变量
    x.allocate(bp);

    // This sets up the blueprint variables
    // so that the first one (out) represents the public
    // input and the rest is private input

    bp.set_input_sizes(1); //设置public input变量数为1，即表示所分配的第一个变量（out）为public input，之后的均为private input

    // Initialize component

    test_component<field_type> g(bp, out, x);
    g.generate_gates(); //添加约束，生成电路。
    
    // Add witness values

    bp.val(out) = 35; //为public和private input赋值
    bp.val(x) = 3;

    g.generate_assignments(); //为中间变量赋值
    
    assert(bp.is_satisfied()); //验证所赋变量值能否满足电路约束

    const snark::r1cs_constraint_system<field_type> constraint_system = bp.get_constraint_system(); //获取约束系统

    const typename snark::r1cs_gg_ppzksnark<curve_type>::keypair_type keypair = snark::generate<crypto3::zk::snark::r1cs_gg_ppzksnark<curve_type>>(constraint_system); //基于约束系统做可信设置，获得keypair

    const typename snark::r1cs_gg_ppzksnark<curve_type>::proof_type proof = snark::prove<crypto3::zk::snark::r1cs_gg_ppzksnark<curve_type>>(keypair.first, bp.primary_input(), bp.auxiliary_input()); //基于proving key、public（primary） input、auxiliary input（包括private input以及中间变量值）生成proof。

    bool verified = snark::verify<crypto3::zk::snark::r1cs_gg_ppzksnark<curve_type>>(keypair.second, bp.primary_input(), proof); //基于verifying key、public（primary）input和proof验证证明

    std::cout << "Number of R1CS constraints: " << constraint_system.num_constraints() << std::endl; //打印约叔叔
    std::cout << "Verification status: " << verified << std::endl;

    const typename snark::r1cs_gg_ppzksnark<curve_type>::verification_key_type vk = keypair.second;

    return 0;
}

3. Inner product示例

class inner_product : public component<FieldType> {
                private:
                    /* S_i = \sum_{k=0}^{i} A[k] * B[k] */
                    blueprint_variable_vector<FieldType> S;

                public:
                    const blueprint_linear_combination_vector<FieldType> A;
                    const blueprint_linear_combination_vector<FieldType> B;
                    const blueprint_variable<FieldType> result;

                    inner_product(blueprint<FieldType> &bp,
                                  const blueprint_linear_combination_vector<FieldType> &A,
                                  const blueprint_linear_combination_vector<FieldType> &B,
                                  const blueprint_variable<FieldType> &result) :
                        component<FieldType>(bp),
                        A(A), B(B), result(result) {
                        assert(A.size() >= 1);
                        assert(A.size() == B.size());

                        S.allocate(bp, A.size() - 1);
                    }

                    void generate_gates() {
                        /*
                          S_i = \sum_{k=0}^{i} A[k] * B[k]
                          S[0] = A[0] * B[0]
                          S[i+1] - S[i] = A[i] * B[i]
                        */
                        for (std::size_t i = 0; i < A.size(); ++i) {
                            this->bp.add_r1cs_constraint(snark::r1cs_constraint<FieldType>(
                                A[i], B[i],
                                (i == A.size() - 1 ? result : S[i]) +
                                    (i == 0 ? 0 * blueprint_variable<FieldType>(0) : -S[i - 1])));
                        }
                    }

                    void generate_assignments() {
                        typename FieldType::value_type total = FieldType::value_type::zero();
                        for (std::size_t i = 0; i < A.size(); ++i) {
                            A[i].evaluate(this->bp);
                            B[i].evaluate(this->bp);

                            total += this->bp.lc_val(A[i]) * this->bp.lc_val(B[i]);
                            this->bp.val(i == A.size() - 1 ? result : S[i]) = total;
                        }
                    }
                };

            }    // namespace components

void test_inner_product_component(size_t n) {
    blueprint<FieldType> bp;
    nil::crypto3::zk::detail::blueprint_variable_vector<FieldType> A;
    A.allocate(bp, n);
    nil::crypto3::zk::detail::blueprint_variable_vector<FieldType> B;
    B.allocate(bp, n);

    nil::crypto3::zk::detail::blueprint_variable<FieldType> result;
    result.allocate(bp);

    components::inner_product<FieldType> g(bp, A, B, result);
    g.generate_gates();

    for (std::size_t i = 0; i < 1ul << n; ++i) {
        for (std::size_t j = 0; j < 1ul << n; ++j) {
            std::size_t correct = 0;
            for (std::size_t k = 0; k < n; ++k) {
                bp.val(A[k]) = (i & (1ul << k) ? FieldType::value_type::one() : FieldType::value_type::zero());
                bp.val(B[k]) = (j & (1ul << k) ? FieldType::value_type::one() : FieldType::value_type::zero());
                correct += ((i & (1ul << k)) && (j & (1ul << k)) ? 1 : 0);
            }

            g.generate_assignments();

            BOOST_CHECK(bp.val(result) == typename FieldType::value_type(correct));
            BOOST_CHECK(bp.is_satisfied());

            bp.val(result) = typename FieldType::value_type(100 * n + 19);
            BOOST_CHECK(!bp.is_satisfied());
        }
    }
}

4. SHA-256示例

附录 nil Foundation系列博客

nil Foundation的Solana-Ethereum Bridge Based on Light-Client State Proof Verification
nil Foundation的基于Solana light client实现的zk-bridge方案
nil Foundation的Mina-＞以太坊 bridge原型已完成
nil Foundation的Mina-Ethereum State Proof Verification Applications
nil Foundation的in-EVM Full Mina State Verification
nil Foundation的Placeholder证明系统（1）
zkLLVM：nil Foundation开发的电路编译器

nil Foundation blueprint模块代码解析1. 引言2. Vitalik R1CS示例3. Inner product示例4. SHA-256示例附录 nil Foundation系列博客

1. 引言

1.1 PLONK Component接口

2. Vitalik R1CS示例

3. Inner product示例

4. SHA-256示例

附录 nil Foundation系列博客

继续阅读

Halo2 学习笔记——背景资料之Polynomials（3）1. 引言2. Horner’s rule3. FFT4. The Schwartz-Zippel lemma5. Vanishing polynomial6. Lagrange basis functions参考资料

zkTree: a zk recursion tree with ZKP membership proofs1. 引言

零知识证明-入门学习笔记(五)

Bulletproofs++1. 引言

Sigma protocol用于one-out-of-many证明

Rollup交易的固化流程1. 引言2. Sequencer’s Promise3. Transaction Order Finality4. Execution Settlement5. Rollup交易的固化流程小结参考资料

Mina中的树结构1. 引言2. Mina中的账号树3. Mina中的pending coinbase树4. Mina中的scan state树5. Mina中Parties交易中的other_parties Call_forest树附录1. Mina系列博客

Lookup argument总览1. 引言

我公司有几项专利技术，想做无形资产评估，哪些公司

区块链知识系列 - 系统学习EVM(四)-zkEVM

各种开源许可协议图

零知识证明技术研究

一文读懂Layer 2

密码学中的各种假设——DL/SDH...

Why and How zk-SNARK Works 1: Introduction & the Medium of a Proof