國立臺灣師範大學博碩士論文全文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	何明諭 Ho, Ming-Yu
論文名稱：	以IPA增強之KZG10的批次狀態更新驗證技術 Verification of Batch State Updates Based on IPA Enhanced KZG10
指導教授：	黃冠寰 Hwang, Gwan-Hwan
口試委員：	黃冠寰 Hwang, Gwan-Hwan 張道顧 Chang, Tao-Ku 梁家為 Liang, Chia-Wei
口試日期：	2024/07/29
學位類別：	碩士 Master
系所名稱：	資訊工程學系 Department of Computer Science and Information Engineering
論文出版年：	2024
畢業學年度：	112
語文別：	英文
論文頁數：	81
英文關鍵詞：	zkSNARKs, KZG10, IPA, Polynomial Commitment Scheme, Reed-Solomon Fingerprinting
研究方法:	實驗設計法
DOI URL：	http://doi.org/10.6345/NTNU202401597
論文種類：	學術論文
相關次數：	點閱：62 下載：0
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

自從區塊鏈技術問世以來, 擴展性問題一直是其發展中的一大挑戰。為了提升區塊鏈的交易處理能力, Vitalik Buterin 和 Barry Whitehat 等先驅提出了 ZK-Rollup 作為一種 Layer 2 技術, 因其能夠在不犧牲安全性的前提下大幅提高交易吞吐量而備受矚目。ZK-Rollup 透過將大量交易捆綁成一個批次並生成零知識證明, 使得區塊鏈主網僅需驗證該證明即可確保交易的有效性, 從而大幅減少了鏈上數據的處理壓力。

本研究針對區塊鏈 Layer 2 擴展技術中的 ZK-Rollup 狀態轉移效率問題, 提出了一種結合 Inner Product Argument (IPA) 和 KZG10 Polynomial Commitment Scheme 的創新方法。在大規模數據的批次更新的情境下, 此方法可以透過可接受範圍內證明者 (Prover) 運算負擔的增加, 提升了驗證者 (Verifier) 運算效率。這項特性無論對於智能合約的驗證, 或這要結合 zkSNARKs 技術都有著重要的意義。實驗結果證明了 Prover 所增加的運算負擔依舊使整套流程保持可行性, 並且確實降低了驗證過程的運算成本。本研究提供了一種新的權衡方案, 展示了在 Prover 運算效率與 Verifier 運算成本之間的平衡可能性。

Since the advent of blockchain technology, scalability has remained a significant challenge in its development. To enhance the transaction processing capacity of blockchains, pioneers like Vitalik Buterin and Barry Whitehat proposed ZK-Rollup as a Layer 2 technology. ZK-Rollup has garnered considerable attention due to its ability to significantly increase transaction throughput without compromising security. By bundling a large number of transactions into a batch and generating a zero-knowledge proof, ZK-Rollup enables the blockchain mainnet to verify the proof alone to ensure the validity of transactions, thereby greatly reducing the processing pressure on on-chain data.

This study addresses the state transition efficiency problem in ZK-Rollup, a blockchain Layer 2 scaling technology, by proposing an innovative method that combines the Inner Product Argument (IPA) and the KZG10 Polynomial Commitment Scheme. In the context of batch updates of large-scale data, this method improves the verifier's computational efficiency at the expense of an acceptable increase in the prover's computational burden. This feature is of significant importance for the verification of smart contracts and the integration of zkSNARKs technology. Experimental results demonstrate that the increased computational burden on the prover remains feasible for the overall process and indeed reduces the computational cost of the verification process. This study provides a new trade-off solution, demonstrating the possibility of balancing prover computational efficiency with verifier computational cost.

Introduction 1
1 Research Motivation and Background 1
2 Overview of the New Method 3
2.1 Intuitive Solution in KZG10 4
2.2 Solution using Reed-Solomon Fingerprinting 5
2.3 Solution using IPA Enhanced KZG10 and Reed-Solomon Fingerprinting 9
Preliminaries 15
1 Reed-Solomon Fingerprinting 15
2 Polynomial Commitment Schemes 19
2.1 Hash-Based Polynomial Commitment Scheme 19
2.2 KZG10 21
3 The Fiat-Shamir Transformation 22
Verification of Single State Updates 24
1 Problem Definition 24
2 Traditional Merkle Tree Solutions 25
3 KZG10-Based Solutions 27
3.1 Representing System States with Polynomials 27
3.2 Verifying Values at Specific Indices Using KZG10 29
3.3 Verifying Values at Specific Indices Using KZG10 and Reed-Solomon Fingerprinting 30
3.4 Verification of Updates 31
Batch Verification Approach for State Updates 39
1 Batch Approach with KZG10-based Solutions 40
1.1 Verifying New Values of Specific Fields 40
1.2 Protocol Description 42
2 Batch Approachs for Polynomial Commitment Schemes Based on Additively Homomorphic Properties 44
IPA Enhanced KZG10 45
1 The Polynomial Identity of P_{S} and P_{S_inv} 46
2 The Polynomial Identity of P_{B_{epsilon}} 47
3 Additive Homomorphic Properties 49
Final Protocol 51
1 The protocol 51
Experimental Results 54
1 Experiment Design 54
1.1 Experimental Variables 55
1.2 Measurement Metrics 55
1.3 Summnary the Complexities 55
1.4 Experimental Machine Specifications 55
2 Experimental Data 56
2.1 Verification Time 56
2.2 Proof Size 64
2.3 Proving Time 71
3 Results Comparison 78
Conclusion and Future Work 78
1 Conclusion 78
2 Future Work 79
Rreferences 79
                                

SanjeevArora and Shmuel Safra. Probabilistic checking of proofs; a new characterization of np. In Proceedings of the 33rd Annual Symposium on Foundations of ComputerScience(FOCS),pages70–122.IEEEComputerSocietyPress,October 1992.
EliBen-Sasson,AlessandroChiesa,ChristinaGarman,MatthewGreen,IanMiers, Eran Tromer, and Madars Virza. Zerocash: Decentralized anonymous payments from bitcoin. Cryptology ePrint Archive, Paper 2014/349, 2014. https://eprint.iacr.org/2014/349.
J.-P. Berrut and L. N.Trefethen. Barycentric lagrange interpolation. SIAM Review, pages 501–517, 2004. To appear.
David S. Dummit and Richard M. Foote. Abstract Algebra. John Wiley & Sons, 3rd edition, 2004.
Amos Fiat andAdi Shamir. How to prove yourself: Practical solutions to identification and signature problems. In Conference on the Theory and Application of Cryptographic Techniques. Springer, 1986.
Max Hoffmann, Michael Klooß, and Andy Rupp. Efficient zero-knowledge arguments in the discrete log setting, revisited. Cryptology ePrint Archive, Paper 2019/944, 2019. https://eprint.iacr.org/2019/944.
Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg. Constant-size commitments to polynomials and their applications. In Masayuki Abe, editor, Advances in Cryptology- ASIACRYPT 2010- 16th International Conference on the Theory and Application of Cryptology and Information Security, volume 6477 of Lecture Notes in Computer Science, pages 177–194. Springer, 12 2010.
R. C. Merkle. Adigital signature based on a conventional encryption function. In Proc. Conf. Theory and Applications of Cryptographic Techniques on Advances in Cryptology (CRYPTO’87), pages 370–378, 1987.
BryanParno,CraigGentry,JonHowell,andMarianaRaykova. Pinocchio: Nearly practical verifiable computation. Cryptology ePrint Archive, Paper 2013/279, 2013. https://eprint.iacr.org/2013/279.
Irving S. Reed and Gustave Solomon. Polynomial codes over certain finite fields. Journal of the Society for Industrial and Applied Mathematics, 8(2):300–304, 1960.
Charles Van Loan. Computational Frameworks for the Fast Fourier Transform. SIAM, Philadelphia, PA, 1992.
BarryWhitehat. Roll up. Accessed: 2024-07-16.Availableat: https://github.com/barryWhiteHat/roll_up.
Gavin Wood. Ethereum: A secure decentralised generalised transaction ledger. https://ethereum.github.io/yellowpaper/paper.pdf, 2014. Accessed: 2024-07-16.
Zk rollup architecture. Accessed: 2024-07-16. Available at: https://zksync.io/faq/tech.html#zk-rollup-architecture.

簡易檢索 / 詳目顯示

相關論文