基于沙普利值計算的區(qū)塊鏈中PoS共識機制的改進

劉怡然 柯俊明 蔣 瀚 宋祥福

1(山東大學計算機科學與技術學院 濟南 250000)2(山東大學軟件學院 濟南 250000)

自2008年中本聰[1]發(fā)表了名為“比特幣：一種點對點的電子現(xiàn)金系統(tǒng)”的文章后，一種新型的“貨幣”——比特幣由此誕生.它被稱為“密碼貨幣”或“數(shù)字貨幣”.歷經(jīng)10年發(fā)展，目前已經(jīng)出現(xiàn)了上千種數(shù)字貨幣，一定程度上得到社會承認的不下百種，支撐這些數(shù)字貨幣運行的核心技術就是區(qū)塊鏈.由于它具備去中心化、防篡改、可驗證等優(yōu)點，迅速成為社會和研究機構的熱門研究對象.區(qū)塊鏈是一個鏈式分布式存儲結構，每一塊中包括了交易的信息以及前一塊的Hash值[2]，正是這些Hash值將這些區(qū)塊連接在一起就構成了區(qū)塊鏈.

共識機制的作用正是保障系統(tǒng)的一致性并保證系統(tǒng)安全、穩(wěn)定運行.共識機制描述了區(qū)塊鏈系統(tǒng)的核心工作——節(jié)點競爭記賬即產生新塊并獲得一定數(shù)目交易費的過程[3]，目前比特幣中使用的共識機制稱為工作量證明機制(proof of work, PoW).系統(tǒng)中的每個節(jié)點都對系統(tǒng)提供計算能力，由能夠完成計算工作的節(jié)點獲得記賬權即創(chuàng)建一個新的區(qū)塊并獲得交易費.與工作量證明機制比拼算力不同，權益證明(proof of stake, PoS)是根據(jù)錢包中的貨幣數(shù)目及貨幣存在天數(shù)來確定一個新的度量單位，即“幣齡”來實現(xiàn)的.它根據(jù)幣齡大小的關系降低了計算機進行Hash計算的難度，一定程度上緩解了資源浪費問題.之后又出現(xiàn)了PoS的進化版本PoA(行動證明)，在權益持有者中選取挖塊者.這種共識機制又大大縮短了達到共識的時間.

工作量證明機制PoW這個概念由Cynthia 和Moni 在1993年的學術論文中首次提出.而工作量證明這個名詞則是在1997年AdamBack的文章[4]中才被真正提出用來防止DOS攻擊.2008年中本聰發(fā)表的比特幣白皮書再次使用了工作量證明機制來保證比特幣系統(tǒng)的一致性.其核心機制是通過競爭計算能力來保證系統(tǒng)中的數(shù)據(jù)一致性以此來達到共識.整個系統(tǒng)中的每個節(jié)點為整個系統(tǒng)提供計算能力(簡稱算力)，節(jié)點通過解決一個難求解易驗證的SHA256的問題來獲得相應的獎勵(也就是通過挖塊來獲得收益)[5].完成這個困難工作并向大家證明的機制就叫做工作量證明機制.另外，這個工作的難度會隨著時間不斷增長，以保持每10 min出1個新塊的速度.在比特幣中，這個工作就是找到一個Hash值，同時這個Hash必須要滿足一定的條件.即滿足：

Hash(data,counter)

在PoW中，最后能夠最先給出滿足條件Hash值的節(jié)點將會獲得最終的挖塊收益，而付出過算力但卻最終沒有挖塊成功的人一無所獲.這樣某些擁有超過全網(wǎng)50%以上算力的人就極有可能發(fā)動51%攻擊進而操控整個區(qū)塊鏈，而其余參與挖塊的人一無所獲.綜上，工作量證明機制邏輯簡單，但并非完美，其缺點主要在于資源的浪費和51%攻擊等安全問題，并且會加劇區(qū)塊鏈中的貧富差距.

權益證明PoS最早由Sunny在2012年提出[6]，最早在PPcoin系統(tǒng)中被實現(xiàn).PPcoin系統(tǒng)混合了PoW機制和PoS機制.PoS機制中引入了幣齡的概念，一個人擁有的幣齡與擁有的錢數(shù)和時間成正比.在PPcoin網(wǎng)絡中，幣齡表示為錢數(shù)和時間的乘積：

Coinage=Coins×Timeweight.

PPcoin沿用了PoW的挖礦機制[7]，不允許礦工窮舉所有counter值而是在1 s之內只允許計算1次Hash值，這個步驟可以通過時間計數(shù)器TimeCounter實現(xiàn)，PoS中Hash值的滿足條件修改為

Hash(data,TimeCounter)Coins×Timeweight，

若符合該條件，持有這些數(shù)據(jù)的礦工獲得挖礦資格和收益.因此，持幣數(shù)越多且持幣時間越長的人就擁有更大的幣齡，從而更有可能使得上述不等式成立，即更容易挖礦成功進而獲得收益.不僅如此，為了改善“富者更富”的現(xiàn)象，PoS規(guī)定，每當一個礦工挖到一塊獎勵時，PPcoin就將該礦工已經(jīng)出示的幣齡清零重新計算.

目前以太坊在Serenity階段使用了Casper協(xié)議，它是一種改進的PoS機制.Casper是一種基于保證金的經(jīng)濟激勵共識協(xié)議(security-deposit based economic consensus protocol).每個節(jié)點必須先繳納一定數(shù)量的保證金才可以參與出塊和共識的形成，惡意參與節(jié)點將存在保證金被罰沒的風險，損失一定的經(jīng)濟利益.一般來說，需要掌握超過全網(wǎng)1/3的幣齡才能左右最終的結果.也就是說3人投票，前2人分別支持一方，這個時候的結果就和第三方的投票結果有關. 不僅如此在PoS機制中，挖塊成功的收益仍然是由某一節(jié)點獨享，其余節(jié)點雖然付出了相應的努力，但是并不會獲得收益.

PoS機制雖然考慮了PoW機制的不足，在一定程度上減輕了資源浪費和節(jié)點之間的貧富差距問題，也在一定程度上解決了大算力節(jié)點壟斷問題，對新加入的節(jié)點更友好，而且各節(jié)點達成共識的時間縮短了.但是也存在一定的缺點，它需要依照權益的結余來選擇，這就會導致首富賬戶的權力更大，它就很有可能支配記賬權和收益.并且PoS很容易產生分叉，所以每一筆交易的產生需要多個交易進行確認.

然而，現(xiàn)在的PoW機制和PoS機制幾乎是挖塊成功的節(jié)點獨享獲得的交易費，而其余付出過工作量或者幣齡的節(jié)點一無所得.在這種情況下，區(qū)塊鏈中的大節(jié)點更容易發(fā)起51%攻擊，獲得全部收益進而控制整個區(qū)塊鏈.不僅如此，這樣還可能加劇區(qū)塊鏈中“富者更富，窮者更窮”的現(xiàn)象，不利于區(qū)塊鏈的健康持續(xù)發(fā)展.

經(jīng)過上面的分析和論述可以發(fā)現(xiàn)，雖然共識機制不斷進化，達到共識的時間也不斷縮短，并且還能夠實現(xiàn)一定的擴展性[8]，但是目前常見的共識機制如PoW,PoS以及后面將要介紹的PoA對于挖礦成功后的收益分配都沒有一個具體的方案.在PoW中，計算出符合條件的Hash值節(jié)點獲得全部收益；在PoS中，幣齡越大的人獲得挖塊權并獲得全部收益的概率越大；對于PoW而言，如果某個節(jié)點掌握了超過全網(wǎng)50%的算力，它就有可能操縱整個區(qū)塊鏈從而獲得全部收益[9]；對于PoS而言，如果某個節(jié)點掌握了超過了全網(wǎng)50%的幣齡，它就有可能瓜分所有的收益.

因此本文基于博弈論中計算沙普利值的原理對權益證明機制(PoS)中的收益分配方式進行改進，使得PoS機制中參與生成區(qū)塊的節(jié)點的收益分配更加公平合理，改善現(xiàn)在區(qū)塊鏈中的社會分層現(xiàn)象，大幅度提高新加入的小節(jié)點獲得收益的可能性，抵制系統(tǒng)中心化的趨勢.

1 預備知識

1.1 行動證明(poof of ativity， PoA)

行動證明PoA是由Bentov等人在2014年提出[10].行動證明協(xié)議結合了工作量證明協(xié)議和權益證明協(xié)議，是比特幣協(xié)議的擴展.在PoA協(xié)議中，全網(wǎng)節(jié)點需要進行更復雜的驗證，由于這些復雜的驗證，PoA才表現(xiàn)出了一些額外的優(yōu)勢.

PoA協(xié)議中主要的執(zhí)行過程是follow-the-satoshi[10].這個過程主要是通過選取一些偽隨機數(shù)來生成一個satoshi(數(shù)字貨幣流通的最小單位)值.這個選擇過程也是與PoS中的幣齡相關，幣齡越大，被選中為權益持有者的可能性越大[11].比如說Alice持有6個幣，Bob持有3個幣，那么Alice在上述過程中的勝出概率為Bob的2倍.這個過程與這些錢的積累過程無關，只與總金額有關.

下面簡述PoA協(xié)議中區(qū)塊產生的過程：

1) 每個礦工首先使用自身的Hash算力通過工作量證明機制生成一個空塊頭(empty block header).這個空塊頭中不包含任何交易信息，其余信息與普通塊相同.

2) 當某一個礦工成功生成一個空塊頭后，礦工將此空塊頭廣播全網(wǎng).

3) 全網(wǎng)節(jié)點通過此塊頭的Hash值來確定n個隨機的權益持有者.選取權益持有者的過程：首先將此塊頭的Hash值與前一個塊的Hash值連接，并在后面加上n個固定的后綴值.然后，將得到的n個值進行再一次的Hash.最后，將這n個值作為輸入，調用follow-the-satoshi子程序.

4) 在線的權益持有者檢查此空塊頭是否有效，即檢查Hash值是否符合現(xiàn)在的難度系數(shù).若合法，權益持有者檢查自己是否被選中，當全網(wǎng)有n-1個權益持有者發(fā)現(xiàn)自己被選中時，他們就對空塊頭的Hash值簽名，這樣就表明他們掌握了目前的satoshi值.當?shù)趎個權益持有者發(fā)現(xiàn)自己被選中后，他就可以在空塊頭的基礎上創(chuàng)建一個新塊，即在空塊頭中添加交易的信息，其余n-1個權益持有者的簽名和自己對整個塊的簽名信息.

5) 第n個權益持有者將新塊廣播全網(wǎng)，全網(wǎng)節(jié)點檢查此塊的有效性.權益持有者每次都是在最長鏈后產生新塊.

6) 礦工與n個權益持有者共享第n個權益持有者挖塊成功獲得的交易費.

在PoA協(xié)議中，最后生成區(qū)塊的第n個權益持有者獲得交易費將分給選出的n個權益持有者和產生空塊頭的礦工.這樣線上的礦工即使不挖礦，作為權益持有者也可以擁有一部分收益，這促使礦工保持線上運行，有利于貨幣的健康運行.但是對于每個節(jié)點的收益分配方式，并沒有給出具體的方案.

1.2 CoA(chains of activity)協(xié)議

CoA系統(tǒng)[12]采用了PoA的思想，對PoS機制進行改進，在一定程度上克服了PoS中的分叉問題.在CoA系統(tǒng)中，區(qū)塊產生的過程與PoA協(xié)議中產生區(qū)塊的過程類似.CoA系統(tǒng)中的協(xié)議叫做CoA協(xié)議，它主要基于PoS協(xié)議和PoA協(xié)議.此協(xié)議主要保證，在一定時間內，只有一名隨機選取的權益持有者可以創(chuàng)建新的區(qū)塊.其執(zhí)行過程類似于一個線上抽獎程序，所有權益持有者遵循CoA協(xié)議進行線上抽獎.每個權益持有者每次執(zhí)行follow-the-satoshi過程.

首先給出一些參數(shù)定義：挖礦所得的satoshi總額為2K；一個子分組的長度ω≥1；一個分組的總長度n=K×ω；comb函數(shù)：{0,1}n→{0,1}K；出塊的最小間隔時間G0；原始塊金額C0；塊獎勵金C1(0≤C1≤C0)；防雙花時間間隔T0.

CoA協(xié)議具體描述如下：

1) 所有的區(qū)塊可以看做是每個長度為l的連續(xù)區(qū)塊構成：每個區(qū)塊由一個權益持有者產生，他的身份必須是公開可驗證的，這個權益持有者收集滿足條件的交易向全網(wǎng)廣播，并創(chuàng)建第Bi塊.這個新塊中包含的信息有：這些交易的信息、前一塊的Hash值、目前的時間戳、索引i，以及用自己私鑰對這部分信息的簽名等.

2) 每個新產生的第Bi塊都和一個假定均勻分布的比特bi聯(lián)系起來，比如說取Hash(Bi)的第1個比特.

3) 第Bj塊和第Bi塊之間的時間間隔應該為|j-i-1|×G0.這就意味著如果存在連續(xù)的4塊分別為Bi,Bi+1,Bi+2,Bi+3，4個塊分別由Ai,Ai+1,Ai+2,Ai+3產生，但是如果Ai+1,Ai+2不想?yún)⑴c，那么第Bi+3塊和第Bi塊之間時間戳的間隔至少為2G0.如果出現(xiàn)的新塊的時間戳與當前時間相差太多，全網(wǎng)節(jié)點會認為此塊無效.

4) 產生前一個區(qū)塊的n個人可以選擇下一部分產生區(qū)塊的人，即生成一組長度為n的候選區(qū)塊Bi1,Bi2,…，Bin.全網(wǎng)節(jié)點使用comb函數(shù)生成一系列K比特的種子：

SBin=comb(bi1,bi2,…，bin).

即是將長度n和它的輸入聯(lián)系在一起的一個函數(shù)(如果ω=1).

5) 種子SBil用交替的方式通過執(zhí)行follow-the-satoshi過程來產生l個權益持有者.也就是說如果l個有效塊為

Bil+j1,Bil+j2,…，Bil+jl.

那么遵循協(xié)議的節(jié)點就可以通過執(zhí)行follow-the-satoshi過程并且將Hash(il,z,SBil)(z∈{1,2,…})作為輸入，就可以得知產生區(qū)塊Bil+jl+z的節(jié)點身份.

7) “三次”列入黑名單法則：若一個控制了輸出為txout0的權益持有者連續(xù)3次都沒有創(chuàng)建新塊，那么這個txout0就被列入了黑名單.也就是說，在下一組n個權益持有者開始創(chuàng)建新塊時，如果他們在執(zhí)行follow-the-satoshi過程，并且得到的Hash(in,z,SBil)指向了txout0，但是這個此時掌握txout0的人3次都沒有創(chuàng)建新塊，那么全網(wǎng)所有的誠實節(jié)點就會從第z-1步直接跳到了第z+1步重新執(zhí)行協(xié)議.假若txout0通過了一個正常的交易，那么構成輸出txout0的這筆錢就不再在黑名單中了.

如果全網(wǎng)節(jié)點遇到了很多競爭的長鏈，那么會將擁有最多塊數(shù)的那條鏈作為最終的一條鏈.

CoA協(xié)議中，在n個候選產生區(qū)塊的人中執(zhí)行follow-the-satoshi過程選取后一塊的生成人，生成區(qū)塊的人獲得收益與n個人共享收益.但是關于n個人中每個人具體的收益是多少并沒有給出分配方案.現(xiàn)在，我們希望對參與共識的每一個節(jié)點最終獲得的收益給出一個具體的描述，并且是一種直觀的表示方法.在博弈論中，Shapley使用公理的方法提出了沙普利值的概念.使用求解沙普利值的方法可以計算出每個節(jié)點的收益情況.由于沙普利值具有很好的經(jīng)濟意義，并且其求解方法淺顯易懂，所以其實用意義巨大.下面我們介紹博弈論中一些基本知識和定義.

1.3 博弈論基礎知識與沙普利值

博弈也叫對策，指的是帶有競爭或對抗性質的行為.博弈的基本要素包括：局中人、策略、收益、信息和行動順序[13].局中人就是在博弈中決策并最后獲得結果的團體，在CoA系統(tǒng)中，每個權益持有者就可以看做一個局中人.策略是局中人完整的相機抉擇的計劃[14].一個博弈結束后，每個局中人從這個博弈中的獲得就叫做收益.在博弈中，如果各個局中人達成了具有約束力的協(xié)議，則稱該博弈為合作博弈[15].在區(qū)塊鏈中各節(jié)點相互約束，共識機制規(guī)定了各個節(jié)點之間的約束條件，所以各節(jié)點執(zhí)行共識協(xié)議就可以看做是各節(jié)點之間進行合作博弈的過程.在合作博弈中，主要的討論對象是聯(lián)盟.下面，給出聯(lián)盟博弈的具體表示方法.

1.3.1 聯(lián)盟博弈

一個聯(lián)盟的博弈可以定義為一個二元組(N,v)[16]：

1) 有限集N表示局中人集合；

2) 函數(shù)v：2N|→是為每個聯(lián)盟(N的一個子集稱為一個聯(lián)盟)S?N定義了價值v(S).一個聯(lián)盟的收益也叫做聯(lián)盟的價值.函數(shù)v也稱為價值函數(shù)，并且我們規(guī)定v(φ)=0.

根據(jù)特征函數(shù)性質的不同，可以將博弈分為4類[13]：

1) 可加博弈.若對于任意的聯(lián)盟S，T?N，S∩T=?，滿足：v(S∪T)=v(S)+v(T)，則博弈G=(N,v)就是一個可加博弈.

2) 超可加博弈.若對于任意的聯(lián)盟S，T?N，S∩T=?，滿足：v(S∪T)≥v(S)+v(T)，則博弈G=(N,v)就是一個超可加博弈.

3) 次可加博弈.若對于任意的聯(lián)盟S，T?N，S∩T=?，滿足：v(S∪T)≤v(S)+v(T)，則博弈G=(N,v)就是一個次可加博弈.

4) 標準化博弈.若?i∈N，有v({i})=0，則稱博弈G=(N,v)是0標準化博弈；若?i∈N，有v({i})=0，且v(N)=1，則稱博弈G=(N,v)是0-1標準化博弈.

特殊地，在一個投票博弈中，|N|個局中人進行投票，若聯(lián)盟總的投票數(shù)過半，則獲勝.用W?2N表示獲勝的聯(lián)盟.對于任意屬于W的聯(lián)盟S，可以將價值函數(shù)v(S)定義成：

1.3.2 聯(lián)盟博弈收益分配

在聯(lián)盟博弈中，要解決的核心問題就是聯(lián)盟中的每個局中人的如何分配收益.在給出一個公平的分配方式之前，先給出博弈分析中的一些專有符號.首先，ψ：N×2|N||→|N|表示從一個聯(lián)盟博弈的集合(包括局中人集合N和一個價值函數(shù)v)到|N|個實數(shù)值的映射.對于x∈|N|，xi表示在聯(lián)盟中局中人i∈N的收益份額.在本文中將ψi(N,v)簡寫為xi.現(xiàn)在給出收益分配的一些基本定義.

定義1. 有效收益.給定聯(lián)盟博弈(N,v)，有效收益集合被定義為{x∈即有效價值集合是指每個局中人的收益不能超過聯(lián)盟的總價值.

定義2. 預估算(pre-imputation).給定聯(lián)盟博弈(N,v)，預估算集合用p表示，預估算集合被定義為{x∈由此可以看出，預估算集合是有效收益集合中收效最大的集合.即局中人分配了聯(lián)盟中所有的價值.

定義3. 估算(imputation).給定聯(lián)盟博弈(N,v)，估算集合用ρ表示，估算集合被定義為{x∈ρ|?i∈N,xi≥v(i)}.在估算集合中，每個局中人必須保證他們在聯(lián)盟中的收益要不少于他們自己作為一個聯(lián)盟的收益.

1.3.3 沙普利的公理化方法[16]

首先，如果對于任何既不包含局中人i，也不包含局中人j的聯(lián)盟S中，N中的2個局中人i和j在函數(shù)v的意義上都有v(S∪{i})=v(S∪{j})，則i，j稱為可以相互替代的.下面對稱性公理表明對于可以相互替代的局中人，他們獲得的收益應該是相等的.

公理1. 對稱性(symmetry).對于任意v，如果i，j是可以相互替代的，則:

ψi(N,v)=ψj(N,v).

接著，給出載體(carrier)的概念.

定義4. 載體(carrier).給定聯(lián)盟博弈(N,v)，若對于?S∈N,T∈N，存在v(S)=v(S∩T)，則稱T為博弈(N,v)的一個載體.

載體通常不唯一，如果T為博弈(N,v)的一個載體，T?T1，則T1也是博弈(N,v)的一個載體.載體之外的局中人i稱為啞元(dummy player).啞元對于任何聯(lián)盟沒有貢獻，即啞元加入任何聯(lián)盟，該聯(lián)盟的收益不會發(fā)生變化.下面的公理說明在進行收益分配時，不必要考慮啞元的存在，即不需要分配收益給啞元.

公理2. 有效性(effective).對于任意v的任何載體T,都有:

最后，考慮2個不同的博弈，即對于同一個局中人集合分別定義2個不同的價值函數(shù)v1，v2.下面給出可加性公理.

公理3. 可加性(additivity).給定2個價值函數(shù)v1，v2，對于任意局中人i，都有ψi(N,v1+v2)=ψi(N,v1)+ψi(N,v2)，并且對于聯(lián)盟S，博弈(N,v1+v2)，(N,v1)和(N,v2)滿足:

(v1+v2)(S)=v1(S)+v2(S).

介紹完上述3個公理后，將引出一個重要結論：總是存在一個預估算滿足公理1～3.

引理1. 對于一個聯(lián)盟博弈(N,v)，總是存在一個特定的預估算φ(N,v)=φ(N,v)，滿足對稱性、啞元和可加性公理.這個特定的收益估算φ(N,v)，就是沙普利值.

定義5. 沙普利值.給定一個聯(lián)盟博弈(N,v)，每個局中人的沙普利值為

這個等式可以看做是計算局中人i的“平均邊際效益”[17].假設N個局中人被排序了，并且假設根據(jù)順序，在聯(lián)盟S(不包含i)中，每一個局中人獲取其之前的局中人形成的聯(lián)盟的邊際遞增價值.那就是第i個局中人獲得的價值為v(S∪{i})-v(S),然后計算局中人i的邊際遞增價值的數(shù)目，在聯(lián)盟S(不包含i)中，所有排在局中人i之前的排列方式一共有|S|!種，在局中人i之后，剩余局中人的排列方式一共有(|N|-|S|-1)!種.最后對所有可能聯(lián)盟S中的邊際遞增價值求和，求均值.

2 基于沙普利值的CoA系統(tǒng)的改進與分析

2.1 基于沙普利值的CoA協(xié)議

現(xiàn)在我們詳細描述改進后的CoA協(xié)議，并給出每個權益持有者收益的計算方式.假設區(qū)塊鏈中有n個候選權益持有者，每個權益持有者標號為1,2,…，i，…,n.這n個權益持有者可以構成一個大的集合：

N={1,2,…，i，…,n}.

這n個權益持有者的總幣齡可以表示為

在n個權益持有者中，把每個節(jié)點的幣齡占比看做每個節(jié)點的投票權，可表示為

ω1，ω2，ω3，…，ωi，…,ωn,

則：

記挖塊所得的收益為R，所以每個權益持有者i獲得的收益為

Ri=φi(N,v)×R.

這樣，就給出了改進的CoA協(xié)議中每個權益持有者收益的計算公式,所以就可以給出一個完整的CoA的改進方案. 改進后的CoA協(xié)議描述如下：

1) 每個礦工通過工作量證明機制生成一個不包含任何交易信息空塊頭，其余信息與普通塊相同.

2) 當某一個礦工成功生成一個空塊頭后，礦工將此空塊頭廣播全網(wǎng).

3) 產生此塊頭的礦工通過調用follow-the-satoshi子程序來確定n個隨機的權益持有者.

4) 在線的權益持有者檢查此空塊頭是否有效，即檢查Hash值是否符合現(xiàn)在的難度系數(shù).若合法，權益持有者檢查自己是否被選中，當全網(wǎng)有n個權益持有者發(fā)現(xiàn)自己被選中時，他們就對空塊頭簽名，這樣就表明他們掌握了目前的satoshi值.

5)n個權益持有者進行投票，選出生成塊的人.每個人的幣齡占比就為其投票權.每個權益持有者出示的幣齡必須為他合法擁有的幣齡.

6) 當?shù)趇個權益持有者發(fā)現(xiàn)自己被選中后，他就可以在空塊頭的基礎上創(chuàng)建一個新塊，即在空塊頭中添加交易的信息，其余n-1個權益持有者的簽名和自己對整個塊的簽名信息.

7) 第i個權益持有者將新塊廣播全網(wǎng)，全網(wǎng)節(jié)點檢查此塊的有效性.權益持有者每次都是在最長鏈后產生新塊.

8) 若一個被選舉出的權益持有者連續(xù)3次都沒有創(chuàng)建新塊，他就被列入了黑名單，然后再次進行投票，重新選舉出創(chuàng)建新塊的人.

n個權益持有者共享第i個權益持有者挖塊成功獲得的交易費，并按照每個節(jié)點的沙普利值進行分配.

2.2 基于沙普利值的CoA協(xié)議分析

2.2.1 合理性分析

對于改進后的CoA協(xié)議，候選出塊的每個權益持有者分紅占比和此節(jié)點的幣齡占比息息相關.

將這2個擁有最大幣齡占比的2個節(jié)點分別計做x和y.對于每個小的節(jié)點的排序，我們可以使用數(shù)組(a，b)來表示所有節(jié)點的排序情況[15]，a(或b)代表x(或y)出現(xiàn)之前的小節(jié)點的個數(shù).對應于數(shù)組(a,b),所有節(jié)點有2種排序：x先于y，或者y先于x.對應于每一種其他的數(shù)對，只有一種排序，因此可能的排序如圖1所示.

Fig. 1 Sort representation of each node圖1 各節(jié)點的排序表示

所以，在這種情況下，2個幣齡占比大約為33%的大節(jié)點所得的收益為30%.對比前面描述的存在一個幣齡占比為50%大節(jié)點所得的收益大約為66.7%的情況，我們可以發(fā)現(xiàn)多個大節(jié)點數(shù)目增加的時候，每個大節(jié)點得到相對收益會降低.這種現(xiàn)象當然是我們現(xiàn)在比較喜歡的，如果在區(qū)塊鏈中的擁有大量算力或者幣齡的大節(jié)點不斷增加，這些節(jié)點的收益不會隨著大節(jié)點的增多而獲得更多的收益，這樣就能有效改善“富者更富，窮者更窮”的局面.

Fig. 2 Sort representation of each node圖2 多節(jié)點下各節(jié)點的排序表示

該合作博弈的幣齡占比和博弈結果可以表示為

雖然我們的模型對現(xiàn)有的各節(jié)點情況進行了簡化，但是仍然可以發(fā)現(xiàn)，在候選出塊者中的大節(jié)點數(shù)目大于2時，小節(jié)點數(shù)目的增加會使得大節(jié)點的收益下降.現(xiàn)在綜合所有情況，可得出以下結論：如果存在大量的小節(jié)點，大節(jié)點只需要得到它們需要數(shù)量的小幣齡節(jié)點的跟隨，就能獲得較大收益.事實上，在這種改進的機制中，小節(jié)點的收益將會變得更多.并且相對較小的節(jié)點并不會聚集在一起，而是保持獨立，游走于各大節(jié)點之間.這種現(xiàn)象有利于使節(jié)點獨立運行，小節(jié)點之間不容易形成團體，有利于共識機制的健康運行.

2.2.2 公平性分析

現(xiàn)在我們從2個角度來說明沙普利值按照各個局中人的幣齡占比來進行收益分配的公平性[11].

此期望收益就是沙普利值.

從節(jié)點之間組成的隨機聯(lián)盟的角度來考慮，設:

記:

和

即期望收益就是沙普利值.

由此可以看出某一節(jié)點的沙普利值即為此節(jié)點的期望收益，所以沙普利值是按照每個節(jié)點的幣齡大小來進行收益分配的一種公平性分配方案.

3 基于沙普利值的Ouroboros協(xié)議改進

Ouroboros是Aggelos等人在Crypto 2017提出的基于PoS的可證明安全協(xié)議[18]，本文引用該協(xié)議模型，對協(xié)議的權益部分進行改進.

Ouroboros協(xié)議及改進描述如下：

1) 初始階段.初始化節(jié)點k和公鑰vk，vk對應的權益sk，初始種子真隨機數(shù)ρ，定義當前的時期epoch，定義時間段slot.

2) 執(zhí)行階段.

① 每個節(jié)點根據(jù)當前的時期epoch對應的ρ執(zhí)行f(follow-the-satoshi)，根據(jù)每個節(jié)點k對應的公鑰vk和權益sk決定區(qū)塊并返回每個節(jié)點對應的分紅占比sk*.

② 節(jié)點k′生成區(qū)塊，將區(qū)塊收益按照每個節(jié)點對應的分紅占比sk*分給對應的節(jié)點，同時根據(jù)安全多方計算生成真隨機數(shù)ρ和下一個時期的epoch，對隨機數(shù)ρ進行承諾.

Ⅰ. 其余的節(jié)點等待節(jié)點k′生成區(qū)塊;

Ⅱ. 時間段slot內收到區(qū)塊，驗證節(jié)點k′生成區(qū)塊;

Ⅲ. 超過時間段slot未收到區(qū)塊，認為節(jié)點k′放棄區(qū)塊.

③ 重復②直到更新時期epoch.

④ 所有節(jié)點對隨機數(shù)ρ進行檢驗.開啟下個時期epoch，進入②.

follow-the-satoshi(4個節(jié)點的情況)[8]描述如下：

輸入:節(jié)點k對應的權益sk、真隨機數(shù)ρ執(zhí)行:

① 根據(jù)每個節(jié)點k對應的權益sk構造FTS-Merkle樹.原始版本的Merkle樹如圖3所示.改進后的Merkle樹如圖4所示.

Fig. 3 Original version of FTS-Merkle tree圖3 原始版本的FTS-Merkle

Fig. 4 Improved version of FTS-Merkle tree圖4 改進后的FTS-Merkle樹

③ 根據(jù)每個節(jié)點k的權益sk計算沙普利值得到每個節(jié)點對應的分紅占比sk*

④ 返回節(jié)點k′的值和每個節(jié)點對應的分紅占比sk*

輸出:某個節(jié)點k′和每個節(jié)點k的分紅占比sk*.

改進后的協(xié)議利用每個節(jié)點k對應的權益sk計算對應的沙普利值φ(vk)，利用φ(vk)計算每個節(jié)點k對應的收益占比

我們引用Garay關于比特幣主干協(xié)議的要求[19]:

① 存活性(liveness)

如果交易是城實的，改進的協(xié)議滿足經(jīng)過一段時間的確認，該交易將保證持續(xù)穩(wěn)定，即不會再更改.存活性可以保證交易的有效時間，當經(jīng)過一段時間之后，交易必須得到處理——接受或被拋棄.

② 持久性(persistence)

如果網(wǎng)絡中存在某個誠實的節(jié)點聲稱接受了某個交易，那么如果剩下的節(jié)點誠實的執(zhí)行協(xié)議，則剩下的節(jié)點也會回應該交易是穩(wěn)定的.在保證持久性的過程中，需要確定一些安全參數(shù)k.持久性可以保證區(qū)塊的不可更改性，如果某個區(qū)塊之后有k個塊被確認，則該區(qū)塊的交易不可更改.

如果Ouroboros協(xié)議滿足以上2條性質，基于沙普利值的Ouroboros協(xié)議依然滿足以上2條性質，只是在區(qū)塊的確認時間上有小的調整，但依然滿足存活性和持久性.

4 結論與下一步工作

本文使用改進的CoA系統(tǒng)中的收益分配方案，通過計算每個節(jié)點沙普利值對收益進行了公平分配，并在一定程度上緩解了51%攻擊.不僅如此，如果大節(jié)點的數(shù)量不斷增加的話，并不會出現(xiàn)“強者更強”的局面.因此，此種改進后的收益分配方式也對小節(jié)點有利，這就從根本上扭轉了區(qū)塊鏈中“弱者更弱”的局面.

重新基于計算幣齡的沙普利值對收益進行分配的方法有效的解決了區(qū)塊鏈中存在的大礦池們一家獨大的情況，實現(xiàn)了收益分配的均衡化. 不僅如此，在這種分配方式下，新加入的小節(jié)點獲得收益的可能性較原來有所提高.同時將相同的思想應用到Ouroboros協(xié)議中，對Ouroboros協(xié)議的收益分配算法進行了改進，并滿足了存活性和持久性.

對于改進后的方案，其中很多的細節(jié)部分還需要進一步的改進與優(yōu)化.比如在分配幣齡方案中每一次進行挖塊之前都要計算各節(jié)點的幣齡占比，必將耗費一定時間代價，若存在挖礦成功節(jié)點不遵守協(xié)議獨吞收益的情況，如何設置懲罰措施等.