您好!刚知道Zcash吗?
The Zcash network is young, but evolving quickly! Sign up and we'll be in touch with monthly highlights on ecosystem growth, network development and how to get started with Zcash!

语言

Bellman: zk-SNARKs 在 Rust 语言中的应用

Sean Bowe | Apr 04, 2017

Bellman 是 Rust 语言中用于建立 zk-SNARKs 的程序库 — 它的特点是小型化,廉价验证随机计算的 零知识证明 。Bellman 的目标是让普通大众更加简单地使用 zk-SNARKs,同时也为了提升 Zcash 的下一个 树苗 版本的安全性和性能。

Bellman 包含一套 BLS12-381 椭圆曲线的建造和实现方法,我们已经在几周之前对其进行了 阐述,它也将出现在我们的科学家未来发布的文章中。这个建造方法在设计时特别考虑了在特定的安全边界中 zk-SNARK 的建造效率问题。

这一周,我已经添加了由 Jens Groth 设计的 新 zk-SNARK 验证系统 的原始实现方法。这一方法被通用组模型所保护,新的设计产生更小的证明这使得证明的建造过程更加迅速并且消耗更小的内存。

zk-SNARK 的概述

如果你对 zk-SNARKs 的内部工作原理感兴趣,可以查看 Ariel Gabizon 在 系列博文 中撰写的 zk-SNARKs 背后的基础数学。现在我们可以从表层先开始理解它。

zk-SNARKs 是功能强大的证明,它的验证设计不同于一般的零知识证明。即便被验证的声明体积大而且复杂,zk-SNARKs 的体积较小 (大约为几百字节) 并且验证较为廉价(大约为几毫秒)。它的零知识特性允许验证器隐藏一些计算过程的细节,因此他们既可以保护隐私又有良好的性能。

在一般的方案中,被公认为更有效率的方式是 预处理。在某种意义上,这种方法需要某一种 环境 必须被提前建立,这个环境将被验证器用来评估声明并产生证明。但是,目前并没有一种方法允许在不获得信息的前提下建造所需的环境,而这种做法会导致建造错误的证明。

Zcash 的遮蔽地址使用 zk-SNARKs。Zcash 使用的参数由一个设计精妙的多重计算仪式生成,您可以在 这里 了解仪式的细节。zk-SNARKs 同样适用于指定验证器模型,在这个模型中验证器自身建立需要的参数,因此验证方和验证器都无需考虑它的诚信度。

在很多的 zk-SNARK 方案中,被验证的声明被削减为所谓的 秩-1 二次约束系统,或被称为 R1CS。在这类系统中,验证方被填加了有一系列由变量(在大素域 \(\mathbb{F}_r\) 中的元素)产生的算法限制,并被要求按照限制对变量进行赋值操作。

Bellman 的概述

Bellman 目前正处于它的婴儿期,但是我们已经可以使用它来建立各种类型的证明。当前,可用的 API 的使用等级很悠闲,我们仅能通过它来建造 DSLs 和不同的合成环路。如果你想要用它来做一些实验,可以在 bellman 板条箱 crates.io 中获取。

我们所有的环路抽象一般会基于引擎的特性来撰写,它被用于处理椭圆曲线和有限域计算。环路分析的中心点是约束系统特性:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
pub trait ConstraintSystem<E: Engine> {
    /// Allocate a private variable in the constraint system, setting it to
    /// the provided value.
    fn alloc(&mut self, value: E::Fr) -> Variable;

    /// Enforce that `A` * `B` = `C`.
    fn enforce(
        &mut self,
        a: LinearCombination<E>,
        b: LinearCombination<E>,
        c: LinearCombination<E>
    );
}

在这里有两个重要的设计抉择:

  1. 所有变量的分配,赋值和约束加强在相同的代码路径被处理。这与 libsnark 针对 gadgetlib 的设计有所不同,在 libsnark 的设计中,由于路径的分离,太容易忘记在当前抽象中存在的约束和一些明显的 bug。而这一方法使得撰写抽象和进行代码审阅更加的简便。
  2. 所有的变量分配和赋值是同时进行的,而当前存在的赋值过程无法被查询和修饰。当前的现状激发了更好的工具设计,并且防止工具被赋值过程无用来互相 “沟通”。这一方式有一个性能上的优势:由于所有的变量已经被赋值,在验证过程中的约束加强被直接合成进了潜在的作证人中,从而避免了作证人始终需要牢记约束系统。

作为一类工具实现的例子,这里列出了布尔变量约束是如何使用 XOR 进行实现的:

 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
#[derive(Clone)]
pub struct Bit {
    var: Variable,
    value: bool
}

impl Bit {
    pub fn alloc<E, CS>(e: &E,
                        cs: &mut CS,
                        value: bool) -> Bit
        where E: Engine, CS: ConstraintSystem<E> + ?Sized
    {
        // Allocate the variable
        let var = cs.alloc(
            if value { E::Fr::one(e) } else { E::Fr::zero() }
        );

        // Enforce (1 - var) * var = 0, which requires
        // var to be either 0 or 1
        cs.enforce(
            LinearCombination::one(e) - var,
            LinearCombination::zero(e) + var,
            LinearCombination::zero(e)
        );

        Bit {
            var: var,
            value: value
        }
    }

    pub fn xor<E, CS>(&self,
                      e: &E,
                      cs: &mut CS,
                      other: &Bit) -> Bit
        where E: Engine, CS: ConstraintSystem<E>
    {
        let new_value = self.value ^ other.value;
        let new_var = cs.alloc(
            if new_value { E::Fr::one(e) } else { E::Fr::zero() }
        );

        // 2a * b = a + b - c
        cs.enforce(
            LinearCombination::zero(e) + self.var + self.var,
            LinearCombination::zero(e) + other.var,
            LinearCombination::zero(e) + self.var + other.var - new_var
        );

        Bit {
            var: new_var,
            value: new_value
        }
    }
}

建立一个环路是实现 环路输入 特性的问题:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
pub trait Circuit<E: Engine> {
    type InputMap: Input<E>;
    fn synthesize<CS: ConstraintSystem<E>>(self,
                                           engine: &E,
                                           cs: &mut CS)
                                           -> Self::InputMap;
}

pub trait Input<E: Engine> {
    fn synthesize<CS: PublicConstraintSystem<E>>(self, engine: &E, cs: &mut CS);
}

设计将环路拆分为单个 环路 来实现,这将允许证明人将建造证明的过程实例化;并且拆分为单个 输入 来实现,它将被证明者和验证者使用并进行输入分配和相关环路的合成。这与 libsnark 不同,这些代码的路径是冗余的,并且它们使用了不同的效用函数并需要仔细的代码校对来保持一致性。

当我们真正有 环路输入 实现的时候,我们就能够使用在 groth16 中的功能:创建一个秘钥对 (同时随机选择一些陷阱门),建立证明并执行验证:

 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
// Create a proving key and verifying key
let (pk, vk) = {
    let tau = E::Fr::random(e, rng);
    let alpha = E::Fr::random(e, rng);
    let beta = E::Fr::random(e, rng);
    let gamma = E::Fr::random(e, rng);
    let delta = E::Fr::random(e, rng);
    let c = DummyCircuit;

    groth16::keypair(e, c, &tau, &alpha, &beta, &gamma, &delta)
};

// Construct a proof
let proof = {
    let r = E::Fr::random(e, rng);
    let s = E::Fr::random(e, rng);

    let c = DummyCircuit;

    groth16::prove(e, c, &r, &s, &pk).unwrap()
};

// Prepare the verifying key
let pvk = groth16::prepare_verifying_key(e, &vk);

// Verify proof
assert!(groth16::verify(e, |cs| {
    DummyInput
}, &proof, &pvk));

未来的工作

这个低等级的基础是 Bellman 目前所拥有的一切。在未来,我们将为其撰写工具,这将允许我们建立哈希函数和序列密码。

Bellman 仍在开发之中,当前并不能被用于软件茶品中。事实上,它的 API 并不会有意地暴露任何可能被人使用它的要素。当前,它的角色是安全高效地建立 zk-SNARKs 的绝好的学习机会,我们从中学到的只是将被用于未来更好地塑造 Zcash。

我们同样激动地将 Bellman 编写如 Rust!如果你是一个 Rustacean,并且对 zk-SNARKs 或 Zcash 感兴趣,我们邀请你查看 我们的项目,加入 社区聊天室 或我们之前在 Rust 中编写的多样的内容,比如 多方计算仪式的代码

Rust, cryptography, zkSNARKs | 查看所有标签