Биткойн: система электронных денежных средств с одноранговой сетью
Чисто одноранговая версия электронных денег позволила бы отправлять онлайн-платежи непосредственно от одной стороны к другой без прохождения через финансовое учреждение. Цифровые подписи обеспечивают часть решения, но основные преимущества теряются, если для предотвращения двойного расходования все еще требуется доверенная третья сторона. Мы предлагаем решение проблемы двойного расходования с использованием одноранговой сети. Сеть временных меток транзакции, хэшируя их в непрерывной цепи доказательства работы на основе хэша, формируя запись, которую нельзя изменить без повторной работы доказательства. Длиннейшая цепь не только служит доказательством последовательности событий, но и доказательством того, что она пришла из самого большого пула вычислительной мощности. Пока большинство вычислительной мощности контролируется узлами, которые не сотрудничают в атаке на сеть, они будут генерировать самую длинную цепь и обгонять злоумышленников. Сама сеть требует минимальной структуры. Сообщения транслируются наилучшим образом, и узлы могут покидать и вновь присоединяться к сети по своему усмотрению, принимая самую длинную цепь доказательства работы как доказательство того, что произошло, пока их не было.
1. Введение Торговля в Интернете почти полностью полагается на финансовые учреждения, выступающие в качестве доверенных третьих сторон для обработки электронных платежей. Хотя система достаточно хорошо работает для большинства транзакций, она все еще страдает от присущих слабостей модели, основанной на доверии. Полностью необратимые транзакции на самом деле не возможны, поскольку финансовые учреждения не могут избежать посредничества в спорах. Стоимость посредничества увеличивает транзакционные издержки, ограничивая минимальный практический размер транзакции и отрезая возможность для небольших случайных транзакций, и существует более широкая стоимость в потере способности совершать необратимые платежи за необратимые услуги. С возможностью отмены необходимость в доверии распространяется. Торговцы должны быть насторожены к своим клиентам, требуя от них больше информации, чем им нужно было бы в противном случае. Определенный процент мошенничества принимается как неизбежный. Эти расходы и неопределенности платежей могут быть избежаны лично, используя наличные деньги, но не существует механизма для осуществления платежей по коммуникационному каналу без доверенной стороны. Необходима электронная платежная система, основанная на криптографическом доказательстве, а не на доверии, позволяющая любым двум готовым сторонам осуществлять прямые транзакции друг с другом без необходимости в доверенной третьей стороне. Транзакции, которые вычислительно непрактичны для отмены, защищали бы продавцов от мошенничества, и рутинные механизмы эскроу могли бы легко быть реализованы для защиты покупателей. В этой статье мы предлагаем решение проблемы двойного расходования с использованием распределенного сервера временных меток одноранговой сети для генерации вычислительного доказательства хронологического порядка транзакций. Система безопасна, пока честные узлы коллективно контролируют больше вычислительной мощности, чем любая группа узлов-злоумышленников, сотрудничающих друг с другом.
2. Подтверждение транзакций Мы определяем электронную монету как цепь цифровых подписей. Каждый владелец передает монету следующему, цифрово подписывая хэш предыдущей транзакции и открытый ключ следующего владельца, добавляя их в конец монеты. Получатель может проверить подписи, чтобы подтвердить цепь владения. Транзакция Подтвердить Открытый ключ владельца 1 Хэш Подпись владельца 0 Открытый ключ владельца 1 Подпись владельца 1 Закрытый ключ владельца 1 Транзакция Открытый ключ владельца 2 Хэш Подпись владельца 2 Закрытый ключ владельца 2 Транзакция Открытый ключ владельца 3 Хэш Подпись владельца 3 Закрытый ключ владельца 3 Проблема в том, что получатель не может подтвердить, что один из владельцев не потратил монету дважды. Общим решением является введение доверенного центрального органа или монетного двора, который проверяет каждую транзакцию на предмет двойных расходов. После каждой транзакции монета должна быть возвращена в монетный двор, чтобы выпустить новую монету, и только монеты, выпущенные непосредственно из монетного двора, считаются надежными и не подлежат двойному расходованию. Проблема с этим решением заключается в том, что судьба всей денежной системы зависит от компании, управляющей монетным двором, при этом каждая транзакция должна проходить через них, как и в банке. Нам нужен способ для получателя знать, что предыдущие владельцы не подписали никаких более ранних транзакций. Для наших целей самой ранней транзакцией является та, которая имеет значение, поэтому нас не волнуют более поздние попытки двойного расходования. Единственный способ подтвердить отсутствие транзакции — быть в курсе всех транзакций. В модели на основе монетного двора монетный двор был осведомлен обо всех транзакциях и решал, какие поступили первыми. Чтобы достичь этого без доверенной стороны, транзакции должны быть публично объявлены [1], и нам нужна система, чтобы участники согласовали единую историю порядка, в котором они были получены. Получатель нуждается в доказательствах того, что в момент каждой транзакции большинство узлов согласилось, что она была первой полученной.
3. Сервер временных меток Решение, которое мы предлагаем, начинается с сервера временных меток. Сервер временных меток работает, беря хэш блока предметов, которые должны быть помечены временем, и широко публикуя хэш, например, в газете или посте Usenet [2-5]. Временная метка доказывает, что данные существовали в то время, очевидно, чтобы попасть в хэш. Каждая временная метка включает предыдущую временную метку в свой хэш, образуя цепь, где каждая дополнительная временная метка усиливает предыдущие. Хэш Хэш Блок Предмет Предмет Блок ... Предмет Предмет ...
4. Доказательство работы Для реализации распределенного сервера временных меток на основе одноранговой сети нам нужно будет использовать систему доказательства работы, аналогичную Hashcash Адама Бэка [6], а не газетные или Usenet посты. Доказательство работы включает в себя поиск значения, которое при хэшировании, например, с помощью SHA-256, хэш начинается с определенного количества нулевых битов. Средняя работа, необходимая для этого, экспоненциальна по количеству требуемых нулевых битов и может быть проверена путем выполнения одного хэша. Для нашей сети временных меток мы реализуем доказательство работы, увеличивая нонсе в блоке, пока не будет найдено значение, которое дает хэшу блока требуемые нулевые биты. После того как вычислительные усилия были потрачены, чтобы сделать его удовлетворяющим доказательству работы, блок не может быть изменен без повторной работы. Поскольку позже блоки связываются после него, работа по изменению блока будет включать повторную работу всех блоков после него. Блок Предыдущий хэш Tx Блок Нонсе Tx ... Предыдущий хэш Нонсе Tx Tx ... Доказательство работы также решает проблему определения представительства в принятии большинства решений. Если большинство основывалось на одном IP-адресе — один голос, его могли бы подорвать все, кто способен выделить много IP-адресов. Доказательство работы по сути представляет собой один ЦП — один голос. Решение большинства представлено самой длинной цепью, в которую было вложено наибольшее количество усилий по доказательству работы. Если большинство вычислительной мощности контролируется честными узлами, честная цепь будет расти быстрее и обгонит любые конкурирующие цепи. Чтобы изменить прошлый блок, злоумышленнику придется повторить доказательство работы блока и всех блоков после него, а затем догнать и превзойти работу честных узлов. Мы покажем позже, что вероятность того, что более медленный злоумышленник догонит, экспоненциально уменьшается по мере добавления последующих блоков. Чтобы компенсировать увеличение скорости аппаратного обеспечения и изменяющийся интерес к запуску узлов со временем, сложность доказательства работы определяется скользящим средним, нацеливающим на среднее количество блоков в час. Если они генерируются слишком быстро, сложность возрастает.
5. Сеть Шаги для запуска сети следующие: 1) Новые транзакции транслируются всем узлам. 2) Каждый узел собирает новые транзакции в блок. 3) Каждый узел работает над поиском сложного доказательства работы для своего блока. 4) Когда узел находит доказательство работы, он транслирует блок всем узлам. 5) Узлы принимают блок только в том случае, если все транзакции в нем действительны и еще не потрачены. 6) Узлы выражают свое принятие блока, работая над созданием следующего блока в цепи, используя хэш принятого блока в качестве предыдущего хэша. Узлы всегда считают самой длинной цепью правильную и будут продолжать работать над ее расширением. Если два узла транслируют разные версии следующего блока одновременно, некоторые узлы могут сначала получить один или другой. В этом случае они работают над первым, который они получили, но сохраняют другую ветвь на случай, если она станет длиннее. Ничья будет разрешена, когда будет найдено следующее доказательство работы, и одна ветвь станет длиннее; узлы, которые работали над другой ветвью, затем переключатся на более длинную.
Новые транзакционные трансляции не обязательно должны достигать всех узлов. Пока они достигают многих узлов, они будут включены в блок довольно быстро. Трансляции блоков также устойчивы к потерянным сообщениям. Если узел не получает блок, он запросит его, когда получит следующий блок и поймет, что пропустил один.
6. Стимул Согласно традиции, первая транзакция в блоке является специальной транзакцией, которая начинает новую монету, принадлежащую создателю блока. Это добавляет стимул для узлов поддерживать сеть и предоставляет способ первоначального распределения монет в обращении, так как нет центрального органа, который бы их выпускал. Постоянное добавление постоянного количества новых монет аналогично тому, как золотые шахтеры тратят ресурсы, чтобы добавить золото в обращение. В нашем случае это вычислительное время и электричество, которые тратятся. Стимул также может финансироваться с помощью сборов за транзакции. Если выходная стоимость транзакции меньше ее входной стоимости, разница является сбором за транзакцию, которая добавляется к ценности стимула блока, содержащего транзакцию. Как только заранее определенное количество монет попадает в обращение, стимул может полностью перейти на сборы за транзакции и стать полностью свободным от инфляции. Стимул может помочь побудить узлы оставаться честными. Если жадный злоумышленник сможет собрать больше вычислительной мощности, чем все честные узлы, ему придется выбирать между использованием ее для мошенничества, возвращая свои платежи, или использованием для генерации новых монет. Ему следует найти более прибыльным следовать правилам, таким образом, чтобы правила, которые благоприятствуют ему с большим количеством новых монет, чем у всех остальных вместе взятых, чем подрывать систему и действительность своего собственного богатства.
7. Восстановление места на диске Как только последняя транзакция в монете закапана под достаточным количеством блоков, потраченные транзакции до нее могут быть отброшены для экономии места на диске. Чтобы облегчить это без разрушения хэша блока, транзакции хэшируются в дереве Меркла [7][2][5], при этом только корень включается в хэш блока. Старые блоки могут быть сжаты путем обрезки ветвей дерева. Внутренние хэши не нужно хранить. Блок Заголовок блока (Хэш блока) Предыдущий хэш Нонсе Корень хэша Хэш01 Хэш0 Хэш1 Хэш23 Хэш2 Tx0 Tx1 Tx2 Хэш3 Tx3 Транзакции, хэшированные в дереве Меркла Блок Заголовок блока (Хэш блока) Предыдущий хэш Нонсе Корень хэша Хэш01 Хэш23 Хэш2 Хэш3 Tx3 После обрезки Tx0-2 из блока Заголовок блока без транзакций будет около 80 байт. Если предположить, что блоки генерируются каждые 10 минут, 80 байт * 6 * 24 * 365 = 4.2 МБ в год. При этом компьютерные системы обычно продаются с 2 ГБ ОЗУ на 2008 год, а Закон Мура предсказывает текущий рост на 1.2 ГБ в год, хранение не должно быть проблемой, даже если заголовки блоков должны храниться в памяти.
8. Упрощенная проверка платежей Возможно проверить платежи, не запуская полный узел сети. Пользователю нужно лишь сохранить копию заголовков блоков самой длинной цепи доказательства работы, которую он может получить, запрашивая узлы сети, пока он не убедится, что у него самая длинная цепь, и получить ветвь Меркла, связывающую транзакцию с блоком, в котором она помечена временем. Он не может проверить транзакцию сам, но, связав ее с местом в цепи, он может видеть, что узел сети принял ее, и блоки, добавленные после этого, дополнительно подтверждают, что сеть приняла ее. Самая длинная цепь доказательства работы Заголовок блока Предыдущий хэш Нонсе Корень Меркла Заголовок блока Предыдущий хэш Корень Меркла Хэш01 Хэш2 Заголовок блока Нонсе Предыдущий хэш Нонсе Корень Меркла Хэш23 Ветвь Меркла для Tx3 Хэш3 Tx3 Таким образом, проверка надежна, пока честные узлы контролируют сеть, но более уязвима, если сеть перегружена злоумышленником. Хотя узлы сети могут проверять транзакции для себя, упрощенный метод может быть обманут фальшивыми транзакциями злоумышленника, пока злоумышленник может продолжать перегружать сеть. Одна из стратегий защиты от этого состоит в том, чтобы принимать уведомления от узлов сети, когда они обнаруживают недействительный блок, побуждая программное обеспечение пользователя загружать полный блок и уведомленные транзакции, чтобы подтвердить несоответствие. Бизнесы, получающие частые платежи, вероятно, все равно захотят запускать свои собственные узлы для более независимой безопасности и более быстрой проверки.
9. Объединение и разделение ценности Хотя было бы возможно обрабатывать монеты индивидуально, было бы неуклюже делать отдельную транзакцию за каждую копейку в передаче. Чтобы позволить ценности быть разделенной и объединенной, транзакции содержат несколько входов и выходов. Обычно будет либо один вход из более крупной предыдущей транзакции, либо несколько входов, объединяющих меньшие суммы, и не более двух выходов: один для платежа и один для возврата сдачи, если таковая имеется, обратно отправителю. Транзакция Вход Вход Выход ... ... Следует отметить, что расслоение, где транзакция зависит от нескольких транзакций, и эти транзакции зависят от многих других, здесь не является проблемой. Никогда не возникает необходимости извлекать полную автономную копию истории транзакции.
10. Конфиденциальность Традиционная банковская модель достигает уровня конфиденциальности, ограничивая доступ к информации сторонами, участвующими в сделке, и доверенной третьей стороной. Необходимость публично объявлять все транзакции исключает этот метод, но конфиденциальность все еще может быть сохранена, прерывая поток информации в другом месте: сохраняя открытые ключи анонимными. Общественность может видеть, что кто-то отправляет сумму кому-то другому, но без информации, связывающей транзакцию с кем-либо. Это похоже на уровень информации, раскрываемой фондовыми биржами, где время и размер отдельных сделок, "лента", становятся публичными, но без указания, кто были стороны. Традиционная модель конфиденциальности Идентичности Новая модель конфиденциальности Идентичности Транзакции Доверенная третья сторона Транзакции Публичный контрагент Публичный В качестве дополнительного брандмауэра новая пара ключей должна использоваться для каждой транзакции, чтобы они не могли быть связаны с общим владельцем. Некоторое связывание все еще неизбежно с много входными транзакциями, которые неизбежно раскрывают, что их входы принадлежали одному и тому же владельцу. Риск заключается в том, что если владелец ключа будет раскрыт, связывание может раскрыть другие транзакции, которые принадлежали тому же владельцу.
11. Расчеты Мы рассматриваем сценарий, в котором злоумышленник пытается сгенерировать альтернативную цепь быстрее, чем честная цепь. Даже если это удастся, это не открывает систему для произвольных изменений, таких как создание ценности из ничего или присвоение денег, которые никогда не принадлежали злоумышленнику. Узлы не собираются принимать недействительную транзакцию в качестве оплаты, и честные узлы никогда не примут блок, содержащий их. Злоумышленник может только попытаться изменить одну из своих собственных транзакций, чтобы вернуть деньги, которые он недавно потратил. Состязание между честной цепью и цепью злоумышленника можно охарактеризовать как биномиальную случайную прогулку. Успех — это событие, когда честная цепь расширяется на один блок, увеличивая свое преимущество на +1, а событие неудачи — это когда цепь злоумышленника расширяется на один блок, уменьшая разрыв на -1. Вероятность того, что злоумышленник догонит от данного дефицита, аналогична проблеме разорения игрока. Предположим, что у игрока неограниченный кредит и он начинает с дефицитом и потенциально играет неограниченное количество попыток, чтобы попытаться достичь безубыточности. Мы можем рассчитать вероятность того, что он когда-либо достигнет безубыточности или того, что злоумышленник когда-либо догонит честную цепь, следующим образом [8]: p = вероятность того, что честный узел находит следующий блок q = вероятность того, что злоумышленник находит следующий блок qz = вероятность того, что злоумышленник когда-либо догонит с z блоков позади qz = { 1 если p≤q q/ pz если pq }
Принимая во внимание наше предположение, что p > q, вероятность падает экспоненциально по мере увеличения количества блоков, с которыми злоумышленнику необходимо догнать. С шансами против него, если он не сделает удачный рывок вперед в начале, его шансы становятся стремительно малыми, по мере того как он отстает. Теперь мы рассматриваем, как долго получателю новой транзакции нужно ждать, прежде чем быть достаточно уверенным, что отправитель не сможет изменить транзакцию. Мы предполагаем, что отправитель является злоумышленником, который хочет заставить получателя поверить, что он заплатил ему в течение некоторого времени, а затем переключить его, чтобы вернуть деньги себе через некоторое время. Получатель будет уведомлен, когда это произойдет, но отправитель надеется, что будет слишком поздно. Получатель генерирует новую пару ключей и передает открытый ключ отправителю незадолго до подписания. Это предотвращает отправителя от подготовки цепи блоков заранее, работая над ней непрерывно, пока ему не повезет достаточно продвинуться вперед, а затем выполняя транзакцию в этот момент. После того как транзакция отправлена, нечестный отправитель начинает работать в тайне над параллельной цепью, содержащей альтернативную версию его транзакции. Получатель ждет, пока транзакция не будет добавлена в блок и z блоков не будет связано после нее. Он не знает точного количества прогресса, которого достиг злоумышленник, но, предположив, что честные блоки заняли среднее ожидаемое время на блок, потенциальный прогресс злоумышленника будет распределением Пуассона с ожидаемым значением: =z q p Чтобы получить вероятность того, что злоумышленник все еще может догнать сейчас, мы умножаем плотность Пуассона для каждого количества прогресса, которое он мог бы сделать, на вероятность того, что он мог бы догнать с этого момента: ∞ ke− ∑ k=0 k! ⋅ { q/ pz−k если k≤z 1 если kz } Переставляя, чтобы избежать суммирования бесконечного хвоста распределения... 1−∑ k=0 z ke− k! 1−q/ pz−k Преобразование в код 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
12. Заключение Мы предложили систему для электронных транзакций, не полагаясь на доверие. Мы начали с привычной структуры монет, сделанных из цифровых подписей, которая обеспечивает сильный контроль над собственностью, но является неполной без способа предотвращения двойного расходования. Чтобы решить эту проблему, мы предложили одноранговую сеть, использующую доказательство работы для записи публичной истории транзакций, которая быстро становится вычислительно непрактичной для злоумышленника, чтобы изменить, если честные узлы контролируют большинство вычислительной мощности. Сеть надежна в своей неструктурированной простоте. Узлы работают одновременно с минимальной координацией. Им не нужно быть идентифицированными, поскольку сообщения не маршрутизируются в какое-либо определенное место и должны быть доставлены наилучшим образом. Узлы могут выходить из сети и вновь присоединяться по своему усмотрению, принимая цепь доказательства работы как доказательство того, что произошло, пока их не было. Они голосуют своей вычислительной мощностью, выражая свое принятие действительных блоков, работая над их расширением, и отвергая недействительные блоки, отказываясь работать над ними. Любые необходимые правила и стимулы могут быть обеспечены с помощью этого механизма консенсуса.