Greetings! New to Zcash?
The Zcash network is young, but evolving quickly! Sign up and we'll be in touch with more information about how you can get started with Zcash!

言語

Bellman: Rustにおけるzk-SNARKs

Sean Bowe | Apr 04, 2017

Bellman とはRust言語のライブラリであり、zk-SNARKsの構築に使用されます — 小規模で、検証が安価にできる任意の計算の ゼロ知識証明 です。Bellmanの目的とは、一般の人々によるzk-SNARKsの試験的な使用を容易にすることと、Zcashの次のメジャーリリース Sapling のセキュリティと性能の向上に進み出ることです。

Bellmanに、数週間前に ご説明した 楕円曲線 BLS12-381 の構築が含まれました。これは、弊社所属の研究者が上梓する次の研究論文に掲載されます。この構築は、高いセキュリティ境界を維持しながらzk-SNARKsを効率的に組み立てるために設計されたものです。

今週、私はJens Groth氏によって設計された 新zk-SNARK証明システム の初期実装を追加しました。一般的なグループモデルとして、この新しいデザインは小さな証明を作成するため、少ないメモリでより迅速に構築が可能です。

zk-SNARKs概要

zk-SNARKs 内部動作の仕組みにご関心がある場合は、Ariel Gabizonが基本的計算について書いている ブログ記事シリーズ をご確認ください。現在のところ、表面的なレベルで記事を理解することができます。

zk-SNARKs は、他のゼロ知識証明方式とは異なり、証明される記述が大規模で複雑だとしても、非常に小規模(数百バイト)で検証コストを抑えた(数ミリ秒)強力な証明となります。ゼロ知識の特性により、証明者は、プロセスで使用される計算の詳細を検証者に知られないようにできるため、プライバシーとパフォーマンスの両方に役立ちます。

効率的であるとし知られている唯一の方法は、前処理 です。ある意味、前処理とは証明者が記述を評価し証明できる「環境」を構築する必要があると言えます。虚偽の証明を作成できる情報を一時的に保有する必要なく、このような環境を構築する方法はありません。

トランザクションをシールドするためにzk-SNARKsを使用するZcashは、本記事 で読むことができる洗練された分散計算法により作成されたパラーメーターを使用します。また、zk-SNARKsは、指定された検証者モデルに役立ちます。その理由は、検証者自身が必要なパラメーターを作成するため、証明者も検証者も整合性について気にする必要がないからです。

zk-SNARKの多くの方式で証明される記述は、ランク1二次制約システム、または R1CS と呼ばれるものに縮小されます。このシステムでは、変数セット(大規模な主要フィールドを構成する要素 \(\mathbb{F}_r\))に算術的な制約をするシステムが証明者に提供され、制約を満たす変数の割り当てが要求されます。

Bellmanの概要

Bellmanは現在、初期段階ですが、すでに証明を作成するために使用できます。現在、極めて低レベルの API のみ利用可能です。サーキットを合成するためにDSLやさまざまなアブストラクションを構築することができます。試してみたい場合は、 crates.ioからBellman crate を実行してください。

すべてのサーキットのアブストラクションは、一般的に楕円曲線と有限体演算方法を処理するエンジンの特性により記述されます。サーキットの合成は、制約システムの特性を中心としています。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
 pub trait ConstraintSystem<E: Engine> {
/// / 制約システムにプライベート変数を割り当て
/// その変数を指定値に設定する。
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>
);
}

設計に関して重要な選択事項が2つあります。

すべての変数の割り振り、割り当て、制約の実行は、同じコードパスで行われます。これは、分離されていることで簡単に制約を忘れたり、既存のアブストラクションにあるバグに気付かない可能性があるため、libsnark のガジェットライブラリの設計と異なります。このアプローチによって、アブストラクションの作成やコードの見直しが簡単になります。 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
 // 証明キーと検証キーを作成
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)
};

// 証明を作成
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()
};

// 検証キーを準備
let pvk = groth16::prepare_verifying_key(e, &vk);

// 証明を検証
assert!(groth16::verify(e, |cs| {
DummyInput
}, &proof, &pvk));

今後の業務

これら低レベルの基礎部分のすべては、現在Bellmanで利用可能です。今後、ハッシュ関数やストリーム暗号のようなものを構築するツールを開発する予定です。

Bellmanは、いまだ開発中のため生産ソフトウェアで使用しないでください。実際に、BellmanのAPIは、使用可能な機能を故意に表示しません。現在、Bellmanは、zk-SNARKsを安全かつ効率的に構築する方法を学ぶ素晴らしい機会としての役割を果たしています。Bellmanを使って構築することで、Zcashの将来像を知ることができます。

また、Rust言語でBellmanの記述のすばらしさを実感しています。Rustacean、zk-SNARKs、またはZcashにご関心がある場合、弊社のプロジェクトコミュニティチャット、および以前にRust言語で記述された 分散計算法のコード などをご覧になることをおすすめします。

Rust, cryptography, zkSNARKs | 全てのタグを見る