摘要：針對如何對并行分布式計算中的欺騙行為進行檢測和防止的問題，本文在Ringers方案上提出了改進方案——單向偽ringers方案；另外，文章還討論了目前亟待解決的串行分布式計算的反欺騙問題，提出了串行計算反欺騙方案。
關鍵詞：分布式計算 欺騙 ringers方案 并行 串行
中圖分類號：TP338.8
Uncheatable Scheme of Distributed Computing
HU Miao
(School of Electronic and Information Engineering, Beijing Jiaotong University, Beijing 100044 China)
Abstract： For how to detect and prevent the cheating act in distributed computing，a improving scheme was brought out based on ringers scheme——improved ringers scheme. Moreover, this article discussed the cheating problem of serial distributed computing and put forward a uncheatable scheme for it.
Key words： distributed computing cheating ringers scheme parallel serial
1 引 言
隨著個人電腦的普及以及性能的提高，互聯網的日益成熟和壯大，分布式計算的潛力在大型計算中得到越來越重要的發揮。在分布式計算中，眾多的計算機包括個人電腦、超級計算機等被連接在一起形成一個虛擬的計算機網絡，許多計算量龐大的工程可以通過這個虛擬計算機網絡得到有效的解決。
但是分布式計算同時也帶來了很多問題。在一個可信度較弱的環境下，如何確保參與分布式計算的參與者返回的結果是正確的呢？參與者可能在未完成工作的情況下欺騙主服務器并聲稱自己完成了工作，這種欺騙行為如果檢測不到，則其所提交的計算結果就沒有價值。SETI@home的項目管理者稱他們已經發現有些用戶試圖去偽造他們空閑CPU總共貢獻的時間以獲得在排名榜上排名靠前的效果[1]。盡管參加SETI@home項目的用戶是自愿的，他們沒有從分布式計算中得到報酬，但如果用戶能從中得到報酬，則他們就有更大的激勵去欺騙以獲得更大的利益。在一般的項目中欺騙的目的可能是為了提高在參與者之中貢獻度的排名，而商業項目的參與者進行欺騙的目的就可能是為了用更少的代價獲得更多的報酬。
為此，我們在基本ringers方案的基礎上提出了改進的單向偽ringers方案，并對串行分布式計算的欺騙問題提出了相應的解決方案。
2 單向偽ringers方案
2.1 問題定義
一個典型的分布式計算環境中需要一個主服務器以及一組能夠提供他們處理器空閑周期用來做相應計算的參與者。參與者之間是毫無關系的，他們只需要在完成各自任務之后將結果返回給主服務器。
首先，將一個并行分布式計算定義為以下元素組成的模型：
(1)函數 
定義在一個有限的定義域
中。計算目標就是計算出所有定義域中的對應的函數
。為了將計算分發出去，主服務器將分為若干子集，這樣在每個子域
上的函數的計算被指派到相應的參與者
去完成。
(2)篩選器
。篩選器是一個程序，就是將一對
，
作為輸入，輸出一個字串
。篩選器就是通過這個字串
來篩選有價值的運算結果并返回給主服務器。這里的前提是假設的運行開銷相對于計算開銷來說是可以忽略不計的。
2.2 可信性定義
下面來定義一個并行分布式計算是不可欺騙的。設一個參與者被分配給一個任務，計算所有
的函數
。如果參與者計算了上的所有，則認為參與者是可信的；反之，如果參與者僅計算了
上的，則認為參與者是不可信的。
設
是具有誠實度
的參與者進行作弊而不被主服務器發現的概率。設
是欺騙成功所預計需要的開銷，
是任務完成總共需要的計算開銷。一個并行分布式計算是不可欺騙的，只要下面兩個條件任一為真或者兩者都為真：
，對于給定的
或者
，由于計算開銷是很難衡量的，所以本文著重以如何降低欺騙可能性作為出發點來進行模型建立的。
2.3 方案模型建立
在Golle and Mironov提出的ringers方案中，管理者把一些先前計算過的秘密輸入和相應的輸入融合在一起，用戶必須找出這些先前計算過的輸入，Golle and Mironov證實了如果選擇合適數目的先前計算過的秘密輸入插入到需要計算的任務中，則用戶能欺騙成功的機會是很小的。ringers方案需要保證從需要計算的結果中找出先前計算過的秘密輸入比試用所有輸入的窮舉法并不簡單。因此，函數 必須具有單向屬性，即從中反向計算出
是很困難的或是不可能的，因此，ringers方案只適合于只有單向屬性的情況；另外，基本ringers方案存在的另外一個主要缺陷的是參與者能夠明確知道最后一個環(ringer)何時被找到。
為了改善ringers方案中明顯存在的兩個缺陷，提出單向偽ringers方案。
設
是一個單向函數。主服務器在產生環的時候，并不把這些環對應的函數值發送給參與者進行驗證，而是對再進行一次
運算，然后將得到的
作為要驗證的內容發送給參與者。這樣就將一個一般計算問題的驗證變為一個具有單向計算函數的計算問題的驗證。詳細步驟如下：
步驟1：主服務器為參與者 隨機選擇一個整數
，范圍在
中。主服務器隨后在內獨立隨機選擇個數為的真環，在
內選擇個數為
的偽環。然后主服務器計算所有
個環的對應的映射
。變換后的值被隨機打亂后分發到參與者中，這樣就無法區分真環與偽環。
步驟2：參與者用篩選對結果進行篩選。參與者在計算出
的同時還要再計算出
，用作對環的搜索。每個篩選器定義為，先看是否屬于主服務器感興趣的計算結果，若是，返回這個結果, ，否則輸出空串；再對于輸入
，看是否屬于集合
，如果屬于則輸出字串，否則，輸出為空。所有輸出字串組成集合。
步驟3：密鑰就是真環的集合 。主服務器檢查參與者返回的是否包含內的所有真環。如果是這樣，主服務器可以相信參與者是誠實的，否則認為參與者有作弊行為。
2.4 方案評價
該方案將ringers方案擴展到更為一般的計算中去，適用范圍更為廣闊，而且有與偽ringers方案一致的誠實度。但可以看出，因為參與者需要對每一個輸入除了計算，之外還要計算 ，這樣就增加了計算量。通過適當選擇函數，例如為一個單向哈希函數，像MD5或者SHA，它們的計算速度都是非�？斓�，可以使得的計算開銷遠小于。這樣使得帶來的額外計算開銷可以接受，使得該方案可行。
該方案擴展了ringers方案以適合于更大范圍的情況，通過優化提供了一種有效的方法來選擇先前計算過的結果，但是這個方法是否能適合于一般的分布式計算還有待證實。
3 串行計算反欺騙方案
3.1 問題定義
上面提到的方案僅僅是用于并行的分布式計算的，這些方案都是針對輸入的域非常大的情況下進行工作的，如果輸入值非常少，比如分配給每個參與者的任務只有一個輸入值，則執行的效率非常低，這就涉及到接下來要討論的串行分布式計算的反欺騙檢測問題。
首先，將一個串行分布式計算定義為以下元素組成的模型：
定義域 
，假定網絡中存在
個串行分布式計算的參與者，第名參與者的任務是迭代計算
，其中
，最終得出
送回到服務器主機。
假設網絡中可能存在欺騙行為，這種欺騙行為可以是沒有經過任何計算而產生任意一隨機數來冒充，也可以是僅僅經過部分的計算而放棄后面計算而生成的隨機數發回主服務器。
下面定義一個串行分布式是可信的。設一個參與者被分配給一個任務，計算
的
次迭代，最終得出。如果參與者計算了輸入的所有的次迭代并得出，則認為參與者是可信的；反之，如果參與者僅計算了部分次的迭代或根本沒有經過計算，則認為參與者是不可信的。
設 是具有誠實度的參與者進行作弊而不被主服務器發現的概率。與并行分布式的定義相同，要使串行分布式計算是不可欺騙的，只需。
3.2 方案模型建立
對于串行分布式計算，由于輸入值很少，目前的解決方案只是簡單地用重復檢測的方法將每個計算任務分配給兩個以上的參與者去完成然后比較計算結果。當然，如果雙方的結果顯示不同的話，我們依然無法判斷哪一方的運算結果是正確的，因此這樣需要至少三次的重復計算才能夠得到令人放心的目標運算結果。
另外，在實際的運算中，
值的大小通常很大，假設
域中所有的數據均為40位二進制數大小，
，則總共需要的存儲空間范圍是
，因此想要存儲運算過程中的所有數據是非常浪費資源的。
考慮到計算的代價大與系統存儲資源有限等主要限制因素，本文探索性的提出串行計算的反欺騙方案。
步驟1：主服務器選取
為兩個相鄰需要保存的運算結果的距離，則整個運算過程中的需要保存的數據應該有
個，分別為
。第個參與者需要將這些數據（也稱生成數據）以及保持運算順序發送給篩選器進行篩選。
步驟2：由主服務器事先確定篩選器所需要檢測的數據點集合
（只須設定
即可），進行該部分的
步串行迭代計算，將得到的結果與
進行比較，若所有的驗證結果與中的值均相同，則認為該參與者可信，篩選器輸出的信息為主服務器所為不同的參與者所生成的特定隨機數
經加密后所生成的密文
；反之，若篩選器所檢測的某一區段的迭代運算結果與參與者所生成結果不符，則認為參與者不可信，假定出現錯誤的迭代區段是所檢測的第個區段
，則篩選器輸出的信息為數據經加密后所生成的密文，并且不再進行之后的區段數據檢測，以保證參與者無法獲取主服務器所設定的檢查區段位置。參與者發送回主服務器的數據為集合
。
步驟3：解密密鑰由主服務器保存。主服務器檢查參與者返回的 經過解密是否包含。如果包含，主服務器可以相信參與者是誠實的，承認結果；否則認為參與者有作弊行為，不承認結果。
3.3 方案評價
本方案的核心內容在于篩選器的選擇上，若希望不進行大數據量的信息傳輸而又能夠保證信息的可靠性，按照之前的想法，需要參與者在返回主服務器所需要的數據的同時發送一個能夠證明其可靠性的數據或者是數據環，而由主服務器發送給單一參與者的信息數量有很有限，比如說在我們前面所提到的例子中此種信息的數量只有一個，本文巧妙地利用了主服務器所發送的某一個隨機數的某種變換作為篩選器的輸出解決了檢測環的生成問題，方案中的變換可以是任意一種加密算法，如前面所提到的MD5或SHA加密算法。利用該篩選器，可以使得，即達到不可欺騙環境所需要的條件。
方案的優點在于模型在一定程度上考慮到了計算的代價大與系統存儲資源有限等因素影響。首先，本串行計算的反欺騙模型有效節約了計算耗費，直接指定兩個不同的參與者進行相同的數據計算是十分耗費資源的，方案雖然也對部分數據進行了重復性的計算，但也已經很有效的節約了網絡資源，畢竟篩選器的工作是在同一參與者的終端上進行的；再者，參與者所要保留的數據量也減少到了 
個，存儲問題得到了有效的解決；此外，由于篩選器的定義，參與者不必將生成的任何中間數據傳送回主服務器，也在一定程度上減輕了網絡傳輸的負荷。
但是本方案所設定的篩選器的復雜度較高，在選定檢測數據較少的情況下它的計算量是可以忍受的，但此時可能會造成欺騙可能性的增加，因此在應用此模型時需要考慮均衡兩者的關系，從而使模型效益最大化。
參考文獻
[1] Kahney L. Cheaters Bow to Peer Pressure [EB／OL](2002-01-l5)．
http://www.Wired.Corn/science/discoveries/news/2001/02/41838
[2] 黃仲偉, 陳莘萌. 網格計算中的反欺騙方案[J]. 計算機工程與設計. 2005. 26 (10):2808-
2809.
Huang Zhongwei, Chen Zimeng. Uncheatable scheme of grid computing. Computer Engineering and Design. 2005. 26 (10):2808-2809.
[3] Philippe Golle and Ila Mironov. Uncheatable Distributed Computations. Stanford University.
[4] Bogdan Carbunar and Radu Sion. Uncheatable Reputation for Distributed Computation Markets. Computer Science.
作者簡介：胡淼（1988-）男，山東諸城人，2007年至今就讀于北京交通大學電子信息工程學院通信工程專業，曾獲2010美國數學建模競賽一等獎。
10347
