Wire 是证明向量中的一个元素。一个 Expression<F> 是线性的 Wire 组合。

BooleanWire 是一种经过约束的 Wire，其只能等于 0 或 1。同样地，一个 BooleanExpression<F> 是一种经过相应约束的 Expression<F>。

BinaryWire 是 BooleanWire 的向量。同样地，一个 BinaryExpression<F> 是 BooleanExpression<F> 的向量。

基本示例

这是一个简单的计算 BN128 字段元素立方的 gadget

// Create a gadget which takes a single input, x, and computes x*x*x.
let mut builder = GadgetBuilder::<Bn128>::new();
let x = builder.wire();
let x_exp = Expression::from(x);
let x_squared = builder.product(&x_exp, &x_exp);
let x_cubed = builder.product(&x_squared, &x_exp);
let gadget = builder.build();

// This structure maps wires to their (field element) values. Since
// x is our input, we will assign it a value before executing the
// gadget. Other wires will be computed by the gadget.
let mut values = values!(x => 5u8.into());

// Execute the gadget and assert that all constraints were satisfied.
let constraints_satisfied = gadget.execute(&mut values);
assert!(constraints_satisfied);

// Check the result.
assert_eq!(Element::from(125u8), x_cubed.evaluate(&values));

这也可以通过 builder.exp(x_exp, 3) 来更简洁地完成，它通过平方取幂进行指数运算。

自定义字段

您可以通过实现 Field 特性来自定义一个字段。例如，以下是上述提到的 Bn128 的定义

pub struct Bn128 {}

impl Field for Bn128 {
    fn order() -> BigUint {
        BigUint::from_str(
            "21888242871839275222246405745257275088548364400416034343698204186575808495617"
        ).unwrap()
    }
}

加密工具

假设我们想要对 Expression 的向量进行哈希处理。一种方法是将块加密算法如 MiMC 转换为使用 Davies-Meyer 构造的单向压缩函数，然后使用 Merkle-Damgård 构造将其转换为哈希函数。我们可以这样做

fn hash<F: Field>(
    builder: &mut GadgetBuilder<F>,
    blocks: &[Expression<F>]
) -> Expression<F> {
    let cipher = MiMCBlockCipher::default();
    let compress = DaviesMeyer::new(cipher);
    let hash = MerkleDamgard::new_defaults(compress);
    hash.hash(builder, blocks)
}

排列网络

为了验证两个列表是彼此的排列，您可以使用 assert_permutation。这是通过 AS-Waksman 排列网络实现的，它使用大约 n log_2(n) - n 个开关来排列 n 个项目。每个开关涉及两个约束：一个“是布尔值”检查和一个路由约束。

排列网络使实现排序 gadget 变得很容易，我们以 sort_ascending 和 sort_descending 的形式提供了这些 gadget。

非确定性

假设我们希望计算字段元素 x 的乘法逆。虽然这可以在确定性算术中完成，但成本过高。我们可以做的是让用户计算 x_inv = 1 / x，将结果作为证明元素提供，并在 R1CS 实例中添加一个约束来验证 x * x_inv = 1。

GadgetBuilder 通过其 generator 方法支持此类非确定性计算，如下所示

fn inverse<F: Field>(builder: &mut GadgetBuilder<F>, x: Expression<F>) -> Expression<F> {
    // Create a new witness element for x_inv.
    let x_inv = builder.wire();

    // Add the constraint x * x_inv = 1.
    builder.assert_product(&x, &Expression::from(x_inv),
                           &Expression::one());

    // Non-deterministically generate x_inv = 1 / x.
    builder.generator(
        x.dependencies(),
        move |values: &mut WireValues<F>| {
            let x_value = x.evaluate(values);
            let x_inv_value = x_value.multiplicative_inverse();
            values.set(x_inv, x_inv_value);
        },
    );

    // Output x_inv.
    x_inv.into()
}

这大致相当于内置的 GadgetBuilder::inverse 方法，略有修改以提高可读性。

后端

可以使用 r1cs-zkinterface crate 将这些 gadget 导出为标准 zkinterface 格式。

通过bellman的r1cs-bellmancrate，还有一个直接的 后端。

免责声明

此代码尚未经过彻底审查或测试，不应在生产系统中使用。