分布式数据库技术-哈希数据的应用与原理

2023-10-28 理论教育版权反馈

【摘要】：确定性意味着哈希函数为相同的输入数据产生相同的哈希值。图19.8独立哈希图19.9重复哈希3）组合哈希组合哈希是在一次变换中让多个数据片变成一个哈希值。图19.10组合数据后计算哈希值图19.11顺序计算哈希值图19.12分层计算哈希值3.哈希指针哈希指针是指向数据块的哈希加密指针。图19.13交易一个块的哈希指针使用哈希指针的目的是构建区块链以防篡改机制，其实现过程如图19.13所示。图19.14哈希指针连接区块链中的数据块

区块链中使用的关键技术是哈希技术，本节讨论哈希数据。

1.哈希概述

哈希也称散列，就是将任意长度的输入（又叫前像，pre-image）通过散列算法转换成固定长度的输出，该输出就是哈希（散列）值。这种转换是一种压缩映射，也就是散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单来说，哈希就是一个将任意长度的消息压缩到某一固定长度的消息摘要的函数。

可以将加密哈希值看成是一种数字指纹。在分布式P2P系统里，需要处理大量交易数据，我们需要迅速识别它们的唯一性并与它们进行比较，这时就需要通过数字指纹实现。

哈希函数是很小的计算机程序，可将任意数据转换为定长的整数。任意给定时刻，哈希函数只接受一部分数据作为输入，经过哈希函数的转换，转换成一个哈希值。哈希函数很多，其中一类称为密码哈希函数（cryptographic hash functions），该函数可为任意数据创建数字指纹。密码哈希函数具有如下性质。

●快速为任何一种数据创建哈希值。实际上，这个性质是两个性质的组合：首先，哈希函数要能够为各种数据计算出哈希值，这是能力要求；其次，哈希函数要能够快速计算，这是速度要求。

●确定性（deterministic）。确定性意味着哈希函数为相同的输入数据产生相同的哈希值。

●伪随机性（pseudorandom）。伪随机性意味着输入数据变化时，哈希函数返回的哈希值是不可预见的。即使基本输入数据的变化只是一个比特，返回的哈希值也无法预测。

●单向性。单向性是指无法通过输出逆向追溯其输入值。不可能通过逆向转换，基于哈希值恢复输入值。

●抗冲突性（collision resistant）。哈希函数是抗冲突的，如果很难找到两个或多个数据片段，那么通过哈希后产生相同的哈希值。换言之，不同的数据片生成相同的哈希值的机会很小，这种哈希函数是抗冲突的。

2.数据哈希模式

数据哈希模式可以分为独立哈希（independent hashing）、重复哈希（repeated hashing）、组合哈希（combined hashing）、顺序哈希（sequential hashing）和层次哈希（hierarchical hashing）等几种。

1）独立哈希

独立哈希是指对每个数据片分别独立实施哈希运算，如对字符串“Hello World！”，可以对“Hello”和“World！”做独立哈希，如图19.8所示。

2）重复哈希

重复哈希是指重复使用哈希函数，如对“Hello World！”先做一次哈希得到哈希值7F83B65，接着再做一次哈希得到哈希值45A47BE7，如图19.9所示。

pagenumber_ebook=425,pagenumber_book=410

图19.8　独立哈希

pagenumber_ebook=425,pagenumber_book=410

图19.9　重复哈希

3）组合哈希(www.chuimin.cn)

组合哈希是在一次变换中让多个数据片变成一个哈希值。将数据组合起来需要耗费计算能力、时间和内存空间，只有独立数据片不是很多时才适合采用这种模式。组合哈希的缺点是，结果生成的是数据组合的一个哈希值，而无法生成独立数据片的哈希值，如图19.10所示。

4）顺序哈希

顺序哈希是一种随着新数据的到达逐步对哈希值更新的一种方式。首先对第一个输入的数据片实施哈希，获得哈希值，然后将该哈希值和新输入的数据片组合后重复实施哈希，获得新的哈希值。逐次递增，直至输入结束，如图19.11所示。

5）层次哈希

如图19.12所示，对独立数据片实施哈希，获得多个哈希值，然后再将它们组合后生成一个哈希值。