📜 [專欄新文章] 瞭解神秘的 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.
👏 歡迎轉載分享鼓掌
iops計算 在 台灣物聯網實驗室 IOT Labs Facebook 的最佳貼文
阿里雲物聯網、專有雲、視頻雲解決方案詳解
2016-4-20 18:35
隨著移動網際網路、物聯網、智能硬件的發展,人類對計算的需求越來越大,自行采購和維護數據基礎設施越來越讓企業難堪重負,曾經雲計算主要是為中小企業和創業者賦能,但現在越來越多的大型企業開始“上雲”,在雲棲大會深圳峰會上,阿里雲透露了包括中石化、中石油、12306、海關總署、國家電網、國稅總局、中國氣象局等等大中型政企客戶,雲計算已經全面覆蓋了大中小什至巨頭類型的企業。
隨著上雲企業的日趨增加,對雲計算的需求也日趨多樣化,4月20日,在雲棲大會·深圳峰會上,阿里雲重磅發布物聯網、專有雲(Apsara Stack)、混合雲、視頻雲四大解決方案,同時亮相的還有存儲、數據庫、安全、雲市場、域名交易平臺、阿里郵箱等多個領域的數十款為企業創造新價值的新品。
阿里巴巴物聯網平臺也在本次大會上正式發布,該平臺融合了雲上網關、規則引擎、共享智能平臺、智能服務集成等產品和服務,開發者能夠在這個平臺上輕松實現全球快速接入、跨廠商設備互聯互通、輕松調用第三方智能服務等,快速搭建穩定可靠的物聯網應用。
有“家電王國”之稱的慈溪市政府與阿里雲簽署了合作協議,雙方攜手推動家電產業智能化升級,從傳統的政策扶持、財政補貼升級到當下的“科技扶持與補貼”,以科技賦能中小家電企業。
出於自身數據中心利舊和數據本地化的考慮,大量客戶需要專屬的雲計算解決方案。對此阿里雲正式發布了專有雲解決方案Apsara Stack,可讓企業客戶實現在自有的數據中心內構建完整的專屬式雲計算服務,為客戶打造安全、可靠、彈性的雲計算工作環境。
阿里雲專有雲(Apsara Stack)基於經過大規模市場服務驗證的阿里雲公共雲平臺,並針對企業市場進行了二次優化,使之易交付、易管理,同時滿足了嚴苛的安全合規和可靠性要求。
阿里雲專有雲(Apsara Stack)提供了包括雲計算、大數據、企業級網際網路架構、安全等全棧雲產品的API和SDK,極大地滿足了定制化要求和生態建設。
Apsara Stack的發布,意味著企業用戶可以享受一致性體驗的“專有雲+公共雲”的混合雲服務,既能為本地數據中心賦予阿里雲同款雲架構能力,又能無縫獲取公共雲的彈性擴展能力,無需考慮軟件架構的差異。
當前,各類視頻應用出現爆發性增長,這與雲計算的普及密不可分。阿里雲此次發布視頻雲解決方案,提供一站式視頻點播、直播服務,集內容采集、上傳加速、存儲錄制、碼轉/截圖/水印、鑒黃服務、CDN分發及播放器等功能於一體,用戶可以非常簡單地借此開展自己的網絡視頻業務。
據介紹,阿里雲視頻點播方案幫助用戶大幅簡化自建視頻點播平臺的開發工作,在業內首次實現零編碼,1分鐘搭建完整視頻處理流程,同時兼顧用戶使用IaaS產品要求的自由可配置性。目前已經支持業內最先進的視頻編碼標準。
阿里雲視頻直播方案擁有先進實時轉碼技術,依托天貓淘寶同款CDN資源和高可靠存儲分發鏈路,能支撐1000萬路以上並發訪問。據測算,視頻雲端到端時延僅2秒,流暢度98%,在同等清晰度下,碼率低20%以上,這意味著客戶可以節省20%以上流量成本。
雲存儲市場近來出現一些新變化:用戶從關注存儲穩定、性價比以及數據如何傳輸,轉向如何及時有效地通過計算發現數據價值。
在大量政企客戶IT系統廣泛使用的文件存儲NAS也在本次雲棲大會正式推出。
NAS提供一個無限擴展的文件系統,使用標準文件協議nfs v3/v4版本,可靠性達到99.9999999%。
共享塊存儲也即將發布,支持空間多讀多寫,256TB容量、40000 IOPS、512MBps內存,支持Oracle RAC、SAP、GIS等應用。
表格存儲推出PB級容量型實例,價格同比下降70%;面向企業客戶的3年在線對象存儲合約發布,價格0.06元/GB/月。
去年雙11,阿里自研的金融級雲數據庫OceaNBAse支撐了每秒8.59萬筆支付,具備三中心同步容災能力,目前正式邀測。
同樣在去年雙11,阿里首秀交易支付的異地多活,其中有一項重要的數據傳輸技術Data Transmission,此次大會也正式產品化對外發布。Data Transmission堪稱企業數據遷移上雲必備利器,實時強一致同步達每秒30000條數據。
堪稱企業級海量數據庫的終極之選的PB級雲數據庫ApsaraDB for PetaData正式上線,它以低成本、高擴展性、兼容MySQL協議等特點受到企業客戶的歡迎。
從成立第一天起,安全就是阿里雲的第一屬性。本次大會雲盾家族又帶來兩款新產品:Web應用防火墻,先知計劃。
Web應用防火墻是一款網站、APP等Web應用的防護利器,重點保護用戶的Web應用程序,可以避免用戶的網站因為Web攻擊導致數據泄露、網頁篡改、用戶隱私泄露,也可以防禦CC攻擊、慢速CC攻擊、應用層CC攻擊,支持HTTPS。
此外,為了更好的幫助企業及早發現自身系統安全問題,阿里雲特別推出先知計劃,搭建白帽子、安全公司與企業之間隱秘溝通的橋梁。先知計劃旨在幫助企業建立“私密”漏洞收集中心,提前發現業務系統的安全風險,保證安全風險可以快速進行響應和修復,防止造成更大的安全損失。
大會發布全新軟件生態戰略,對現有雲市場進行全面升級,打造軟件交易與交付的第一平臺。包括用友、宏碁資訊、潤和軟件、駐雲、空橋克拉、曙安數據、疊雲、泛微、暢捷通、通達等近500家海內外知名軟件商的逾3000款軟件已入駐雲市場,用戶可通過阿里雲官網直接購買,一鍵開通“軟件+雲計算資源”。
除了存儲、數據庫、安全產品外,企業建站所需的郵箱、域名產品也有重要升級。“阿里雲郵”正式更名為“阿里郵箱”。更名後的阿里郵箱,除了提供更為安全穩定快速的郵箱基礎服務外,還為企業用戶打造了一站式的常用辦公需求解決方案,增加了審批流程、差旅出行等便捷應用,用戶可以簡單高效地通過郵箱完成日常辦公協同與事務管理。
域名交易平臺mi.aliyun.com正式開通。基於支付寶擔保交易打造的域名交易系統,為買賣雙方提供安全、便捷的域名交易服務。
雲解析智能解析升級,全面支持多線路運營商分省智能解析和多線路海外國家智能解析,覆蓋范圍包括移動、聯通、電信、教育網的全國31個省(市、自治區、直轄市)以及海外6大洲34個國家和地區。
資料來源:http://www.taiwanfansclub.com/article-374413-1.html