Биткоин: система электронных денег на основе одноранговой сети
Abstract
순수한 peer-to-peer 방식의 전자 화폐는 금융 기관을 거치지 않고 한쪽에서 다른 쪽으로 직접 온라인 지불을 가능하게 할 것이다. 전자 서명이 해결책의 일부를 제공하지만, 이중 지불을 방지하기 위해 여전히 신뢰할 수 있는 제3자가 필요하다면 주요 이점은 사라진다. 우리는 peer-to-peer 네트워크를 이용한 이중 지불 문제의 해결책을 제안한다. 이 네트워크는 거래를 hash 기반의 proof-of-work 체인에 hash하여 타임스탬프를 부여하며, proof-of-work를 다시 수행하지 않고는 변경할 수 없는 기록을 형성한다. 가장 긴 체인은 목격된 사건의 순서에 대한 증거일 뿐만 아니라, 그것이 가장 큰 CPU 연산 능력의 풀에서 나왔다는 증거이기도 하다. CPU 연산 능력의 과반수가 네트워크를 공격하려고 협력하지 않는 노드들에 의해 통제되는 한, 그들은 가장 긴 체인을 생성하여 공격자를 앞지를 것이다. 네트워크 자체는 최소한의 구조만을 필요로 한다. 메시지는 최선 노력(best effort) 기반으로 브로드캐스트되며, 노드들은 자유롭게 네트워크를 떠났다가 다시 참여할 수 있고, 부재 중에 일어난 일의 증거로서 가장 긴 proof-of-work 체인을 수용한다.
Abstract
Полностью одноранговая версия электронных денег позволила бы отправлять онлайн-платежи напрямую от одной стороны к другой без участия финансового учреждения. Цифровые подписи обеспечивают часть решения, но основные преимущества теряются, если для предотвращения двойного расходования по-прежнему требуется доверенная третья сторона. Мы предлагаем решение проблемы двойного расходования с использованием одноранговой сети. Сеть присваивает транзакциям временные метки, хешируя их в непрерывную цепочку proof-of-work на основе хешей, формируя запись, которую невозможно изменить без повторного выполнения proof-of-work. Самая длинная цепочка служит не только доказательством последовательности наблюдавшихся событий, но и доказательством того, что она создана наибольшим пулом вычислительной мощности CPU. Пока большая часть мощности CPU контролируется узлами, не участвующими в атаке на сеть, они будут генерировать самую длинную цепочку и опережать атакующих. Сама сеть требует минимальной структуры. Сообщения рассылаются по принципу максимальных усилий, и узлы могут покидать сеть и присоединяться к ней по желанию, принимая самую длинную цепочку proof-of-work как доказательство того, что произошло в их отсутствие.
Introduction
인터넷 상의 상거래는 전자 지불을 처리하는 신뢰할 수 있는 제3자 역할을 하는 금융 기관에 거의 전적으로 의존하게 되었다. 이 시스템은 대부분의 거래에서 충분히 잘 작동하지만, 신뢰 기반 모델의 본질적인 약점으로부터 여전히 벗어나지 못한다. 금융 기관이 분쟁 중재를 피할 수 없기 때문에, 완전히 비가역적인 거래는 사실상 불가능하다. 중재 비용은 거래 비용을 증가시키며, 최소 실용적 거래 규모를 제한하고, 소규모 일상 거래의 가능성을 차단한다. 또한 비가역적 서비스에 대해 비가역적 지불을 할 수 없게 됨으로써 더 광범위한 비용이 발생한다. 취소 가능성이 존재하면 신뢰의 필요성이 확산된다. 상인은 고객을 경계해야 하며, 본래 필요하지 않을 정보까지 요구하게 된다. 일정 비율의 사기는 불가피한 것으로 받아들여진다. 이러한 비용과 지불 불확실성은 물리적 화폐를 사용하여 대면 거래에서는 피할 수 있지만, 신뢰할 수 있는 당사자 없이 통신 채널을 통해 지불하는 메커니즘은 존재하지 않는다.
필요한 것은 신뢰 대신 암호학적 증명에 기반한 전자 지불 시스템으로, 신뢰할 수 있는 제3자 없이도 두 당사자가 직접 거래할 수 있게 하는 것이다. 계산적으로 되돌리기가 실질적으로 불가능한 거래는 판매자를 사기로부터 보호하고, 일상적인 에스크로 메커니즘을 쉽게 구현하여 구매자를 보호할 수 있다. 이 논문에서 우리는 거래의 시간 순서에 대한 계산적 증명을 생성하기 위해 peer-to-peer 분산 타임스탬프 서버를 사용하는 이중 지불 문제의 해결책을 제안한다. 이 시스템은 정직한 노드들이 공격자 노드들의 어떤 협력 그룹보다 더 많은 CPU 연산 능력을 집합적으로 통제하는 한 안전하다.
Introduction
Коммерция в Интернете стала почти исключительно зависеть от финансовых учреждений, выступающих в роли доверенных третьих сторон для обработки электронных платежей. Хотя система достаточно хорошо работает для большинства транзакций, она по-прежнему страдает от врожденных слабостей модели, основанной на доверии. Полностью необратимые транзакции фактически невозможны, поскольку финансовые учреждения не могут избежать посредничества в спорах. Стоимость посредничества увеличивает транзакционные издержки, ограничивая минимальный практический размер транзакции и исключая возможность мелких повседневных транзакций, а также существует более широкая цена в виде утраты возможности осуществлять необратимые платежи за необратимые услуги. С возможностью отмены потребность в доверии распространяется. Продавцы должны с осторожностью относиться к своим клиентам, запрашивая у них больше информации, чем было бы необходимо в ином случае. Определенный процент мошенничества принимается как неизбежный. Эти издержки и неопределенности платежей можно избежать при личных расчетах с использованием физической валюты, но не существует механизма для осуществления платежей по каналу связи без доверенной стороны.
Необходима электронная платежная система, основанная на криптографическом доказательстве вместо доверия, позволяющая любым двум желающим сторонам совершать сделки напрямую друг с другом без необходимости в доверенной третьей стороне. Транзакции, которые вычислительно непрактично отменить, защитили бы продавцов от мошенничества, а обычные механизмы условного депонирования могли бы быть легко реализованы для защиты покупателей. В данной работе мы предлагаем решение проблемы двойного расходования с использованием одноранговой распределенной системы серверов временных меток для генерации вычислительного доказательства хронологического порядка транзакций. Система безопасна до тех пор, пока честные узлы совместно контролируют больше вычислительной мощности CPU, чем любая кооперирующаяся группа атакующих узлов.
Transactions
우리는 전자 화폐를 전자 서명의 체인으로 정의한다. 각 소유자는 이전 거래의 hash와 다음 소유자의 공개 키를 전자 서명하고 이를 화폐의 끝에 추가함으로써 화폐를 다음 소유자에게 전달한다. 수취인은 서명을 검증하여 소유권의 체인을 확인할 수 있다.
물론 문제는 수취인이 소유자 중 한 명이 화폐를 이중 지불하지 않았는지 검증할 수 없다는 것이다. 일반적인 해결책은 모든 거래의 이중 지불 여부를 확인하는 신뢰할 수 있는 중앙 기관, 즉 조폐국을 도입하는 것이다. 각 거래 후, 화폐는 새로운 화폐를 발행하기 위해 조폐국으로 반환되어야 하며, 조폐국에서 직접 발행된 화폐만이 이중 지불되지 않았다고 신뢰된다. 이 해결책의 문제는 전체 화폐 시스템의 운명이 조폐국을 운영하는 회사에 달려 있으며, 은행처럼 모든 거래가 그들을 거쳐야 한다는 것이다.
우리는 수취인이 이전 소유자들이 어떤 더 이른 거래에도 서명하지 않았음을 알 수 있는 방법이 필요하다. 우리의 목적상, 가장 이른 거래가 유효한 것이므로 이후의 이중 지불 시도는 신경 쓰지 않는다. 거래의 부재를 확인하는 유일한 방법은 모든 거래를 인지하는 것이다. 조폐국 기반 모델에서, 조폐국은 모든 거래를 인지하고 어떤 것이 먼저 도착했는지 결정했다. 신뢰할 수 있는 당사자 없이 이를 달성하려면, 거래는 공개적으로 발표되어야 하며[^1], 참여자들이 거래가 수신된 순서에 대한 단일한 이력에 동의하는 시스템이 필요하다. 수취인은 각 거래 시점에 노드의 과반수가 그것이 최초로 수신되었다는 데 동의했다는 증거가 필요하다.
Transactions
Мы определяем электронную монету как цепочку цифровых подписей. Каждый владелец передает монету следующему, подписывая цифровой подписью хеш предыдущей транзакции и открытый ключ следующего владельца и добавляя их в конец монеты. Получатель платежа может проверить подписи для верификации цепочки владения.
Проблема, разумеется, в том, что получатель платежа не может проверить, не потратил ли один из владельцев монету дважды. Распространенное решение заключается во введении доверенного центрального органа, или монетного двора, который проверяет каждую транзакцию на предмет двойного расходования. После каждой транзакции монета должна быть возвращена на монетный двор для выпуска новой монеты, и только монеты, выпущенные непосредственно монетным двором, считаются не потраченными дважды. Проблема этого решения в том, что судьба всей денежной системы зависит от компании, управляющей монетным двором, и каждая транзакция должна проходить через них, как через банк.
Нам нужен способ, позволяющий получателю платежа знать, что предыдущие владельцы не подписывали никаких более ранних транзакций. Для наших целей самая ранняя транзакция является определяющей, поэтому нас не беспокоят последующие попытки двойного расходования. Единственный способ подтвердить отсутствие транзакции — быть осведомленным обо всех транзакциях. В модели монетного двора монетный двор знал обо всех транзакциях и решал, какая поступила первой. Чтобы достичь этого без доверенной стороны, транзакции должны быть объявлены публично [^1], и нам нужна система, позволяющая участникам согласовать единую историю порядка, в котором они были получены. Получателю платежа нужно доказательство того, что в момент каждой транзакции большинство узлов согласились, что она была получена первой.
Timestamp Server
우리가 제안하는 해결책은 타임스탬프 서버에서 시작한다. 타임스탬프 서버는 타임스탬프를 부여할 항목 블록의 hash를 취하고, 그 hash를 신문이나 유즈넷 게시물[^2] [^3] [^4] [^5]과 같이 널리 공개하는 방식으로 작동한다. 타임스탬프는 hash에 포함되기 위해서는 당연히 그 시점에 데이터가 존재했어야 함을 증명한다. 각 타임스탬프는 자신의 hash에 이전 타임스탬프를 포함하여 체인을 형성하며, 추가되는 각 타임스탬프는 그 이전의 타임스탬프들을 강화한다.
Timestamp Server
Предлагаемое нами решение начинается с сервера временных меток. Сервер временных меток работает, беря хеш блока элементов, которым нужно присвоить временную метку, и широко публикуя этот хеш, например, в газете или посте Usenet [^2] [^3] [^4] [^5]. Временная метка доказывает, что данные, очевидно, должны были существовать в это время, чтобы попасть в хеш. Каждая временная метка включает предыдущую временную метку в свой хеш, образуя цепочку, где каждая дополнительная временная метка усиливает предыдущие.
Proof-of-Work
peer-to-peer 기반으로 분산 타임스탬프 서버를 구현하려면, 신문이나 유즈넷 게시물 대신 Adam Back의 Hashcash[^6]와 유사한 proof-of-work 시스템을 사용해야 한다. proof-of-work는 SHA-256과 같은 방식으로 hash했을 때, hash가 일정 수의 0 비트로 시작하는 값을 찾는 것을 포함한다. 필요한 평균 작업량은 요구되는 0 비트 수에 대해 지수적이며, 단일 hash 실행으로 검증할 수 있다.
우리의 타임스탬프 네트워크에서, 블록의 hash가 요구되는 0 비트를 갖는 값이 발견될 때까지 블록 내의 nonce를 증가시키는 방식으로 proof-of-work를 구현한다. CPU 노력이 proof-of-work를 충족하도록 투입되면, 그 작업을 다시 수행하지 않고는 블록을 변경할 수 없다. 이후 블록들이 그 뒤에 체인으로 연결되므로, 해당 블록을 변경하려면 그 이후의 모든 블록을 다시 수행하는 작업이 포함된다.
proof-of-work는 다수결 의사 결정에서 대표성을 결정하는 문제도 해결한다. 만약 다수결이 1-IP-주소-1-투표에 기반한다면, 다수의 IP를 할당할 수 있는 누구라도 이를 전복할 수 있다. proof-of-work는 본질적으로 1-CPU-1-투표이다. 다수결 결정은 가장 큰 proof-of-work 노력이 투입된 가장 긴 체인으로 대표된다. CPU 연산 능력의 과반수가 정직한 노드에 의해 통제되면, 정직한 체인이 가장 빠르게 성장하여 경쟁하는 어떤 체인도 앞지를 것이다. 과거 블록을 수정하려면, 공격자는 해당 블록과 그 이후 모든 블록의 proof-of-work를 다시 수행한 후 정직한 노드들의 작업을 따라잡고 능가해야 한다. 뒤처진 공격자가 따라잡을 확률이 후속 블록이 추가됨에 따라 지수적으로 감소함을 나중에 보일 것이다.
증가하는 하드웨어 속도와 시간에 따라 변동하는 노드 운영에 대한 관심을 보상하기 위해, proof-of-work 난이도는 시간당 평균 블록 수를 목표로 하는 이동 평균에 의해 결정된다. 블록이 너무 빨리 생성되면 난이도가 증가한다.
Proof-of-Work
Для реализации распределенного сервера временных меток на одноранговой основе нам потребуется использовать систему proof-of-work, аналогичную Hashcash Адама Бэка [^6], вместо газет или постов Usenet. Proof-of-work включает поиск значения, хеш которого, например при использовании SHA-256, начинается с определенного количества нулевых битов. Средний объем работы, необходимый для этого, экспоненциально зависит от количества требуемых нулевых битов и может быть проверен выполнением одного хеширования.
Для нашей сети временных меток мы реализуем proof-of-work путем увеличения nonce в блоке до тех пор, пока не будет найдено значение, дающее хешу блока требуемое количество нулевых битов. После того как затрачена вычислительная мощность CPU для удовлетворения proof-of-work, блок не может быть изменен без повторного выполнения работы. Поскольку последующие блоки связываются после него, работа по изменению блока включала бы повторное выполнение всех блоков после него.
Proof-of-work также решает проблему определения представительства при принятии решений большинством. Если бы большинство определялось по принципу один-IP-адрес-один-голос, оно могло бы быть подорвано любым, кто способен выделить множество IP-адресов. Proof-of-work — это, по сути, один-CPU-один-голос. Решение большинства представлено самой длинной цепочкой, в которую вложен наибольший объем работы proof-of-work. Если большая часть мощности CPU контролируется честными узлами, честная цепочка будет расти быстрее всех и опережать любые конкурирующие цепочки. Чтобы изменить прошлый блок, атакующему пришлось бы повторно выполнить proof-of-work этого блока и всех последующих блоков, а затем догнать и превзойти работу честных узлов. Позже мы покажем, что вероятность того, что более медленный атакующий догонит, экспоненциально уменьшается по мере добавления последующих блоков.
Для компенсации возрастающей скорости оборудования и меняющегося интереса к запуску узлов с течением времени сложность proof-of-work определяется скользящим средним, нацеленным на среднее количество блоков в час. Если они генерируются слишком быстро, сложность возрастает.
Network
네트워크를 운영하는 단계는 다음과 같다:
- 새로운 거래가 모든 노드에 브로드캐스트된다.
- 각 노드는 새로운 거래를 블록에 수집한다.
- 각 노드는 자신의 블록에 대한 어려운 proof-of-work를 찾기 위해 작업한다.
- 노드가 proof-of-work를 찾으면, 해당 블록을 모든 노드에 브로드캐스트한다.
- 노드들은 블록 내의 모든 거래가 유효하고 아직 지출되지 않은 경우에만 블록을 수락한다.
- 노드들은 수락된 블록의 hash를 이전 hash로 사용하여 체인의 다음 블록을 생성하는 작업을 함으로써 블록 수락을 표현한다.
노드들은 항상 가장 긴 체인을 올바른 것으로 간주하고 이를 연장하는 작업을 계속한다. 만약 두 노드가 다음 블록의 서로 다른 버전을 동시에 브로드캐스트하면, 일부 노드는 한쪽을, 다른 노드는 다른 쪽을 먼저 수신할 수 있다. 이 경우, 먼저 수신한 것에 대해 작업하되, 더 길어질 경우를 대비하여 다른 분기를 저장한다. 다음 proof-of-work가 발견되어 한 분기가 더 길어지면 동률은 깨지며, 다른 분기에서 작업하던 노드들은 더 긴 분기로 전환한다.
새로운 거래 브로드캐스트가 반드시 모든 노드에 도달할 필요는 없다. 많은 노드에 도달하는 한, 머지않아 블록에 포함될 것이다. 블록 브로드캐스트 역시 누락된 메시지에 대해 관대하다. 만약 노드가 블록을 수신하지 못하면, 다음 블록을 수신할 때 하나를 놓쳤음을 인지하고 해당 블록을 요청할 것이다.
Network
Шаги для работы сети следующие:
- Новые транзакции рассылаются всем узлам.
- Каждый узел собирает новые транзакции в блок.
- Каждый узел работает над поиском сложного proof-of-work для своего блока.
- Когда узел находит proof-of-work, он рассылает блок всем узлам.
- Узлы принимают блок, только если все транзакции в нем действительны и не были потрачены ранее.
- Узлы выражают свое принятие блока, работая над созданием следующего блока в цепочке, используя хеш принятого блока в качестве предыдущего хеша.
Узлы всегда считают самую длинную цепочку правильной и продолжают работать над ее удлинением. Если два узла одновременно рассылают разные версии следующего блока, некоторые узлы могут получить одну или другую первой. В этом случае они работают над той, которую получили первой, но сохраняют другую ветвь на случай, если она станет длиннее. Ничья будет разрешена, когда будет найден следующий proof-of-work и одна ветвь станет длиннее; узлы, работавшие над другой ветвью, тогда переключатся на более длинную.
Рассылка новых транзакций не обязательно должна достигать всех узлов. Пока они достигают многих узлов, они попадут в блок в скором времени. Рассылка блоков также устойчива к потере сообщений. Если узел не получает блок, он запросит его при получении следующего блока, осознав, что пропустил один.
Incentive
관례적으로, 블록의 첫 번째 거래는 블록 생성자가 소유하는 새로운 화폐를 시작하는 특별한 거래이다. 이는 노드들이 네트워크를 지원할 인센티브를 추가하며, 화폐를 발행할 중앙 기관이 없으므로 화폐를 유통에 최초로 배분하는 방법을 제공한다. 일정량의 새로운 화폐가 꾸준히 추가되는 것은 금 채굴자들이 자원을 투입하여 금을 유통에 추가하는 것과 유사하다. 우리의 경우, 투입되는 것은 CPU 시간과 전기이다.
인센티브는 거래 수수료로도 충당될 수 있다. 거래의 출력 값이 입력 값보다 작으면, 그 차이는 해당 거래를 포함하는 블록의 인센티브 값에 추가되는 거래 수수료이다. 사전에 정해진 수의 화폐가 유통에 들어가면, 인센티브는 완전히 거래 수수료로 전환될 수 있으며, 완전히 인플레이션이 없게 된다.
인센티브는 노드들이 정직하게 유지되도록 장려하는 데 도움이 될 수 있다. 탐욕스러운 공격자가 모든 정직한 노드보다 더 많은 CPU 연산 능력을 모을 수 있다면, 자신의 지불을 되돌려 훔치는 사기에 사용하거나, 새로운 화폐를 생성하는 데 사용하는 것 중에서 선택해야 한다. 그는 다른 모든 사람을 합친 것보다 더 많은 새로운 화폐를 자신에게 유리하게 하는 규칙대로 행동하는 것이, 시스템과 자신의 부의 유효성을 훼손하는 것보다 더 수익성이 높다고 판단해야 할 것이다.
Incentive
По соглашению, первая транзакция в блоке является специальной транзакцией, которая создает новую монету, принадлежащую создателю блока. Это добавляет стимул для узлов поддерживать сеть и обеспечивает способ первоначального распределения монет в обращение, поскольку нет центрального органа для их выпуска. Постоянное добавление фиксированного количества новых монет аналогично тому, как золотодобытчики тратят ресурсы для добавления золота в обращение. В нашем случае расходуется процессорное время и электроэнергия.
Стимул также может финансироваться за счет комиссий за транзакции. Если выходное значение транзакции меньше ее входного значения, разница представляет собой комиссию за транзакцию, которая добавляется к стимулирующему значению блока, содержащего транзакцию. Как только заранее определенное количество монет поступит в обращение, стимул может полностью перейти на комиссии за транзакции и быть полностью свободным от инфляции.
Стимул может помочь побудить узлы оставаться честными. Если жадный атакующий сможет собрать больше вычислительной мощности CPU, чем все честные узлы, ему придется выбирать между использованием ее для обмана людей путем возврата своих платежей или использованием ее для генерации новых монет. Ему должно быть выгоднее играть по правилам, которые дают ему больше новых монет, чем всем остальным вместе взятым, чем подрывать систему и обесценивать собственное богатство.
Reclaiming Disk Space
화폐의 최신 거래가 충분한 블록 아래에 묻히면, 그 이전의 지출된 거래들은 디스크 공간을 절약하기 위해 폐기할 수 있다. 블록의 hash를 깨뜨리지 않으면서 이를 용이하게 하기 위해, 거래들은 Merkle Tree[^7] [^2] [^5]로 hash되며, 루트만 블록의 hash에 포함된다. 오래된 블록은 트리의 가지를 잘라내어 압축할 수 있다. 내부 hash는 저장할 필요가 없다.
거래가 없는 블록 헤더는 약 80바이트이다. 블록이 10분마다 생성된다고 가정하면, 80바이트 * 6 * 24 * 365 = 연간 4.2MB이다. 2008년 기준으로 컴퓨터 시스템이 일반적으로 2GB RAM과 함께 판매되고, 무어의 법칙이 연간 1.2GB의 현재 성장률을 예측하고 있으므로, 블록 헤더가 메모리에 유지되어야 하더라도 저장 공간은 문제가 되지 않을 것이다.
Reclaiming Disk Space
Как только последняя транзакция в монете оказывается погребена под достаточным количеством блоков, потраченные транзакции до нее могут быть отброшены для экономии дискового пространства. Чтобы обеспечить это без нарушения хеша блока, транзакции хешируются в дереве Меркла (Merkle Tree) [^7] [^2] [^5], и только корень включается в хеш блока. Старые блоки затем могут быть сжаты путем отсечения ветвей дерева. Внутренние хеши не нужно хранить.
Заголовок блока без транзакций занимал бы около 80 байт. Если предположить, что блоки генерируются каждые 10 минут, 80 байт * 6 * 24 * 365 = 4,2 МБ в год. При том, что компьютерные системы обычно продавались с 2 ГБ ОЗУ по состоянию на 2008 год, а закон Мура предсказывает текущий рост в 1,2 ГБ в год, хранение не должно быть проблемой, даже если заголовки блоков необходимо хранить в памяти.
Simplified Payment Verification
전체 네트워크 노드를 운영하지 않고도 지불을 검증하는 것이 가능하다. 사용자는 가장 긴 proof-of-work 체인의 블록 헤더 사본만 유지하면 되며, 이는 가장 긴 체인을 확보했다고 확신할 때까지 네트워크 노드에 질의하여 얻을 수 있고, 거래를 타임스탬프된 블록에 연결하는 Merkle 분기를 확보하면 된다. 거래를 직접 확인할 수는 없지만, 체인의 한 위치에 연결함으로써 네트워크 노드가 이를 수락했음을 알 수 있고, 그 이후에 추가된 블록들은 네트워크가 이를 수락했음을 추가로 확인해 준다.
이와 같이, 정직한 노드들이 네트워크를 통제하는 한 검증은 신뢰할 수 있지만, 네트워크가 공격자에 의해 압도되면 더 취약해진다. 네트워크 노드가 거래를 스스로 검증할 수 있는 반면, 간소화된 방법은 공격자가 네트워크를 계속 압도할 수 있는 한 공격자의 조작된 거래에 속을 수 있다. 이에 대한 한 가지 보호 전략은 네트워크 노드가 유효하지 않은 블록을 감지했을 때 경고를 수락하여, 사용자의 소프트웨어가 전체 블록과 경고된 거래를 다운로드하여 불일치를 확인하도록 하는 것이다. 빈번한 지불을 수신하는 사업체는 보다 독립적인 보안과 빠른 검증을 위해 자체 노드를 운영하기를 원할 것이다.
Simplified Payment Verification
Можно проверять платежи, не запуская полный сетевой узел. Пользователю нужно лишь хранить копию заголовков блоков самой длинной цепочки proof-of-work, которую он может получить, опрашивая сетевые узлы, пока не убедится, что имеет самую длинную цепочку, и получить ветвь Меркла, связывающую транзакцию с блоком, в котором она получила временную метку. Он не может проверить транзакцию самостоятельно, но, связав ее с местом в цепочке, он может увидеть, что сетевой узел принял ее, и блоки, добавленные после нее, дополнительно подтверждают, что сеть ее приняла.
Таким образом, проверка надежна, пока честные узлы контролируют сеть, но более уязвима, если сеть захвачена атакующим. В то время как сетевые узлы могут самостоятельно проверять транзакции, упрощенный метод может быть обманут сфабрикованными транзакциями атакующего, пока тот может продолжать доминировать в сети. Одной из стратегий защиты от этого было бы принятие предупреждений от сетевых узлов при обнаружении ими недействительного блока, побуждающих программное обеспечение пользователя загрузить полный блок и отмеченные транзакции для подтверждения несоответствия. Предприятия, получающие частые платежи, вероятно, по-прежнему захотят запускать собственные узлы для более независимой безопасности и более быстрой проверки.
Combining and Splitting Value
화폐를 개별적으로 다루는 것이 가능하겠지만, 이체에서 매 센트마다 별도의 거래를 만드는 것은 다루기 어려울 것이다. 가치의 분할과 결합을 허용하기 위해, 거래는 다수의 입력과 출력을 포함한다. 일반적으로 더 큰 이전 거래로부터의 단일 입력 또는 더 작은 금액을 결합하는 다수의 입력이 있으며, 최대 두 개의 출력이 있다: 하나는 지불을 위한 것이고, 하나는 잔돈이 있는 경우 발신자에게 돌려주는 것이다.
하나의 거래가 여러 거래에 의존하고, 그 거래들이 다시 더 많은 거래에 의존하는 팬아웃(fan-out)은 여기서 문제가 되지 않음에 유의해야 한다. 거래 이력의 완전한 독립 사본을 추출할 필요는 결코 없다.
Combining and Splitting Value
Хотя было бы возможно обрабатывать монеты по отдельности, было бы неудобно создавать отдельную транзакцию для каждого цента при переводе. Чтобы позволить разделение и объединение стоимости, транзакции содержат несколько входов и выходов. Обычно будет либо один вход от более крупной предыдущей транзакции, либо несколько входов, объединяющих меньшие суммы, и не более двух выходов: один для платежа и один для возврата сдачи, если таковая имеется, отправителю.
Следует отметить, что разветвление (fan-out), когда транзакция зависит от нескольких транзакций, а те, в свою очередь, зависят от еще большего числа, здесь не является проблемой. Никогда нет необходимости извлекать полную самостоятельную копию истории транзакции.
Privacy
전통적인 은행 모델은 관련 당사자와 신뢰할 수 있는 제3자에게만 정보 접근을 제한함으로써 일정 수준의 개인정보 보호를 달성한다. 모든 거래를 공개적으로 발표해야 하는 필요성은 이 방법을 배제하지만, 정보의 흐름을 다른 곳에서 끊음으로써 개인정보 보호는 여전히 유지될 수 있다: 공개 키를 익명으로 유지하는 것이다. 대중은 누군가가 다른 누군가에게 금액을 보내고 있음을 볼 수 있지만, 거래를 누구에게도 연결하는 정보가 없다. 이는 증권 거래소가 공개하는 정보 수준과 유사하며, 개별 거래의 시간과 규모, 즉 "시세 테이프"는 공개되지만 당사자가 누구인지는 알리지 않는다.
추가적인 방화벽으로, 각 거래마다 새로운 키 쌍을 사용하여 공통 소유자에게 연결되는 것을 방지해야 한다. 다중 입력 거래에서는 일부 연결이 여전히 불가피한데, 이는 그 입력들이 동일한 소유자의 것이었음을 필연적으로 드러내기 때문이다. 위험은 키의 소유자가 밝혀지면 연결을 통해 동일한 소유자에게 속한 다른 거래들이 드러날 수 있다는 것이다.
Privacy
Традиционная банковская модель обеспечивает определенный уровень конфиденциальности, ограничивая доступ к информации вовлеченными сторонами и доверенной третьей стороной. Необходимость публично объявлять все транзакции исключает этот метод, но конфиденциальность все еще может быть сохранена путем прерывания потока информации в другом месте: путем сохранения анонимности открытых ключей. Общественность может видеть, что кто-то отправляет сумму кому-то другому, но без информации, связывающей транзакцию с кем-либо. Это аналогично уровню информации, публикуемой фондовыми биржами, где время и объем отдельных сделок, «лента», делаются публичными, но без указания того, кем были стороны.
В качестве дополнительного барьера для каждой транзакции следует использовать новую пару ключей, чтобы предотвратить их привязку к общему владельцу. Некоторая связь по-прежнему неизбежна при транзакциях с несколькими входами, которые неизбежно раскрывают, что их входы принадлежали одному владельцу. Риск состоит в том, что если владелец ключа будет раскрыт, связывание может раскрыть другие транзакции, принадлежавшие тому же владельцу.
Calculations
우리는 공격자가 정직한 체인보다 더 빠르게 대안 체인을 생성하려고 시도하는 시나리오를 고려한다. 이것이 달성되더라도, 무에서 가치를 만들거나 공격자에게 속하지 않은 돈을 빼앗는 것과 같은 임의적인 변경에 시스템을 개방하지는 않는다. 노드들은 유효하지 않은 거래를 지불로 수락하지 않을 것이며, 정직한 노드들은 그러한 거래를 포함하는 블록을 절대 수락하지 않을 것이다. 공격자는 오직 자신의 거래 중 하나를 변경하여 최근에 지출한 돈을 되돌리려고 시도할 수 있을 뿐이다.
정직한 체인과 공격자 체인 간의 경쟁은 이항 랜덤 워크(Binomial Random Walk)로 특성화할 수 있다. 성공 사건은 정직한 체인이 한 블록 연장되어 리드를 +1만큼 증가시키는 것이고, 실패 사건은 공격자의 체인이 한 블록 연장되어 격차를 -1만큼 줄이는 것이다.
주어진 격차에서 공격자가 따라잡을 확률은 도박사의 파산 문제(Gambler's Ruin problem)에 비유된다. 무한한 신용을 가진 도박사가 적자에서 시작하여 손익분기점에 도달하기 위해 잠재적으로 무한한 횟수의 시도를 한다고 가정하자. 그가 손익분기점에 도달하는 확률, 또는 공격자가 정직한 체인을 따라잡는 확률은 다음과 같이 계산할 수 있다[^8]:
p = probability an honest node finds the next block
q = probability the attacker finds the next block
q = probability the attacker will ever catch up from z blocks behind
``````
\[
qz =
\begin{cases}
1 & \text{if } p \leq q \\
\left(\frac{q}{p}\right) z & \text{if } p > q
\end{cases}
\]
p q라는 가정하에, 공격자가 따라잡아야 하는 블록 수가 증가함에 따라 확률은 지수적으로 감소한다. 불리한 상황에서, 초반에 운 좋게 앞서 나가지 못하면, 뒤처질수록 그의 가능성은 극히 작아진다.
이제 새로운 거래의 수신자가 발신자가 거래를 변경할 수 없다고 충분히 확신하기 전에 얼마나 기다려야 하는지 고려한다. 발신자는 수신자에게 자신이 지불했다고 한동안 믿게 만든 후, 일정 시간이 지난 후 자신에게 되돌려 지불하도록 전환하려는 공격자라고 가정한다. 그런 일이 발생하면 수신자에게 경고가 가지만, 발신자는 그때쯤이면 너무 늦기를 바란다.
수신자는 새로운 키 쌍을 생성하고 서명 직전에 발신자에게 공개 키를 제공한다. 이는 발신자가 충분히 앞서 나갈 만큼 운이 좋을 때까지 블록 체인을 미리 연속적으로 작업하여 준비한 후 그 시점에 거래를 실행하는 것을 방지한다. 거래가 전송되면, 부정직한 발신자는 자신의 거래의 대안 버전을 포함하는 병렬 체인을 비밀리에 작업하기 시작한다.
수신자는 거래가 블록에 추가되고 z개의 블록이 그 뒤에 연결될 때까지 기다린다. 공격자가 이룬 정확한 진행 정도를 알 수 없지만, 정직한 블록이 블록당 평균 예상 시간이 걸렸다고 가정하면, 공격자의 잠재적 진행은 기대값이 다음과 같은 포아송 분포가 될 것이다:
\[
\lambda = z\frac{q}{p}
\]
공격자가 지금이라도 따라잡을 수 있는 확률을 구하기 위해, 그가 이룰 수 있었던 각 진행 정도에 대한 포아송 밀도에 그 지점에서 따라잡을 수 있는 확률을 곱한다:
\[
\sum_{k=0}^{\infty} \frac{\lambda^k e^{-\lambda}}{k!} \cdot \left\{
\begin{array}{cl}
\left(\frac{q}{p}\right)^{(z-k)} & \text{if } k \leq z \\
1 & \text{if } k > z
\end{array}
\right.
\]
분포의 무한 꼬리를 합산하는 것을 피하기 위해 재배열하면...
\[
1 - \sum_{k=0}^{z} \frac{\lambda^k e^{-\lambda}}{k!} \left(1-\left(\frac{q}{p}\right)^{(z-k)}\right)
\]
C 코드로 변환하면...
```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
Calculations
Рассмотрим сценарий, в котором атакующий пытается сгенерировать альтернативную цепочку быстрее, чем честная цепочка. Даже если это удастся, это не открывает систему для произвольных изменений, таких как создание стоимости из ничего или присвоение денег, которые никогда не принадлежали атакующему. Узлы не примут недействительную транзакцию в качестве платежа, и честные узлы никогда не примут блок, содержащий такие транзакции. Атакующий может лишь попытаться изменить одну из своих собственных транзакций, чтобы вернуть деньги, которые он недавно потратил.
Гонку между честной цепочкой и цепочкой атакующего можно охарактеризовать как биномиальное случайное блуждание. Событие успеха — это удлинение честной цепочки на один блок, увеличивающее ее отрыв на +1, а событие неудачи — это удлинение цепочки атакующего на один блок, сокращающее разрыв на -1.
Вероятность того, что атакующий наверстает упущенное с заданного отставания, аналогична задаче о разорении игрока. Предположим, что игрок с неограниченным кредитом начинает с дефицита и играет потенциально бесконечное число раундов, пытаясь выйти в ноль. Мы можем рассчитать вероятность того, что он когда-либо выйдет в ноль, или что атакующий когда-либо догонит честную цепочку, следующим образом [^8]:
p = вероятность того, что честный узел найдет следующий блок
q = вероятность того, что атакующий найдет следующий блок
q = вероятность того, что атакующий когда-либо догонит, отставая на z блоков
\[ qz = \begin{cases} 1 & \text{если } p \leq q \\ \left(\frac{q}{p}\right) z & \text{если } p > q \end{cases} \]
Учитывая наше предположение, что p q, вероятность экспоненциально падает с увеличением числа блоков, которые атакующему нужно наверстать. При неблагоприятных шансах, если он не сделает удачный рывок в самом начале, его шансы становятся исчезающе малыми по мере дальнейшего отставания.
Теперь рассмотрим, как долго получатель новой транзакции должен ждать, прежде чем быть достаточно уверенным, что отправитель не может изменить транзакцию. Мы предполагаем, что отправитель — атакующий, который хочет заставить получателя поверить, что он заплатил ему, на некоторое время, а затем переключить платеж на себя после истечения некоторого времени. Получатель будет предупрежден, когда это произойдет, но отправитель надеется, что будет слишком поздно.
Получатель генерирует новую пару ключей и передает открытый ключ отправителю незадолго до подписания. Это предотвращает подготовку отправителем цепочки блоков заранее путем непрерывной работы над ней, пока ему не посчастливится достаточно продвинуться вперед, а затем выполнить транзакцию в этот момент. После отправки транзакции нечестный отправитель начинает тайно работать над параллельной цепочкой, содержащей альтернативную версию его транзакции.
Получатель ждет, пока транзакция не будет добавлена в блок и z блоков не будут связаны после него. Он не знает точный объем прогресса атакующего, но предполагая, что честные блоки создавались за среднее ожидаемое время на блок, потенциальный прогресс атакующего будет иметь распределение Пуассона с математическим ожиданием:
\[ \lambda = z\frac{q}{p} \]
Чтобы получить вероятность того, что атакующий все еще может догнать, мы умножаем плотность Пуассона для каждого объема прогресса, который он мог сделать, на вероятность того, что он сможет догнать с этой точки:
\[ \sum_{k=0}^{\infty} \frac{\lambda^k e^{-\lambda}}{k!} \cdot \left\{ \begin{array}{cl} \left(\frac{q}{p}\right)^{(z-k)} & \text{если } k \leq z \\ 1 & \text{если } k > z \end{array} \right. \]
Преобразуя, чтобы избежать суммирования бесконечного хвоста распределения...
\[ 1 - \sum_{k=0}^{z} \frac{\lambda^k e^{-\lambda}}{k!} \left(1-\left(\frac{q}{p}\right)^{(z-k)}\right) \]
Преобразуя в код на 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
Conclusion
우리는 신뢰에 의존하지 않는 전자 거래 시스템을 제안했다. 전자 서명으로 만들어진 화폐의 일반적인 프레임워크에서 출발했는데, 이는 소유권의 강력한 통제를 제공하지만 이중 지불을 방지할 방법 없이는 불완전하다. 이를 해결하기 위해, 거래의 공개 이력을 기록하는 proof-of-work를 사용하는 peer-to-peer 네트워크를 제안했으며, 정직한 노드가 CPU 연산 능력의 과반수를 통제하는 한 공격자가 변경하는 것이 계산적으로 빠르게 실질적으로 불가능해진다. 네트워크는 비구조적 단순성에서 강건하다. 노드들은 거의 조율 없이 모두 동시에 작업한다. 메시지가 특정 장소로 라우팅되지 않고 최선 노력(best effort) 기반으로만 전달되면 되므로, 노드를 식별할 필요가 없다. 노드들은 자유롭게 네트워크를 떠났다가 다시 참여할 수 있으며, 부재 중에 일어난 일의 증거로서 proof-of-work 체인을 수용한다. 그들은 CPU 연산 능력으로 투표하며, 유효한 블록을 연장하는 작업을 통해 수락을 표현하고, 유효하지 않은 블록에 대한 작업을 거부함으로써 이를 거부한다. 필요한 규칙과 인센티브는 이 합의 메커니즘으로 시행될 수 있다.
Conclusion
Мы предложили систему электронных транзакций, не основанную на доверии. Мы начали с обычной структуры монет, созданных из цифровых подписей, которая обеспечивает надежный контроль над собственностью, но является неполной без способа предотвращения двойного расходования. Для решения этой проблемы мы предложили одноранговую сеть, использующую proof-of-work для записи публичной истории транзакций, которую быстро становится вычислительно непрактично изменить для атакующего, если честные узлы контролируют большую часть мощности CPU. Сеть устойчива в своей неструктурированной простоте. Узлы работают одновременно с минимальной координацией. Их не нужно идентифицировать, поскольку сообщения не направляются в какое-либо конкретное место и должны быть доставлены лишь по принципу максимальных усилий. Узлы могут покидать сеть и присоединяться к ней по желанию, принимая цепочку proof-of-work как доказательство того, что произошло в их отсутствие. Они голосуют своей вычислительной мощностью CPU, выражая принятие действительных блоков работой над их продлением и отклоняя недействительные блоки отказом работать над ними. Любые необходимые правила и стимулы могут быть реализованы с помощью этого механизма консенсуса.
References
-
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.
-
S. Haber, W.S. Stornetta, "How to time-stamp a digital document," In Journal of Cryptology, vol 3, no 2, pages 99-111, 1991.
-
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.
-
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.
-
A. Back, "Hashcash - a denial of service counter-measure," http://www.hashcash.org/papers/hashcash.pdf, 2002.
-
R.C. Merkle, "Protocols for public key cryptosystems," In Proc. 1980 Symposium on Security and Privacy, IEEE Computer Society, pages 122-133, April 1980.
-
W. Feller, "An introduction to probability theory and its applications," 1957.
References
-
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.
-
S. Haber, W.S. Stornetta, "How to time-stamp a digital document," In Journal of Cryptology, vol 3, no 2, pages 99-111, 1991.
-
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.
-
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.
-
A. Back, "Hashcash - a denial of service counter-measure," http://www.hashcash.org/papers/hashcash.pdf, 2002.
-
R.C. Merkle, "Protocols for public key cryptosystems," In Proc. 1980 Symposium on Security and Privacy, IEEE Computer Society, pages 122-133, April 1980.
-
W. Feller, "An introduction to probability theory and its applications," 1957.
