영지식 증명과 블록체인

#ZKP #Research #Klaytn

블록체인에서는 노드들이 투명하게 동일한 원장을 유지하며 모든 트랜잭션들을 실행하고 검증하기 때문에, 프라이버시와 확장성의 문제가 있습니다. 블록체인 씬에서는 프라이버시와 확장성 문제를 해결 하기위해 영지식 증명 기술(zero Knowledge proof)을 적용한 많은 연구개발들이 진행 중에 있습니다.

영지식 증명이란 상대방에게 어떠한 정보도 제공하지 않은 채, 자신이 해당 정보를 가지고 있다는 사실을 증명할 수 있는 기술입니다.이러한 영지식 증명 기술을 블록체인에 적용하게 되면 거래를 공개하지 않아도 거래의 유효성을 검증할 수 있어 프라이버시 문제를 해결할 수 있고, 수많은 트랜잭션의 실행과 검증 대신에 하나의 영지식 증명 검증으로만 수많은 트랜잭션의 실행과 검증을 대체 할 수 있는 computation compress work이 가능하여 확장성 문제를 해결합니다.

본 세션에서는 클레이튼에서의 진행하고 있는 ZKP를 활용한 Privacy 연구와 확장성에 대한 연구에 대해 소개드립니다. 설명에는 문제의 해결방식과 분석에 대한 내용을 설명 드리고자 합니다. 사전 지식이 없어도 쉽게 이해 할 수 있도록 설명 드리고자 하니 많은 관심 부탁드립니다.

발표자 : iron.cho
크러스트유니버스 코어 데브팀의 아이언입니다. 블록체인의 문제들을 연구개발로 해결하는일을 하고 있습니다.

Transcript

1. 1분 요약 안녕하세요, 저는 클레인튼의 코어개발팀의 아이언입니다. 이번 발표에서는 근래에 블록체인에서 화두가 되고 있는 영지식 증명기술에 대해 이야기를 드리고자 합니다. 영지식 기술이 무엇이고, 영지식 기술을 통해 블록체인의 프라이버시, 확장성, 상호운영성의 문제를 어떻게 해 결하는지에 대해 설명을 드리고자 합니다. 본 발표는 블록체인에 관심이 있으셨던분들이 영지식 기술을 이해할 수 있도록 쉽게 구성이 되어있습니다. 많은 관심 부탁 드립니다. 감사합니다.
2. : #೥కೞక #৔૑ध੉ # ࠶۾୓ੋীࢲ Copyright 2022. Kakao Corp. All rights reserved. Redistribution or public display is not permitted without written permission from Kakao. ৔૑ध ૐݺҗ ࠶۾୓ੋ ઑࣻജ iron.cho ௼۞झ౟ ਬפߡझ if(kakao)2022
3. ־ҳࣁਃ ? Klaytn Core Dev Team| Research Part Iron.cho ✓ 3FTFBSDI
   PO
   UIF
   "EWBODFE
   5FDIOPMPHZ
   3FRVJSFE
   GPS
   ,MBZUO
   $PSF
   
   3FTFBSDI
   PO
   ;,1SFMBUFE
   *OUFSPQFSBCJMJUZ
   4DBMBCJMJUZ
   BOE
   1SJWBDZ ✓ Activating the Blockchain Research Community: Planning and Implementation of the Blockchain Research Center(BRC) Program #Ӗ۽ߥ ࠶۾୓ੋ োҳ ݍ૘ # ਬݎ઱ • Ph.d Computer Science -Research Blockchain • Emblock - Blockchain core and application tech • Microsoft - Testing windows 8.1 project
4. 1. ৔૑ध ૐݺ (zero knowledge proof, Zkp )? 2. Zkp Research – Privacy 3. zkp Research - Scalability 4. Zkp Research – Interoperability
5. 이 발표 내용구성은 zkp를 쉽게 설명하기위해 구성 되어있습니다. (zkp 기술은 난이도가 조금 있고 ? 사전지식이 많이 필요로 합니다.) 정확한 기술의 구성과 용어들은 참조 자료들을 꼭 봐주세요 !
6. 1. ৔૑ध ૐݺ (zero knowledge proof, Zkp )?
7. 블록체인의 Mass Adoption에 뭐선 129 Scalability, Privacy, Interoperability …. 탈중앙화 (Decentralized) 합의 (Consensus) 투명성 (Transparency) 안전하게 (Secure)
8. ZKP How ?
9. Zero knowledge Proof #알리바바 동글 증명하는데 지식이 없다. Alice Bob 나의 어떠한 사실 또는 정보가 참이라는것을 증명 하고 싶어 Alice의 어떠한 사실 또는 정보를 몰라도 나는 참인지 알수가 있어
10. Alice Bob Age = 23 Balance = 100 Klay Degree = M.S ? Age = 23 Balance = 100 Klay Degree = M.S Alice Age = 23 True Balance = 100 Klay True Degree = M.S True
11. Alice Bob Age = 23 Balance = 100 Klay Degree = M.S Age = 23 Balance = 100 Klay Degree = M.S Trust : Service Age True Balance True Degree True Alice
12. Alice Bob Age = 23 Balance = 100 Klay Degree = M.S Blockchain[Cypress] Age True Balance True Degree True Age = 23 Balance = 100 Klay Degree = M.S Alice
13. Alice Bob Age = 23 Balance = 100 Klay Degree = M.S Age True Balance True Degree True π ≈ Proof ? Alice ? Blockchain[Cypress]
14. Z K P In [1] cryptography, a zero - knowledge proof or zero - knowledge protocol is a method by which one party (the prover) can prove to another party (the veri fi er) that a given statement is true while the prover avoids conveying any additional information apart from the fact that the statement is indeed true. The essence of zero - knowledge proofs is that it is trivial to prove that one possesses knowledge of certain information by simply revealing it; the challenge is to prove such possession without revealing the information itself or any additional information Completeness: true -> honest prove, honest veri fi er Soundness : false -> dishonest prove, veri fi er Zero - knowledge : veri fi er , zero Zero - knowledge Property Ref[1] :https://en.wikipedia.org/wiki/Zero-knowledge_proof#cite_note-:0-1
15. Non-Interactive Zero-Knowledge Proof system Non-Interactive zero-knowledge proof system, Prover sends Proof to Verifier only once ✓ Send a message only once ✓ Connectionless Blockchain Zk Snarks [2] Zk SNARK zero-knowledge Succinct Non-interactive Argument of Knowledges Non- interactive Succinctness ✓ Assume verifier has limited computational resources ✓ Reduce ZKP's proof size and verify quickly ✓ Maximize the practicality of non-interactive ZKP Ref[2]: https://eprint.iacr.org/2016/260.pdf
16. Z K P How ? Zero Knowledge Proof prove and verify ݃ߨ
17. Zk Snark Algebraic Circuit Problem (Code) R1CS QAP (Quadratic Arithmetic Program) Elliptic Curve Pairings f(x): y= x³+2x²+x+1. (x=2, y=19) Code Gate1: x*(x+2) = sym1 Gate2: sym1*x = sym2 Gate3: (sym2 + x +1) * 1 = y (~out) C= A*B Circuit 0 1 0 0 0 0 0 1 0 0 1 1 0 1 0 2 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 A B C (A • S) (B • S) - C • S = 0 ੗ࣁೠ zk snark ੄ ਗܻח ଵઑ ੗ܐ [2]ܳ ଵઑ೧઱ࣁਃ ! 1 4 -3 1 0 -1.5 -4 4 -1.5 0 0.5 1 -1 0.5 0 A[t] B[t] C[t] 7 0 0 0 0 -6.5 1.5 0 0 0 1.5 -0.5 0 0 0 0 0 3 -3 1 0 0 -2.5 4 -1.5 0 0 0.5 -1 0.5 A(t_0) * B(t_0) — C(t_0) = H(t_0) * Z(t_0) Trusted Party (t_0) A(t_0), B(t_0), C(t_0), H(t_0) Discrete Logarithm Problem e(G,G) A(t_0)*B(t_0)-C(t_0) = e(G,G) H(t_0)* Z(t_0) e(π_a, π_b) / e(π_c, G) = e (π_h, Z(t_0) * G) 1) Check QAP divisibility 2)Check validity of knowledge commitments forA,B,C: 3)Check same coefficients were used π_a, π_b, π_c, π_h π_a', π_b', π_c', π_s' Bilinear Pairing Verifier Proof A[t], B[t], C[t], Z(t) ݃ߨ
18. Zk Snark Magic Algebraic Circuit R1CS QAP Elliptic Curve Pairings ✓F( ) = Original Problem ✓x = secret (witness) ✓y = result ✓F(x) = y ✓F’( ) = Transform Problem -> Proving , Verifying ✓Proving (x) = π (Proof) ✓Verify (π) = result (True | False) ≈ zkp੄ ޙઁ߸ച
19. CRS common reference string ≈ Proving Key(Pk), Verifying Key (Vk) Alice = Prover Age == 23 Balance == 100 Klay Degree == M.S Problem = F() λ) : security parameter (Toxic wasted) Zk Snark Magic ≈ Transform the problem into zero knowledge proof X=23 Balance = 100 Klay Degree = M.S w= witness Trust Party Transform Problem = F’() Proving(), Verifying() Proving (w, pk ) = π (proof) Verifying(π, vk) Cypress-Blockchain True | False Verifying Contract Compile Generate Proof Generate Verifying Contract Verifying Proof Setup
20. zkp੄ ؊ ݆਷ ੿ࠁܳ ਗೞन׮ݶ ? Klay Makers zkp Workshop • Awesome : https://github.com/matter-labs/awesome-zero-knowledge-proofs • https://eprint.iacr.org/2016/260.pdf • Zcash ZKP : https://z.cash/technology/zksnarks/ • Vitalik Buterin's blog series on SNARKs • https://eprint.iacr.org/2013/879.pdf • https://www.youtube.com/user/hhanh01/videos • https://www.youtube.com/watch?v=_6TqUNVLChc • https://eprint.iacr.org/2013/279.pdf
21. 2. Zkp Research – Privacy
22. Blockchain Privacy Transparent Privacy
23. > not broadcast private data on public network > not privacy friendly Web 2.0 Web 3.0 Apps DApps privacy friendly
24. Digital Asset Native Coin, Token Transaction ≈ Sender, Receiver, amount + Ownership (Digital Signature)
25. Segregating Unlinking Hiding Off-payment channel Onetime Address Mixing Ring Signature Ledger Segregating Transaction ≈ Sender, Receiver, amount + Ownership (Digital Signature)
26. Blockchain Wallet Bob(EOA) Alice(EOA) 100 Klay Alice(EOA) Transaction ≈ Sender, Receiver, amount + Ownership (Digital Signature) Alice state Update Bob state Update Tx = Alice Sig, Alice addr, Bob addr , 100 If tx valid : 1. Owner Ship (Signature) 2. Balance (Integrity) 3. Double Spending 4. Protocol Rule
27. যڌѱ ৔૑ध ૐݺਵ۽ ? zero-knowledge proof ≈ no any information except whether the statement is true or false. Transaction ≈ Sender, Receiver, amount Transaction -> Valid? Blockchain + Ownership (Digital Signature) π
28. ޙઁ 1 : Hiding Transaction ≈ Sender, Receiver, amount Balance,Sender, Receiver, amount KLAYTN (State Model) Contract >cryptography UTXO Model To Address Alice Address Alice V V = V’ + V’’ Unspent Spent Balance,Sender, Receiver, amount
29. ޙઁ 2 : Transaction validation & update Cypress-Blockchain Verify () if π is valid Balance , Sig Sender, Receiver, amount Update
30. CM := Hash(v||addr||o) Commitment Alice(EOA) Cypress-Blockchain Bob(EOA) CM1 = Hash(100Klay|Alice | O) CM2= Hash(100Klay|Bob | O) CM1 CM2 Update How to ? 1. Owner Ship (Signature) 2. Balance (Integrity) 3. Double Spending 4. Protocol Rule
31. How to ? > Owner Ship (Signature) 2. Balance (Integrity) > Double Spending 4. Protocol Rule Alice(EOA) Cypress-Blockchain Bob(EOA) CM1 = Hash(100Klay|Alice | O) CM2 = Hash(100Klay|Bob | O) Nullifier COM CM1 CM2 CM3 CM4 ,,, .. Nf Double Spending Nf = Hash (Skown ,cm1 ) Ownership Skown Skown
32. How to ? 1. Owner Ship (Signature) > Balance (Integrity) 3. Double Spending 4. Protocol Rule Alice(EOA) Cypress-Blockchain Bob(EOA) CM1= Hash(100Klay|Alice | O) CM2= Hash(100Klay|Bob | O) Co-Path = A,B, Cm1 Cm1 A B Membership Proof RT
33. How to ? 1. Owner Ship (Signature) 2. Balance (Integrity) 3. Double Spending > Protocol Rule ✓ Membership proof (rt, Cm1, Path) ✓ CM1 = Hash(100Klay|Alice | O) ✓ CM2 = Hash(100Klay|Bob | O) ✓ nf1 = Hash (Skown ,Cm1 ) ✓ PCT bob ✓ PCT Audit ✓ Update process ZKP π (proof) Verify : ✓ CM2 ✓ rt ✓ nf 1 ✓ If π is valid : Update ✓ Cypress-Blockchain
34. money laundering drug trafficking Audit Cypress-Blockchain Zkp Privacy money laundering drug trafficking Blockchain Zkp Privacy “Azeroth [3] [Auditable Zero-knowledge Transactions in Smart Contracts] ” Performance + Audit https://www.zkrypto.com/ Zkp core, tech. Rollup Privacy, Voting, did [3] : Azeroth https://eprint.iacr.org/2022/211.pdf
35. Transaction Type Proof Generate time Gas Zether[4] transfer 17.9 sec 606 million withdraw 8.5 sec 245 million Zeth[5] transfer 13.2 sec 142 million withdraw 13.5 sec 145million Azeroth zkTrasnfer(transfer,withdra w) 0.9 sec 150 million • Private Network Solo Consensus Node CN 1 / PN 1 / EN 1 (local network): macmini i7 • Zether(sigma-bulletproof) • Zeth (GROTH16) • Azeroth (GROTH16) • Azeroth (GROTH16) Tx_Latency : 3.5 sec (Client : 1.9 + KLAYTN Blockchain : 1.6 ) • Zk Freindly cryptography, Optimization Ref[4] : https://crypto.stanford.edu/~buenz/papers/zether.pdf Ref[5] : https://arxiv.org/pdf/1904.00905.pdf
36. Research on improvement of Azeroth ✓ Usability ✓ Wallet support ✓ Security ✓ Performance (Gas) : Layer 2 , Membership proof, Structure Next !
37. 3. zkp Research - Scalability
38. Blockchain Scalability 탈중앙화 (Decentralized) 합의 (Consensus) 투명성 (Transparency) 안전하게 (Secure) Low TPS, High gas Cost, Storage ….
39. Sharding, Consensus, Network, Storage, cryptography EVM… Mainchain L1 Lightning network, state channel, side chain, Plasma.. .. And .. Rollup L2 Solution(L1 offchain)
40. Cypress- Blockchain Layer 1 Layer 2 Tx1 Tx2 Tx3 Tx4 Tx5 Tx6 .. . Contract Batch StateRoot Data (Highly compression ) Single Transaction L2 1000 Transaction > Valid ?
41. যڌѱ ৔૑ध ૐݺਵ۽ ? zero-knowledge proof ≈ no any information except whether the statement is true or false. ≈ L2 Transactions Transactions ->ZKP ->π (Proof) Layer1 Contract Verify
42. zk Rollup Structure ] • L1 Trust L2 Zkp proof -> L1 verify • Compression effect on transaction execution and validation Layer1 Layer 2 π (proof) Tx1 Tx2 Tx3 Tx4 Tx5 Tx6 .. . ERC20, ETHER Transfer Deposit Withdraw Tx verification conditions Circuit Constraint Block1 Block2 Block3 π (proof) π (proof) Πblock Data State Root Aggregate Verify (Πblock )
43. zk Rollup Structure Alice Bob Deposit Withdraw (Full Exit) Alice Bob Layer2 L2 State Deposit Withdraw (Full Exit) Layer1 Contract L1 Transaction L1 -> L2-> L2 –Block Commit (stateRoot, L2 data), commit proof -> L1-verify -> Finalize state L2 Transaction L2-> L2 -> L2-Block Commit (stateRoot, L2 data), commit proof -> L1-verify -> Finalize state Zkp proof -> Verify Block & finalize state L1 Transaction L2 Transaction Server Prover State Merkle Tree Transaction state : Committed, Verified
44. zk Rollup Structure Alice Bob Deposit Withdraw (Full Exit) Alice Bob Layer2 L2 State Deposit Withdraw (Full Exit) Layer1 Contract L1 Transaction L1 -> L2-> L2 –Block Commit (stateRoot, L2 data), commit proof -> L1-verify -> Finalize state L2 Transaction L2-> L2 -> L2-Block Commit (stateRoot, L2 data), commit proof -> L1-verify -> Finalize state Zkp proof -> Verify Block & finalize state L1 Transaction L2 Transaction Server Prover State Merkle Tree Transaction state : Committed, Verified
45. zk Rollup Structure ▪Data Availability : The L2 data update for every block is published over the mainchain network ▪Users can always retrieve the funds from the Rollup even if validator(s) stop cooperating because the data is available -> Modular Blockchain ▪On chain Operation -> withdraw ▪ Opcode, ▪ Account, ▪ Amount ▪ … ▪ .. ▪L2 Data (Highly compression )
46. zk EVM (2.0) • zkEVM : virtual machine that runs zero-knowledge proofs in a manner compatible with zero-knowledge proof computations. • Zkp complexity -> Smart Contract Deploy (lang support) -> Proof , Circuit , verify • Supports smart contract development toolz • zk-friendly : Hash function (SHA256, Keccak256), cryptographic , computation
47. • Rollup & Zk EVM • L2 Cost & Block Commit (block size chunk), zk Snark 1 ≈ 1000 • Tps & Tx Latency
48. 4. Zkp Research – Interoperability
49. Blockchain Interoperability Bridge
50. Bridge Contract Contract Trust party Service provider Operator, Validator Security threats Blockchain A Blockchain B Contract Contract Trustless Blockchain A Blockchain B
51. How can we make a trustless bridge? 
 zero-knowledge proof no any information except whether the statement is true or false. Blockchain A Blockchain B Blockchain B Blockchain B π π Alice(EOA) Alice(EOA) Contract Contract Blockchain A Blockchain B π >> Each isolated chain only trusts zkp Proof 

52. যڌѱ
    ೞݶ
    ন
    ଃ୓ੋীࢲ
    ౟ے੥࣌੉
    ৢ߄ܰѱ
    ୊ܻо
    غ঻Ҋ
    ࠶۾ী
    ನೣ੉
    غ঻חо
    #MPDL
    )FBEFS
    
    ℵ
    $POTFOTVT
    /PEF > Blockchain Consensus >Transaction Execution ! Difficult (Consensus) ! High computation cost off chain (Cryptography) ! Non-ZKP Next )FBEFSSFDFJQUT3PPU
    
    NFSLMF3PPU 5Y@SFDFJQU
    .FSLMF
    1BUI 5Y@SFDFJQU-PH<*EY>'SPN
    
    
    
    
    
    
    
    
    
    
    
    
    
    6TFS.$ 5Y@SFDFJQU-PH<*EY>5P
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    #SJEHF
    "EES.$
    IBSE
    DPEFE 5Y@SFDFJQU-PH<*EY>"NPVOU
    
    
    
    
    
    
    
    
    
    "NPVOU 5Y@SFDFJQU-PH<*EY>%FTUJOBUJPO
    
    
    
    
    #SJEHF
    "EES4$
    IBSE
    DPEFE 5Y@SFDFJQU-PH<*EY>4$@"DDPVOU
    
    
    6TFS4$ 5Y@SFDFJQU4UBUVT
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    IBSE
    DPEFE