Resumen: Una versión puramente electrónica de efectivo permitiría que los pagos en línea fuesen enviados directamente, de un ente a otro, sin tener que pasar por medio de una institución financiera. Las firmas digitales proporcionan parte de la solución al problema, pero los beneficios principales se pierden si tiene que existir un tercero de confianza para prevenir el doble gasto. Proponemos una solución al problema del doble gasto utilizando una red usuario-a-usuario. La red coloca marcas de tiempo a las transacciones que introduce en una cadena continua de pruebas de trabajo basadas en el cálculo de hashes, formando un registro que no puede ser cambiado sin volver a recrear la prueba de trabajo completa. La cadena más larga no solo sirve como testigo y prueba de la secuencia de eventos, sino que asegura que esta vino desde la agrupación con procesamiento de CPU más grande. Siempre que la mayoría del poder de procesamiento de CPU esté bajo el control de nodos que no cooperan para atacar la red, estos generarán la cadena más larga y llevarán ventaja a los atacantes. La red en sí misma requiere una estructura mínima. Los mensajes son enviados bajo la premisa del menor esfuerzo, y los nodos pueden irse y volver a unirse a la red cuando les parezca, aceptando la cadena más larga de prueba de trabajo, como prueba de lo que sucedió durante su ausencia.
1. Introducción
El comercio en Internet ha llegado exclusivamente a depender de las instituciones financieras, las cuales sirven como terceros de confianza, para el procesamiento de los pagos electrónicos. Aunque el sistema funciona suficientemente bien para la mayoría de las transacciones, aún sufre de las debilidades inherentes del modelo basado en la confianza. Las transacciones completamente irreversibles no son realmente posibles, debido a que las instituciones financieras no pueden evitar la mediación en disputas. El coste de la mediación incrementa los costes de transacción, limitando el tamaño mínimo práctico por transacción y eliminando la posibilidad de realizar pequeñas transacciones casuales, existiendo un coste mayor por esta pérdida y la imposibilidad de hacer pagos irreversibles por servicios no reversibles. Con la posibilidad de revertir, la necesidad de confianza se expande. Los comerciantes deben tener cuidado de sus clientes, molestándoles pidiendo más información de la que se necesitaría de otro modo. Un cierto porcentaje de fraude se acepta como inevitable. Estos costes e incertidumbres en los pagos pueden ser evitados si la persona utiliza dinero físico, pero no existe un mecanismo para hacer pagos por un canal de comunicación sin un tercero confiable. Lo que se necesita es un sistema de pagos electrónicos que esté basado en pruebas criptográficas en vez de en confianza, permitiendo a las dos partes interesadas realizar transacciones directamente sin la necesidad de un tercero confiable. Las transacciones que son computacionalmente poco factibles de revertir protegerían a los vendedores de fraude, del mismo modo que mecanismos rutinarios de depósito de garantía podrían ser fácilmente implementados para proteger a los compradores. En este trabajo, proponemos una solución al problema del doble gasto, utilizando un servidor de marcas de tiempo usuario a usuario, distribuido para generar una prueba computacional del orden cronológico de las transacciones. El sistema es seguro mientras que los nodos honestos controlen colectivamente más poder de procesamiento (CPU) que cualquier grupo de nodos atacantes.
2. Transacciones
Definimos una moneda electrónica como una cadena de firmas digitales. Cada dueño transfiere la moneda al próximo al firmar digitalmente un hash de la transacción previa y la clave pública del próximo dueño y agregando ambos al final de la moneda. Un beneficiario puede verificar las firmas para verificar la cadena de propiedad.
El problema está en que el beneficiario no puede verificar si alguno de los dueños previos no hizo un doble gasto de la moneda. La solución común es introducir una autoridad central confiable, una especie de casa de la moneda, que revisaría si cada transacción tiene doble gasto o no. Después de cada transacción, la moneda debe ser devuelta a la casa de la moneda para generar una nueva, de modo que solo las monedas generadas directamente por esta casa de la moneda son en las que se confían de no tener doble-gasto. El problema con esta solución es que, el destino del sistema monetario entero depende de la compañía que gestiona la casa de la moneda, teniendo que pasar todas las transacciones por ellos, tal y como actuaría un banco. Por tanto, necesitamos encontrar una forma para que el beneficiario pueda saber que los dueños previos no firmaron ninguna transacción anterior. Para nuestros propósitos, la transacción última o más temprana es la que cuenta, así que no nos importarán otros intentos de doble gasto posteriores. La única forma de confirmar la ausencia de una transacción es estando al tanto de todas las transacciones existentes. En el modelo de la casa de la moneda, era esta casa la que estaba al tanto de todas las transacciones y decidía cuales llegaban primero. Para lograr esto sin un tercero confiable, las transacciones deben ser anunciadas públicamente [1], y necesitaremos de un sistema de participantes que estén de acuerdo en una historia única, del orden en que estas transacciones fueron recibidas. El beneficiario necesita saber que, en el momento de cada transacción, la mayoría de los nodos estuvieron de acuerdo en cuál fue la primera que se recibió.
3. Servidor de Marcas de Tiempo
La solución que proponemos comienza con un servidor de marcas de tiempo. Funciona al realizar el hash de un bloque de datos a ser fechados y publicándolo ampliamente, tal y como se haría en un periódico o en una publicación de Usenet [2-5]. La marca de tiempo prueba que el dato, obviamente, debió de haber existido en ese momento para poder incluirse dentro del hash. Cada marca de tiempo incluye en su hash la marca de tiempo previa, formando una cadena, de modo que cada marca de tiempo adicional refuerza las anteriores a una dada.
4. Prueba de Trabajo
Para implementar un servidor de marcas de tiempo siguiendo un esquema usuario-a-usuario, necesitaremos utilizar un sistema de prueba de trabajo similar al Hashcash de Adam Back [6], en vez de usar una publicación en un periódico o en Usenet. La prueba de trabajo implica la exploración de un valor, tal que, al calcular un hash, como SHA-256, este empiece con un número determinado de bits con valor cero. El trabajo promedio requerido será exponencial al número de bits requeridos con valor cero, pero que puede ser verificado ejecutando un solo hash.
Para nuestra red de marcas de tiempo implementamos la prueba de trabajo incrementando el valor de un campo nonce, perteneciente al bloque, hasta que se encuentre un valor que dé el número requerido de bits con valor cero para el hash de este. Una vez que el esfuerzo de CPU se ha gastado para satisfacer la prueba de trabajo, el bloque no puede ser cambiado sin rehacer todo el trabajo. A medida que más bloques son encadenados después de uno dado, el trabajo para cambiar un bloque incluiría rehacer todos los bloques después de este.
La prueba de trabajo también resuelve el problema de determinar cómo representar la decisión por mayoría. Si esta mayoría se basara en un voto por dirección IP, podría ser alterada por alguien capaz de asignar muchas IPs. La prueba de trabajo equivale esencialmente a “una-CPU-un-voto”. La decisión de la mayoría es representada por la cadena más larga, la cual posee la prueba de trabajo con mayor esfuerzo invertido. Si la mayoría del poder de CPU está controlada por nodos honestos, la cadena honesta crecerá más rápido y dejará atrás cualquier otra cadena que esté compitiendo. Para modificar un bloque en el pasado, un atacante tendría que rehacer la prueba de trabajo del bloque y de todos los bloques posteriores, y luego alcanzar y superar el trabajo de los nodos honestos. Luego demostraremos que la probabilidad de que un atacante más lento pueda alcanzar a la cadena más larga disminuye exponencialmente a medida que más bloques subsecuentes son incorporados.
Para compensar el incremento de la velocidad del hardware y el interés variable de ejecutar nodos en el tiempo, la dificultad de la prueba de trabajo es determinada por una media móvil dirigida por un número promedio de bloques a la hora. Si estos se generan muy rápido, la dificultad se incrementa.
5. La red
Los pasos que ejecuta la red son los siguientes:
- Las transacciones nuevas son emitidas a todos los nodos.
- Cada nodo recolecta nuevas transacciones en un bloque.
- Cada nodo trabaja en encontrar una prueba de trabajo difícil para su bloque.
- Cuando un nodo encuentra una prueba de trabajo, emite el bloque a todos los nodos.
- Los nodos aceptan el bloque si todas las transacciones en el bloque son válidas y no se han gastado ya.
- Los nodos expresan su aceptación del bloque al trabajar en crear el próximo bloque en la cadena, utilizando el hash del bloque aceptado como hash previo.
Los nodos siempre consideran la cadena más larga como la correcta y empiezan a trabajar en extenderla. Si dos nodos emiten versiones diferentes del próximo bloque simultáneamente, algunos nodos puede que reciban uno o el otro primero. En ese caso, trabajan en el primero que reciban, pero guardan la otra rama en caso de que esta se vuelva más larga. El empate se rompe cuando se encuentra la próxima prueba de trabajo y una rama se vuelve más larga; los nodos que estaban trabajando en la otra rama posteriormente se cambian a la que ahora es más larga.
Las emisiones de nuevas transacciones no necesariamente necesitan llegar a todos los nodos. En el momento que estas lleguen a muchos nodos, acabaran entrando en un bloque antes de que pase mucho tiempo. La emisión de los bloques también es tolerante a la pérdida de mensajes. Si un nodo no recibe un bloque, lo pedirá cuando reciba el próximo bloque y se dé cuenta que perdió uno.
6. Incentivo
Por convención, la primera transacción en el bloque es una transacción especial que genera una nueva moneda cuyo dueño es el creador del bloque. Esto agrega un incentivo para que los nodos apoyen a la red, y provee una forma inicial de distribuir y poner en circulación las monedas, dado que no hay una autoridad para crearlas. Esta adición estable de una cantidad constante de monedas nuevas es análoga a los mineros de oro que gastan recursos para ponerlo en circulación. En nuestro caso, los recursos son el tiempo de CPU y la electricidad que se gastan.
El incentivo también puede establecerse con los costes de transacción. Si el valor de salida de una transacción es menor que la entrada, la diferencia será una tarifa de transacción que se añadirá al valor del incentivo del bloque que la contiene. Una vez que un número predeterminado de monedas han entrado en circulación, el incentivo puede evolucionar enteramente a tarifas de transacción y estar completamente libres de inflación.
El incentivo también puede ayudar a animar a los nodos a mantenerse honestos. Si un atacante egoísta es capaz de reunir más potencia de CPU que todos los nodos honestos, este tendría que elegir entre utilizarlo para defraudar a la gente robando sus pagos, o usarlo para generar monedas nuevas. Debería encontrar más rentable jugar siguiendo las reglas, ya que estas lo favorecerán con más monedas que combinar a todos los demás nodos, que socavar el sistema y la validez de su propia riqueza.
7. Reclamando Espacio en Disco
Una vez que la última transacción está enterrada bajo suficientes bloques, las transacciones gastadas anteriores a esta pueden ser descartadas para ahorrar espacio en disco. Para facilitar esto sin romper el hash del bloque, las transacciones se comprueban en un árbol de Merkle [7] [2] [5], con solo la raíz incluida en el hash del bloque. Los bloques viejos pueden compactarse al sacar ramas del árbol. Los hashes interiores no necesitan ser guardados.
La cabecera de un bloque sin transacciones será de unos 80 bytes. Si suponemos que cada bloque se genera cada 10 minutos, 80 bytes * 6 * 24 * 365 = 4.2MB por año. Con ordenadores vendiéndose generalmente con 2GB de RAM en 2008, y la ley de Moore prediciendo un crecimiento actual de 1.2GB por año, el almacenamiento no debe ser un problema aun si las cabeceras de los bloques deben permanecer en memoria.
8. Verificación de Pagos Simplificada
Es posible verificar pagos sin ejecutar un nodo de red completo. Un usuario solo necesita mantener una copia de las cabeceras de los bloques de la cadena más larga de la prueba de trabajo, la cuál puede obtenerse haciendo una búsqueda en los nodos de la red hasta que esté convencido de tener la cadena más larga, y obtener la rama del árbol de Merkle, que enlaza la transacción con el bloque en que ha sido fechado. Aunque no puede verificar la transacción por sí mismo, al enlazarla a algún lugar de la cadena, puede ver que algún nodo de la red la ha aceptado, de modo que los bloques añadidos después confirmarían aún más esta aceptación por parte de la red.
Como tal, la verificación es confiable a medida que los nodos honestos controlen la red, pero se vuelve más vulnerable si la red es dominada por un atacante. Mientras que los nodos de la red puedan verificar las transacciones por sí mismos, el método simplificado puede ser engañado por transacciones fabricadas por un atacante mientras este pueda dominar la red. Una estrategia para protegerse es aceptar alertas de los nodos de la red cuando detecten un bloque inválido, pidiéndole al usuario que se baje el bloque completo y las transacciones alertadas para confirmar la inconsistencia. Los negocios que frecuentemente reciban pagos querrán ejecutar sus propios nodos para tener una seguridad más independiente y una verificación más rápida.
9. Combinando y Dividiendo Valor
Aunque sería posible manipular monedas individualmente, seria difícil de manejar el hacer transacciones separadas por cada céntimo de una transferencia. Para permitir que el valor se divida y se combine, las transacciones contienen múltiples entradas y salidas. Normalmente habrá, o una sola entrada de una transacción previa más grande, o múltiples entradas combinando cantidades más pequeñas, y al menos dos salidas: una para el pago, y una para devolver el cambio, si es que hay alguno, de vuelta al emisor.
Hay que tener en cuenta que este sistema se abre en abanico, de modo que una transacción puede depender de varias transacciones, y esas a su vez depender de muchas más, lo que no es ningún problema. Nunca existe la necesidad de extraer una copia completa única de la historia de las transacciones.
10. Privacidad
El modelo bancario tradicional logra su nivel de privacidad al limitar el acceso a la información a las partes involucradas y al tercero de confianza. La necesidad de anunciar todas las transacciones públicamente se opone a este método, pero la privacidad aún puede mantenerse rompiendo el flujo de información en otro lugar: manteniendo las claves públicas anónimas. Públicamente puede verse que alguien está enviando una cierta cantidad a otra persona, pero sin información que relacione la transacción con nadie en particular. Esto es similar al nivel de información que se muestra en las bolsas de valores, donde el tiempo y el tamaño de las transacciones individuales, la “cinta”, son públicos, pero sin decir quienes son las partes.
Como un cortafuegos adicional, un nuevo par de claves debe utilizarse para cada transacción de modo que puedan asociarse a un dueño en común. Son inevitables algunos tipos de asociación con transacciones de múltiples entradas, las cuáles pueden revelar que sus entradas pertenecen al mismo dueño. El riesgo estaría en que, si el dueño de una clave se revela, entonces el enlazado podría revelar otras transacciones que pertenecieron al mismo dueño.
11. Cálculos
Consideramos el escenario en el que un atacante intenta generar una cadena alterna más rápido que la cadena honesta. Aun si esto se lograse, no abriría el sistema a cambios arbitrarios, tales como crear valor del aire o tomar dinero que nunca perteneció al atacante. Los nodos no aceptarían una transacción inválida como pago, y los nodos honestos nunca aceptaran un bloque que las contenga. Un atacante puede únicamente intentar cambiar solo sus propias transacciones para retomar dinero que ha gastado recientemente.
La carrera entre una cadena honesta y la cadena de un atacante puede ser caracterizada como un Camino Binomial Aleatorio. El evento de éxito es la cadena honesta siendo extendida en un bloque adicional e incrementado su ventaja en +1, y siendo el evento de fracaso que la cadena del atacante sea extendida en un bloque reduciendo la distancia en -1.
La probabilidad de que un atacante pueda alcanzarnos, desde un déficit dado, es análogo al problema de la Ruina del Jugador. Supóngase que un jugador con crédito ilimitado empieza en déficit y juega potencialmente un número infinito de intentos para intentar llegar a un punto de equilibrio. Podemos calcular la probabilidad de que llegase al punto de equilibrio, o que llegue a alcanzar a la cadena honesta, como sigue [8]:
Dada nuestra hipótesis de que p > q, la probabilidad cae exponencialmente mientras que el número de bloques que el atacante debe alcanzar, incrementa. Con las probabilidades en contra, si no hace una jugada afortunada desde el principio, sus oportunidades se vuelven extremadamente pequeñas a medida que se queda más atrás.
Ahora consideremos cuánto necesita esperar el beneficiario de una nueva transacción antes de tener la certeza suficiente de que el emisor no puede cambiarla. Asumimos que el emisor es un atacante el cuál quiere hacer creer al beneficiario que se le pagó durante un rato, y luego cambiar la transacción para pagarse a sí mismo de vuelta una vez que ha pasado un tiempo. El beneficiario será alertado cuando esto suceda, pero el emisor espera que sea demasiado tarde.
El beneficiario genera un nuevo par de claves y entrega la clave pública al emisor poco después de hacer la firma. Esto previene que el emisor prepare una cadena de bloques antes de tiempo, y pueda estar trabajando en ella continuamente hasta que tenga la suerte de adelantarse lo suficiente, y luego ejecutar la transacción en ese momento. Una vez que la transacción es enviada, el emisor deshonesto empieza a trabajar en secreto en una cadena paralela que contiene una versión alterna de su transacción.
El beneficiario espera a que la transacción sea añadida a un bloque y que z bloques hayan sido enlazados después de la transacción. No necesitará saber la cantidad exacta de progreso que ha logrado el atacante, pero asumiendo que los bloques honestos tardaron el promedio esperado por bloque, el progreso potencial del atacante será una distribución de Poisson con un valor esperado de:
Para obtener la probabilidad de que el atacante aún pueda alcanzarnos ahora, multiplicamos la densidad de Poisson de la cantidad de progreso que pudo haber hecho por la probabilidad de que pudiera alcanzar ese punto:
Re-organizamos para evitar sumar de la cola infinita de la distribución…
Convertimos a código en C…
Ejecutamos algunos resultados, podemos ver que la probabilidad cae exponencialmente con z.
Resolvemos para P menor que 0.1%…
12. Conclusión
Hemos propuesto un sistema para transacciones electrónicas sin depender en la confianza. Comenzamos con el marco habitual de monedas hechas de firmas digitales, lo que proporciona un fuerte control de propiedad, pero está incompleto sin una manera de evitar el doble gasto. Para resolver esto, propusimos una red de igual-a-igual, utilizando prueba de trabajo para registrar un historial público de transacciones que, rápidamente, se vuelve computacional impráctico de cambiar para un atacante si los nodos honestos controlan la mayoría de la potencia de CPU. La red es robusta en su simpleza desestructurada. Los nodos trabajan todos a la vez con poca coordinación. Ellos no necesitan ser identificados, ya que los mensajes no se envían a ningún lugar en particular y solo deben ser entregados en base al mejor esfuerzo. Los nodos pueden abandonar y volver a unirse a la red a voluntad, aceptando la cadena de prueba de trabajo como prueba de lo que sucedió mientras estaban fuera. Ellos votan con su poder de CPU, expresando su aceptación de bloques válidos al trabajar en extenderlos y rechazando bloques inválidos al rehusarse a trabajar en ellos. Cualquier regla e incentivo necesarios pueden ser impuestos con este mecanismo de consenso.
Referencias
[1] W. Dai, “b-money,” http://www.weidai.com/bmoney.txt, 1998.
[2] 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.
[3] S. Haber, W.S. Stornetta, “How to time-stamp a digital document,” In Journal of Cryptology, vol 3, no 2, pages 99-111, 1991.
[4] 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.
[5] 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.
[6] A. Back, “Hashcash – a denial of service counter measure,” http://www.hashcash.org/papers/hashcash.pdf, 2002.