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

语言

培育树苗:全新加密基础

Sean Bowe | Jul 26, 2017

Zcash 下一个主要协议升级,代号为 树苗 (Sapling),将对我们的 隐秘交易 性能,安全性以及可用性进行一些改进。这是一系列博客文章中的第一篇,将探索在树苗发展过程中取得的进展。

BLS12-381:一条全新的 zk-SNARK 曲线

目前 Zcash 中使用的 zk-SNARKs 算法依赖于 libsnark 库内部实现的 Barreto-Naehrig 椭圆曲线结构,且该椭圆曲线对配对操作友好,这是由我们的科学家很多年前设计实现的。在此之后,Kim–Barbulescu 对数字域筛选算法的优化将这条曲线的猜想安全级别降低到大约 110 位,尽管根据目前的研究,该曲线具体的安全级别仍然保持在原先预期的 128 位左右。

作为一个额外的预防措施,我们借此机会在树苗升级阶段中更新我们的椭圆曲线。今年早些时候,我提出了一条新的曲线,称之为 BLS12-381 。这条曲线的目标安全性是 128 位,它使用了最近几篇论文中提出的更为保守的建议。

现在已有一个该曲线的 Rust 语言 实现 版本。该实现版本具有强大的内存安全保证,因为它没有使用任何 unsafe{} 的代码或者是汇编级别的优化。尽管是一条更大的曲线,这个新的实现比我们目前在 Zcash 中使用的 BN254 更加高效。

Pairing crate benchmarks

速度的提升在椭圆曲线配对与 \(\mathbb{G}_2\) 算术过程中尤为明显,这提高了 zk-SNARK 证明与验证阶段的性能。

全新多指数(multi-exponentiation)算法

创建一个 zk-SNARK 证据最耗时的部分是对椭圆曲线群 \(\mathbb{G}_1\)\(\mathbb{G}_2\) 上的大多项式(指多项式项数很多)的评估,这通过一个称为多指数的算法来完成,该算法本质是通过将大指数向量 \(\vec{s}\) 驻留在内存中以及位于 zk-SNARK 证明密钥内部的大底数向量 \(\vec{b}\) 驻留在磁盘中来计算 \(\prod_{i=0}^{n}{b_{i}^{s_i}}\)

目前,我们使用的是 libsnark 库中的 Bos-Coster 算法的实现版本。在最坏的情况下,该算法会使用与操作的底数相同数量级的内存,因此减少内存使用的唯一途径是一次性使用较小的底数子集。例如,Ariel Gabizon 在对 libsnark 库的一次更改中实现了这种 优化

Libsnark 库最近实现了一个 Pippenger 算法的变种,它将多指数分解成指数的按位区域,将底数累积到桶中,并且按部分执行求和运算。该算法不仅比 Bos-Coster 更加高效,而且在流式验证的上下文中非常方便。使用该算法,我们可以避免在构建证据之前将证明密钥加载到内存中,这是我们系统中内存使用的主要来源。

全新证明系统

当然,执行更少的多指数操作也是提高运行时性能的一种好的方法。我们正在强烈地考虑使用一种由 Jens Groth 发现的 全新 zk-SNARK 证明系统,来替代 PGHR ( Pinnochio )。该证明系统使用了更强的加密假设,但具有更小的证据以及更加快速的证明/验证过程。

此外,Groth 的全新证明系统允许我们设计更加廉价的多方计算和其它非常有趣的特性,我们将在未来的博客中探讨更多的细节。

下一步

尽管上述提到的改进结合在一起对内存使用以及证明时间提供了实质性的改进,但是降低我们的 zk-SNARK 电路的大小将会有更明显的效果。我们已经基于 BLS12-381 曲线结构构建了大量的加密原语,这允许我们缩小我们算术电路的大小,降低 Zcash 地址的大小,以及简化协议。

在我们下一篇博客中,我们将更多地探讨这些原语,以及这些改进是如何帮助提升我们 zk-SNARKs 算法性能的。

Sapling, zkSNARKs, protocol | 查看所有标签