原始文献 / 邮件 / Bitcoin P2P e-cash paper
Bitcoin P2P e-cash paper
Cryptography Mailing List · 2008-11-13 22:56:55 UTC
James A. Donald 写道：
> 仅仅"每个人都知道X"是不够的。我们还需要每个人都知道每个人知道X，以及每个人都知道每个人知道每个人知道每个人知道X——这和拜占庭将军问题一样，是分布式数据处理的经典难题。
工作量证明链是拜占庭将军问题的一个解决方案。我试着在那个语境中重新表述。
一批拜占庭将军每人有一台计算机，想通过暴力破解密码攻击国王的 wi-fi，他们得知密码长度为特定字符数。一旦他们刺激网络生成一个数据包，就必须在有限时间内破解密码、入侵并抹去日志，否则就会被发现并惹上麻烦。只有当大多数人同时进攻时，他们才有足够的 CPU 算力快速破解。
他们并不特别在意攻击何时进行，只在意达成一致。已经决定：任何愿意的人都可以宣布一个时间，最先被听到的时间就是官方攻击时间。问题在于网络不是瞬时的，如果两个将军在接近同一时间宣布了不同的攻击时间，有些人可能先听到一个，其他人可能先听到另一个。
他们用工作量证明链来解决这个问题。每个将军收到他最先听到的攻击时间后，就让自己的计算机求解一个极其困难的工作量证明问题，该问题的哈希中包含攻击时间。这个工作量证明非常困难，预计他们所有人同时工作10分钟才会有人找到解。一旦某位将军找到工作量证明，他就向网络广播，所有人都把当前的工作量证明计算改为包含这个工作量证明的新哈希。如果有人正在为另一个攻击时间工作，就切换到这个，因为它的工作量证明链现在更长了。
两小时后，一个攻击时间应被一条包含12个工作量证明的链哈希。每个将军只需验证工作量证明链的难度，就能估算每小时投入了多少并行 CPU 算力，并看出在规定时间内产出这么多工作量证明必定需要大多数计算机参与。他们必定都看到过它，因为工作量证明就是他们参与过的证明。如果工作量证明链展示的 CPU 算力足以破解密码，他们就可以在约定的时间安全进攻。
您问到的所有同步、分布式数据库和全局视图问题，都是通过工作量证明链解决的。
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com
英文原文
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.
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com