發表文章

動手實做零知識 - circom

-
圖片
零知識證明在過去一年越來越廣為人知，去年(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 而 circom 就是一個將我們寫的邏輯（程式）轉成迴路的工具，不需要自己處理迴路。若你證明的內容需要雜湊或是簽章， circomlib  已經有實
張貼留言
閱讀完整內容

瞭解神秘的 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. 
1 則留言
閱讀完整內容

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設計已經改進了不少）
張貼留言
閱讀完整內容

Monero.門羅幣 隱匿交易的基礎介紹

-
圖片
今天要來簡單介紹一下，門羅幣是怎麼達到匿名交易的。本篇文章會牽涉到橢圓曲線的原理，如果不懂，可以先參考「 加密技术核心算法之安全快捷的ECC算法 」。簡單來說就是要知道這樣的關係：  p = k*G ,      p ：公鑰         k ：私鑰     G ：曲線上的基準點 門羅隱匿交易包含了三個技術： Ring Signature（環簽章） ,  Ring Confidential Transactions （RingCT, 環保密交易） 跟 Stealth Address（隱匿位址） 。在 Digital Asset Research 的文章 中這張圖解釋了各個技術所使用的地方，本篇文章，就是要介紹這三個技術。 source:  https://medium.com/digitalassetresearch/monero-becomes-bulletproof-f98c6408babf 在介紹之前，先了解門羅鏈有些基本概念。在門羅中有兩把key（其實是4把，因為各有私鑰跟公鑰），一把是 view key 另一把是 spend key 。顧名思義，一把是拿來看的自己餘額的（在鏈上找 隱匿位址 ），一把是拿來花的（做 環簽章 ）。由spend key可以產生 key image （ 金鑰映像 ），用來做預防雙花的證明，有點像zcash的nullifier。 Ring Signature （環簽章） 環簽章有點像混幣，就是把好幾筆交易混在一起，不過還是有差異，可以參考「 What are the technical advantages of Ring Signatures (CryptoNote) compared to CoinJoin? 」 那實際上怎麼做呢？！ 假設一個初始值v，跟一串隨機數$(y_1, y_2, ..., y_n)$，然後把v跟隨機數經由$E_k$做加密，再把加密過的值跟下一個隨機數做運算(xor)再加密，如：$E_k(y_{n-1} {\oplus} E_k(y_n{\oplus}v))$，所以函數如下 $$C_{k,v}(y_1, y_2, ..., y_n) = E_k(y_1 \oplus E_k(y_2 \oplus ... E_k(y_n \
張貼留言
閱讀完整內容

Data Availability on Ethereum 2.0 Light Node

-
圖片
本來是要展開一個叫做「與大神(C.C. Liang)共筆系列」，無奈C.C.太忙，最終還是只能自幹，不過依舊感謝 C.C. Liang 提供素材跟觀念釐清 data availability（資料可取得性） 跟 fraud proof （詐欺證明）對於區塊鏈交易量擴展，是很重要的兩項因素。當交易量大意味著資料量就變大（無論是分片或是加大區塊大小），而資料量越大，能夠運行全節點的人就會越少（因為硬體跟維護成本越高）。舉例來說，Ethereum 2.0 有1024 條鏈，不可能每個人都把1024條的資料都下載下來，更何況，這樣也失去分片的意義，但若某節點做分片A的validator，此時，需要跟分片B有所互動，不太可能把分片B的所有區塊都下載下來，太耗時也太佔空間，而且若如此設計，最終也會把全部的鏈都下載下來....。但是，若沒有全部的區塊那要怎麼驗證交易呢？！這就是「資料可取得性」的重要性。 資料可取得性簡單來說就是拿不拿得到資料，但不代表拿到的資料的有效的/正確的。那在討論資料可取得性問題之前，先來認識詐欺證明。 在區塊鏈世界中，驗證資料方式可以分為有效證明(validity proof) 跟詐欺證明兩種。有效證明就是現在區塊鏈的運作方式-「驗證資料是正確的，才能上鏈」，也就是當你需要轉帳時，礦工需要先驗證你的餘額是否足夠，確認你餘額是夠的（驗證資料是正確的）才會打包。而詐欺證明則是相反，驗證者收到交易之後，經過一段時間若沒有人提出異議/挑戰，那就代表你送出的交易是沒問題的，這種方式驗證成本相對較低，也因此大部分L2方案選擇使用詐欺證明作為資料驗證的方式。 而輕節點只下載部分的資料（通常是block header），要如何能在運作上幾乎跟全節點一樣可靠呢（'幾乎' 是因為輕節點需要額外的一些假設）？就必須借助資料可取得性跟詐欺證明的的合作。 Fishermen 漁夫（fishermen）機制是一種很直覺的設計方式，就是漁夫們觀察著網路上的無效資料，發現後送出詐欺證明以得到獎勵。 基本的獎懲機制如下， 1. 若有人提出無效的詐欺證明，則沒收押金， 2. 若有人提出有效的詐欺證明，送出無效資料的人會被沒收押金，而押金部份當作挑戰者（提出詐欺證明的人）的獎勵。 但是，這種機制在這個情境會有問題。我們來
張貼留言
閱讀完整內容

深入瞭解 zk-SNARKs

-
這篇文章主要是更深入介紹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 Circuit --&
張貼留言
閱讀完整內容

Upgradable smart contract using zos

-
smart contract跟一般程式最大的差異，就是smart contract上了鏈就不能改了（這是區塊鏈的特性也是優點，但是如果真的有bug，麻煩就大了...）。所以今天要介紹的是，如何用 ZeppelinOS 來實作upgradeable smart contract，可升級的smart contract。 版本  - zos: 2.1.0  - Truffle: 5.0.1 OpenZeppelin 對smart contract的開發者一定不陌生，提供相當多smart contract的範例程式。Zeppelin部落格有介紹如何使用proxy contract實作可升級的contract，這是他們 proxy patterns的設計 ，之後有機會再深入介紹proxy pattern。本篇主要在介紹如何使用 zos 部署可升級的contract。（本篇需要有使用過truffle的經驗） Deploy contracts 環境部分，先安裝Node.js跟npm，跟Ganache（或Ganache-cli）。 Deploy your first project 有詳細地介紹如何使用zos部署。 先安裝ZeppelinOS npm install --global zos 再來建立專案 mkdir MyProject cd MyProject 初始化專案 npm init zos init MyProject npm install zos-lib 這個時候，資料夾內容就跟下過 truffle init 一樣，有 contracts , migrations 資料夾， truffle-config.js 等。以上環境就都建置完成了，再來就是寫contract了，這裡直接用官方的範例 pragma solidity ^ 0.4 .24; import "zos-lib/contracts/Initializable.sol" ; contract MyContract is Initializable { uint256 public x; string public s; function initialize(uint256
張貼留言
閱讀完整內容