關於零知識證明的探討及其在區塊鏈系統上之應用

On the Zero-Knowledge Proof and its Application in Blockchain

程鼎元(Ting-Yuan Cheng)

指導教授 ： 廖世偉

共同指導教授 ： 鄭振牟

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2019年)

https://doi.org/10.6342/NTU201904438

摘要

區塊鏈技術可以在分散的不受信任的各方之間達成共識，而零知識證明可以增進區塊鏈上的隱私。透過零知識證明，任何人可以證明一條特定的敘述是正確的，而不會洩漏保密的資訊。但是，通常必須將該敘述轉換為特定的形式，即Rank-1約束系統，才能在已廣泛被採用的系統中使用。轉換的效率決定了公共參考字串（CRS）的大小以及證明該敘述所需的運算量。 更具體地說，為了最大程度地減少R1CS中的約束數量，我們優化了布林函式和動態陣列訪問操作，它們廣泛用於加密和可驗證計算中。本文並介紹數個建構於區塊鏈系統上之零知識應用。

關鍵字

密碼學 ； 零知識證明 ； 二次算術程式 ； 一階約束系統 ； 編譯器 ； 可驗證計算 ； 非交互式簡潔知識證明

並列摘要

Blockchain technology can reach consensus between decentralized untrusted parties, and zero-knowledge proof can enhance the privacy on the blockchain. By zero-knowledge proof, one can prove that a particular statement is true without leaking other information. However, a general statement must be converted to a specific circuit form, Rank-1 constraint system, typically, to use in the above mechanism. The efficiency of the conversion determines the size of the common reference string (CRS) and the resources it takes to prove the statement. More specifically, to minimize the number of constraints in R1CS, we optimized boolean functions and dynamic array accessing operations, which are widely used in cryptography and computational verification.

並列關鍵字

Cryptography ； Zero-knowledge proof ； Quadratic arithmetic programs ； Rank-1 constraint system ； Compiler ； Verifiable computation ； SNARKs

參考文獻

Ajtai, M., Koml´os, J., Szemer´edi, E.: An 0 (n log n) sorting network. In: Proceedings of the fifteenth annual ACM symposium on Theory of computing. pp. 1–9. ACM (1983)

Batcher, K.E.: Sorting networks and their applications. In: Proceedings of the April 30–May 2, 1968, spring joint computer conference. pp. 307–314. ACM (1968)

Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E., Virza, M.: Snarks for c: Verifying program executions succinctly and in zero knowledge. In: Annual Cryptology Conference. pp. 90–108. Springer (2013)

Ben-Sasson, E., Chiesa, A., Riabzev, M., Spooner, N., Virza, M., Ward, N.P.: Aurora: Transparent succinct arguments for r1cs. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques. pp. 103–128. Springer (2019)

Ben-Sasson, E., Chiesa, A., Tromer, E., Virza, M.: Scalable zero knowledge via cycles of elliptic curves. Algorithmica 79(4), 1102–1160 (2017)