近日因为种种原因又拾起了零知识证明方向的相关工作，于是在此简略做一下libsnark相关的记录

https://github.com/scipr-lab/libsnark/tree/2af440246fa2c3d0b1b0a425fb6abd8cc8b9c54d

基于zk-SNARKs实现非交互式零知识证明应用的开发顺序可以概括如下：

  1. 创建一个r1cs_constraint_system（libsnark设计了gadget的框架帮助构建）；

  2. 生成proving key和verification key；

  3. Alice使用proving key和拥有的可行解构造证明$\pi$；

  4. Bob使用verification key验证$\pi$；

下面参考https://zhuanlan.zhihu.com/p/46477111中给出的例子，逐步跟进，对gadgetlib1的相关源码进行解析：

先定位到添加r1cs约束相关的add_r1cs_constraint：

libsnark/gadgetlib1/protoboard.hpp : L51 & protoboard.tcc : L100-110

1
2
3
4
5
6
7
8
9
10
11
12
13
void add_r1cs_constraint(const r1cs_constraint<FieldT> &constr, const std::string &annotation="");

template<typename FieldT>
void protoboard<FieldT>::add_r1cs_constraint(const r1cs_constraint<FieldT> &constr, const std::string &annotation)
{
#ifdef DEBUG
    assert(annotation != "");
    constraint_system.constraint_annotations[constraint_system.constraints.size()] = annotation;
#else
    libff::UNUSED(annotation);
#endif
    constraint_system.constraints.emplace_back(constr);
}

其中r1cs_constraint_system<FieldT> constraint_system

且constraint_system.constraints的类型为std::vector<r1cs_constraint<FieldT> >

于是我们跟进到r1cs_constraint类：

libsnark/relations/constraint_satisfaction_problems/r1cs/r1cs.hpp : L41-70

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * A R1CS constraint is a formal expression of the form
 *
 *                < A , X > * < B , X > = < C , X > ,
 *
 * where X = (x_0,x_1,...,x_m) is a vector of formal variables and A,B,C each
 * consist of 1+m elements in <FieldT>.
 *
 * A R1CS constraint is used to construct a R1CS constraint system (see below).
 */
template<typename FieldT>
class r1cs_constraint {
public:

    linear_combination<FieldT> a, b, c;

    r1cs_constraint() {};
    r1cs_constraint(const linear_combination<FieldT> &a,
                    const linear_combination<FieldT> &b,
                    const linear_combination<FieldT> &c);

    r1cs_constraint(const std::initializer_list<linear_combination<FieldT> > &A,
                    const std::initializer_list<linear_combination<FieldT> > &B,
                    const std::initializer_list<linear_combination<FieldT> > &C);

    bool operator==(const r1cs_constraint<FieldT> &other) const;

    friend std::ostream& operator<< <FieldT>(std::ostream &out, const r1cs_constraint<FieldT> &c);
    friend std::istream& operator>> <FieldT>(std::istream &in, r1cs_constraint<FieldT> &c);
};

注意到参数类型为linear_combination的构造函数，继续跟进相关类：

image-20211017201752561

image-20211017205311619

libsnark/relations/variable.hpp : L144-158

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * A linear combination represents a formal expression of the form "sum_i coeff_i * x_{index_i}".
 */
template<typename FieldT>
class linear_combination {
public:

    std::vector<linear_term<FieldT> > terms;

    linear_combination() {};
    linear_combination(const integer_coeff_t int_coeff);
    linear_combination(const FieldT &field_coeff);
    linear_combination(const variable<FieldT> &var);
    linear_combination(const linear_term<FieldT> &lt);
    linear_combination(const std::vector<linear_term<FieldT> > &all_terms);

参数类型为std::vector<linear_term<FieldT> >的构造函数具体实现如下：

libsnark/relations/variable.tcc : L484-508

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
template<typename FieldT>
linear_combination<FieldT>::linear_combination(const std::vector<linear_term<FieldT> > &all_terms)
{
    if (all_terms.empty())
    {
        return;
    }

    terms = all_terms;
    std::sort(terms.begin(), terms.end(), [](linear_term<FieldT> a, linear_term<FieldT> b) { return a.index < b.index; });

    auto result_it = terms.begin();
    for (auto it = ++terms.begin(); it != terms.end(); ++it)
    {
        if (it->index == result_it->index)
        {
            result_it->coeff += it->coeff;
        }
        else
        {
            *(++result_it) = *it;
        }
    }
    terms.resize((result_it - terms.begin()) + 1);
}

该构造函数中还做了linear_item::index（变量标识）的合并，表现为coeff相加

以及其他参数类型的构造函数，比如

1
2
3
4
5
6
7
8
9
10
11
12
13
template<typename FieldT>
linear_combination<FieldT>::linear_combination(const FieldT &field_coeff)
{
    this->add_term(linear_term<FieldT>(0, field_coeff));
}

// r1cs.hpp L108-111👇

/**
* NOTE:
* The 0-th variable (i.e., "x_{0}") always represents the constant 1.
* Thus, the 0-th variable is not included in num_variables.
*/

至此我们知道如何去构建一个r1cs_constraint{_system_}的后半部分

image-20211017211212901

现在回到前半部分：

gadgetlib1提供了pb_variable、pb_variable_array、pb_linear_combination和pb_linear_combination_array四个类，是对variable、linear_combination的封装

libsnark/gadgetlib1/pb_variable.hpp & pb_variable.tcc

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template<typename FieldT>
void pb_variable<FieldT>::allocate(protoboard<FieldT> &pb, const std::string &annotation)
{
    this->index = pb.allocate_var_index(annotation);
}

/* allocates pb_variable<FieldT> array in MSB->LSB order */
template<typename FieldT>
void pb_variable_array<FieldT>::allocate(protoboard<FieldT> &pb, const size_t n, const std::string &annotation_prefix)
{
#ifdef DEBUG
    assert(annotation_prefix != "");
#endif
    (*this).resize(n);

    for (size_t i = 0; i < n; ++i)
    {
        (*this)[i].allocate(pb, FMT(annotation_prefix, "_%zu", i));
    }
}

需要注意的是pb_variable::allocate👉protoboard::allocate_var_index（即分配输入变量的相关部分）

libsnark/gadgetlib1/protoboard.hpp : L34 & protoboard.tcc : L37-49

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
r1cs_variable_assignment<FieldT> values; /* values[0] will hold the value of the first allocated variable of the protoboard, *NOT* constant 1 */
// values将存储着r1cs一系列变量的*值*

template<typename FieldT>
var_index_t protoboard<FieldT>::allocate_var_index(const std::string &annotation)
{
#ifdef DEBUG
    assert(annotation != "");
    constraint_system.variable_annotations[next_free_var] = annotation;
#else
    libff::UNUSED(annotation);
#endif
    ++constraint_system.auxiliary_input_size;
    values.emplace_back(FieldT::zero());	// 初始化
    return next_free_var++;
}

具体的gadget实现例子可参考

libsnark还会用到libff（C++ library for Finite Fields and Elliptic Curves）等库👈e.g. #define FMT libff::FORMAT，在此不加赘述