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

Перевод https://bitcoin.org/bitcoin.pdf

Аннотация

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

1. Введение

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

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

2. Транзакции

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

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

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

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

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

4.Доказательства выполнения работы (Proof-of-Work)

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

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

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

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

5.Сеть.

Шаги для работы сети следующие:

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

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

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

6.Стимул.

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

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

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

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

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

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

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

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

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

9.Обьединение и разделение стоимости.

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

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

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

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

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

12.Заключение.

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

Ссылки.

W. Dai, "b-money," http://www.widai.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," http://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.