Предлагаю вниманию сообщества вольный перевод оригинальной статьи Satoshi Nakamoto «Bitcoin: A Peer-to-Peer Electronic Cash System».
От переводчика:
Я не являюсь профессиональным переводчиком и плохо разбираюсь в криптографии, но вот недавно заинтересовался технологией Биткоин и захотел начать изучение с первооснов. Беглый поиск по интернету не дал мне перевода основополагающей статьи Satoshi Nakamoto и я решил попробовать перевести ее сам.
Вскоре после того как перевод был начат я понял, что английский язык, скорее всего, не является родным для автора статьи поскольку иногда было крайне трудно понять — что автор подразумевает и зачем в одном предложении так много частиц «and». Однако большинство трудностей удалось преодолеть и я решил представить сей конечный продукт публике.
Коротко.
Полностью децентрализованная версия электронных платежей
позволит проводить онлайн платежи напрямую без финансовых
институтов. Цифровая подпись — лишь часть решения вся выгода
от которого теряется из-за того, что все еще нужен доверительный
центр для того чтобы нельзя было потратить одни и те же средства
несколько раз (проблема многократного использования). Мы
предлагаем решение проблемы многократного использования с
помощью технологии децентрализованных сетей. Таким решением
является отправка транзакций (вместе с меткой времени сети) в
виде трудновычисляемых хэш-цепочек формирующих запись, которую
невозможно изменить не вычислив хэш-цепочку. Самая длинная
цепочка является самым достоверным доказательством
последовательности событий в силу того, что на ее создание
потрачено наибольшая вычислительная мощность. Поскольку
основная вычислительная мощность контролируется узлами
сети не связанными с злоумышленниками, эти узлы будут
генерировать цепочки быстрее и длиннее чем атакующие. Сама
по себе сеть требует минимальной структуры. Для лучшей
производительности, сообщения посылаются широковещательно,
узлы могут покидать сеть и опять присоединяться, принимая и
записывая при этом самые длинные хэш-цепочки сформированные
за время отсутствия узла.
1. Введение
Электронные платежи в интернете практически целиком зависят от финансовых институтов, которые являются доверенной третьей стороной для проведения платежа. Хотя система работает хорошо для большинства транзакций, она страдает от врожденного порока: модели основанной на доверии.
Полностью невозвратные платежи невозможны, поскольку финансовые институты не могут избежать споров с посредниками. Затраты связанные с посредниками увеличивают затраты на транзакции, что ведет к ограничению минимального размера транзакций и делает нецелесообразным проведение малых повседневных платежей. Кроме этого, цена увеличивается из-за невозможности проведения невозвратных платежей для сервисов, оказывающих невозвратные услуги. Возможность возврата требует наличия доверенных посредников. Продавцы вынуждены остерегаться своих покупателей, требуя от них больше информации, чем требовалось бы при наличии возможности безвозвратных платежей. Некоторый процент возвратов предполагается как неизбежность. Этих затрат и сомнений можно избежать, если покупатель использует обычные деньги, однако нет механизма проведения платежей в интернете без посредника которому доверяют.
Вот почему необходима система электронных платежей, основанная на криптографической сложности вместо доверия, позволяющая любым двум сторонам производить переводы друг другу без доверительных посредников. Транзакции, которые практически невозможно отменить защитят продавцов от мошенников, а для защиты покупателей может быть легко реализован механизм круговой поруки (routine escrow mechanisms). В данной статье мы предлагаем решение проблемы многократного использования средств с помощью распределенного сервера меток времени, генерирующего сложновычисляемые транзакции в хронологическом порядке. Система безопасна до тех пор, пока дружественные узлы одновременно контролируют большую вычислительную мощность, чем любая группа атакующих.
2. Транзакции
Цепочку цифровых подписей будем называть электронными монетами. Каждый владелец посылает монеты следующему, добавляя все в конец монеты подписанный цифровой подписью хэш предыдущей транзакции и свой открытый ключ. Получатель платежа может проверить подписи (монету), проверив цепочку владельцев.
next by digitally signing a hash of the previous transaction and the public key of the next owner
and adding these to the end of the coin. Я три дня пытался соотнести написанное с нарисованным ниже, пока не наткнулся на статью: habrahabr.ru/users/3s3s/favorites/ Только тогда я понял, что «next owner» это не «следующий владелец по отношению к текущему», а «следующий по отношению к предыдущему, то есть текущий».
Проблема конечно в том, что получатель платежа не может узнать, не потратил ли кто-то из предыдущих владельцев одни и те же средства дважды. Обычно эта проблема решается использованием доверенной централизованной организации — посредника, которая проверяет каждую транзакцию на предмет двойной траты. После каждой транзакции монета должна вернуться к посреднику который вместо старой, выпускает новую монету, тогда только монеты выпущенные посредником гарантированно не могут быть потрачены дважды.
Проблема при таком подходе в том, что судьба всей финансовой системы зависит от компании-посредника, поскольку все транзакции проходят через нее как через банк.
Итак, нужен способ благодаря которому получатель платежа будет знать, что отправители не расплатились этими же монетами с кем-то еще. В нашем случае важна лишь предыдущая история транзакций, последующие попытки двойного использования монет нас не волнуют. Единственный способ подтвердить отсутствие транзакции — это знать все транзакции. В модели с посредником, посредник знает о всех транзакциях и их последовательности. Чтобы достигнуть этого без доверенного посредника, все транзакции должны быть известны всем, т.е. нужна система участники которой будут согласны на единую историю всех платежей. Получателям платежей нужно проверять, что во время транзакции большинство участников согласны с тем, что она получена впервые.
3. Сервер меток времени
Решение, которое мы предлагаем основано на сервере меток времени. Работа сервера меток времени заключается в хэшировании блока записей, запоминании времени и публикации хэша. Метка времени служит доказательством того, что данные существовали в то время и в том порядке, в котором они поступили для хэширования. Каждая метка времени включает предыдущую метку в свой хэш формируя цепочку, в которой каждая следующая метка времени подтверждает предыдущую.
4. Сложные вычисления.
Для реализации сервера меток времени на основе децентрализованной сети нужно использовать алгоритм сложных вычислений типа Hashcash. Сложные вычисления заключаются в поиске значения, которое при хэшировании алгоритмом SHA-256, даст хэш который будет начинаться с большого количества нулевых битов. Средняя время вычислений экспоненциально растет с увеличением числа нулевых битов, а результат может быть проверен вычислением одного хэша.
Для нашего сервера меток времени мы реализуем сложные вычисления, увеличивая на единицу специальную переменную (nonce) внутри блока, пока не будет найден хэш с нужным количеством нулевых битов. Как только время, для выполнения сложных вычислений будет потрачено, блок нельзя будет изменить, не проделав вычисления еще раз. Поскольку следующие блоки образуют цепочку, то работа для изменения блока включает в себя и работу для изменения всех следующих блоков после него.
Проверяемые сложные вычисления решают также проблему получения подтверждения от большинства участников. Подтверждение, основанное на принципе «один IP-адрес — один голос», может быть дискредитировано любым, у кого под контролем находится множество IP адресов. Проверяемые вычисления это по сути «один процессор — один голос». Подтверждением от большинства является самая длинная цепочка, на создание которой было потрачено наибольшее количество вычислительных мощностей. Если основные вычислительные мощности контролируют честные участники, честная цепочка будет расти быстрее любой цепочки злонамеренных участников. Чтобы модифицировать какой-нибудь блок, атакующий должен будет проделать сложные вычисления связанные с этим блоком, а так же всеми блоками после него, нужно будет догнать и перегнать честных строителей блоков. Мы покажем далее, что у медленного атакующего, возможность догнать экспоненциально уменьшается при добавлении новых блоков.
5. Сеть
Следующие шаги описывают работу сети:
1) Новая транзакция широковещательно посылается всем узлам
2) Каждый узел помещает новые транзакции в блок
3) Каждый узел выполняет сложные вычисления для нахождения своего блока
4) Когда узел находит решение для своего блока, он широковещательно посылает этот блок всем узлам.
5) Узел принимает блок только если все транзакции в нем правильные и не просроченные.
6) Согласие узла принять блок выражается в том, что узел начинает работу над созданием следующего блока в цепочке, используя хэш принятого блока как предыдущий хэш.
Узлы всегда воспринимают самую длинную цепочку как корректную и работают над ее увеличением. Если два узла одновременно широковещательно посылают разные версии следующего блока, узлы могут принять каждую из версий в разное время. В этом случае узел начинает работать с тем блоком который был получен раньше, но другая версия должна быть сохранена на случай, если она впоследствии станет более длинной цепочкой. Ответвления можно будет игнорировать когда следующий этап вычислений будет закончен и одна из веток станет длиннее остальных; узлы, работавшие с другими ветками переключатся на самую длинную.
Широковещательная посылка новой транзакции не обязательно должна достигнуть всех узлов. Она будет включена в блок как только достигнет многих узлов. Широковещательные посылки блоков тоже могут не доходить до всех. Если узел не получил блок, он запросит его когда получит следующий блок чтобы заполнить пропущенные звенья цепи.
6. Стимул
Договоримся, что первая транзакция в блоке будет специальной транзакцией, которая начинает новую монету принадлежащую создателю блока. Это добавит стимул для узлов поддерживать сеть и обеспечит способ начального ввода монет в обращение, так как нет центрального органа для их выпуска. Постоянное добавление новых монет подобно добыче золота, когда расходуются ресурсы чтобы добавить золото в обращение. В нашем случае расходуется время процессора и электричество.
Стимул может также присутствовать при осуществлении транзакций. Если значение на выходе транзакции меньше значения на входе, эта разница добавляется к стимулирующему значению блока, содержащего транзакцию. Когда предопределенное количество монет будет выпущено, стимулирование будет производиться только через транзакции, т.е инфляции полностью исчезнет.
Стимул поощряет узлы оставаться честными. Если жадный атакующий сможет собрать большую вычислительную мощность чем все честные узлы, то он будет стоять перед выбором: обманывать людей, воруя их монеты или самому генерировать новые монеты. Он найдет для себя более выгодным играть по правилам, правилам которые позволят ему получить больше монет чем любые другие комбинации и не подрывать систему, а вместе с ней свое собственное состояние.
7. Использование дискового пространства
В то время как последние транзакции записываются в блок, отклоненные транзакции тоже занимают место на диске. Чтобы исправить это не изменяя хэши блоков, транзакции хэшируются в Дерево Меркле, где только корень включается в хэш блока. Старые блоки могут быть упакованы обрезанием веток дерева. Внутренние хэши можно не сохранять.
Заголовок блока без транзакций занимает примерно 80 байт. Если блоки генерируются каждые 10 минут, 80 байт * 6 * 24 * 365 = 4.2MB в год. В 2008 году компьютеры в основном продавались с 2ГБ оперативной памяти, а закон Мура предсказывает рост этого значения на 1.2Гб в год, следовательно дисковое пространство не должно быть проблемой, даже если заголовки блоков хранить в памяти.
8. Упрощенная проверка платежей
У узла есть возможность проверить платежи даже если нет информации о всей сети. Пользователю достаточно иметь копию заголовков блоков самой длинной цепочки, которую он может получить опрашивая узлы сети пока не решит, что получил длиннейшую цепочку. После этого пользователь получает ветку Меркле, сопоставляя транзакцию с блоком у которого такая же метка времени, как у транзакции. Он не может проверить саму транзакцию, но сопоставляя ее с местом в цепочке он может видеть, что узел принял ее, а блоки добавленные после подтверждают, что сеть приняла эту транзакцию.
Конечно, такая проверка возможна когда большинство узлов в сети являются честными, однако она уязвима если сеть контролируется атакующим. Хотя узлы сети могут проверять транзакции друг у друга, упрощенный метод может быть использован атакующими для ложных транзакций в том случае, если атакующие контролируют сеть. Одним из методов защиты против этого может быть обработка сообщений от узлов сети, когда они обнаруживают неправильный блок. Пользовательская программа, получив сообщение, может загрузить весь блок и подозрительную транзакцию чтобы проверить ее обычным способом. Для бизнеса в котором платежи приходят часто, лучшим решением будет иметь полноценный узел сети для более безопасной и быстрой проверки транзакций.
9. Комбинирование и разделение суммы
Хотя можно передавать монеты по отдельности, может оказаться слишком громоздко делать отдельную транзакцию для каждого переводимого цента. Чтобы можно было делить и комбинировать суммы, транзакции содержат множество входов и выходов. Обычно они имеют либо один вход от большой предыдущей транзакции, либо множество входов комбинирующих малые суммы, а также хотя бы два выхода: один для платежа и один для возврата сдачи, если она есть, обратно посылающему.
Нужно заметить что такой веер транзакций зависящих от нескольких транзакций, которые зависят еще от нескольких, здесь не является проблемой, потому что никогда нет необходимости восстанавливать историю всех транзакций.
10. Конфиденциальность
В традиционной банковской модели конфиденциальность достигается ограничением доступа к информации всех вовлеченных сторон. Необходимость публичного анонсирования всех транзакций исключает такой подход, однако конфиденциальность все еще может быть сохранена за счет анонимности открытых ключей. Все могут видеть, что кто-то перевел кому-то некоторую сумму, но эту информацию нельзя сопоставить с конкретной личностью. Это походит на биржевую торговлю, где время и размер сделок всем известны, но стороны сделки не разглашаются.
Как дополнительный защитный экран, для каждой транзакции должна использоваться новая пара ключей, которые нельзя сопоставить с общим владельцем. Некоторые сопоставления все таки неизбежны в транзакциях со многими входами, поскольку все входы рассматриваться как принадлежащие одному владельцу. Риск в том, что если будет выявлен владелец ключа, то можно будет узнать другие транзакции этого владельца.
11. Расчеты
Рассмотрим сценарий, когда атакующий пытается генерировать альтернативную цепочку быстрее чем честные узлы. Даже если это удастся, он не сможет делать в системе любые изменения, например создавать монеты из воздуха или брать монеты, которые ему никто не переводил. Узлы не примут неправильную транзакцию в качестве платежа, а честные узлы никогда не примут блок с неправильной транзакцией. Атакующий может лишь изменить одну из своих собственных транзакций вернув себе платеж, который он недавно осуществил.
Гонка между честной цепочкой и цепочкой атакующего может быть описана в терминах Биномиального Случайного Блуждания. Удачное событие это возрастание честной цепочки на один блок с приближением к цели на +1, неудачное событие это возрастание на один блок цепочки атакующего с уменьшением отрыва на -1.
Возможности атакующего в гонке в условиях ограничений, похоже на описание проблемы Gambler’s Ruin (Разорения Картежника). Предположим картежник с неограниченным кредитом начинает игру в условиях ограничений и может потенциально провести неограниченное число партий чтобы попытаться достигнуть безубыточности. Мы можем посчитать вероятность достижения им безубыточности или что атакующий обгонит честных строителей цепочки.
p = вероятность что честный хост найдет следующий блок
q = вероятность, что атакующий найдет следующий блок
qz = вероятность, что атакующий выиграет гонку если он отстал на z блоков
Предположим, что p>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.001
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. Заключение
Мы предложили систему электронных платежей без доверенных посредников. Она основана на принципе использования монет, состоящих из цифровых подписей, которые обеспечивают надежный контроль сами по себе, но не могут предотвратить проблему двойного использования. Решением является использование децентрализованной сети использующей сложные вычисления для записи публичной истории транзакций, которая быстро становится недоступной для модификации атакующими если честные узлы контролируют большую долю вычислительной мощности. Надежность сети в ее неструктурированности и простоте. Каждый узел работает самостоятельно с минимальной координацией. Узлам не нужно себя идентифицировать, так как сообщения идут не по конкретному маршруту, а по наиболее быстрому пути. Узлы могут покидать сеть и вновь присоединяться, принимая созданную за прошедшее время цепочку для проверки новых транзакций. Узлы голосуют своим вычислительным временем, выражая свое согласие с правильностью блоков путем присоединения их к своей цепочке для дальнейшей работы или игнорированием неправильных блоков. С таким механизмом согласия можно реализовать любые нужные правила и стимулы.
Автор: 3s3s
