📜 [專欄新文章] [zkp 讀書會] Cairo 語言介紹
✍️ NIC Lin
📥 歡迎投稿: https://medium.com/taipei-ethereum-meetup #徵技術分享文 #使用心得 #教學文 #medium
Cairo 是 STARK 證明系統的其中一個編程語言,讓開發者能透過 Cairo 來使用 STARK,撰寫效能更高的 Dapp
Photo by Simon Berger on Unsplash
Warning:本篇會保持在 high level 的介紹,實際深入的部分請見文內附上的文檔或是官方開發者文件
背景介紹
建構於密碼學的零知識證明能提供計算的隱私性,但同時在區塊鏈生態系也被用來提升 Scalability — 我可以用 10 秒的運算資源來驗證原本耗費 1000 秒運算資源的計算過程
如同更多人熟悉的 SNARK,STARK 也是一個零知識證明的證明系統,但當前的 STARK 著重的是在 Scalability ,而非大家比較習以為常零知識證明提供的隱私性特質
其實目前基於 SNARK 的 Rollup 項目,例如 zkSync、Loopring、Aztec、zkopru,除了 Aztec 外,其他都是利用 SNARK 來增加 Scalability — 這些 Rollup 上資料都還是公開、沒有隱私性的
StarkWare 是目前唯一基於 STARK 的開發團隊
STARK 要加上隱私保護不會太難,只是 StarkWare 還沒有把這項功能放在未來規劃中
Cairo 簡介
標榜為圖靈完備的零知識證明系統語言,Cairo 對原本熟悉 Solidity 的開發者來說還是會感到比較難上手和陌生的。再加上套件庫還不夠充足,目前支援的雜湊函式是 Pedersen,數位簽章演算法是 ECDSA(相對於 SNARK,EdDSA 的效能反而比較差所以沒有支援)。
但 Cairo 還在早期開發的階段,相信開發體驗會越來越好的。
另外需要注意的是作為一個證明系統,會有 Prover 和 Verifier 的角色。而 STARK 的 Verifier 是公開的,但 Prover 軟體預計會有 License 保護。Prover 一般情況下不得用於商業用途,除非將 proof 上傳至官方的 Verifier。
最後要提及的是,第一版的 Cairo 是設計來方便開發者將 Dapp 的運算遷移至鏈下。不同於 Rollup,這個鏈下只會有它自己一個 Dapp。這個 Dapp 的項目方自己維護自己 Dapp 的 state。( Rollup 則是 operator 維護所有 Dapp 的 state,Dapp 開發者不需自己操煩)
這可能有點難懂。如果你有在寫 Solidity,想像一下今天你在合約要用到合約裡宣告的 storage 變數時,你要自己提供 merkle proof 上來,證明這個storage 變數真的是這個值。這個就是開發者要自己維護 state 的意思。
而第二版的 Cairo 則是 StarkNet 裡使用的 Cairo(第一和第二版是不同編譯器),這版的 Cairo 就是作為 Dapp 在 Rollup 開發所使用 — 開發者可以在合約裡宣告變數,變數的值不需開發者維護,可以直接假設存在。
註1:StarkWare 不喜歡 Rollup 這個詞,他們覺得 Data Availability 的需求是一段光譜:不一定得要把 data 全都送上 L1,中間有其他方式可以做不同層級的 Data Availability。
註2:第一版和第二版實際上在官方版本裡是 0.0.1 及 0.0.2,在撰文當前最新版即是 0.0.2
官方網站:https://www.cairo-lang.org
開發者文件:https://www.cairo-lang.org/docs/
開發環境
Cairo 有提供像是 Remix 的瀏覽器 IDE:playground。裡面提供各種範例練習和挑戰,除了可以編譯,還可以直接生成並上傳 proof。
註:但有些功能還是沒辦法在 playground 裡使用,例如要給你的程式 custom input 時。這時候只能在本地端開發才能使用這個功能。
開發 Cairo 要先安裝python,我將開發者文件整理出來的資料統整在這個 hackmd 文檔裡:https://hackmd.io/w690dpAQTsKeKZv3oikzTQ
裡面包含簡介、設置本地開發環境以及 Cairo 基礎(因為篇幅原因,所以不將內容複製到這裡)
註:我把開發者文件裡的代碼整理到這裡:https://github.com/NIC619/cairo_practice/tree/master/practices
如果不想在研究開發者文件過程中,還要自己手動拼湊裡面例子的話,可以直接用整理好的代碼來執行。同時 repo 裡還有包含一些額外自己測試 Cairo 功能的範例。
深入 Cairo
在那份 hackmd 文檔裡的開頭,可以連結到第二部分 — 深入 Cairo 的部分。裡面也是從開發者文件裡擷取出來我覺得比較重要的部分。如果你要讀開發者文件的話,我建議從 Hello Cairo 開始,它會從例子切入,會比較好知道 Cairo 怎麼使用。接著如果要更深入了解,再去讀 How Cairo Works。
StarkNet Cairo
第二版的 Cairo 其實功能和第一版的 Cairo 是差不多的,所以不必擔心在開發者文件裡學到的 Cairo 在 StarkNet 版本會不能用或差很多。在讀完 Hello Cairo/How Cairo works 後,就可以接著看 Hello StarkNet。會很順利的切換到 StarkNet 版本的 Cairo。
註1:我整理的文檔裡是按照第一版 Cairo 所寫的
註2:如果你從開發者文件一路看下來,體驗過非 StarkNet 版的 Cairo,那你在體驗 StarkNet 版的 Cairo 時一定會發現這更像一般智能合約的使用方式 — 你可以用 view 函式查詢 storage 變數,可以用 external 函式去執行合約(非 StarkNet 版本不是這樣操作 Dapp 的,這邊因為篇幅原因沒有詳細介紹)。
非常建議嘗試兩種版本的 Cairo,你會知道 1. 操作一個單獨在 L2 的 Dapp 和2. 操作與其他 Dapp 共存在 Rollup 上的 Dapp 的不同。這對了解 L2 怎麼運行、需要哪些資料、為什麼需要這些資料非常有幫助。
0.0.2 版的 StarkNet Cairo 目前還缺少一些功能:
函式還沒辦法宣告陣列或 struct 型態的參數
合約和合約之間還沒辦法互動
L1 沒有辦法讀取到 L2 的資料,L2 也沒辦法讀取到 L1 的資料。如果要建立跨 L2 Bridge,這個功能非常重要。
補充及個人心得
STARK 的 proof size 相比於 SNARK 系列的 proof size 大很多,又其證明所包含的交易數量對 proof size 和驗證時間的影響不大,所以把很多筆交易一併做一個 proof 會是對 STARK 非常有利、節省成本的方式(SNARK、STARK 比較表)。但這同時也是一個缺點,如果你的 Dapp 或 Rollup 的 TPS 不高,那就只能等更久時間搜集多一點的交易,要不然就只能提高成本來維持驗證 proof 的頻率。
StarkWare和 zkSync 一樣都有 Rollup 宇宙的概念( Rollup 宇宙的用詞並不精確,因為在他們的宇宙中不會所有子鏈都是 Rollup,而是會有依照 Data Availability 程度不同所區分的子鏈,像是 Validium、zk Porter 的設計),個人覺得能夠有(針對 Data Availability 程度的)選擇是會比只有一個選擇(完全 Data Available) 還好的方式,但實際上的可行性就要等其團隊釋出更多的資訊。
在 Rollup 越趨成熟的情況下,能夠提供快速跨 Rollup 服務的流動性提供者的角色會越來越重要。zk Rollup(StarkNet、zkSync、etc…)比 Optimistic Rollup (Optimism、Arbitrum、etc…)有著短上許多的 finalize 時間,這對降低流動性提供者的風險有很大的幫助,但目前 zk Rollup 支援合約功能甚至 L1 <-> L2 互動的完成度都比 Optimistic Rollup 還低上許多。短期內快速跨 Rollup 的服務應該還是侷限在 Optimitic Rollup 之間。
abbrev
[zkp 讀書會] Cairo 語言介紹 was originally published in Taipei Ethereum Meetup on Medium, where people are continuing the conversation by highlighting and responding to this story.
👏 歡迎轉載分享鼓掌
ecdsa 簽章 在 Taipei Ethereum Meetup Facebook 的最佳貼文
📜 [專欄新文章] [ZKP 讀書會] MACI
✍️ Kimi Wu
📥 歡迎投稿: https://medium.com/taipei-ethereum-meetup #徵技術分享文 #使用心得 #教學文 #medium
Photo by Jesus Kiteque on Unsplash
預計這將是一系列介紹ZKP應用的文章,認識目前ZKP的應用,包含L1, L2和其他比較難分類的應用,當中也穿插著常用的ZKP演算法。而目前的規劃的主題有
MACI
ZKopuru
ZKSync
Trust Token
ZCash
Groth16
PLONK
ZKZK Rollup
…
首次的讀書會介紹了
MACI by Chih-Cheng Liang
ZKopru by NIC Lin
本篇文章先介紹MACI,ZKopru會由 NIC Lin在撰文介紹。
MACI
MACI 是 Minimal Anti-Collusion Infrastructure的縮寫, Vitalik 在2019年5月於ethreaser.ch所提出,為了讓用應用程式在區塊鏈上可以有抵抗共謀的一個機制(主要是想達到正確地執行你的想法跟抗審查(censorship resistance))。而最實際的應用就是投票,若在區塊鏈上投票能做到他人無法查驗你的票,這樣行賄者就無法知道你是否有乖乖投票,如此一來就能減低行賄的誘因。
(關於共謀的概念可以參考 Williams Lai 翻譯 Vitalik的論共謀)
基本流程大致為
欲投票者需要註冊期間內,以公鑰(EdDSA)向合約注冊身份
註冊期結束
投票開始,投票者將自己的票加密送到合約
投票結束,協調者(coordinator)從合約上抓下所有的票, 計算結果,並產生zk證明到合約,更新票數(注1)
MACI中最關鍵的機制在於,投票結束前,投票者都可以向合約發出更換公鑰的指令,然後再使用新的公私鑰去投票。當協調者計票時,會去合約上找註冊者的公鑰,若發現此身份有更換過公鑰,則舊公鑰所投的票就會被認定為無效票。程序大約為
Alice 註冊身份為 公鑰A
行賄者利誘或威脅 Alice 投贊成票,而 Alice 也照行賄者的意思投給了贊成票
在投票結束前,Alice 隨時可以向合約更改身份為公鑰B
更改完公鑰後,Alice 可再用私鑰B簽章投反對票
當協調者計票時,會發現用公鑰A已經被改為公鑰B,所以私鑰A所簽的贊成票,將記為無效票
再深入一點細節 . . .
使用者註冊先產生一組EdDSA的私鑰對(注2),再是透過合約的 signUp() 註冊公鑰,而合約中有一 merkle tree 記載著帳號相關的資訊
接著使用者產生一組臨時的 (ECDSA)私鑰對 prvE/pubE(每次投票就產生一組)
利用這組臨時的私鑰 prvE 跟協調者的公鑰 pubC 產生加密的鑰匙 EncKey,使用密鑰 EncKey 加密投票指令(command)(注3)
再將臨時的公鑰 pubE 與加密過的指令,透過合約的 publishMessage()上鏈
協調者透過 ECDH 交換秘密的方式可以得到 EncKey,當投票結束時協調者再使用這把密鑰把訊息(注3)解密,接著更新票數。
而更換公鑰的指令也是透過 publishMessage()上鏈,因為上鏈的指令都是加密過的,也只有協調者能解密,因此行賄者無法得知受賄者是否有更換過身份。
在MACI中,所有訊息都是上鏈的,因此不怕協調者不打包特定資料。不過所有資料協調者都可以解密,行賄者可以直接與協調者串通,去得知受賄者們是否有乖乖投票,如何防範不在 MACI 原本的提案內,有興趣的人可以去 MACI Github 上了解實作細節。
注1:對!MACI系統中協調者必須是誠實的
注2:在 snarks 的應用中通常使用EdDSA做簽章,而非以太的ECDSA,因為EdDSA在 zk circuit 的實作上複雜度比較低。
注3:在 MACI 中投票, 更換公鑰等動作都稱作指令(command),而加密後的指令稱作訊息(message)
Reference:
ethresear.ch post by Vitalik
MACI spec
[ZKP 讀書會] MACI was originally published in Taipei Ethereum Meetup on Medium, where people are continuing the conversation by highlighting and responding to this story.
👏 歡迎轉載分享鼓掌
ecdsa 簽章 在 Taipei Ethereum Meetup Facebook 的最佳貼文
📜 [專欄新文章] Ethereum Casper — 認識 BLS signature
✍️ Kimi W
📥 歡迎投稿: https://medium.com/taipei-ethereum-meetup #徵技術分享文 #使用心得 #教學文 #medium
最近重新追了一下Ethereum Casper的進展,發現到好多新東西(應該是之前看得太表面 XD),Casper跟sharding會綁一起,然後又有個beacon chain,zk-STARK(zk-SNARK的升級版)也來湊一腳,短時間有點難消化,有興趣的人可以google上面幾個keyword。
不過,今天想要介紹的是BLS signature(這又是什麼?????),這個新的簽章方式讓Casper往前再邁進一步!
BLS是Boneh–Lynn–Shacham的縮寫,有興趣的可以參考wiki。這個簽章方式厲害的是,可以把所有signature加起來,然後驗證。如果以現今的ECDSA簽章,100個人簽同一個message,那訊息量就是乘以100倍,以Ethereum官方估計,Casper的validators約有30萬,每一個finality都需要2/3的節點做投票,光是驗證signature這件事,大概就要花到一天,所以以現行的ECDSA簽章方式根本不可行。這也是之前Casper的bottleneck之一,Ethereum的researcher, Justin Drake提出了這個方案,當然也不是拿了就可以用的,BLS的介紹可以參考BLS signatures: better than Schnorr,寫得非常清楚也好懂。下面會簡單介紹一下。
首先,就是要找到一個特殊的橢圓對稱曲線可以達到以下的算式
e(a x P, b x Q) = e(P, ab x Q) = e(ab x P, Q) = e(P, Q)^(ab)
也就是某種的交換律
source from: https://medium.com/…/bls-signatures-better-than-schnorr-5a7… (也徵得作者同意)
用上面那邊文章的圖做解釋 pk:私鑰 P :公鑰 H(m):可以看作是hash過的message S:簽章
驗證簽章會滿足 e(P, H(m)) = e(G, S)
也就是signature可以用P(公鑰)跟 H(m)(hash過的message)做驗證,跟我們以往的認知是一致的。從公式看BLS在sign跟verify都很簡潔,資料量的部分也小了許多(好像是33 bytes)。而ECDSA在verify的部分就複雜了一點(需要先算出v值),細節可以參考這裡。簽章的加總(signature aggregation)簡單來講,就是利用上面提到的交換律所達成,細節可以參考上面提到的文章,這裡就不多提了。
省了空間,那效能呢?!
如果有把BLS signatures: better than Schnorr看過,最下面會提到,看起來很美好,其實很不實用,因為要找尋特殊的對稱曲線,其實很困難及複雜,所以在verify時會比原本的ECDSA更久。(啥?! 那Casper幹嘛用它!!)實際上Ethereum用BLS128–381,是去年Zcash發表的,是非對稱的橢圓曲線,針對128bits的應用上做了最佳化,所以也解決了效能上的問題。
根據Justin Drake提供的數據,2/3validators(預估總共validator數量為 312,500)的簽章大約會是40K,verify速度大約在300ms左右,但是離線蒐集跟打包signature大約要9分鐘,所以每次finality大約可以在10分鐘左右完成。
最後!這個是Ethereum中期的簽章方案,長期的預計會使用zk-STARK,zk-STARK的設計是可以抗量子攻擊,但目前資料量約在100kB左右,還會針對Ethereum做最佳化。
附:這有Ethereum meeting 討論BLS的影片
Originally published at kimiwublog.blogspot.com.
Ethereum Casper — 認識 BLS signature was originally published in Taipei Ethereum Meetup on Medium, where people are continuing the conversation by highlighting and responding to this story.
👏 歡迎轉載分享鼓掌