混合策略下的理性交換協(xié)議模型

丁洪，彭長(zhǎng)根，鄺青青

（1. 貴州大學(xué)理學(xué)院，貴州 貴陽(yáng) 550025；2. 貴州大學(xué)密碼學(xué)與數(shù)據(jù)安全研究所，貴州 貴陽(yáng)550025）

混合策略下的理性交換協(xié)議模型

丁洪1，2，彭長(zhǎng)根1，2，鄺青青1，2

（1. 貴州大學(xué)理學(xué)院，貴州 貴陽(yáng) 550025；2. 貴州大學(xué)密碼學(xué)與數(shù)據(jù)安全研究所，貴州 貴陽(yáng)550025）

在小額支付的交換協(xié)議中，通過(guò)TTP保證協(xié)議公平性所需代價(jià)往往高于協(xié)議本身價(jià)值，在這種情況下，理性交換協(xié)議是一種合適的選擇。應(yīng)用擴(kuò)展式博弈混合策略理論對(duì)交換協(xié)議進(jìn)行了建模，引入熵函數(shù)對(duì)交換過(guò)程中的公平性進(jìn)行了描述；在保證過(guò)程公平性原則的前提下，運(yùn)用混合策略納什均衡概念形式化定義了理性公平性，并在此模型基礎(chǔ)上構(gòu)造了一個(gè)新的理性交換協(xié)議；對(duì)協(xié)議的可追究性、理性公平性進(jìn)行了證明，結(jié)果表明該協(xié)議能達(dá)到混合策略納什均衡。該協(xié)議無(wú)須可信第三方，實(shí)現(xiàn)了理性公平性并對(duì)懲罰值進(jìn)行了優(yōu)化，具有更好的適應(yīng)性。

理性交換協(xié)議；混合策略；過(guò)程公平；納什均衡

中文分類(lèi)號(hào)：TP309

1　引言

交換協(xié)議被廣泛應(yīng)用在電子合同簽署、電子郵件認(rèn)證和網(wǎng)絡(luò)支付服務(wù)等領(lǐng)域，如何保證交換過(guò)程中各方參與者的公平性是交換協(xié)議的一個(gè)重要問(wèn)題，目前，主要依賴(lài)于公平交換原則和理性交換原則來(lái)解決。傳統(tǒng)的公平交換協(xié)議通常以可信第三方（TTP，trusted third party）或復(fù)雜的通信為代價(jià)來(lái)保證公平性的實(shí)現(xiàn)，可信第三方容易成為瓶頸。理性交換不需要可信第三方，在實(shí)現(xiàn)理性公平性的同時(shí)提高了效率，因此理性交換逐漸成為研究熱點(diǎn)。在微支付協(xié)議中，保證強(qiáng)公平性的代價(jià)往往高于支付協(xié)議本身的價(jià)值，從而強(qiáng)公平性不再適用于這類(lèi)協(xié)議，而理性交換能提供更合適的解決方法。

1998年，Asokan［1］首次將博弈論應(yīng)用到公平交換協(xié)議的分析設(shè)計(jì)中，同年 Syverson［2］首次提出了理性交換的概念，即在交換過(guò)程中，參與者的不誠(chéng)實(shí)行為可能會(huì)對(duì)其他參與者的利益造成損失，但是參與者不會(huì)因不誠(chéng)實(shí)行為而獲利。換言之，理性交換不能夠完全保證公平性，但理性參與者沒(méi)有理由偏離協(xié)議。2001年，Buttyan等［3］運(yùn)用博弈論的方法給出了公平性的形式化定義，基于擴(kuò)展式博弈對(duì)交換協(xié)議進(jìn)行了建模并對(duì)Syverson協(xié)議進(jìn)行了分析。針對(duì)Syverson協(xié)議中的不足，Alcaide等［4～6］應(yīng)用不完全信息動(dòng)態(tài)博弈理論，在交換協(xié)議中引入信念，建立了貝葉斯博弈下的理性交換協(xié)議模型，使理性交換更加符合現(xiàn)實(shí)應(yīng)用環(huán)境。在文獻(xiàn)［7］中，作者基于極大熵原理設(shè)計(jì)了一個(gè)新的理性交換協(xié)議，并對(duì)協(xié)議的安全性和公平性進(jìn)行了證明。上述研究成果都只對(duì)交換協(xié)議的結(jié)果公平性進(jìn)行了討論，并未涉及過(guò)程公平性的分析。而本文考慮用信息論中的熵理論［8］對(duì)過(guò)程公平性進(jìn)行描述，并探討過(guò)程公平原則下的理性公平性。

本文應(yīng)用擴(kuò)展式博弈下的混合策略［9］對(duì)理性交換協(xié)議進(jìn)行建模，給出此模型下的混合策略納什均衡定義；通過(guò)引入熵理論對(duì)過(guò)程公平性進(jìn)行描述，給出過(guò)程公平性的定義；在過(guò)程公平性原則下，利用博弈樹(shù)對(duì)整個(gè)交換過(guò)程進(jìn)行分析并給出協(xié)議的可追究性［10］、理性公平性的證明。結(jié)果表明該協(xié)議能達(dá)到混合策略納什均衡。協(xié)議交換過(guò)程無(wú)須可信第三方，該協(xié)議實(shí)現(xiàn)了理性公平性并對(duì)懲罰值進(jìn)行了優(yōu)化，具有更好的適應(yīng)性。

2　理性交換協(xié)議的混合策略模型

博弈論是研究決策問(wèn)題的理論。在博弈過(guò)程中，參與者會(huì)極力猜測(cè)對(duì)方如何選擇，同時(shí)又不想讓對(duì)方猜到自己的選擇，在這樣的情況下，參與者往往會(huì)隨機(jī)選擇自己的策略。混合策略解釋了一個(gè)參與者對(duì)其他參與者所采取行動(dòng)的不確定性，它描述了參與者在給定信息下以某種概率分布隨機(jī)地選擇不同的行動(dòng)或策略。可以通過(guò)引用熵對(duì)這樣的不確定性進(jìn)行描述。

在小額支付協(xié)議中，選擇可信第三方來(lái)保證公平性所需的代價(jià)往往高于支付協(xié)議本身。在這種情況下，理性交換協(xié)議是一種合適的選擇。而協(xié)議參與者進(jìn)行信息交互的過(guò)程可以看作一個(gè)混合策略擴(kuò)展式博弈過(guò)程，因此可以利用混合策略擴(kuò)展式博弈理論對(duì)其進(jìn)行建模。

2.1基礎(chǔ)知識(shí)

1）混合策略

4）混合策略Nash均衡

2.2混合策略下的交換協(xié)議模型

下面將一個(gè)交換協(xié)議記為π，其執(zhí)行的過(guò)程看作一個(gè)混合策略擴(kuò)展式博弈進(jìn)行的過(guò)程，則可以將交換協(xié)議描述為與擴(kuò)展式博弈類(lèi)似的七元組其中各元素的含義如下。

1）T：參與者集合。

4）P：參與者函數(shù)，用于計(jì)算非終點(diǎn)行動(dòng)序列的下一個(gè)參與者。表示為對(duì)于任意非終點(diǎn)行動(dòng)序列表示非終點(diǎn)行動(dòng)序列q后的下一個(gè)參與者。

在對(duì)收益值進(jìn)行計(jì)算的過(guò)程中，加入一個(gè)懲罰函數(shù) F。在協(xié)議執(zhí)行的每一輪中，只要參與者采取某種不誠(chéng)實(shí)行為，就在他的收益值上減去相應(yīng)的懲罰函數(shù)。在計(jì)算最終收益時(shí)將每一輪的懲罰值都算入收益結(jié)果中。

2.3混合策略下的理性公平性

定義3過(guò)程公平性原則。在協(xié)議執(zhí)行過(guò)程中，若每個(gè)參與者在每個(gè)自己的可選行動(dòng)集上的策略熵函數(shù)相等，即則該交換協(xié)議是過(guò)程公平的。

定義4混合策略Nash均衡。將有2個(gè)參與者的交換協(xié)議記為π′，將交換協(xié)議看為一個(gè)博弈，2個(gè)參與者分別為A和B，參與者的混合策略集分別記為若一個(gè)交換協(xié)議是混合策略Nash均衡公平的，則其存在一個(gè)混合策略組合滿足

定義 5若一個(gè)交換協(xié)議在保證過(guò)程公平的前提下，能滿足混合策略Nash均衡公平性，則稱(chēng)該協(xié)議為一個(gè)理性交換協(xié)議。

3　一種新的理性交換協(xié)議

3.1理性交換協(xié)議的構(gòu)造

在以上的混合策略博弈模型的基礎(chǔ)上，構(gòu)建一個(gè)新的理性交換協(xié)議。假設(shè)進(jìn)行通信的網(wǎng)絡(luò)是可靠的，使用的加密方法是安全的，在保證過(guò)程公平的基礎(chǔ)上，通過(guò)對(duì)收益函數(shù)進(jìn)行調(diào)整，最終達(dá)到混合策略Nash均衡點(diǎn)，從而實(shí)現(xiàn)理性公平交換。

協(xié)議中有2個(gè)參與者A、B，A是商家，B是顧客。他們要交換的物品分別為假設(shè)他們用于交換的物品是等價(jià)的，即若協(xié)議正常執(zhí)行，則參與者A、B的收益均為0。協(xié)議中用到弱秘密承諾函數(shù)（）w k，在一定的時(shí)間內(nèi)，該函數(shù)無(wú)法破解。構(gòu)造的協(xié)議如圖1所示。

圖1　理性交換協(xié)議交互過(guò)程

步驟2參與者B能觀察到參與者A選擇發(fā)送消息的概率分布，為了保證過(guò)程公平性，B采取與A相同的概率分布選擇自己要發(fā)送的消息。假設(shè)參與者B是誠(chéng)實(shí)且理性的，他可以選擇發(fā)送的信息為

3.2理性交換協(xié)議的分析

下面從正確性、可追究性、公平性的角度對(duì)以上的理性交換協(xié)議進(jìn)行分析。首先，分析了在混合策略下該理性交換協(xié)議的正確性；其次，用 Kailar邏輯對(duì)該協(xié)議進(jìn)行了可追究性分析；最后，在過(guò)程公平性的原則下，基于博弈樹(shù)對(duì)整個(gè)協(xié)議過(guò)程進(jìn)行了描述，探尋了其混合策略Nsah均衡的存在性。

1）正確性

定理 1當(dāng)交換協(xié)議正常執(zhí)行完畢時(shí)，若協(xié)議主體A和B分別能夠獲得所交換的物品和，則上述基于混合策略下的理性交換協(xié)議是正確的。

證明通過(guò)協(xié)議的執(zhí)行過(guò)程，可以看到，當(dāng)協(xié)議完成后，參與者A能夠獲得消息并且 A可以利用自己的私鑰通過(guò)解密算法獲得經(jīng)過(guò)一定的時(shí)間后，通過(guò)弱秘密承諾函數(shù)得到從而通過(guò)計(jì)算得到想要交換的商品

綜上，當(dāng)協(xié)議正常執(zhí)行完畢時(shí)，各方參與者都能得到自己想要交換的商品itemA、itemB，即該混合策略下的理性交換協(xié)議是正確的。

2）可追究性

可追究性要求任何交易方必須為自己的行為負(fù)責(zé)，Kailar邏輯是專(zhuān)門(mén)針對(duì)電子商務(wù)可追究性進(jìn)行分析的邏輯。其有如下基本原理。

用Kailar邏輯對(duì)上述協(xié)議進(jìn)行形式化分析，若協(xié)議能滿足一定的目標(biāo)，則說(shuō)明該協(xié)議在Kailar邏輯下滿足可追究性。

定理 2在給定的初始狀態(tài)假設(shè)下，該協(xié)議在Kailar邏輯下具有可追究性。

證明根據(jù)Kailar邏輯的定義，該協(xié)議保證可追究性必須滿足的目標(biāo)如下。

對(duì)于協(xié)議目標(biāo)的推導(dǎo)有關(guān)的部分語(yǔ)句解釋如下。

引入如下初始狀態(tài)假設(shè)。

根據(jù)上述假設(shè)，利用Kailar邏輯進(jìn)行如下推理。

當(dāng)B收到消息①時(shí)，可得

由假設(shè)A3和簽名原理得

再由假設(shè)A5和推斷原理得

即滿足G2。

當(dāng)A收到消息②時(shí)，可得

由假設(shè)A1和簽名原理得

在由假設(shè)A4和連結(jié)原理得

最后，由假設(shè)A6和推斷原理得

即滿足G1。

同理可證目標(biāo)G3、G4能被滿足。

因此，該協(xié)議在Kailar邏輯下具有可追究性。

3）公平性

根據(jù)上述建立的模型，利用博弈樹(shù)對(duì)整個(gè)協(xié)議過(guò)程進(jìn)行描述，如圖2所示。

第二輪由參與者B開(kāi)始選擇行動(dòng)。參與者B不能夠區(qū)分A發(fā)送的消息是還是但是，B能夠觀察到A在可選行動(dòng)集上的概率分布。此時(shí)參與者B的信息集為了達(dá)到過(guò)程公平，即參與者B不想讓參與者A通過(guò)自己的行動(dòng)推測(cè)到更多的信息，B選擇以和A相同的概率分布選擇自己的行動(dòng)。此時(shí)在上的混合策略為，混合策略熵函數(shù)若參與者B選擇行動(dòng)，則博弈終止；若B選擇第二輪結(jié)束進(jìn)入第三輪，雙方受益待定。

下面分析此交換協(xié)議的公平性。在博弈過(guò)程中，每個(gè)參與者會(huì)極力猜測(cè)對(duì)方如何選擇，同時(shí)又不能讓對(duì)方猜到自己的選擇，為了使對(duì)方猜不透自己的選擇，會(huì)隨機(jī)選擇自己的策略，即以一定的概率分布去選擇自己的策略。通過(guò)分析，可以知道如下信息。

參與者A的純策略集為

相應(yīng)的混合策略為

參與者B的純策略集為

相應(yīng)的混合策略為

則可以得到如圖3所示的收益矩陣。

圖2　交換協(xié)議的博弈樹(shù)描述

圖3　收益矩陣

下面討論在什么條件下混合策略組合

為混合策略Nash均衡。

在過(guò)程公平的原則下，為了保證每一輪中的混合策略熵函數(shù)不變，假設(shè)θ=α=β。所以，參與者 A在混合策略組合下的期望收益為

當(dāng)參與者B選擇混合策略σB時(shí)，A選擇各個(gè)純策略的期望收益為

同理，可以對(duì)參與者B在混合策略

下的期望收益進(jìn)行討論。

當(dāng)參與者 A選擇混合策略σA時(shí)，參與者 B選擇純策略m2、quitB的期望收益為

通過(guò)以上分析可以看到，在所構(gòu)造的新的理性交換協(xié)議中，懲罰值并非越大越好。參與者遵守協(xié)議的概率與懲罰值和交換物品本身的價(jià)值之比有關(guān)。在這樣的情況下，可以通過(guò)對(duì)懲罰值的設(shè)定控制參與者遵守協(xié)議的概率分布，從而更好地促使參與者遵守協(xié)議。

3.3實(shí)例分析

表1　成本與選擇概率之間的關(guān)系

可以看到，隨著商家給出折扣的升高，顧客B在得到實(shí)惠的同時(shí)，所面臨風(fēng)險(xiǎn)的不確定度也在增大。此時(shí)商家的報(bào)價(jià)越接近商品的實(shí)際價(jià)值，則協(xié)議正常執(zhí)行的概率就越大。而這時(shí)若隨意改動(dòng)懲罰值，則有可能找不到滿足條件的θ。那么，原有的協(xié)議博弈在沒(méi)有均衡解的情況下，很難保證協(xié)議的正常進(jìn)行。而對(duì)于懲罰值的設(shè)定，并非越高越好。在所提出的模型中，過(guò)高的懲罰值反而會(huì)降低θ最大值的取值，讓商家望而卻步，從而降低了商家誠(chéng)信參與協(xié)議的概率。

4　結(jié)束語(yǔ)

本文在假設(shè)加密方法安全、網(wǎng)絡(luò)通道可靠的前提下，引入熵理論對(duì)協(xié)議交換過(guò)程中的不確定性進(jìn)行描述，進(jìn)而給出過(guò)程公平的定義，并在保證過(guò)程公平的原則下，應(yīng)用擴(kuò)展式博弈下的混合策略理論對(duì)理性交換協(xié)議進(jìn)行建模。結(jié)合所建模型和博弈論中混合策略Nash均衡的定義，本文對(duì)理性交換協(xié)議做了形式化的定義，并構(gòu)造了一個(gè)新的理性交換協(xié)議。而當(dāng)網(wǎng)絡(luò)不一定可靠以及過(guò)程不一定嚴(yán)格公平時(shí)，如何建立一個(gè)基于擴(kuò)展博弈的協(xié)議博弈模型，在這樣的模型中交換協(xié)議是否依然滿足理性公平將是進(jìn)一步研究的方向。

［1］ASOKAN N. Fairness in electronic commerce［D］. Waterloo：University of Waterloo，1998.

［2］SYVERSON P. Weakly secret bit commitment：applications to lotteries and fair exchange［C］//The 11th IEEE Computer Security Foundations Workshop. c1998：2-13.

［3］BUTTYAN L. Building blocks for secure services：authenticated key transport and rational exchange protocols［D］. Lausanne：Ecole Polytechnique Federale de Lausanne，2001.

［4］ALCAIDE A，ESTEVEZ-TAPIADOR J M，HERNANDEECASTRO J C，et al. An extended model of rational exchange based on dynamic games of imperfect information［C］//International Conference on Emerging Trends in Information and Communication Security. c2006：396-408.

［5］ALCAIDE A. Rational exchange protocols［D］. Leganés：Universidad Carlos III de Madrid，2008.

［6］ESTEVEZ-JAPIADOR J M，ALCAIDE A，HERMANDEZCASTRO J C，et al. Bayesian rational exchange［J］. International Journal of Network Security，2008，7（1）：85-100.

［7］呂楨，彭長(zhǎng)根，劉海. 基于極大熵原理的理性公平交換協(xié)議［J］.計(jì)算機(jī)應(yīng)用研究，2014，31（2）：563-567. LV Z，PENG C G，LIU H. Rational fairness exchange protocols based on maximum entropy principle［J］. Application Research of Computers，2014，31（2）：563-567.

［8］陳運(yùn). 信息論與編碼［M］. 北京：電子工業(yè)出版社，2007. CHEN Y.Information theory and coding［M］. Beijing：Publishing House of Electronics Industry，2007.

［9］朱·弗登博格，讓·梯若兒. 博弈論［M］. 黃濤，譯. 北京：中國(guó)人民大學(xué)出版社，2010. FUDENBERG D，TIROLE J. Game theory［M］. Translated by HUANG T. Beijing：China Renmin University Press，2010.

［10］王可心，韓芳溪. Kailar邏輯推理中初始狀態(tài)假設(shè)［J］. 大連理工大學(xué)學(xué)報(bào)，2003，43（1）：193-196. WANG K X，HAN F X. Initial state assumptions in Kailar logic reasoning［J］. Journal of Dalian University of Technology，2003，43（1）：193-196.

Rational exchange protocol model based on mixed strategy

DING Hong1，2，PENG Chang-gen1，2，KUANG Qing-qing1，2

（1. College of Science，Guizhou University，Guiyang 550025，China；2. Institute of Cryptography & Data Security，Guizhou University，Guiyang 550025，China）

In the exchange of micropayment protocol，the cost of ensuring fairness by TTP is higher than the value of protocol，in this case the rational exchange protocol is a appropriate choice. Exchange protocol was modeled by extensive mixed strategy game and the entropy function was introduced to discuss the fairness in the process of exchange. In addition，the rational fairness was formally defined by using the concept of mixed strategy Nash equilibrium under the principle of the fairness in the process，and on the basis of this model to construct a new rational exchange protolcol. The protocol's accountability and rational fairness were proved，the results show that the proposed protocol can achieve mixed stratrgy Nash equilibrium. Without the participation of the trusted third party，the protocol can achieve rational fairness and optimize the penalty values，it is beautifully adapted to the real environment.

rational exchange protocol，mixed strategy，process fairness，Nash equilibrium

A

10.11959/j.issn.2096-109x.2016.00016

2015-11-11；

2016-01-09。通信作者：彭長(zhǎng)根，peng_stud@163.com

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61262073）；全國(guó)統(tǒng)計(jì)科學(xué)研究計(jì)劃基金資助項(xiàng)目（No.2013LZ46）；貴州省統(tǒng)計(jì)科學(xué)研究課題基金資助項(xiàng)目（No.201511）

Foundation Items：The National Natural Science Foundation of China（No.61262073），The National Statistical Scientific Research Project（No.2013LZ46），The Guizhou Provincial Statistical Science Research Project（No.201511）

丁洪（1991-），女，貴州安順人，貴州大學(xué)碩士生，主要研究方向?yàn)槊艽a學(xué)理論與工程。

彭長(zhǎng)根（1963-），男，侗族，貴州錦屏人，博士，貴州大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)槊艽a學(xué)、信息安全。

鄺青青（1988-），男，貴州安順人，貴州大學(xué)碩士生，主要研究方向?yàn)槊艽a學(xué)理論與工程。