比特币：一种点对点电子现金系统
Abstract
Полностью одноранговая версия электронных денег позволила бы отправлять онлайн-платежи напрямую от одной стороны к другой без участия финансового учреждения. Цифровые подписи обеспечивают часть решения, но основные преимущества теряются, если для предотвращения двойного расходования по-прежнему требуется доверенная третья сторона. Мы предлагаем решение проблемы двойного расходования с использованием одноранговой сети. Сеть присваивает транзакциям временные метки, хешируя их в непрерывную цепочку proof-of-work на основе хешей, формируя запись, которую невозможно изменить без повторного выполнения proof-of-work. Самая длинная цепочка служит не только доказательством последовательности наблюдавшихся событий, но и доказательством того, что она создана наибольшим пулом вычислительной мощности CPU. Пока большая часть мощности CPU контролируется узлами, не участвующими в атаке на сеть, они будут генерировать самую длинную цепочку и опережать атакующих. Сама сеть требует минимальной структуры. Сообщения рассылаются по принципу максимальных усилий, и узлы могут покидать сеть и присоединяться к ней по желанию, принимая самую длинную цепочку proof-of-work как доказательство того, что произошло в их отсутствие.
Abstract
一种完全的点对点电子现金系统将允许在线支付从一方直接发送到另一方，而无需通过金融机构。数字签名提供了部分解决方案，但如果仍然需要一个可信赖的第三方来防止双重支付，那么其主要优势就会丧失。我们提出一种使用点对点网络来解决双重支付问题的方案。该网络通过将交易 hash 到一条基于 hash 的 proof-of-work 的持续增长的链中来为交易打上时间戳，形成一份不重做 proof-of-work 就无法更改的记录。最长的链不仅作为所见证事件序列的证明，而且证明它来自最大的 CPU 算力池。只要大多数 CPU 算力由不合谋攻击网络的节点控制，它们就会生成最长的链并超过攻击者。该网络本身只需要最小化的结构。消息以尽最大努力的方式广播，节点可以随时离开和重新加入网络，并接受最长的 proof-of-work 链作为其离开期间所发生事件的证明。
Introduction
Коммерция в Интернете стала почти исключительно зависеть от финансовых учреждений, выступающих в роли доверенных третьих сторон для обработки электронных платежей. Хотя система достаточно хорошо работает для большинства транзакций, она по-прежнему страдает от врожденных слабостей модели, основанной на доверии. Полностью необратимые транзакции фактически невозможны, поскольку финансовые учреждения не могут избежать посредничества в спорах. Стоимость посредничества увеличивает транзакционные издержки, ограничивая минимальный практический размер транзакции и исключая возможность мелких повседневных транзакций, а также существует более широкая цена в виде утраты возможности осуществлять необратимые платежи за необратимые услуги. С возможностью отмены потребность в доверии распространяется. Продавцы должны с осторожностью относиться к своим клиентам, запрашивая у них больше информации, чем было бы необходимо в ином случае. Определенный процент мошенничества принимается как неизбежный. Эти издержки и неопределенности платежей можно избежать при личных расчетах с использованием физической валюты, но не существует механизма для осуществления платежей по каналу связи без доверенной стороны.
Необходима электронная платежная система, основанная на криптографическом доказательстве вместо доверия, позволяющая любым двум желающим сторонам совершать сделки напрямую друг с другом без необходимости в доверенной третьей стороне. Транзакции, которые вычислительно непрактично отменить, защитили бы продавцов от мошенничества, а обычные механизмы условного депонирования могли бы быть легко реализованы для защиты покупателей. В данной работе мы предлагаем решение проблемы двойного расходования с использованием одноранговой распределенной системы серверов временных меток для генерации вычислительного доказательства хронологического порядка транзакций. Система безопасна до тех пор, пока честные узлы совместно контролируют больше вычислительной мощности CPU, чем любая кооперирующаяся группа атакующих узлов.
Introduction
互联网上的商业活动已经几乎完全依赖金融机构作为可信赖的第三方来处理电子支付。虽然该系统对于大多数交易运行得足够好，但它仍然受制于基于信任模型的固有弱点。完全不可逆的交易实际上是不可能的，因为金融机构无法避免调解纠纷。调解成本增加了交易成本，限制了最小实际交易规模，并切断了小额临时交易的可能性，而且在无法为不可逆服务进行不可逆支付方面存在更广泛的成本。由于存在逆转的可能性，对信任的需求就会蔓延。商家必须对客户保持警惕，向他们索要比其他情况下更多的信息。一定比例的欺诈被认为是不可避免的。这些成本和支付的不确定性可以通过使用实物货币进行面对面交易来避免，但不存在一种无需可信赖方就能通过通信渠道进行支付的机制。
所需要的是一种基于密码学证明而非信任的电子支付系统，允许任何两个有意愿的当事方直接进行交易，而无需可信赖的第三方。在计算上不可行的逆转交易将保护卖家免受欺诈，而常规的托管机制可以很容易地实施以保护买家。在本文中，我们提出一种使用点对点分布式时间戳服务器来生成交易时间顺序的计算证明的双重支付问题解决方案。只要诚实节点共同控制的 CPU 算力超过任何合谋的攻击者节点群组，该系统就是安全的。
Transactions
Мы определяем электронную монету как цепочку цифровых подписей. Каждый владелец передает монету следующему, подписывая цифровой подписью хеш предыдущей транзакции и открытый ключ следующего владельца и добавляя их в конец монеты. Получатель платежа может проверить подписи для верификации цепочки владения.
Проблема, разумеется, в том, что получатель платежа не может проверить, не потратил ли один из владельцев монету дважды. Распространенное решение заключается во введении доверенного центрального органа, или монетного двора, который проверяет каждую транзакцию на предмет двойного расходования. После каждой транзакции монета должна быть возвращена на монетный двор для выпуска новой монеты, и только монеты, выпущенные непосредственно монетным двором, считаются не потраченными дважды. Проблема этого решения в том, что судьба всей денежной системы зависит от компании, управляющей монетным двором, и каждая транзакция должна проходить через них, как через банк.
Нам нужен способ, позволяющий получателю платежа знать, что предыдущие владельцы не подписывали никаких более ранних транзакций. Для наших целей самая ранняя транзакция является определяющей, поэтому нас не беспокоят последующие попытки двойного расходования. Единственный способ подтвердить отсутствие транзакции — быть осведомленным обо всех транзакциях. В модели монетного двора монетный двор знал обо всех транзакциях и решал, какая поступила первой. Чтобы достичь этого без доверенной стороны, транзакции должны быть объявлены публично [^1], и нам нужна система, позволяющая участникам согласовать единую историю порядка, в котором они были получены. Получателю платежа нужно доказательство того, что в момент каждой транзакции большинство узлов согласились, что она была получена первой.
Transactions
我们将一枚电子货币定义为一条数字签名链。每个所有者通过对前一笔交易的 hash 和下一个所有者的公钥进行数字签名，并将这些附加到该货币的末尾，从而将货币转移给下一个所有者。收款人可以验证签名以验证所有权链。
当然，问题在于收款人无法验证某个所有者是否对该货币进行了双重支付。一个常见的解决方案是引入一个可信赖的中央权威机构，即铸币厂，来检查每笔交易是否存在双重支付。每次交易后，该货币必须返回铸币厂以发行新的货币，并且只有直接从铸币厂发行的货币才被信任未被双重支付。这个方案的问题是，整个货币系统的命运取决于运营铸币厂的公司，每笔交易都必须经过他们，就像银行一样。
我们需要一种方式让收款人知道前任所有者没有签署任何更早的交易。就我们的目的而言，最早的交易是算数的那个，所以我们不关心后来的双重支付尝试。确认一笔交易不存在的唯一方法是了解所有交易。在基于铸币厂的模型中，铸币厂了解所有交易并决定哪个先到达。为了在没有可信赖方的情况下实现这一点，交易必须被公开宣布 [^1]，并且我们需要一个系统让参与者就它们被接收的顺序的单一历史达成一致。收款人需要证明在每笔交易发生时，大多数节点都同意它是第一个被接收的。
Timestamp Server
Предлагаемое нами решение начинается с сервера временных меток. Сервер временных меток работает, беря хеш блока элементов, которым нужно присвоить временную метку, и широко публикуя этот хеш, например, в газете или посте Usenet [^2] [^3] [^4] [^5]. Временная метка доказывает, что данные, очевидно, должны были существовать в это время, чтобы попасть в хеш. Каждая временная метка включает предыдущую временную метку в свой хеш, образуя цепочку, где каждая дополнительная временная метка усиливает предыдущие.
Proof-of-Work
Для реализации распределенного сервера временных меток на одноранговой основе нам потребуется использовать систему proof-of-work, аналогичную Hashcash Адама Бэка [^6], вместо газет или постов Usenet. Proof-of-work включает поиск значения, хеш которого, например при использовании SHA-256, начинается с определенного количества нулевых битов. Средний объем работы, необходимый для этого, экспоненциально зависит от количества требуемых нулевых битов и может быть проверен выполнением одного хеширования.
Для нашей сети временных меток мы реализуем proof-of-work путем увеличения nonce в блоке до тех пор, пока не будет найдено значение, дающее хешу блока требуемое количество нулевых битов. После того как затрачена вычислительная мощность CPU для удовлетворения proof-of-work, блок не может быть изменен без повторного выполнения работы. Поскольку последующие блоки связываются после него, работа по изменению блока включала бы повторное выполнение всех блоков после него.
Proof-of-work также решает проблему определения представительства при принятии решений большинством. Если бы большинство определялось по принципу один-IP-адрес-один-голос, оно могло бы быть подорвано любым, кто способен выделить множество IP-адресов. Proof-of-work — это, по сути, один-CPU-один-голос. Решение большинства представлено самой длинной цепочкой, в которую вложен наибольший объем работы proof-of-work. Если большая часть мощности CPU контролируется честными узлами, честная цепочка будет расти быстрее всех и опережать любые конкурирующие цепочки. Чтобы изменить прошлый блок, атакующему пришлось бы повторно выполнить proof-of-work этого блока и всех последующих блоков, а затем догнать и превзойти работу честных узлов. Позже мы покажем, что вероятность того, что более медленный атакующий догонит, экспоненциально уменьшается по мере добавления последующих блоков.
Для компенсации возрастающей скорости оборудования и меняющегося интереса к запуску узлов с течением времени сложность proof-of-work определяется скользящим средним, нацеленным на среднее количество блоков в час. Если они генерируются слишком быстро, сложность возрастает.
Proof-of-Work
为了在点对点的基础上实现分布式时间戳服务器，我们需要使用类似于 Adam Back 的 Hashcash [^6] 的 proof-of-work 系统，而不是报纸或 Usenet 帖子。proof-of-work 涉及扫描一个值，使得对该值进行 hash（例如使用 SHA-256）时，hash 以一定数量的零位开头。所需的平均工作量随所需零位数呈指数增长，并且可以通过执行一次 hash 来验证。
对于我们的时间戳网络，我们通过在区块中递增一个 nonce 来实现 proof-of-work，直到找到一个使区块的 hash 满足所需零位数的值。一旦 CPU 花费了足够的努力使其满足 proof-of-work，该区块就无法在不重做工作的情况下被更改。随着后续区块被链接在其后，更改该区块的工作将包括重做其后所有区块的工作。
proof-of-work 还解决了在多数决定中确定代表性的问题。如果多数决定是基于一个 IP 地址一票，那么任何能够分配大量 IP 的人都可以颠覆它。proof-of-work 本质上是一个 CPU 一票。多数决定由最长的链代表，因为它投入了最大的 proof-of-work 努力。如果大多数 CPU 算力由诚实节点控制，诚实链将增长最快并超过任何竞争链。要修改一个过去的区块，攻击者必须重做该区块及其后所有区块的 proof-of-work，然后追上并超过诚实节点的工作。我们将在后面展示，一个较慢的攻击者追上的概率随着后续区块的增加呈指数下降。
为了补偿不断提高的硬件速度和随时间变化的运行节点兴趣，proof-of-work 难度由一个移动平均值确定，目标是每小时平均产出一定数量的区块。如果它们生成得太快，难度就会增加。
Network
Шаги для работы сети следующие:
- Новые транзакции рассылаются всем узлам.
- Каждый узел собирает новые транзакции в блок.
- Каждый узел работает над поиском сложного proof-of-work для своего блока.
- Когда узел находит proof-of-work, он рассылает блок всем узлам.
- Узлы принимают блок, только если все транзакции в нем действительны и не были потрачены ранее.
- Узлы выражают свое принятие блока, работая над созданием следующего блока в цепочке, используя хеш принятого блока в качестве предыдущего хеша.
Узлы всегда считают самую длинную цепочку правильной и продолжают работать над ее удлинением. Если два узла одновременно рассылают разные версии следующего блока, некоторые узлы могут получить одну или другую первой. В этом случае они работают над той, которую получили первой, но сохраняют другую ветвь на случай, если она станет длиннее. Ничья будет разрешена, когда будет найден следующий proof-of-work и одна ветвь станет длиннее; узлы, работавшие над другой ветвью, тогда переключатся на более длинную.
Рассылка новых транзакций не обязательно должна достигать всех узлов. Пока они достигают многих узлов, они попадут в блок в скором времени. Рассылка блоков также устойчива к потере сообщений. Если узел не получает блок, он запросит его при получении следующего блока, осознав, что пропустил один.
Network
运行该网络的步骤如下：
- 新交易被广播到所有节点。
- 每个节点将新交易收集到一个区块中。
- 每个节点为其区块寻找一个困难的 proof-of-work。
- 当一个节点找到一个 proof-of-work 时，它将该区块广播到所有节点。
- 节点只有在区块中所有交易都是有效的且未被花费过的情况下才接受该区块。
- 节点通过在链中创建下一个区块来表示对该区块的接受，使用被接受区块的 hash 作为前一个 hash。
节点始终将最长的链视为正确的链，并将继续在其上扩展。如果两个节点同时广播了下一个区块的不同版本，一些节点可能先接收到其中一个或另一个。在这种情况下，它们在先接收到的版本上工作，但保留另一个分支以防它变得更长。当下一个 proof-of-work 被找到且其中一个分支变得更长时，平局将被打破；在另一个分支上工作的节点将切换到更长的那个。
新交易广播不一定需要到达所有节点。只要它们到达足够多的节点，它们不久就会进入一个区块。区块广播也容忍丢失的消息。如果一个节点没有收到一个区块，它会在收到下一个区块并意识到它遗漏了一个时请求该区块。
Incentive
По соглашению, первая транзакция в блоке является специальной транзакцией, которая создает новую монету, принадлежащую создателю блока. Это добавляет стимул для узлов поддерживать сеть и обеспечивает способ первоначального распределения монет в обращение, поскольку нет центрального органа для их выпуска. Постоянное добавление фиксированного количества новых монет аналогично тому, как золотодобытчики тратят ресурсы для добавления золота в обращение. В нашем случае расходуется процессорное время и электроэнергия.
Стимул также может финансироваться за счет комиссий за транзакции. Если выходное значение транзакции меньше ее входного значения, разница представляет собой комиссию за транзакцию, которая добавляется к стимулирующему значению блока, содержащего транзакцию. Как только заранее определенное количество монет поступит в обращение, стимул может полностью перейти на комиссии за транзакции и быть полностью свободным от инфляции.
Стимул может помочь побудить узлы оставаться честными. Если жадный атакующий сможет собрать больше вычислительной мощности CPU, чем все честные узлы, ему придется выбирать между использованием ее для обмана людей путем возврата своих платежей или использованием ее для генерации новых монет. Ему должно быть выгоднее играть по правилам, которые дают ему больше новых монет, чем всем остальным вместе взятым, чем подрывать систему и обесценивать собственное богатство.
Incentive
按照惯例，区块中的第一笔交易是一笔特殊交易，它创建一枚由区块创建者拥有的新货币。这为节点支持网络增加了激励，并提供了一种将货币最初分配到流通中的方式，因为没有中央权威机构来发行它们。稳定地增加固定数量的新货币类似于金矿矿工消耗资源将黄金加入流通。在我们的案例中，消耗的是 CPU 时间和电力。
激励也可以通过交易费来资助。如果一笔交易的输出值小于其输入值，差额就是交易费，它被加到包含该交易的区块的激励值中。一旦预定数量的货币进入流通，激励就可以完全过渡到交易费，并且完全没有通货膨胀。
激励可能有助于鼓励节点保持诚实。如果一个贪婪的攻击者能够集结比所有诚实节点更多的 CPU 算力，他将不得不在使用它来通过偷回自己的付款来欺骗人们，或使用它来生成新货币之间做出选择。他应该发现按照规则行事更有利可图，因为这些规则使他获得比所有其他人加起来还多的新货币，而不是破坏系统和他自身财富的有效性。
Reclaiming Disk Space
Как только последняя транзакция в монете оказывается погребена под достаточным количеством блоков, потраченные транзакции до нее могут быть отброшены для экономии дискового пространства. Чтобы обеспечить это без нарушения хеша блока, транзакции хешируются в дереве Меркла (Merkle Tree) [^7] [^2] [^5], и только корень включается в хеш блока. Старые блоки затем могут быть сжаты путем отсечения ветвей дерева. Внутренние хеши не нужно хранить.
Заголовок блока без транзакций занимал бы около 80 байт. Если предположить, что блоки генерируются каждые 10 минут, 80 байт * 6 * 24 * 365 = 4,2 МБ в год. При том, что компьютерные системы обычно продавались с 2 ГБ ОЗУ по состоянию на 2008 год, а закон Мура предсказывает текущий рост в 1,2 ГБ в год, хранение не должно быть проблемой, даже если заголовки блоков необходимо хранить в памяти.
Reclaiming Disk Space
一旦一枚货币中的最新交易被埋在足够多的区块之下，之前已花费的交易就可以被丢弃以节省磁盘空间。为了在不破坏区块 hash 的情况下实现这一点，交易被 hash 到一棵 Merkle Tree [^7] [^2] [^5] 中，只有根节点包含在区块的 hash 中。旧区块随后可以通过裁剪树的分支来压缩。内部 hash 不需要被存储。
一个没有交易的区块头大约是 80 字节。如果我们假设区块每 10 分钟生成一次，80 字节 * 6 * 24 * 365 = 每年 4.2MB。截至 2008 年，计算机系统通常配备 2GB 的 RAM，而摩尔定律预测当前每年增长 1.2GB，即使区块头必须保存在内存中，存储也不应该成为问题。
Simplified Payment Verification
Можно проверять платежи, не запуская полный сетевой узел. Пользователю нужно лишь хранить копию заголовков блоков самой длинной цепочки proof-of-work, которую он может получить, опрашивая сетевые узлы, пока не убедится, что имеет самую длинную цепочку, и получить ветвь Меркла, связывающую транзакцию с блоком, в котором она получила временную метку. Он не может проверить транзакцию самостоятельно, но, связав ее с местом в цепочке, он может увидеть, что сетевой узел принял ее, и блоки, добавленные после нее, дополнительно подтверждают, что сеть ее приняла.
Таким образом, проверка надежна, пока честные узлы контролируют сеть, но более уязвима, если сеть захвачена атакующим. В то время как сетевые узлы могут самостоятельно проверять транзакции, упрощенный метод может быть обманут сфабрикованными транзакциями атакующего, пока тот может продолжать доминировать в сети. Одной из стратегий защиты от этого было бы принятие предупреждений от сетевых узлов при обнаружении ими недействительного блока, побуждающих программное обеспечение пользователя загрузить полный блок и отмеченные транзакции для подтверждения несоответствия. Предприятия, получающие частые платежи, вероятно, по-прежнему захотят запускать собственные узлы для более независимой безопасности и более быстрой проверки.
Simplified Payment Verification
在不运行完整网络节点的情况下验证支付是可能的。用户只需要保留一份最长 proof-of-work 链的区块头副本，他可以通过查询网络节点直到确信自己拥有最长的链来获取它，并获取将交易链接到其被打上时间戳的区块的 Merkle 分支。他无法自己检查交易，但通过将其链接到链中的某个位置，他可以看到网络节点已经接受了它，而在其后添加的区块进一步确认了网络已经接受了它。
因此，只要诚实节点控制着网络，验证就是可靠的，但如果网络被攻击者制服则更加脆弱。虽然网络节点可以自己验证交易，但只要攻击者能够继续制服网络，简化方法就可能被攻击者伪造的交易所欺骗。一种防御策略是接受来自网络节点的警报，当它们检测到无效区块时，提示用户的软件下载完整区块和被警报的交易以确认不一致性。频繁接收支付的企业可能仍然希望运行自己的节点以获得更独立的安全性和更快的验证。
Combining and Splitting Value
Хотя было бы возможно обрабатывать монеты по отдельности, было бы неудобно создавать отдельную транзакцию для каждого цента при переводе. Чтобы позволить разделение и объединение стоимости, транзакции содержат несколько входов и выходов. Обычно будет либо один вход от более крупной предыдущей транзакции, либо несколько входов, объединяющих меньшие суммы, и не более двух выходов: один для платежа и один для возврата сдачи, если таковая имеется, отправителю.
Следует отметить, что разветвление (fan-out), когда транзакция зависит от нескольких транзакций, а те, в свою очередь, зависят от еще большего числа, здесь не является проблемой. Никогда нет необходимости извлекать полную самостоятельную копию истории транзакции.
Privacy
Традиционная банковская модель обеспечивает определенный уровень конфиденциальности, ограничивая доступ к информации вовлеченными сторонами и доверенной третьей стороной. Необходимость публично объявлять все транзакции исключает этот метод, но конфиденциальность все еще может быть сохранена путем прерывания потока информации в другом месте: путем сохранения анонимности открытых ключей. Общественность может видеть, что кто-то отправляет сумму кому-то другому, но без информации, связывающей транзакцию с кем-либо. Это аналогично уровню информации, публикуемой фондовыми биржами, где время и объем отдельных сделок, «лента», делаются публичными, но без указания того, кем были стороны.
В качестве дополнительного барьера для каждой транзакции следует использовать новую пару ключей, чтобы предотвратить их привязку к общему владельцу. Некоторая связь по-прежнему неизбежна при транзакциях с несколькими входами, которые неизбежно раскрывают, что их входы принадлежали одному владельцу. Риск состоит в том, что если владелец ключа будет раскрыт, связывание может раскрыть другие транзакции, принадлежавшие тому же владельцу.
Privacy
传统的银行模型通过限制相关方和可信赖第三方对信息的访问来实现一定程度的隐私。公开宣布所有交易的必要性排除了这种方法，但隐私仍然可以通过在另一个地方打断信息流来维持：保持公钥匿名。公众可以看到某人正在向其他人发送一笔金额，但没有将交易与任何人关联的信息。这类似于证券交易所发布的信息级别，个别交易的时间和规模，即"行情"，是公开的，但不会透露当事方是谁。
作为额外的防火墙，每笔交易应使用一对新的密钥，以防止它们被关联到一个共同的所有者。对于多输入交易，某些关联仍然是不可避免的，因为它们必然揭示其输入属于同一所有者。风险在于，如果密钥的所有者被揭露，关联可能会揭示属于同一所有者的其他交易。
Calculations
Рассмотрим сценарий, в котором атакующий пытается сгенерировать альтернативную цепочку быстрее, чем честная цепочка. Даже если это удастся, это не открывает систему для произвольных изменений, таких как создание стоимости из ничего или присвоение денег, которые никогда не принадлежали атакующему. Узлы не примут недействительную транзакцию в качестве платежа, и честные узлы никогда не примут блок, содержащий такие транзакции. Атакующий может лишь попытаться изменить одну из своих собственных транзакций, чтобы вернуть деньги, которые он недавно потратил.
Гонку между честной цепочкой и цепочкой атакующего можно охарактеризовать как биномиальное случайное блуждание. Событие успеха — это удлинение честной цепочки на один блок, увеличивающее ее отрыв на +1, а событие неудачи — это удлинение цепочки атакующего на один блок, сокращающее разрыв на -1.
Вероятность того, что атакующий наверстает упущенное с заданного отставания, аналогична задаче о разорении игрока. Предположим, что игрок с неограниченным кредитом начинает с дефицита и играет потенциально бесконечное число раундов, пытаясь выйти в ноль. Мы можем рассчитать вероятность того, что он когда-либо выйдет в ноль, или что атакующий когда-либо догонит честную цепочку, следующим образом [^8]:
p = вероятность того, что честный узел найдет следующий блок
q = вероятность того, что атакующий найдет следующий блок
q = вероятность того, что атакующий когда-либо догонит, отставая на z блоков
\[ qz = \begin{cases} 1 & \text{если } p \leq q \\ \left(\frac{q}{p}\right) z & \text{если } p > q \end{cases} \]
Учитывая наше предположение, что p q, вероятность экспоненциально падает с увеличением числа блоков, которые атакующему нужно наверстать. При неблагоприятных шансах, если он не сделает удачный рывок в самом начале, его шансы становятся исчезающе малыми по мере дальнейшего отставания.
Теперь рассмотрим, как долго получатель новой транзакции должен ждать, прежде чем быть достаточно уверенным, что отправитель не может изменить транзакцию. Мы предполагаем, что отправитель — атакующий, который хочет заставить получателя поверить, что он заплатил ему, на некоторое время, а затем переключить платеж на себя после истечения некоторого времени. Получатель будет предупрежден, когда это произойдет, но отправитель надеется, что будет слишком поздно.
Получатель генерирует новую пару ключей и передает открытый ключ отправителю незадолго до подписания. Это предотвращает подготовку отправителем цепочки блоков заранее путем непрерывной работы над ней, пока ему не посчастливится достаточно продвинуться вперед, а затем выполнить транзакцию в этот момент. После отправки транзакции нечестный отправитель начинает тайно работать над параллельной цепочкой, содержащей альтернативную версию его транзакции.
Получатель ждет, пока транзакция не будет добавлена в блок и z блоков не будут связаны после него. Он не знает точный объем прогресса атакующего, но предполагая, что честные блоки создавались за среднее ожидаемое время на блок, потенциальный прогресс атакующего будет иметь распределение Пуассона с математическим ожиданием:
\[ \lambda = z\frac{q}{p} \]
Чтобы получить вероятность того, что атакующий все еще может догнать, мы умножаем плотность Пуассона для каждого объема прогресса, который он мог сделать, на вероятность того, что он сможет догнать с этой точки:
\[ \sum_{k=0}^{\infty} \frac{\lambda^k e^{-\lambda}}{k!} \cdot \left\{ \begin{array}{cl} \left(\frac{q}{p}\right)^{(z-k)} & \text{если } k \leq z \\ 1 & \text{если } k > z \end{array} \right. \]
Преобразуя, чтобы избежать суммирования бесконечного хвоста распределения...
\[ 1 - \sum_{k=0}^{z} \frac{\lambda^k e^{-\lambda}}{k!} \left(1-\left(\frac{q}{p}\right)^{(z-k)}\right) \]
Преобразуя в код на C...
#include math.h
double AttackerSuccessProbability(double q, int z)
{
double p = 1.0 - q;
double lambda = z * (q / p);
double sum = 1.0;
int i, k;
for (k = 0; k = z; k++)
{
double poisson = exp(-lambda);
for (i = 1; i = k; i++)
poisson *= lambda / i;
sum -= poisson * (1 - pow(q / p, z - k));
}
return sum;
}
Выполнив некоторые расчеты, мы можем видеть, как вероятность экспоненциально падает с z.
q=0.1
z=0 P=1.0000000
z=1 P=0.2045873
z=2 P=0.0509779
z=3 P=0.0131722
z=4 P=0.0034552
z=5 P=0.0009137
z=6 P=0.0002428
z=7 P=0.0000647
z=8 P=0.0000173
z=9 P=0.0000046
z=10 P=0.0000012
q=0.3
z=0 P=1.0000000
z=5 P=0.1773523
z=10 P=0.0416605
z=15 P=0.0101008
z=20 P=0.0024804
z=25 P=0.0006132
z=30 P=0.0001522
z=35 P=0.0000379
z=40 P=0.0000095
z=45 P=0.0000024
z=50 P=0.0000006
Решая для P менее 0,1%...
P 0.001
q=0.10 z=5
q=0.15 z=8
q=0.20 z=11
q=0.25 z=15
q=0.30 z=24
q=0.35 z=41
q=0.40 z=89
q=0.45 z=340
Calculations
我们考虑一个攻击者试图比诚实链更快地生成替代链的场景。即使这一目标达成，也不会使系统面临任意更改的风险，例如凭空创造价值或夺取从不属于攻击者的资金。节点不会接受无效交易作为支付，诚实节点永远不会接受包含无效交易的区块。攻击者只能尝试更改自己的一笔交易，以收回他最近花费的资金。
诚实链与攻击者链之间的竞赛可以被描述为一个二项随机游走。成功事件是诚实链被延长一个区块，使其领先优势增加 +1，失败事件是攻击者的链被延长一个区块，使差距缩小 -1。
攻击者从给定落后距离追上的概率类似于赌徒破产问题。假设一个拥有无限信用的赌徒从亏损开始，进行潜在的无限次尝试以达到盈亏平衡。我们可以计算他最终达到盈亏平衡的概率，即攻击者追上诚实链的概率，如下 [^8]：
p = probability an honest node finds the next block
q = probability the attacker finds the next block
q = probability the attacker will ever catch up from z blocks behind
``````
\[
qz =
\begin{cases}
1 & \text{if } p \leq q \\
\left(\frac{q}{p}\right) z & \text{if } p > q
\end{cases}
\]
假设 p q，概率随着攻击者需要追赶的区块数量的增加而呈指数下降。如果他没有在早期幸运地向前冲刺，随着他进一步落后，他的机会变得微乎其微。
我们现在考虑新交易的接收者需要等待多长时间才能充分确定发送者无法更改交易。我们假设发送者是一个攻击者，他想让接收者相信他已经付款了一段时间，然后在一段时间后将其改为支付给自己。接收者在那时会收到警报，但发送者希望那时已经太晚了。
接收者生成一对新密钥，并在签名前不久将公钥提供给发送者。这防止了发送者通过持续在其上工作来提前准备一条区块链，直到他足够幸运地取得足够的领先，然后在那个时刻执行交易。一旦交易发送，不诚实的发送者开始秘密地在一条包含其交易替代版本的并行链上工作。
接收者等待交易被添加到一个区块中，并且在其后链接了 z 个区块。他不知道攻击者已经取得的确切进展，但假设诚实区块按照每个区块的平均预期时间产出，攻击者的潜在进展将是一个期望值为以下值的泊松分布：
\[
\lambda = z\frac{q}{p}
\]
为了获得攻击者现在仍然能够追上的概率，我们将他可能取得的每个进展量的泊松密度乘以他从该点追上的概率：
\[
\sum_{k=0}^{\infty} \frac{\lambda^k e^{-\lambda}}{k!} \cdot \left\{
\begin{array}{cl}
\left(\frac{q}{p}\right)^{(z-k)} & \text{if } k \leq z \\
1 & \text{if } k > z
\end{array}
\right.
\]
重新整理以避免对分布的无穷尾部求和......
\[
1 - \sum_{k=0}^{z} \frac{\lambda^k e^{-\lambda}}{k!} \left(1-\left(\frac{q}{p}\right)^{(z-k)}\right)
\]
转换为 C 代码......
```c
#include math.h
double AttackerSuccessProbability(double q, int z)
{
double p = 1.0 - q;
double lambda = z * (q / p);
double sum = 1.0;
int i, k;
for (k = 0; k = z; k++)
{
double poisson = exp(-lambda);
for (i = 1; i = k; i++)
poisson *= lambda / i;
sum -= poisson * (1 - pow(q / p, z - k));
}
return sum;
}
运行一些结果，我们可以看到概率随 z 呈指数下降。
q=0.1
z=0 P=1.0000000
z=1 P=0.2045873
z=2 P=0.0509779
z=3 P=0.0131722
z=4 P=0.0034552
z=5 P=0.0009137
z=6 P=0.0002428
z=7 P=0.0000647
z=8 P=0.0000173
z=9 P=0.0000046
z=10 P=0.0000012
q=0.3
z=0 P=1.0000000
z=5 P=0.1773523
z=10 P=0.0416605
z=15 P=0.0101008
z=20 P=0.0024804
z=25 P=0.0006132
z=30 P=0.0001522
z=35 P=0.0000379
z=40 P=0.0000095
z=45 P=0.0000024
z=50 P=0.0000006
求解 P 小于 0.1%......
P 0.001
q=0.10 z=5
q=0.15 z=8
q=0.20 z=11
q=0.25 z=15
q=0.30 z=24
q=0.35 z=41
q=0.40 z=89
q=0.45 z=340
Conclusion
Мы предложили систему электронных транзакций, не основанную на доверии. Мы начали с обычной структуры монет, созданных из цифровых подписей, которая обеспечивает надежный контроль над собственностью, но является неполной без способа предотвращения двойного расходования. Для решения этой проблемы мы предложили одноранговую сеть, использующую proof-of-work для записи публичной истории транзакций, которую быстро становится вычислительно непрактично изменить для атакующего, если честные узлы контролируют большую часть мощности CPU. Сеть устойчива в своей неструктурированной простоте. Узлы работают одновременно с минимальной координацией. Их не нужно идентифицировать, поскольку сообщения не направляются в какое-либо конкретное место и должны быть доставлены лишь по принципу максимальных усилий. Узлы могут покидать сеть и присоединяться к ней по желанию, принимая цепочку proof-of-work как доказательство того, что произошло в их отсутствие. Они голосуют своей вычислительной мощностью CPU, выражая принятие действительных блоков работой над их продлением и отклоняя недействительные блоки отказом работать над ними. Любые необходимые правила и стимулы могут быть реализованы с помощью этого механизма консенсуса.
Conclusion
我们提出了一种不依赖信任的电子交易系统。我们从由数字签名构成的货币的通常框架开始，这提供了对所有权的强有力控制，但如果没有防止双重支付的方法则是不完整的。为了解决这个问题，我们提出了一种使用 proof-of-work 的点对点网络来记录交易的公共历史，如果诚实节点控制了大多数 CPU 算力，对攻击者来说更改记录在计算上很快就变得不可行。该网络在其非结构化的简单性中是健壮的。节点同时工作，几乎不需要协调。它们不需要被识别，因为消息不会被路由到任何特定的地方，只需要以尽最大努力的方式传递。节点可以随时离开和重新加入网络，接受 proof-of-work 链作为其离开期间所发生事件的证明。它们用自己的 CPU 算力投票，通过在有效区块上扩展来表示接受，通过拒绝在无效区块上工作来表示拒绝。任何需要的规则和激励都可以通过这种共识机制来执行。
References
-
H. Massias, X.S. Avila, and J.-J. Quisquater, "Design of a secure timestamping service with minimal trust requirements," In 20th Symposium on Information Theory in the Benelux, May 1999.
-
S. Haber, W.S. Stornetta, "How to time-stamp a digital document," In Journal of Cryptology, vol 3, no 2, pages 99-111, 1991.
-
D. Bayer, S. Haber, W.S. Stornetta, "Improving the efficiency and reliability of digital time-stamping," In Sequences II: Methods in Communication, Security and Computer Science, pages 329-334, 1993.
-
S. Haber, W.S. Stornetta, "Secure names for bit-strings," In Proceedings of the 4th ACM Conference on Computer and Communications Security, pages 28-35, April 1997.
-
A. Back, "Hashcash - a denial of service counter-measure," http://www.hashcash.org/papers/hashcash.pdf, 2002.
-
R.C. Merkle, "Protocols for public key cryptosystems," In Proc. 1980 Symposium on Security and Privacy, IEEE Computer Society, pages 122-133, April 1980.
-
W. Feller, "An introduction to probability theory and its applications," 1957.
References
-
H. Massias, X.S. Avila, and J.-J. Quisquater, "Design of a secure timestamping service with minimal trust requirements," In 20th Symposium on Information Theory in the Benelux, May 1999.
-
S. Haber, W.S. Stornetta, "How to time-stamp a digital document," In Journal of Cryptology, vol 3, no 2, pages 99-111, 1991.
-
D. Bayer, S. Haber, W.S. Stornetta, "Improving the efficiency and reliability of digital time-stamping," In Sequences II: Methods in Communication, Security and Computer Science, pages 329-334, 1993.
-
S. Haber, W.S. Stornetta, "Secure names for bit-strings," In Proceedings of the 4th ACM Conference on Computer and Communications Security, pages 28-35, April 1997.
-
A. Back, "Hashcash - a denial of service counter-measure," http://www.hashcash.org/papers/hashcash.pdf, 2002.
-
R.C. Merkle, "Protocols for public key cryptosystems," In Proc. 1980 Symposium on Security and Privacy, IEEE Computer Society, pages 122-133, April 1980.
-
W. Feller, "An introduction to probability theory and its applications," 1957.
