基于排隊博弈的最優(yōu)比特幣交易費支付策略

黃冬艷，李 浪

（廣西無線寬帶通信與信號處理重點實驗室（桂林電子科技大學(xué)），廣西桂林 541004）

0 引言

比特幣［1］是以區(qū)塊鏈技術(shù)為支撐的一種數(shù)字貨幣。在比特幣系統(tǒng)中，數(shù)據(jù)以區(qū)塊（block）為單位產(chǎn)生和存儲，并按照時間順序連成鏈?zhǔn)剑╟hain）數(shù)據(jù)結(jié)構(gòu)。區(qū)塊之間通過哈希值進(jìn)行關(guān)聯(lián)。后一個區(qū)塊的哈希值由前一個區(qū)塊的哈希值、隨機(jī)數(shù)以及若干等待處理的交易關(guān)參數(shù)共同決定。新區(qū)塊的創(chuàng)建需得到全網(wǎng)多數(shù)節(jié)點的確認(rèn)并向各節(jié)點廣播實現(xiàn)全網(wǎng)同步。任何一個區(qū)塊的改動將會導(dǎo)致該區(qū)塊的哈希值發(fā)生變化，從而與鏈上其他區(qū)塊的哈希值無法匹配。因此，比特幣具有去中心化、難以篡改等特性，受到廣泛關(guān)注。其底層技術(shù)區(qū)塊鏈的應(yīng)用已經(jīng)延伸到智能制造［2］、物聯(lián)網(wǎng)［3-5］、供應(yīng)鏈［6］、電力競價［7］交易等領(lǐng)域。

比特幣網(wǎng)絡(luò)的共識機(jī)制為工作量證明（Proof of Work，PoW）。在PoW 共識機(jī)制下，為獲得記賬權(quán)或稱出塊權(quán)，每個參與節(jié)點必須找到符合條件的哈希值所需要的隨機(jī)數(shù)。尋找隨機(jī)數(shù)的過程稱為“挖礦”，參與“挖礦”的節(jié)點稱為礦工。

目前礦工的收益由挖礦獎勵和交易費兩部分組成［8］。挖礦獎勵是指，伴隨著新區(qū)塊的產(chǎn)生會生成一定數(shù)量的比特幣，作為挖出該區(qū)塊的礦工的工作獎勵；交易費也稱手續(xù)費，由用戶自行設(shè)置，交易費作為額外獎勵發(fā)給處理該交易的礦工。

交易費的存在增加了欺詐交易與無效交易的成本，從一定程度上避免了系統(tǒng)濫用；同時，交易費的高低很大程度上影響著交易的優(yōu)先級。由于比特幣中每一個區(qū)塊的空間大小有一定限制，礦工需要依據(jù)多種因素（如塊齡、交易費、交易大小等），選擇將待處理的交易打包進(jìn)入?yún)^(qū)塊。為最大化自身的收益，礦工往往更愿意處理交易費高的交易。因此，交易費越高的交易被優(yōu)先打包進(jìn)入?yún)^(qū)塊的概率越高，相應(yīng)的交易耗時就越少。實際上，自2016 年初以來，比特幣網(wǎng)絡(luò)容量的限制已經(jīng)造成交易之間的競爭，從而導(dǎo)致更高的費用，免費交易徹底成為過去式。零費用或非常低費用的交易鮮少被處理，有時甚至不會在網(wǎng)絡(luò)上傳播［8］。文獻(xiàn)［9］的調(diào)查結(jié)果也表明，交易的處理速度與交易的金額無關(guān)，而與交易費強(qiáng)相關(guān)，非零交易費的交易的處理速度比零交易費的交易要快。

對用戶而言，交易能否被快速處理和所需交易費都是其關(guān)心的主要問題。交易費過高增加了用戶交易成本，過低則會增加用戶的交易耗時。因此，研究交易費與交易耗時之間的關(guān)系有助于揭示系統(tǒng)的交易運作規(guī)律，從而幫助用戶選擇合適的支付策略。

文獻(xiàn)［10］研究了在股權(quán)證明的聯(lián)盟鏈中，共識延遲與用戶交易費之間的權(quán)衡。文獻(xiàn)［11］結(jié)合排隊理論，分析了區(qū)塊鏈中的三個關(guān)鍵性能指標(biāo)（系統(tǒng)中的平均交易數(shù)、單個區(qū)塊中的平均交易數(shù)、交易的平均確認(rèn)時間），設(shè)計了一個具有兩個不同服務(wù)階段的馬爾可夫批量服務(wù)排隊系統(tǒng)。文獻(xiàn)［12］通過在用戶交易之間引進(jìn)第三方保險機(jī)構(gòu)的做法來解決比特幣的雙花風(fēng)險問題，給用戶提供了交易安全保障。文獻(xiàn)［13］將比特幣交易按照交易金額大小分類，發(fā)現(xiàn)小額交易（交易金額小于1比特幣）的用戶占比更高，處理速度更慢。文獻(xiàn)［14-16］基于排隊論研究了系統(tǒng)容量、交易速率等問題。以上文獻(xiàn)分析了系統(tǒng)容量、交易安全和交易速率等，但未能考慮用戶之間的博弈以及用戶個體的策略性決策行為對交易速率的影響。

結(jié)合排隊博弈論，本文研究了比特幣網(wǎng)絡(luò)中用戶交易手續(xù)費對交易耗時的影響，旨在為用戶提供最優(yōu)的交易手續(xù)費支付策略。本文的主要貢獻(xiàn)如下：1）將比特幣網(wǎng)絡(luò)中交易排隊競爭上鏈的過程建模為一個帶優(yōu)先權(quán)的非搶占型排隊博弈模型；2）分析了交易費對交易耗時的影響并推導(dǎo)出用戶的納什均衡支付策略。

1 系統(tǒng)模型

一筆交易從提交到比特幣系統(tǒng)中到被記錄到區(qū)塊中的過程如圖1 所示。由PoW 共識機(jī)制決定，比特幣的交易不是實時完成的，只有交易被寫入?yún)^(qū)塊并廣播交易才算完成。通常認(rèn)為，連續(xù)篡改6 個以上區(qū)塊［8］難度極大，因此真正確認(rèn)一筆交易需經(jīng)歷6個區(qū)塊。

圖1 交易上鏈?zhǔn)疽鈭DFig.1 A transaction going up on blockchain

每個區(qū)塊的大小上限為1 MB［17］（比特幣在2017年8月24日實施了隔離見證（Segregated Witness，SegWit）方案，將交易數(shù)據(jù)與交易簽名進(jìn)行了分離，區(qū)塊的實際大小仍為1 MB，但是加上簽名信息后，總大小突破了1 MB 上限）。其中，前50 KB 保留給UTXO（Unspent Transaction Output）優(yōu)先級高的交易，剩下的區(qū)塊空間由其他交易競爭，礦工優(yōu)先選擇交易手續(xù)費高的交易來填充剩下的空間。

交易的UTXO 優(yōu)先級由交易的UTXO 模型［8］決定。UTXO從被記錄到區(qū)塊鏈中到當(dāng)前交易處理時的區(qū)塊鏈末端所經(jīng)歷的區(qū)塊數(shù)，稱為“塊齡”。交易輸入值高、“塊齡”大的交易比那些新的、輸入值小的交易擁有更高的優(yōu)先級。具體地，UTXO優(yōu)先級的定義為：

其中：N是交易的總輸入個數(shù)，l表示交易的總大小，Vi表示交易第i個部分輸入的金額，單位是聰，Ai是其“塊齡”。當(dāng)一筆交易的Hp＞5.76×107時（相當(dāng)于1 比特幣、塊齡為144（大約為1 d）、交易大小為250 B），可以被打包進(jìn)前50 KB中。

由于相較于1 MB 的區(qū)塊空間，前50 KB 的字節(jié)占比很小，后面的大部分的區(qū)塊空間通過交易費的高低競爭。因此本文僅討論交易手續(xù)費對交易耗時的影響。交易耗時為交易的等待時間與交易的處理時間之和，如圖1 所示。其中，等待時間為交易提交到系統(tǒng)到被打包進(jìn)區(qū)塊的時間，交易處理的時間為服務(wù)時間，也即挖礦過程。

后續(xù)分析中的優(yōu)先級區(qū)別于UTXO 優(yōu)先級，專指用戶通過支付交易費獲得的被優(yōu)先打包進(jìn)入除前50 KB 字節(jié)以外的區(qū)塊空間的優(yōu)先權(quán)。

2 排隊博弈模型與均衡支付策略

2.1 排隊模型

假設(shè)每個到達(dá)的用戶不知道當(dāng)前系統(tǒng)中的交易數(shù)量，也不知道其他用戶支付的交易費。用戶在進(jìn)隊時要選擇最優(yōu)的支付策略使得自己的總花費最小，并且交易一旦提交交易費不可更改。

礦工處理交易的流程如圖2 所示。礦工根據(jù)交易費將當(dāng)前交易池中的交易按照交易費高低進(jìn)行排序，選取當(dāng)中的前若干筆交易組成一個批次進(jìn)行處理，生成一個區(qū)塊，該批次中的交易費雖有不同，卻一同被處理，因此將其視為同優(yōu)先級的一筆業(yè)務(wù)，用其交易費均值表示此筆業(yè)務(wù)的優(yōu)先級。接著，礦工開始進(jìn)行PoW 工作處理這筆業(yè)務(wù)。基于PoW 的特性，交易一旦選定不可更改，因此，此時到達(dá)系統(tǒng)的交易無論交易費的高低，都必須等待當(dāng)前交易處理完畢，即非搶占型優(yōu)先權(quán)?；诒忍貛诺某鰤K特性（一次只能出一個單塊），因此將礦工視為單一性服務(wù)臺處理。一筆業(yè)務(wù)交易處理完成后，加入新到達(dá)的交易，對交易池進(jìn)行重排列。

圖2 礦工交易處理流程Fig.2 Miners processing transactions

參照文獻(xiàn)［17-18］，本模型設(shè)定交易到達(dá)（指批次，下同）是參數(shù)為λ的泊松流，交易的處理時間（服務(wù)時間）服從參數(shù)為μ的指數(shù)分布。記ρ=，為系統(tǒng)的擁塞指標(biāo)。ρ越大意味著系統(tǒng)越擁擠，在區(qū)塊生成時間穩(wěn)定的情況下意味著交易量增大。因此，整個過程可建模為一個有非搶占型優(yōu)先權(quán)和隨機(jī)服務(wù)的M/M/1排隊系統(tǒng)。

2.2 平均交易耗時

假設(shè)當(dāng)前系統(tǒng)中有n批交易，且n≥0。第i批用戶ui支付的交易費均值為xi，則用戶ui的優(yōu)先級等價于交易費的總占比出，即

2.3 均衡交易費支付策略

命題2 設(shè)單位等待費用為c，用戶總花費為x+cW(x)，用戶的納什均衡支付策略為支付交易費-x，有：

證明 假設(shè)所有批次交易支付的交易費為1，若最優(yōu)策略為支付，需滿足：

由式（9）可知，W(x)是下凸函數(shù)，因此當(dāng)c＞0時必存在唯一最優(yōu)解-x。求解式（14）可以得到式（13）。證畢。

3 仿真與評估

3.1 交易費對交易耗時的影響

根據(jù)式（9）得到平均交易耗時隨交易費的變化如圖3所示。

圖3 不同ρ下平均交易耗時隨交易費的變化Fig.3 Average transaction time changing with transaction fee with different ρ

從圖3 中可以看出，給定系統(tǒng)擁塞ρ，用戶的平均交易耗時隨著交易費的增加而減小。在支付交易費一定時，如果交易增多，系統(tǒng)的擁塞指標(biāo)增大即系統(tǒng)交易量增大，則用戶的平均交易耗時也會隨之增加。

3.2 用戶的交易費支付策略

不同交易費支付策略下用戶的平均交易耗時與用戶的總花費的對比分別如圖4和圖5所示。

圖4 平均交易耗時對比Fig.4 Comparison of average transaction time

從圖4 中可以看出，在不同的系統(tǒng)狀態(tài)下，用戶采用均衡支付策略都可以將平均交易耗時維持在服務(wù)時間附近，即用戶可以獲得最高優(yōu)先級，享受優(yōu)先服務(wù)。當(dāng)ρ=0.5 時，均衡支付策略的耗時約為7.7 min，比x=ρ策略減少了38%，比不支付交易費策略減少了61.3%。當(dāng)ρ=0.9（系統(tǒng)高負(fù)荷）時，均衡支付策略的平均交易耗時比不支付交易費策略減少了98%，比x=ρ支付策略減少了81.2%。

同時從圖5 可以看出，雖然采用均衡策略需要支付交易費，但是因為交易耗時下降，時間成本大幅度降低，所以用戶的總花費相對更小。當(dāng)ρ=0.7 時，均衡支付策略的用戶總花費比支付x=ρ的策略下降了45%，比不支付交易費的策略下降了79.5%。當(dāng)ρ=0.9 時，均衡支付策略的用戶總花費比支付x=ρ的策略下降了72%，比不支付交易費的策略下降了97%。從圖4和圖5可以看出，隨著ρ的增大，均衡支付策略的優(yōu)勢更加明顯。

圖5 用戶總花費對比Fig.5 Comparison of user total cost

綜上所述，用戶可根據(jù)系統(tǒng)擁塞程度采用最優(yōu)的支付策略，保證交易被盡快處理的同時避免過高的交易費支出；另一方面，用戶還可以根據(jù)系統(tǒng)擁塞程度和自身對交易耗時的要求，根據(jù)命題1 的結(jié)論，計算出保證自己的交易在預(yù)期時間內(nèi)上鏈所需的交易費。

4 結(jié)語

本文通過排隊博弈論研究了比特幣系統(tǒng)中交易費對平均交易耗時的影響，推導(dǎo)出了平均交易耗時與交易費、系統(tǒng)擁塞指標(biāo)之間的關(guān)系式，并給出了用戶的納什均衡支付策略。在后續(xù)研究中，可以從礦工收益出發(fā)，考慮區(qū)塊大小一定的情況下，如何選擇交易填滿有限的區(qū)塊空間來最大化礦工收益的問題。