您好!刚知道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!

语言

BLS12-381: 新 zk-SNARK 椭圆曲线的构造

Sean Bowe | Mar 11, 2017

我们的团队始终致力于提升我们 隐私交易 的安全性,稳定性和可用性。再我们之前的博文 近期的工作重点 中,我们正在对 Zcash 的下个版本"树苗"做许多密码学方面的提升和改进。我们的目标之一是使得隐私支付更有效率并且需要占据的内存更少。我们同样想要提升椭圆曲线建造的安全性,我们使用它来建立 zk-SNARK 证明。

The BLS12-381 curve.

在上个月,我花费了一些时间设计并建立了一个更易于配对的椭圆曲线的建立方法,它将使 zk-SNARKs 优化到 128 位的安全等级。这个建造过程将使用性的损耗降到了最低,同时提升了安全边界。

这项建造技术将在我们科学家的学术论文中做出讨论,论文中会详细描述建造过程和如何进行选择。

Barreto-Naehrig 曲线

Barreto-Naehrig (BN) 曲线是一簇 易于配对 的椭圆曲线,它建造在 \(r\)\(\mathbb{F}_q\) 域下,此时有 \(r \approx q\) 。我们当前的曲线建造有 \(r \approx q\)。 在去年,Kim 和 Barbulescu 展示了 一种数域筛选算法,它按保守估计 [1] 可以减小安全等级至 110 比特,这一观点来自 近期论文

根据这项保守的估计,通过选择一条近似于 \(q \approx 2^{384}\) 的曲线,并建造一个新的 BN 曲线并且有 128 位比特的安全等级是有可能的。然而,更大的 \(r\) 阶数影响了多重乘方的性能,快速傅里叶变换以及其他的密码学操作,我们需要提升 zk-SNARK 的性能和多重计算。除此之外,更大规模的 \(\mathbb{F}_r\) 使得重要文献不必要的增大了。

Barreto-Lynn-Scott 曲线

Barreto-Lynn-Scott (BLS) 曲线是稍有些古老的友好配对曲线,在实现这个等级的安全性方面很有优势。当前的研究建议在使用 \(q \approx 2^{384}\) 和 12 的包埋度的情况下,曲线可以达到 128 比特的安全等级。便利地,这一簇曲线的阶数是 \(r \approx 2^{256}\),他允许我们避免在大规模使用中的性能局限性。

BLS12-381

在 zk-SNARK 方案中,我们需要控制和修改标量场 \(\mathbb{F}_r\) 中巨大的多项式。我们可以使用快速傅里叶变换来提升效率,只要我们能够保证 \(\mathbb{F}_r\) 中包含一个 \(2^s\) 的整数根。

通常,我们将这些曲线的子集定位为优化扩充域塔和简单扭转重构。为了保证蒙哥马利剑法和其他的近似算法是有空间效率的,我们定位 \(r \approx 2^{255}\) 由此,最明确的 \(r\) (和 \(q\)) 的比特是 64 位的形式。

通常情况下,为了优化配对性能,我们需要保证 BLS 曲线参数有低的 Hamming 重量。我们最终选择的曲线是 BLS12-381 同样被称为 \(q \approx 2^{381}\)

u = -0xd201000000010000
k = 12
q = 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687 629129015664037894272559787
r = 52435875175126190479447740508185965837690552500527637822603658699938581184513
E(Fq) := y^2 = x^3 + 4
Fq2 := Fq[i]/(x^2 + 1)
E'(Fq2) := y^2 = x^3 + 4(i + 1)

Rust 语言的实现

我将实现 Rust 语言作为我 zk-SNARK 项目 传达员 工作的一部分。资料库的设计目标是可以更加便捷,标准兼容化和更高的使用性能。由于 zk-SNARK 设计的特性,在恒定的时间内高效率的建造证明是困难的,因此当前的资料库设计并没有关注与侧通道阻力。

未来的博文中将讨论我们的科学家在优化 Zcash 的曲线建造时所使用的技术和工具。

[1]在 Menzes, Sarkar 和 Singh (http://eprint.iacr.org/2016/1102.pdf) 的这篇文章中,他们指出 2^110 时空间多项式阶数的保守估计。然而,对于在 BN 曲线中常见的 q=p^12 情况,目前并没有扫描这个空间有效的方式。(分别检查每一个多项式将导致运行时间超过 2^128)。因此,我们所了解到的当前最有效率的方式是 Zcash 所使用的 Pollard's rho,它可以实时地运行 sqrt(q)~2^127。(感谢 Palash Sankar 和 Shashank Singh 来帮助我们理解这些结果)。

cryptography, zkSNARKs | 查看所有标签