文章閱讀頁通欄

昨晚河南22选5开奖号码是多少:隨機數和分布式網絡:實施

來源: 區塊網 作者:考拉
介紹 與許多密碼概念一樣,“公開可驗證的隨機信標”協議(簡稱PVRB)只是一種趨近理想的方案。但理想的方案并不適用于真實的網絡:應該就輪中的唯一......
介紹

與許多密碼概念一樣,“公開可驗證的隨機信標”協議(簡稱PVRB)只是一種趨近理想的方案。但理想的方案并不適用于真實的網絡:應該就輪中的唯一“位”、輪的數量以及必須快速且始終交付的網絡消息達成共識。但對于真實的網絡卻不是這樣。現代區塊鏈的自定義PVRB解決方案開發涉及許多技術問題,因此無法控制隨機數生成和加密算法的強度。
區塊鏈本身是PVRB的通信媒介,其中消息=交易。現在,我們可以忘記網絡問題、消息未交付問題以及中間軟件問題——所有這些風險都由分散式網絡來處理。PVRB不能回滾或破壞已發送的交易 ,而且參與者不能拒絕參與協議,除非他們成功地攻擊了網絡共識。由于安全級別是可以接受的,所以PVRB必須與區塊鏈的主鏈一樣,抵抗參與者之間的共謀。有跡象表明,PVRB應該成為共識的一部分;如果網絡同意主鏈,它也應該同意正確的產生隨機數。否則,PVRB只是一個由智能合約支持的獨立協議。這兩種方法各有利弊,在兩者之間做出選擇是相當困難的。

實現PVRB的兩種方法

我們將更詳細地描述兩個選項:基于區塊鏈獨立智能合約的獨立版本,以及嵌入協議的共識集成版本。對于每種情況,我將參考流行的區塊鏈:Ethereum、EOS,以及那些具有類似存儲和處理智能合約方法的區塊鏈。

獨立合約

這里PVRB是一個智能合約,它接受來自隨機生產者(以下簡稱RP)的交易,處理它們,組合結果,并最終生成任何合約用戶都可以接收的一些值。此值可能不會直接存儲在合約中,但具有數據表示形式,因此允許確定產生隨機性的惟一值。在該方案中,RP是區塊鏈用戶,任何人都可以參與生成過程。

獨立合約選項看起來不錯,因為:

· 可移植性(合約可以在區塊鏈之間“拖動”)
· 易于實現和測試(編寫和測試合約很方便)
· 方便的經濟方案(使用特定于PVRB的邏輯很容易創建自己的代幣)
· 適用于區塊鏈中工作

它也有缺點:

· 對消耗的計算資源的嚴格限制:交易復雜性、容量、網絡速度和區塊鏈存儲(換句話說,是傳統的cpu/mem/io/存儲)
· 存在內部合約機指令的限制(并非所有指令都可用,很難連接外部庫)
· 消息傳遞的速度不能超過區塊鏈中包含的交易的速度

如果我們想在現有的網絡中運行PVRB,而該網絡不包含復雜的加密技術,也不需要大量的交互,那么這個選項是合適的。

共識一體化選擇

這里PVRB嵌入到區塊鏈節點代碼中,或者與區塊鏈節點消息傳遞并行工作。協議結果直接寫入產生的塊中,而協議消息在節點之間通過p2p網絡發送。由于協議的數值結果需要用塊來編寫,因此網絡必須對它們達成一致。這意味著PVRB消息和交易必須由節點進行驗證,并包含在塊中(以便網絡中的任何成員都可以驗證是否符合PVRB協議)。這自動將我們引向一個顯而易見的解決方案——如果網絡在一個塊及其交易上達成共識,那么PVRB應該是共識的一部分,而不是一個獨立的協議。否則,該塊在協商共識方面是有效的,但是由于沒有遵循PVRB協議,因此不能接受該塊。因此,如果選擇“共識整合”選項,PVRB將成為共識的重要組成部分。

在網絡共識級別上討論PVRB實現時,無論如何都不能避免終結性問題。終結性是確定性共識中使用的一種機制,它修復了一個“最終確定”的塊(以及指向它的鏈),即使在并行分叉的情況下,這個塊也不會被丟棄。如果你發布一條更復雜的鏈,它將取代任何其他更簡單的鏈,而不用管鏈的“年齡”和長度。例如,在EOS中,有所謂的最后不可逆塊被認為是最終確定的。它們平均每432個塊出現一次(12*21(預投票)+ 12*15(預提交))。而比上一個庫更老的分支將被簡單地丟棄。該機制保證交易包含在區塊鏈中,并且永遠不會回滾??⒁桓魴槔慈繁W鈧戰峁魑桓鲆恢碌耐飩映絳蚴怯幸庖宓?,因為它能夠與塊生產和發布異步工作。

當BP持有這些區塊,并在網絡看到一筆不錯的交易后發布它們時,對于那些可能成為“雙倍支出”攻擊受害者的用戶來說,最終結果至關重要。PVRB有更嚴格的終結性要求,因為分叉構造意味著攻擊者可以準備幾個隨機數選項并發布最有益的一個。因此,限制可能的攻擊時間是一個很好的解決方案。

因此,最好的選擇是將PVRB和終結性結合在一個協議中—那么最終確定的塊將等于最終確定的隨機數—這正是我們的目標。從現在開始,玩家將在N秒內得到一個保證的隨機數,并確保不可能將其回滾或重放。

共識一致選項看起來不錯:

· 與塊生產相關的可能的異步實現——塊像往常一樣生成,但是PVRB協議可以并行工作,并為每個塊生成隨機數
· 能夠實現即使是復雜的密碼學,沒有智能合約的限制
· 能夠比區塊鏈中包含的交易更快地組織消息傳遞,例如,協議的一部分可以在沒有網絡交互的節點之間工作

它也有缺點:

· 測試和開發中的困難—您將不得不模擬錯誤網絡、丟失的節點和網絡硬分叉
· 實現錯誤需要一個網絡硬分叉

這兩種實現PVRB的方法都是可以接受的,但是現代區塊鏈中的智能合約在計算資源方面仍然非常有限,這使得一般的密碼學幾乎不可能實現。但是這種情況一年比一年好。我們可以以以太坊中zksnark的預編譯系統合約為例。

提供透明可靠的協議消息傳遞通道并不是免費的。任何分散協議都必須考慮到可能發生的西比爾( Sybil)攻擊,任何行動都可以通過多個帳戶進行協調。在開發過程中,請記住攻擊者能夠從任意數量的協議參與者中創建共謀。

PVRB和塊變量

我并沒有撒謊說 (到2019年春季) 還沒有人在區塊鏈中實施一個好的、強大的 PVRB, 并在賭博應用中進行了測試。以太坊和 EOS 中的這些賭博應用申請來自何方?我和你一樣驚訝: 在完全確定的環境中, 怎么會有這么多 "強" 隨機數呢?

我最喜歡的在區塊鏈中獲取隨機數的方法是從塊中獲取一些“不可預測”的信息,并在其基礎上生成一個隨機數。您還可以選擇塊中的任何其他“不可預測”值,例如,塊哈希值、大量交易、網絡復雜性和其他未知值。您甚至可以在白皮書中寫道,您的方案是“后量子安全的”(因為存在防量子哈希值函數:)。

唉,即使是后量子安全的哈希值也不夠。秘訣在于PVRB的要求,我將引用上一篇文章:

1. 結果應該具有可證明的均勻分布,即基于強密碼學。
2. 控制任何一點結果都是不可能的。
3. 不參與協議或用攻擊消息重載網絡來破壞生成協議是不可能的。
4. 上面所述的一切都應抵制一定數量的不誠實的協議參與者(例如1/3的參與者)串通一氣。

在這種情況下,只需滿足第一個需求。通過哈希不可預測的塊值,我們將得到一個均勻分布和正確的隨機數。BP至少能夠決定是否“驗證一個塊”,并從兩個隨機變量中進行選擇的問題。BP可以作弊,保留一個塊來看看接下來會發生什么,然后決定是否發布它。因此,以“偶數-奇數”或“紅/黑”輪盤賭為例,他只能在獲利的情況下發布一個區塊。使用未來塊的參數也沒有什么意義。在這種情況下,他們說“通過哈希當前數據和一個高度為N+42的未來塊獲得隨機性,其中N是當前塊高度”。這稍微加強了該方案,但是BP仍然可以選擇是否持有或發布區塊。

在塊生成軟件中執行這樣的攻擊并不復雜。在驗證和包含一個塊中的交易時,會有一個快速檢查通道,以查看是否會有收益,并可能選擇一個交易參數來增加獲勝概率。與此同時,發現一個聰明的BP來執行這樣的操作幾乎是不可能的,因為每次他都可以使用新的地址,并在不引起懷疑的情況下一點一點地獲勝。

因此,基于塊數據的方法不適用于通用PVRB實現。在一個簡短的版本中,限制了賭注大小、玩家數量或KYC注冊(為了禁止玩家使用多個地址),這些方案只適用于小型游戲。

PVRB和commit-reveal

好吧, 至少我們有哈希值, 一個 "幾乎不可預測" 的塊哈希值。如果我們設法解決領先礦工的問題, 我們可能會得到更有價值的東西。讓我們將用戶添加到此方案中, 并允許他們影響隨機性結果: 任何技術支持員工都會告訴您, IT 系統中最隨機的問題是用戶操作:)

在這種方案中,用戶只需發送隨機數,然后通過哈希他們的共同產品計算結果。在這種情況下,最后一個玩家可以選擇自己的隨機數來控制結果。這就是為什么最好使用眾所周知的commit-reveal模式。首先,參與者發送他們的隨機數的哈希值,然后提交原始隨機數。一旦收集了所有必要的提交,“reveal”階段就開始了,也就是說,參與者只能發送之前提交的哈希值隨機數。現在我們將添加塊參數—最好使用將來的塊參數,因為隨機數只出現在下一個塊中。現在任何玩家都可以影響結果的隨機性,并能夠“擊敗”一個惡意的BP,用它自己不可預測的隨機性來阻止它……您還可以通過為“提交”請求一些交易費用來提高協議安全性。

這是一個很好的嘗試(類似的方案也在不同的DApps中使用)。唉,這還不夠。現在,不僅礦工可以影響結果,協議的任何參與者也可以。

至少我們有機會懲罰那些提交了卻而沒有顯示的人,這個方案稍后會有用。此外,它的簡單性也是一個重要的優勢,因為更重要的協議需要更多的計算。

PVRB和確定性簽名

確定性簽名是使RP生成偽隨機數的另一種好方法,它不會影響偽隨機數。例如,RSA簽名就是其中之一,而ECS(橢圓曲線簽名)則不是。如果RP有一對密鑰(RSA和ECS),并且他使用自己的私鑰對一些值進行簽名,RSA允許生成一個惟一的簽名,而ECS允許生成任意數量的有效簽名。在創建ECS簽名時,簽名者可以隨意選擇一個隨機數,從而有機會從多個簽名中選擇一個。RSA是 “一個輸入值”+“一個密鑰對”=“一個簽名”。要預測另一個RP的簽名是不可能的,因此具有確定性簽名的PVRB可以通過組合多個已簽名相同值的參與者的RSA簽名來構建,例如前面的隨機數。這種方案節省了大量資源,因為簽名既是正確協議行為的確認,也是隨機性的來源。

然而,確定性簽名并不是萬能的,而且該方案仍然容易受到“最后一個參與者”問題的影響。最后一個參與者仍然可以決定是否發布簽名,從而控制結果。此外,RSA密鑰可以很長(1024和2048位),這對于區塊鏈交易來說是一個非常重要的參數。顯然,沒有簡單的方法來解決這個問題。

PVRB和秘密共享方案

有一些加密方案允許網絡協商一個惟一的PVRB值,同時保持對某些參與者的任何惡意行為的抵抗。其中一個有用的協議是Shamir的秘密共享。它將一些秘密(例如,一個秘密密鑰)劃分為幾個部分,并將這些部分分發給N個參與者。這個秘密的分布方式是,從N到M個部分足夠恢復它,這些可以是任意M個部分。簡單地說,有一個未知函數的圖,參與者在圖上交換點,得到M個點后,整個函數就可以恢復(線性函數需要2個點,二次函數需要3個點,等等)。

wiki提供了一個很好的解釋;您還可以在這個演示頁面上以實時模式試用該協議。

如果FSSS (Fiat-Shamir秘密共享)方案能夠以其單純的形式應用,PVRB將是無懈可擊的。在其最簡單的形式中,協議可能是這樣的:

· 每個參與者生成一個隨機數,并將其份額分配給其他人
· 每個參與者都揭示了其他參與者的秘密
· 如果一個參與者收集了更多的m點,他的數字可以計算出來。無論“顯示”的參與者集是什么,這個數字都是惟一的
· 所需的PVRB是顯示的隨機數的組合

因此,考慮到有必要數量的可靠RP遵循規則,該協議按照嚴格的密碼學要求工作,并保持對“最后一個參與者”問題的抵抗力。

這可能是一個理想的選擇。例如,本文描述了基于Fiat-Shamir秘密共享的PVRB方案。正如我前面提到的,如果您試圖將其應用到區塊鏈的單純形式中,技術限制將不可避免地出現。下面是EOS 智能合約中協議測試實現的一個示例,其中最重要的部分是檢查參與者已發布的共享:代碼。很明顯,證明驗證需要多次標量乘法,而且數字非常大。同時,我們應該記住,在區塊鏈中,當區塊生產者處理事交易時,會調用verify函數。一般來說,任何參與者都應該很容易地驗證協議的正確性,這就是為什么對“verify()”函數的速度要求非常嚴格的原因。我們的方案沒有成功,因為驗證沒有滿足交易時間限制(0.5秒)。

驗證效率是區塊鏈中任何高級密碼方案最重要的要求之一。證明和消息創建可以脫離鏈,由高性能計算機完成,但是不能忽略驗證——這是PVRB的另一個重要要求。

PVRB和閾值簽名

秘密共享方案打開了在“閾值”?;ど∠巒騁壞囊煥嘈?。他們允許處理“最后的參與者”的問題:如果攻擊者不透露秘密的一部分,另一個誠實的參與者會相反。反過來,這使我們能夠就唯一的意義達成一致,即使一些參與者正在破壞協議。

結合確定性簽名和閾值方案,我們得到了一個非常方便和有前途的PVRB方案-確定性閾值簽名。

上一篇文章討論了BLS的公共簽名和私有簽名以及密鑰,現在可以使用簡單的數學操作組合它們——這對開發人員來說非常方便。組合仍然是有效的密匙和簽名,這使得將多個簽名聚合為一個密匙和多個公鑰聚合為一個密匙變得很容易。它們的決定論允許獲得具有相同輸入數據的相同結果。由于這種特性,BLS簽名組合成為有效的密鑰,這使得M個誠實的參與者(從N個總數到M個總數)有可能生成唯一的確定性、公共可驗證性和不可預測的簽名,直到M個參與者披露為止。

在BLS閾值簽名方案中,每個參與者都使用BLS(例如前面的隨機數)簽名,并將其份額發送給區塊鏈。BLS簽名的密碼特性滿足隨機性質量要求,因為閾值部分防止“最后的參與者”,而密鑰的獨特兼容性允許使用許多有趣的算法(例如,有效聚合協議消息的算法)。

因此,如果您正在為您的區塊鏈在2019年春夏構建PVRB,您很可能會遇到BLS閾值簽名方案;一些項目已經在使用它。例如,DFinity是一個實現該方案的基準測試工具, Keep.network是一個為協議提供服務的智能合約示例。

實現PVRB

遺憾的是,目前還沒有真正的強密碼PVRB區塊鏈協議,這證明了它在真實的DApps中的安全性和穩定性。盡管現有協議是現成的,但是將它們應用于現有解決方案并不容易。PVRB對于集中式系統毫無用處,而分散式系統的計算資源非常有限:CPU、內存、存儲、I/O??VRB涉及到不同協議的組合,以便它能夠匹配至少一個真正可行的區塊鏈。

我將列出您在選擇高品質PVRB時必須考慮的因素:

1. 它應該是強加密的,即嚴格不可偏置的,不能給任何人控制。對于某些方案,情況并非如此,因此最好向密碼編寫者尋址。
2. “最后一個參與者”問題。當控制一個或多個RP的攻擊者可以在兩種可能的結果中進行選擇時,PVRB必須能夠抵抗攻擊。
3. 協議破壞。當控制一個或多個RP的攻擊者決定是否生成隨機數時,您的PVRB必須能夠抵抗攻擊,并且能夠影響隨機信標的生成。
4. 消息數量。您的RP應該向區塊鏈發送最少數量的消息,并盡可能避免同步操作,比如“發送信息,等待特定參與者的響應”。您不應該期望p2p網絡中的快速響應,尤其是來自地理分布的網絡。
5. 計算的復雜性。任何PVRB階段的鏈上驗證都應該很容易,因為它是由所有完整的網絡客戶機執行的。在智能合約執行的情況下,速度要求是非常嚴格的。
6. 可訪問性和靈活性。您的PVRB應該對可能的網絡故障具有彈性(例如,當它在一段時間內不可用,并且部分RPs停止工作時)。
7. 可信設置和初始密鑰分發。如果PVRB涉及主協議設置,則可能會導致某些問題。這里舉一個例子:如果參與者必須在開始協議之前告訴對方他們的密鑰,這也是一個問題,因為參與者的列表可能會改變。
8. 發展問題。所需語言的庫的可用性、它們的安全性和性能、公共可訪問性、復雜的測試等等。

例如,閾值BLS簽名有一個顯著的瓶頸——在開始之前,參與者必須共享密鑰并組織閾值組。這意味著我們將不得不在一個分散式網絡中跳過至少一輪,并且,由于隨機數對于實時模式下的游戲來說是必不可少的,因此存在著很高的協議破壞風險,而閾值方案的優點將變得毫無用處。這個問題比之前的問題要簡單,但是我們仍然需要開發一個單獨的閾值組程序,它必須通過對不遵守協議的參與者的存款和資金提取(削減)來得到經濟上的?;?。合約代碼由虛擬機WebAssembly或EVM執行。密碼函數尚未在本地實現,并且比普通密碼庫慢很多倍。許多協議根本不滿足密鑰長度要求:例如,RSA的1024位和2048位。這是標準比特幣和以太坊交易簽名大小的4-8倍。

還應該使用不同的編程語言實現,這種語言并不多,尤其是對于新協議而言。為了將PVRB集成到共識中,我們應該用平臺語言編寫代碼,即查找用于geth的Go代碼、Parity的Rust代碼和用于EOS的c++代碼。JavaScript代碼更難找到,而且由于JavaScript和密碼學關系并不密切,所以選擇WebAssembly。它看起來將成為下一個重要的互聯網標準。

結論

我希望在上一篇文章中,我成功地說服了您,區塊鏈中的隨機數生成對于分散式網絡的許多方面都是至關重要的。今天我已經表明,這項任務是極其艱巨的,但也有一些很好的解決辦法。說實話,協議體系結構只有在進行了涉及從設置到故障模擬各個方面的大規模測試之后才會被認為是最終的。你不太可能在白皮書或文章中找到現成的解決方案。我們也不能建議該做什么。至少在最近的幾年是這種情況。

到目前為止,在Haya區塊鏈中開發我們的PVRB時,我們已經選擇了閾值BLS簽名,并計劃在共識級別上實現PVRB,因為智能合約不允許體面的安全驗證。我們可以同時使用兩種方案:首先,一個昂貴的秘密共享來創建一個長期的種子值,它將作為具有確定性閾值BLS簽名的高頻隨機數生成的基礎。我們還可以把自己限制在其中一個計劃之內。不可能預先說協議是什么樣子的,然而,一個負面的結果也是一個結果,每一次解決問題的新嘗試對參與研究的每個人來說都是另一個步驟。為了滿足業務需求,我們正在處理一個特定的實際問題——為游戲應用程序提供一個可靠的熵源,因此我們還必須關注區塊鏈,特別是終結性問題和網絡治理問題。

目前,還沒有經過驗證的PVRB可以被長期使用;然而,許多可能的解決方案證明了還是有出路的,最終會有算法來解決這個問題。我們將樂于分享結果,并感謝其他團隊提供的文章和代碼,使開發人員不會犯同樣的錯誤。

所以,如果你遇到一個開發分散式隨機數生成器的開發人員,一定要督促他小心謹慎,如果有必要,還要提供心理上的幫助:)
關鍵詞: 隨機數  分布式網絡  
0/300
?