实验四

零知识证明libsnark实践

姓名：徐慧聪

学号：2023103793

1. 实验要求

  • 部署libsnark：libsnark 是实现了 zkSNARK 模式的 C++ 库
  • 编写程序，生成零知识证明，证明自己拥有某个问题的解
    • 数独
    • 多项式等式

2. libsnark部署

2.1 实验环境

  • Ubuntu 22.04
  • g++-9、gcc-9

2.2 部署

按照环境要求部署libsnark，因为部署比较复杂，这里我们参考这篇博客进行部署，https://blog.csdn.net/matlabdd1/article/details/123637302

3. 代码实现

3.1 数独

参考GitHub实现代码

  • validateInput_gadget：验证输入是否在集合$\{v_1…v_n\}$中，判断$(x - v_1) … (x - v_n) = 0$
  • checkEquality_gadget：验证行列块的值是否不同，判断$\prod (inputs[i] - inputs[j]) * inv = 1$
  • sudoku_gadget：接收数独的输入，验证输入、行、列、字块是否有效
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
template<typename FieldT>
class validateInput_gadget : public gadget<FieldT> {
private:
public:
    std::vector<int> values;
    pb_variable<FieldT> x;
    pb_variable_array<FieldT> intermediates;

    validateInput_gadget(protoboard<FieldT> &pb,
                         const pb_variable<FieldT> &x,
                         const std::vector<int> &values,
                         const std::string &annotation_prefix = "validate Input") :
            gadget<FieldT>(pb, annotation_prefix), x(x), values(values) {
        intermediates.allocate(pb, values.size() - 1, FMT(annotation_prefix, "intermediates"));
    }

    void generate_r1cs_constraints() {
        this->pb.add_r1cs_constraint(r1cs_constraint<FieldT>(
                {ONE * (-values[0]), x},
                {ONE * (-values[1]), x},
                {intermediates[0]}));

        for (size_t i = 1; i < values.size() - 1; i++) {
            this->pb.add_r1cs_constraint(r1cs_constraint<FieldT>(
                    { ONE * (-values[i]), x},
                    { intermediates[i-1] },
                    { intermediates[i] }));
        }
    }

    void generate_r1cs_witness() {
        FieldT _x = this->pb.val(x);
        this->pb.val(intermediates[0]) = FieldT((_x - values[0]) * (_x - values[1]));
        for (size_t i = 1; i < values.size() - 1; i++) {
            this->pb.val(intermediates[i]) = this->pb.val(intermediates[i - 1]) * (_x - values[i]);
        }
    }
};

template<typename FieldT>
class checkEquality_gadget : public gadget<FieldT> {
private:
public:
    pb_variable<FieldT> inv;
    pb_variable_array<FieldT> inputs;
    pb_variable_array<FieldT> intermediates;

    checkEquality_gadget(protoboard<FieldT> &pb,
                         const pb_variable_array<FieldT> &inputs,
                         const std::string &annotation_prefix = "checkEquality") :
            gadget<FieldT>(pb, annotation_prefix), inputs(inputs) {

        inv.allocate(pb, FMT(annotation_prefix, "inv"));

        int num = inputs.size() * (inputs.size() - 1) / 2;
        intermediates.allocate(pb, num, FMT(annotation_prefix, "intermediates"));
    }

    void generate_r1cs_constraints() {
        size_t counter = 0;
        for (size_t i = 0; i < inputs.size() - 1; i++) {
            for (size_t j = i + 1; j < inputs.size(); j++) {
                if (i == 0 && j == 1) {
                    this->pb.add_r1cs_constraint(r1cs_constraint<FieldT>(
                            {ONE},
                            {inputs[i], inputs[j] * (-1)},
                            {intermediates[0]}));
                    counter++;
                } else {
                    this->pb.add_r1cs_constraint(r1cs_constraint<FieldT>(
                            {intermediates[counter - 1]},
                            {inputs[i], inputs[j] * (-1)},
                            {intermediates[counter]}
                    ));
                    counter++;
                }
            }
        }

        this->pb.add_r1cs_constraint(r1cs_constraint<FieldT>(
                {intermediates[intermediates.size() - 1]},
                {inv},
                {ONE}
        ));
    }

    void generate_r1cs_witness() {
        std::vector<FieldT> _inputs(inputs.size());
        for (size_t i = 0; i < inputs.size(); i++) {
            _inputs[i] = this->pb.val(inputs[i]);
        }

        int counter = 0;
        for (size_t i = 0; i < inputs.size(); i++) {
            for (size_t j = i + 1; j < inputs.size(); j++) {
                if (i == 0 && j == 1) {
                    this->pb.val(intermediates[counter]) = _inputs[0] - _inputs[1];
                } else {
                    this->pb.val(intermediates[counter]) = this->pb.val(intermediates[counter - 1]) *
                                                           (_inputs[i] - _inputs[j]);
                }
                counter++;
            }
        }
        this->pb.val(inv) = this->pb.val(intermediates[counter-1]).inverse();
    }
};
template<typename FieldT>
class sudoku_gadget : public gadget<FieldT> {
private:
    /* internal */
public:
    std::vector<std::shared_ptr<validateInput_gadget<FieldT>>> v_inputs;

    std::vector<std::shared_ptr<checkEquality_gadget<FieldT>>> c_rows;
    std::vector<std::shared_ptr<checkEquality_gadget<FieldT>>> c_cols;
    std::vector<std::shared_ptr<checkEquality_gadget<FieldT>>> c_grids;

    pb_variable<FieldT> a11;
    pb_variable<FieldT> a12;
    pb_variable<FieldT> a21;
    pb_variable<FieldT> a22;

    pb_variable<FieldT> b11;
    pb_variable<FieldT> b12;
    pb_variable<FieldT> b21;
    pb_variable<FieldT> b22;

    pb_variable<FieldT> c11;
    pb_variable<FieldT> c12;
    pb_variable<FieldT> c21;
    pb_variable<FieldT> c22;

    pb_variable<FieldT> d11;
    pb_variable<FieldT> d12;
    pb_variable<FieldT> d21;
    pb_variable<FieldT> d22;

    pb_variable<FieldT> zero;

    sudoku_gadget(protoboard<FieldT> &pb, const std::string &annotation_prefix) :
            gadget<FieldT>(pb, annotation_prefix) {

        //primary inputs consist of a21, b11, b22, c11, c22, d21
        a21.allocate(pb, FMT(annotation_prefix, "primary_a21"));
        b11.allocate(pb, FMT(annotation_prefix, "primary_b11"));
        b22.allocate(pb, FMT(annotation_prefix, "primary_b22"));
        c11.allocate(pb, FMT(annotation_prefix, "primary_c11"));
        c22.allocate(pb, FMT(annotation_prefix, "primary_c22"));
        d21.allocate(pb, FMT(annotation_prefix, "primary_d21"));

        zero.allocate(pb, FMT(annotation_prefix, "zero"));
        //auxiliary inputs consist of the remaining 10 elements in the 4 x 4 grid
        a11.allocate(pb, FMT(annotation_prefix, "aux_a11"));
        a12.allocate(pb, FMT(annotation_prefix, "aux_a12"));
        a22.allocate(pb, FMT(annotation_prefix, "aux_a22"));
        b12.allocate(pb, FMT(annotation_prefix, "aux_b12"));
        b21.allocate(pb, FMT(annotation_prefix, "aux_b21"));
        c12.allocate(pb, FMT(annotation_prefix, "aux_c12"));
        c21.allocate(pb, FMT(annotation_prefix, "aux_c21"));
        d11.allocate(pb, FMT(annotation_prefix, "aux_d11"));
        d12.allocate(pb, FMT(annotation_prefix, "aux_d12"));
        d22.allocate(pb, FMT(annotation_prefix, "aux_d22"));

        pb.set_input_sizes(6);

        //input validation
        std::vector<pb_variable<FieldT>> inputs = {a11, a12, a21, a22,
                                                   b11, b12, b21, b22,
                                                   c11, c12, c21, c22,
                                                   d11, d12, d21, d22};
        v_inputs.reserve(16);
        v_inputs.resize(16);
        for (size_t i = 0; i < 16; i++) {
            v_inputs[i].reset(new validateInput_gadget<FieldT>(pb, inputs[i], {1, 2, 3, 4}));
        }

        c_rows.reserve(4); c_rows.resize(4);
        c_cols.reserve(4); c_cols.resize(4);
        c_grids.reserve(4); c_grids.resize(4);

        //row validation
        std::vector<pb_variable<FieldT>> row0 = {a11, a12, b11, b12};
        std::vector<pb_variable<FieldT>> row1 = {a21, a22, b21, b22};
        std::vector<pb_variable<FieldT>> row2 = {c11, c12, d11, d12};
        std::vector<pb_variable<FieldT>> row3 = {c21, c22, d21, d22};

        pb_variable_array<FieldT> _row0(row0.begin(), row0.end());
        pb_variable_array<FieldT> _row1(row1.begin(), row1.end());
        pb_variable_array<FieldT> _row2(row2.begin(), row2.end());
        pb_variable_array<FieldT> _row3(row3.begin(), row3.end());

        c_rows[0].reset(new checkEquality_gadget<FieldT>(pb, _row0));
        c_rows[1].reset(new checkEquality_gadget<FieldT>(pb, _row1));
        c_rows[2].reset(new checkEquality_gadget<FieldT>(pb, _row2));
        c_rows[3].reset(new checkEquality_gadget<FieldT>(pb, _row3));

        //column validation
        std::vector<pb_variable<FieldT>> col0 = {a11, a21, c11, c21};
        std::vector<pb_variable<FieldT>> col1 = {a12, a22, c12, c22};
        std::vector<pb_variable<FieldT>> col2 = {b11, b21, d11, d21};
        std::vector<pb_variable<FieldT>> col3 = {b12, b22, d12, d22};

        pb_variable_array<FieldT> _col0(col0.begin(), col0.end());
        pb_variable_array<FieldT> _col1(col1.begin(), col1.end());
        pb_variable_array<FieldT> _col2(col2.begin(), col2.end());
        pb_variable_array<FieldT> _col3(col3.begin(), col3.end());

        c_cols[0].reset(new checkEquality_gadget<FieldT>(pb, _col0));
        c_cols[1].reset(new checkEquality_gadget<FieldT>(pb, _col1));
        c_cols[2].reset(new checkEquality_gadget<FieldT>(pb, _col2));
        c_cols[3].reset(new checkEquality_gadget<FieldT>(pb, _col3));

        //subgrid validation
        std::vector<pb_variable<FieldT>> grid0 = {a11, a12, a21, a22};
        std::vector<pb_variable<FieldT>> grid1 = {b11, b12, b21, b22};
        std::vector<pb_variable<FieldT>> grid2 = {c11, c12, c21, c22};
        std::vector<pb_variable<FieldT>> grid3 = {d11, d12, d21, d22};

        pb_variable_array<FieldT> _grid0(grid0.begin(), grid0.end());
        pb_variable_array<FieldT> _grid1(grid1.begin(), grid1.end());
        pb_variable_array<FieldT> _grid2(grid2.begin(), grid2.end());
        pb_variable_array<FieldT> _grid3(grid3.begin(), grid3.end());

        c_grids[0].reset(new checkEquality_gadget<FieldT>(pb, _grid0));
        c_grids[1].reset(new checkEquality_gadget<FieldT>(pb, _grid1));
        c_grids[2].reset(new checkEquality_gadget<FieldT>(pb, _grid2));
        c_grids[3].reset(new checkEquality_gadget<FieldT>(pb, _grid3));
    }

    void generate_r1cs_constraints() {
        for (size_t i = 0; i < 16; i++) {
            v_inputs[i]->generate_r1cs_constraints();
        }

        for (size_t i = 0; i < 4; i++) {
            c_rows[i]->generate_r1cs_constraints();
            c_cols[i]->generate_r1cs_constraints();
            c_grids[i]->generate_r1cs_constraints();
        }
    }

    void generate_r1cs_witness(const std::vector<int> &_inputs_a,
                               const std::vector<int> &_inputs_b,
                               const std::vector<int> &_inputs_c,
                               const std::vector<int> &_inputs_d) {
        assert(_inputs_a.size() == 4);
        assert(_inputs_b.size() == 4);
        assert(_inputs_c.size() == 4);
        assert(_inputs_d.size() == 4);

        this->pb.val(a11) = _inputs_a[0];
        this->pb.val(a12) = _inputs_a[1];
        this->pb.val(a21) = _inputs_a[2];
        this->pb.val(a22) = _inputs_a[3];

        this->pb.val(b11) = _inputs_b[0];
        this->pb.val(b12) = _inputs_b[1];
        this->pb.val(b21) = _inputs_b[2];
        this->pb.val(b22) = _inputs_b[3];

        this->pb.val(c11) = _inputs_c[0];
        this->pb.val(c12) = _inputs_c[1];
        this->pb.val(c21) = _inputs_c[2];
        this->pb.val(c22) = _inputs_c[3];

        this->pb.val(d11) = _inputs_d[0];
        this->pb.val(d12) = _inputs_d[1];
        this->pb.val(d21) = _inputs_d[2];
        this->pb.val(d22) = _inputs_d[3];

        for (size_t i = 0; i < 16; i++) {
            v_inputs[i]->generate_r1cs_witness();
        }

        for (size_t i = 0; i < 4; i++) {
            c_rows[i]->generate_r1cs_witness();
            c_cols[i]->generate_r1cs_witness();
            c_grids[i]->generate_r1cs_witness();
        }
    }
};

3.2 多项式等式

  • 判断多项式$x^3+x+5 = out$

  • 将多项式转化成R1CS电路

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#define CURVE_ALT_BN128
#include <libsnark/common/default_types/r1cs_gg_ppzksnark_pp.hpp>
#include <libsnark/zk_proof_systems/ppzksnark/r1cs_gg_ppzksnark/r1cs_gg_ppzksnark.hpp>
#include <libsnark/gadgetlib1/pb_variable.hpp>

using namespace libsnark;
using namespace std;

int main () {
    typedef libff::Fr<default_r1cs_gg_ppzksnark_pp> FieldT;

    // Initialize the curve parameters
    default_r1cs_gg_ppzksnark_pp::init_public_params();
  
    // Create protoboard
    protoboard<FieldT> pb;

    // Define variables
    pb_variable<FieldT> x;
    pb_variable<FieldT> sym_1;
    pb_variable<FieldT> y;
    pb_variable<FieldT> sym_2;
    pb_variable<FieldT> out;

    // Allocate variables to protoboard
    // The strings (like "x") are only for debugging purposes    
    out.allocate(pb, "out");
    x.allocate(pb, "x");
    sym_1.allocate(pb, "sym_1");
    y.allocate(pb, "y");
    sym_2.allocate(pb, "sym_2");

    // This sets up the protoboard variables
    // so that the first one (out) represents the public
    // input and the rest is private input
    pb.set_input_sizes(1);

    // Add R1CS constraints to protoboard

    // x*x = sym_1
    pb.add_r1cs_constraint(r1cs_constraint<FieldT>(x, x, sym_1));

    // sym_1 * x = y
    pb.add_r1cs_constraint(r1cs_constraint<FieldT>(sym_1, x, y));

    // y + x = sym_2
    pb.add_r1cs_constraint(r1cs_constraint<FieldT>(y + x, 1, sym_2));

    // sym_2 + 5 = ~out
    pb.add_r1cs_constraint(r1cs_constraint<FieldT>(sym_2 + 5, 1, out));
    
    const r1cs_constraint_system<FieldT> constraint_system = pb.get_constraint_system();

    // generate keypair
    const r1cs_gg_ppzksnark_keypair<default_r1cs_gg_ppzksnark_pp> keypair = r1cs_gg_ppzksnark_generator<default_r1cs_gg_ppzksnark_pp>(constraint_system);

    // Add public input and witness values
    pb.val(out) = 35;

    pb.val(x) = 3;
    pb.val(sym_1) = 9;
    pb.val(y) = 27;
    pb.val(sym_2) = 30;

    // generate proof
    const r1cs_gg_ppzksnark_proof<default_r1cs_gg_ppzksnark_pp> proof = r1cs_gg_ppzksnark_prover<default_r1cs_gg_ppzksnark_pp>(keypair.pk, pb.primary_input(), pb.auxiliary_input());

    // verify
    bool verified = r1cs_gg_ppzksnark_verifier_strong_IC<default_r1cs_gg_ppzksnark_pp>(keypair.vk, pb.primary_input(), proof);

    cout << "Number of R1CS constraints: " << constraint_system.num_constraints() << endl;
    cout << "Primary (public) input: " << pb.primary_input() << endl;
    cout << "Auxiliary (private) input: " << pb.auxiliary_input() << endl;
    cout << "Verification status: " << verified << endl;

    return 0;
}

4. 实验结果

4.1 数独

  • 可以看到通过了验证

Untitled

4.2 多项式

  • 输入out = 35通过验证

Untitled

5. 总结

  • 部署了零知识证明的libsnark库
  • 实现了零知识的数独和多项式等式验证