Оригинал: Satoshi Nakamoto, Bitcoin: A Peer-to-Peer Electronic Cash System.
Резюме. Чисто пиринговая (полностью децентрализованная, одноранговая) версия электронной наличности могла бы позволить одному участнику платить напрямую другому участнику в реальном времени (онлайн) без какого-либо посредничества иных (существующих) финансовых институтов. Однако цифровой подписи недостаточно – необходимо ещё гарантировать защиту от повторной платы (платы уже израсходованной монетой – double-spending). Мы предлагаем решение проблемы повторной платы посредством пиринговой сети.
Сеть приписывает сделкам (транзакциям) метки времени (timestampts), хэшируя их в создаваемой цепи подтверждений (доказательств) корректно выполненной работы (proof-of-work), образуя запись, которую невозможно изменить без выполнения такого доказательства заново. Самая длинная цепь служит не только доказательством правильности содержащихся в ней фактов, но и доказательством того, что она прибыла от пула с самой большой вычислительной мощностью. До тех пор, пока большая часть вычислительной мощности контролируется лояльными узлами, не участвующими в злонамеренных атаках на сеть, они успешно создают самую длинную цепь и успешно противостоят злоумышленникам.
Сеть сама по себе требует минимума структуры. Адресации узлов не требуется вовсе, а рассылка сообщений требует лишь “максимально возможного усердия”, так что узлы могут покидать сеть или вновь соединяться с ней, используя самую длинную цепь как доказательное описание того, что произошло за время их отсутствия.
1. Введение
… Ключевая проблема: нет механизма, позволяющего платить напрямую (по каналу связи между плательщиком и получателем) без участия гаранта корректности – узла-посредника, пользующегося доверием обоих участников сделки. …
2. Сделки (Transactions)
Мы определяем электронные деньги как цепь цифровых подписей. Каждый владелец передаёт деньги следующему владельцу, подписывая хэш предыдущей сделки вместе с публичным ключом следующего владельца, и помещая это в конец цепи. Получатель может проверить подписи, чтобы проверить корректность цепи собственников.
Главная проблема в том, что получатель при этом не в состоянии проверить, что плательщик не использовал одни и те же деньги повторно. Обычное решение – внешний гарант корректности – нехорошо тем, что судьба всей денежной системы становится полностью зависимой от этого гаранта. …
Мы ликвидируем необходимость в гаранте, делая все сделки публичными (открытыми) для каждого получателя, а также обеспечивая возможность достигать согласия в том, что сделки заключены именно в том порядке, который указан в цепи.
Получателю нужно иметь доказательство того, что в момент каждой сделки большинство узлов сети было согласно, что именно эта сделка проведена первой из возможных сделок-конкурентов (возможно, с теми же деньгами в случае попытки повторной платы).
3. Метки времени (Timestamp Server)
Мы предлагаем обеспечивать метки времени, хэшируя содержащие такие метки блоки данных и делая их публичными. Метки удостоверяют, что данные существовали в соответствующий момент и, конечно, появлялись именно в том порядке, в котором они присутствуют в хэшированной цепи. Каждый блок включает предыдущую метку, образуя цепь блоков данных.
4. Подтверждение выполненной работы (Proof-of-Work)
Чтобы реализовать распределённый сервис меток времени в пиринговой сети, нам требуется система подтверждения выполненной работы, подобная Adam Back’s Hashcash [6].
Это подтверждение включает необходимость найти такое значение, хэш которого начинается с заданного числа нулей.
Затраты на такое вычисление растут экспоненциально с ростом числа заданных нулей, с то время как проверка корректности такого вычисления достаточно одной обычной операции хэширования.
Мы реализуем подтверждение работы, меняя в блоке метку времени на текущее время, пока не будет найдено требуемое значение, хэш которого начинается ровно с требуемого числа нулей. Таким образом, невозможно изменить блок, не проделав заново подтверждение выполненной работы, так как текущее время будет уже другим. Если возникнет попытка изменить промежуточный блок, то потребуется проделать подтверждение работы для всех последующих блоков.
Решена также проблема представительства большинства при принятии решений о корректности сделки. Если бы большинство определялось по принципу “один IP – один голос”, то злоумышленник, способный располагать многими IP, мог бы сыграть на этом. В нашем случае действует принцип “один процессор (вычислитель) – один голос”. Решение большинства представлено самой длинной цепью, обладающей подтверждением максимальных усилий, вложенных в подтверждение выполненной работы.
Если большая часть вычислительной мощности контролируется лояльными узлами, лояльная цепь будет расти быстрее любых потенциальных конкурентов. Чтобы модифицировать какой-либо предыдущий блок, злоумышленник должен заново проделать подтверждающую работу как для этого блока, так и для всех последующих, и только затем попытаться обогнать лояльные узлы.
Мы покажем ниже, что вероятность успеха для медленного злоумышленника падает экспоненциально по мере добавления блоков.
Чтобы компенсировать необходимый рост скорости аппаратуры и изменение интереса к поддержанию работоспособности узлов, сложность подтверждения сделана зависимой от среднего количества появляющихся новых блоков в час. Если блоки создаются слишком быстро, сложность возрастает.
5. Сеть (Network)
Работа сети состоит из следующих шагов:
- Новые сделки рассылаются всем узлам.
- Каждый узел собирает новые сделки в новый блок.
- Каждый узел работает (тратит вычислительные ресурсы), вычисляя трудное подтверждение работы.
- Когда узел находит подтверждение, он рассылает свой блок всем узлам.
- Узлы считают блок законным (воспринимают блок) только при условии, что все сделки корректны (и повторные платы отсутствуют).
- Узлы выражают своё приятие блока, используя в создании следующего блока хэш принятого предыдущего блока.
Узлы всегда признают самую длинную цепь правильной и будут работать именно с ней. Однако если два узла рассылают различные версии следующего блока одновременно, некоторые узлы могут получить ту или иную версию раньше другой. В таком случае они начинают работать с любой из них, но сохраняют вторую на случай, если она в действительности окажется длиннее (может быть продолжена дальше первой).
Эта привязка (задержка) будет разрушена, когда будет выполнено подтверждение работы и одна из ветвей окажется длиннее. Тогда узлы, работавшие над другой веткой, переключаются на более длинную.
Рассылки сделок не обязаны достигать все узлы в сети. Как только они достигнут достаточно много узлов, они уже могут быть обработаны.
Рассылка блоков также не зависит жёстко от потери сообщений (толерантна к ней) . Ведь если узел не получит некоторый блок, он обнаружит этот факт, получив следующий блок вместе с отсутствующим ранее.
6. Стимулы (Incentive)
Первая сделка в блоке – это всегда специальная сделка, создающая новую монету, принадлежащую создателю блока.
Это дополнительный стимул для узлов, чтобы поддерживать сеть, а также способ запускать в обращение новые монеты, так как никакой центральной власти (центрального эмитента) не существует.для этого.
Регулярный (стандартный) выпуск новых монет в обращение аналогичен тому, как добытчики золота тратят ресурсы, чтобы добавить в обращение золото. В нашем случае, затрачиваются вычислительные ресурсы и электричество. Стимулирование возможно также посредством налога на сделки. Если выходное значение сделки меньше входного, то разность – это налог, стимулирующий (поддерживающий) работу с этим блоком.
После того как предопределённое (исходное) количество денег выпущено в обращение, стимулы могут быть сведены исключительно к налогу на сделки при полном отсутствии инфляции.
Стимул может также помочь заинтересовать узлы оставаться лояльными. Если злоумышленника способен собрать вычислительную мощность, большую, чем у лояльных узлов, то у него есть выбор – попытаться украсть у людей их деньги или создать новые деньги и легально пустить их в оборот от своего имени в полном соответствии с общими правилами. Последнее может оказаться предпочтительнее с точки зрения его личных интересов – он получит больше денег, чем все остальные вместе взятые, вместо того, чтобы ломать систему и вместе с ней возможность собственного обогащения.
7. Экономия дискового пространства (Reclaiming Disk Space)
Когда последняя сделка в системе закрыта достаточным количеством блоков, предыдущие сделки можно не хранить, чтобы сохранить дисковое пространство. Чтобы сделать это без изменения хэша блоков, сделки хэшируются в виде дерева Меркла, и только корень этого дерева помещается в хэш блока. Старые блоки могут быть затем уплотнены за счёт обрезания ветвей дерева. Внутренние хэши хранить не требуется. Заголовок блока без сделок будет занимать порядка 80 байт. Если предположить, что блоки создаются каждые 10 минут, то 80 байт * 6 * 24 * 365 = 4.2MB в год. С учётом того, что в 2008 году оперативная память компьютера была обычно порядка 2GB, то с учётом закона Мура, предсказывающего рост порядка 1.2GB в год, проблем с памятью не должно быть, даже если заголовки блоков будут храниться в оперативной памяти.
8. Упрощённая проверка платежей (Simplified Payment Verification)
В принципе, можно проверить правильность платежей по упрощённой схеме. Достаточно иметь копию заголовков блоков самой длинной цепи подтверждений (выполненной работы), которую можно получить, запрашивая узлы сети до тех пор, пока не будет уверенности, что получена именно самая длинная цепь, и получить ветвь дерева Меркла (Ральф Меркл), связывающую проверяемую сделку с блоком, в который она включена вместе с соответствующей меткой времени. При этом невозможно перепроверить сделку самостоятельно, но, видя соответствующее место в цепи, можно убедиться, что соответствующий узел одобрил эту сделку, а наличие последующих добавленных в цепь блоков подтверждает, что сеть в целом одобрила эту сделку.
Такая проверка правильности надёжна только до тех пор, пока лояльные узлы контролируют сеть, но уязвима более полной проверки, если сеть окажется под влиянием злоумышленника. Если узлы проверяют сделки по этой схеме самостоятельно, упрощённый метод может дать неверные результаты из-за козней злоумышленника, создающего ложные сделки в тот период, пока он в состоянии контролировать сеть.
Одна из стратегий (возможностей) защититься от этого – принимать аварийные сигналы от узлов сети, обнаруживших некорректный блок, и вынуждающих программы клиента загружать полный блок и вызвавшие подозрение сделки, чтобы проверить-подтвердить их некорректность. Фирмы (бизнесы), получающие частые платежи, скорее всего будут запускать свои собственные узлы для более независимого обеспечения безопасности и быстрой проверки корректности.
9. Комбинирование и наложение платежей (Combining and Splitting Value)
Хотя обрабатывать монеты индивидуально возможно, было бы неразумно создавать отдельную сделку для каждого передаваемого цента. Чтобы позволить комбинации и разделение платежей, сделки могут содержать много входов и выходов. Обычно это будет или единый вход из крупной предыдущей сделки или много входов, содержащих небольшие объёмы платежей, и, как минимум, два выхода – один для собственно оплаты, второй для возможного возврата платежей, если он необходим, обратно плательщику.
Стоит отметить, что зависимость конкретной сделки от нескольких сделок, в свою очередь зависящих от многих других, не является проблемой в этой системе. Необходимость извлекать отдельно полную копию всей истории совершённых сделок не возникает никогда.
10. Приватность (Privacy)
Традиционная банковская модель обеспечивает некоторый уровень приватности, ограничивая доступ участников к информации, а также за счёт вовлечения доверенного дополнительного (третьего) участника. Необходимость объявить все сделки публичными противоречит этому подходу, но приватность по-прежнему может быть обеспечена иным запретом на передачу информации, поддержкой анонимности публичных ключей. Публика может видеть, что некто пересылает некую сумму другому, однако без какой либо информации о связи этой сделки с каким-либо конкретным субъектом. Это сравнимо с уровнем информации, сообщаемой в торговле на бирже, когда время и объём сделки становятся публичными, но не сообщается, кто именно эту сделку совершил. Дополнительный уровень защиты обеспечивается тем, что новая пара ключей создаётся для каждой сделки, чтобы не позволить ассоциировать эту сделку с каким-либо известным собственником. Некоторые ссылки всё ещё неустранимы в случае сделок с несколькими входами, которые означают, что все их входы (кошельки) принадлежат одному собственнику. Имеется риск, что если будет обнаружен собственник ключа, то будут обнаружены и другие сделки этого же собственника (связанные с его другими кошельками).
11. Вычисления (Calculations)
Рассмотрим сценарий, когда злоумышленник пытается создать альтернативную цепь быстрее лояльной цепи.
Даже если это произойдёт, это не значит, что система станет открытой для произвольных изменений, подобных созданию монет из воздуха или захвату денег, никогда не принадлежавших атакующему. Узлы не одобрят неправильную сделку как реальный платёж, и лояльные узлы никогда не одобрят блок, содержащий эту сделку. Злоумышленник может лишь попытаться изменить одну из его собственных сделок, вернув только что потраченные (уплаченные) деньги.
Соревнование между лояльной цепью и цепью атакующего может быть характеризовано как биномиальное случайное блуждание.
Успех – когда лояльная цепь вырастает на один блок (делая шаг вперёд), а неудача – когда атакующий наращивает на один блок свою цепь (сокращая разрыв на один шаг). Вероятность того, что атакующий преодолеет заданный разрыв, аналогична задаче о разорении игрока (в игре с противником, обладающим неограниченным капиталом). …
В нашем случае эта вероятность возрастает экспоненциально при росте количества блоков, которые атакующему необходимо изменить.
Приведём программу на языке C, вычисляющую вероятность успеха атакующего в зависимости от вероятности q построить очередной блок и количества z блоков, которые нужно заменить:
#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
12. Заключение
Мы предложили систему электронных платежей (сделок), не зависящую от доверия. Мы начали с обычной платёжной платформы с цифровыми подписямя, обеспечивающей строгий контроль за правом собственности, но недостаточно полной без защиты от повторной платы. Чтобы обеспечить эту защиту, мы предложили пиринговую (одноранговую децентрализованную) сеть, требующую подтвердить право создавать публично доступную историю сделок путём предварительного подтверждения выполненной работы, До тех пор, пока лояльные узлы контролируют основную вычислительную мощность, для потенциального злоумышленника это быстро делает непрактичным (с точки зрения затраты вычислительных ресурсов) пытаться исказить эту историю.
Сеть надёжна (робастна) за счёт простоты своей структуры (никаких подструктур) . Узлы работают одновременно, требуя минимальной координации. Их не требуется идентифицировать, так как сообщения не отправляются по конкретным адресам, требуется лишь прилагать максимум усилий, чтобы доставить сообщения максимально возможному числу узлов. (ВК: здесь в некоторых переводах ошибочно говорится о кратчайшем пути и т.п.) Узлы могут покидать сеть и возвращаться в неё, используя корректную с точки зрения подтверждения выполненной работы цепь как достоверное описание того, что произошло за время их отсутствия. Узлы голосуют с учётом их вычислительной мощности, выражая своё приятие корректных блоков, работая над их пополнением, и отвергая некорректные блоки, отказываясь от работы с ними. Любые необходимые правила и стимулы могут быть введены в действие посредством подобного механизма отбора.
Ссылки
[1] W. Dai, “b-money,” https://www.weidai.com/bmoney.txt, 1998.
[2] 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.
[3] S. Haber, W.S. Stornetta, “How to time-stamp a digital document,” In Journal of Cryptology , vol 3, no 2, pages 99-111, 1991.
[4] 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.
[5] 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.
[6] A. Back, “Hashcash – a denial of service counter-measure,” https://www.hashcash.org/papers/hashcash.pdf, 2002.
[7] R.C. Merkle, “Protocols for public key cryptosystems,” In Proc. 1980 Symposium on Security and Privacy , IEEE Computer Society, pages 122-133, April 1980.
[8] W. Feller, “An introduction to probability theory and its applications,” 1957.
Замечания
- Недавно нашёл относительно неплохой перевод на русский: https://habrahabr.ru/post/215557/ , однако посчитал разумным представить здесь и свой вариант – как минимум, для сравнения.
- О Сатоши Накамото в bitcoinwiki