如何使用dalek-cryptography中的Bulletproofs实现（Bulletproofs implementation）[1]创建各种零知识证明。示例为i）证明自己知道给定数字的因数而不披露该因数，ii）范围证明，即证明自己知道能使a≤x≤b的x值，而不披露x，iii）证明该x值非零并不披露（而且不使用上面的范围证明），iv）集合的包含证明，即给定一个集合S，证明自己知道集合中的一个元素而不披露该元素，v）类似的，集合的不包含证明，且不披露非成员元素的值。这些示例可以轻松调整，以便用于诸如libsnark、bellman等的ZK-SNARK实现。浏览代码，请转至此[2]。
概述
大概各位已经可以纯熟利用运算电路来证明任意语句了。有关零知识证明，在很多文献中都有描述，本文则主要基于“对离散对数设定中运算电路的高效零知识论证（Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting）[3]”这篇。这个技能后来被Bulletproofs论文（Bulletproofs paper）[4]进一步完善，随后dalek-cryptography也发布了它们对此的实现（implementation）[1]。想法是将语句表示成一个运算电路，即一组方程，允许的运算符是加法、减法和乘法，并将这些方程转换为Rank-1约束系统（R1CS）。约束系统指针对一组变量的运算限定。想要了解此过程或者R1CS的更多信息，参阅此文章（post）[5]。利用了R1CS的证明系统最近是越来越受欢迎了，最火的当属ZK-SNARKs。不过，ZK-SNARK有个缺点是必须要有可信设置，即一次性的协议参数生成，这就涉及秘密一旦被知晓，就有可能被用来破坏协议的保证。所以说，设置的过程需要以一种‘秘（密）而不宣（相对的）’的方式进行，这就难了。不过在这一点上，Zcash采用了多方计算的对策。可信设置还有一个问题就是必须为每个电路分别完成设置，譬如，现在想证明自己知道2个因数，首先得有一个可信设置。后来，想证明知道3个因数，还得再来一遍可信设置，因为约束（条件）变了。使用Bulletproofs构建的R1CS系统则不需要这种可信设置，因此避免了上述2个问题。
这种证明系统的高层概念包括：
1. 证明人提交一（多）个值，证明自己知道这个值。
2. 证明人通过对提交值与其他公共值实施约束（条件）生成证明。这些约束可能要求证明人提交其他变量。
3. 证明人向验证人发送其在步骤1、步骤2中的所有提交以及步骤2中的证明。
4. 验证人通过对提交与其他公共值实施相同的约束（条件）加来验证此证明。
Bulletproofs API
我们用示例探索下Bulletproofs API。
假设证明人想要证明自己知道公共数字r的因数。证明人知道因数p和q，但是验证人不知道。因此，证明人为语句p*q=r创建证明，其中证明人和验证人都知道r，但是只有证明人知道p和q。
1. 创建一些证明人与验证人都可以使用的生成器。
let pc_gens = PedersenGens::default();
let bp_gens = BulletproofGens::new(128, 1);
上面的代码创建了2组生成器，pc_gens是一对（2个）的生成器，bp_gens是一对（2个）生成器向量（列表）。参数128表明每个向量有128个生成器。所以，bp_gens中一共创建了2*128=256个生成器。pc和bp分别代表Pedersen和Bulletproofs。
2. 证明人实例化。
let mut prover_transcript = Transcript::new(b"Factors");
let mut prover = Prover::new(&bp_gens, &pc_gens, &mut prover_transcript);
prover_transcript指证明人抄本，记录了证明人与验证人之间交换的各种消息，譬如证明人向验证人发送的提交或是验证人向证明人发送的挑战。由于这种Bulletproofs实现是非交互式的，所以由菲亚特 - 沙米尔启发式算法生成挑战，即对抄本的当前状态做哈希。Factors是该记录的标签，用来在协议有了子协议的时候区分各种不同的抄本或者子抄本。
3. 证明人提交变量。
let x1 = Scalar::random(&mut rng);
let (com_p, var_p) = prover.commit(p.into(), x1);
let x2 = Scalar::random(&mut rng);
let (com_q, var_q) = prover.commit(q.into(), x2);
证明人使用随机x1与pc_gens的两个生成器g、h提交因数p。这就是Pedersen提交，因此com_p = gᵖhˣ¹。类似地，com_q是用x2对因数q的提交。除了创建提交，提交方法还为约束系统创建了相应的变量，var_p和var_q分别为p和q的变量。此外，提交期间，有2个提交被添加至记录中。
4. 证明人约束变量。
let (_, _, o) = prover.multiply(var_p.into(), var_q.into());
证明人使用multiply函数规定变量var_p与var_q相乘，并将结果捕获在变量o中。此函数也会将对应于var_p、var_q和o的变量进行分配。另外，multiply还会评估输入变量，约束其等于相应的分配变量。
let r_lc: LinearCombination = vec![(Variable::One(), r.into())].iter().collect();
prover.constrain(o - r_lc);
现在证明人想要让p和q的乘积等于r。由于p和q的变量乘积，即var_p和var_q被变量o捕获，证明人可以为r分配一个变量，然后确保r-variable与o相减得0。证明人通过创建一个线性约束，即变量乘以标量，的方式来创建这个r-variable。（Variable::One(), r.into()）元组代表了值等于r的线性约束，即使用值为1的变量（Variable::One()）乘以标量r。若证明人想要创建一个值为p+q+r的变量，可以对要相加的向量做vec![(Variable::One(), (p+q+r).into())]或vec![(Variable::One(), p.into()), (Variable::One(), q.into())。
由于线性组合可以通过彼此相加或相减的方式得出另一个线性组合，因此证明人需要确保线性组合o -lc为0，这一步通过调用constrain来完成。constrain方法确保了传给自己的线性组合等于0。
5. 证明人创建证明。
let proof = prover.prove().unwrap();
6. 验证人实例化。
let mut verifier_transcript = Transcript::new(b"Factors");
let mut verifier = Verifier::new(&bp_gens, &pc_gens, &mut verifier_transcript);
验证人再此被实例化，同时创建出自己的抄本。注意，该抄本的名称与证明人示例中（的抄本名称）相同。这一点非常重要，因为名称属于抄本内容的一部分，而证明人与验证人之间的挑战是要对抄本内容做哈希的。所以说，名称不同意味着抄本内容不同，那么证明人和验证人之间的挑战也会不同，最终导致证明验证失败的情形。
7. 验证人使用提交。
let var_p = verifier.commit(commitments.0);
let var_q = verifier.commit(commitments.1);
验证人记录下证明人在抄本中发送的p、q提交，并为这些提交创建变量，（创建变量）这一点跟证明人是相似的。 不同之处在于证明人可以访问提交的值和随机性，验证人则不能。
8. 验证人约束变量。
let (_, _, o) = verifier.multiply(var_p.into(), var_q.into());
let r_lc: LinearCombination = vec![(Variable::One(), r.into())].iter().collect();
verifier.constrain(o - r_lc);
与证明人类似，验证人也会约束与提交相对应的变量。注意，这里的约束条件与证明人处的完全相同的。
9. 最后，验证人验证证明。
verifier.verify(&proof) ;
这个例子少了一个用来确保p和q都不为1（除非r为1）的约束（条件），可以使用范围证明（就是贵点）或直接证明不等于1（见下面的示例）来完成。 完整的示例就在这里（here）[6]。
其他示例
1. 范围证明
为了证明对于某个公共的min与max，提交的值x满足min≤x≤max，证明人必须满足2个声明：x≥min和x≤max。x≥min相当于证明 x-min≥0；x≤max相当于证明max-x≥0。现在，对于证明人来说，有某个提交v。v≥0时，证明人可以同时证明x-min≥0且max-x≥0，并提交x-min和max-x。现在我们专心证明v≥0且小于最大允许值，避免某些已提交v会溢出，即[0, MAX_VALUE]中的v。证明人创建了v的位表示且该位表示包含n位时，显然v在[0, 2ⁿ)中。 一旦证明人创建了这个n位向量，仍无法向验证人披露这个位向量，因为对于验证人来说就是个v。 但是若证明人可以向验证人证明该向量的每个元素确实都是1位，并且这些位设置在“正确的索引”处，就能说服验证人v在范围内。
假设n位向量为[b₋₁, b₋₂,…b₁, b₀]。要证明每个b都是1位，证明出b*(1-b)=0即可。下面的代码就是这个意思。
for i in 0..n {
// Create low-level variables and add them to constraints（创建低级变量并添加至约束函数）
let (a, b, o) = cs.allocate(|| {
let q: u64 = v.assignment.ok_or(R1CSError::MissingAssignment)?;
let bit: u64 = (q >> i) & 1;
Ok(((1 - bit).into(), bit.into(), Scalar::zero()))
})?;
// Enforce a * b = 0, so one of (a,b) is zero
cs.constrain(o.into());
// Enforce that a = 1 - b, so they both are 1 or 0.
cs.constrain(a + (b - 1u64));
}
上面的例子遍历了v的n位。cs是约束系统。前面示例中的证明人和验证人都是约束系统，而且都会运行上述代码块。allocate分配3个变量a、b和o，约束条件为a*b=o。另外，变量a和b分别赋值1－bit和bit。因此，对于v的每个bit位【(q>>i)&1返回第i个最低有效位】，证明人都满足约束(1-bit)*bit=o，并在cs.constrain(o.into())中将o约束为0。但是，有没有注意到传递给allocate的闭包能够访问v的值，要知道这个值是不能被验证人访问的，对吧？不用担心，闭包仅对证明人执行，不对验证人执行。 但这也意味着可以为a和b赋任意值，因为只有o被约束为0，好比a=3，b=0时，a*b仍等于0。所以，就需要有个另外的约束条件a=1-b => cs.constrain（a+（b-1u64））。
上面的例子能证明向量的元素是一个位，但仍未能证明位向量是v的。也就是说，全0或全1都能满足上述约束系统，但仍不能正确表示v。所以，需要更多的约束来证明位向量是v的。
pub fn positive_no_gadget(
cs: &mut CS,
v: AllocatedQuantity,
n: usize
,) -> Result<(), R1CSError> {
let mut constraint_v = vec![(v.variable, -Scalar::one())];
let mut exp_2 = Scalar::one();
for i in 0..n {
// Create low-level variables and add them to constraints
let (a, b, o) = cs.allocate(|| {
....
})?;
// Enforce a * b = 0, so one of (a,b) is zero
// Enforce that a = 1 - b, so they both are 1 or 0.
....
constraint_v.push((b, exp_2) );
exp_2 = exp_2 + exp_2;
}
// Enforce that -v + Sum(b_i * 2^i, i = 0..n-1) = 0 => Sum(b_i * 2^i, i = 0..n-1) = v
cs.constrain(constraint_v.iter().collect());
Ok(())
}
我们从constraint_v的向量开始，负v是第一项。然后，对于v的每个位，我们将该位乘以2的适当幂，并将结果添加到constraint_v.push((b,exp_2))中的上述线性组合。最后将线性组合的所有项的求和会得到0。cs.constrain(constraint_v.iter().collect())的意思是将constraint_v中的所有项相加，确保和为0。AllocatedQuantity类型是提交的包装器变量。完整的代码在这里（here）[7]。
现在可以使用上面的positive_no_gadget来证明x-min和max-x都在[0, 2ⁿ)中。记住，证明人在这一步仍然可以作弊。 由于证明人只是给出x-min和max-x的提交，那么他完全可以在提交中使用不同的x，这么一来，一个提交超过了x-min，而另一个超过max-y。为了防止这一点，需要确保将两个提交值相加会得到max-min。设a=x-min，b=max-x。证明人提交v、a和b。
let (com_v, var_v) = prover.commit(v.into(), Scalar::random(&mut rng));
let quantity_v = AllocatedQuantity {
variable: var_v,
assignment: Some(v),
};
let (com_a, var_a) = prover.commit(a.into(), Scalar::random(&mut rng));
let quantity_a = AllocatedQuantity {
variable: var_a,
assignment: Some(a),
};
let (com_b, var_b) = prover.commit(b.into(), Scalar::random(&mut rng));
let quantity_b = AllocatedQuantity {
variable: var_b,
assignment: Some(b),
};
证明人为v、a和b传递变量至bound_check_gadget，这个函数确保v在[min，max]中。然后，证明人创建证明。
assert!(bound_check_gadget(&mut prover, quantity_v, quantity_a, quantity_b, max, min, n).is_ok());
let proof = prover.prove()?;
bound_check_gadget确保a+b=max-min，且a和b都在[0, 2ⁿ)中。完整的代码在这里（here）[8]。
pub fn bound_check_gadget(
cs: &mut CS,
v: AllocatedQuantity,
a: AllocatedQuantity,
b: AllocatedQuantity,
max: u64,
min: u64,
n: usize
) -> Result<(), R1CSError> {
// a + b = max - min
let lc_max_minus_min: LinearCombination = vec![(Variable::One(), Scalar::from(max-min))].iter().collect();
// Constrain a + b to be same as max - min.
cs.constrain(a.variable + b.variable - lc_max_minus_min);
// Constrain a in [0, 2^n)
assert!(positive_no_gadget(cs, a, n).is_ok());
// Constrain b in [0, 2^n)
assert!(positive_no_gadget(cs, b, n).is_ok());
Ok(())
}
2. 证明提交值非零
需要证明某些值非零但是又不能披露只能做提交的情形也还蛮常见。下面的集合非成员资格的证明中就会看到这种操作。还有一种用法是证明某个值不等于某个特定值，因为证明了x不等于c，便足以证明x-c不等于0。
证明基于以下（不是我的）观察。假设要证明x不等于0。计算出x的倒数，称其为inv。设y = if x!=0 then 1 else 0。当x=0时，inv=0 else inv=x⁻¹。 现在，下面2个方程式成立：
i) x*(1-y) = 0
ii) x*inv = y
首先，证明人提交x和x的倒数inv，然后满足上述2个约束。
let (com_val, var_val) = prover.commit(value.clone(), Scalar::random(&mut rng));
let alloc_scal = AllocatedScalar {
variable: var_val,
assignment: Some(value),
};
let inv = value.invert();
let (com_val_inv, var_val_inv) = prover.commit(inv.clone(), Scalar::random(&mut rng));
let alloc_scal_inv = AllocatedScalar {
variable: var_val_inv,
assignment: Some(inv),
};
assert!(is_nonzero_gadget(&mut prover, alloc_scal, alloc_scal_inv).is_ok());
以下为约束条件：
pub fn is_nonzero_gadget(
cs: &mut CS,
x: AllocatedScalar,
x_inv: AllocatedScalar,
) -> Result<(), R1CSError> {
let y: u32 = 1;
let x_lc: LinearCombination = vec![(x.variable, Scalar::one())].iter().collect();
let one_minus_y_lc: LinearCombination = vec![(Variable::One(), Scalar::from(1-y))].iter().collect();
let y_lc: LinearCombination = vec![(Variable::One(), Scalar::from(y))].iter().collect();
// x * (1-y) = 0
let (_, _, o1) = cs.multiply(x_lc.clone(), one_minus_y_lc);
cs.constrain(o1.into());
// x * x_inv = y
let inv_lc: LinearCombination = vec![(x_inv.variable, Scalar::one())].iter().collect();
let (_, _, o2) = cs.multiply(x_lc.clone(), inv_lc.clone());
// Output wire should have value `y`
cs.constrain(o2 - y_lc);
// Ensure x_inv is the really the inverse of x by ensuring x*x_inv = 1
let (_, x_inv_var, o3) = cs.multiply(x_lc, inv_lc);
// Output wire should be 1
let one_lc: LinearCombination = vec![(Variable::One(), Scalar::one())].iter().collect();
cs.constrain(o3 - one_lc);
Ok(())
}
注意前两个约束条件cs.constrain(o1.into())和cs.constrain(o2 — y_lc)对应上面的2个等式，但是还有个检查inv是否为x倒数的第三个约束条件。这个条件是很必要的，因为证明人只向验证人提供了x和inv（x-1）的提交，并且证明人可以通过提供非inv的其他值舞弊。因此验证人确保该inv是真的。 完整的代码在这里（here）[9]。
3. 集合非会员（不包含）证明
证明人需要证明自己提交的值不在集合中，譬如，假设有个公共集合S，长这样[2,9,78,44,55]，证明人提交的值v为12，而且不想告诉验证人知道这个值是12，所以需要证明这个值不在集合中。
想法是证明人可以用集合中的每个元素中减去他的值并证明每个减法结果都是非零的，即对于每个集合索引i，S[i]-v！=0。所以，证明人首先提交自己的值，然后提交每个集合元素与自己值的差，以及每个差的倒数。一共2*n+1个提交，其中n代表集合中的元素数量。 提交差值的倒数用来证明差值是非零的，如前面的例子所示。
let mut comms: Vec = vec![];
let mut diff_vars: Vec = vec![];
let mut diff_inv_vars: Vec = vec![];
let (com_value, var_value) = prover.commit(value.clone(), Scalar::random(&mut rng));
let alloc_scal = AllocatedScalar {
variable: var_value,
assignment: Some(value),
};
for i in 0..set_length {
let elem = Scalar::from(set[i]);
let diff = elem - value;
let diff_inv = diff.invert();
// Take difference of set element and value, `set[i] - value`
let (com_diff, var_diff) = prover.commit(diff.clone(), Scalar::random(&mut rng));
let alloc_scal_diff = AllocatedScalar {
variable: var_diff,
assignment: Some(diff),
};
diff_vars.push(alloc_scal_diff);
comms.push(com_diff);
// Inverse needed to prove that difference `set[i] - value` is non-zero
let (com_diff_inv, var_diff_inv) = prover.commit(diff_inv.clone(), Scalar::random(&mut rng));
let alloc_scal_diff_inv = AllocatedScalar {
variable: var_diff_inv,
assignment: Some(diff_inv),
};
diff_inv_vars.push(alloc_scal_diff_inv);
comms.push(com_diff_inv);
}
assert!(set_non_membership_gadget(&mut prover, alloc_scal, diff_vars, diff_inv_vars, &set).is_ok());
随后，在以下约束条件中使用对应上述提交的变量
pub fn set_non_membership_gadget(
cs: &mut CS,
v: AllocatedScalar,
diff_vars: Vec,
diff_inv_vars: Vec,
set: &[u64]
) -> Result<(), R1CSError> {
let set_length = set.len();
for i in 0..set_length {
// Take difference of value and each set element, `v - set[i]`
let elem_lc: LinearCombination = vec![(Variable::One(), Scalar::from(set[i]))].iter().collect();
let v_minus_elem = v.variable - elem_lc;
// Since `diff_vars[i]` is `set[i] - v`, `v - set[i]` + `diff_vars[i]` should be 0
cs.constrain(diff_vars[i].variable + v_minus_elem);
// Ensure `set[i] - v` is non-zero
is_nonzero_gadget(cs, diff_vars[i], diff_inv_vars[i])?;
}
Ok(())
}
注意，上述约束条件中，除了非零约束之外，还要对每个集合元素单独约束。 这个单独的约束是为了确保对于每个集合索引i，证明在S[i]-v！=0中都使用了相同的v。具体来说，就是为v-S[i]创建一个变量并将其添加到上面的差，使得约束结果为0。完整代码在这里（here）[10]。
4. 集合会员（包含）证明
证明人有可能需要证明自己提交的值v在集合S中，但不披露具体的v值。想法是这个样子的（摘自ethsnarks repo[11]）：
1. 证明人创建一个集合S的位向量，集合中的每个元素都是1位。所有位都是0。
2. 证明人将位向量中的位设为v值的索引，譬如，集合S为[5, 9, 1, 100, 200]，证明人的v值为100，则位向量为[0, 0, 0, 1, 0]。
3. 证明人证明：
i) 位向量的每个元素都是1位。
ii) 将所有位相加位，位向量中只有1个位组，并证明和为1。
iii) 对于每个集合索引i，关系始终为set[i]*bitvec[i]=bitvec[i]*value。等式应该会成立，因为除了值的索引之外，所有i的bitvec[i]都为0。
首先，证明人创建位向量并提交每个位。
let bit_map: Vec = set.iter().map( | elem | {
if *elem == value { 1 } else { 0 }
}).collect();
let mut comms = vec![];
let mut bit_vars = vec![];
for b in bit_map {
let (com, var) = prover.commit(b.into(), Scalar::random(&mut rng));
let quantity = AllocatedQuantity {
variable: var,
assignment: Some(b),
};
assert!(bit_gadget(&mut prover, quantity).is_ok());
comms.push(com);
bit_vars.push(quantity);
}
为证明某个值是1位，使用基于bit*(1-bit)=0的bit_gadget。
pub fn bit_gadget(
cs: &mut CS,
v: AllocatedQuantity
) -> Result<(), R1CSError> {
let (a, b, o) = cs.allocate(|| {
let bit: u64 = v.assignment.ok_or(R1CSError::MissingAssignment)?;
Ok(((1 - bit).into(), bit.into(), Scalar::zero()))
})?;
// Variable b is same as v so b + (-v) = 0
let neg_v: LinearCombination = vec![(v.variable, -Scalar::one())].iter().collect();
cs.constrain(b + neg_v);
// Enforce a * b = 0, so one of (a,b) is zero
cs.constrain(o.into());
// Enforce that a = 1 - b, so they both are 1 or 0.
cs.constrain(a + (b - 1u64));
Ok(())
}
注意，需要cs.constrain(b + neg_v)来确保证明人为变量b赋的值与v中提交的值相同。
现在，证明人通过对向量求和并将结果与1进行比较，确保向量中只1个位组。
assert!(vector_sum_gadget(&mut prover, &bit_vars, 1).is_ok());
以下是个可以用来比对给定向量之和与给定值的通用向量求和工具。
// Ensure sum of items of `vector` is `sum`
pub fn vector_sum_gadget(
cs: &mut CS,
vector: &[AllocatedQuantity],
sum: u64
) -> Result<(), R1CSError> {
let mut constraints: Vec<(Variable, Scalar)> = vec![(Variable::One(), -Scalar::from(sum))];
for i in vector {
constraints.push((i.variable, Scalar::one()));
}
cs.constrain(constraints.iter().collect());
Ok(())
}
注意，线性组合constraints的第一项为负，sum以及该线性组合所有项的和被约束为0。现在，证明人提交值并使用为已提交位向量bit_vars分配的变量来满足最终乘积关set[i]*bitvec[i]=bitvec[i]*value。
let (com_value, var_value) = prover.commit(value.into(), Scalar::random(&mut rng));
let quantity_value = AllocatedQuantity {
variable: var_value,
assignment: Some(value),
};
assert!(vector_product_gadget(&mut prover, &set, &bit_vars, &quantity_value).is_ok());
The vector_product_gadget
// Ensure items[i] * vector[i] = vector[i] * value
pub fn vector_product_gadget(
cs: &mut CS,
items: &[u64],
vector: &[AllocatedQuantity],
value: &AllocatedQuantity
) -> Result<(), R1CSError> {
let mut constraints = vec![(value.variable, -Scalar::one())];
for i in 0..items.len() {
let (a, b, o) = cs.allocate(|| {
let bit: u64 = vector[i].assignment.ok_or(R1CSError::MissingAssignment)?;
let val = value.assignment.ok_or(R1CSError::MissingAssignment)?;
Ok((items[i].into(), bit.into(), (bit*val).into()))
})?;
constraints.push((o, Scalar::one()));
let item_var: LinearCombination = vec![(Variable::One(), items[i].into())].iter().collect();
cs.constrain(a - item_var);
// Each `b` is already constrained to be 0 or 1
}
// Constrain the sum of output variables to be equal to the value of committed variable
cs.constrain(constraints.iter().collect());
Ok(())
}
注意约束条件cs.constrain(a — item_var)。 验证人确保证明人为变量a赋的值等于该索引处集合项的值。 完整的代码在这里（here）[12]。
相关链接：
[1]https://github.com/dalek-cryptography/bulletproofs
[2]https://github.com/lovesh/bulletproofs/blob/range-proof/tests
[3]https://eprint.iacr.org/2016/263
[4]https://eprint.iacr.org/2017/1066.pdf
[5]https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649
[11]https://github.com/HarryR/ethsnarks/blob/master/hide/gadgets/one_of_n.hpp
转载：https://blog.csdn.net/shangsongwww/article/details/100892149