Bitcoin.org

拜占庭将军问题

中本聪 · 2009 年 3 月 9 日

SN-10049 附来源、原文与上下文。

阅读语言

若干名拜占庭将军,每人有一台电脑,想通过暴力破解密码来攻击国王的 wi-fi。他们已经得知,密码长度为某个确定的字符数。他们一旦触发网络生成一个数据包,就必须在有限时间内破解密码,侵入并擦除日志,以免被发现。只有大多数将军同时攻击,他们才有足够的 CPU 算力及时破解密码。

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, lest they be discovered. 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 agree. It has been decided that anyone who feels like it will announce an attack time, which we'll call the "plan", and whatever plan is heard first will be the official plan. The problem is that the network is not instantaneous, and if two generals announce different plans at close to the same time, some may hear one first and others hear the other first.

他们用工作量证明链来解决这个问题。每名将军收到自己最先听到的计划后,就让电脑求解一道基于哈希的困难工作量证明题,并把计划纳入哈希。工作量证明的难度足够高,即使所有人同时计算,预计也要 10 分钟,才会有一个人找到答案,并向网络广播。收到答案后,每个人都会调整自己的工作量证明计算,把第一个答案纳入哈希,这样找到的下一个工作量证明就会接在第一个后面。如果有人原本在为另一个计划计算,就会切换到这个计划,因为它的工作量证明链现在更长。

They use a proof-of-work chain to solve the problem. Once each general receives whatever plan he hears first, he sets his computer to solve a difficult hash-based proof-of-work problem that includes the plan in its hash. The proof-of-work is difficult enough that with all of them working at once, it's expected to take 10 minutes before one of them finds a solution and broadcasts it to the network. Once received, everyone adjusts the hash in their proof-of-work computation to include the first solution, so that when they find the next proof-of-work, it chains after the first one. If anyone was working on a different plan, they switch to this one, because its proof-of-work chain is now longer.

大约两小时后,这个计划应该已经通过哈希,纳入一条包含 12 个工作量证明的链。每名将军只要验证工作量证明链的难度,就能估算每小时投入了多少并行 CPU 算力,并看出,要在规定时间内生成它,必然需要大多数电脑参与。至少,大多数人一定看到了这个计划,因为工作量证明就证明他们为它做过计算。如果工作量证明体现的 CPU 算力足够破解密码,他们就可以放心地在约定时间发动攻击。

After about two hours, the plan 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 in the allotted time. At the least, most of them had to have seen the plan, since the proof-of-work is proof that they worked on it. If the CPU power exhibited by the proof-of-work is sufficient to crack the password, they can safely attack at the agreed time.

来源

阅读字号

选择适合你的字号,之后阅读会继续使用。