背景
PoW消耗現(xiàn)實(shí)中的算力達(dá)成區(qū)塊鏈的共識(shí)體系，就好像需要從外界提供能量來獲得一個(gè)穩(wěn)定系統(tǒng)一樣，而PoS能根據(jù)歷史所產(chǎn)生的“權(quán)益”，使用一套算法能利用好歷史中的“權(quán)益”來達(dá)成共識(shí)從而不斷衍生出新的價(jià)值，使得區(qū)塊鏈本身就能成為一個(gè)閉環(huán)，不斷運(yùn)行下去。
有很多不同的方式來實(shí)現(xiàn)權(quán)益證明的算法，但是權(quán)益證明設(shè)計(jì)的兩個(gè)主要原理是基于鏈的PoS和基于拜占庭容錯(cuò)（BFT）的PoS。
“基于鏈的PoS”：Ouroboros
論文中的Ouroboros是一個(gè)理論：按照什么樣的一個(gè)流程可以設(shè)計(jì)出一個(gè)健壯的PoS算法并給出數(shù)學(xué)上充分的證明。而Cardano中的Ouroboros是對(duì)論文的實(shí)現(xiàn)，工程實(shí)現(xiàn)上跟論文中的描述有所不同。
本質(zhì)上，PoW和PoS都是一種隨機(jī)選擇下一個(gè)區(qū)塊生產(chǎn)者的方式。
所以，Ouroboros的根本目的就是為了根據(jù)權(quán)益多少，隨機(jī)的選出一個(gè)出塊者，并且隨機(jī)選擇的這個(gè)過程是不可預(yù)知的。
Ouroboros運(yùn)行流程
首先要對(duì)一些術(shù)語進(jìn)行解釋：
在Cardano的運(yùn)行中，時(shí)間被分為slot每個(gè)slot只能生產(chǎn)一個(gè)塊，若這個(gè)塊有問題，或者生產(chǎn)這個(gè)塊的“礦工”（stakeholder的候選人）不在線，或者產(chǎn)出的塊沒有廣播給大多數(shù)人，那么這個(gè)slot是當(dāng)作廢棄的，也就是會(huì)調(diào)過這個(gè)slot的塊。多個(gè)slot為一個(gè)epoch，權(quán)益的計(jì)算是以每個(gè)epoch開始前的歷史來計(jì)算，也就是說在這個(gè)epoch中所產(chǎn)生的權(quán)益變化不影響當(dāng)前這個(gè)epoch中的slot的出塊者的選擇和其他和歷史相關(guān)的東西。當(dāng)前epoch中所產(chǎn)生的這些歷史只能在以后的epoch中生效。每個(gè)epoch的開頭有個(gè)genesis block，其不會(huì)上鏈，而是當(dāng)前這個(gè)節(jié)點(diǎn)（礦工）自己在內(nèi)存中生成，這個(gè)genesis block會(huì)記錄好當(dāng)前這個(gè)epoch中的可能參與出塊的stakeholder的候選人，及一個(gè)隨機(jī)種子ρ。stakeholder是權(quán)益持有者，也就是潛在礦工，在Cardano的實(shí)現(xiàn)中權(quán)益stake并不是直接指有多少ADA（Cardano的代幣），而是和有多少ADA相關(guān)聯(lián)，同時(shí)要成為一個(gè)stakeholder需要有2%的ADA才行。stakeholder并不一定要參與出塊，只要記錄在每個(gè)epoch的genesis block中的stakeholder才能參與當(dāng)前epoch中slot的出塊，所以記錄在每個(gè)epoch中g(shù)enesis block中的stakeholder叫做“stakeholder候選人”。由這些epoch銜接而成的鏈就是由Ouroboros共識(shí)產(chǎn)生的鏈，這個(gè)鏈的基本屬性和Bitcoin相同（比如每個(gè)塊包含上一個(gè)塊的hash等）。Slot Leader Selection是指根據(jù)權(quán)益占比選擇按概率選擇出當(dāng)前slot的出塊者。在當(dāng)前epoch中，按genesis block中記錄的stakeholder候選人的權(quán)益分別占用的比例為這個(gè)epoch中的每一個(gè)slot選擇出塊者的概率。
論文中的函數(shù)表示按照權(quán)益占比為概率從stakeholder候選人集合中選出該slot的出塊者U。
secure multiparty computation（MPC）MPC協(xié)議，參與者使用一種能達(dá)成MPC的密碼學(xué)協(xié)議來參與生成下一輪epoch的隨機(jī)種子ρ，這個(gè)MPC協(xié)議必須保證guarantee output delivery（GOD），這個(gè)隨機(jī)種子ρ是用于Slot Leader Selection中的。
1.從鏈的真正創(chuàng)世塊開始，硬編碼進(jìn)入一些公鑰和這些公鑰對(duì)應(yīng)的權(quán)益s及初始的種子ρ，之后，這個(gè)epoch會(huì)采用這些基礎(chǔ)信息繼續(xù)運(yùn)行。2.每個(gè)節(jié)點(diǎn)自己獨(dú)立運(yùn)行代碼，根據(jù)當(dāng)前epoch的種子ρ，執(zhí)行F(follow-the-satoshi)，把genesis block中的權(quán)益，ρ和slot的index作為輸入，根據(jù)概率獲得當(dāng)前這個(gè)slot應(yīng)該由誰出塊。1.若發(fā)現(xiàn)自己出塊，則執(zhí)行打包交易等操作，和bitcoin沒有太大區(qū)別，除了基礎(chǔ)工作之外，還要生成一個(gè)隨機(jī)數(shù)，但這個(gè)隨機(jī)數(shù)不放在鏈（塊）中，而是放一個(gè)承諾（后面大家打開承諾一看，驗(yàn)證自己沒有說謊）。若不是自己出塊，則等待出塊者出塊并廣播。收到這個(gè)塊的時(shí)候就性和bitcoin類似的檢查，要是長時(shí)間未收到（超出這個(gè)slot的時(shí)間）則會(huì)認(rèn)為這個(gè)slot的塊廢棄。3.在當(dāng)前epoch中不斷重復(fù)2的流程直到這個(gè)epoch中的所有slot結(jié)束。在整個(gè)epoch的過程中會(huì)產(chǎn)生出一個(gè)在這個(gè)epoch參與出塊者們（slot leaders）都共同認(rèn)同的隨機(jī)種子ρ。在自己的內(nèi)存里記錄好這個(gè)ρ及下一個(gè)epoch參與的stakeholders，開啟下一個(gè)epoch周期，進(jìn)入2的流程。
深入解釋
Ouroboros的模型及結(jié)合目的“產(chǎn)生一個(gè)不可預(yù)測的隨機(jī)數(shù)”，我們來探討一下其中的關(guān)鍵問題：如何隨機(jī)的選出記賬者
這個(gè)問題在Ouroboros的模型下，可以拆分成兩個(gè)部分：
1.產(chǎn)生一個(gè)隨機(jī)種子ρ2.根據(jù)隨機(jī)種子ρ在當(dāng)前epoch中以權(quán)益的比例為概率，隨機(jī)選出slot leader
以每一個(gè)epoch為分析單位，只要一個(gè)epoch的執(zhí)行流程是成立的，那么不斷重復(fù)epoch生成的鏈就是成立的。（就像銜尾蛇一樣）
產(chǎn)生一個(gè)隨機(jī)種子ρ
產(chǎn)生這個(gè)隨機(jī)種子的方法在密碼學(xué)中應(yīng)該屬于交互式協(xié)議
coin tossing（投硬幣）
coin tossing是為了在多方通信中，通過偽隨機(jī)數(shù)和互相交互，最終得到一個(gè)統(tǒng)一的，被所有人認(rèn)可的真隨機(jī)數(shù)的交互式協(xié)議。如下圖的左邊所示：
左圖是一個(gè)兩方進(jìn)行coin tossing的過程：
A首先產(chǎn)生一個(gè)隨機(jī)串s和一個(gè)nonce，然后用A和B都認(rèn)可的加密方式進(jìn)行加密此時(shí)加密的結(jié)果稱為一個(gè)承諾（Commitments），A把這個(gè)承諾發(fā)送給B，此時(shí)相當(dāng)于B知道A已經(jīng)產(chǎn)生了一個(gè)東西，雖然不知道是什么，但是已經(jīng)知道存在了B保存這個(gè)承諾，然后自己生成一個(gè)自己的隨機(jī)串s',并發(fā)送給A此時(shí)A同時(shí)具有了A自己的串s和B的隨機(jī)串s',那么A就發(fā)送一個(gè)揭露（Open）給B，包含自己一開始的s和nonceB收到Open后使用Open的數(shù)據(jù)加密，把結(jié)果和之前的承諾做對(duì)比，發(fā)現(xiàn)一致，那么B就可以肯定A發(fā)送的Open就是在自己發(fā)送B自己的隨機(jī)串之前就確實(shí)生成好并存在的此時(shí)A和B都分別拿到了對(duì)方的隨機(jī)串，并能肯定對(duì)方生成自己的串的時(shí)候是不知道自己的隨機(jī)串的信息的，所以即便兩方都是使用偽隨機(jī)生成的字符串，那么對(duì)這兩個(gè)字符串做一些統(tǒng)一的操作（比如異或xor）之后的結(jié)果一定是一個(gè)真隨機(jī)串S，并且被雙方所認(rèn)可。
把這個(gè)兩方coin tossing擴(kuò)展為多方的時(shí)候，就是一個(gè)多方coin tossing的交互式隨機(jī)數(shù)生成協(xié)議了。
這種交互至少需要3步，要達(dá)成這樣的交互式協(xié)議是不能比3步更少的，如果能在盡量少的通信下（如三步）又希望保證整個(gè)協(xié)議不會(huì)因?yàn)锳bort而無法運(yùn)行下去，這樣的目的就被稱為guarantee output delivery（GOD），為了保證GOD這個(gè)目標(biāo)成立，就需要引入一些新的機(jī)制。
verifiable secret sharing（VSS）
VSS:可驗(yàn)證的密鑰分享。在Cardano中使用的是PVSS。
先講解VSS：
把一個(gè)秘密S通過share(s)可以拆分成m份，分別給m個(gè)人，每個(gè)人拿到其中的一片并不知道整個(gè)S是什么
但是只要收集到另外t(t
VSS的特定就是，每個(gè)人拿到的那個(gè)秘密是不可能知道原來的秘密是什么的，必須得到其他人的幫助才能恢復(fù)出原來的密碼是什么。
每個(gè)人并不是要拿到所有的秘密，而是要拿到一定多的秘密，就可以重新恢復(fù)出原來的那個(gè)秘密S。
這個(gè)特性就可以達(dá)成這樣一個(gè)功能：例如A向大家宣告我有一個(gè)東西，然后A就可以用VSS把這個(gè)東西分發(fā)給所有人，但是所有人又不知道這個(gè)東西是什么，此時(shí)，即時(shí)A掛了或者跑路了，大家也可以互相通信恢復(fù)出A一開始的東西。
VSS就是用來解決coin tossing協(xié)議中斷執(zhí)行的問題。
GOD coin tossing
coin tossing的問題是要是A沒有發(fā)送open給B，那么協(xié)議就無法執(zhí)行下去。那么VSS的性質(zhì)，直接把open分發(fā)給所有人就可以，即使A跑路了，大家也可以相互通信恢復(fù)出A一開始給出的承諾是什么東西，使得coin tossing的協(xié)議能夠正常執(zhí)行下去，得到大家都認(rèn)可的真隨機(jī)串。
把VSS和coin tossing結(jié)合起來，就可以達(dá)成GOD的目標(biāo)，稱為“GOD coin tossing”。
論文提出的方案如下：
這里的Deal()對(duì)應(yīng)上面的Share()并對(duì)share的結(jié)果使用對(duì)應(yīng)接受者的公鑰進(jìn)行加密
Ouroboros采用的方法如下：
把整個(gè)epoch的slot分成10等份，這里的k是倍數(shù)，在Cardano中可以通過配置文件指定
整個(gè)epoch被分為三個(gè)階段：Commitment Phase，Revel Phase，Recovery Phase，分別占比4：4：2
1.在Commitment階段的時(shí)候，所有的stakehols(i∈{0...n})必須把自己的隨機(jī)串生成做處理后并把這個(gè)內(nèi)容廣播出去，被前4k的leader打包進(jìn)入?yún)^(qū)塊。（當(dāng)然如果這個(gè)時(shí)間內(nèi)沒有把自己的隨機(jī)串廣播出去的話就相當(dāng)于放棄了參與下一個(gè)epoch隨機(jī)的權(quán)力了）而這個(gè)處理的內(nèi)容是2部分：這個(gè)隨機(jī)串的承諾commitment把Open的內(nèi)容做成VSS后對(duì)應(yīng)所有的leader，使用這些leader的公鑰（在genesis block中有）進(jìn)行加密，也就是Dea的過程，生成σ1, . . . , σn 被加密過的shared secret2.在Reveal階段中，這些stakeholders(i∈{0...n})把自己的Open廣播出去。這時(shí)候就出現(xiàn)有人跑路了，有人掉線，網(wǎng)絡(luò)不好的情況，這個(gè)人的Open沒有被打包到鏈中，此時(shí)若沒有下一個(gè)階段救場的話，就相當(dāng)于coin tossing協(xié)議被Abort了。若所有的Open都在的話，就當(dāng)然得到下一個(gè)epoch的ρ是什么了。3.在Recovery階段的時(shí)候，這些誠實(shí)的slot leaders(i∈{0...R})就會(huì)檢查出有哪些Open沒有成功，那么他們就會(huì)把沒有成功的Open對(duì)應(yīng)的秘密自己解密后，廣播出去上鏈條，那么這樣每個(gè)人都可以收集到足夠數(shù)量的共享秘密而恢復(fù)出沒有被Open的隨機(jī)串，GOD滿足。此時(shí)所有人都獲得了所有人的隨機(jī)字符串，那么就可以得到一個(gè)統(tǒng)一的隨機(jī)數(shù)ρ了。
至此，如果在一個(gè)epoch中生成一個(gè)不可控制的隨機(jī)數(shù)ρ就深入解釋完成了。可以看出通過GOD coin tossing是可以做到一個(gè)不會(huì)被Abort的交互式隨機(jī)數(shù)生成過程。
前兩個(gè)階段指的是所有的stakeholders都參與，然后Recovery階段只有被選中的stakeholders才參與。
根據(jù)Cardano結(jié)算層的文檔來看，在實(shí)現(xiàn)上和論文有區(qū)別的。
Slot leaders are elected from the group of all stakeholders.Please note that not all stakeholders participate in this election, but only ones who have enough stake (for example, 2% of the total stake). This group of stakeholders are known as “electors”.
具有權(quán)益的確就是stakeholders，但是參與過程的并不是所有的stakeholders，而是只有2%以上的人才能參與，而這些2%以上的人就叫做“electors”。
而后續(xù)的操作都是基于elector的。
根據(jù)隨機(jī)種子ρ在當(dāng)前epoch中以權(quán)益的比例為概率，隨機(jī)選出slotleader
在論文中沒有詳細(xì)描述，只是直接定義出了這樣一個(gè)函數(shù)，在Cardano中的實(shí)現(xiàn)使用的是“follow-the-satoshi”算法。
follow-the-satoshi算法最原始來自于論文:Proof of Activity:Extending Bitcoin's Proof of Work via Proof of Stake
論文大概是說，使用PoW產(chǎn)生一堆stakeholders，然后在這堆stakeholders中使用follow-the-satoshi找出出塊者，當(dāng)然Ouroboros對(duì)其的改進(jìn)就是把pow做成了G.O.D coin tossing
如上圖，把所有的stakeholders組成一個(gè)merkletree的形式，然后根據(jù)一個(gè)隨機(jī)種子開始，通過偽隨機(jī)數(shù)作出選擇，最終會(huì)按照大家權(quán)益的比例選出對(duì)應(yīng)的stakeholder。
這里的偽隨機(jī)數(shù)，是為了當(dāng)有一個(gè)相同的種子后，每個(gè)不同的個(gè)體分別執(zhí)行這個(gè)偽隨機(jī)后都能得到相同的序列。
根據(jù)隨機(jī)數(shù)進(jìn)行隨機(jī)漫步，最后選中某個(gè)stakeholder的概率就是其權(quán)益占總體的比例。又因?yàn)槭鞘褂靡粋€(gè)真隨機(jī)數(shù)作為種子，執(zhí)行偽隨機(jī)進(jìn)行漫步，那么只要所有人拿到的真隨機(jī)數(shù)的種子是一致的時(shí)候，那么所有人得到的隨機(jī)出的stakeholder的結(jié)果就是一致的。
這就可以解釋GOD coin tossing中的問題，只要genesis block能夠生成后得到ρ和權(quán)益集合S，那么就相當(dāng)于可以計(jì)算出當(dāng)前這個(gè)epoch中所有的slotleaders們都是誰了。
總結(jié)
整個(gè)Ouroboros的核心就是隨機(jī)數(shù)，如何隨機(jī)選擇出塊人，并且被全網(wǎng)認(rèn)可，還不能被操控，也不能被預(yù)測。
Ouroboros是基于鏈的PoS方案，隨機(jī)選舉一個(gè)節(jié)點(diǎn)出塊，其被選中的概率和它擁有的份額相關(guān)。關(guān)鍵是如何保證“隨機(jī)”性？
傳統(tǒng)的PoS方案都是從現(xiàn)有的鏈上數(shù)據(jù)入手，比如使用上一個(gè)區(qū)塊的哈希值，上一個(gè)區(qū)塊的時(shí)間戳作為隨機(jī)數(shù)的來源，但這些會(huì)帶來額外的安全風(fēng)險(xiǎn)，因?yàn)閰^(qū)塊本身的信息就是節(jié)點(diǎn)寫進(jìn)去的，然后又根據(jù)里面的信息來選舉后續(xù)的出塊者，存在循環(huán)論證的嫌疑，安全性不會(huì)太好。
Coin-Tossing，如果大家都不跑路，就能得到一個(gè)一致的無法被操控的隨機(jī)數(shù)。
VSS，就是預(yù)防跑路的，叛徒節(jié)點(diǎn)。結(jié)合Coin-Tossing和VSS就有一個(gè)完整的隨機(jī)數(shù)生成協(xié)議了。
協(xié)議流程：
1.提交階段，每個(gè)節(jié)點(diǎn)本地生成隨機(jī)數(shù)和對(duì)應(yīng)的承諾，把隨機(jī)數(shù)拆n份匹配其他投票節(jié)點(diǎn)，相應(yīng)投票節(jié)點(diǎn)的公鑰加密，承諾和加密信息廣播。2.打開階段，每個(gè)節(jié)點(diǎn)把自己的打開發(fā)到鏈上。3.恢復(fù)階段，恢復(fù)出隨機(jī)數(shù)。4.選下一輪出塊者?
