非原生域设备

nonnative 库提供了一种在证明系统中检查非原生域上计算的R1CS约束。

该库基于约束编写框架 arkworks-rs，并使用MIT许可证和Apache v2许可证发布（见许可证）。

警告：这是一个学术性的概念原型；特别是，它尚未经过仔细的代码审查。此实现尚未准备好用于生产。

概述

该库实现了在另一个素域 Fq 上定义的素域 Fp 的域设备。

在编写许多密码证明的约束系统时，我们受限于原生域（例如，配对友好曲线的标量域）。这可能不方便；例如，通过曲线循环的递归组合证明需要验证者在非原生域上计算。

该库使得能够在与原生域相同的方式下编写非原生域上的计算。这自然引入了额外的开销，我们通过各种优化来最小化这些开销。

用法

因为非原生域在arkworks中实现了 FieldVar 特性，我们可以将其视为原生域变量（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)?;

高级优化

在每个乘法之后，我们的库内部执行一个 reduce 操作，将中间类型 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;

这总共进行了两次 reduce 操作，每个乘法一次。

我们可以通过使用 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()?;

它只执行一个 reduce 操作，比第一个实现快大约 2 倍。

灵感和基本设计

该库采用使用多个 limbs 来表示目标字段元素的常规想法。例如，TargetField 中的一个元素可能由三个 BaseField 元素表示（即 limbs）。

TargetField -> limb 1, limb 2, and limb 3 (each is a BaseField element)

经过一些计算后，limbs 变得过多，需要 reduced，以便进行更多计算。

我们大量使用了 [KPS18] 和 [OWWB20] 中的优化技术。这两项工作都有自己的开源库：xJsnark 和 bellman-bignat。与它们相比，此库与 arkworks 环境一起工作，并且也针对密度进行了优化，而不是约束的数量，这对于像 Marlin 这样的全息零知识证明很有用。

许可证

根据您的意愿，该库受以下任一许可证的许可。

• Apache 许可证版本 2.0（LICENSE-APACHE 或 http://www.apache.org/licenses/LICENSE-2.0）
• MIT 许可证（LICENSE-MIT 或 http://opensource.org/licenses/MIT）

除非您明确声明，否则您提交给此库的任何贡献都应双重许可，如上所述（如 Apache v2 许可证中定义），而不附加任何其他条款或条件。

参考文献

[KPS18]: A. E. Kosba, C. Papamanthou, 和 E. Shi. "xJsnark: 一个高效的验证计算框架," 在 第 39 届安全与隐私研讨会，S&P '18，2018 年，第 944-961 页。

[OWWB20]: A. Ozdemir, R. S. Wahby, B. Whitehat 和 D. Boneh. "使用有效的集合累积器扩展验证计算," 在 第 29 届 USENIX 安全研讨会，Security '20，2020 年。