Доказательства с нулевым разглашением с использованием Bulletproofs

Доказательства с нулевым разглашением с использованием Bulletproofs

Здесь я покажу, как создавать различные доказательства с нулевым разглашением, используя Bulletproofs implementation из далек-криптографии. Примерами будут: i) доказательство знания факторов данного числа без раскрытия факторов, ii) доказательство диапазона, т. Е. Доказательство того, что вы знаете значение x такое, что a ≤ x ≤ b, не раскрывая x, iii) доказательство того, что значение у вас есть ненулевое значение, не раскрывая его (без использования вышеуказанного доказательства диапазона), iv) докажите, что значение не равно заданному значению, не раскрывая вашего собственного, v) установите членство, т. е. учитывая набор S, докажите, что вы знаете элемент, содержащийся в наборе, но не раскрывающий элемент, vi) Аналогичным образом установите непринадлежность, не раскрывая значения отсутствующего элемента. Примеры можно адаптировать с небольшими усилиями, чтобы их можно было использовать в реализациях ZK-SNARK, таких как libsnark или bellman. Чтобы напрямую просмотреть код, перейдите здесь.

Код в этом посте был отредактирован, дополнен дополнительными примерами и перенесен в новое репо.

Обзор

Я предполагаю, что вы уже знакомы с использованием арифметических схем для доказательства произвольных утверждений. Он был описан в нескольких статьях, но библиотека в этом посте рассказывает об этом, построенном на статье Эффективные аргументы с нулевым разглашением для арифметических схем в настройке дискретного журнала. Техника была сделана более эффективной с помощью Bulletproofs paper, и далек-криптография опубликовала свою реализацию этого. Идея состоит в том, чтобы представить утверждение в виде арифметической схемы, то есть набора уравнений, в которых разрешенными операторами являются сложение, вычитание и умножение, и преобразовать эти уравнения в систему ограничений ранга-1 (R1CS). Система ограничений - это набор арифметических ограничений по набору переменных. Чтобы узнать больше об этом процессе и R1CS, прочтите этот пост. Системы проверки, использующие R1CS, приобрели популярность в последнее время, причем ZK-SNARK является самой популярной из них. Недостатком ZK-SNARK является наличие надежной настройки, то есть одноразовой генерации параметров протокола, которая включает в себя знание или изучение некоторых секретов, которые могут быть использованы для нарушения гарантий протокола. Это сложно, поскольку теперь настройка должна выполняться таким образом, чтобы такие секреты не могли быть изучены (полностью), Zcash делает это с помощью многосторонних вычислений. Еще одна проблема заключается в том, что для каждой цепи необходимо выполнить надежную настройку, например. Если вы хотите доказать, что знаете два фактора, вам нужно сделать надежную настройку. Теперь, если вам нужно подтвердить знание трех факторов, вам нужно снова выполнить надежную настройку, поскольку ограничения изменились. Система R1CS, созданная с помощью Bulletproofs, не имеет надежной настройки, и, следовательно, можно избежать двух вышеуказанных проблем.

Идея высокого уровня этой системы доказательства состоит в том, что
1. Доказывающий принимает значение (я), знание о котором он хочет доказать. ценности и любые дополнительные общественные ценности. Ограничения могут потребовать, чтобы доказывающая сторона зафиксировала некоторые дополнительные переменные.
3. Проверяющая отправляет верификатору все обязательства, которые он принял на шаге 1 и шаге 2, вместе с доказательством из шага 2.
4. Проверяющий теперь проверяет доказательство, налагая те же ограничения на обязательства плюс любые общественные ценности.

Bulletproofs API

Давайте рассмотрим API Bulletproofs в контексте примера. Допустим, доказывающий хочет доказать знание множителей публичного числа 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 генераторов. Итого вы создаете 2 * 128 = 256 генераторов в bp_gens. 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 не интерактивна, проблемы генерируются эвристикой Fiat-Shamir, то есть хешированием текущего состояния стенограммы. 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);

Выше доказывающая сторона принимает фактор p, используя случайность x1 и 2 генератора g и h из pc_gens. Это обязательство Педерсена, отсюда com_p = gᵖhˣ¹. Аналогичным образом com_q является обязательством q с x2. Помимо создания обязательства, метод commit также создает соответствующие переменные для системы ограничений, var_p и var_q являются переменными для p и q соответственно. Кроме того, в протокол во времяcommit добавлены 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-переменной и o равно 0 Программа доказательства создает эту r-переменную, создавая линейное ограничение, то есть переменную, умноженную на скаляр. Кортеж (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()), (Variable::One(), r.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, как показано в примере ниже. Полный пример находится здесь.

Еще примеры

Доказательство диапазона
Чтобы доказать, что зафиксированное значение x удовлетворяет min ≤ x ≤ max для некоторых общедоступных min и 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, то есть v в [0, MAX_VALUE]. Если доказывающая сторона создала битовое представление v, а битовое представление содержало n битов, ясно, что v находится в [0, 2ⁿ). Как только доказывающая сторона создает этот 71_-битовый вектор, она все еще не может раскрыть этот битовый вектор верификатору, поскольку это будет v верификатору. Но если доказывающая сторона сможет доказать верификатору, что каждый элемент этого вектора действительно является битом и биты установлены по «правильному индексу», он может убедить верификатора, что v находится в диапазоне.
Произнесите n -битовый вектор [bₙ₋₁, bₙ₋₂,… b₁, b₀]. Чтобы доказать, что каждый bᵢ является битом, достаточно доказать, что 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));
}

В приведенном выше примере выполняется итерация по n битам v. cs - система ограничений. И проверяющий, и проверяющий из предыдущих примеров являются системами ограничений, и оба будут запускать вышеуказанный блок кода. allocate назначит 3 переменные, a, b и o с ограничением, которое a * b = o. Также переменным a и b присваиваются значения 1-bit и bit соответственно. Следовательно, для каждого бита bit из v ((q >> i) & 1 возвращает i младший значащий бит) доказывающая сторона будет соответствовать константе (1-bit)*bit=o и ограничит o равным 0 в cs.constrain(o.into()). Но если вы заметили, что закрытие, переданное в allocate, имеет доступ к значению v, чего не может быть в случае верификатора, и на самом деле это не так. Закрытие выполняется только для проверяющего, а не для проверяющего. Но это означает, что можно присвоить произвольные значения a и b, поскольку только o ограничено равным 0, например, a = 3 и b = 0 по-прежнему приводят к a * b = 0. Таким образом, требуется дополнительное ограничение, которое a = 1 - b = ›_ 98_
Приведенный выше пример доказывает, что элемент вектора является битом, но все же не доказывает, что бит-вектор предназначен для v. например, указанная выше система ограничений будет удовлетворена для всех нулей или всех единиц, но это может быть неправильным представлением v. Нам нужно больше ограничений, чтобы доказать, что битовый вектор предназначен для v.

pub fn positive_no_gadget<CS: ConstraintSystem>(
    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 является оболочкой над зафиксированной переменной. Полный код находится здесь.
Теперь мы можем использовать приведенный выше 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ⁿ). Полный код находится здесь.

pub fn bound_check_gadget<CS: ConstraintSystem>(
    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(())
}

Доказательство того, что зафиксированное значение не равно нулю

Часто возникает необходимость доказать, что какое-то значение не равно нулю, не раскрывая его, а только фиксируя его, мы увидим его использование в доказательстве отсутствия принадлежности к множеству ниже. Другое использование - доказательство того, что какое-то значение не равно определенному значению, поскольку для доказательства того, что x не равно c, достаточно доказать, что x-c не равно 0.
Доказательство основано на следующем наблюдении (не моя). Допустим, вы хотите доказать, что x не равно 0. Вычислите обратное значение x, назовите это inv. Пусть y = if x!=0 then 1 else 0. inv = 0, если x = 0, иначе _138 _ = _ 139_⁻¹. Теперь выполняются следующие 2 уравнения
i) x * (1-y) = 0
ii) x * inv = y
Доказывающий сначала фиксирует как 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: ConstraintSystem>(
    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(())
}

Обратите внимание, что первые 2 ограничения cs.constrain(o1.into()) и cs.constrain(o2 — y_lc) соответствуют двум приведенным выше уравнениям, но есть третье ограничение, которое проверяет, действительно ли inv является обратным x. Это необходимо, поскольку доказывающая сторона передает только обязательства x и inv (x⁻¹) проверяющей, а доказывающая сторона может обмануть, давая не обратное, а какое-то другое значение. Таким образом, проверяющий удостоверяется, что inv на самом деле обратное. Полный код находится здесь.

Доказательство того, что зафиксированное значение не равно заданному значению

Доказать, что ваше значение v не равно заданному c, то же самое, что доказать, что
v — c != 0. Итак, мы используем указанное выше is_nonzero_gadget. Полный код находится здесь.

Установить отказ от членства

Доказывающему может потребоваться доказать, что его совершенная ценность не лежит в наборе, например. Скажем, существует общедоступный набор S как [2, 9, 78, 44, 55] и подтвержденное значение проверяющего v равно 12, он не хочет, чтобы проверяющий знал, что его значение равно 12, а только то, что его значение отсутствует в наборе . Идея состоит в том, что доказывающий может вычесть свое значение из каждого элемента набора и доказать, что каждый результат не равен нулю, то есть S[i] — v != 0 для каждого индекса набора i. Таким образом, доказывающий сначала принимает свое значение, затем фиксирует разницу между каждым элементом набора и его значением, а также обратное значение каждой разницы, всего 2*n+1 обязательств, где n - количество элементов в наборе. Обязательство обратного разности необходимо, чтобы доказать, что разница не равна нулю, как показано в предыдущем примере.

let mut comms: Vec<CompressedRistretto> = vec![];
let mut diff_vars: Vec<AllocatedScalar> = vec![];
let mut diff_inv_vars: Vec<AllocatedScalar> = 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: ConstraintSystem>(
    cs: &mut CS,
    v: AllocatedScalar,
    diff_vars: Vec<AllocatedScalar>,
    diff_inv_vars: Vec<AllocatedScalar>,
    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(())
}

Обратите внимание, что в приведенных выше ограничениях, помимо ненулевых ограничений, существует дополнительное ограничение для каждого элемента набора. Это ограничение необходимо для того, чтобы доказывающая сторона использовала один и тот же v в S[i] — v != 0 для каждого индекса набора i. Это делается путем создания переменной для v-S[i] и добавления ее к указанной выше разнице и ограничения результата до 0. Полный код находится здесь.

Установить доказательство членства

Доказывающему может потребоваться доказать, что его переданное значение лежит в наборе S, но без раскрытия его значения v. Это идея (взята из репозитория ethsnarks)
1. Прувер создает бит-вектор, соответствующий набору, с 1 битом на элемент набора. Все биты равны 0.
2. Проверяющий устанавливает бит в битовом векторе по индексу своего значения v. например. если установлено S было [5, 9, 1, 100, 200], а значение доказывающего элемента было 100, бит-вектор будет [0, 0, 0, 1, 0].
3. Затем доказывающий доказывает, что < br /> i) фактически каждый элемент битового вектора является битом,
ii) в битовом векторе установлен только 1 бит путем сложения всех битов и доказательства, что сумма равна 1.
iii) для каждого набора индекса i это соотношение выполняется set[i] * bitvec[i] = bitvec[i] * v. Это должно сохраняться, поскольку bitvec[i] равно 0 для всех i, кроме индекса v.

Программа доказательства сначала создает битовый вектор и фиксирует каждый бит.

let bit_map: Vec<u64> = 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);
}

Чтобы доказать, что какое-то значение является битом, используется bit_gadget, который основан на этом соотношении bit*(1-bit)=0.

pub fn bit_gadget<CS: ConstraintSystem>(
    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: ConstraintSystem>(
    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.

Теперь доказывающая программа удовлетворяет конечному результату отношения set[i] * bitvec[i] = bitvec[i] * v, фиксируя значение и используя уже выделенные переменные для принятого битового вектора bit_vars.

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());

vector_product_gadget

// Ensure items[i] * vector[i] = vector[i] * value
pub fn vector_product_gadget<CS: ConstraintSystem>(
    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, равно значению заданного элемента по этому индексу. Полный код находится здесь.
Существует альтернативный способ подтверждения членства в множестве. Он основан на этой идее: если элемент присутствует в наборе, то вектор, построенный путем взятия разности каждого элемента набора и этого элемента, будет содержать 1 нулевое значение. Итак, если мы умножим все элементы этого нового вектора, произведение будет 0. Доказывающая фиксирует значение и его разницу с каждым элементом набора и вызывает новый гаджет членства в наборе set_membership_1_gadget

let (com_value, var_value) = prover.commit(value.clone(), Scalar::random(&mut rng));
let alloc_scal = AllocatedScalar {
    variable: var_value,
    assignment: Some(value),
};
comms.push(com_value);

for i in 0..set_length {
    let elem = Scalar::from(set[i]);
    let diff = elem - value;

    // 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);
}

assert!(set_membershiprgadget(&mut prover, alloc_scal, diff_vars, &set).is_ok());

В set_membership_1_gadget произведение элементов diff_vars ограничено равным 0. Полный код находится здесь.

pub fn set_membershiprgadget<CS: ConstraintSystem>(
    cs: &mut CS,
    v: AllocatedScalar,
    diff_vars: Vec<AllocatedScalar>,
    set: &[u64]
) -> Result<(), R1CSError> {
    let set_length = set.len();
    // Accumulates product of elements in `diff_vars`
    let mut product: LinearCombination = Variable::One().into();

    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);

        let (_, _, o) = cs.multiply(product.clone(), diff_vars[i].variable.into());
        product = o.into();
    }

    // Ensure product of elements if `diff_vars` is 0
    cs.constrain(product);

    Ok(())
}

Получайте лучшие предложения по программному обеспечению прямо в свой почтовый ящик