📜 [專欄新文章] Ethereum RNG (RANDAO & VDF)
✍️ Kimi Wu
📥 歡迎投稿： https://medium.com/taipei-ethereum-meetup #徵技術分享文 #使用心得 #教學文 #medium
Ethereum RNG solution（RANDAO & VDF）
RNG是Random Number Generator，也就是亂數產生器
在現實世界中要產生真正的隨機數，其實不容易，各個語言的library所提供的隨機數，都是偽隨機數，是可以預測的，不過在大部分的應用場域，都是可以應付的。區塊鏈的世界，面對的是全世界的人，怎麼產生不可預測的隨機數，就很重要，不然就可以被有心人所操作。例如Ethereum Beacon chain(POS chain)中的validator/attester(產塊跟驗證的角色)，若是可以被預測，那大概就沒有人會相信這條鏈了。而這也是Ethereum Serenity(Eth-2.0)，所遇到的問題之一。目前隨機數的產生，就由RANDOA + VDF所產生，以下就分別介紹
ＲＡＮＤＡＯ
RANDAO是利用經濟模式（獎勵跟處罰）的方式，促使在公共場域中能產生隨機變數
原理很簡單，想參加的人把拿錢來抵押，需要產生隨機數的人要付錢。所以參加者就可以從中分潤，當然不守規矩抵押的錢也就會被沒收，利用獎勵跟處罰的方式迫使大家都守規矩。詳細步驟如下：
首先，會有個收集seed的時間，例如6個block的時間。接著，想參與的人，投入某個數量的ETH到RANDAO這個smart contract（作質押），然後附上secret（某個只有你知道的值s，然後作sha3）。
等收集時間結束，就是驗證時間。此階段所有參與著需要把s傳入smart contract做驗證，smart contract會把s作sha3，去驗證是不是跟第一階段傳進來的一致。最終會把驗證過的s當作seed去產生隨機數。
最後，就是產生隨機數，然後把隨機數傳給之前有請求過的contract。然後歸還質押的ETH跟利潤分給參與者。
此外有幾個附加條件
第一階段若收集到數筆一樣的secret，只接受第一筆
第一階段會規定基本人數，若結束後未到達人數門檻，則此次的產生就失敗
若第二階段需提供s3.1 若未提供，則質押的ETH會被沒收3.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)² mod p
上面提到「運算一段時間」的運算，其實是重複做同一種運算，從數學式看就很清楚，把x帶入g(x)，然後把算出的結果再帶入g(x)。所以同一段時間，如果能迭代的次數比其他人多，那其他人就猜不到結果，也就沒辦法預測亂數結果。
最後，介紹一下這兩個方法怎麼運用在Ethereum Serenity中
首先，RANDAO會在內建在Beacon chain的邏輯中，而不是一個獨立的smart contract，但RANDAO有個缺點，就是最後一位可以預測/操縱結果。如下圖，因為最後一位可以知道前面的值，所以在最後可以決定要出值或是不出，因此可以操縱結果。(目前epoch是64個slot，而每個slot是6秒，所以epoch約是6.4 minutes)
source : Justin Drake slides on DevCon4
所以設計上除了RANDAO，還多一層VDF。 VDF把RANDAO產生出來的亂數當種子去產生亂數，而且計算時間要夠長（至少要一個epoch，目前規劃是10個epoch，不過相信還會有變動），如下圖
source : Justin Drake slides on DevCon4
實際的lifecycle會像這樣，在VDF計算完後，會有一個epoch的緩衝讓這個亂數可以上鏈，然後接著下一個RANDAO mixing。
source : Justin Drake slides on DevCon4
但問題來了，怎麼確保沒有人算得比你快？？
所以Ethereum Foundation計畫做硬體，設計新的ASIC晶片來計算VDF，以確保沒人可以預測最終的亂數。實際設計當然不是Foundation的researcher們，他們找了學界跟產業的IC design專家做設計，因為硬體研發費用龐大，Filecoin也一起支援這項計畫。更多細節的部分，可以參考Minimal VDF randomness beacon
other references :RANDAO中文白皮書Justin Drake explains “Ethereum 2.0 randomness” on Devcon4
Originally published at kimiwublog.blogspot.com.
Ethereum RNG (RANDAO & VDF) was originally published in Taipei Ethereum Meetup on Medium, where people are continuing the conversation by highlighting and responding to this story.
👏 歡迎轉載分享鼓掌
xor計算 在 Re: [請問] 數學問題- 看板Math - 批踢踢實業坊 的推薦與評價
※ 引述《GoalBased (Artificail Intelligence)》之銘言：
: ※ [本文轉錄自 ask 看板 #1HTi2kk3 ]
: 作者: GoalBased (Artificail Intelligence) 看板: ask
: 標題: [請問] 數學問題
: 時間: Wed Apr 24 01:11:03 2013
: https://ppt.cc/zkN-
: 題目在上面，
: p1是x^3 / x^3+x+1 的 rem，也就是餘數的意思，
: 不過裡面的例子算出來好像都不是如此，
: 有人知道為什麼嗎?
: 他是怎麼算的呢?
個人覺得應該要解釋一下係數 mod 2 跟 XOR 關係何在 XD
首先這裡所討論的多項式是特別限制在 Z/2Z 下面的
也就是說這個多項式的係數只會是 0 跟 1 運算完要除以 2 取餘數
例如: (x^3) - (x^3 + x + 1) = - x - 1 = x + 1
這樣子的係數的加減運算如果仔細去看它 其實就只是下面這幾條式子而已:
0 + 0 = 0 0 - 0 = 0
0 + 1 = 1 0 - 1 = 1
1 + 0 = 1 1 - 0 = 1
1 + 1 = 0 1 - 1 = 0
由於係數只會是 0 或 1
我可以用一個固定長度的二進位數字來表示最多多少次的多項式
像是可以用三位二進位描述一個最多二次的這樣的多項式
(像是書裡用 011 表示 x + x^2 這個樣子)
而上面這些運算如果把 0 當 False, 1 當 True 的話
正好跟邏輯裡的 XOR (互斥或)運算是一模一樣的 (不管加減)
因此這種特別的多項式如果要寫成程式計算時
就會直接用跟它等同的二進位數值去進行 XOR 來運算
(像是書裡接下來可能會講到的檢查碼就會利用這個特性實作)
至於這種多項式的乘除法也跟普通的多項式除法差不多
所以除算可以直接寫長除法 當然裡面的加減就都是這些 XOR 運算了
那你真的把這個長除法寫下來就會變成上一篇回文裡的那個樣子
這就解釋了這裡的餘數是怎麼求出來的
--
'Oh, Harry, don't you see?' Hermione breathed. 'If she could have done
one thing to make absolutely sure that every single person in this school
will read your interview, it was banning it!'
---'Harry Potter and the order of the phoenix', P513
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.118.131.54
... <看更多>