Биткоин: система электронных денег на основе одноранговой сети
Abstract
Una version puramente peer-to-peer de dinero electronico permitiria enviar pagos en linea directamente de una parte a otra sin pasar por una institucion financiera. Las firmas digitales proporcionan parte de la solucion, pero los principales beneficios se pierden si todavia se requiere un tercero de confianza para prevenir el doble gasto. Proponemos una solucion al problema del doble gasto utilizando una red peer-to-peer. La red marca temporalmente las transacciones al incluirlas mediante hash en una cadena continua de proof-of-work basada en hash, formando un registro que no puede ser modificado sin rehacer el proof-of-work. La cadena mas larga no solo sirve como prueba de la secuencia de eventos presenciados, sino como prueba de que proviene del mayor conjunto de poder de CPU. Mientras la mayoria del poder de CPU este controlado por nodos que no cooperan para atacar la red, generaran la cadena mas larga y superaran a los atacantes. La red en si requiere una estructura minima. Los mensajes se transmiten con base en el mejor esfuerzo, y los nodos pueden abandonar y reincorporarse a la red a voluntad, aceptando la cadena de proof-of-work mas larga como prueba de lo que ocurrio mientras estuvieron ausentes.
Abstract
Полностью одноранговая версия электронных денег позволила бы отправлять онлайн-платежи напрямую от одной стороны к другой без участия финансового учреждения. Цифровые подписи обеспечивают часть решения, но основные преимущества теряются, если для предотвращения двойного расходования по-прежнему требуется доверенная третья сторона. Мы предлагаем решение проблемы двойного расходования с использованием одноранговой сети. Сеть присваивает транзакциям временные метки, хешируя их в непрерывную цепочку proof-of-work на основе хешей, формируя запись, которую невозможно изменить без повторного выполнения proof-of-work. Самая длинная цепочка служит не только доказательством последовательности наблюдавшихся событий, но и доказательством того, что она создана наибольшим пулом вычислительной мощности CPU. Пока большая часть мощности CPU контролируется узлами, не участвующими в атаке на сеть, они будут генерировать самую длинную цепочку и опережать атакующих. Сама сеть требует минимальной структуры. Сообщения рассылаются по принципу максимальных усилий, и узлы могут покидать сеть и присоединяться к ней по желанию, принимая самую длинную цепочку proof-of-work как доказательство того, что произошло в их отсутствие.
Introduction
El comercio en Internet ha llegado a depender casi exclusivamente de instituciones financieras que sirven como terceros de confianza para procesar pagos electronicos. Si bien el sistema funciona suficientemente bien para la mayoria de las transacciones, todavia adolece de las debilidades inherentes del modelo basado en la confianza. Las transacciones completamente irreversibles no son realmente posibles, ya que las instituciones financieras no pueden evitar mediar en disputas. El costo de la mediacion aumenta los costos de transaccion, limitando el tamano minimo practico de la transaccion y eliminando la posibilidad de pequenas transacciones casuales, y existe un costo mas amplio en la perdida de la capacidad de realizar pagos irreversibles por servicios irreversibles. Con la posibilidad de reversion, la necesidad de confianza se extiende. Los comerciantes deben desconfiar de sus clientes, solicitandoles mas informacion de la que de otro modo necesitarian. Un cierto porcentaje de fraude se acepta como inevitable. Estos costos e incertidumbres de pago pueden evitarse en persona utilizando moneda fisica, pero no existe ningun mecanismo para realizar pagos a traves de un canal de comunicacion sin un tercero de confianza.
Lo que se necesita es un sistema de pago electronico basado en prueba criptografica en lugar de confianza, que permita a dos partes dispuestas realizar transacciones directamente entre si sin la necesidad de un tercero de confianza. Las transacciones que son computacionalmente impracticas de revertir protegerian a los vendedores del fraude, y mecanismos rutinarios de deposito en garantia podrian implementarse facilmente para proteger a los compradores. En este documento, proponemos una solucion al problema del doble gasto utilizando un servidor de marcas de tiempo distribuido peer-to-peer para generar prueba computacional del orden cronologico de las transacciones. El sistema es seguro mientras los nodos honestos controlen colectivamente mas poder de CPU que cualquier grupo cooperante de nodos atacantes.
Introduction
Коммерция в Интернете стала почти исключительно зависеть от финансовых учреждений, выступающих в роли доверенных третьих сторон для обработки электронных платежей. Хотя система достаточно хорошо работает для большинства транзакций, она по-прежнему страдает от врожденных слабостей модели, основанной на доверии. Полностью необратимые транзакции фактически невозможны, поскольку финансовые учреждения не могут избежать посредничества в спорах. Стоимость посредничества увеличивает транзакционные издержки, ограничивая минимальный практический размер транзакции и исключая возможность мелких повседневных транзакций, а также существует более широкая цена в виде утраты возможности осуществлять необратимые платежи за необратимые услуги. С возможностью отмены потребность в доверии распространяется. Продавцы должны с осторожностью относиться к своим клиентам, запрашивая у них больше информации, чем было бы необходимо в ином случае. Определенный процент мошенничества принимается как неизбежный. Эти издержки и неопределенности платежей можно избежать при личных расчетах с использованием физической валюты, но не существует механизма для осуществления платежей по каналу связи без доверенной стороны.
Необходима электронная платежная система, основанная на криптографическом доказательстве вместо доверия, позволяющая любым двум желающим сторонам совершать сделки напрямую друг с другом без необходимости в доверенной третьей стороне. Транзакции, которые вычислительно непрактично отменить, защитили бы продавцов от мошенничества, а обычные механизмы условного депонирования могли бы быть легко реализованы для защиты покупателей. В данной работе мы предлагаем решение проблемы двойного расходования с использованием одноранговой распределенной системы серверов временных меток для генерации вычислительного доказательства хронологического порядка транзакций. Система безопасна до тех пор, пока честные узлы совместно контролируют больше вычислительной мощности CPU, чем любая кооперирующаяся группа атакующих узлов.
Transactions
Definimos una moneda electronica como una cadena de firmas digitales. Cada propietario transfiere la moneda al siguiente firmando digitalmente un hash de la transaccion anterior y la clave publica del siguiente propietario, y anadiendo estos al final de la moneda. Un beneficiario puede verificar las firmas para verificar la cadena de propiedad.
El problema, por supuesto, es que el beneficiario no puede verificar que uno de los propietarios no haya gastado doblemente la moneda. Una solucion comun es introducir una autoridad central de confianza, o casa de moneda, que verifique cada transaccion en busca de doble gasto. Despues de cada transaccion, la moneda debe ser devuelta a la casa de moneda para emitir una nueva moneda, y solo las monedas emitidas directamente por la casa de moneda son confiables de no haber sido doblemente gastadas. El problema con esta solucion es que el destino de todo el sistema monetario depende de la empresa que administra la casa de moneda, y cada transaccion debe pasar por ella, igual que un banco.
Necesitamos una forma para que el beneficiario sepa que los propietarios anteriores no firmaron ninguna transaccion previa. Para nuestros propositos, la transaccion mas temprana es la que cuenta, por lo que no nos preocupan los intentos posteriores de doble gasto. La unica forma de confirmar la ausencia de una transaccion es estar al tanto de todas las transacciones. En el modelo basado en la casa de moneda, esta estaba al tanto de todas las transacciones y decidia cual llego primero. Para lograr esto sin un tercero de confianza, las transacciones deben ser anunciadas publicamente [^1], y necesitamos un sistema para que los participantes acuerden un unico historial del orden en que fueron recibidas. El beneficiario necesita prueba de que, en el momento de cada transaccion, la mayoria de los nodos acordo que fue la primera recibida.
Transactions
Мы определяем электронную монету как цепочку цифровых подписей. Каждый владелец передает монету следующему, подписывая цифровой подписью хеш предыдущей транзакции и открытый ключ следующего владельца и добавляя их в конец монеты. Получатель платежа может проверить подписи для верификации цепочки владения.
Проблема, разумеется, в том, что получатель платежа не может проверить, не потратил ли один из владельцев монету дважды. Распространенное решение заключается во введении доверенного центрального органа, или монетного двора, который проверяет каждую транзакцию на предмет двойного расходования. После каждой транзакции монета должна быть возвращена на монетный двор для выпуска новой монеты, и только монеты, выпущенные непосредственно монетным двором, считаются не потраченными дважды. Проблема этого решения в том, что судьба всей денежной системы зависит от компании, управляющей монетным двором, и каждая транзакция должна проходить через них, как через банк.
Нам нужен способ, позволяющий получателю платежа знать, что предыдущие владельцы не подписывали никаких более ранних транзакций. Для наших целей самая ранняя транзакция является определяющей, поэтому нас не беспокоят последующие попытки двойного расходования. Единственный способ подтвердить отсутствие транзакции — быть осведомленным обо всех транзакциях. В модели монетного двора монетный двор знал обо всех транзакциях и решал, какая поступила первой. Чтобы достичь этого без доверенной стороны, транзакции должны быть объявлены публично [^1], и нам нужна система, позволяющая участникам согласовать единую историю порядка, в котором они были получены. Получателю платежа нужно доказательство того, что в момент каждой транзакции большинство узлов согласились, что она была получена первой.
Timestamp Server
La solucion que proponemos comienza con un servidor de marcas de tiempo. Un servidor de marcas de tiempo funciona tomando un hash de un bloque de elementos a los que se les asignara una marca de tiempo y publicando ampliamente el hash, como en un periodico o una publicacion de Usenet [^2] [^3] [^4] [^5]. La marca de tiempo demuestra que los datos deben haber existido en ese momento, obviamente, para poder ser incluidos en el hash. Cada marca de tiempo incluye la marca de tiempo anterior en su hash, formando una cadena, donde cada marca de tiempo adicional refuerza las anteriores.
Timestamp Server
Предлагаемое нами решение начинается с сервера временных меток. Сервер временных меток работает, беря хеш блока элементов, которым нужно присвоить временную метку, и широко публикуя этот хеш, например, в газете или посте Usenet [^2] [^3] [^4] [^5]. Временная метка доказывает, что данные, очевидно, должны были существовать в это время, чтобы попасть в хеш. Каждая временная метка включает предыдущую временную метку в свой хеш, образуя цепочку, где каждая дополнительная временная метка усиливает предыдущие.
Proof-of-Work
Para implementar un servidor de marcas de tiempo distribuido en una base peer-to-peer, necesitaremos utilizar un sistema de proof-of-work similar al Hashcash de Adam Back [^6], en lugar de publicaciones en periodicos o Usenet. El proof-of-work implica buscar un valor que, al ser hasheado, como con SHA-256, el hash comience con un numero de bits cero. El trabajo promedio requerido es exponencial en el numero de bits cero requeridos y puede verificarse ejecutando un unico hash.
Para nuestra red de marcas de tiempo, implementamos el proof-of-work incrementando un nonce en el bloque hasta que se encuentra un valor que le da al hash del bloque los bits cero requeridos. Una vez que el esfuerzo de CPU se ha gastado para satisfacer el proof-of-work, el bloque no puede ser cambiado sin rehacer el trabajo. A medida que se encadenan bloques posteriores, el trabajo para cambiar el bloque incluiria rehacer todos los bloques posteriores.
El proof-of-work tambien resuelve el problema de determinar la representacion en la toma de decisiones por mayoria. Si la mayoria se basara en una-direccion-IP-un-voto, podria ser subvertida por cualquiera capaz de asignar muchas IPs. El proof-of-work es esencialmente un-CPU-un-voto. La decision mayoritaria esta representada por la cadena mas larga, que tiene el mayor esfuerzo de proof-of-work invertido en ella. Si la mayoria del poder de CPU esta controlada por nodos honestos, la cadena honesta crecera mas rapido y superara a cualquier cadena competidora. Para modificar un bloque pasado, un atacante tendria que rehacer el proof-of-work del bloque y todos los bloques posteriores, y luego alcanzar y superar el trabajo de los nodos honestos. Mostraremos mas adelante que la probabilidad de que un atacante mas lento alcance a los demas disminuye exponencialmente a medida que se anaden bloques subsiguientes.
Para compensar el aumento de la velocidad del hardware y el interes variable en ejecutar nodos a lo largo del tiempo, la dificultad del proof-of-work se determina mediante un promedio movil que apunta a un numero promedio de bloques por hora. Si se generan demasiado rapido, la dificultad aumenta.
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
Los pasos para ejecutar la red son los siguientes:
- Las nuevas transacciones se transmiten a todos los nodos.
- Cada nodo recopila nuevas transacciones en un bloque.
- Cada nodo trabaja en encontrar un proof-of-work dificil para su bloque.
- Cuando un nodo encuentra un proof-of-work, transmite el bloque a todos los nodos.
- Los nodos aceptan el bloque solo si todas las transacciones en el son validas y no han sido gastadas previamente.
- Los nodos expresan su aceptacion del bloque trabajando en crear el siguiente bloque en la cadena, utilizando el hash del bloque aceptado como el hash anterior.
Los nodos siempre consideran la cadena mas larga como la correcta y continuaran trabajando para extenderla. Si dos nodos transmiten diferentes versiones del siguiente bloque simultaneamente, algunos nodos pueden recibir una u otra primero. En ese caso, trabajan en la primera que recibieron, pero guardan la otra rama en caso de que se vuelva mas larga. El empate se rompera cuando se encuentre el siguiente proof-of-work y una rama se vuelva mas larga; los nodos que estaban trabajando en la otra rama cambiaran entonces a la mas larga.
Las transmisiones de nuevas transacciones no necesariamente necesitan llegar a todos los nodos. Mientras lleguen a muchos nodos, entraran en un bloque en poco tiempo. Las transmisiones de bloques tambien son tolerantes a mensajes perdidos. Si un nodo no recibe un bloque, lo solicitara cuando reciba el siguiente bloque y se de cuenta de que le falta uno.
Network
Шаги для работы сети следующие:
- Новые транзакции рассылаются всем узлам.
- Каждый узел собирает новые транзакции в блок.
- Каждый узел работает над поиском сложного proof-of-work для своего блока.
- Когда узел находит proof-of-work, он рассылает блок всем узлам.
- Узлы принимают блок, только если все транзакции в нем действительны и не были потрачены ранее.
- Узлы выражают свое принятие блока, работая над созданием следующего блока в цепочке, используя хеш принятого блока в качестве предыдущего хеша.
Узлы всегда считают самую длинную цепочку правильной и продолжают работать над ее удлинением. Если два узла одновременно рассылают разные версии следующего блока, некоторые узлы могут получить одну или другую первой. В этом случае они работают над той, которую получили первой, но сохраняют другую ветвь на случай, если она станет длиннее. Ничья будет разрешена, когда будет найден следующий proof-of-work и одна ветвь станет длиннее; узлы, работавшие над другой ветвью, тогда переключатся на более длинную.
Рассылка новых транзакций не обязательно должна достигать всех узлов. Пока они достигают многих узлов, они попадут в блок в скором времени. Рассылка блоков также устойчива к потере сообщений. Если узел не получает блок, он запросит его при получении следующего блока, осознав, что пропустил один.
Incentive
Por convencion, la primera transaccion en un bloque es una transaccion especial que inicia una nueva moneda propiedad del creador del bloque. Esto anade un incentivo para que los nodos apoyen la red, y proporciona una forma de distribuir inicialmente monedas en circulacion, ya que no existe una autoridad central para emitirlas. La adicion constante de una cantidad fija de nuevas monedas es analoga a los mineros de oro que gastan recursos para anadir oro a la circulacion. En nuestro caso, es el tiempo de CPU y la electricidad lo que se gasta.
El incentivo tambien puede financiarse con tarifas de transaccion. Si el valor de salida de una transaccion es menor que su valor de entrada, la diferencia es una tarifa de transaccion que se anade al valor del incentivo del bloque que contiene la transaccion. Una vez que un numero predeterminado de monedas ha entrado en circulacion, el incentivo puede transicionar completamente a tarifas de transaccion y estar completamente libre de inflacion.
El incentivo puede ayudar a alentar a los nodos a mantenerse honestos. Si un atacante codicioso es capaz de reunir mas poder de CPU que todos los nodos honestos, tendria que elegir entre usarlo para defraudar a las personas robando sus pagos, o usarlo para generar nuevas monedas. Deberia encontrar mas rentable jugar segun las reglas, reglas que lo favorecen con mas monedas nuevas que todos los demas combinados, que socavar el sistema y la validez de su propia riqueza.
Incentive
По соглашению, первая транзакция в блоке является специальной транзакцией, которая создает новую монету, принадлежащую создателю блока. Это добавляет стимул для узлов поддерживать сеть и обеспечивает способ первоначального распределения монет в обращение, поскольку нет центрального органа для их выпуска. Постоянное добавление фиксированного количества новых монет аналогично тому, как золотодобытчики тратят ресурсы для добавления золота в обращение. В нашем случае расходуется процессорное время и электроэнергия.
Стимул также может финансироваться за счет комиссий за транзакции. Если выходное значение транзакции меньше ее входного значения, разница представляет собой комиссию за транзакцию, которая добавляется к стимулирующему значению блока, содержащего транзакцию. Как только заранее определенное количество монет поступит в обращение, стимул может полностью перейти на комиссии за транзакции и быть полностью свободным от инфляции.
Стимул может помочь побудить узлы оставаться честными. Если жадный атакующий сможет собрать больше вычислительной мощности CPU, чем все честные узлы, ему придется выбирать между использованием ее для обмана людей путем возврата своих платежей или использованием ее для генерации новых монет. Ему должно быть выгоднее играть по правилам, которые дают ему больше новых монет, чем всем остальным вместе взятым, чем подрывать систему и обесценивать собственное богатство.
Reclaiming Disk Space
Una vez que la ultima transaccion en una moneda esta enterrada bajo suficientes bloques, las transacciones gastadas anteriores pueden descartarse para ahorrar espacio en disco. Para facilitar esto sin romper el hash del bloque, las transacciones se hashean en un Merkle Tree [^7] [^2] [^5], con solo la raiz incluida en el hash del bloque. Los bloques antiguos pueden entonces compactarse eliminando ramas del arbol. Los hashes interiores no necesitan ser almacenados.
Un encabezado de bloque sin transacciones seria de aproximadamente 80 bytes. Si suponemos que los bloques se generan cada 10 minutos, 80 bytes * 6 * 24 * 365 = 4.2MB por ano. Con los sistemas informaticos que tipicamente se vendian con 2GB de RAM en 2008, y la Ley de Moore prediciendo un crecimiento actual de 1.2GB por ano, el almacenamiento no deberia ser un problema incluso si los encabezados de bloque deben mantenerse en memoria.
Reclaiming Disk Space
Как только последняя транзакция в монете оказывается погребена под достаточным количеством блоков, потраченные транзакции до нее могут быть отброшены для экономии дискового пространства. Чтобы обеспечить это без нарушения хеша блока, транзакции хешируются в дереве Меркла (Merkle Tree) [^7] [^2] [^5], и только корень включается в хеш блока. Старые блоки затем могут быть сжаты путем отсечения ветвей дерева. Внутренние хеши не нужно хранить.
Заголовок блока без транзакций занимал бы около 80 байт. Если предположить, что блоки генерируются каждые 10 минут, 80 байт * 6 * 24 * 365 = 4,2 МБ в год. При том, что компьютерные системы обычно продавались с 2 ГБ ОЗУ по состоянию на 2008 год, а закон Мура предсказывает текущий рост в 1,2 ГБ в год, хранение не должно быть проблемой, даже если заголовки блоков необходимо хранить в памяти.
Simplified Payment Verification
Es posible verificar pagos sin ejecutar un nodo completo de la red. Un usuario solo necesita mantener una copia de los encabezados de bloque de la cadena de proof-of-work mas larga, que puede obtener consultando los nodos de la red hasta estar convencido de que tiene la cadena mas larga, y obtener la rama del Merkle Tree que vincula la transaccion al bloque en el que se le asigno la marca de tiempo. No puede verificar la transaccion por si mismo, pero al vincularla a un lugar en la cadena, puede ver que un nodo de la red la ha aceptado, y los bloques anadidos despues de ella confirman aun mas que la red la ha aceptado.
Como tal, la verificacion es confiable mientras los nodos honestos controlen la red, pero es mas vulnerable si la red es dominada por un atacante. Aunque los nodos de la red pueden verificar las transacciones por si mismos, el metodo simplificado puede ser enganado por transacciones fabricadas de un atacante mientras este pueda continuar dominando la red. Una estrategia para protegerse contra esto seria aceptar alertas de los nodos de la red cuando detecten un bloque invalido, solicitando al software del usuario descargar el bloque completo y las transacciones alertadas para confirmar la inconsistencia. Los negocios que reciben pagos frecuentes probablemente aun querran ejecutar sus propios nodos para una seguridad mas independiente y una verificacion mas rapida.
Simplified Payment Verification
Можно проверять платежи, не запуская полный сетевой узел. Пользователю нужно лишь хранить копию заголовков блоков самой длинной цепочки proof-of-work, которую он может получить, опрашивая сетевые узлы, пока не убедится, что имеет самую длинную цепочку, и получить ветвь Меркла, связывающую транзакцию с блоком, в котором она получила временную метку. Он не может проверить транзакцию самостоятельно, но, связав ее с местом в цепочке, он может увидеть, что сетевой узел принял ее, и блоки, добавленные после нее, дополнительно подтверждают, что сеть ее приняла.
Таким образом, проверка надежна, пока честные узлы контролируют сеть, но более уязвима, если сеть захвачена атакующим. В то время как сетевые узлы могут самостоятельно проверять транзакции, упрощенный метод может быть обманут сфабрикованными транзакциями атакующего, пока тот может продолжать доминировать в сети. Одной из стратегий защиты от этого было бы принятие предупреждений от сетевых узлов при обнаружении ими недействительного блока, побуждающих программное обеспечение пользователя загрузить полный блок и отмеченные транзакции для подтверждения несоответствия. Предприятия, получающие частые платежи, вероятно, по-прежнему захотят запускать собственные узлы для более независимой безопасности и более быстрой проверки.
Combining and Splitting Value
Aunque seria posible manejar monedas individualmente, seria poco practico hacer una transaccion separada por cada centavo en una transferencia. Para permitir que el valor se divida y combine, las transacciones contienen multiples entradas y salidas. Normalmente habra una unica entrada de una transaccion previa mayor o multiples entradas que combinan cantidades menores, y como maximo dos salidas: una para el pago, y una devolviendo el cambio, si lo hay, al remitente.
Cabe senalar que la ramificacion, donde una transaccion depende de varias transacciones, y esas transacciones dependen de muchas mas, no es un problema aqui. Nunca es necesario extraer una copia completa e independiente del historial de una transaccion.
Combining and Splitting Value
Хотя было бы возможно обрабатывать монеты по отдельности, было бы неудобно создавать отдельную транзакцию для каждого цента при переводе. Чтобы позволить разделение и объединение стоимости, транзакции содержат несколько входов и выходов. Обычно будет либо один вход от более крупной предыдущей транзакции, либо несколько входов, объединяющих меньшие суммы, и не более двух выходов: один для платежа и один для возврата сдачи, если таковая имеется, отправителю.
Следует отметить, что разветвление (fan-out), когда транзакция зависит от нескольких транзакций, а те, в свою очередь, зависят от еще большего числа, здесь не является проблемой. Никогда нет необходимости извлекать полную самостоятельную копию истории транзакции.
Privacy
El modelo bancario tradicional logra un nivel de privacidad limitando el acceso a la informacion a las partes involucradas y al tercero de confianza. La necesidad de anunciar todas las transacciones publicamente excluye este metodo, pero la privacidad aun puede mantenerse rompiendo el flujo de informacion en otro lugar: manteniendo las claves publicas anonimas. El publico puede ver que alguien esta enviando una cantidad a alguien mas, pero sin informacion que vincule la transaccion a nadie. Esto es similar al nivel de informacion publicado por las bolsas de valores, donde el tiempo y tamano de las operaciones individuales, la "cinta", se hace publica, pero sin revelar quienes fueron las partes.
Como cortafuegos adicional, se deberia usar un nuevo par de claves para cada transaccion para evitar que se vinculen a un propietario comun. Cierto grado de vinculacion es aun inevitable con transacciones de multiples entradas, que necesariamente revelan que sus entradas pertenecian al mismo propietario. El riesgo es que si se revela el propietario de una clave, la vinculacion podria revelar otras transacciones que pertenecieron al mismo propietario.
Privacy
Традиционная банковская модель обеспечивает определенный уровень конфиденциальности, ограничивая доступ к информации вовлеченными сторонами и доверенной третьей стороной. Необходимость публично объявлять все транзакции исключает этот метод, но конфиденциальность все еще может быть сохранена путем прерывания потока информации в другом месте: путем сохранения анонимности открытых ключей. Общественность может видеть, что кто-то отправляет сумму кому-то другому, но без информации, связывающей транзакцию с кем-либо. Это аналогично уровню информации, публикуемой фондовыми биржами, где время и объем отдельных сделок, «лента», делаются публичными, но без указания того, кем были стороны.
В качестве дополнительного барьера для каждой транзакции следует использовать новую пару ключей, чтобы предотвратить их привязку к общему владельцу. Некоторая связь по-прежнему неизбежна при транзакциях с несколькими входами, которые неизбежно раскрывают, что их входы принадлежали одному владельцу. Риск состоит в том, что если владелец ключа будет раскрыт, связывание может раскрыть другие транзакции, принадлежавшие тому же владельцу.
Calculations
Consideramos el escenario de un atacante que intenta generar una cadena alternativa mas rapido que la cadena honesta. Incluso si esto se logra, no abre el sistema a cambios arbitrarios, como crear valor de la nada o tomar dinero que nunca pertenecio al atacante. Los nodos no van a aceptar una transaccion invalida como pago, y los nodos honestos nunca aceptaran un bloque que las contenga. Un atacante solo puede intentar cambiar una de sus propias transacciones para recuperar dinero que gasto recientemente.
La carrera entre la cadena honesta y la cadena de un atacante puede caracterizarse como un Paseo Aleatorio Binomial. El evento de exito es que la cadena honesta se extienda un bloque, aumentando su ventaja en +1, y el evento de fracaso es que la cadena del atacante se extienda un bloque, reduciendo la brecha en -1.
La probabilidad de que un atacante alcance desde un deficit dado es analoga al problema de la Ruina del Jugador. Supongamos que un jugador con credito ilimitado comienza con un deficit y juega potencialmente un numero infinito de intentos para tratar de alcanzar el punto de equilibrio. Podemos calcular la probabilidad de que alguna vez alcance el punto de equilibrio, o de que un atacante alguna vez alcance a la cadena honesta, de la siguiente manera [^8]:
p = probabilidad de que un nodo honesto encuentre el siguiente bloque
q = probabilidad de que el atacante encuentre el siguiente bloque
q = probabilidad de que el atacante alguna vez alcance desde z bloques detras
``````
\[
qz =
\begin{cases}
1 & \text{if } p \leq q \\
\left(\frac{q}{p}\right) z & \text{if } p > q
\end{cases}
\]
Dada nuestra suposicion de que p q, la probabilidad cae exponencialmente a medida que aumenta el numero de bloques que el atacante tiene que alcanzar. Con las probabilidades en su contra, si no logra un avance afortunado temprano, sus posibilidades se vuelven infinitesimalmente pequenas a medida que queda mas atras.
Ahora consideramos cuanto tiempo necesita esperar el destinatario de una nueva transaccion antes de estar suficientemente seguro de que el remitente no puede cambiar la transaccion. Asumimos que el remitente es un atacante que quiere hacer creer al destinatario que le pago durante un tiempo, y luego cambiarlo para pagarse a si mismo despues de que haya pasado algun tiempo. El receptor sera alertado cuando eso suceda, pero el remitente espera que sea demasiado tarde.
El receptor genera un nuevo par de claves y entrega la clave publica al remitente poco antes de firmar. Esto evita que el remitente prepare una cadena de bloques con anticipacion trabajando en ella continuamente hasta que tenga la suerte de adelantarse lo suficiente, y luego ejecutar la transaccion en ese momento. Una vez que la transaccion es enviada, el remitente deshonesto comienza a trabajar en secreto en una cadena paralela que contiene una version alternativa de su transaccion.
El destinatario espera hasta que la transaccion se haya anadido a un bloque y z bloques se hayan vinculado despues de el. No conoce la cantidad exacta de progreso que el atacante ha hecho, pero asumiendo que los bloques honestos tomaron el tiempo promedio esperado por bloque, el progreso potencial del atacante sera una distribucion de Poisson con valor esperado:
\[
\lambda = z\frac{q}{p}
\]
Para obtener la probabilidad de que el atacante aun pueda alcanzar, multiplicamos la densidad de Poisson para cada cantidad de progreso que podria haber hecho por la probabilidad de que pueda alcanzar desde ese punto:
\[
\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.
\]
Reorganizando para evitar sumar la cola infinita de la distribucion...
\[
1 - \sum_{k=0}^{z} \frac{\lambda^k e^{-\lambda}}{k!} \left(1-\left(\frac{q}{p}\right)^{(z-k)}\right)
\]
Convirtiendo a codigo 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;
}
Ejecutando algunos resultados, podemos ver que la probabilidad cae exponencialmente con 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
Resolviendo para P menor que 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
Hemos propuesto un sistema para transacciones electronicas sin depender de la confianza. Comenzamos con el marco habitual de monedas hechas de firmas digitales, que proporciona un fuerte control de propiedad, pero es incompleto sin una forma de prevenir el doble gasto. Para resolver esto, propusimos una red peer-to-peer que utiliza proof-of-work para registrar un historial publico de transacciones que rapidamente se vuelve computacionalmente impractico de cambiar para un atacante si los nodos honestos controlan la mayoria del poder de CPU. La red es robusta en su simplicidad no estructurada. Los nodos trabajan todos a la vez con poca coordinacion. No necesitan ser identificados, ya que los mensajes no se enrutan a ningun lugar particular y solo necesitan ser entregados con base en el mejor esfuerzo. Los nodos pueden abandonar y reincorporarse a la red a voluntad, aceptando la cadena de proof-of-work como prueba de lo que ocurrio mientras estuvieron ausentes. Votan con su poder de CPU, expresando su aceptacion de bloques validos al trabajar en extenderlos y rechazando bloques invalidos al negarse a trabajar en ellos. Cualquier regla e incentivo necesario puede ser aplicado con este mecanismo de consenso.
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.
