Kimi的筆記

零知識證明在過去一年越來越廣為人知，去年(2019)也有越來越多的專案是基於零知識證明。前年底提出的 zk rollup，目前由  Matter Labs  在開發，Matter Labs更在上個月（2019/12）發表了  ZK Sync ，解決了因為產生證明（proof）而延伸的延遲問題。此外  Iden3  跟 ConsenSys  也有 zk rollup 的專案。在以太坊研究論壇有基於 zk rollup 所衍生的 匿名 zk rollup 。 Semaphore 是一個基於零知識證明的一個訊號系統，發送者可以不揭露身份的狀況下廣播任何訊息(an arbitrary string)。 Semaphorejs 延續 Semaphore 的核心概念，並將整個概念更加完整化，從前端網頁到後端服務。這兩年才發表的 zk-STARKs，也在去年年初跟 0x 合作，推出基於 zk-STARKs 的 去中心化交易所 。 在技術上，去年下半年有新的論文，使用 DARK compiler 可以讓 SNARKs 達到公開性（Transparent）。還有 MARLIN, SONIC, PLONK 等可通用且可更新的可信設定（trusted setup）。STARKs 的 FRI 驗證方式也默默地跟 SNARKs 做結合。（東西越來越多，根本看不完 QQ） 這篇文章沒有要談高深的技術，只會介紹實做所需的知識。這篇會使用到 Iden3 所開發語言  circom  來幫助寫算數迴路 。藉由 circom，可以更輕鬆地實做零知識證明的程式。但在開始之前，先介紹一些基本觀念。 算數迴路 在實做零知識程式跟一般撰寫程式不同，需要先把問題轉成迴路，才去執行（實際上是把 問題 轉成 多項式 再轉成 迴路 ）。舉例來說，一個多項式 $x^3 + x +5$，會轉成像這樣的迴路 sym_1 = x * x // sym_1 = x^2 sym_2 = sym_1 * x // sym_2 = x^3 y = sym_2 + x // y = x^3 + x ~out = y + 5 ...

上一篇關於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 ...