Ou: Automating the Parallelization of Zero-Knowledge Protocols
Ou: Automating the Parallelization of Zero-Knowledge Protocols
复制标题
Ou：零知识协议的自动化并行化
DOI：
10.1145/3576915.3616621
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Shao, Zhong
中科院分区：
文献类型：
--
作者：
Sang, Yuyang;Luo, Ning;Judson, Samuel;Chaimberg, Ben;Antonopoulos, Timos;Wang, Xiao;Piskac, Ruzica;Shao, Zhong
零知识证明（ZKP）是一种强大的加密原语，用于许多分散或以隐私为中心的应用程序。然而，zkp的高开销限制了它们的实际适用性。我们设计了一种编程语言Ou，旨在减轻程序员在编写高效zkp时的负担；我们设计了一个编译器框架Lian，用于自动分析语句并将其分发到计算集群。Ou使用编程语言语义、形式化方法和组合优化来自动将Ou程序划分为有效大小的块，以进行并行zk证明和/或验证。我们贡献：(1)一种前端语言，用户可以用熟悉的语法将证明语句写成命令式程序；(2)编译器架构和实现，自动分析程序并将其编译为可提升为各种ZKP结构的优化IR；(3)基于伪布尔优化和整数线性规划的切割算法，该算法对指令进行重新排序，然后将程序划分为有效大小的块，以便并行计算和有效的状态协调。
A zero-knowledge proof (ZKP) is a powerful cryptographic primitive used in many decentralized or privacy-focused applications. However, the high overhead of ZKPs can restrict their practical applicability. We design a programming language, Ou, aimed at easing the programmer's burden when writing efficient ZKPs, and a compiler framework, Lian, that automates the analysis and distribution of statements to a computing cluster. Ou uses programming language semantics, formal methods, and combinatorial optimization to automatically partition an Ou program into efficiently sized chunks for parallel ZK-proving and/or verification. We contribute: (1) A front-end language where users can write proof statements as imperative programs in a familiar syntax; (2) A compiler architecture and implementation that automatically analyzes the program and compiles it into an optimized IR that can be lifted to a variety of ZKP constructions; and (3) A cutting algorithm, based on Pseudo-Boolean optimization and Integer Linear Programming, that reorders instructions and then partitions the program into efficiently sized chunks for parallel evaluation and efficient state reconciliation.
登录
查看更多内容
DOI：
10.1109/eurosp53844.2022.00015
发表时间：
2022-06
期刊：
2022 IEEE 7th European Symposium on Security and Privacy (EuroS&P)
影响因子：
--
作者：
Yibin Yang;David Heath;V. Kolesnikov;David Devecsery
通讯作者：
Yibin Yang;David Heath;V. Kolesnikov;David Devecsery
提高线点零知识：以一倍的价格进行两次乘法
DOI：
--
发表时间：
2022
期刊：
IACR Cryptology ePrint Archive
影响因子：
--
作者：
Samuel Dittmer;Yuval Ishai;Steve Lu;R. Ostrovsky
通讯作者：
R. Ostrovsky
Lunar：更高效的通用和可更新 zkSNARK 以及提交和证明扩展的工具箱
DOI：
--
发表时间：
2020
期刊：
IACR Cryptology ePrint Archive
影响因子：
--
作者：
Michael B Dreifke;M. Fröba;Martin Armbrecht
通讯作者：
Martin Armbrecht
DOI：
--
发表时间：
2020
期刊：
IACR Cryptol. ePrint Arch.
影响因子：
--
作者：
Joseph Bonneau;Izaak Meckler;V. Rao;Evan Shapiro
通讯作者：
Joseph Bonneau;Izaak Meckler;V. Rao;Evan Shapiro
DOI：
10.1007/978-3-030-45727-3_19
发表时间：
2020-05
期刊：
IACR Cryptol. ePrint Arch.
影响因子：
--
作者：
David Heath;V. Kolesnikov
通讯作者：
David Heath;V. Kolesnikov