Биткоин: система электронных денег на основе одноранговой сети
Abstract
Une version purement pair-a-pair de monnaie electronique permettrait d'envoyer des paiements en ligne directement d'une partie a une autre sans passer par une institution financiere. Les signatures numeriques fournissent une partie de la solution, mais les principaux avantages sont perdus si un tiers de confiance est toujours necessaire pour empecher la double depense. Nous proposons une solution au probleme de la double depense en utilisant un reseau pair-a-pair. Le reseau horodate les transactions en les hachant dans une chaine continue de proof-of-work basee sur le hachage, formant un enregistrement qui ne peut etre modifie sans refaire le proof-of-work. La chaine la plus longue sert non seulement de preuve de la sequence des evenements observes, mais aussi de preuve qu'elle provient du plus grand pool de puissance CPU. Tant qu'une majorite de la puissance CPU est controlee par des noeuds qui ne cooperent pas pour attaquer le reseau, ils genereront la chaine la plus longue et devanceront les attaquants. Le reseau lui-meme necessite une structure minimale. Les messages sont diffuses au mieux, et les noeuds peuvent quitter et rejoindre le reseau a volonte, acceptant la chaine de proof-of-work la plus longue comme preuve de ce qui s'est passe pendant leur absence.
Abstract
Полностью одноранговая версия электронных денег позволила бы отправлять онлайн-платежи напрямую от одной стороны к другой без участия финансового учреждения. Цифровые подписи обеспечивают часть решения, но основные преимущества теряются, если для предотвращения двойного расходования по-прежнему требуется доверенная третья сторона. Мы предлагаем решение проблемы двойного расходования с использованием одноранговой сети. Сеть присваивает транзакциям временные метки, хешируя их в непрерывную цепочку proof-of-work на основе хешей, формируя запись, которую невозможно изменить без повторного выполнения proof-of-work. Самая длинная цепочка служит не только доказательством последовательности наблюдавшихся событий, но и доказательством того, что она создана наибольшим пулом вычислительной мощности CPU. Пока большая часть мощности CPU контролируется узлами, не участвующими в атаке на сеть, они будут генерировать самую длинную цепочку и опережать атакующих. Сама сеть требует минимальной структуры. Сообщения рассылаются по принципу максимальных усилий, и узлы могут покидать сеть и присоединяться к ней по желанию, принимая самую длинную цепочку proof-of-work как доказательство того, что произошло в их отсутствие.
Introduction
Le commerce sur Internet en est venu a reposer presque exclusivement sur des institutions financieres servant de tiers de confiance pour traiter les paiements electroniques. Bien que le systeme fonctionne assez bien pour la plupart des transactions, il souffre encore des faiblesses inherentes au modele base sur la confiance. Les transactions completement irreversibles ne sont pas vraiment possibles, puisque les institutions financieres ne peuvent eviter de medier les litiges. Le cout de la mediation augmente les couts de transaction, limitant la taille minimale pratique des transactions et eliminant la possibilite de petites transactions occasionnelles, et il y a un cout plus large dans la perte de la capacite a effectuer des paiements irreversibles pour des services irreversibles. Avec la possibilite d'inversion, le besoin de confiance se repand. Les commercants doivent se mefier de leurs clients, les harcelant pour obtenir plus d'informations qu'ils n'en auraient autrement besoin. Un certain pourcentage de fraude est accepte comme inevitable. Ces couts et incertitudes de paiement peuvent etre evites en personne en utilisant de la monnaie physique, mais aucun mecanisme n'existe pour effectuer des paiements sur un canal de communication sans un tiers de confiance.
Ce qui est necessaire est un systeme de paiement electronique base sur la preuve cryptographique plutot que sur la confiance, permettant a deux parties consentantes de transiger directement l'une avec l'autre sans besoin d'un tiers de confiance. Les transactions qu'il est informatiquement impraticable d'inverser protegeraient les vendeurs contre la fraude, et des mecanismes d'entiercement routiniers pourraient etre facilement mis en oeuvre pour proteger les acheteurs. Dans cet article, nous proposons une solution au probleme de la double depense en utilisant un serveur d'horodatage distribue pair-a-pair pour generer une preuve informatique de l'ordre chronologique des transactions. Le systeme est securise tant que les noeuds honnetes controlent collectivement plus de puissance CPU que tout groupe cooperant de noeuds attaquants.
Introduction
Коммерция в Интернете стала почти исключительно зависеть от финансовых учреждений, выступающих в роли доверенных третьих сторон для обработки электронных платежей. Хотя система достаточно хорошо работает для большинства транзакций, она по-прежнему страдает от врожденных слабостей модели, основанной на доверии. Полностью необратимые транзакции фактически невозможны, поскольку финансовые учреждения не могут избежать посредничества в спорах. Стоимость посредничества увеличивает транзакционные издержки, ограничивая минимальный практический размер транзакции и исключая возможность мелких повседневных транзакций, а также существует более широкая цена в виде утраты возможности осуществлять необратимые платежи за необратимые услуги. С возможностью отмены потребность в доверии распространяется. Продавцы должны с осторожностью относиться к своим клиентам, запрашивая у них больше информации, чем было бы необходимо в ином случае. Определенный процент мошенничества принимается как неизбежный. Эти издержки и неопределенности платежей можно избежать при личных расчетах с использованием физической валюты, но не существует механизма для осуществления платежей по каналу связи без доверенной стороны.
Необходима электронная платежная система, основанная на криптографическом доказательстве вместо доверия, позволяющая любым двум желающим сторонам совершать сделки напрямую друг с другом без необходимости в доверенной третьей стороне. Транзакции, которые вычислительно непрактично отменить, защитили бы продавцов от мошенничества, а обычные механизмы условного депонирования могли бы быть легко реализованы для защиты покупателей. В данной работе мы предлагаем решение проблемы двойного расходования с использованием одноранговой распределенной системы серверов временных меток для генерации вычислительного доказательства хронологического порядка транзакций. Система безопасна до тех пор, пока честные узлы совместно контролируют больше вычислительной мощности CPU, чем любая кооперирующаяся группа атакующих узлов.
Transactions
Nous definissons une piece electronique comme une chaine de signatures numeriques. Chaque proprietaire transfere la piece au suivant en signant numeriquement un hash de la transaction precedente et la cle publique du proprietaire suivant, et en ajoutant ceux-ci a la fin de la piece. Un beneficiaire peut verifier les signatures pour verifier la chaine de propriete.
Le probleme bien sur est que le beneficiaire ne peut pas verifier qu'un des proprietaires n'a pas double-depense la piece. Une solution courante est d'introduire une autorite centrale de confiance, ou un atelier monetaire, qui verifie chaque transaction pour la double depense. Apres chaque transaction, la piece doit etre retournee a l'atelier monetaire pour emettre une nouvelle piece, et seules les pieces emises directement par l'atelier monetaire sont considerees comme non double-depensees. Le probleme avec cette solution est que le destin de l'ensemble du systeme monetaire depend de l'entreprise qui gere l'atelier monetaire, chaque transaction devant passer par eux, tout comme une banque.
Nous avons besoin d'un moyen pour le beneficiaire de savoir que les proprietaires precedents n'ont pas signe de transactions anterieures. Pour nos besoins, la transaction la plus ancienne est celle qui compte, donc nous ne nous soucions pas des tentatives ulterieures de double depense. La seule facon de confirmer l'absence d'une transaction est d'etre au courant de toutes les transactions. Dans le modele base sur l'atelier monetaire, l'atelier monetaire etait au courant de toutes les transactions et decidait laquelle etait arrivee en premier. Pour accomplir cela sans un tiers de confiance, les transactions doivent etre publiquement annoncees [^1], et nous avons besoin d'un systeme pour que les participants s'accordent sur un historique unique de l'ordre dans lequel elles ont ete recues. Le beneficiaire a besoin de la preuve qu'au moment de chaque transaction, la majorite des noeuds a convenu qu'elle etait la premiere recue.
Transactions
Мы определяем электронную монету как цепочку цифровых подписей. Каждый владелец передает монету следующему, подписывая цифровой подписью хеш предыдущей транзакции и открытый ключ следующего владельца и добавляя их в конец монеты. Получатель платежа может проверить подписи для верификации цепочки владения.
Проблема, разумеется, в том, что получатель платежа не может проверить, не потратил ли один из владельцев монету дважды. Распространенное решение заключается во введении доверенного центрального органа, или монетного двора, который проверяет каждую транзакцию на предмет двойного расходования. После каждой транзакции монета должна быть возвращена на монетный двор для выпуска новой монеты, и только монеты, выпущенные непосредственно монетным двором, считаются не потраченными дважды. Проблема этого решения в том, что судьба всей денежной системы зависит от компании, управляющей монетным двором, и каждая транзакция должна проходить через них, как через банк.
Нам нужен способ, позволяющий получателю платежа знать, что предыдущие владельцы не подписывали никаких более ранних транзакций. Для наших целей самая ранняя транзакция является определяющей, поэтому нас не беспокоят последующие попытки двойного расходования. Единственный способ подтвердить отсутствие транзакции — быть осведомленным обо всех транзакциях. В модели монетного двора монетный двор знал обо всех транзакциях и решал, какая поступила первой. Чтобы достичь этого без доверенной стороны, транзакции должны быть объявлены публично [^1], и нам нужна система, позволяющая участникам согласовать единую историю порядка, в котором они были получены. Получателю платежа нужно доказательство того, что в момент каждой транзакции большинство узлов согласились, что она была получена первой.
Timestamp Server
La solution que nous proposons commence par un serveur d'horodatage. Un serveur d'horodatage fonctionne en prenant un hash d'un bloc d'elements a horodater et en publiant largement le hash, comme dans un journal ou un message Usenet [^2] [^3] [^4] [^5]. L'horodatage prouve que les donnees devaient exister a ce moment-la, evidemment, pour etre incluses dans le hash. Chaque horodatage inclut l'horodatage precedent dans son hash, formant une chaine, chaque horodatage supplementaire renforcant les precedents.
Timestamp Server
Предлагаемое нами решение начинается с сервера временных меток. Сервер временных меток работает, беря хеш блока элементов, которым нужно присвоить временную метку, и широко публикуя этот хеш, например, в газете или посте Usenet [^2] [^3] [^4] [^5]. Временная метка доказывает, что данные, очевидно, должны были существовать в это время, чтобы попасть в хеш. Каждая временная метка включает предыдущую временную метку в свой хеш, образуя цепочку, где каждая дополнительная временная метка усиливает предыдущие.
Proof-of-Work
Pour implementer un serveur d'horodatage distribue sur une base pair-a-pair, nous devrons utiliser un systeme de proof-of-work similaire au Hashcash d'Adam Back [^6], plutot que des journaux ou des messages Usenet. Le proof-of-work consiste a rechercher une valeur qui, lorsqu'elle est hachee, par exemple avec SHA-256, le hash commence par un certain nombre de bits zero. Le travail moyen requis est exponentiel par rapport au nombre de bits zero requis et peut etre verifie en executant un seul hash.
Pour notre reseau d'horodatage, nous implementons le proof-of-work en incrementant un nonce dans le bloc jusqu'a ce qu'une valeur soit trouvee qui donne au hash du bloc les bits zero requis. Une fois que l'effort CPU a ete depense pour satisfaire le proof-of-work, le bloc ne peut pas etre modifie sans refaire le travail. Comme les blocs ulterieurs sont chaines apres lui, le travail pour modifier le bloc inclurait de refaire tous les blocs apres lui.
Le proof-of-work resout egalement le probleme de la determination de la representation dans la prise de decision majoritaire. Si la majorite etait basee sur une-adresse-IP-un-vote, elle pourrait etre corrompue par quiconque capable d'allouer de nombreuses adresses IP. Le proof-of-work est essentiellement un-CPU-un-vote. La decision majoritaire est representee par la chaine la plus longue, qui a le plus grand effort de proof-of-work investi. Si une majorite de la puissance CPU est controlee par des noeuds honnetes, la chaine honnete croitra le plus rapidement et devancera toutes les chaines concurrentes. Pour modifier un bloc passe, un attaquant devrait refaire le proof-of-work du bloc et de tous les blocs apres lui, puis rattraper et depasser le travail des noeuds honnetes. Nous montrerons plus tard que la probabilite qu'un attaquant plus lent rattrape diminue exponentiellement a mesure que des blocs subsequents sont ajoutes.
Pour compenser la vitesse croissante du materiel et l'interet variable pour l'exploitation des noeuds au fil du temps, la difficulte du proof-of-work est determinee par une moyenne mobile visant un nombre moyen de blocs par heure. S'ils sont generes trop rapidement, la difficulte augmente.
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
Les etapes pour faire fonctionner le reseau sont les suivantes :
- Les nouvelles transactions sont diffusees a tous les noeuds.
- Chaque noeud collecte les nouvelles transactions dans un bloc.
- Chaque noeud travaille a trouver un proof-of-work difficile pour son bloc.
- Lorsqu'un noeud trouve un proof-of-work, il diffuse le bloc a tous les noeuds.
- Les noeuds acceptent le bloc uniquement si toutes les transactions qu'il contient sont valides et n'ont pas deja ete depensees.
- Les noeuds expriment leur acceptation du bloc en travaillant a la creation du bloc suivant dans la chaine, en utilisant le hash du bloc accepte comme hash precedent.
Les noeuds considerent toujours la chaine la plus longue comme etant la correcte et continueront a travailler a son extension. Si deux noeuds diffusent des versions differentes du bloc suivant simultanement, certains noeuds peuvent recevoir l'une ou l'autre en premier. Dans ce cas, ils travaillent sur la premiere qu'ils ont recue, mais conservent l'autre branche au cas ou elle deviendrait plus longue. L'egalite sera brisee lorsque le prochain proof-of-work sera trouve et qu'une branche deviendra plus longue ; les noeuds qui travaillaient sur l'autre branche basculeront alors sur la plus longue.
Les diffusions de nouvelles transactions n'ont pas necessairement besoin d'atteindre tous les noeuds. Tant qu'elles atteignent de nombreux noeuds, elles seront integrees dans un bloc sous peu. Les diffusions de blocs sont egalement tolerantes aux messages perdus. Si un noeud ne recoit pas un bloc, il le demandera lorsqu'il recevra le bloc suivant et realisera qu'il en a manque un.
Network
Шаги для работы сети следующие:
- Новые транзакции рассылаются всем узлам.
- Каждый узел собирает новые транзакции в блок.
- Каждый узел работает над поиском сложного proof-of-work для своего блока.
- Когда узел находит proof-of-work, он рассылает блок всем узлам.
- Узлы принимают блок, только если все транзакции в нем действительны и не были потрачены ранее.
- Узлы выражают свое принятие блока, работая над созданием следующего блока в цепочке, используя хеш принятого блока в качестве предыдущего хеша.
Узлы всегда считают самую длинную цепочку правильной и продолжают работать над ее удлинением. Если два узла одновременно рассылают разные версии следующего блока, некоторые узлы могут получить одну или другую первой. В этом случае они работают над той, которую получили первой, но сохраняют другую ветвь на случай, если она станет длиннее. Ничья будет разрешена, когда будет найден следующий proof-of-work и одна ветвь станет длиннее; узлы, работавшие над другой ветвью, тогда переключатся на более длинную.
Рассылка новых транзакций не обязательно должна достигать всех узлов. Пока они достигают многих узлов, они попадут в блок в скором времени. Рассылка блоков также устойчива к потере сообщений. Если узел не получает блок, он запросит его при получении следующего блока, осознав, что пропустил один.
Incentive
Par convention, la premiere transaction d'un bloc est une transaction speciale qui cree une nouvelle piece appartenant au createur du bloc. Cela ajoute une incitation pour les noeuds a soutenir le reseau et fournit un moyen de distribuer initialement les pieces en circulation, puisqu'il n'y a pas d'autorite centrale pour les emettre. L'ajout regulier d'une quantite constante de nouvelles pieces est analogue aux mineurs d'or qui depensent des ressources pour ajouter de l'or en circulation. Dans notre cas, ce sont le temps CPU et l'electricite qui sont depenses.
L'incitation peut aussi etre financee par les frais de transaction. Si la valeur de sortie d'une transaction est inferieure a sa valeur d'entree, la difference est un frais de transaction qui s'ajoute a la valeur d'incitation du bloc contenant la transaction. Une fois qu'un nombre predetermine de pieces est entre en circulation, l'incitation peut passer entierement aux frais de transaction et etre completement exempte d'inflation.
L'incitation peut aider a encourager les noeuds a rester honnetes. Si un attaquant cupide est capable de rassembler plus de puissance CPU que tous les noeuds honnetes, il devrait choisir entre l'utiliser pour escroquer les gens en volant ses paiements, ou l'utiliser pour generer de nouvelles pieces. Il devrait trouver plus profitable de jouer selon les regles, des regles qui le favorisent avec plus de nouvelles pieces que tous les autres combines, plutot que de saper le systeme et la validite de sa propre richesse.
Incentive
По соглашению, первая транзакция в блоке является специальной транзакцией, которая создает новую монету, принадлежащую создателю блока. Это добавляет стимул для узлов поддерживать сеть и обеспечивает способ первоначального распределения монет в обращение, поскольку нет центрального органа для их выпуска. Постоянное добавление фиксированного количества новых монет аналогично тому, как золотодобытчики тратят ресурсы для добавления золота в обращение. В нашем случае расходуется процессорное время и электроэнергия.
Стимул также может финансироваться за счет комиссий за транзакции. Если выходное значение транзакции меньше ее входного значения, разница представляет собой комиссию за транзакцию, которая добавляется к стимулирующему значению блока, содержащего транзакцию. Как только заранее определенное количество монет поступит в обращение, стимул может полностью перейти на комиссии за транзакции и быть полностью свободным от инфляции.
Стимул может помочь побудить узлы оставаться честными. Если жадный атакующий сможет собрать больше вычислительной мощности CPU, чем все честные узлы, ему придется выбирать между использованием ее для обмана людей путем возврата своих платежей или использованием ее для генерации новых монет. Ему должно быть выгоднее играть по правилам, которые дают ему больше новых монет, чем всем остальным вместе взятым, чем подрывать систему и обесценивать собственное богатство.
Reclaiming Disk Space
Une fois que la derniere transaction d'une piece est enfouie sous suffisamment de blocs, les transactions depensees avant elle peuvent etre supprimees pour economiser de l'espace disque. Pour faciliter cela sans casser le hash du bloc, les transactions sont hachees dans un Merkle Tree [^7] [^2] [^5], avec seule la racine incluse dans le hash du bloc. Les anciens blocs peuvent alors etre compactes en elaguant les branches de l'arbre. Les hash interieurs n'ont pas besoin d'etre stockes.
Un en-tete de bloc sans transactions ferait environ 80 octets. Si nous supposons que les blocs sont generes toutes les 10 minutes, 80 octets * 6 * 24 * 365 = 4,2 Mo par an. Avec des systemes informatiques generalement vendus avec 2 Go de RAM en 2008, et la loi de Moore prevoyant une croissance actuelle de 1,2 Go par an, le stockage ne devrait pas etre un probleme meme si les en-tetes de blocs doivent etre conserves en memoire.
Reclaiming Disk Space
Как только последняя транзакция в монете оказывается погребена под достаточным количеством блоков, потраченные транзакции до нее могут быть отброшены для экономии дискового пространства. Чтобы обеспечить это без нарушения хеша блока, транзакции хешируются в дереве Меркла (Merkle Tree) [^7] [^2] [^5], и только корень включается в хеш блока. Старые блоки затем могут быть сжаты путем отсечения ветвей дерева. Внутренние хеши не нужно хранить.
Заголовок блока без транзакций занимал бы около 80 байт. Если предположить, что блоки генерируются каждые 10 минут, 80 байт * 6 * 24 * 365 = 4,2 МБ в год. При том, что компьютерные системы обычно продавались с 2 ГБ ОЗУ по состоянию на 2008 год, а закон Мура предсказывает текущий рост в 1,2 ГБ в год, хранение не должно быть проблемой, даже если заголовки блоков необходимо хранить в памяти.
Simplified Payment Verification
Il est possible de verifier les paiements sans faire fonctionner un noeud reseau complet. Un utilisateur n'a besoin que de conserver une copie des en-tetes de blocs de la plus longue chaine de proof-of-work, qu'il peut obtenir en interrogeant les noeuds du reseau jusqu'a ce qu'il soit convaincu d'avoir la chaine la plus longue, et d'obtenir la branche Merkle reliant la transaction au bloc dans lequel elle est horodatee. Il ne peut pas verifier la transaction par lui-meme, mais en la reliant a un endroit dans la chaine, il peut voir qu'un noeud du reseau l'a acceptee, et les blocs ajoutes apres confirment davantage que le reseau l'a acceptee.
En tant que telle, la verification est fiable tant que les noeuds honnetes controlent le reseau, mais est plus vulnerable si le reseau est domine par un attaquant. Bien que les noeuds du reseau puissent verifier les transactions par eux-memes, la methode simplifiee peut etre trompee par les transactions fabriquees d'un attaquant tant que l'attaquant peut continuer a dominer le reseau. Une strategie pour se proteger contre cela serait d'accepter les alertes des noeuds du reseau lorsqu'ils detectent un bloc invalide, incitant le logiciel de l'utilisateur a telecharger le bloc complet et les transactions signalees pour confirmer l'incoherence. Les entreprises qui recoivent des paiements frequents voudront probablement toujours faire fonctionner leurs propres noeuds pour une securite plus independante et une verification plus rapide.
Simplified Payment Verification
Можно проверять платежи, не запуская полный сетевой узел. Пользователю нужно лишь хранить копию заголовков блоков самой длинной цепочки proof-of-work, которую он может получить, опрашивая сетевые узлы, пока не убедится, что имеет самую длинную цепочку, и получить ветвь Меркла, связывающую транзакцию с блоком, в котором она получила временную метку. Он не может проверить транзакцию самостоятельно, но, связав ее с местом в цепочке, он может увидеть, что сетевой узел принял ее, и блоки, добавленные после нее, дополнительно подтверждают, что сеть ее приняла.
Таким образом, проверка надежна, пока честные узлы контролируют сеть, но более уязвима, если сеть захвачена атакующим. В то время как сетевые узлы могут самостоятельно проверять транзакции, упрощенный метод может быть обманут сфабрикованными транзакциями атакующего, пока тот может продолжать доминировать в сети. Одной из стратегий защиты от этого было бы принятие предупреждений от сетевых узлов при обнаружении ими недействительного блока, побуждающих программное обеспечение пользователя загрузить полный блок и отмеченные транзакции для подтверждения несоответствия. Предприятия, получающие частые платежи, вероятно, по-прежнему захотят запускать собственные узлы для более независимой безопасности и более быстрой проверки.
Combining and Splitting Value
Bien qu'il soit possible de gerer les pieces individuellement, il serait peu pratique de faire une transaction separee pour chaque centime dans un transfert. Pour permettre de diviser et combiner la valeur, les transactions contiennent des entrees et des sorties multiples. Normalement, il y aura soit une seule entree provenant d'une transaction precedente plus importante, soit plusieurs entrees combinant des montants plus petits, et au plus deux sorties : une pour le paiement, et une restituant la monnaie, le cas echeant, a l'expediteur.
Il convient de noter que l'eventail, ou une transaction depend de plusieurs transactions, et ces transactions dependent de beaucoup d'autres, n'est pas un probleme ici. Il n'y a jamais besoin d'extraire une copie autonome complete de l'historique d'une transaction.
Combining and Splitting Value
Хотя было бы возможно обрабатывать монеты по отдельности, было бы неудобно создавать отдельную транзакцию для каждого цента при переводе. Чтобы позволить разделение и объединение стоимости, транзакции содержат несколько входов и выходов. Обычно будет либо один вход от более крупной предыдущей транзакции, либо несколько входов, объединяющих меньшие суммы, и не более двух выходов: один для платежа и один для возврата сдачи, если таковая имеется, отправителю.
Следует отметить, что разветвление (fan-out), когда транзакция зависит от нескольких транзакций, а те, в свою очередь, зависят от еще большего числа, здесь не является проблемой. Никогда нет необходимости извлекать полную самостоятельную копию истории транзакции.
Privacy
Le modele bancaire traditionnel atteint un niveau de confidentialite en limitant l'acces a l'information aux parties concernees et au tiers de confiance. La necessite d'annoncer toutes les transactions publiquement exclut cette methode, mais la confidentialite peut toujours etre maintenue en rompant le flux d'informations a un autre endroit : en gardant les cles publiques anonymes. Le public peut voir que quelqu'un envoie un montant a quelqu'un d'autre, mais sans information reliant la transaction a quiconque. Ceci est similaire au niveau d'information publie par les bourses, ou le moment et la taille des transactions individuelles, le "ruban", sont rendus publics, mais sans dire qui etaient les parties.
Comme pare-feu supplementaire, une nouvelle paire de cles devrait etre utilisee pour chaque transaction afin de les empecher d'etre liees a un proprietaire commun. Un certain lien est toujours inevitable avec les transactions a entrees multiples, qui revelent necessairement que leurs entrees appartenaient au meme proprietaire. Le risque est que si le proprietaire d'une cle est revele, le lien pourrait reveler d'autres transactions qui appartenaient au meme proprietaire.
Privacy
Традиционная банковская модель обеспечивает определенный уровень конфиденциальности, ограничивая доступ к информации вовлеченными сторонами и доверенной третьей стороной. Необходимость публично объявлять все транзакции исключает этот метод, но конфиденциальность все еще может быть сохранена путем прерывания потока информации в другом месте: путем сохранения анонимности открытых ключей. Общественность может видеть, что кто-то отправляет сумму кому-то другому, но без информации, связывающей транзакцию с кем-либо. Это аналогично уровню информации, публикуемой фондовыми биржами, где время и объем отдельных сделок, «лента», делаются публичными, но без указания того, кем были стороны.
В качестве дополнительного барьера для каждой транзакции следует использовать новую пару ключей, чтобы предотвратить их привязку к общему владельцу. Некоторая связь по-прежнему неизбежна при транзакциях с несколькими входами, которые неизбежно раскрывают, что их входы принадлежали одному владельцу. Риск состоит в том, что если владелец ключа будет раскрыт, связывание может раскрыть другие транзакции, принадлежавшие тому же владельцу.
Calculations
Nous considerons le scenario d'un attaquant essayant de generer une chaine alternative plus rapidement que la chaine honnete. Meme si cela est accompli, cela n'ouvre pas le systeme a des modifications arbitraires, comme creer de la valeur a partir de rien ou prendre de l'argent qui n'a jamais appartenu a l'attaquant. Les noeuds n'accepteront pas une transaction invalide comme paiement, et les noeuds honnetes n'accepteront jamais un bloc les contenant. Un attaquant ne peut qu'essayer de modifier une de ses propres transactions pour recuperer l'argent qu'il a recemment depense.
La course entre la chaine honnete et la chaine d'un attaquant peut etre caracterisee comme une marche aleatoire binomiale. L'evenement de succes est l'extension de la chaine honnete d'un bloc, augmentant son avance de +1, et l'evenement d'echec est l'extension de la chaine de l'attaquant d'un bloc, reduisant l'ecart de -1.
La probabilite qu'un attaquant rattrape a partir d'un deficit donne est analogue au probleme de la ruine du joueur. Supposons qu'un joueur avec un credit illimite commence avec un deficit et joue potentiellement un nombre infini d'essais pour tenter d'atteindre l'equilibre. Nous pouvons calculer la probabilite qu'il atteigne un jour l'equilibre, ou qu'un attaquant rattrape un jour la chaine honnete, comme suit [^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}
\]
Etant donne notre hypothese que p q, la probabilite diminue exponentiellement a mesure que le nombre de blocs que l'attaquant doit rattraper augmente. Avec les chances contre lui, s'il ne fait pas une poussee chanceuse en avant tot, ses chances deviennent infiniment petites a mesure qu'il prend du retard.
Nous considerons maintenant combien de temps le destinataire d'une nouvelle transaction doit attendre avant d'etre suffisamment certain que l'expediteur ne peut pas modifier la transaction. Nous supposons que l'expediteur est un attaquant qui veut faire croire au destinataire qu'il l'a paye pendant un certain temps, puis basculer pour se rembourser lui-meme apres un certain temps. Le destinataire sera alerte quand cela se produira, mais l'expediteur espere qu'il sera trop tard.
Le destinataire genere une nouvelle paire de cles et donne la cle publique a l'expediteur peu avant la signature. Cela empeche l'expediteur de preparer une chaine de blocs a l'avance en y travaillant continuellement jusqu'a ce qu'il ait la chance d'etre suffisamment en avance, puis d'executer la transaction a ce moment-la. Une fois la transaction envoyee, l'expediteur malhonnete commence a travailler en secret sur une chaine parallele contenant une version alternative de sa transaction.
Le destinataire attend que la transaction ait ete ajoutee a un bloc et que z blocs aient ete lies apres. Il ne connait pas la quantite exacte de progres que l'attaquant a fait, mais en supposant que les blocs honnetes ont pris le temps moyen attendu par bloc, le progres potentiel de l'attaquant sera une distribution de Poisson avec la valeur attendue :
\[
\lambda = z\frac{q}{p}
\]
Pour obtenir la probabilite que l'attaquant puisse encore rattraper maintenant, nous multiplions la densite de Poisson pour chaque quantite de progres qu'il aurait pu faire par la probabilite qu'il puisse rattraper a partir de ce point :
\[
\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.
\]
Rearrangement pour eviter de sommer la queue infinie de la distribution...
\[
1 - \sum_{k=0}^{z} \frac{\lambda^k e^{-\lambda}}{k!} \left(1-\left(\frac{q}{p}\right)^{(z-k)}\right)
\]
Conversion en code 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;
}
En executant quelques resultats, nous pouvons voir la probabilite diminuer exponentiellement avec 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
Resolution pour P inferieur a 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
Nous avons propose un systeme pour les transactions electroniques sans reposer sur la confiance. Nous avons commence avec le cadre habituel de pieces faites de signatures numeriques, qui fournit un controle fort de la propriete, mais est incomplet sans un moyen de prevenir la double depense. Pour resoudre cela, nous avons propose un reseau pair-a-pair utilisant le proof-of-work pour enregistrer un historique public des transactions qui devient rapidement informatiquement impraticable a modifier pour un attaquant si les noeuds honnetes controlent une majorite de la puissance CPU. Le reseau est robuste dans sa simplicite non structuree. Les noeuds travaillent tous en meme temps avec peu de coordination. Ils n'ont pas besoin d'etre identifies, puisque les messages ne sont pas achemines vers un endroit particulier et n'ont besoin d'etre delivres qu'au mieux. Les noeuds peuvent quitter et rejoindre le reseau a volonte, acceptant la chaine de proof-of-work comme preuve de ce qui s'est passe pendant leur absence. Ils votent avec leur puissance CPU, exprimant leur acceptation des blocs valides en travaillant a les etendre et rejetant les blocs invalides en refusant de travailler dessus. Toutes les regles et incitations necessaires peuvent etre appliquees avec ce mecanisme de consensus.
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.
