發表文章

動手實做零知識 - 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. 

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