發表文章

目前顯示的是 11月, 2019的文章

瞭解神秘的 ZK-STARKs

圖片
上一篇關於zkSNARK扯到太多數學式,導致很難入手,這次介紹STARK會盡量減少數學式,以原理的方式跟大家介紹。 STARK被視為新一代的SNARK,除了速度較快之外,最重要的是有以下好處 1. 不需要可信任的設置(trusted setup),以及 2. 抗量子攻擊 但也沒這麼完美,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^3 + 3x^2 + 3 = 0$,多項式解容易被破解猜出,若多項式為 $x^{2000000} + x^{1999999} + ...$則難度會高非常多。 第一步,先把想驗證的問題,轉換成多項式。 這邊以 Collatz Conjecture 為例子,什麼是Collatz Conjecture呢?(每次都用Fibonacci做為例子有點無聊 XD) 1. 若數字為偶數,則除以2 2.