比特币和加密货币技术外文翻译资料

比特币和加密货币技术

作者：Arvind Narayanan

国籍：美国

出处： Princeton University Press

中文译文：

我们需要理解的第一个密码原语是加密哈希函数。哈希函数是一种数学函数，具有以下三个属性：

bull;它的输入可以是任何大小的任何字符串。

bull;它产生一个固定大小的输出。为了使本章中的讨论具体化，我们将假设输出大小为256位。然而我们的讨论适用于任何输出大小，只要它足够大。

bull;它是高效可计算的。直观的说，这意味着对于任意给定的输入，你可以在合理的时间内计算出哈希函数的输出，更严格的来说，计算一个n位字符串的哈希应该有O(n)的运行时间。

这些属性定义了一个通用的哈希函数，可以用来构建一个数据结构，比如哈希表。我们将专门关注加密哈希函数。为了使哈希函数加密安全，我们将要求它具有以下三个额外的属性：（1）抗冲突性，（2）隐藏性，（3）谜题友好性。

我们将更仔细研究这些属性中的每一个，以了解为什么函数以这种方式运行是有用的。学过密码学的读者都知道这本书对哈希函数的处理有点不同于标准的密码学教科书。尤其是，谜题友好性不是加密哈希函数的一般要求，而是一个对加密货币特别有用的要求。

属性1：抗冲突性。我们从加密哈希函数中需要的第一个属性就是它的抗冲突性。当两个不同的输入产生相同的输出时，就会发生冲突。哈希函数是抗冲突的如果没人能发现冲突。

x

H(x)=H(y)

y

图1.1. 哈希冲突。x和y是不同的值，当把输入输进哈希函数H时，它们产生了相同的输出。

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

可能的输出

可能的输入

图1.2.因为输入的数量超过了输出的数量，所以我们保证至少有一个输出，哈希函数能将多个输入映射到该输出。

现在，更糟糕的是，我们说不可能找到冲突。然而，有一些方法可以保证找到冲突。考虑以下查找具有256位输出大小的哈希函数冲突的简单办法：选择个不同的值，计算每个值的哈希，并检查是否有两个输出相等，因为我们选择的输入比可能的输出多，所以当你应用哈希函数时，它们中的一些必然会发生冲突。

上面的方法保证能找到冲突。但是如果我们选择随机输入并计算哈希值，在检查个输入之前，我们就会发现一个高概率的冲突。事实上，如果我们随机选择个输入，结果是有99.8%的几率至少有两个发生冲突。我们只需粗略检查可能输出数的平方根就能找到冲突，这一事实源于一种被称为“生日悖论”的概率现象。在本章最后的作业问题中，我们将更详细的讨论这个问题。

这种冲突检测算法适用于每个哈希函数。但是，当然，它的问题是需要非常非常长的时间。对于有256位输出的哈希函数，在最坏的情况下，必须计算哈希函数次，平均次。这当然是一个天文数字，如果一台计算机每秒计算10000次哈希值，计算次哈希将需要超过亿年的时间.换一种角度来看，我们可以说，如果人类制造的每台计算机从整个宇宙开始就在计算，到现在为止，它们发现冲突的几率仍然微乎其微。如此之小，比地球在两秒内被一颗巨大的流星摧毁的可能性更小。

因此我们已经看到了一个通用但不切实际的算法来寻找任何哈希函数的冲突。一个更难的问题是：是否有其他的方法可以用于特定的哈希函数，以便找到冲突？换句话说，即使通用的冲突检测算法不可行，但仍有一些其他算法可以高效的找到特定哈希函数的冲突。

例如，考虑下面的哈希函数：

这个函数满足我们对哈希函数的要求，因为它接受任何长度的输入，返回固定大小的输出，并且是有效计算的。但是这个函数也有一个寻找冲突的有效方法。请注意这个函数只返回输入的最后256位，一个冲突就是值3和.这个简单的例子说明，即使我们的通用的冲突检测方法在实践中不可行，但至少有一些哈希函数确实存在有效的冲突检测方法。

然而对于其它哈希函数，我们不知道是否存在这样的方法。我们怀疑它们是抗冲突的。然而，没有任何哈希函数被证明是抗冲突的。我们在实践中依赖的加密哈希函数只是人们已经尝试过的函数，很难找到冲突，而且没有成功。在某些情况下，例如旧版的MD5哈希函数，经过多年的工作最终发现了冲突，导致该函数被弃用并逐步退出实际使用。所以我们选择相信这些是抗冲突的。

应用：消息摘要 既然我们知道了什么是抗冲突，逻辑问题是：抗冲突有什么用？这里有一个应用，如果我们知道抗冲突哈希函数H的两个不同的输入x和y，那么可以安全的假设它们的哈希值H(x)和H(y)是不同的--如果有人知道x和y是不同的却有相同的哈希值，那么这将违背我们关于H是抗冲突的假设。

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

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

哈希作为消息的固定长度或明确的摘要。这给了我们一个非常有效的方法来记住我们以前见过的东西，并再次识别它们。虽然整个文件可能有千兆字节长，但是哈希值是固定长度的，在我们的例子中，哈希函数是256位。这大大减少了我们的存储需求。在本章的后半部分以及整本书中，我们将会看到使用哈希作为消息摘要的应用程序。

属性2：隐匿性。我们想要从哈希函数中得到的第二个属性就是隐匿性。如果给定哈希函数y=H(x)的输出，这里没有可行的方法计算输入x是什么。问题是这个属性在规定的形势下不可能是真的。考虑下面这个例子：我们要做一个实验，投掷硬币，如果硬币翻转的结果是正面，我们宣布哈希值是字符串“heads”，如果是背面，我们宣布哈希值是字符串“tails”。

然后，我们询问一个对手，他没有看到硬币翻转，但只看到了哈希输出，为了弄清楚被哈希的字符串是什么。作为回应，他们将简单的计算字符串“heads”和“tails”的哈希值，并且他们可以看到他们得到了哪一个。因此，只需几个步骤，他们就能知道输入是什么。

对手能够猜出字符串是什么，因为x只有两个可能的值，对手很容易尝试这两个值。为了能够实现隐匿性，它需要没有x的值的情况，这是特别可能的。也就是说，x必须从某种意义上来说非常分散的集合中选择x，如果从这样的集合中选择x，这种尝试几个特别可能的x值的方法将不起作用。

最大的问题是，当我们想要的值不是来自分散集合例如“heads”，“tails”实验。幸运的是，答案是肯定的。因此我们可以通过将一个未展开的输入与另一个展开的输入连接起来来隐藏它。现在我们可以更精确地说明隐匿的含义（双竖线‖表示连接）。

隐藏性。一下情况称哈希函数H是有隐藏性的：当从具有高最小熵的概率分布中选择秘密值r，给出H（r || x）是无法找到x值的。

在信息论中，最小熵是对结果可预测程度的一种度量。高最小熵抓住了分布非常分散的直观想法。具体来说，当我们从分布中抽样时，没有特定值会大概率出现。因此，举一个具体的例子，如果从所有256位长的字符串中统一选择r，那么任何特定的字符串都是以的概率被选择，这是一个非常小的值。

应用：承诺。现在我们来看一个隐藏属性的应用。例如我们想要做的是一种叫做“承诺”的东西。承诺是取值的数字模拟，将其密封在信封中，然后将信封放在每个人都可以看到的桌子上。当你这样做时，你已经承诺了信封里的东西，但是你还没有打开它，所以即使你已经承诺了一个价值，这个价值仍然是其他人的秘密。稍后，你可以打开信封并显示你之前承诺的价值。

承诺方案。一个承诺方案由两种算法组成：

• com :=commit(msg,nonce) 承诺函数将消息和随机秘密值（称为随机数）作为一个输入并返回一个承诺。
• verify(com, msg, nonce) 验证函数以承诺、随机数和消息作为输入。如果 com ==commit(msg, nonce)则返回true否则返回false。

我们要求满足一下两个安全属性。

• 隐藏性：给定 com，试图找到msg是不可行的
• 绑定性：不可能找到两对(msg, nonce) 和(msgrsquo;, noncersquo;)使得msgne;msgrsquo;，并commit(msg,nonce) == commit(msgrsquo;,noncersquo;)

为了使用承诺计划，我们首先需要生成随机数。然后我们将commit函数与msg应用于这个nonce，然后我们发布com。这个阶段类似于把密封的信封放在桌子上。稍后，如果我们想要揭示他们之前提交的值，我们会公布我们用来创建这个承诺的随机数和消息msg。现在，任何人都可以证实msg确实是之前提交的消息，这个阶段类似于打开信封。

每提交一个值时，重要的是选择一个新的随机值nonce，在密码学中，属于nonce用于指代只能使用一次的值

这两个安全属性决定了算法实际上就像密封和打开信封一样。首先，给定com，承诺，有人看着信封不知道信息是什么。第二个属性是绑定。这确保了当你把提交的东西放到信封，你不能改变主意，也就是说，找到两个不同的信息是不可能的，这样你可以提交一个消息，然后声称你提交了另一个。

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

commit(msg, nonce):= H(nonce || msg) ，nonce是一个随机的256位的值

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

再看看我们对承诺方案所要求的两个属性。如果我们用commit和verify的实例化以及H(nonce||msg)替换com，则这些属性变为：

• 隐藏性：给定H（nonce||msg）,找到msg是不可行的。
• 绑定性：找到两对(msg, nonce)和(msgrsquo;, noncersquo;)是不可行的，使得msgne;msgrsquo;以及H（nonce||msg）==H(noncersquo; ||msgrsquo;)

承诺的隐藏属性正是我们哈希函数所需要的隐藏属性。如果key被选择为一个随机的256位值，那么隐藏属性表明，如果我们对key和消息的连接进行哈希处理，那么从哈希输出中回复消息是不可行的。事实证明，绑定属性隐含在底层哈希函数的抗碰撞属性中。如果哈希函数是抗碰撞的，那么找不到不同的值msg和msgrsquo;使得H（nonce||msg）=H(noncersquo;||msgrsquo;)将是不可行的，因为这样的值是冲突的。

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

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

谜题友好性。如果对于每个可能的n位输出y，如果k是从具有高最小熵的分布中选择的，那么找到x使得H（k || x）=y在时间上明显小于2ⁿ是不可行的。

直观的说，这意味着如果有人想要用哈希函数得出某个特定的输出值y，如果输入的某个部分是以适当的随机化方式选择的，那么会很难找到另一个正好符合该目标的值

附：外文原文（五号，宋体） 剩余内容已隐藏，支付完成后下载完整资料

1.1 Cryptographic Hash Functions

The first cryptographic primitive that wersquo;ll need to understand is a cryptographic hash function. A hash function is a mathematical function with the following three properties:

• Its input can be any string of any size.
• It produces a fixed size output. For the purpose of making the discussion in this chapter concrete, we will assume a 256‐bit output size. However, our discussion holds true for any output size as long as it is sufficiently large.
• It is efficiently computable. Intuitively this means that for a given input string, you can figure

out what the output of the hash function is in a reasonable amount of time. More technically, computing the hash of an n‐bit string should have a running time that is O(n).

Those properties define a general hash function, one that could be used to build a data structure such as a hash table. Wersquo;re going to focus exclusively on cryptographic​ hash functions. For a hash function to be cryptographically secure, wersquo;re going to require that it has the following three additional properties: (1) collision‐resistance, (2) hiding, (3) puzzle‐friendliness.

Wersquo;ll look more closely at each of these properties to gain an understanding of why itrsquo;s useful to have a function that behaves that way. The reader who has studied cryptography should be aware that the treatment of hash functions in this book is a bit different from a standard cryptography textbook. The puzzle‐friendliness property, in particular, is not a general requirement for cryptographic hash functions, but one that will be useful for cryptocurrencies specifically.

Property 1: Collision‐resistance. The first property that we need from a cryptographic hash function is that itrsquo;s collision‐resistant. A collision occurs when two distinct inputs produce the same output. A hash function H(.) is collision‐resistant if nobody can find a collision. Formally:

Collision‐resistance: A hash function H is said to be collision resistant if it is infeasible to find two values, ​x and y​, such that ​x ^ne; y​, yet ​H(x)​=​H(y)​.

Figure 1.1 A hash collision. ​x ​and ​y​ are distinct values, yet when input into hash function ​H​, they produce the same output.

Notice that we said ​nobody can find ​a collision, but we did not say that no collisions exist. Actually, we know for a fact that collisions do exist, and we can prove this by a simple counting argument. The input space to the hash function contains all strings of all lengths, yet the output space contains only strings of a specific fixed length. Because the input space is larger than the output space (indeed, the input space is infinite, while the output space is finite), there must be input strings that map to the same output string. In fact, by the Pigeonhole Principle there will necessarily be a very large number of possible inputs that map to any particular output.

Figure 1.2​ Because the number of inputs exceeds the number of outputs, we are guaranteed that there must be at least one output to which the hash function maps more than one input.

Now, to make things even worse, we said that it has to be impossible to find a collision. Yet, there are methods that are guaranteed to find a collision. Consider the following simple method for finding a collision for a hash function with a 256‐bit output size: pick 2^256​ 1 distinct values, compute the hashes of each of them, and check if there are any two outputs are equal. Since we picked more inputs than possible outputs, some pair of them must collide when you apply the hash function.

The method above is guaranteed to find a collision. But if we pick random inputs and compute the hash values, wersquo;ll find a collision with high probability long before examining 2^256​ 1 inputs. In fact, if we randomly choose just 2¹³⁰ 1 inputs, it turns out therersquo;s a 99.8% chance that at least two of them are going to collide. The fact that we can find a collision by only examining roughly the square root of the number of possible outputs results from a phenomenon in probability known as the birthday​paradox​. In the homework questions at the end of this chapter, we will examine this in more detail.

This collision‐detection algorithm works for every hash function. But, of course, the problem with it is that this takes a very, very long time to do. For a hash function with a 256‐bit output, you would have to compute the hash function 2²⁵⁶ 1 times in the worst case, and about 2^128​ times on average. Thatrsquo;s of course an astronomically large number — if a computer calculates 10,000 hashes per second, it would take more than one octillion (10²⁷) years to calculate 2^128​ hashes! For another way of thinking about this, we can say that, if every computer ever made by humanity was computing since the beginning of the entire universe, up to now, the odds that they would have found a collision is still infinitesimally small. So small that itrsquo;s way less than the odds that the Earth will be destroyed by a giant meteor in the next two seconds.

We have thus seen a general but impractical algorithm to find a collision for any ​ hash function. A more difficult question is: is there some other method that could be used on a particular hash function in order to find a collision? In other words, although the generic collision detection algorithm is not feasible to use, there still may be some other algorithm t

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[596358]，资料为PDF文档或Word文档，PDF文档可免费转换为Word