比特币：点对点电子现金论文
原始发布页
打开来源页面查看 1 个交叉存档
James A. Donald 写道：
仅仅每个人都知道 X 是不够的。我们还 需要每个人都知道每个人都知道 X，并且 每个人都知道每个人都知道每个人都知道 X ——这就像拜占庭将军问题一样，是 分布式数据处理中的经典难题。
工作量证明链是拜占庭将军问题的一种解决方案。我会试着在那个语境下重新表述它。
若干名拜占庭将军各有一台计算机，想通过暴力破解密码来攻击国王的 Wi-Fi，而他们已经得知密码具有一定的字符长度。一旦他们刺激网络生成一个数据包，就必须在有限时间内破解密码，以便闯入并清除日志，否则他们就会被发现并惹上麻烦。只有其中大多数人同时发动攻击，他们才有足够的 CPU 算力及时破解密码。
他们并不特别在意攻击何时发生，只在意所有人达成一致。大家已经决定，任何想宣布时间的人都可以宣布，而最先被听到的时间将成为正式攻击时间。问题在于网络并非瞬时传输，如果两名将军在非常接近的时间宣布不同的攻击时间，有些人可能先听到一个，另一些人则先听到另一个。
他们使用工作量证明链来解决这个问题。每名将军收到自己最先听到的攻击时间后，就让自己的计算机去解决一个极其困难的工作量证明问题，并将攻击时间包含在其哈希中。这个工作量证明非常困难，预计需要他们所有人同时工作 10 分钟，才会有一人找到解。一旦其中一名将军找到一个工作量证明，他就将它广播到网络，所有人则改变自己当前的工作量证明计算，把那个工作量证明包含进自己正在计算的哈希中。如果有人原本在为另一个攻击时间计算，就会切换到这个时间，因为它的工作量证明链现在更长。
两小时后，某个攻击时间应当由一条包含 12 个工作量证明的链进行哈希。每名将军只需验证工作量证明链的难度，就能估算每小时在它上面耗费了多少并行 CPU 算力，并看出要在规定时间内产生如此多的工作量证明，必定需要大多数计算机参与。他们必定全都见过它，因为工作量证明证明了他们曾在它上面工作。如果工作量证明链所体现的 CPU 算力足以破解密码，他们就可以放心地在约定时间发动攻击。
工作量证明链正是解决你所询问的所有同步、分布式数据库和全局视图问题的方式。
英文原文
展开英文原文
James A. Donald wrote:
It is not sufficient that everyone knows X. We also need everyone to know that everyone knows X, and that everyone knows that everyone knows that everyone knows X
- which, as in the Byzantine Generals problem, is the classic hard problem of distributed data processing.
The proof-of-work chain is a solution to the Byzantine Generals' Problem. I'll try to rephrase it in that context.
A number of Byzantine Generals each have a computer and want to attack the King's wi-fi by brute forcing the password, which they've learned is a certain number of characters in length. Once they stimulate the network to generate a packet, they must crack the password within a limited time to break in and erase the logs, otherwise they will be discovered and get in trouble. They only have enough CPU power to crack it fast enough if a majority of them attack at the same time.
They don't particularly care when the attack will be, just that they all agree. It has been decided that anyone who feels like it will announce a time, and whatever time is heard first will be the official attack time. The problem is that the network is not instantaneous, and if two generals announce different attack times at close to the same time, some may hear one first and others hear the other first.
They use a proof-of-work chain to solve the problem. Once each general receives whatever attack time he hears first, he sets his computer to solve an extremely difficult proof-of-work problem that includes the attack time in its hash. The proof-of-work is so difficult, it's expected to take 10 minutes of them all working at once before one of them finds a solution. Once one of the generals finds a proof-of-work, he broadcasts it to the network, and everyone changes their current proof-of-work computation to include that proof-of-work in the hash they're working on. If anyone was working on a different attack time, they switch to this one, because its proof-of-work chain is now longer.
After two hours, one attack time should be hashed by a chain of 12 proofs-of-work. Every general, just by verifying the difficulty of the proof-of-work chain, can estimate how much parallel CPU power per hour was expended on it and see that it must have required the majority of the computers to produce that much proof-of-work in the allotted time. They had to all have seen it because the proof-of-work is proof that they worked on it. If the CPU power exhibited by the proof-of-work chain is sufficient to crack the password, they can safely attack at the agreed time.
The proof-of-work chain is how all the synchronisation, distributed database and global view problems you've asked about are solved.