糾刪碼分片驗(yàn)證技術(shù)研究

摘要:糾刪碼分片驗(yàn)證技術(shù)在拜占庭環(huán)境中非常重要。分析了現(xiàn)有的糾刪碼分片驗(yàn)證技術(shù)。基于同態(tài)指紋技術(shù)提出了一種新的驗(yàn)證方法。分析結(jié)果表明，新的方法具有更好的效率。

關(guān)鍵詞:糾刪碼;同態(tài)指紋;指紋交叉校驗(yàn)和;延遲驗(yàn)證;拜占庭故障

Research of the Verification Technology for Erasure-Coded Data

WANG Bao-lin1，2， YANG Ming1， ZHANG Yong-hui1

(1.Institute of Command Automation， PLA Univ. of Sci. Tech.， Nanjing 210007， China; 2. The Unit 91004 of PLA， Dalian 116031， China)

Abstract: Verifing the erasure-coded data is important in Byzantine environment. This paper first analyses the existing verification technologies for erasure-coded data. Then it proposes a new approach based on the homomorphic fingerprint and lazy verification. Analysis result shows that the new approach is more efficiency than the existing approaches.

Key words: erasure code; homomorphic fingerprint; fingerprinted cross-checksum; lazy verification; byzantine fault

在信息化技術(shù)飛速發(fā)展的今天，計算機(jī)及網(wǎng)絡(luò)技術(shù)得到迅速發(fā)展，現(xiàn)代企業(yè)和個人的數(shù)據(jù)信息量正在呈爆炸式的增長，數(shù)據(jù)作為在計算機(jī)系統(tǒng)內(nèi)存在的形式越來越成為企業(yè)和個人最重要的財富。與此同時，人們也更加關(guān)注數(shù)據(jù)的可用性和可靠性。傳統(tǒng)的增強(qiáng)可用性和可靠性的方式主要是完全復(fù)制技術(shù)。采用完全復(fù)制技術(shù)時，需要將數(shù)據(jù)做多個拷貝，然后將多個拷貝分發(fā)到多個不同的位置，這樣能夠提供很好的可用性和可靠性。但是，完全復(fù)制技術(shù)也有一個缺點(diǎn):存儲多個副本的空間開銷太大。假定數(shù)據(jù)的大小用L表示，如果將數(shù)據(jù)采用k倍復(fù)制的話，那么總的存儲開銷將是k*L。為了降低存儲的空間開銷并增強(qiáng)系統(tǒng)的可用性，人們開始將糾刪碼技術(shù)應(yīng)用于存儲領(lǐng)域。以(m，n)糾刪碼技術(shù)為例，將需要存儲的數(shù)據(jù)分成m個分片，然后通過編碼生成n個分片，將這n個分片分發(fā)到多個不同的位置。在需要對數(shù)據(jù)進(jìn)行恢復(fù)時，只需要任意m個分片，就可以恢復(fù)出原來的數(shù)據(jù)。使用(m，n)糾刪碼技術(shù)的存儲開銷是n*(L/m)。但是，純粹的糾刪碼技術(shù)有一個假定:參與存儲的客戶端和服務(wù)器都是可信的。在客戶端和服務(wù)器不可信的環(huán)境(如可能出現(xiàn)拜占庭故障)中，惡意的客戶端可能向服務(wù)器寫入“有毒”的(即數(shù)據(jù)分片不是對應(yīng)于同一個原始數(shù)據(jù))數(shù)據(jù)或不完整的數(shù)據(jù);惡意的服務(wù)器可能篡改或刪除存儲其上的數(shù)據(jù)分片。……