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 ...

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設計已經改進了不少） ...

這篇文章主要是更深入介紹zk-SNARKs，不可避免的會有”一些“數學出現，不過會盡量著重在數學式背後的意義，而不是深入探討數學公式，如果不知道什麼是zk-SNARKS的，可以先參考 這篇 跟 這篇 。 一開始的假設 1. Alice有一個多項式P(x) 2. Bob選一個點 s 給Alice 3. Alice回傳P(s)給Bob 希望能達到 1. Alice不知道點 s，Bob不知道多項式P(x)。(Blindness) 2. 但Alice可傳回P(s)給Bob，並且Bob可以驗證P(s)。(verifiable) 也就是雙方都不知道對方的資訊，卻可以共同得到一個可被驗證的結果 上面就是基本的假設。然後，先定義一些基本的數學式 上述所提的多項式定義為： $$P(x) = C_0+C_1x+C_2x^2 + ... + C_nx^n$$ 首先，先介紹Homomorphic Hiding( 同態隱藏 ) [1] ，藉由 同態隱藏 可以達到 隱藏資訊 的目的。我們從數學定義來看他有什麼特質。首先$E(x)$的定義為$E(x) = g^x$ ，然後 $E(x+y) = E(x)*E(y)$ HH支援線性相加，所以下列式子成立 $$E(ax+by) = g^{ax+by} = g^{ax}*g^{by} =E(x)^a + E(y)^b$$ * HH的假設：知道$E(x)$，是無法回推x的值 若我們對$P(x)$作 同態隱藏 ， 可以得出 $$E(P(x)) = E( C_0+C_1x+C_2x^2 + ... + C_d^d) = E(1)^{C_0} * E(s)^{C_1}*E(s^2)^{C_2}...E(s^d)^{C_d}$$ 也就是Bob只需要給$ E(1), E(s), E(s^2),...E(s^d)$，而不用給s（$E(s)$無法反推出s），Alice就可以得出E(P(s))的值。藉此可以達成第一點的blindness，接下來就是要如何達成verifiable，因為Alice有可能給一個假的值，非P(x)上的點，所以要確保Alice會乖乖地照規矩來。接下來就要介紹如何保證Alice會送出正確的結果，並且Bob可以驗證。 Computation --> Arithmetic Ci...