Биткойн: одноранговая электронная денежная система

Абстрактный. Чисто одноранговая версия электронных денег позволит отправлять онлайн-платежи напрямую от одной стороны к другой, минуя финансовое учреждение. Цифровые подписи обеспечивают часть решения, но основные преимущества теряются, если для предотвращения двойных расходов по-прежнему требуется доверенная третья сторона. Мы предлагаем решение проблемы двойных расходов с помощью одноранговой сети. Сеть маркирует транзакции, хэшируя их в непрерывную цепочку доказательств работы на основе хэша, образуя запись, которую невозможно изменить без повторного выполнения доказательства работы. Самая длинная цепочка служит не только доказательством последовательности наблюдаемых событий, но и доказательством того, что она исходит из самого большого пула мощности процессора. Пока большая часть мощности ЦП контролируется узлами, которые не участвуют в атаке на сеть, они будут генерировать самую длинную цепочку и опережать атакующих. Сама сеть требует минимальной структуры. Сообщения передаются по принципу «максимально возможно», и узлы могут выходить из сети и снова присоединяться к ней по своему желанию, принимая самую длинную цепочку доказательства работы как доказательство того, что произошло, пока их не было.

Сатоши Накамото
satoshin@gmx.com
www.bitcoin.org

1. Введение

Коммерция в Интернете стала полагаться почти исключительно на финансовые учреждения, выступающие в качестве доверенных третьих сторон при обработке электронных платежей. Хотя система работает достаточно хорошо для большинства транзакций, она по-прежнему страдает от недостатков, присущих модели, основанной на доверии. Полностью необратимые транзакции на самом деле невозможны, поскольку финансовые учреждения не могут избежать посредничества в спорах. Стоимость посредничества увеличивает транзакционные издержки, ограничивая минимальный практический размер транзакции и исключая возможность мелких случайных транзакций, а более широкие издержки связаны с потерей возможности осуществлять необратимые платежи за необратимые услуги. С возможностью обратного хода потребность в доверии распространяется. Торговцы должны опасаться своих клиентов, требуя от них больше информации, чем им в противном случае могло бы понадобиться. Определенный процент мошенничества считается неизбежным. Этих затрат и неопределенности платежей можно избежать лично, используя физическую валюту, но не существует механизма для осуществления платежей по каналу связи без доверенной стороны.

Что необходимо, так это электронная платежная система, основанная на криптографическом доказательстве, а не на доверии, позволяющая любым двум желающим сторонам совершать транзакции напрямую друг с другом без необходимости в доверенной третьей стороне. Транзакции, которые с вычислительной точки зрения невозможно отменить, защитят продавцов от мошенничества, а для защиты покупателей можно легко внедрить обычные механизмы условного депонирования. В этой статье мы предлагаем решение проблемы двойных расходов с использованием однорангового распределенного сервера временных меток для генерации вычислительного доказательства хронологического порядка транзакций. Система безопасна, пока честные узлы коллективно контролируют большую мощность процессора, чем любая сотрудничающая группа узлов злоумышленника.

2. Сделки

Мы определяем электронную монету как цепочку цифровых подписей. Каждый владелец передает монету следующему, подписывая цифровой подписью хэш предыдущей транзакции и открытый ключ следующего владельца и добавляя их в конец монеты. Получатель платежа может проверить подписи, чтобы подтвердить цепочку владения.

Проблема, конечно, в том, что получатель платежа не может проверить, что один из владельцев не потратил монету дважды. Распространенным решением является создание доверенного центрального органа, или монетного двора, который проверяет каждую транзакцию на предмет двойных расходов. После каждой транзакции монета должна быть возвращена на монетный двор для выпуска новой монеты, и только монетам, выпущенным непосредственно монетным двором, гарантировано, что они не будут потрачены дважды. Проблема с этим решением заключается в том, что судьба всей денежной системы зависит от компании, управляющей монетным двором, и каждая транзакция должна проходить через нее, как в банке.

Нам нужен способ, чтобы получатель платежа мог знать, что предыдущие владельцы не подписывали никаких предыдущих транзакций. Для наших целей учитывается самая ранняя транзакция, поэтому нас не волнуют последующие попытки двойного расходования. Единственный способ подтвердить отсутствие транзакции — быть в курсе всех транзакций. В модели, основанной на монетном дворе, монетный двор знал обо всех транзакциях и решал, какие из них поступили первыми. Чтобы добиться этого без доверенной стороны, транзакции должны быть публично объявлены [1], и нам нужна система, позволяющая участникам согласовывать единую историю порядка их получения. Получателю платежа необходимо доказательство того, что во время каждой транзакции большинство узлов согласились, что она была получена первой.

3. Сервер временных меток

Предлагаемое нами решение начинается с сервера временных меток. Сервер временных меток работает, беря хэш блока элементов, для которых необходимо пометить время, и широко публикуя этот хэш, например, в газете или сообщении Usenet [2-5]. Метка времени доказывает, что данные, очевидно, должны были существовать в то время, чтобы попасть в хэш. Каждая временная метка включает предыдущую временную метку в свой хеш, образуя цепочку, причем каждая дополнительная временная метка усиливает предыдущую.

4. Доказательство работы

Чтобы реализовать распределенный сервер временных меток на одноранговой основе, нам нужно будет использовать систему доказательства работы, аналогичную Hashcash Адама Бэка [6], а не сообщения в газетах или Usenet. Доказательство работы включает в себя сканирование значения, которое при хешировании, например, с помощью SHA-256, хеш-код начинается с ряда нулевых битов. Средняя требуемая работа экспоненциально зависит от количества требуемых нулевых битов и может быть проверена путем выполнения одного хеширования.

Для нашей сети временных меток мы реализуем доказательство работы, увеличивая одноразовый номер в блоке до тех пор, пока не будет найдено значение, которое дает хешу блока необходимые нулевые биты. После того, как усилия ЦП были затрачены на обеспечение соответствия доказательству работы, блок нельзя изменить без повторного выполнения работы. Поскольку последующие блоки присоединяются после него, работа по изменению блока будет включать в себя переделывание всех блоков после него.

Доказательство работы также решает проблему определения представительства при принятии решений большинством. Если бы большинство основывалось на принципе «один IP-адрес — один голос», его мог бы опровергнуть любой, кто мог бы выделить много IP-адресов. Доказательство работы — это, по сути, «один процессор — один голос». Решение большинства представлено самой длинной цепочкой, в которую вложено наибольшее количество усилий по доказательству работы. Если большая часть мощности процессора контролируется честными узлами, честная цепочка будет расти быстрее всех и опережать любые конкурирующие цепочки. Чтобы изменить предыдущий блок, злоумышленнику придется переделать доказательство работы блока и всех блоков после него, а затем догнать и превзойти работу честных узлов. Позже мы покажем, что вероятность того, что более медленный злоумышленник догонит, экспоненциально уменьшается по мере добавления последующих блоков.

Чтобы компенсировать увеличение скорости оборудования и изменение интереса к работе узлов с течением времени, сложность доказательства работы определяется с помощью скользящего среднего, нацеленного на среднее количество блоков в час. Если они генерируются слишком быстро, сложность возрастает.

5. Сеть

Шаги для запуска сети следующие:

Новые транзакции передаются всем узлам.
Каждый узел собирает новые транзакции в блок.
Каждый узел работает над поиском сложного доказательства работы для своего блока.
Когда узел находит подтверждение работы, он передает блок всем узлам.
Узлы принимают блок только в том случае, если все транзакции в нем действительны и еще не потрачены.
Узлы выражают свое принятие блока, работая над созданием следующего блока в цепочке, используя хеш принятого блока в качестве предыдущего хеша.

Узлы всегда считают самую длинную цепочку правильной и продолжают работать над ее расширением. Если два узла одновременно транслируют разные версии следующего блока, некоторые узлы могут получить один или другой первым. В этом случае они работают с первой полученной веткой, но сохраняют другую ветку на случай, если она станет длиннее. Связь будет разорвана, когда будет найдено следующее доказательство работы, и одна ветвь станет длиннее; узлы, работавшие в другой ветке, переключятся на более длинную.

Широковещательная рассылка новых транзакций не обязательно должна достигать всех узлов. Как только они достигнут многих узлов, они вскоре попадут в блок. Блочные широковещательные рассылки также терпимы к пропущенным сообщениям. Если узел не получил блок, он запросит его, когда получит следующий блок и поймет, что пропустил один.

6. Стимул

По соглашению, первая транзакция в блоке — это специальная транзакция, которая запускает новую монету, принадлежащую создателю блока. Это добавляет стимул для узлов поддерживать сеть и дает возможность первоначально распределять монеты в обращение, поскольку нет центрального органа, который мог бы их выпускать. Постоянное добавление постоянного количества новых монет аналогично тому, как золотодобытчики тратят ресурсы на добавление золота в обращение. В нашем случае затрачивается процессорное время и электроэнергия.

Стимул также может быть профинансирован за счет комиссий за транзакции. Если выходное значение транзакции меньше входного значения, разница представляет собой комиссию за транзакцию, которая добавляется к поощрительной стоимости блока, содержащего транзакцию. Как только заранее определенное количество монет поступит в обращение, стимул может полностью перейти на комиссию за транзакцию и быть полностью свободным от инфляции.

Стимул может помочь узлам оставаться честными. Если жадный злоумышленник сможет собрать больше мощности процессора, чем все честные узлы, ему придется выбирать между использованием ее для обмана людей путем кражи его платежей или использованием ее для генерации новых монет. Он должен счесть более выгодным играть по правилам, таким правилам, которые позволяют ему получать больше новых монет, чем всем остальным вместе взятым, чем подрывать систему и обоснованность своего собственного богатства.

7. Освобождение дискового пространства

Как только последняя транзакция в монете будет скрыта под достаточным количеством блоков, потраченные до нее транзакции можно будет отбросить для экономии дискового пространства. Чтобы облегчить это, не нарушая хэш блока, транзакции хешируются в дереве Меркла [7][2][5], при этом в хеш блока включается только корень. Старые блоки затем можно уплотнить, отрубив ветки дерева. Внутренние хеши сохранять не нужно.

Btc wp освобождает дисковое пространство

Заголовок блока без транзакций будет иметь размер около 80 байт. Если предположить, что блоки генерируются каждые 10 минут, то 80 байт * 6 * 24 * 365 = 4,2 МБ в год. Поскольку в 2008 году компьютерные системы обычно продавались с 2 ГБ ОЗУ, а закон Мура предсказывает текущий рост на 1,2 ГБ в год, хранение не должно быть проблемой, даже если заголовки блоков должны храниться в памяти.

8. Упрощенная проверка платежа

Подтверждать платежи можно без запуска полного узла сети. Пользователю нужно только сохранить копию заголовков блоков самой длинной цепочки доказательства работы, которую он может получить, опрашивая узлы сети, пока не убедится, что у него самая длинная цепочка, и получить ветвь Меркла, связывающую транзакцию с блоком. он имеет отметку времени. Он не может проверить транзакцию самостоятельно, но, связав ее с местом в цепочке, он может увидеть, что узел сети принял ее, а блоки, добавленные после нее, еще раз подтверждают, что сеть приняла ее.

Таким образом, проверка надежна, пока честные узлы контролируют сеть, но становится более уязвимой, если сеть оказывается под контролем злоумышленника. Хотя сетевые узлы могут проверять транзакции самостоятельно, упрощенный метод может быть обманут сфабрикованными транзакциями злоумышленника до тех пор, пока злоумышленник может продолжать подавлять сеть. Одной из стратегий защиты от этого может быть принятие предупреждений от сетевых узлов, когда они обнаруживают недействительный блок, предлагающих программному обеспечению пользователя загрузить полный блок и предупреждающих транзакций для подтверждения несоответствия. Компании, которые получают частые платежи, вероятно, по-прежнему захотят запускать собственные узлы для более независимой безопасности и более быстрой проверки.

9. Объединение и разделение ценности

Хотя можно было бы обрабатывать монеты индивидуально, было бы громоздко выполнять отдельную транзакцию для каждого цента перевода. Чтобы обеспечить разделение и объединение стоимости, транзакции содержат несколько входов и выходов. Обычно будет либо один вход от более крупной предыдущей транзакции, либо несколько входов, объединяющих меньшие суммы, и не более двух выходов: один для платежа и один, возвращающий сдачу, если таковая имеется, обратно отправителю.

Следует отметить, что разветвление, когда транзакция зависит от нескольких транзакций, а эти транзакции зависят от многих других, здесь не является проблемой. Никогда не возникает необходимости извлекать полную автономную копию истории транзакций.

10. Конфиденциальность

Традиционная банковская модель обеспечивает определенный уровень конфиденциальности за счет ограничения доступа к информации участвующим сторонам и доверенной третьей стороне. Необходимость публичного объявления обо всех транзакциях исключает этот метод, но конфиденциальность все же можно сохранить, прервав поток информации в другом месте: сохраняя анонимность открытых ключей. Публика может видеть, что кто-то отправляет сумму кому-то другому, но без информации, связывающей транзакцию с кем-либо. Это похоже на уровень информации, публикуемой фондовыми биржами, где время и объем отдельных сделок, «лента», обнародуются, но без указания сторон.

В качестве дополнительного брандмауэра для каждой транзакции следует использовать новую пару ключей, чтобы предотвратить привязку их к общему владельцу. Некоторая связь по-прежнему неизбежна при транзакциях с несколькими входами, которые обязательно показывают, что их входы принадлежали одному и тому же владельцу. Риск заключается в том, что если будет раскрыт владелец ключа, привязка может выявить другие транзакции, принадлежащие тому же владельцу.

11. Расчеты

Мы рассматриваем сценарий, когда злоумышленник пытается создать альтернативную цепочку быстрее, чем честную цепочку. Даже если это будет достигнуто, это не сделает систему открытой для произвольных изменений, таких как создание ценности из воздуха или изъятие денег, которые никогда не принадлежали злоумышленнику. Узлы не будут принимать недействительную транзакцию в качестве оплаты, а честные узлы никогда не примут содержащий их блок. Злоумышленник может попытаться изменить только одну из своих транзакций, чтобы вернуть деньги, которые он недавно потратил.

Гонку между честной цепочкой и цепочкой злоумышленников можно охарактеризовать как биномиальное случайное блуждание. Событием успеха является расширение честной цепочки на один блок, увеличивающее ее преимущество на +1, а событием неудачи — расширение цепочки злоумышленника на один блок, уменьшающее разрыв на -1.

Вероятность того, что атакующий восполнит заданный дефицит, аналогична проблеме разорения игрока. Предположим, игрок с неограниченным кредитом начинает с дефицита и потенциально играет бесконечное количество попыток, пытаясь достичь безубыточности. Мы можем вычислить вероятность того, что он когда-либо достигнет безубыточности или что злоумышленник когда-либо догонит честную цепочку, следующим образом [8]:

p = вероятность того, что честный узел найдет следующий блок
q = вероятность того, что злоумышленник найдет следующий блок
qz = вероятность того, что злоумышленник когда-либо догонит z блоков позади

Учитывая наше предположение, что p > q, вероятность падает экспоненциально по мере увеличения количества блоков, которые атакующий должен догнать. Учитывая шансы против него, если он не сделает удачный рывок вперед на ранней стадии, его шансы станут исчезающе малы, поскольку он будет все больше отставать.

Теперь мы рассмотрим, как долго получатель новой транзакции должен ждать, прежде чем будет достаточно уверен, что отправитель не сможет изменить транзакцию. Мы предполагаем, что отправитель — злоумышленник, который хочет заставить получателя поверить, что он заплатил ему на какое-то время, а затем переключить его на возврат денег самому себе по прошествии некоторого времени. Когда это произойдет, получатель будет предупрежден, но отправитель надеется, что будет слишком поздно.

Получатель генерирует новую пару ключей и передает открытый ключ отправителю незадолго до подписания. Это не позволяет отправителю заранее подготовить цепочку блоков, работая над ней непрерывно, пока ему не повезет продвинуться достаточно далеко вперед, а затем выполнить транзакцию в этот момент. Как только транзакция отправлена, нечестный отправитель начинает тайно работать над параллельной цепочкой, содержащей альтернативную версию его транзакции.

Получатель ждет, пока транзакция не будет добавлена в блок и после нее не будут связаны z блоков. Он не знает точного прогресса, достигнутого злоумышленником, но если предположить, что честные блоки заняли среднее ожидаемое время на блок, потенциальный прогресс злоумышленника будет распределением Пуассона с ожидаемым значением:

Чтобы получить вероятность того, что злоумышленник все еще может догнать сейчас, мы умножаем плотность Пуассона для каждого объема прогресса, которого он мог бы достичь, на вероятность того, что он сможет догнать с этой точки:

Перестановка, чтобы избежать суммирования бесконечного хвоста распределения...

Преобразование в код C...

#include <math.h>
double AttackerSuccessProbability(double q, int z)
{
double p = 1.0 - q;
двойная лямбда = z*(q/p);
двойная сумма = 1,0;
интервал я, к;
for (k = 0; k <= z; k++)
{
двойной Пуассон = exp(-лямбда);
for (i = 1; i <= k; i++)
Пуассона *= лямбда / i;
sum -= Пуассон * (1 - pow(q/p, z - k));
}
Возвращаемая сумма;
}

Проведя некоторые результаты, мы можем увидеть, что вероятность падает экспоненциально с увеличением 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. Заключение

Мы предложили систему электронных транзакций, не полагаясь на доверие. Мы начали с обычной структуры монет, созданных на основе цифровых подписей, которая обеспечивает строгий контроль владения, но является неполной без способа предотвращения двойных расходов. Чтобы решить эту проблему, мы предложили одноранговую сеть, использующую доказательство работы для записи общедоступной истории транзакций, которую злоумышленнику быстро становится непрактично изменять в вычислительном отношении, если честные узлы контролируют большую часть мощности процессора. Сеть надежна в своей неструктурированной простоте. Узлы работают одновременно с небольшой координацией. Их не нужно идентифицировать, поскольку сообщения не перенаправляются в какое-то конкретное место, а доставляются только при максимально возможном уровне. Узлы могут покидать сеть и вновь присоединяться к ней по своему желанию, принимая цепочку доказательства работы как доказательство того, что произошло, пока их не было. Они голосуют за счет мощности своего процессора, выражая свое согласие с действительными блоками, работая над их расширением, и отклоняя недействительные блоки, отказываясь работать с ними. Любые необходимые правила и стимулы могут быть реализованы с помощью этого механизма консенсуса.