Аннотация
Чисто одноранговая версия электронных денег позволит отправлять онлайн-платежи напрямую от одной стороны к другой, минуя финансовое учреждение. Цифровые подписи обеспечивают часть решения, но основные преимущества теряются, если доверенная третья сторона по-прежнему требуется для предотвращения двойных расходов. Мы предлагаем решение проблемы двойного расходования с помощью одноранговой сети. Сеть метит временные метки транзакций, хешируя их в непрерывную цепочку доказательств работы на основе хэша, формируя запись, которая не может быть изменена без повторного подтверждения работы. Самая длинная цепочка служит не только доказательством последовательности событий, свидетелями которых они стали, но и доказательством того, что она исходила из самого большого пула мощности процессора. До тех пор, пока большая часть мощности процессора контролируется узлами, которые не сотрудничают для атаки на сеть, они будут генерировать самую длинную цепочку и опережать злоумышленников. Сама сеть требует минимальной структуры. Сообщения транслируются на основе максимальных усилий, и узлы могут покидать сеть и присоединяться к ней по своему желанию, принимая самую длинную цепочку доказательства работы в качестве доказательства того, что произошло, пока их не было.
1. Введение
Торговля в Интернете стала полагаться почти исключительно на финансовые учреждения, выступающие в качестве доверенных третьих сторон для обработки электронных платежей. Несмотря на то, что система работает достаточно хорошо для большинства транзакций, она по-прежнему страдает от недостатков, присущих модели, основанной на доверии. Полностью необратимые транзакции на самом деле невозможны, поскольку финансовые учреждения не могут избежать посредничества в спорах. Издержки, связанные с посредничеством, увеличивают трансакционные издержки, ограничивая минимальный практический размер сделки и отсекая возможность для мелких случайных сделок, а также более широкие издержки связаны с потерей возможности производить необратимые платежи за необратимые услуги. С возможностью разворота потребность в доверии распространяется. Продавцы должны опасаться своих клиентов, требуя от них больше информации, чем им понадобилось бы в противном случае. Определенный процент мошенничества считается неизбежным. Этих затрат и неопределенностей с платежами можно избежать лично, используя физическую валюту, но не существует механизма для осуществления платежей по каналу связи без доверенной стороны.
Что необходимо, так это электронная платежная система, основанная на криптографическом доказательстве, а не на доверии, позволяющая любым двум желающим сторонам совершать сделки напрямую друг с другом без необходимости в доверенной третьей стороне. Транзакции, которые с вычислительной точки зрения нецелесообразно отменить, защитят продавцов от мошенничества, а обычные механизмы условного депонирования могут быть легко реализованы для защиты покупателей. В этой статье мы предлагаем решение проблемы двойного расходования с использованием однорангового распределенного сервера меток времени для генерации вычислительного доказательства хронологического порядка транзакций. Система безопасна до тех пор, пока честные узлы коллективно контролируют большую мощность процессора, чем любая сотрудничающая группа узлов-злоумышленников.
2. Транзакции
Мы определяем электронную монету как цепочку цифровых подписей. Каждый владелец передает монету следующему, подписывая цифровой подписью хэш предыдущей транзакции и открытый ключ следующего владельца и добавляя их в конец монеты. Получатель платежа может проверить подписи, чтобы проверить цепочку владения.
Проблема, конечно, в том, что получатель платежа не может проверить, что один из владельцев не потратил монету дважды. Распространенным решением является введение доверенного центрального органа, или монетного двора, который проверяет каждую транзакцию на предмет двойных расходов. После каждой транзакции монета должна быть возвращена монетному двору для выпуска новой монеты, и только монеты, выпущенные непосредственно монетным двором, не могут быть потрачены дважды. Проблема с этим решением заключается в том, что судьба всей денежной системы зависит от компании, управляющей монетным двором, и каждая транзакция должна проходить через них, как банк.
Нам нужен способ, чтобы получатель платежа знал, что предыдущие владельцы не подписывали никаких предыдущих транзакций. Для наших целей самая ранняя транзакция — это та, которая имеет значение, поэтому нас не волнуют последующие попытки двойного расходования. Единственный способ подтвердить отсутствие транзакции — быть в курсе всех транзакций. В модели, основанной на монетном дворе, монетный двор знал обо всех транзакциях и решал, какая из них прибыла первой. Чтобы сделать это без доверенной стороны, транзакции должны быть публично объявлены[1], и нам нужна система, чтобы участники согласовывали единую историю того порядка, в котором они были получены. Получателю платежа необходимо доказать, что во время каждой транзакции большинство узлов согласились с тем, что она была получена первой.
3. Сервер меток времени
Решение, которое мы предлагаем, начинается с сервера временных меток. Сервер меток времени работает, беря хэш блока элементов для отметки времени и широко публикуя хэш, например, в газете или сообщении Usenet[2-5]. Временная метка доказывает, что данные должны были существовать в то время, очевидно, чтобы попасть в хэш. Каждая метка времени включает предыдущую метку времени в свой хэш, образуя цепочку, причем каждая дополнительная метка времени усиливает предыдущие.
4. Доказательство работы
Чтобы реализовать распределенный сервер меток времени на одноранговой основе, нам нужно будет использовать систему доказательства работы, аналогичную Hashcash Адама Бэка[6], а не в газетах или сообщениях в Usenet. Доказательство работы включает в себя сканирование значения, которое при хешировании, например, в SHA-256, начинается с количества нулевых битов. Средняя требуемая работа экспоненциальна по количеству требуемых нулевых битов и может быть проверена путем выполнения одного хэша.
Для нашей сети меток времени мы реализуем доказательство работы, увеличивая одноразовый номер в блоке до тех пор, пока не будет найдено значение, которое дает хэшу блока требуемые нулевые биты. После того, как усилия ЦП были затрачены на то, чтобы он удовлетворял доказательству работы, блок не может быть изменен без повторного выполнения работы. Поскольку более поздние блоки объединяются в цепочку после него, работа по изменению блока будет включать в себя повторение всех блоков после него.
Proof-of-work также решает проблему определения представительства при принятии решений большинством. Если бы большинство было основано на принципе «один IP-адрес-один голос», оно могло бы быть подорвано любым, кто может выделить много IP-адресов. Proof-of-work — это, по сути, один процессор — один голос. Решение большинства представлено самой длинной цепочкой, в которую вложено наибольшее количество усилий по доказательству работы. Если большая часть мощности процессора контролируется честными узлами, честная цепочка будет расти быстрее всех и опережать любые конкурирующие цепочки. Чтобы изменить прошлый блок, злоумышленнику придется переделать доказательство работы блока и всех последующих блоков, а затем догнать и превзойти работу честных узлов. Позже мы покажем, что вероятность того, что более медленный злоумышленник догонит его, уменьшается экспоненциально по мере добавления последующих блоков.
Чтобы компенсировать увеличение скорости оборудования и изменение интереса к запуску узлов с течением времени, сложность доказательства работы определяется скользящей средней, ориентированной на среднее количество блоков в час. Если они генерируются слишком быстро, сложность увеличивается.
5. Сеть
Для запуска сети выполните следующие действия:
- Новые транзакции транслируются на все узлы.
- Каждый узел собирает новые транзакции в блок.
- Каждый узел работает над поиском сложного доказательства работы для своего блока.
- Когда узел находит доказательство работы, он транслирует блок всем узлам.
- Узлы принимают блок только в том случае, если все транзакции в нем действительны и еще не потрачены.
- Узлы выражают свое принятие блока, работая над созданием следующего блока в цепочке, используя хэш принятого блока в качестве предыдущего хэша.
Узлы всегда считают самую длинную цепочку правильной и будут продолжать работать над ее расширением. Если два узла одновременно транслируют разные версии следующего блока, некоторые узлы могут получить одну или другую первыми. В этом случае они работают над первой полученной, но сохраняют вторую ветку на случай, если она станет длиннее. Стяжка будет разорвана, когда будет найдено следующее доказательство работы, и одна ветвь станет длиннее; Узлы, которые работали над другой ветвью, затем переключатся на более длинную.
Новые трансляции транзакций не обязательно должны охватывать все узлы. Пока они достигают многих узлов, они вскоре попадут в блок. Блокировка трансляций также терпима к пропущенным сообщениям. Если узел не получает блок, он запросит его, когда получит следующий блок и поймет, что пропустил один.
6. Стимулирование
По соглашению, первая транзакция в блоке — это специальная транзакция, которая запускает новую монету, принадлежащую создателю блока. Это добавляет стимул для узлов поддерживать сеть, и дает возможность изначально распределять монеты в обращение, поскольку нет центрального органа для их выпуска. Постоянное добавление константы количества новых монет аналогично золотодобытчикам, расходующим ресурсы на добавление золота в обращение. В нашем случае расходуется именно процессорное время и электричество.
Стимул также может быть профинансирован за счет комиссий за транзакции. Если выходное значение транзакции меньше ее входного значения, разница представляет собой комиссию за транзакцию, которая добавляется к стимулирующей стоимости блока, содержащего транзакцию. После того, как в обращение поступило заранее определенное количество монет, стимул может полностью перейти на комиссию за транзакцию и быть полностью свободным от инфляции.
Стимул может помочь побудить узлы оставаться честными. Если жадный злоумышленник сможет собрать больше мощности процессора, чем все честные узлы, ему придется выбирать между использованием его для обмана людей путем кражи его платежей или использованием его для генерации новых монет. Ему должно быть выгоднее играть по правилам, таким правилам, которые благоприятствуют ему с большим количеством новых монет, чем у всех остальных вместе взятых, чем подрывать систему и обоснованность его собственного богатства.
7. Освобождение места на диске
После того, как последняя транзакция в монете похоронена под достаточным количеством блоков, потраченные транзакции перед ней могут быть отброшены для экономии места на диске. Чтобы облегчить это без нарушения хэша блока, транзакции хешируются в дереве Меркла [7][2][5], при этом в хэш блока включен только корень. Затем старые блоки можно уплотнить, обрубив ветви дерева. Внутренние хэши хранить не нужно.
Заголовок блока без транзакций будет иметь размер около 80 байт. Если мы предположим, что блоки генерируются каждые 10 минут, 80 байт * 6 * 24 * 365 = 4,2 МБ в год. Поскольку компьютерные системы обычно продаются с 2 ГБ ОЗУ по состоянию на 2008 год, а закон Мура предсказывает текущий рост на 1,2 ГБ в год, хранилище не должно быть проблемой, даже если заголовки блоков должны храниться в памяти.
8. Упрощенная проверка платежа
Можно проверять платежи без запуска полного узла сети. Пользователю нужно только сохранить копию заголовков блоков самой длинной цепочки доказательств работы, которую он может получить, запросив узлы сети, пока не убедится, что у него самая длинная цепочка, и получить ветвь Меркла, связывающую транзакцию с блоком, в котором она отмечена меткой времени. Он не может проверить транзакцию самостоятельно, но, связав ее с местом в цепочке, он может увидеть, что узел сети принял ее, и блоки, добавленные после того, как он дополнительно подтвердит, что сеть приняла ее.
Таким образом, проверка надежна до тех пор, пока сеть контролируется честными узлами, но более уязвима, если сеть подавлена злоумышленником. В то время как сетевые узлы могут проверять транзакции для себя, упрощенный метод может быть обманут сфабрикованными транзакциями злоумышленника до тех пор, пока злоумышленник может продолжать подавлять сеть. Одна из стратегий защиты от этого может заключаться в том, чтобы принимать оповещения от сетевых узлов, когда они обнаруживают недействительный блок, предлагая программному обеспечению пользователя загрузить полный блок и предупреждающие транзакции для подтверждения несоответствия. Компании, которые получают частые платежи, вероятно, по-прежнему захотят запускать свои собственные узлы для более независимой безопасности и более быстрой проверки.
9. Объединение и разделение ценности
Хотя можно было бы обрабатывать монеты индивидуально, было бы громоздко делать отдельную транзакцию для каждого цента в переводе. Чтобы можно было разделить и объединить значение, транзакции содержат несколько входов и выходов. Обычно будет либо один вход из более крупной предыдущей транзакции, либо несколько входных данных, объединяющих меньшие суммы, и максимум два выхода: один для платежа и один возвращает изменение, если таковое имеется, обратно отправителю.
Следует отметить, что разветвление, когда транзакция зависит от нескольких транзакций, а эти транзакции зависят от многих других, здесь не является проблемой. Нет необходимости извлекать полную автономную копию истории транзакций.
10. Конфиденциальность
Традиционная банковская модель обеспечивает определенный уровень конфиденциальности за счет ограничения доступа к информации вовлеченными сторонами и доверенной третьей стороной. Необходимость публичного объявления обо всех транзакциях исключает этот метод, но конфиденциальность все еще можно сохранить, нарушив поток информации в другом месте: сохраняя анонимность открытых ключей. Общественность может видеть, что кто-то отправляет сумму кому-то другому, но без информации, связывающей транзакцию с кем-либо. Это похоже на уровень информации, публикуемой фондовыми биржами, где время и размер отдельных сделок, «лента», обнародуются, но без указания того, кто был сторонами.
В качестве дополнительного брандмауэра для каждой транзакции следует использовать новую пару ключей, чтобы они не были связаны с общим владельцем. Некоторые связи по-прежнему неизбежны с транзакциями с несколькими входами, которые обязательно показывают, что их входные данные принадлежали одному и тому же владельцу. Риск заключается в том, что если владелец ключа будет раскрыт, связывание может выявить другие транзакции, принадлежавшие тому же владельцу.
11. Расчеты
Мы рассматриваем сценарий, в котором злоумышленник пытается создать альтернативную цепочку быстрее, чем честную цепочку. Даже если это будет достигнуто, это не подвергнет систему произвольным изменениям, таким как создание стоимости из воздуха или получение денег, которые никогда не принадлежали злоумышленнику. Узлы не будут принимать недействительную транзакцию в качестве оплаты, а честные узлы никогда не примут блок, содержащий их. Злоумышленник может только попытаться изменить одну из своих транзакций, чтобы вернуть деньги, которые он недавно потратил.
Гонку между честной цепочкой и цепочкой злоумышленников можно охарактеризовать как биномиальное случайное блуждание. Событие успеха — это честная цепочка, расширенная на один блок, увеличивающая ее преимущество на +1, а событие неудачи — это цепочка злоумышленника, расширенная на один блок, сокращающая разрыв на -1.
Вероятность того, что злоумышленник наверстает упущенное из данного дефицита, аналогична задаче разорения игрока. Предположим, что игрок с неограниченным кредитом начинает с дефицита и потенциально играет бесконечное количество испытаний, чтобы попытаться достичь безубыточности. Мы можем рассчитать вероятность того, что он когда-нибудь достигнет безубыточности или что злоумышленник когда-нибудь догонит честную цепочку, следующим образом[8]:
pqqz===Вероятность того, что честный узел найдет следующий блокВероятность того, что злоумышленник найдет следующий блокВероятность того, что злоумышленник когда-нибудь догонит z Блоки позади�=Вероятность того, что честный узел найдет следующий блок�=Вероятность того, что злоумышленник найдет следующий блок��=Вероятность того, что злоумышленник когда-нибудь догонит�Блоки позади
qz={1(q/p)zИф≤qИф>q}��={1если�≤�(�/�)�если�>�}
Учитывая наше предположение о том, что p>q�>�, вероятность падает экспоненциально по мере увеличения количества блоков, которые злоумышленник должен догнать. Учитывая шансы против него, если он не сделает удачный выпад вперед на ранней стадии, его шансы становятся исчезающе малыми, поскольку он все больше отстает.
Теперь мы рассмотрим, как долго получатель новой транзакции должен ждать, прежде чем будет достаточно уверен, что отправитель не сможет изменить транзакцию. Мы предполагаем, что отправитель является злоумышленником, который хочет заставить получателя поверить, что он заплатил ему какое-то время, а затем переключить его, чтобы вернуть деньги себе через некоторое время. Получатель будет предупрежден, когда это произойдет, но отправитель надеется, что будет слишком поздно.
Получатель генерирует новую пару ключей и передает открытый ключ отправителю незадолго до подписания. Это не позволяет отправителю заранее подготовить цепочку блоков, непрерывно работая над ней, пока ему не повезет продвинуться достаточно далеко вперед, а затем выполнить транзакцию в этот момент. Как только транзакция отправлена, нечестный отправитель начинает тайно работать над параллельной цепочкой, содержащей альтернативную версию его транзакции.
Получатель ждет, пока транзакция не будет добавлена в блок, и z� блоки были связаны после него. Он не знает точного прогресса, достигнутого злоумышленником, но если предположить, что честные блоки заняли среднее ожидаемое время на блок, потенциальный прогресс атакующего будет распределением Пуассона с ожидаемым значением:
λ=zqp�=���
Чтобы получить вероятность того, что атакующий все еще может догнать сейчас, мы умножаем плотность Пуассона для каждого количества прогресса, которого он мог бы достичь, на вероятность того, что он мог бы догнать с этой точки:
∑k=0∞λke−λК!⋅{(q/p)(z−k)1И.Ф. К≤zИФК>z}∑�=0∞���−��!⋅{(�/�)(�−�)если�≤�1если�>�}
Перестановка, чтобы избежать суммирования бесконечного хвоста распределения…
1−∑k=0zλke−λК!(1−(q/p)(z−k))1−∑�=0����−��!(1−(�/�)(�−�))
Преобразование в код C…
#include 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. Заключение
Мы предложили систему электронных транзакций без опоры на доверие. Мы начали с обычной структуры монет, сделанных из цифровых подписей, которая обеспечивает строгий контроль над владением, но будет неполной без способа предотвращения двойных расходов. Чтобы решить эту проблему, мы предложили одноранговую сеть, использующую proof-of-work для записи общедоступной истории транзакций, которая быстро становится вычислительно нецелесообразной для злоумышленника, если честные узлы контролируют большую часть мощности процессора. Сеть надежна в своей неструктурированной простоте. Узлы работают сразу с небольшой координацией. Их не нужно идентифицировать, поскольку сообщения не направляются в какое-либо конкретное место и должны быть доставлены только на основе максимальных усилий. Узлы могут покидать сеть и присоединяться к ней по своему желанию, принимая цепочку Proof-of-Work как доказательство того, что произошло, пока их не было. Они голосуют мощностью своего процессора, выражая свое согласие с действительными блоками, работая над их расширением, и отклоняя недействительные блоки, отказываясь работать с ними. Любые необходимые правила и стимулы могут быть применены с помощью этого механизма консенсуса.
Ссылки
- В. Дай, «b-money», http://www.weidai.com/bmoney.txt, 1998.
- Х. Массиас, Х.С. Авила и Ж.-Ж. Quisquater, «Проектирование безопасной службы временных меток с минимальными требованиями к доверию», на 20-м симпозиуме по теории информации в странах Бенилюкса, май 1999 года.
- С. Хабер, В.С. Сторнетта, «Как поставить метку времени в цифровом документе», Журнал криптологии, том 3, No 2, страницы 99-111, 1991.
- Д. Байер, С. Хабер, В.С. Сторнетта, «Повышение эффективности и надежности цифровых меток времени», В последовательностях II: Методы в области связи, безопасности и информатики, стр. 329-334, 1993.
- С. Хабер, В.С. Сторнетта, «Безопасные имена для битовых строк», В материалах 4-й конференции ACM по компьютерной и коммуникационной безопасности, страницы 28-35, апрель 1997 г.
- A. Назад, «Hashcash - контрмера отказа в обслуживании», http://www.hashcash.org/papers/hashcash.pdf 2002 г.
- Р.К. Меркл, «Протоколы для криптосистем с открытым ключом», Симпозиум по безопасности и конфиденциальности 1980 года, IEEE Computer Society, страницы 122-133, апрель 1980 года.
- У. Феллер, «Введение в теорию вероятностей и ее приложения», 1957.
bitcoin-ru.pdf (185,7 КБ)