nonnative
v0.3.0
nonnative библиотека предоставляет ограничения R1CS для проверки вычислений над неродным полем в системе доказательства.
Библиотека основана на платформе написания ограничений arkworks-rs и распространяется под лицензией MIT и лицензией Apache v2 (см. Лицензию).
ВНИМАНИЕ: Это академический прототип, подтверждающий концепцию; в частности, он не прошел тщательную проверку кода. Эта реализация НЕ готова к использованию в производстве.
Эта библиотека реализует гаджет поля для простого поля Fp над другим простым полем Fq , где p != q .
При написании систем ограничений для многих криптографических доказательств мы ограничены собственным полем (например, скалярным полем кривой, благоприятной для спаривания). Это может быть неудобно; например, рекурсивная композиция доказательств с помощью циклов кривых требует, чтобы проверяющий выполнял вычисления над неродным полем.
Библиотека позволяет записывать вычисления над неродным полем так же, как если бы они записывали вычисления над собственным полем. Это, естественно, приводит к дополнительным накладным расходам, которые мы минимизируем с помощью различных оптимизаций.
Поскольку неродное поле реализует признак FieldVar в arkworks, мы можем обращаться с ним как с нативной переменной поля ( FpVar ).
Мы можем выполнять стандартные операции с полями, такие как + , - и * . См. следующий пример:
let a = NonNativeFieldVar :: < Fr , Fq > :: new_witness ( ns ! ( cs, "a" ) , || Ok ( a_value ) ) ? ;
let b = NonNativeFieldVar :: < Fr , Fq > :: new_witness ( ns ! ( cs, "b" ) , || Ok ( b_value ) ) ? ;
// add
let a_plus_b = & a + & b ;
// sub
let a_minus_b = & a - & b ;
// multiply
let a_times_b = & a * $b ;
// enforce equality
a . enforce_equal ( & b ) ? ; После каждого умножения наша библиотека внутренне выполняет операцию сокращения , которая сводит промежуточный тип NonNativeFieldMulResultVar к нормализованному типу NonNativeFieldVar . Это позволяет пользователю беспрепятственно выполнять последовательность операций, не беспокоясь о базовых деталях.
Однако эта операция дорогостоящая, и иногда ее можно избежать. Мы можем уменьшить количество ограничений, используя этот промежуточный тип, который поддерживает только дополнения. Для умножения его необходимо снова уменьшить до NonNativeFieldVar . Ниже приведен пример скелета.
Чтобы вычислить a * b + c * d , простая (но более дорогая) реализация выглядит следующим образом:
let a_times_b = &a * &b;
let c_times_d = &c * &d;
let res = &a_times_b + &c_times_d;
Всего выполняется две операции сокращения , по одной для каждого умножения.
Мы можем сохранить одно сокращение, используя NonNativeFieldMulResultGadget следующим образом:
let a_times_b = a.mul_without_reduce(&b)?;
let c_times_d = c.mul_without_reduce(&d)?;
let res = (&a_times_b + &c_times_d)?.reduce()?;
Он выполняет только одну операцию сокращения и примерно в 2 раза быстрее, чем первая реализация.
Библиотека использует стандартную идею использования нескольких конечностей для представления элемента целевого поля. Например, элемент в TargetField может быть представлен тремя элементами BaseField (т. е. конечностями).
TargetField -> limb 1, limb 2, and limb 3 (each is a BaseField element)
После некоторых вычислений конечности перегружаются, и их необходимо сокращать , чтобы участвовать в дальнейших вычислениях.
Мы активно используем методы оптимизации из [KPS18] и [OWWB20]. Обе работы имеют собственные библиотеки с открытым исходным кодом: xJsnark и bellman-bignat. По сравнению с ними, эта библиотека работает со средой arkworks, а также оптимизирована по плотности, а не количеству ограничений, что полезно для голографических доказательств с нулевым разглашением, таких как Marlin.
Библиотека лицензируется по одной из следующих лицензий на ваше усмотрение.
Если вы явно не указали иное, любой вклад, представленный вами для включения в эту библиотеку, должен иметь двойную лицензию, как указано выше (как определено в лицензии Apache v2), без каких-либо дополнительных положений и условий.
[KPS18]: А.Э. Косба, К. Папаманту и Э. Ши. «xJsnark: структура для эффективных проверяемых вычислений», в Proceedings of the 39th Symposium on Security and Privacy , сер. S&P '18, 2018 г., стр. 944–961.
[OWWB20]: А. Оздемир, Р. С. Вахби, Б. Уайтхет и Д. Боне. «Масштабирование проверяемых вычислений с использованием эффективных аккумуляторов наборов», в Proceedings of the 29th USENIX Security Symposium , сер. Безопасность '20, 2020.
