本篇主要介紹區(qū)塊鏈中常用到的哈希算法。

1 哈希算法

1.1 定義及特性

??哈希算法是指通過哈希函數(shù)(Hash Function)對任意長度的輸入數(shù)據(jù)(比如文件、消息、數(shù)字等)進(jìn)行轉(zhuǎn)換，生成一個(gè)固定長度的哈希值(Hash Value)的過程。
??在區(qū)塊鏈中，哈希算法常用于區(qū)塊驗(yàn)證及安全性保證。為了保證安全，哈希算法必須滿足以下三個(gè)條件：

• 抗沖突(collision-resistance): 即不同的輸入不能產(chǎn)生相同的輸出。為了保證哈希算法的抗沖突性，一般會(huì)采用以下幾種方式：將輸入信息盡可能均勻地映射到輸入空間、引入隨機(jī)性、提升計(jì)算復(fù)雜度等。好的哈希算法設(shè)計(jì)能夠大大降低哈希碰撞的概率，提高數(shù)據(jù)的安全性和完整性。
• 信息隱藏性(information hiding): 即無法通過哈希函數(shù)的輸出反推其輸入。
• 可隱匿性(puzzle friendly): 即任何微小的輸入變化都會(huì)使得輸出哈希值的分布發(fā)生不可預(yù)測的改變，可以保證攻擊者無法通過改變輸入數(shù)據(jù)的一部分來預(yù)測輸出哈希值的變化情況。

1.2 常用哈希算法

??密碼學(xué)中常用的哈希算法有MD5、SHA1、SHA2、SHA256、SHA512\SHA3、RIPEMD160。這里僅以MD5和SHA1為例展示其Python代碼，如下：

import hashlib

message='今天是2023年7月13號，今年天氣很熱！'

#MD5
md5=hashlib.md5()
md5.update(message.encode('utf-8'))
md5_mess=md5.hexdigest()
print("MD5加密后的內(nèi)容為:{}".format(md5_mess))

#SHA1
sha1=hashlib.sha1()
sha1.update(message.encode('utf-8'))
sha1_mess=sha1.hexdigest()
print("SHA1加密后的內(nèi)容為:{}".format(sha1_mess))

其結(jié)果如下：

MD5加密后的內(nèi)容為:77815d973ce48613428d52956a1f6979
SHA1加密后的內(nèi)容為:572379a7baa62fd26e39bb4bbaf511497dbf838c

2 一致性哈希算法

??一致性哈希算法(Consistent Hashing,CH)是哈希算法的一種擴(kuò)展，主要是為了解決分布式系統(tǒng)中的數(shù)據(jù)分布和負(fù)載均衡問題。

2.1 算法原理

??一致性哈希算法的工作原理如下：

• 設(shè)置一個(gè)地址空間范圍為$0～(2^{32}?1)$的哈希環(huán)；
• 使用節(jié)點(diǎn)的特征值(一般使用節(jié)點(diǎn)ip地址)計(jì)算哈希值，并將該哈希值映射到哈希環(huán)上的某點(diǎn)；
• 對數(shù)據(jù)key使用相同的哈希函數(shù)計(jì)算出哈希值，同樣將其映射到哈希環(huán)上；
• 從數(shù)據(jù)映射的位置開始順時(shí)針查找，其所遇到的第一個(gè)存儲(chǔ)節(jié)點(diǎn)，即為這個(gè)key值所對應(yīng)的存儲(chǔ)節(jié)點(diǎn)地址。

??但當(dāng)哈希環(huán)結(jié)構(gòu)上的存儲(chǔ)節(jié)點(diǎn)較少時(shí)，存儲(chǔ)節(jié)點(diǎn)在哈希環(huán)上分配隨機(jī)性較高，導(dǎo)致存儲(chǔ)節(jié)點(diǎn)所承擔(dān)的負(fù)載并不均勻。為了避免這種現(xiàn)象的發(fā)生，引入虛節(jié)點(diǎn)。其思想是將哈希環(huán)的不同位置上放置一個(gè)節(jié)點(diǎn)的多個(gè)拷貝(即虛擬節(jié)點(diǎn)，使用真實(shí)節(jié)點(diǎn)對應(yīng)虛擬節(jié)點(diǎn)的特征來計(jì)算哈希值得到虛擬節(jié)點(diǎn)在哈希環(huán)上的位置)。加入虛擬節(jié)點(diǎn)后，key值的映射關(guān)系需要經(jīng)過兩步：

• 計(jì)算出key值和虛擬節(jié)點(diǎn)的映射關(guān)系；
• 根據(jù)虛擬節(jié)點(diǎn)和存儲(chǔ)節(jié)點(diǎn)的映射關(guān)系找到key值對應(yīng)的真實(shí)存儲(chǔ)節(jié)點(diǎn)；

2.2 案例

??使用python代碼模擬使用一致性哈希算法解決分布式數(shù)據(jù)分布的問題。案例代碼如下：

import hashlib

class ConsistentHashing:
    def __init__(self, nodes=None, replica_count=10):
        self.replica_count = replica_count #虛擬節(jié)點(diǎn)的數(shù)量
        self.ring = {} #記錄哈希環(huán)地址及其對應(yīng)的真實(shí)節(jié)點(diǎn)
        self.sorted_keys = []
        if nodes:
            for node in nodes:
                self.add_node(node)
                
    #新節(jié)點(diǎn)加入
    def add_node(self, node):
        for i in range(self.replica_count):
            key = self.get_key(node, i)
            self.ring[key] = node
            self.sorted_keys.append(key)
 
        self.sorted_keys.sort()
        
    #節(jié)點(diǎn)退出
    def remove_node(self, node):
        for i in range(self.replica_count):
            key = self.get_key(node, i)
            del self.ring[key]
            self.sorted_keys.remove(key)
            
    #獲取數(shù)據(jù)內(nèi)容的保存地址
    def get_node(self, data_key):
        if not self.ring:
            return None

        hashed_key = self.hash_key(data_key)
        for key in self.sorted_keys:
            if hashed_key <= key:
                return self.ring[key]

        return self.ring[self.sorted_keys[0]]
    
    #根據(jù)真實(shí)節(jié)點(diǎn)構(gòu)造虛擬節(jié)點(diǎn)的特征值，并用此特征值計(jì)算虛擬節(jié)點(diǎn)在哈希環(huán)上的地址
    def get_key(self, node, replica_index):
        return self.hash_key(f"{node}#{replica_index}")

    #這里使用的哈希函數(shù)為SHA1
    def hash_key(self, key):
        hashed_key = hashlib.sha1(key.encode()).digest()
        return int.from_bytes(hashed_key, byteorder='big')


nodes = ['node1', 'node2', 'node3', 'node4']
CH = ConsistentHashing(nodes=nodes, replica_count=5)

data_keys = ['data1', 'data2', 'data3', 'data4']
for key in data_keys:
    node = CH.get_node(key)
    print(f"'{key}' belongs to '{node}'")

其中一種可能的運(yùn)行結(jié)果如下：

‘data1’ belongs to ‘node1’
‘data2’ belongs to ‘node3’
‘data3’ belongs to ‘node1’
‘data4’ belongs to ‘node2’文章來源地址http://www.zghlxwxcb.cn/news/detail-580967.html

參考資料

1. 《一致性哈希算法的對比研究》
2. 《白話區(qū)塊鏈》

到了這里，關(guān)于區(qū)塊鏈：哈希算法與一致性哈希算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！