libsnark教程
原文出自：libsnark库
作者：libsnark贡献者
译者：Matter实验室
gadgetlib2库的使用以及如何整合ppzkSNARK的教程和范例。这分文档专为小零件(gadget)写的，推荐从上至下作为教程来阅读。
1. 面包板(protoboard)的使用和范例
这个测试给出构造系统限制(constraint)的第一个范例。我们将时不时交替使用 ‘系统限制’(Constraint) 和 ‘电路’(Circuit) 两个术语. 用输入和输出形象化一个电路非常容易。每个门强制规定输入和输出线之间的逻辑。例如，AND(inp1,inp2) 会强制 (inp1 & inp2 = out) 这个限制。因此，我们也能认为这个电路是一个限制系统。每个门是一个数学限制，每个线是一个变量。在AND的例子中，通过boolean类型{0,1}我们将写出一个像(inp1*inp2==out)这样的限制。如果我们指派值到{inp1,inp2,out}，并且这个限制对于这样的赋值是满足的，因此对这个限制的评估就是TRUE。所有接下来的例子是要么是领域不可知或素数字段的特殊形式。
-
领域不可知情况：在这些例子中，我们用低级电路来创建一个高级电路。这种方法我们可以忽略一个字段的具体的情况，并假定低级电路会处理这个。如果我们必须在这些电路中显示的写出限制。这种情况常常是一下非常基础的限制，并可以定义在每个字段上，例如(e.g. x+y=0)。
-
所有字段都具体的例子，在这个库中，是对素数性质的字段来说的，采用的是‘二次秩1多项式’或者叫R1P 。这是当前SNARKs实现的唯一形式。这种形式专门处理像(Linear Combination) * (Linear Combination) == (Linear Combination)这样的限制。这个库已经被设计成允许未来加入其他的特性或形式，目前只为这样的形式实现了低级电路。
1. 代码与过程
初始化素数字段参数，R1P总是需要这么做。
initPublicParamsFromDefaultPp();
面包版是一个“内存管理器”，它维护所有的限制(当创建验证电路的时候)和变量赋值(当创建证明证人的时候)。我们特别说明这个R1P的类型，能在未来增加对BOOLEAN或GF2_EXTENSION字段的支持。
ProtoboardPtr pb = Protoboard::create(R1P);
现在我们创建三个输入和一个输出
VariableArray input(3, "input");
Variable output("output");
我们现在可以添加一些限制，其中字符串的目的是为了调试方便，并且能够给这个限制一个文本说明。
pb->addRank1Constraint(
input[0],
5 + input[2],
output,
"Constraint 1: input[0] * (5 + input[2]) == output"
);
第二种形式是添加一个一元限制，这个意味着(LinearCombination == 0)
pb->addUnaryConstraint(
input[1] - output,
"Constraint 2: input[1] - output == 0"
);
注意到这样写也是可以的：
pb->addRank1Constraint(1, input[1] - input[2], 0, "");
对于更加一般化形式的字段，可以一次性实现，我们可以使用addGeneralConstraint(Polynomial1, Polynomial2, string)会转换成(Polynomial1 == Polynomial2)限制。例如：
pb->addGeneralConstraint(
input[0] * (3 + input[1]) * input[2],
output + 5,
"input[0] * (3 + input[1]) * input[2] == output + 5"
);
现在我们能将值赋给变量了，并且看一看限制是否满足。之后，当我们运行SNARK(或者任何其他证明系统)的时候，这些限制将会被验证者(verifier)使用，并且指派的值被证明者(prover)使用。
注意到面包版(protoboard)存储了被指派的值。
pb->val(input[0]) =
pb->val(input[1]) =
pb->val(input[2]) =
pb->val(output) = 42;
EXPECT_FALSE(pb->isSatisfied());
这个限制系统是没有被满足的，现在让我们尝试一下可以满足上面两个等式的值。
The constraint system is not satisfied. Now let's try values which satisfy the two equations above:
pb->val(input[0]) = 1;
pb->val(input[1]) =
pb->val(output) = 42; // input[1]-output == 0
pb->val(input[2]) = 37; // 1*(5+37)==42
EXPECT_TRUE(pb->isSatisfied());
2. Gadget与非的例子
在上面的例子中，我们清晰的写了所有的限制和赋值。
在这个例子中，我们将构造一个非常简单的gadget，一个实现了与非(NAND)的门。这个gadget是字段无关的，因为它只使用了低级的gadget以及字段元素 '0' & '1'。
Gadget是一个允许我们委托复杂电路元件到低层的框架。依靠限定与赋值以及利用子gadget，每一个gadget能够构造一个限定系统或证明者，或是两者一起。。
1. 主过程
下面这个测试用来说明使用方法：
初始化字段
initPublicParamsFromDefaultPp();
用R1P系统的类型创建一个面包板。
ProtoboardPtr pb = Protoboard::create(R1P);
创建5个变量inputs[0]...inputs[4]。字符串“inputs”是调试信息。
FlagVariableArray inputs(5, "inputs");
FlagVariable output("output");
GadgetPtr nandGadget = NAND_Gadget::create(pb, inputs, output);
现在我们能生成一个限定系统(或电路)
nandGadget->generateConstraints();
如果我们现在尝试去计算这个电路，一个异常会被抛出来，因为我们企图计算没有赋值的变量。
EXPECT_ANY_THROW(pb->isSatisfied());
因此让我们对这个输入变量赋值，这么就可以进行与非(NAND)计算，并且在创建证据之后，再次尝试计算这个电路。
for (const auto& input : inputs) {
pb->val(input) = 1;
}
nandGadget->generateWitness();
EXPECT_TRUE(pb->isSatisfied());
EXPECT_TRUE(pb->val(output) == 0);
现在让我们毁坏某些东西，并看看发生了什么？
pb->val(inputs[2]) = 0;
EXPECT_FALSE(pb->isSatisfied());
现在让我们尝试欺骗一下。如果我们没有强制要求boolean化，这应该是能运行的。
pb->val(inputs[1]) = 2;
EXPECT_FALSE(pb->isSatisfied());
现在让我们重新设置inputs[1]为一个正确的值。
pb->val(inputs[1]) = 1;
之前我们设置了inputs和output。注意到output仍然是'0'。
// before, we set both the inputs and the output. Notice the output is still set to '0'
EXPECT_TRUE(pb->val(output) == 0);
现在我们将使gadget利用generateWitness() 创建证据计算出结果并且看发生了什么？
nandGadget->generateWitness();
EXPECT_TRUE(pb->val(output) == 1);
EXPECT_TRUE(pb->isSatisfied());
3. hash难度执行者例子
另外一个例子展示双重变量的使用。一个双重变量是一个具有下面两种特性的变量，字的安位表现形式，以及可包装的展现形式(例如，包装值 {42} 和非包装值 {1,0,1,0,1,0} )。如果这个字够短(比如，小于它主要特征的任何整数)，那么包装起来的表达方式将被存储在一个元素字段中。字在这个上下文中的意思是一组二进制位，这是一个惯例，意味着我们期待一些语义能力去分解包装的值到二进制位去。
使用双重变量是为了提高效率。更多的展示在例子的结尾。在这个例子中我们将构造一个gadget，这个gadget接收一个包装的整数作为输入称为'hash'，和一个二进制位的‘难度’级别，以及构造一个用来证明‘hash’上第一个‘难度’位是0的电路。为了简单，我们将假定‘hash’总是64位长度。
1. 主过程
记得我们指出，双重变量被用来提升效率。现在就是详细说明这个的时候。就像你看到的，我们需要一个位表达来检查hashValue的第一个位。但是hashValue可能被用于很多其他的地方，因为我们想要检查实例是否与另一个值相等。在包装的表达上检查相等会‘消耗’我们一个限定，当在没有包装的值上检查相等的时候，将‘消耗’我们64个限制。在ppzkSNARK证明系统中，这个转换会加重构造证明的时间和内存消耗。
initPublicParamsFromDefaultPp();
auto pb = Protoboard::create(R1P);
const MultiPackedWord hashValue(64, R1P, "hashValue");
const size_t difficulty = 10;
auto difficultyEnforcer = HashDifficultyEnforcer_Gadget::create(pb, hashValue, difficulty);
difficultyEnforcer->generateConstraints();
现在限制以及创建，但是还没有赋值。在计算是会抛出异常。
EXPECT_ANY_THROW(pb->isSatisfied());
pb->val(hashValue[0]) = 42;
difficultyEnforcer->generateWitness();
42的起始的10个位(当以64位数形式展示的时候)都是'0'，因此应该可以工作。
EXPECT_TRUE(pb->isSatisfied(PrintOptions::DBG_PRINT_IF_NOT_SATISFIED));
pb->val(hashValue[0]) = 1000000000000000000;
这个值大于2^54，因此我们期待限制系统不会被满足。
在断言之前，generateWitness应该就失败了。
difficultyEnforcer->generateWitness();
EXPECT_FALSE(pb->isSatisfied());
4. R1P验证交易金额例子
在这个例子中，我们将构造一个gadget，这个gadget构建了一个证明(证据)电路，并且认可(限制)一个比特币交易输入的数量必须等于输出+矿工费。证明的限制将包括找到矿工的费用。这个费用能够作为电路的输出被考虑。
这是特定领域的gadget，就像我们将要用的 '+'操作一样自由。在主特性领域而非在扩展领域，加法操作像所期望的一样工作在整数上。如果你不熟悉扩展领域，不用担心。应该简单的意识到 + 和 * 在不同的领域表现得不一样，并且不一定给出你期望的整数值。
由于要用到不同的场景下，这个库的设计支持多域构造。当其他的应用使用主要域的时候一些加密图应用可能需要扩展域，但是，用使用非rank-1的限制，并且有些可能还需要boolean电路。在新域或限制构造上，这个库的设计使高层次的gadget能够重用底层的实现。
之后通过使用不可知接口，我们将提供一个创建这种特殊领域gadget的诀窍。我们在这儿使用一些惯例，采用宏将这个过程变得容易。
1. Gadget定义
这是一个为所有的特定域创建一个继承自gadget接口类的宏。
惯用法是：class {GadgetName}_GadgetBase
CREATE_GADGET_BASE_CLASS(VerifyTransactionAmounts_GadgetBase);
注意这里的多继承。我们必须指定接口以及基础gadget的特殊域。这允许类工厂在编译期决定，特定的类需要为每个面包板实例化哪种域。可以在"gadget.hpp"中看到这个设计的信息。
惯用法：class {FieldType}_{GadgetName}_Gadget
#1: 我们给出工厂类的友元访问为了实例化私有的构造函数。
class R1P_VerifyTransactionAmounts_Gadget : public VerifyTransactionAmounts_GadgetBase,
public R1P_Gadget {
public:
void generateConstraints();
void generateWitness();
friend class VerifyTransactionAmounts_Gadget; // #1
private:
R1P_VerifyTransactionAmounts_Gadget(ProtoboardPtr pb,
const VariableArray& txInputAmounts,
const VariableArray& txOutputAmounts,
const Variable& minersFee);
void init();
const VariableArray txInputAmounts_;
const VariableArray txOutputAmounts_;
const Variable minersFee_;
DISALLOW_COPY_AND_ASSIGN(R1P_VerifyTransactionAmounts_Gadget);
};
使用宏CREATE_GADGET_FACTORY_CLASS_XX创建工厂类(用构造函数的参数数量替换XX，protoboard不算)。有时候我们像要多构造函数，可以参照AND_Gadget。在这个场景下，我们将手工写出工厂类。
CREATE_GADGET_FACTORY_CLASS_3(
VerifyTransactionAmounts_Gadget,
VariableArray, txInputAmounts,
VariableArray, txOutputAmounts,
Variable, minersFee
);
2. Gadget实现
为基类实现空析构函数
VerifyTransactionAmounts_GadgetBase::~VerifyTransactionAmounts_GadgetBase() {}
看起来下面这点实现就足够了，但是一个对抗者可能在域的模数上引起等式的一边溢出。事实上，对于每个输入/输出的和我们总是会找到一个矿工的服务费满足这个限制。只剩下一个给读者的练习，实现一个加法限制(和证据)，用来检查每个数量（输入，输出，费用）在0和21,000,000 * 1E8 中本村之间。用最大的输入/输出数量组合这个数防止域溢出。
提示：使用Comparison_Gadget创建gadget，这个gadget将一个变量的值与常数做比较。使用这些新gadget的数组去检查各自的值。
不要忘记：
- 在init()中连接这些gadgets。
- 在generateConstraints()中调用这些gadgets的限定。
- 在generateWitness()中调用这些gadgets的证据。
#1 注意我们必须初始化3个基类（菱形继承）
void R1P_VerifyTransactionAmounts_Gadget::generateConstraints() {
addUnaryConstraint(
sum(txInputAmounts_) - sum(txOutputAmounts_) - minersFee_,
"sum(txInputAmounts) == sum(txOutputAmounts) + minersFee"
);
}
void R1P_VerifyTransactionAmounts_Gadget::generateWitness() {
FElem sumInputs = 0;
FElem sumOutputs = 0;
for (const auto& inputAmount : txInputAmounts_) {
sumInputs += val(inputAmount);
}
for (const auto& outputAmount : txOutputAmounts_) {
sumOutputs += val(outputAmount);
}
val(minersFee_) = sumInputs - sumOutputs;
}
R1P_VerifyTransactionAmounts_Gadget::R1P_VerifyTransactionAmounts_Gadget(
ProtoboardPtr pb,
const VariableArray& txInputAmounts,
const VariableArray& txOutputAmounts,
const Variable& minersFee
):
Gadget(pb),
VerifyTransactionAmounts_GadgetBase(pb),
R1P_Gadget(pb), // #1
txInputAmounts_(txInputAmounts),
txOutputAmounts_(txOutputAmounts),
minersFee_(minersFee) {}
void R1P_VerifyTransactionAmounts_Gadget::init() {}
2. 主流程
按照约定，用不可知接口创建一个特定域gadgets的诀窍是：
-
用宏创建一个基类：
CREATE_GADGET_BASE_CLASS({GadgetName}_GadgetBase); -
为基类创建一个构造函数：
{GadgetName_Gadget}Base::~{GadgetName}_GadgetBase() {} -
使用多继承创建你需要的特定域gadgets。
class {FieldType}_{GadgetName}_Gadget :
public {GadgetName}_GadgetBase,
public {FieldType_Gadget}注意到为了使用工厂类宏，构造函数的所有参数必须是 const&。构造参数必须与所有的特定域实现一致。
-
给工厂类{GadgetName}_Gadget友元访问特定域类的权限。
-
采用宏创建工厂类。
CREATE_GADGET_FACTORY_CLASS_XX(
{GadgetName}_Gadget,
type1, input1, type2, input2, ... ,
typeXX, inputXX
);
void examples_r1p_verify_transaction_amounts() {
initPublicParamsFromDefaultPp();
auto pb = Protoboard::create(R1P);
const VariableArray inputAmounts(2, "inputAmounts");
const VariableArray outputAmounts(3, "outputAmounts");
const Variable minersFee("minersFee");
auto verifyTx = VerifyTransactionAmounts_Gadget::create(
pb,
inputAmounts,
outputAmounts,
minersFee
);
verifyTx->generateConstraints();
pb->val(inputAmounts[0]) = pb->val(inputAmounts[1]) = 2;
pb->val(outputAmounts[0]) =
pb->val(outputAmounts[1]) =
pb->val(outputAmounts[2]) = 1;
verifyTx->generateWitness();
EXPECT_TRUE(pb->isSatisfied());
EXPECT_EQ(pb->val(minersFee), 1);
pb->val(minersFee) = 3;
EXPECT_FALSE(pb->isSatisfied());
}
5. 整合gadgetlib2和ppzkSNARK
下面是一个整合gadgetlib2所构造的限制系统和ppzkSNARK的例子。
1. 主流程
initPublicParamsFromDefaultPp();
创建一个限制系统的例子，并翻译成libsnark的格式化。
const libsnark::r1cs_example<
libff::Fr<
libff::default_ec_pp
>
> example = libsnark::gen_r1cs_example_from_gadgetlib2_protoboard(100);
const bool test_serialization = false;
运行ppzksnark，跳转到分析函数。
const bool bit = libsnark::run_r1cs_ppzksnark<
libff::default_ec_pp
>(example, test_serialization);
EXPECT_TRUE(bit);
2. r1cs创建
限制系统在gen_r1cs_example_from_gadgetlib2_protoboard中创建，我们来看看里面的过程是什么。
注意：这个例子确实创建了一个限制，这个限制至少说明说明了QAP限制的健全性。
r1cs_example<
libff::Fr<
libff::default_ec_pp
>
>
gen_r1cs_example_from_gadgetlib2_protoboard(const size_t size)
{
typedef libff::Fr<libff::default_ec_pp> FieldT;
gadgetlib2::initPublicParamsFromDefaultPp();
必要的情况下，在之前就建立一个面包板，libsnark假定变量索引总是从0开始，因此我们必须在创建被libsnark使用的限制之前重设索引。
gadgetlib2::GadgetLibAdapter::resetVariableIndex();
创建一个gadgetlib2的gadget。这个部分靠生成器和证明器实现。
auto pb = gadgetlib2::Protoboard::create(gadgetlib2::R1P);
gadgetlib2::VariableArray A(size, "A");
gadgetlib2::VariableArray B(size, "B");
gadgetlib2::Variable result("result");
auto g = gadgetlib2::InnerProduct_Gadget::create(pb, A, B, result);
创建一个限制，这个部分靠生成器完成。
g->generateConstraints();
创建赋值(证据)。这个部分是证明者完成的。
for (size_t k = 0; k < size; ++k)
{
pb->val(A[k]) = std::rand() % 2;
pb->val(B[k]) = std::rand() % 2;
}
g->generateWitness();
将限制系统转换成libsnark格式。
r1cs_constraint_system<FieldT> cs =
get_constraint_system_from_gadgetlib2(*pb);
转换所有的变量的赋值到libsnark格式。
const r1cs_variable_assignment<FieldT> full_assignment =
get_variable_assignment_from_gadgetlib2(*pb);
提取主要的和辅助的输入
const r1cs_primary_input<FieldT> primary_input(
full_assignment.begin(),
full_assignment.begin() + cs.num_inputs()
);
const r1cs_auxiliary_input<FieldT> auxiliary_input(
full_assignment.begin() + cs.num_inputs(),
full_assignment.end()
);
assert(cs.is_valid());
assert(cs.is_satisfied(primary_input, auxiliary_input));
return r1cs_example<FieldT>(cs, primary_input, auxiliary_input);
}
3. 运行ppzksnark
下面的代码提供了一个以R1CS的形式运行ppzkSNARK的全场景的例子。
当然，在实际的情景中，我们有三个明显的实体，下面将乱入到一个演示实例中。这三种实体如下：
-
生成器：它运行ppzkSNARK生成器，输入一个给定的限制系统CS来创建一个证明过程和一个对于CS来说可验证的key。
-
证明者：运行ppzkSNARK的证明者，输入一个证明用的key。
-
验证者：运行ppzkSNARK验证者，输入一个可验证的key，一个CS的主输入，和一个证据。
template<typename ppT>
bool run_r1cs_ppzksnark(const r1cs_example<libff::Fr<ppT> > &example,
const bool test_serialization)
{
//libff::enter_block("Call to run_r1cs_ppzksnark");
//libff::print_header("R1CS ppzkSNARK Generator");
r1cs_ppzksnark_keypair<ppT> keypair =
r1cs_ppzksnark_generator<ppT>(example.constraint_system);
//printf("\n");
//libff::print_indent();
//libff::print_mem("after generator");
//libff::print_header("Preprocess verification key");
r1cs_ppzksnark_processed_verification_key<ppT> pvk =
r1cs_ppzksnark_verifier_process_vk<ppT>(keypair.vk);
if (test_serialization) {
//libff::enter_block("Test serialization of keys");
keypair.pk =
libff::reserialize<
r1cs_ppzksnark_proving_key<ppT>
>(keypair.pk);
keypair.vk =
libff::reserialize<
r1cs_ppzksnark_verification_key<ppT>
>(keypair.vk);
pvk =
libff::reserialize<
r1cs_ppzksnark_processed_verification_key<ppT>
>(pvk);
//libff::leave_block("Test serialization of keys");
}
//libff::print_header("R1CS ppzkSNARK Prover");
r1cs_ppzksnark_proof<ppT> proof =
r1cs_ppzksnark_prover<ppT>(
keypair.pk,
example.primary_input,
example.auxiliary_input
);
//printf("\n");
//libff::print_indent();
//libff::print_mem("after prover");
if (test_serialization)
{
//libff::enter_block("Test serialization of proof");
proof = libff::reserialize<
r1cs_ppzksnark_proof<ppT>
>(proof);
//libff::leave_block("Test serialization of proof");
}
//libff::print_header("R1CS ppzkSNARK Verifier");
const bool ans =
r1cs_ppzksnark_verifier_strong_IC<ppT>(
keypair.vk,
example.primary_input,
proof
);
//printf("\n");
//libff::print_indent();
//libff::print_mem("after verifier");
//printf("* The verification result is: %s\n", (ans ? "PASS" : "FAIL"));
//libff::print_header("R1CS ppzkSNARK Online Verifier");
const bool ans2 =
r1cs_ppzksnark_online_verifier_strong_IC<ppT>(
pvk,
example.primary_input,
proof
);
assert(ans == ans2);
test_affine_verifier<ppT>(
keypair.vk,
example.primary_input,
proof,
ans
);
//libff::leave_block("Call to run_r1cs_ppzksnark");
return ans;
}
译者总结：
结构图
