Ethereum RNG (RANDAO & VDF)

-


RNG是Random Number Generator，也就是亂數產生器
在現實世界中要產生真正的隨機數，其實不容易，各個語言的library所提供的隨機數，都是偽隨機數，是可以預測的，不過在大部分的應用場域，都是可以應付的。區塊鏈的世界，面對的是全世界的人，怎麼產生不可預測的隨機數，就很重要，不然就可以被有心人所操作。例如Ethereum Beacon chain(POS chain)中的validator/attester(產塊跟驗證的角色)，若是可以被預測，那大概就沒有人會相信這條鏈了。而這也是Ethereum Serenity(Eth-2.0)，所遇到的問題之一。目前隨機數的產生，就由RANDOA + VDF所產生，以下就分別介紹

ＲＡＮＤＡＯ

RANDAO是利用經濟模式（獎勵跟處罰）的方式，促使在公共場域中能產生隨機變數

原理很簡單，想參加的人把拿錢來抵押，需要產生隨機數的人要付錢。所以參加者就可以從中分潤，當然不守規矩抵押的錢也就會被沒收，利用獎勵跟處罰的方式迫使大家都守規矩。詳細步驟如下：

  1. 首先，會有個收集seed的時間，例如6個block的時間。接著，想參與的人，投入某個數量的ETH到RANDAO這個smart contract（作質押），然後附上secret（某個只有你知道的值s，然後作sha3）。
  2. 等收集時間結束，就是驗證時間。此階段所有參與著需要把s傳入smart contract做驗證，smart contract會把s作sha3，去驗證是不是跟第一階段傳進來的一致。最終會把驗證過的s當作seed去產生隨機數。
  3. 最後，就是產生隨機數，然後把隨機數傳給之前有請求過的contract。然後歸還質押的ETH跟利潤分給參與者。
此外有幾個附加條件
  1. 第一階段若收集到數筆一樣的secret，只接受第一筆
  2. 第一階段會規定基本人數，若結束後未到達人數門檻，則此次的產生就失敗
  3. 若第二階段需提供s
    1. 若未提供，則質押的ETH會被沒收
    2. 若此階段有一個以上參與著未提供s，則此次產生失敗，並且把沒收的ETH分給有提供s的參與者。且退還請求者所支付的ETH。


ＶＤＦ

VDF 全名為Verifiable delay functions，從字面上有點難懂在幹嘛，從運作方面做解釋，就是輸入一個值，然後運算一段時間(delay)，得出一個結果，最後這個結果是可以被輕易驗證的。如下列算式， 

                f(x) = g(g(g(g(....g(x)....)))) 
                where g(x) = xor(x^((p+1)/4), 1) mod p
        其反函數為
                 h(x) = xor(x, 1)^2 mod p

上面提到「運算一段時間」的運算，其實是重複做同一種運算，從數學式看就很清楚，把x帶入g(x)，然後把算出的結果再帶入g(x)。所以同一段時間，如果能迭代的次數比其他人多，那其他人就猜不到結果，也就沒辦法預測亂數結果。


最後，介紹一下這兩個方法怎麼運用在Ethereum Serenity中
首先，RANDAO會在內建在Beacon chain的邏輯中，而不是一個獨立的smart contract，但RANDAO有個缺點，就是最後一位可以預測/操縱結果。如下圖，因為最後一位可以知道前面的值，所以在最後可以決定要出值或是不出，因此可以操縱結果。(目前epoch是64個slot，而每個slot是6秒，所以epoch約是6.4 minutes)



所以設計上除了RANDAO，還多一層VDF。
VDF把RANDAO產生出來的亂數當種子去產生亂數，而且計算時間要夠長（至少要一個epoch，目前規劃是10個epoch，不過相信還會有變動），如下
source : Justin Drake slides on DevCon4

實際的lifecycle會像這樣，在VDF計算完後，會有一個epoch的緩衝讓這個亂數可以上鏈，然後接著下一個RANDAO mixing。


但問題來了，怎麼確保沒有人算得比你快？？
所以Ethereum Foundation計畫做硬體，設計新的ASIC晶片來計算VDF，以確保沒人可以預測最終的亂數。實際設計當然不是Foundation的researcher們，他們找了學界跟產業的IC design專家做設計，因為硬體研發費用龐大，Filecoin也一起支援這項計畫。

更多細節的部分，可以參考Minimal VDF randomness beacon


other references : 

留言

張貼留言

這個網誌中的熱門文章

What's New in Ethereum Serenity (2.0)

-
圖片
Ethereum 2.0 已經正式改名為Ethereum Serenity 原本預計在今年(2018)上線的Hybrid POS(Casper FFG)跟sharding，因為遇到一些技術上的困難，所以把Hybrid POS改成單純POS，然後因為sharding跟POS有部份技術是重疊的，所以把POS跟sharding併在一起做（本來是分成兩個team作開發） Beacon Chain 在Ethereum Serenity的規劃中，在原本的POW chain之外多一個鏈叫做 Beacon chain ，是一個POS chain。在Beacon chain中有兩種角色 proposer 跟 attester ，proposer就是產塊的人，attester是驗證的人。而在POW chain上存入32 ETH，可以成為Beacon chain上的 validator ，而validator有權利產塊(proposer)，也會有機會被選attester。此外，延續了Casper FFG finality這個概念，也就是在finality之後的狀態就是正確的狀態（不可回復），不像POW一般需要6個塊的時間才能確認交易是不會被更改的（POW的狀態確認是機率，六個塊之後有"很高的機率"是無法被改變的，而finality就像是0跟1一樣，沒有中間）。 聽到這，好像覺得很簡單，但是在實作上會遇到幾個問題，首先，怎麼決定誰是proposer誰是attester，如果亂數的隨機性不夠，就很容易被遭到操控。接下來是，每次驗證都需要做一次簽名，因為32個ETH就可以當validator/attester，每次驗證可能會有10~20幾萬的簽章（ 簽章數量的預估方法 ），驗完簽章天都黑了 ＸＤ。 ＲＮＧ 針對亂數產生（ RNG , Random Number Generator），使用 RANDAO 跟 VDF ，RANDAO是個利用經濟獎勵的機制來產生亂數，原始的設計是在smart contract上，而在Beacin chain會直接實作這個邏輯。而VDF是一個delay function，因為速度的關係，基金會打算自己開發ASIC晶片。關於這RNG之後會再寫一篇 詳細解釋 。 Signature Aggregatio...
閱讀完整內容

瑞士滑雪分享2 - 策馬特

-
圖片
本篇同 上一篇 ，只介紹滑雪資訊，關於觀光資訊，就不在這裡詳述 一樣，我們先來介紹策馬特/馬特洪峰，這裡一樣是分兩區，Zermatt跟International，如下圖，左邊紅色框是 Zermatt ，而 International 是Zermatt+Italy，也就是 全山卷 ，在Zermatt賣的就這兩種票 在這我一樣只有滑兩天，就只買了Zermatt的票，所以不要再問我買International需要不要護照之類的問題，我不知道阿~~ XD 我住在Zermatt，這個鎮還滿大的，所以在挑住宿的時候需要注意一下，Zermatt的住宿非常的貴，比Grindelwald貴上許多，所以也有人選擇住下面的小鎮，再坐火車到Zermatt，至於住哪個小鎮或是便宜多少，我沒有研究，就不知道了。Zermatt火車站一出來，就有往山上的小火車，所以住下面的小鎮要上山滑雪，也算滿方便的。 Zermatt雪場分三區，最左邊Rothorn，中間Gornergrat，最右邊Matterhorn Glacier Paradise。 Rothorn ：要搭小火車上山，滿特別的，詳細介紹可參考 這篇網誌 ，離Zermatt火車站約10分鐘的路程。 Gornergrat ：一出火車站，對面就是車站了，小火車直接拉到山頂，相當方便 Gornergrat車站 Matterhorn Glacier Paradise ：上山纜車離市區相當遠，走路大約要20-25分鐘（有接駁巴士），需要轉2次纜車才能到山頂，要花不少時間，山頂非常冷，滑道很平緩，又冷又不好玩 三座山基本上可以互通，不需要回到小鎮再上山。這裡高度大都在2000-3000公尺，所以雪況比少女峰好很多，不過相當多的平路，對snowborders相當不友善....。 完整的地圖可參考： Zermatt ski map 雪票價格如下，這裡的雪票是用磁卡，所以會有5CHF的押金，最後記得去退（像我就忘了...@@） Zermatt/International ski pass (2014/15) ： Zermatt International (Zermatt - Cervinia) Days Adults You...
閱讀完整內容

動手實做零知識 - 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 ...
閱讀完整內容