Bitcoin: sistema de efectivo electrónico peer-to-peer
Abstracto. Una versión puramente peer-to-peer del dinero electrónico permitirá que los pagos en línea se envíen directamente de una parte a otra, sin pasar por la institución financiera. Las firmas digitales proporcionan parte de la solución, pero los principales beneficios se pierden si aún se requiere un tercero confiable para evitar el doble gasto. Proponemos una solución al problema del doble gasto utilizando una red peer-to-peer. La red marca las transacciones al convertirlas en una cadena continua de pruebas de trabajo basadas en hash, creando un registro que no se puede cambiar sin volver a ejecutar la prueba de trabajo. La cadena más larga sirve no sólo como prueba de la secuencia de eventos observados, sino también como prueba de que proviene del mayor conjunto de potencia de procesador. Mientras la mayor parte de la potencia de la CPU esté controlada por nodos que no participan en el ataque a la red, generarán la cadena más larga y superarán a los atacantes. La red en sí requiere una estructura mínima. Los mensajes se transmiten de la mejor manera posible y los nodos pueden salir y volver a unirse a la red a voluntad, tomando la cadena de prueba de trabajo más larga como prueba de lo que sucedió mientras estaban fuera.
Satoshi Nakamoto
satoshin@gmx.com
www.bitcoin.org
1. Introducción
El comercio en línea ha llegado a depender casi exclusivamente de instituciones financieras que actúan como terceros confiables para procesar pagos electrónicos. Aunque el sistema funciona bastante bien para la mayoría de las transacciones, todavía adolece de las desventajas inherentes a un modelo basado en la confianza. En realidad, las transacciones completamente irreversibles no son posibles porque las instituciones financieras no pueden evitar mediar en las disputas. El costo de la intermediación aumenta los costos de transacción al limitar el tamaño mínimo práctico de una transacción y eliminar la posibilidad de pequeñas transacciones aleatorias, y los costos más amplios están asociados con la pérdida de la capacidad de realizar pagos irreversibles por servicios irreversibles. Ante la posibilidad de reversión, se extiende la necesidad de confianza. Los comerciantes deben desconfiar de sus clientes y pedirles más información de la que de otro modo necesitarían. Un cierto porcentaje de fraude se considera inevitable. Estos costos y la incertidumbre de los pagos se pueden evitar en persona mediante el uso de moneda física, pero no existe ningún mecanismo para realizar pagos a través de un canal de comunicación sin una parte confiable.
Lo que se necesita es un sistema de pago electrónico basado en pruebas criptográficas en lugar de confianza, que permita a dos partes interesadas realizar transacciones directamente entre sí sin la necesidad de un tercero de confianza. Las transacciones que son computacionalmente imposibles de revertir protegerán a los vendedores del fraude, y los mecanismos de depósito en garantía convencionales pueden implementarse fácilmente para proteger a los compradores. En este artículo, proponemos una solución al problema del doble gasto mediante el uso de un servidor de marca de tiempo distribuido punto a punto para generar una prueba computacional del orden cronológico de las transacciones. El sistema es seguro siempre que los nodos honestos controlen colectivamente más potencia de CPU que cualquier grupo cooperante de nodos atacantes.
2. Transacciones
Definimos una moneda electrónica como una cadena de firmas digitales. Cada propietario pasa la moneda al siguiente firmando digitalmente el hash de la transacción anterior y la clave pública del siguiente propietario y agregándolos al final de la moneda. El beneficiario puede verificar las firmas para confirmar la cadena de propiedad.
El problema, por supuesto, es que el beneficiario no puede verificar que uno de los propietarios no gastó la moneda dos veces. Una solución común es crear una autoridad central confiable, o casa de moneda, que verifique cada transacción para detectar doble gasto. Después de cada transacción, la moneda debe devolverse a la casa de la moneda para emitir una nueva moneda, y solo se garantiza que las monedas emitidas directamente por la casa de la moneda no se gastarán dos veces. El problema con esta solución es que el destino de todo el sistema monetario depende de la empresa que gestiona la casa de moneda, y cada transacción debe pasar por ella, como en un banco.
Necesitamos una forma para que el beneficiario sepa que los propietarios anteriores no aprobaron ninguna transacción anterior. Para nuestros propósitos, se cuenta la transacción más temprana, por lo que no nos importan los intentos posteriores de doble gasto. La única forma de confirmar la ausencia de una transacción es estar al tanto de todas las transacciones. En el modelo basado en la Casa de la Moneda, la Casa de la Moneda conocía todas las transacciones y decidía cuáles llegaban primero. Para lograr esto sin una parte confiable, las transacciones deben anunciarse públicamente [1] y necesitamos un sistema que permita a los participantes acordar un historial único del orden en que fueron recibidas. El beneficiario necesita prueba de que durante cada transacción, la mayoría de los nodos acordaron que se recibió primero.
3. Servidor de marca de tiempo
Nuestra solución propuesta comienza con un servidor de marca de tiempo. Un servidor de marca de tiempo funciona tomando un hash de un bloque de elementos que necesitan tener una marca de tiempo y publicándolo ampliamente, como en un periódico o en una publicación de Usenet [2-5]. La marca de tiempo demuestra que los datos obviamente tenían que existir en ese momento para ser incluidos en el hash. Cada marca de tiempo incluye la marca de tiempo anterior en su hash, formando una cadena, y cada marca de tiempo adicional amplifica la anterior.
4. Prueba de trabajo
Para implementar un servidor de marca de tiempo distribuido punto a punto, necesitaríamos utilizar un sistema de prueba de trabajo similar al Hashcash de Adam Back [6], en lugar de publicaciones en periódicos o Usenet. La prueba de trabajo implica escanear un valor que, cuando se aplica un hash con, por ejemplo, SHA-256, el código hash comienza con una serie de bits cero. El trabajo promedio requerido depende exponencialmente de la cantidad de bits cero requeridos y se puede verificar realizando un único hash.
Para nuestra red de marca de tiempo, implementamos una prueba de trabajo incrementando el nonce en un bloque hasta que se encuentra un valor que le da al hash del bloque los cero bits necesarios. Una vez que se ha invertido el esfuerzo de la CPU para igualar la prueba de trabajo, el bloque no se puede cambiar sin volver a ejecutar el trabajo. Dado que los bloques posteriores se adjuntan después de él, el trabajo de cambiar un bloque implicará reelaborar todos los bloques posteriores.
La prueba de trabajo también resuelve el problema de determinar la representación en la toma de decisiones por mayoría. Si la mayoría se basara en el principio de "una dirección IP, un voto", podría ser refutado por cualquiera que pudiera asignar muchas direcciones IP. La prueba de trabajo es esencialmente "un procesador, un voto". La solución mayoritaria está representada por la cadena más larga que se esfuerza más en demostrar que funciona. Si la mayor parte de la potencia de la CPU está controlada por nodos honestos, la cadena honesta crecerá más rápido y superará a cualquier cadena competidora. Para cambiar un bloque anterior, un atacante tendría que rehacer la prueba de trabajo del bloque y todos los bloques posteriores, y luego alcanzar y superar el trabajo de los nodos honestos. Más adelante mostraremos que la probabilidad de que un atacante más lento se ponga al día disminuye exponencialmente a medida que se agregan bloques posteriores.
Para compensar el aumento de las velocidades del hardware y el cambio de interés en ejecutar nodos a lo largo del tiempo, la prueba de dificultad del trabajo se determina utilizando un promedio móvil que apunta al número promedio de bloques por hora. Si se generan demasiado rápido, la dificultad aumenta.
5. Red
Los pasos para iniciar 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 para encontrar una prueba de trabajo compleja para su bloque.
- Cuando un nodo encuentra prueba de trabajo, transmite el bloque a todos los nodos.
- Los nodos solo aceptan un bloque si todas las transacciones que contiene son válidas y aún no se han gastado.
- Los nodos expresan su aceptación de un bloque trabajando para crear el siguiente bloque en la cadena, utilizando el hash del bloque aceptado como hash anterior.
Los nodos siempre consideran que la cadena más larga es la correcta y continúan trabajando para expandirla. Si dos nodos transmiten simultáneamente diferentes versiones del siguiente bloque, algunos nodos pueden recibir primero una u otra. En este caso, trabajan con la primera rama que obtienen, pero mantienen otra rama en caso de que se alargue. El vínculo se romperá cuando se encuentre la siguiente prueba de trabajo y una rama se alargue; Los nodos que trabajan en la otra rama cambiarán a la más larga.
No es necesario que la transmisión de nuevas transacciones llegue a todos los nodos. Una vez que lleguen a muchos nodos, pronto terminarán en un bloque. Las transmisiones en bloque también toleran los mensajes perdidos. Si un nodo no ha recibido un bloque, solicitará uno cuando reciba el siguiente bloque y se dé cuenta de que perdió uno.
6. Estímulo
Por convención, la primera transacción en un bloque es una transacción especial que lanza una nueva moneda propiedad del creador del bloque. Esto añade un incentivo para que los nodos mantengan la red y permite distribuir inicialmente monedas en circulación, ya que no existe una autoridad central para emitirlas. Agregar constantemente una cantidad constante de nuevas monedas es similar a cómo los mineros de oro gastan recursos agregando oro a la circulación. En nuestro caso, se desperdicia tiempo del procesador y electricidad.
El incentivo también podría financiarse mediante tarifas de transacción. Si el valor de salida de una transacción es menor que el valor de entrada, la diferencia es una tarifa de transacción que se agrega al valor del incentivo del bloque que contiene la transacción. Una vez que una cantidad predeterminada de monedas entra en circulación, el incentivo puede trasladarse por completo a las tarifas de transacción y estar completamente libre de inflación.
Un incentivo puede ayudar a los nodos a ser honestos. Si un atacante codicioso puede recolectar más potencia de CPU que todos los nodos honestos, tendrá que elegir entre usarla para estafar a la gente robándole sus pagos o usarla para generar nuevas monedas. Debería resultarle más rentable seguir las reglas, reglas que le permitan obtener más monedas nuevas que todos los demás juntos, que socavar el sistema y la validez de su propia riqueza.
7. Liberar espacio en disco
Una vez que la última transacción en una moneda está oculta bajo suficientes bloques, las transacciones realizadas antes de que se pueda descartar para ahorrar espacio en el disco. Para facilitar esto sin violar el hash del bloque, las transacciones se procesan en un árbol Merkle [7][2][5], con solo la raíz incluida en el hash del bloque. Luego, los bloques viejos se pueden compactar cortando ramas de árboles. No es necesario guardar hashes internos.
El encabezado del bloque sin transacciones tendrá un tamaño de aproximadamente 80 bytes. Si asumimos que los bloques se generan cada 10 minutos, entonces 80 bytes * 6 * 24 * 365 = 4,2 MB por año. Dado que los sistemas informáticos se vendían normalmente con 2 GB de RAM en 2008, y la Ley de Moore predice un crecimiento actual de 1,2 GB por año, el almacenamiento no debería ser un problema, incluso si los encabezados de los bloques deben almacenarse en la memoria.
8. Verificación de pago simplificada
Puede confirmar pagos sin iniciar un nodo de red completo. El usuario solo necesita conservar una copia de los encabezados de bloque de la cadena de prueba de trabajo más larga que puede obtener sondeando los nodos de la red hasta que esté seguro de que tiene la cadena más larga, y obtener la rama Merkle que vincula la transacción al bloque. . tiene una marca de tiempo. No puede verificar la transacción por sí mismo, pero al vincularla a un lugar en la cadena, puede ver que un nodo en la red la aceptó y los bloques agregados después confirman que la red la aceptó.
Por lo tanto, la verificación es confiable siempre que nodos honestos controlen la red, pero se vuelve más vulnerable si la red está bajo el control de un atacante. Aunque los nodos de la red pueden verificar las transacciones por sí solos, un método abreviado puede ser engañado por transacciones fabricadas por un atacante siempre que el atacante pueda continuar saturando la red. Una estrategia para protegerse contra esto sería aceptar advertencias de los nodos de la red cuando detecten un bloque no válido, solicitando al software del usuario que descargue el bloque completo y advirtiendo a las transacciones para confirmar la discrepancia. Es probable que las empresas que reciben pagos frecuentes aún quieran ejecutar sus propios nodos para obtener una seguridad más independiente y una verificación más rápida.
9. Poner en común y compartir valor
Si bien sería posible procesar monedas individualmente, sería engorroso realizar una transacción separada para cada centavo transferido. Para permitir compartir y agrupar valor, las transacciones contienen múltiples entradas y salidas. Por lo general, habrá una entrada de una transacción anterior más grande, o múltiples entradas que combinan cantidades más pequeñas, y no más de dos salidas: una para el pago y otra para devolver el cambio, si corresponde, al remitente.
Cabe señalar que la bifurcación, en la que una transacción depende de varias transacciones y esas transacciones dependen de muchas otras, no es un problema aquí. Nunca es necesario recuperar una copia completa sin conexión de su historial de transacciones.
10. Privacidad
El modelo bancario tradicional proporciona un cierto nivel de privacidad al limitar el acceso a la información a los participantes y terceros de confianza. La necesidad de anunciar públicamente todas las transacciones impide este método, pero aún se puede preservar la privacidad interrumpiendo el flujo de información en otros lugares: manteniendo las claves públicas en el anonimato. El público puede ver que alguien está enviando una cantidad a otra persona, pero sin información que vincule la transacción con nadie. Esto es similar al nivel de información publicada por las bolsas de valores, donde el momento y el volumen de las operaciones individuales, la “cinta”, se hacen públicos, pero sin identificar a las partes.
Como firewall adicional, se debe utilizar un nuevo par de claves para cada transacción para evitar que queden vinculadas a un propietario común. Cierto acoplamiento sigue siendo inevitable en transacciones con múltiples insumos, lo que necesariamente muestra que sus insumos pertenecían al mismo propietario. El riesgo es que si se revela el propietario de la clave, la vinculación podría revelar otras transacciones que pertenecen al mismo propietario.
11. Cálculos
Consideramos un escenario en el que un atacante intenta crear una cadena alternativa más rápido que la cadena honesta. Incluso si esto se logra, no abrirá el sistema a cambios arbitrarios, como crear valor de la nada o tomar dinero que nunca perteneció al atacante. Los nodos no aceptarán una transacción no válida como pago y los nodos honestos nunca aceptarán un bloque que las contenga. Un atacante podría intentar cambiar sólo una de sus transacciones para recuperar el dinero que gastó recientemente.
La carrera entre una cadena honesta y una cadena maliciosa se puede caracterizar como un paseo aleatorio binomial. Un evento de éxito es que la cadena honesta se extiende en un bloque, lo que aumenta su ventaja en +1, y un evento de fracaso es que la cadena del atacante se extiende en un bloque, lo que reduce la ventaja en -1.
La probabilidad de que un atacante recupere un déficit determinado es similar al problema de que un jugador quiebre. Digamos que un jugador con crédito ilimitado comienza con un déficit y potencialmente juega un número infinito de intentos tratando de alcanzar el punto de equilibrio. Podemos calcular la probabilidad de que alguna vez alcance el punto de equilibrio, o de que el atacante alguna vez alcance la cadena honesta, de la siguiente manera [8]:
p = probabilidad de que un nodo honesto encuentre el siguiente bloque
q = probabilidad de que un atacante encuentre el siguiente bloque
qz = probabilidad de que un atacante alguna vez alcance z bloques detrás
Dada nuestra suposición de que p > q, la probabilidad cae exponencialmente a medida que aumenta el número de bloques que el atacante tiene que alcanzar. Dadas las probabilidades en su contra, si no hace un intento exitoso desde el principio, sus posibilidades serán cada vez más pequeñas a medida que se quede más atrás.
Ahora veremos cuánto tiempo debe esperar el destinatario de una nueva transacción antes de estar razonablemente seguro de que el remitente no podrá cambiar la transacción. Suponemos que el remitente es un atacante que quiere engañar al destinatario haciéndole creer que le pagó por un tiempo y luego cambiarlo para que se devuelva el dinero a sí mismo después de que haya pasado un tiempo. Cuando esto suceda, se alertará al destinatario, pero el remitente espera que sea demasiado tarde.
El destinatario genera un nuevo par de claves y transmite la clave pública al remitente poco antes de firmar. Esto evita que el remitente prepare la cadena de bloques con anticipación, trabaje en ella continuamente hasta que tenga la suerte de avanzar lo suficiente y luego ejecute la transacción en ese punto. Una vez enviada la transacción, el remitente deshonesto comienza a trabajar en secreto en una cadena paralela que contiene una versión alternativa de su transacción.
El destinatario espera hasta que la transacción se agrega al bloque y hay z bloques asociados después. No conoce el progreso exacto realizado por el atacante, pero suponiendo que los bloques honestos tomaron el tiempo promedio esperado por bloque, el progreso potencial del atacante será una distribución de Poisson con el valor esperado:
Para obtener la probabilidad de que un atacante aún pueda alcanzarlo ahora, multiplicamos la densidad de Poisson por cada cantidad de progreso que pueda lograr por la probabilidad de que pueda alcanzarlo desde ese punto:
Reordenamiento para evitar la suma de la cola infinita de la distribución...
Convertir a código C...
#include <math.h>
double AttackerSuccessProbability(double q, int z)
{
double p = 1.0 - q;
doble lambda = z*(q/p);
doble suma = 1,0;
intervalo i, k;
for (k = 0; k <= z; k++)
{
doble Poisson = exp(-lambda);
para (i = 1; i <= k; i++)
Poisson *= lambda / i;
suma -= Poisson * (1 - pow(q/p, z - k));
}
Importe de devolución;
}
Después de ejecutar algunos resultados, podemos ver que la probabilidad cae exponencialmente a medida que aumenta 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
Solución 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
12. Conclusión
Propusimos un sistema de transacciones electrónicas sin depender de la confianza. Comenzamos con una estructura de moneda convencional creada mediante firmas digitales, que proporciona un fuerte control de propiedad, pero está incompleta sin una forma de evitar el doble gasto. Para resolver este problema, propusimos una red peer-to-peer que utiliza prueba de trabajo para registrar un historial de transacciones públicas, lo que rápidamente se vuelve impracticable desde el punto de vista computacional para que un atacante lo modifique si los nodos honestos controlan la mayor parte de la potencia de la CPU. La red es robusta en su simplicidad no estructurada. Los nodos funcionan simultáneamente con poca coordinación. No es necesario identificarlos porque los mensajes no se reenvían a ninguna ubicación específica, sino que sólo se entregan al nivel más alto posible. Los nodos pueden salir y volver a unirse a la red a voluntad, tomando la cadena de prueba de trabajo como prueba de lo que sucedió mientras estaban fuera. Votan con la potencia de su procesador, aceptan bloques válidos trabajando para expandirlos y rechazan bloques no válidos negándose a trabajar en ellos. Todas las reglas e incentivos necesarios pueden implementarse a través de este mecanismo de consenso.
Recomendaciones
[1] W. Dai, “b-money”, http://www.weidai.com/bmoney.txt, 1998.
[2] H. Massías, KS. Ávila y J.-J. Kiskater, "Desarrollo de un servicio de sellado de tiempo seguro con gastos generales mínimos".
Requisitos de confianza”, en el 20º Simposio de Teoría de la Información del Benelux, mayo de 1999.
[3] S. Haber, VS. Stornetta, “Cómo marcar la hora de un documento digital”, Journal of Cryptology, vol 3, no.
2, páginas 99-111, 1991.
[4] D. Bayer, S. Haber, V. S. Stornetta, "Mejora de la eficiencia y confiabilidad del sellado de tiempo digital".
En Secuencias II: Métodos de comunicación, seguridad y ciencias de la información, páginas 329–334, 1993.
[5] S. Haber, V.S. Stornetta, “Nombres seguros para cadenas de bits”, en Actas de la 4ª Conferencia ACM.
sobre seguridad informática y de las comunicaciones, páginas 28 a 35, abril de 1997.
[6] A. Atrás, "Hashcash: una medida para contrarrestar la denegación de servicio".
http://www.hashcash.org/papers/hashcash.pdf, 2002
[7] R. C. Merkle, “Protocolos para criptosistemas de clave pública”, en Proc. 1980 Simposio sobre Seguridad y
Privacidad, IEEE Computer Society, páginas 122–133, abril de 1980.
[8] W. Feller, “Introducción a la teoría de la probabilidad y sus aplicaciones”, 1957.