Приветствуем! Впервые на сайте 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-SNARK на языке Rust

Sean Bowe | Apr 04, 2017

Bellman это библиотека на языке Rust для построения zk-SNARK — маленьких, недорогих для проверки доказательств с нулевым разглашением произвольных вычислений. Цель bellman сделать проще для широкой публики использование zk-SNARK и эксперименты с ними, а также он является шагом вперед для улучшения безопасности и производительности следующего большого релиза Zcash, Дерево.

Bellman содержит реализацию конструкции эллиптических кривых BLS12-381 которую мы описали пару недель назад, и которая будет представлена в новой работе наших учёных. Эта конструкция была построена для того, чтобы эффективно строить zk-SNARK, для поддержания высокого уровня безопасности.

На этой неделе я добавил реализацию примитивов новой системы проверки zk-SNARK разработанной Йенсом Гротом. Безопасная в универсальной модели группы, новая конструкция производит меньшие по размерам доказательства, которые могут быть построены быстрее и с меньшими требованиями к памяти.

Обзор zk-SNARK

Если вас интересует, как zk-SNARK работает внутри, Ариэль Габизон написал серию постов в блог о лежащей в основе математике, которые вы должны проверить! На данный момент мы можем понять их на поверхностном уровне.

zk-SNARK это сильные доказательства, которые, в отличие от других схем доказательства нулевого разглашения, очень маленькие (пара сотен байт) и недорогие для проверки (несколько миллисекунд), даже если доказываемое утверждение большое и сложное. Их собственность нулевого знания позволяет проверяющему скрывать детали вычисления от проверяемого, таким образом это полезно как для приватности, так и для производительности.

Единственными такими схемами, о которых известна их эффективность, были схемы препроцессинга. В некотором смысле, это своего рода "окружающая среда", которая должна быть построена, чтобы программа проверки смогла оценить заявление и проверить доказательство. Нет никакого известного способа построить такую окружающую среду без обязательного временного владения информацией, которая могла бы вам позволить построить ложные доказательства.

Zcash, который использует zk-SNARK для своих скрытых транзакций, использует параметры, созданные во время сложной, из нескольких частей, церемонии вычисления, о которой вы можете прочесть здесь. zk-SNARK также полезны в выбранной модели проверки, где проверяющий сам строит необходимые параметры, и таким образом ни проверяющий ни проверяемый не затрагивают целостности.

Во многих схемах zk-SNARK, доказательство для проверяющего сокращается до того, что называют -1 разрядной квадратичной ограничительной системой, или R1CS. В этой системе проверяющий получает систему арифметических ограничений по ряду переменных (элементы в большой главной области \(\mathbb{F}_r\)), и просит назначить переменные, которые удовлетворяют этим ограничениям.

Обзор Bellman

Bellman сейчас находится в очень юном возрасте, но мы уже можем использовать его для построения этих видов доказательств. В настоящее время доступен только API очень низкого уровня, на котором мы можем построить DSL и различные абстракции для синтезирования схем. Если вы хотите экспериментировать с ним, возьмите программный пакет bellman с crates.io.

Все наши абстракции схем написаны, используя эллиптические кривые и арифметику конечного поля. Главная черта при синтезе схем это ConstraintSystem:

 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, для которой было слишком легко забыть ограничения или заметить ошибки в существующих абстракциях из-за разделения. Этот подход делает проще написание абстракций и выполнение обзора кода.
  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-SNARK безопасно и эффективно, и уроки, которые мы извлекаем из этого строительства, будут формировать будущее Zcash.

Мы взволнованы возможностью написать Bellman на языке Rust! Если вы разработчик на Rust и вас интересуют zk-SNARK или Zcash, мы приглашаем вас проверить наш проект, присоединиться к нашему чату сообщества или посмотреть на различные вещи, которые мы писали на языке Rust раньше, такие, как наша церемония вычисления из нескольких частей.

Rust, cryptography, zkSNARKs | Просмотреть все тэги