📜 [專欄新文章] 瞭解神秘的 ZK-STARKs
✍️ Kimi Wu
📥 歡迎投稿: https://medium.com/taipei-ethereum-meetup #徵技術分享文 #使用心得 #教學文 #medium
上一篇關於 zkSNARK扯到太多數學式,導致很難入手,這次介紹 STARK 會盡量減少數學式,以原理的方式跟大家介紹。
STARK 被視為新一代的 SNARK,除了速度較快之外,最重要的是有以下好處1. 不需要可信任的設置(trusted setup),以及
2. 抗量子攻擊
但 STARK 也沒這麼完美,STARK 的證明量(proof size)約 40–50KB,太佔空間,相較於 SNARK 只有288 bytes,明顯大上幾個級距。此外,這篇論文發佈約兩年的時間,就密碼學的領域來說,還需要時間的驗證。
STARK 的 S 除了簡潔(Succinct)也代表了擴展性(Scalable),而T代表了透明性(Transparency),擴展性很好理解,透明性指的是利用了公開透明的算法,可以不需要有可信任的設置來存放秘密參數。
SNARK 跟 STARK 都是基於多項式驗證的零知識技術。差別在於,如何隱藏資訊、如何簡潔地驗證跟如何達到非互動性。
快轉一下 SNARK 是如何運作的。
Alice 有多項式 P(x)、Bob有秘密 s,Alice 不知道 s、Bob 不知道 P(x)的狀況下,Bob 可以驗證P(s)。藉由同態隱藏(Homomorphic Hindings)隱藏Bob的 s → H(s),藉由 QAP/Pinocchio 達到了簡潔地驗證,然後把 H(s) 放到CRS(Common Reference String),解決了非互動性。細節可以參考之前的文章 。
問題轉換
零知識的第一步,需要先把「問題」轉成可以運算的多項式去做運算。這一小節,只會說明怎麼把問題轉成多項式,至於如何轉換的細節,不會多琢磨。
問題 → 限制條件 → 多項式
在 SNRAK 跟 STARK 都是藉由高維度的多項式來作驗證。也就是若多項式為: x³ + 3x² + 3 = 0,多項式解容易被破解猜出,若多項式為 x^2000000 + x^1999999 + … 則難度會高非常多。
第一步,先把想驗證的問題,轉換成多項式。
這邊以Collatz Conjecture為例子,什麼是Collatz Conjecture呢?(每次都用Fibonacci做為例子有點無聊 XD)
1. 若數字為偶數,則除以2
2. 若數字為奇數,則乘以3再加1 (3n+1)
任何正整數,經由上述兩個規則,最終結果會為 1 。(目前尚未被證明這個猜想一定成立,但也還未找出不成立的數字)
52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1.
把每個運算過程的結果紀錄起來,這個叫做執行軌跡(Execution Trace),如上述52 -> 26 -> … -> 1。接著我們把執行軌跡轉換成多項式(由執行軌跡轉成多項式不是這裡的重點,這裡不會贅述,細節可以參考 StarkWare的文章 )如下
https://medium.com/starkware/arithmetization-i-15c046390862
合成多項式
接著就把這四個限制條件的多項式合成為一個,這個最終的多項式就叫做合成多項式(composition polynomial),而這個合成多項式就是後面要拿來驗證的多項式。
就像一開始提的,SNARK跟STARK都是使用高維度多項式,接著,來介紹STARK是藉由哪些方式,達到零知識的交換、透明性(Transparency)跟可擴展性(Scalability)。
修改多項式維度
這一步是為了後面驗證做準備的。在驗證過程使用了一個技巧,將多項式以2的次方一直遞減為常數項(D, D/2, D/4 … 1),大幅減低了驗證的複雜度。因此,需要先將多項式修改為2^n維度
假設上述的每個限制多項式(不是合成多項式喔)為Cj(x),維度為 Dj,D >= Dj 且 D 等於2^n,為了達到 D 維度,乘上一個維度(D -Dj)的多項式,
所以最終的合成多項式,如下
其中的αj、βj是由驗證者(verifier)所提供,所以最終的多項式是由證明方(prover)跟驗證方所共同組成。
*這小節的重點是將多項式修改成D維度,覺得多項式太煩可忽略
FRI
FRI 的全名是”Fast RS IOPP”(RS = “Reed-Solomon”, IOPP = “Interactive Oracle Proofs of Proximity”)。藉由FRI可以達到簡潔地驗證多項式。在介紹FRI 之前,先來討論要怎麼證明你知道多項式 f(x) 為何?
RS 糾刪碼:
糾刪碼的概念是把原本的資料作延伸,使得部分資料即可以做驗證與可容錯。其方式是將資料組成多項式,藉由驗證多項式來驗證資料是否正確。舉例來說,有d個點可以組成 d-1 維的多項式 y = f(x),藉由驗證 f(z1) ?= y,來確定 z1是否是正確資料。
回到上面的問題,怎麼證明知道多項式?最直接的方式就是直接帶入點求解。藉由糾刪碼的方式,假設有d+1個點,根據Lagrange插值法,可以得到一個 d 維的多項式 h(x),如果如果兩個多項式在(某個範圍內)任意 d 點上都相同( f(z) = h(z), z = z1, z2…zd),即可證明我知道 f(x)。但是我們面對的是高維度的多項式,d 是1、2百萬,這樣的測試太沒效率,且不可行。FRI 解決了這個問題,驗證次數由百萬次變成數十次。
降低複雜度
假設最終的合成多項式為 f(x),藉由將原本的1元多項式改成2元多項式,以減少多項式的維度。假設 f(x) = 1744 * x^{185423},加入第二變數 y,使 y = x^{1000},所以多項式可改寫為 g(x, y) = 1744*x^{423}*y^{185}。藉由這樣的方式,從本來10萬的維度變成1千,藉由這種技巧大幅降低多項式的維度。在 FRI 目前的實做,是將維度對半降低 y = x²(f(x) = g(x, x²))。
此外,還有另一個技巧,將一個多項式拆成兩個較小的多項式,把偶數次方跟奇數次方拆開,如下:
f(x)= g(x²) + xh(x²)
假如:
f(x) = a0 + a1x + a2x² + a3x³ + a4x⁴ + a5x⁵
g(x²) = a0 + a2x² + a4x⁴, (g(x) = a0 + a2x + a4x²)
h(x²) = a1x + a3x² + a5x⁴, (h(x) = a1 + a3x + a5x² )
藉由這兩個方法,可以將高維度的多項式拆解,重複地將維度對半再對半,以此類推到常數項。而 FRI 協議在流程上包含兩階段 — 「提交」跟「查詢」。
提交階段:提交階段就如同上述過程,將多項式拆解後,由驗證者提供一亂數,組成新的多項式,再繼續對多項式拆解,一直重複。
f(x) = f0(x) = g0(x²) + x*h0(x²)
==> f1(x) = g0(x) + α0*h0(x), ← α0(驗證者提供)
==> f2(x) = g1(x) + α1*h1(x), ← α1(驗證者提供)
==> . . .
查詢階段:這個階段要驗證證明者所提交的多項式 f0(x), f1(x), f2(x), … 是否正確,這邊運用一個技巧,帶入任意數 z 及 -z(這代表在選域的時候,需滿足 L²= {x²:x ∊ L},這邊不多提)。所以可以得
f0(z) = g0(z²) + z*h0(z²)
f0(-z) = g0(z²) -z*h0(z²)
藉由兩者相加、相減,及可得g0(z²)、h0(z²),則可以計算出f1(z²),再推導出f1(x),以此類推驗證證明者傳來的多項式。
Interactive Oracle Proofs (IOPs)
藉由FRI(RS糾刪碼、IOPs),將驗證次數由數百萬降至20–30次(log2(d)),達到了簡潔地驗證。不過,我們解決了複雜度,但還有互動性!
* 與SNARK比較 :SNARK在驗證方面利用了QAP跟Pinocchio協定。
非互動性
藉由 Micali 建構(Micali construction)這個概念來解釋如何達到非互動的驗證。Micali 建構包括兩部分,PCPs(Probabilistically checkable proof)跟雜湊函數。PCPs 這是一個隨機抽樣檢查的證明系統。簡單來說,證明者產出一個大資料量的證明(long proof),經由隨機抽樣來驗證這個大資料量的證明。過程大約是這樣,證明者產出證明𝚿,而驗證者隨機確認 n 個點是否正確。
在STARK,我們希望達到:1.小的證明量,2.非互動。隨機抽樣可以讓達到小的證明量,那互動性呢? 想法很簡單,就是預先抽樣,把原本 PCPs 要做的事先做完,然後產出只有原本證明 𝚿 抽樣出的幾個區塊當作證明。但想也知道,一定不會是由證明者抽樣,因為這樣就可以作假。這裡是使用 Fiat-Shamir Heuristic 來作預先取樣。
首先,先把證明 𝚿組成 merkle tree,接著把 merkle root 做雜湊可得到一亂數 𝛒,而 𝛒 就是取樣的索引值。將利用𝛒取出來的區塊證明、區塊證明的 merkle tree 路徑跟 merkle root, 組一起,即為STARK 證明 𝛑。
到目前,只使用雜湊函數這個密碼學的輕量演算法。而雜湊函數的選擇是這個證明系統唯一的全域參數(大家都需要知道的),不像是 SNARK 有 KCA 使用的(α, β, 𝛾)等全域的秘密參數,再藉由 HH(同態隱藏)隱藏這些資訊來產生 CRS。因為證明的驗證是靠公開的雜湊函數,並不需要預先產生的秘密,因此 STARK 可以達到透明性,也不用可信任的設置。
接著,將FRI中需要互動的部分(驗證者提供 α 變數),使用上述的 PCP + Fiat-Shamir Heuristic, 即可達到非互動性。
* 與SNARK比較: SANRK 的非互動性是將所需的全域參數放到CRS中,因為全域參數是公開的,所以CRS裡的值使用了 HH 做隱藏。
MIMC
大部分證明系統,會使用算數電路來實作,此時,電路的複雜程度就關係到證明產生的速度。 STARK 的雜湊函數選用了電路複雜度較簡單的 MIMC,計算過程如下:
https://vitalik.ca/general/2018/07/21/starks_part_3.html
這樣的計算有另一個特性,就是無法平行運算,但卻又很好驗證,因此也很適合 VDF 的運算。Vitalik有一個使用 MIMIC 作為 VDF 的提案。
ps. 反向運算比正向慢百倍,所以會是反向計算,正向驗證
從上面的解釋,可以理解為什麼 STARK 不需要可信任設置,至於為什麼能抗量子?因為 SNARK 中使用了 HH 來隱藏秘密,而 HH 是依靠橢圓曲線的特性,但橢圓曲線沒有抗量子的特性(也就是可以從公鑰回推私鑰)。而STARK在整個過程中只使用了雜湊函數,而目前還沒有有效的演算法能破解雜湊函數,因此可以抵抗抗量子攻擊。
有錯誤或是不同看法,歡迎指教
參考:
StarkDEX Deep Dive: the STARK Core Engine
STARK 系列文:
STARK Math: The Journey Begins
Arithmetization I
Arithmetization II
Low Degree Testing
A Framework for Efficient STARKs
Vitalik 系列文:
STARKs, Part I: Proofs with Polynomials
STARKs, Part II: Thank Goodness It’s FRI-day
STARKs, Part 3: Into the Weeds
ZK-STARKs — Create Verifiable Trust, even against Quantum Computers
https://ethereum.stackexchange.com/questions/59145/zk-snarks-vs-zk-starks-vs-bulletproofs-updated
Originally published at http://kimiwublog.blogspot.com on November 12, 2019.
瞭解神秘的 ZK-STARKs was originally published in Taipei Ethereum Meetup on Medium, where people are continuing the conversation by highlighting and responding to this story.
👏 歡迎轉載分享鼓掌
「general bytes」的推薦目錄:
- 關於general bytes 在 Taipei Ethereum Meetup Facebook 的最佳解答
- 關於general bytes 在 Taipei Ethereum Meetup Facebook 的最佳解答
- 關於general bytes 在 General Bytes - Home - Facebook 的評價
- 關於general bytes 在 GENERAL BYTES - YouTube 的評價
- 關於general bytes 在 GENERAL BYTES - GitHub 的評價
- 關於general bytes 在 Golang bitwise operations as well as general byte manipulation 的評價
general bytes 在 Taipei Ethereum Meetup Facebook 的最佳解答
📜 [專欄新文章] ZK Rollup一開始提出來的時候,是被定義為layer 2的解決方案,年初的時候一度以Plasma…
✍️ Kimi Wu
📥 歡迎投稿: https://medium.com/taipei-ethereum-meetup #徵技術分享文 #使用心得 #教學文 #medium
ZK Rollup & Optimistic Rollup
ZK Rollup不是一個新的提案,大約在一年前被Barry Whitehat所提出,同時間Vitalik在以太坊研究員的論壇有一篇比較完整的文章解釋,現在由Matter Lab在開發。研究完zk-SNARKs之後,一直沒空來看,直到最近才有機會來深入瞭解。除了ZK Rollup,也會簡單帶一下前陣子在Plasma Group所提出的 Optimistic Rollup。
ZK Rollup一開始提出來的時候,是被定義為layer 2的解決方案,年初的時候一度以Plasma Ignis這個名稱作為發表。應該是因為去年Plasma很紅,一直不斷有新的提案跟進展,加上這當時也被定義為layer 2的解決方案,這些種種原因,開發者就冠上了Plasma的名稱,不過因為這項技術跟Plasma的精神完全不一樣,被社群抗議,後來就恢復到Rollup這個名稱(開發者的聲明),所以搜尋 ‘Plasma Ignis’會找不到什麼東西。到最近,Rollup被更名為semi-layer 2的解決方案,就是有一點layer 2但又沒這麼layer 2… XD
簡單一句話解釋ZK Rollup就是,資料放在鏈上的layer 2解決方案。在瞭解ZK Rollup之前,先來解釋原本layer 2有什麼問題。以Plasma為例,Plasma鏈只把Plasma區塊的hash放上Ethereum主鏈上做公正(欲瞭解Plasma可以參考這裡),也就是在鏈下交易了數百或數千筆的交易,最後上鏈只有幾十個bytes,這是鏈下交易的精神,但也是設計上最麻煩的地方 — 資料的可取得性。
就是當有人要離開這個鏈時,需要一個額外的遊戲規則,在Plasma叫做挑戰期(因為鏈上沒有資料,需要側鏈參與者的提供證據),這衍生了有資料才能挑戰,所以大家都要存一定數量的資料,相較於跟主鏈的互動,只需要裝一個錢包,並不需要下載區塊資料,使用者體驗上差異很大。挑戰期的另一個問題是,使用者需要保持上線狀態,不然錯過挑戰期,就代表默認了交易(因為是採用詐欺證明並非是有效性證明)。簡單來說,因為資料的可取得性問題,衍生了
1.使用者需要常在線上2. 需下載部分資料
而造成使用者體驗很糟(當然現在的Plasma設計已經改進了不少)
如何資料放在鏈上,又不會造成資料過大呢?
首先,先介紹整體架構。跟Plasma一樣,有一個智能合約做擔保,有中繼者(relayer)幫忙送交易到智能合約(在Plasma叫operator),中繼者除了送交易外,還需要產生SNARK證明,一起送上鏈做驗證。
智能合約的部分,可以想像跟ERC20一樣,在合約裡記每個參與者的帳,差別在於,標準的ERC20交易是由Ethereum這系統做驗證,也因此不能合併(因為這就是Ethereum的標準交易),而Rollup中,是把好幾筆交易包成一個標準交易,對Ethereum這個系統,就是一個交易,而驗證交易的有效性則由智能合約做驗證。
實際在智能合約裡,用兩個merkle tree做紀錄,一棵樹是紀錄地址,所以只需要樹的索引值就可以代表一個位址(未註冊的索引值內容為0),因此位址的資料量就從原本的20 bytes減少到只有3 bytes,另一棵樹則記錄balance跟nonce。
Merkle Tree of Addresses
這是資料格式(這是最初的提案,後來的實作交易量更小),
因為用索引值當地址的代表,所以只需要3 bytes(2²⁴個位址),Value的部分是以10^-6當作基底,這樣只需要15 bytes就可以代表一筆交易,而儲存這樣一筆交易大約只需要 892 gas(雖然Value是6 bytes,但是文章中的假設大部分的交易只會使用到4 bytes,所以算法是13 bytes * 68 + 2 bytes * 4 = 892),而一般ether的轉移需要21K gas,因此交易速度能提升(所以Vitalik的文章標題是”On-chain scaling to potentially ~500 tx/sec through mass tx validation”)。
https://vitalik.ca/general/2019/08/28/hybrid_layer_2.html
為什麼交易速度能提升?也順便來瞭解一下交易速度
現今以太坊每個區塊的gas上限約8M,所以若單純ether交易,速度約略是
8M / 21K / 15 ~= 25 tps
所以現在的交易瓶頸其實是gas 的問題,下降交易手續費或是提升區塊gas上限,都能適時紓困(但也會造成衍伸的問題),而ZK Rollup就是藉由交易數據量(size)的減少,進而能增加交易速度。那來看一下使用ZK Rollup後交易速度能到多快
(8M — 600K (zk-SNARK驗證) — 50K(預計合約運行的gas花費)) / 892 / 15 ~= 550 tps
這個數字就是Vitalik文章的標頭”On-chain scaling to potentially ~500 tx/sec”。但實際上並沒有這麼理想,在作者Barry的實作中,大約只有268 tps,因為每次資產的更新都會留下event,所以有多餘的gas花費,然而,這樣的設計在應用上也是比較親切的。
資料都在鏈上,而且透過zk-SNARK做驗證,代表著上鏈的資料都是被驗證過的,因此就沒有一開始layer 2遇到的問題,需要挑戰、需要下載資料等等。這也隱含著不需要信任中繼者,因為他們無法作壞,最多就是不幫你送交易。
事情沒有這麼美好…
大家都覺得zk-SNARK像個萬靈丹一樣,用了好像什麼事都解決了,不過實際上並沒有這麼完美。zk-SNARK除了需要初始設定之外,最大的問題就是需要大量的運算力,在 Barry提供的數據中,中繼者的電腦若是一台8G記憶體加上20G的硬碟swap,大概只能產生 20 tx/sec,遠遠不及預期的500tps或是實作的200多tps。所以這個方案最大的問題在於要怎麼解決算力問題。
平行運算!
Matter Lab使用了多中繼者模型跟平行運算。多中繼者的模型,很像小型的區塊鏈,使用了DPOS (Delegated Proof of Stake),還有隨機挑選區塊產生者,所以被挑選到的區塊產生者,就可以收集交易、產生證明並且上鏈。這樣的方法避免了中心化,若中繼者被惡意攻擊,整個網路還是能運作得下去,另一方面,也為平行運算做了鋪路。零知識證明的產生非常花時間,因此基於多中繼者模型,Matter Lab提出了”上鏈-驗證”兩階段的方式,也就是中繼者先把資料上鏈,下一個階段再上傳證明做驗證,進而達到平行運算(如下圖)。再加上一些資料的最佳化,測試結果可達到1600 tps。
https://medium.com/matter-labs/introducing-matter-testnet-502fab5a6f17
延遲…
聽似很美好,但是因為你的交易被分兩階段上鏈,也就是從送出到到被驗證,會是好幾個區塊,時間比原本單純上鏈時間會更久。當然,延遲多久是使用者可接受的,這目前也無從得知。這是一個取捨,省了手續費,增加了交易速度,卻也增加了時間的延遲,這一切也要等上線後才會知道。
今年初,Vitalik在台北的線下聚會中分享了ZK Rollup的進階版 — ZK ZK Rollup,有興趣的人可以參考這篇文章,記錄的很詳細。
Plasma & Optimistic Rollup
Optimistic Rollup在設計上跟Plasma相關,所以只會簡單帶一下差異。
Karl(註)基於ZK Rollup的設計,在上個月提出Optimistic Rollup,概念上也是把資料都放鏈上,但不是用zk-SNARK做驗證,因為希望能達成更普遍性的應用。而不一樣的地方有,把from的部分,改為使用者的簽章(65 bytes),因為資料量變大的,可想而知,花的gas會更多,交易速度就會不及ZK Rollup。另一部份是,因為不是用zk-SNARK做驗證,就需要資料驗證的輔助方法(validity game),這邊就不詳細介紹,有機會在寫一篇Plasma/Optimistic Rollup的詳細介紹。在估算上,交易速度約是100 tps,若簽章方式改為BLS,約可提升到450 tps。而在10月的硬分岔後,gas會下降,預估的交易速度也會分別到達400/2000 tps。(許願:希望有人可以介紹一下10月的硬分岔細節 XD)
註:在中文的媒體文章中,都稱他是Casper的核心研究員之一,但是從我一開始知道這個人,都是在大力宣揚Plasma,他的部落格、twitter都是跟Plasma相關的文章,不確定他在Plasma Group的角色,但我是把他定位成Plasma Group的 leader
文章內容若有錯誤或是不同觀點,歡迎指教
references:On-chain scaling to potentially ~500 tx/sec through mass tx validationIntroducing Matter TestnetOptimistic Rollup
ZK Rollup一開始提出來的時候,是被定義為layer 2的解決方案,年初的時候一度以Plasma… was originally published in Taipei Ethereum Meetup on Medium, where people are continuing the conversation by highlighting and responding to this story.
👏 歡迎轉載分享鼓掌
general bytes 在 GENERAL BYTES - YouTube 的推薦與評價
How to buy bitcoin. •. 226,747 views 3 years ago. How to buy bitcoin, like a boss, on a GENERAL BYTES #cryptocurrency ATM in 20 seconds! ... <看更多>
general bytes 在 GENERAL BYTES - GitHub 的推薦與評價
XChange Public. XChange is a Java library providing a streamlined API for interacting with 60+ Bitcoin and Altcoin exchanges providing a consistent ... ... <看更多>
general bytes 在 General Bytes - Home - Facebook 的推薦與評價
All our clients now can sync General Bytes Bitcoin ATMs with Coin ATM Map! Thousands of BATMs installed around the world allow end users to purchase or sell ... ... <看更多>