比特币和加密货币技术 第 1 章：密码学和加密货币简介

Jul 19, 2023

比特币和加密货币技术 第 1 章：密码学和加密货币简介

所有货币都需要某种方式来控制供应，并执行各种安全特性以防止作弊。在法定货币中，中央银行等组织控制货币供应，并为实物货币添加防伪功能。这些安全特性提高了攻击者的门槛，但并不能使货币无法伪造。最终，执法对于阻止人们破坏系统规则是必要的。

加密货币也必须有安全措施，防止人们篡改系统状态，防止人们含糊其辞，即对不同的人做出相互矛盾的陈述。例如，如果爱丽丝让鲍勃相信她向他支付了一枚数字硬币，那么她就不应该让卡罗尔相信她向他支付了同样的硬币。但与法定货币不同的是，加密货币的安全规则需要纯粹通过技术手段来执行，而无需依赖中央机构。

顾名思义，加密货币大量使用加密技术。加密技术提供了一种将加密货币系统的规则安全地编码到系统本身的机制。我们可以用它来防止篡改和等价交换，以及将创建新货币单位的规则编码成数学协议。因此，在正确理解加密货币之前，我们需要深入研究其所依赖的加密基础。

密码学是一个深奥的学术研究领域，它运用了许多先进的数学技术，而这些技术又是出了名的微妙和复杂难懂。幸运的是，比特币只依赖于少数相对简单和众所周知的加密结构。在本章中，我们将专门研究加密哈希值和数字签名，这两种原语对构建加密货币非常有用。以后的章节将介绍更复杂的加密方案，如零知识证明，这些方案将用于比特币的扩展和修改。

在学习了必要的加密原语后，我们将讨论如何使用这些原语来构建加密货币。本章最后，我们将以一些简单的加密货币为例，说明我们需要应对的一些设计挑战。

1.1 密码哈希函数

我们需要了解的第一个加密原语是加密散列函数。散列函数是一种数学函数，具有以下三个特性：

• 它的输入可以是任何大小的字符串。
• 它的输出大小固定。为了使本章的讨论具体化，我们将假设输出大小为 256 位。不过，只要输出大小足够大，我们的讨论都是正确的。
• 可高效计算。直观地说，这意味着对于给定的输入字符串，你可以在合理的时间内计算出散列函数的输出结果。更严格地说，计算 n 位字符串的哈希值的运行时间应为 O(n)。

这些属性定义了一种通用哈希函数，可以用来构建哈希表等数据结构。我们将专门讨论加密哈希函数。为了保证哈希函数在密码学上的安全性，我们将要求它具备以下三个附加属性：（1）抗碰撞性；（2）隐藏性；（3）谜题友好。

我们将更仔细地研究这些特性中的每一个，以了解为什么有这样一个函数是有用的。学过密码学的读者应该知道，本书对哈希函数的处理与标准密码学教科书有些不同。特别是 “谜题友好 “属性，它并不是对加密哈希函数的一般要求，而是对加密货币特别有用的属性。

属性 1：抗碰撞性。我们需要加密哈希函数具备的第一个属性就是抗碰撞性。当两个不同的输入产生相同的输出时，就会发生碰撞。如果无法发现碰撞，那么就可以说一个哈希函数​H(.)是抗碰撞性的。正式地：

抗碰撞性：如果不可能找到两个值 x 和 y，使得 x≠y 但 H(x)=H(y) ，那么就可以说哈希函数具有抗碰撞性。

请注意，我们说没有人能找到碰撞，但并没有说不存在碰撞。事实上，我们知道碰撞确实存在，我们可以通过一个简单的计数论证来证明这一点。哈希函数的输入空间包含所有长度的字符串，而输出空间只包含特定固定长度的字符串。由于输入空间大于输出空间（事实上，输入空间是无限的，而输出空间是有限的），因此一定存在映射到相同输出字符串的输入字符串。事实上，根据鸽洞原理，必然会有非常多的可能输入映射到任何特定的输出。

现在，更糟糕的是，我们说过不可能找到碰撞。然而，有些方法却能保证找到碰撞。请看下面这个寻找一个拥有256比特输出的哈希函数的碰撞的简单方法：选取 2²⁵⁶ + 1 个不同的值，计算每个值的哈希值，然后检查是否有两个输出值相等。由于我们选取的输入值比可能的输出值多，因此在应用哈希函数时，其中一定有一对会发生碰撞。

上述方法可以保证找到碰撞。但如果我们随机选取输入并计算哈希值，那么早在检查 2²⁵⁶ + 1 输入之前，我们就会以很高的概率发现碰撞。事实上，如果随机选择 2¹³⁰ + 1 个输入，那么至少有两个输入会发生碰撞的概率高达 99.8%。我们只需检查可能输出数的大约平方根，就能发现碰撞，这一事实源于概率论中的一个现象，即生日悖论。在本章结尾的作业题中，我们将更详细地探讨这一问题。

这种碰撞检测算法适用于所有哈希函数。当然，它的问题在于需要非常非常长的时间才能完成。对于一个 256 位输出的哈希函数，在最坏的情况下，你必须计算哈希函数 2²⁵⁶ + 1 次，平均大约 2¹²⁸ 次。这毫无疑问将是一个天文数字，如果一台计算机每秒计算 10,000 次哈希值，那么计算 2¹²⁸个哈希值需要的时间将超过 10 亿年（10²⁷）！换个角度思考，我们可以说，如果人类制造的每一台计算机从整个宇宙诞生之初就开始计算，直到现在，它们发现碰撞的几率仍然微乎其微。概率小到远远低于地球在接下来的两秒钟内被一颗巨大流星摧毁的几率。

因此，我们看到了一种通用但不切实际的算法，可以找到任何散列函数的碰撞。一个更难的问题是：是否有其他方法可以用于特定的哈希函数，从而找到碰撞？换句话说，虽然通用碰撞检测算法不可行，但仍可能有其他算法可以有效地找到特定哈希函数的碰撞。

例如，请看下面的哈希函数：

H(x) = x mod 2²⁵⁶

这个函数符合我们对散列函数的要求，因为它可以接受任意长度的输入，返回固定大小的输出（256 位），并且可以高效计算。不过，这个函数也有一种高效的方法来查找碰撞。请注意，该函数只返回输入的最后 256 位。那么碰撞值就是 3 和 3 + 2²⁵⁶。这个简单的例子说明，尽管我们的通用碰撞检测方法在实践中无法使用，但至少有一些哈希函数确实存在高效的碰撞检测方法。

然而，对于其他哈希函数，我们不知道是否存在这样的方法。我们怀疑它们具有抗碰撞性。然而，没有任何哈希函数被证明是抗碰撞的。我们在实践中所依赖的加密哈希函数，只是人们非常非常努力地寻找碰撞但尚未成功的函数。在某些情况下，比如老式的 MD5 哈希函数，经过多年的努力，碰撞最终被发现，导致该函数被淘汰，不再实际使用。因此，我们选择相信这些函数是抗碰撞的。

应用： 既然我们知道了什么是抗碰撞，那么合乎逻辑的问题就是：抗碰撞有什么用？这里有一个应用： 如果我们知道抗碰撞哈希函数的两个输入 x 和 y 是不同的，那么可以安全地假设它们的哈希值 H(x) 和
如果我们知道 x 和 y 的哈希值是不同的，那么我们就可以认为它们的哈希值 H(x) 和 H (y ) 是安全的–如果我们知道 x 和 y 的哈希值是安全的，那么就违反了我们关于它具有抗碰撞性的假设。

应用： Mes­sage digests 既然我们知道了什么是抗碰撞，那么合乎逻辑的问题就是：抗碰撞有什么用？这里有一个应用： 如果我们知道抗碰撞哈希函数的两个输入 x 和 y 是不同的，那么可以安全地假设它们的哈希值 H(x) 和 H (y )是不同的–如果已知x和y是不同的但有相同的哈希值，那么这将会与我们之前关于哈希函数H是抗碰撞的假设相矛盾。

考虑一下 SecureBox，这是一个经过验证的在线文件存储系统，允许用户上传文件，并在下载时确保文件的完整性。假设爱丽丝上传了一个非常大的文件，并希望能在稍后验证她下载的文件与上传的文件是否相同。一种方法是将整个大文件保存在本地，然后直接与她下载的文件进行比较。虽然这种方法可行，但它在很大程度上违背了上传文件的初衷；如果爱丽丝需要访问文件的本地副本以确保其完整性，她可以直接使用本地副本。

这个说法允许我们使用哈希输出作为Mes­sage digests。考虑 SecureBox，这是一个经过身份验证的在线文件存储系统，允许用户上传文件并在下载文件时确保其完整性。 假设 Alice 上传了非常大的文件，并且希望稍后能够验证她下载的文件与她上传的文件是否相同。 一种方法是将整个大文件保存在本地，然后直接将其与她下载的文件进行比较。 虽然这有效，但它在很大程度上违背了上传它的初衷； 如果Alice需要访问文件的本地副本以确保其完整性，她可以直接使用本地副本。

无碰撞哈希为这个问题提供了一个优雅而有效的解决方案。 Alice 只需记住原始文件的哈希值即可。 当她稍后从 Secure­Box 下载文件时，她计算下载文件的哈希值并将其与她存储的哈希值进行比较。 如果哈希值相同，则她可以断定该文件确实是她上传的文件，但如果它们不同，则 Alice 可以断定该文件已被篡改。 因此，记住哈希值可以让她检测到文件在传输过程中或 Secure­Box 服务器上的意外损坏，以及服务器对文件的有意修改。 面对其他实体的潜在恶意行为时的这种保证是密码学为我们提供的核心保证。

哈希充当消息的固定长度摘要或明确的总结。 这为我们提供了一种非常有效的方式来记住我们以前见过的事物并再次识别它们。 尽管整个文件可能有 GB 那么长，但哈希值具有固定长度，在我们的示例中哈希函数为 256 位。 这大大减少了我们的存储需求。 在本章后面和整本书中，我们将看到使用哈希作为消息摘要的有用应用程序。

属性 2：隐藏性 我们想要从哈希函数中获得的第二个属性是隐藏性。隐藏属性断言，如果我们给出哈希函数的输出 y​=​H​(x)，​则没有可行的方法来弄清楚输入 x​是什么。 问题是这个属性在规定的形式中不可能是真的。 考虑以下简单的例子：我们要做一个抛硬币的实验。 如果抛硬币的结果是正面，我们将宣布字符串“heads”的哈希值。 如果结果是背面，我们将公布字符串“tails”的哈希值。

然后，我们询问某人，即对手，他没有看到硬币翻转，但只看到了这个哈希输出，以找出经过哈希处理的字符串是什么（我们很快就会明白为什么我们可能想玩这样的游戏）。 作为回应，他们只需计算字符串“heads”的哈希值和字符串“tails”的哈希值，然后他们就可以看到他们得到的是哪一个。 因此，只需几个步骤，他们就可以弄清楚输入是什么。

攻击者能够猜测字符串是什么，因为 x 只有两个可能的值，并且攻击者很容易尝试这两个值。 为了能够实现隐藏属性，需要出现 x​不存在值的情况，这种情况特别有可能。 也就是说，x​必须从某种意义上非常分散的集合中选择。 如果 x​是从这样的集合中选择的，那么尝试一些特别可能的 x 值的方法将不起作用。

最大的问题是：当我们想要的值不是来自“heads”和“tails”实验中的展开集时，我们能否实现隐藏属性？ 幸运的是，答案是肯定的！ 所以通过将其与已传播的其他输入连接起来，我们甚至可以隐藏未传播的输入。 现在我们可以更精确地理解隐藏的含义（双竖线 ‖ 表示串联）。

隐藏性。​哈希函数 H 是隐藏性的，如果：当从具有高最小熵的概率分布中选择秘密值 r​时，则给定 H​(r ‖ x)​不可能找到 x​。​

在信息论中，最小熵m​in-entropy​是对结果可预测程度的度量，高的 min-entropy 体现了分布（如，随机变量）非常分散的直观想法。这具体意味着，当我们从分布中采样时，可能不会出现特定的值。 因此，举一个具体的例子，如果从所有 256 位长的字符串中统一选择 r​，则以概率 1/2​选择任何特定字符串，这是一个无限小的值。

应用：承诺 Com­mit­ments。​现在让我们看一下隐藏属性的应用。 特别是，我们想做的是所谓的承诺。承诺是数字模拟，取一个值，将其密封在信封中，然后将信封放在每个人都可以看到的桌子上。 当你这样做时，你就已经承诺了信封内的内容。 但你还没有打开它，所以即使你承诺了一个价值观，这个价值观对其他人来说仍然是一个秘密。 稍后，您可以打开信封并显示您之前承诺的价值。

承诺方案。​承诺方案由两种算法组成：
● com := commit(m​sg, nonce)​ com­mit 函数采用消息和秘密随机值（称为随机数）作为输入并返回承诺。
● verify(com, msg, nonce)​ 验证函数将承诺、随机数和消息作为输入。 如果 com​ == commit(m​sg,​n​once)​则返回 true，否则返回 false。
我们要求满足以下两个安全属性：
● Hid­ing：​给定com，​不可能找到m​sg
● Bind­ing：​不可能找到两对 (​msg, nonce)​和 (​msg’, nonce’)​使得 m​sg ≠​
msg’​和提交（m​sg，nonce）​== commit（m​sg’，nonce’）​

要使用承诺方案，我们首先需要生成一个随机数。 然后，我们将 com­mit 函数与要提交的值 m​sg 一起应用于此随机数，并发布承诺 com。此阶段类似于将密封的信封放在桌子上。 稍后，如果我们想揭示他们之前承诺的值，我们会发布用于创建此承诺的随机数，以及消息​msg。现在，任何人都可以验证 m​sg 确实是之前承诺的消息。 这个阶段类似于打开信封。

每次您提交一个值时，选择一个新的值非常重要。​​在密码学中，术语“n​once​”用于指只能使用一次的值。

这两个安全属性决定了算法的行为实际上就像密封和打开信封一样。 首先，给定 com​承诺，查看信封的人无法弄清楚消息是什么。 第二个属性是它具有约束力。 这确保了当您承诺信封中的内容时，您以后无法改变主意。 也就是说，您可以先提交一条消息，然后又声称您提交了另一条消息，找到这样两条不同的消息是不可能的。

那么我们如何知道这两个属性成立呢？ 在回答这个问题之前，我们需要讨论如何实际实施承诺计划。 我们可以使用加密哈希函数来做到这一点。 考虑以下承诺方案：

com­mit(m​sg, nonce)​:= H(n​once ‖ msg)​，其中 n​once​是一个256位的随机值。

为了提交消息，我们生成一个随机 256 位随机数。 然后我们将随机数和消息连接起来，并返回该连接值的哈希值作为承诺。 为了进行验证，有人将计算与消息连接的随机数的相同哈希值。 他们将检查这是否等于他们看到的承诺。

再看看我们的承诺计划所要求的两个属性。 如果我们将­com­mit和ver­i­fy的实例化以及 H(nonce ‖ msg) 替换为com，那么这些属性变为：

● 隐藏：​给定 H(n​once ‖ msg)，​不可能找到 m​sg
● 绑定：​不可能找到两对 (​msg, nonce)​和 (​msg’, nonce’)​使得 m​sg ≠​msg’和 H(n​once ‖ msg)​== H(n​once’ ‖ msg’)​

承诺的隐藏性正是我们哈希函数所需的隐藏性功能 。 如果随机选择256位值作为key，则隐藏性说明如果哈希将密钥和消息连接起来，从哈希输出中找到消息是不可行的。 事实证明，绑定属性隐含在底层哈希函数的抗碰撞属性¹中。 如果哈希函数是抗碰撞的，那么将不可能找到不同的值 msg 和 msg’ 使得 H(n​once ‖ msg) = H​(n​once’ ‖ msg’)​，因为这些值确实会发生碰撞。

因此，如果 H​是一个抗碰撞和隐藏的哈希函数，则该承诺方案将起作用，因为它将具有必要的安全属性。

属性3：谜题友好性。 我们需要哈希函数的第三个安全特性是它们的谜题友好性。 这个属性有点复杂。 我们将首先解释该属性的技术要求是什么，然后给出一个应用来说明为什么该属性有用。

谜题友好性。对于每个可能的 n 位输出值 y​，如果 k 是从具有高最小熵的分布中选择的，那么在明显小于 2ⁿ​​的时间内，不可能找到 x​，使得H(k ‖ x) = y ，则哈希函数 H​被认为是易解谜性。

直观地说，这意味着，如果有人想要将哈希函数定位为某个特定的输出值 y​，​如果输入的一部分是以适当随机的方式选择的，则很难找到另一个完全符合该目标的值。

应用：搜索谜题。​现在，让我们考虑一个说明此属性有用性的应用。 在此应用中，我们将构建一个搜索谜题，这是一个需要搜索非常大的空间才能找到解决方案的数学问题。 特别是，搜索谜题没有捷径。 也就是说，除了搜索那么大的空间之外，没有办法找到有效的解决方案。

¹ 相反的推论不成立。 也就是说，您可能会发现碰撞，但它们都不是 H(n​once ‖ msg) == H​(n​once’ ‖ msg’) 形式。例如，如果您只能找到两个不同的随机数为同一消息生成相同承诺的碰撞，则承诺方案仍然具有约束力，但底层哈希函数不具有抗碰撞性。

搜索谜题。 搜索谜题包括
● 哈希函数，H​，​
● 一个值，i​d（我们称之为谜题 ID）​，从高最小熵分布中选择
● 和目标集 Y​
这个谜题的一个解决方案是一个值 x​，​使得 H ( id ​ ‖ x ) ​ ∈ Y ​ 。

直觉是这样的：如果 H 有一个 n 位输出，那么它可以采用 2 个值中的任何一个。 解决谜题需要找到一个输入，以便输出落在集合 Y 内，该集合通常比所有输出的集合小得多。 Y 的大小决定了拼图的难度。 如果 Y 是所有 n 位字符串的集合，则密题很简单，而如果 Y 只有 1 个元素，则谜题非常困难。 谜题 ID 具有高最小熵这一事实确保了没有捷径。 相反，如果 ID 的特定值是可能的，那么有人可能会作弊，比如通过使用该 ID 预先计算谜题的解决方案。

如果一个搜索谜题是谜题友好的，这意味着这个谜题没有解决策略，这比仅仅尝试 x 的随机值要好得多。因此，如果我们想要提出一个难以解决的谜题，只要我们能够以适当随机的方式生成谜题 ID，我们就可以这样做。 稍后当我们讨论比特币挖矿时，我们将使用这个想法，这是一种计算难题。

SHA-256。 我们已经讨论了哈希函数的三个属性，以及每个属性的一个应用。 现在让我们讨论一个特定的哈希函数，我们将在本书中大量使用它。 存在很多哈希函数，但这是比特币主要使用的哈希函数，而且它是一个非常好用的哈希函数。 它被称为 SHA‐256。​

回想一下，我们要求哈希函数适用于任意长度的输入。 幸运的是，只要我们能够构建一个适用于固定长度输入的哈希函数，就有一种通用方法可以将其转换为适用于任意长度输入的哈希函数。 它被称为 Merkle-Damgard 变换。SHA-256 是使用此方法的许多常用哈希函数之一。 用通用术语来说，底层的定长抗碰撞哈希函数称为压缩函数。​已经证明，如果底层压缩函数是抗碰撞的，那么整个哈希函数也是抗碰撞的。

Merkle-Damgard 变换非常简单。 假设压缩函数接受长度为 m​的输入，并输出较小的长度 n​。哈希函数的输入（可以是任意大小）被分为长度为 ​m‐n的块​。构造工作如下：将每个块与前一个块的输出一起传递到压缩函数中。 请注意，输入长度将为 (m​‐n)​ + n​ = ​​m，这是压缩函数的输入长度。 对于第一个块，没有预先的块输出，我们在每次调用哈希函数时都使用初始化向量（IV）。这个数字在每次调用哈希函数时都会使用，实际上你可以看一下它在标准文件中。 最后一个块的输出是您返回的结果。

SHA-256 使用压缩函数，该函数接受 768 位输入并生成 256 位输出。 块大小为 512 位。 请参见图 1.3 了解 SHA-256 工作原理的图形描述。

我们讨论了哈希函数、具有特殊属性的加密哈希函数、这些属性的应用以及我们在比特币中使用的特定哈希函数。 在下一节中，我们将讨论使用哈希函数构建在比特币等分布式系统中使用的更复杂的数据结构的方法。

边栏：哈希函数建模。哈希函数是密码学的瑞士军刀：它们在各种各样的应用程序中占有一席之地。 这种多功能性的另一面是，不同的应用需要稍微不同的哈希函数属性来确保安全性。 事实证明，要确定一个哈希函数属性列表来全面证明安全性是非常困难的。
在本文中，我们选择了对于比特币和其他加密货币中使用哈希函数的方式至关重要的三个属性。 即使在这个空间内，并非所有这些属性对于每次使用哈希函数都是必需的。 例如，正如我们将看到的，谜题友好性仅在比特币挖矿中才重要。
安全系统的设计者经常认输，并将哈希函数建模为每个可能的输入输出独立随机值的函数。 使用这种“随机预言模型”来证明安全性在密码学中仍然存在争议。 无论人们在这场辩论中的立场如何，推理如何将我们在应用中想要的安全属性减少到底层原语的基本属性对于构建安全系统来说是一项有价值的智力练习。 我们在本章中的演示旨在帮助您学习这项技能。

1.2 哈希指针和数据结构

在本节中，我们将讨论哈希指针及其应用。 哈希指针是一种数据结构，在我们将要讨论的许多系统中都非常有用。 哈希指针只是指向某些信息与信息的加密哈希一起存储的位置的指针。 常规指针为您提供了一种检索信息的方法，而哈希指针还为您提供了一种验证信息是否未更改的方法。

我们可以使用哈希指针来构建各种数据结构。 直观上，我们可以采用一种熟悉的使用指针（例如链表或二叉搜索树）的数据结构，并使用哈希指针来实现它，而不是像通常那样使用指针。

区块链。​在图1.5中，我们使用哈希指针构建了一个链表。 我们将这种数据结构称为块链。在具有一系列块的常规链表中，每个块都有数据以及指向列表中前一个块的指针，而在块链中，前一个块指针将被哈希指针替换。 因此，每个块不仅告诉我们前一个块的值在哪里，而且还包含该值的摘要，使我们能够验证该值是否未更改。 我们存储列表的头部，它只是一个指向最新数据块的常规哈希指针。

区块链的一个用例是防篡改日志。也就是说，我们想要构建一个存储一堆数据的日志数据结构，并允许我们将数据附加到日志的末尾。 但如果有人更改了日志中较早的数据，我们就会检测到它。

为了理解为什么区块链实现了这种防篡改的属性，让我们问一下如果对手想要篡改链中间的数据会发生什么。 具体来说，攻击者的目标是让只记住区块链头部哈希指针的人无法检测到篡改。 为了实现这一目标，对手改变了某些区块的数据。​由于数据已更改，因此区块 k​的哈希值 + 1（表示整个区块 k​的哈希值）将不会匹配。 请记住，我们在统计上保证新的哈希值不会与更改的内容匹配，因为哈希函数具有抗碰撞性。 因此，我们将检测块 k​中的新数据与块 k​ + 1 中的哈希指针之间的不一致。当然，对手也可以继续尝试通过更改下一个块的哈希来掩盖此更改。 对手可以继续这样做，但是当他到达列表的头部时，这个策略就会失败。 具体来说，只要我们将链表头部的哈希指针存储在对手无法更改的地方，对手就无法在不被发现的情况下更改任何块。

这样做的结果是，如果对手想要篡改整个链中任何位置的数据，为了保持故事的一致性，他将不得不一直篡改哈希指针，直到开始。 他最终会遇到障碍，因为他无法篡改列表的头部。 因此，通过记住这个单个哈希指针，我们基本上就记住了整个列表的防篡改哈希。 因此，我们可以构建一个像这样的区块链，其中包含我们想要的任意数量的块，回到列表开头的某个特殊块，我们将其称为创世块。

您可能已经注意到，区块链结构与我们在上一节中看到的 Merkle-Damgard 结构类似。 事实上，它们非常相似，并且相同的安全论点也适用于它们。

Merkle 树。我们可以使用哈希指针构建的另一个有用的数据结构是二叉树。 带有哈希指针的二叉树被称为 Merkle 树，以其发明者 Ralph Merkle 的名字命名。 假设我们有许多包含数据的块。 这些块构成了我们树的叶子。 我们将这些数据块分成两对，然后对于每一对，我们构建一个具有两个哈希指针的数据结构，每个数据块都有一个哈希指针。 这些数据结构构成了树的下一层。 我们依次将它们分为两组，并为每一对创建一个包含每个组的哈希值的新数据结构。 我们继续这样做，直到到达单个块，即树的根。

和以前一样，我们只记住树头的哈希指针。 我们现在可以通过哈希指针向下遍历到列表中的任何点。 这可以让我们确保数据没有被篡改，因为就像我们在区块链中看到的那样，如果对手篡改了树底部的某个数据块，就会导致上一层的哈希指针不匹配，即使他继续篡改这个块，变化最终也会传播到树的顶部，在那里他将无法篡改我们存储的哈希指针。 同样，只要记住顶部的哈希指针，就可以检测到任何篡改任何数据的尝试。

成员资格证明。Merkle 树的另一个很好的功能是，与我们之前构建的区块链不同，它允许简洁的成员资格证明。 假设有人想证明某个数据块是 Merkle Tree 的成员。 像往常一样，我们只记住词根。 然后他们需要向我们展示这个数据块，以及从数据块到根的路径上的块。 我们可以忽略树的其余部分，因为这条路径上的块足以让我们验证哈希一直到树的根。 请参见图 1.8 了解其工作原理的图形描述。

如果树中有 n 个节点，则只需要显示大约 l​og(n)​项。 由于每个步骤只需要计算子块的哈希值，因此我们需要大约 (n) 时间来验证它。 并且即使 Merkle 树包含非常大量的区块，我们仍然可以在相对较短的时间内证明成员资格。 因此，验证在时间和空间上运行，时间和空间与树中节点的数量成对数。

排序的 Merkle 树只是一棵 Merkle 树，我们在底部获取块，然后使用某种排序函数对它们进行排序。 这可以是字母顺序、字典顺序、数字顺序或其他商定的顺序。

非成员资格证明。​使用排序的 Merkle 树，可以在对数时间和空间中验证非成员资格。 也就是说，我们可以证明某个特定的区块不在 Merkle 树中。 我们这样做的方法很简单，就是显示相关项目所在位置之前的项目的路径，并显示该项目所在位置之后的项目的路径。 如果这两个项目在树中是连续的，则这可以作为不包括相关项目的证据。 因为如果包含它，则它需要位于显示的两个项目之间，但它们之间没有空格，因为它们是连续的。

我们已经讨论了在链表和二叉树中使用哈希指针，但更一般地说，事实证明我们可以在任何基于指针的数据结构中使用哈希指针，只要该数据结构没有循环。 如果数据结构中存在循环，那么我们将无法使所有哈希值都匹配。 如果您考虑一下，在非循环数据结构中，我们可以从叶子附近或没有任何指针的事物附近开始，计算它们的哈希值，然后返回到开头。 但在有循环的结构中，我们没有尽头可以开始并计算回来。

因此，考虑另一个例子，我们可以用哈希指针构建一个有向无环图。 我们将能够非常有效地验证该图中的成员资格。 而且很容易计算。 以这种方式使用哈希指针是一个通用技巧，您将在分布式数据结构的上下文中以及我们在本章后面和整本书中讨论的算法中一次又一次地看到它。

1.3 数字签名

在本节中，我们将研究数字签名。这是第二个加密原语以及哈希函数，我们需要它们作为稍后讨论加密货币的构建块。 数字签名应该是纸上手写签名的数字模拟。 我们希望数字签名具有与手写签名类比很好对应的两个属性。 首先，只有你可以签名，但任何看到它的人都可以验证它是否有效。 其次，我们希望签名与特定文档相关联，以便签名不能用于表明您同意或认可其他文档。 对于手写签名，后一个属性类似于确保某人无法获取您的签名并将其从一份文档上剪下来并将其粘贴到另一份文档的底部。

我们如何使用密码学以数字形式构建它？ 首先，让我们把之前直观的讨论变得更具体一些。 这将使我们能够更好地推理数字签名方案并讨论其安全属性。

数字签名方案。​数字签名方案由以下三种算法组成：
● (sk, pk) :=generateKeys(k​eysize)​ generateKeys方法采用密钥大小并生成密钥对。 秘密密钥 sk​被秘密保存并用于签署消息。 p​k​是您提供给每个人的公共验证密钥。 任何拥有此密钥的人都可以验证您的签名。
● sig := sign(s​k,​m​essage)​ sign方法采用消息和密钥s​k,​a​s 输入并输出 s​k 下 m​essage 的签名
● isValid := verify(p​k,​m​essage,​s​ig)​ 验证方法将消息、签名和公钥作为输入。 它返回一个布尔值 i​sValid，如果s​ig​是公钥p​k下消息的有效签名，则该值为true，否则为false。
我们要求满足以下两个性质：
● 有效签名必须验证 verify(​p​k,​m​essage,​sign(​s​k,​m​essage)​) == t​rue
● 签名本质上是不可伪造的

我们注意到，generateKeys 和 sign 可以是随机算法。 事实上，generateKeys 最好是随机的，因为它应该为不同的人生成不同的密钥。 另一方面，验证始终是确定性的。

现在让我们更详细地研究数字签名方案所需的两个属性。 第一个属性很简单——必须验证有效签名。 如果我使用 s​k（我的密钥）签署一条消息，并且稍后有人尝试使用我的公钥 p​k 在同一条消息上验证该签名，则该签名必须正确验证。 此属性是签名发挥作用的基本要求。

不可伪造性。 第二个要求是伪造签名在计算上是不可行的。 也就是说，知道您的公钥并可以看到您在其他一些消息上的签名的对手无法在他没有看到您的签名的某些消息上伪造您的签名。 这种不可伪造性通常以我们与对手玩的游戏来形式化。 游戏的使用在密码安全证明中相当常见。

在不可伪造性游戏中，有一个对手声称他可以伪造签名，还有一个挑战者将测试这一主张。 我们要做的第一件事是使用 g​enerateKeys​生成一个秘密签名密钥和相应的公共验证密钥。 我们将密钥提供给挑战者，并将公钥提供给挑战者和对手。 因此，对手只知道公开的信息，而他的任务就是试图伪造信息。 挑战者知道秘密密钥。 这样他就可以签名了。

直观上，该游戏的设置符合现实世界的条件。 现实生活中的攻击者可能能够在许多不同的文档上看到潜在受害者的有效签名。 如果这对攻击者有用的话，攻击者甚至可以操纵受害者签署看似无害的文件。

为了在我们的游戏中对此进行建模，我们将允许攻击者在他选择的某些文档上获得签名，只要他愿意，只要猜测的数量是合理的。 给个直观的理解合理的猜测次数意味着什么，我们允许攻击者尝试 100 万次猜测，但不允许 2⁸⁰ 次猜测²。

一旦攻击者确信他看到了足够的签名，那么攻击者就会选择一些消息 M，他们将尝试在其上伪造签名。 对 M​的唯一限制是，它必须是攻击者之前未见过签名的消息（因为攻击者显然可以发回他所获得的签名！）。 挑战者运行验证算法来确定攻击者生成的签名是否是公共验证密钥下 M 上的有效签名。 如果验证成功，攻击者就赢得了游戏。

2 用渐近术语来说，我们允许攻击者尝试多次猜测，这些猜测是密钥大小的多项式函数，但不能更多（例如，攻击者不能尝试指数级多次猜测）。

More Details