SKILLCASHTools

1 Introducción

El comercio en Internet ha llegado a depender casi exclusivamente de instituciones financieras que actúan como terceros de confianza para procesar pagos electrónicos. Si bien el sistema funciona razonablemente bien para la mayoría de las transacciones, sigue sufriendo las debilidades inherentes del modelo basado en confianza. Las transacciones completamente irreversibles no son realmente posibles, ya que las instituciones financieras no pueden evitar mediar en disputas. El costo de esa mediación aumenta los costos de transacción, limitando el tamaño práctico mínimo de las transacciones y cortando de raíz la posibilidad de pequeñas transacciones casuales — y existe un costo más amplio en la pérdida de la capacidad de hacer pagos irreversibles por servicios irreversibles. Con la posibilidad de reversión, la necesidad de confianza se extiende: los comerciantes deben desconfiar de sus clientes, molestándolos para pedir más información de la que de otro modo necesitarían. Cierto porcentaje de fraude se acepta como inevitable. Estos costos y la incertidumbre de los pagos pueden evitarse en persona usando efectivo físico, pero no existe ningún mecanismo para hacer pagos a través de un canal de comunicación sin un tercero de confianza.

Lo que se necesita es un sistema de efectivo electrónico basado en prueba criptográfica en lugar de confianza, que permita a dos partes dispuestas transar directamente entre sí sin necesidad de un tercero de confianza. Las transacciones que son computacionalmente poco prácticas de revertir protegerían a los vendedores del fraude, y mecanismos de depósito en garantía de rutina podrían implementarse fácilmente para proteger a los compradores. En este artículo proponemos una solución al problema del doble gasto usando un servidor de marcas de tiempo distribuido entre pares, que genera prueba computacional del orden cronológico de las transacciones. El sistema es seguro mientras los nodos honestos controlen colectivamente más poder de cómputo que cualquier grupo cooperante de nodos atacantes.

2 Transacciones

Definimos una moneda electrónica como una cadena de firmas digitales. Cada propietario transfiere la moneda al siguiente firmando digitalmente un hash de la transacción anterior y la clave pública del siguiente propietario, y agregando estos al final de la moneda. Un beneficiario puede verificar las firmas para comprobar la cadena de propiedad.

El problema, por supuesto, es que el beneficiario no puede verificar que uno de los propietarios no haya gastado la moneda dos veces. Una solución común es introducir una autoridad central de confianza, o "casa de moneda", que verifique cada transacción en busca de doble gasto. Después de cada transacción, la moneda debe devolverse a la casa de moneda para acuñar una nueva moneda, y solo las monedas emitidas directamente por ella son de confianza. El problema de esta solución es que el destino de todo el sistema monetario depende de la empresa que opera la casa de moneda, con cada transacción teniendo que pasar por ella, igual que un banco.

Necesitamos una manera de que el beneficiario sepa que los propietarios anteriores no firmaron ninguna transacción anterior. A nuestros efectos, la transacción más antigua es la que cuenta, así que no nos importan los intentos posteriores de doble gasto. La única manera de confirmar la ausencia de una transacción es estar al tanto de todas las transacciones. En el modelo de la casa de moneda, ella estaba al tanto de todas las transacciones y decidía cuál llegó primero. Para lograr esto sin un tercero de confianza, las transacciones deben anunciarse públicamente, y necesitamos un sistema para que los participantes se pongan de acuerdo sobre un único historial en el orden en que se recibieron. El beneficiario necesita prueba de que, en el momento de cada transacción, la mayoría de los nodos acordó que fue la primera recibida.

3 Servidor de Marcas de Tiempo

La solución que proponemos comienza con un servidor de marcas de tiempo (timestamp server). Un servidor de este tipo funciona tomando el hash de un bloque de elementos a marcar y publicando ampliamente ese hash — como en un periódico o en un post de Usenet. La marca de tiempo prueba que los datos debieron haber existido en ese momento, obviamente, para poder entrar al hash. Cada marca de tiempo incluye la marca de tiempo anterior en su propio hash, formando una cadena, con cada marca adicional reforzando a las que vinieron antes.

4 Prueba de Trabajo

Para implementar un servidor de marcas de tiempo distribuido entre pares, necesitamos usar un sistema de prueba de trabajo similar al Hashcash de Adam Back, en lugar de un periódico o un post de Usenet. La prueba de trabajo consiste en buscar un valor que, al ser hasheado (por ejemplo con SHA-256), el hash comience con un número determinado de bits en cero. El trabajo promedio requerido es exponencial en el número de bits en cero exigidos, y puede verificarse ejecutando un único hash.

Para nuestra red de marcas de tiempo, implementamos la prueba de trabajo incrementando un nonce en el bloque hasta encontrar un valor que le dé al hash del bloque los bits en cero requeridos. Una vez que se gasta el esfuerzo de cómputo para satisfacer la prueba de trabajo, el bloque no puede modificarse sin rehacer ese trabajo. Como los bloques posteriores se encadenan después de él, el trabajo para modificar un bloque incluiría rehacer 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 "un IP, un voto", podría ser subvertida por cualquiera capaz de asignarse muchas IPs. La prueba de trabajo es esencialmente "una CPU, un voto". La decisión de la mayoría está representada por la cadena más larga, en la que se ha invertido el mayor esfuerzo de prueba de trabajo. Si la mayoría del poder de cómputo está controlada por nodos honestos, la cadena honesta crecerá más rápido y superará a cualquier cadena competidora. Para modificar un bloque pasado, un atacante tendría que rehacer la prueba de trabajo de ese bloque y de todos los posteriores, y luego alcanzar y superar el trabajo de los nodos honestos — y esa probabilidad disminuye exponencialmente a medida que se agregan más bloques.

Para compensar el aumento en la velocidad del hardware y el interés variable en ejecutar nodos con el tiempo, la dificultad de la prueba de trabajo se determina mediante un promedio móvil que apunta a un número promedio de bloques por hora: si se generan demasiado rápido, la dificultad aumenta.

5 Red

Los pasos para operar la red son los siguientes:

1) Las nuevas transacciones se difunden a todos los nodos.
2) Cada nodo recolecta las nuevas transacciones en un bloque.
3) Cada nodo trabaja en encontrar una prueba de trabajo difícil para su bloque.
4) Cuando un nodo encuentra una prueba de trabajo, difunde el bloque a todos los nodos.
5) Los nodos aceptan el bloque solo si todas las transacciones en él son válidas y no han sido gastadas antes.
6) Los nodos expresan su aceptación trabajando en crear el siguiente bloque de la cadena, usando el hash del bloque aceptado como el hash anterior.

Los nodos siempre consideran que la cadena más larga es la correcta y seguirán trabajando para extenderla. Si dos nodos difunden versiones diferentes del siguiente bloque simultáneamente, algunos nodos pueden recibir una primero; en ese caso trabajan en la primera que recibieron, pero guardan la otra rama por si se vuelve más larga. El empate se rompe cuando se encuentra la siguiente prueba de trabajo y una de las ramas se vuelve más larga; los nodos que trabajaban en la otra rama cambian entonces a la más larga.

Las nuevas transmisiones de transacciones no necesariamente tienen que llegar a todos los nodos: mientras lleguen a muchos, entrarán en un bloque en poco tiempo. Las transmisiones de bloques también toleran mensajes perdidos — si un nodo no recibe un bloque, lo pedirá al recibir el siguiente y darse cuenta de que se perdió uno.

6 Incentivo

Por convención, la primera transacción en un bloque es una transacción especial que inicia una nueva moneda propiedad del creador del bloque. Esto añade un incentivo para que los nodos apoyen la red, y provee una manera de poner monedas en circulación inicialmente, ya que no hay ninguna autoridad central que las emita. La adición constante de una cantidad fija de nuevas monedas es análoga a los mineros de oro que gastan recursos para agregar oro a la circulación — en nuestro caso, es tiempo de CPU y electricidad lo que se gasta.

El incentivo también puede financiarse con comisiones de transacción: si el valor de salida de una transacción es menor que su valor de entrada, la diferencia es una comisión que se añade al valor de incentivo del bloque que la contiene. Una vez que un número predeterminado de monedas haya entrado en circulación, el incentivo puede transicionar completamente a comisiones de transacción y estar totalmente libre de inflación.

El incentivo también puede ayudar a alentar a los nodos a mantenerse honestos. Si un atacante codicioso lograra reunir más poder de cómputo que todos los nodos honestos juntos, tendría que elegir entre usarlo para defraudar a la gente robándole sus pagos, o usarlo para generar nuevas monedas. Debería encontrarle más rentable jugar según las reglas — reglas que lo favorecen con más monedas nuevas que todos los demás combinados — en vez de socavar el sistema y la validez de su propia riqueza.

7 Recuperación de Espacio en Disco

Una vez que la transacción más reciente de una moneda está enterrada bajo suficientes bloques, las transacciones gastadas antes de ella pueden descartarse para ahorrar espacio en disco. Para facilitar esto sin romper el hash del bloque, las transacciones se hashean en un árbol de Merkle, con solo la raíz incluida en el hash del bloque. Los bloques antiguos pueden entonces compactarse podando ramas del árbol — no es necesario almacenar los hashes internos.

El encabezado de un bloque sin transacciones pesaría alrededor de 80 bytes. Si suponemos que los bloques se generan cada diez minutos, 80 bytes × 6 × 24 × 365 = 4.2 MB por año. Con los sistemas de computadoras típicos vendidos en 2008 con 2 GB de RAM, y con la Ley de Moore prediciendo un crecimiento de 1.2 GB por año, el almacenamiento no debería ser un problema incluso si los encabezados de los bloques deben mantenerse en memoria.

8 Verificación de Pagos Simplificada

Es posible verificar los pagos sin ejecutar un nodo de red completo. Un usuario solo necesita conservar una copia de los encabezados de bloque de la cadena de prueba de trabajo más larga, que puede obtener consultando a los nodos de la red hasta convencerse de que tiene la cadena más larga, y obtener la rama de Merkle que enlaza la transacción con el bloque en el que se marcó con fecha y hora. No puede verificar la transacción por sí mismo, pero al enlazarla con un lugar en la cadena, puede ver que un nodo de la red la ha aceptado, y los bloques añadidos después confirman que la red la ha aceptado.

Como tal, la verificación es confiable mientras los nodos honestos controlen la red, pero es más vulnerable si la red es dominada por un atacante. Mientras que los nodos de la red pueden verificar las transacciones por sí mismos, el método simplificado puede ser engañado por transacciones fabricadas de un atacante mientras este siga pudiendo superar a la red. Una estrategia para protegerse de esto sería aceptar alertas de los nodos de la red cuando detecten un bloque inválido, incitando al software del usuario a descargar el bloque completo y las transacciones alertadas para confirmar la inconsistencia. Los negocios que reciben pagos frecuentes probablemente aún querrán operar sus propios nodos para una seguridad más independiente y una verificación más rápida.

9 Combinación y División de Valor

Aunque sería posible manejar monedas individualmente, sería incómodo hacer una transacción separada por cada céntimo en una transferencia. Para permitir que el valor se divida y combine, las transacciones contienen múltiples entradas y salidas. Normalmente habrá una sola entrada de una transacción anterior más grande, o múltiples entradas combinando cantidades más pequeñas, y como máximo dos salidas: una para el pago, y una devolviendo el cambio, si lo hay, de vuelta al emisor.

Cabe señalar que la "propagación" (fan-out), donde una transacción depende de varias transacciones y esas de muchas más, no es un problema aquí: nunca hay necesidad de extraer una copia completa e independiente del historial de una transacción.

10 Privacidad

El modelo bancario tradicional logra un nivel de privacidad al limitar el acceso a la información a las partes involucradas y al tercero de confianza. La necesidad de anunciar públicamente todas las transacciones descarta 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. El público puede ver que alguien le envía una cantidad a otro alguien, pero sin información que vincule la transacción a nadie — similar al nivel de información publicado por las bolsas de valores, donde se da a conocer el momento y el tamaño de las operaciones individuales sin decir quiénes fueron las partes.

Como salvaguarda adicional, se debería usar un nuevo par de claves para cada transacción, para evitar que se las vincule a un propietario común. Es inevitable cierto enlace en transacciones con múltiples entradas, ya que necesariamente revelan que esas entradas pertenecían al mismo propietario. El riesgo es que si se revela el propietario de una clave, el enlace podría revelar otras transacciones que pertenecían al mismo propietario.

11 Cálculos

Consideramos el escenario de un atacante tratando de generar una cadena alternativa más rápido 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 perteneció al atacante: los nodos no aceptarán una transacción inválida como pago, y los nodos honestos nunca aceptarán un bloque que las contenga. Un atacante solo puede intentar cambiar una de sus propias transacciones para recuperar dinero que gastó recientemente.

La carrera entre la cadena honesta y la de un atacante puede modelarse como una Caminata Aleatoria Binaria: el evento de "éxito" es que la cadena honesta se extienda un bloque (+1), y el de "fracaso" es que la cadena del atacante se extienda un bloque (−1). La probabilidad de que el atacante alcance a la cadena honesta desde un déficit de z bloques es análoga al clásico Problema de la Ruina del Apostador:

donde p es la probabilidad de que un nodo honesto encuentre el siguiente bloque y q la de que lo encuentre el atacante. Dada nuestra suposición de que p > q, la probabilidad disminuye exponencialmente a medida que aumenta el número de bloques que el atacante debe recuperar. Con las probabilidades en su contra, si no tiene un golpe de suerte temprano que lo adelante, sus posibilidades se vuelven insignificantes a medida que cae más y más atrás.

Esto lleva a la pregunta de cuánto debe esperar el receptor de una nueva transacción antes de estar suficientemente seguro de que el emisor no puede revertirla. El receptor espera hasta que la transacción se haya agregado a un bloque y z bloques se hayan enlazado después. Asumiendo que los bloques honestos tomaron el tiempo promedio esperado por bloque, el progreso potencial del atacante sigue una distribución de Poisson con valor esperado:

12 Conclusión

Hemos propuesto un sistema para transacciones electrónicas que no depende de la confianza. Comenzamos con el marco habitual de monedas hechas de firmas digitales, que provee un control fuerte sobre la propiedad, pero que es incompleto sin una manera de evitar el doble gasto. Para resolver esto, propusimos una red entre pares usando prueba de trabajo para registrar un historial público de transacciones que rápidamente se vuelve computacionalmente impráctico de modificar para un atacante, si los nodos honestos controlan la mayoría del poder de cómputo.

La red es robusta en su simplicidad no estructurada: los nodos trabajan todos a la vez con poca coordinación, no necesitan ser identificados, y los mensajes solo necesitan entregarse con el mejor esfuerzo posible. Los nodos pueden salir y volver a unirse a la red a voluntad, aceptando la cadena de prueba de trabajo como prueba de lo que pasó mientras estuvieron ausentes. Votan con su poder de cómputo, expresando su aceptación de bloques válidos trabajando en extenderlos y rechazando los inválidos al negarse a trabajar en ellos. Cualquier regla y los incentivos necesarios pueden hacerse cumplir con este mecanismo de consenso.

↳ Referencias

1. W. Dai, "b-money", lista de correo de cypherpunks, 1998.
2. H. Massias, X.S. Avila y J.-J. Quisquater, "Diseño de un sistema seguro de marcas de tiempo con requisitos mínimos de confianza", 20º Simposio sobre Teoría de la Información en el Benelux, 1999.
3. S. Haber y W.S. Stornetta, "Cómo poner fecha y hora a un documento digital", Journal of Cryptology, vol. 3, n.º 2, pp. 99–111, 1991.
4. D. Bayer, S. Haber y W.S. Stornetta, "Mejorando la eficiencia y confiabilidad del marcado de tiempo digital", en Sequences II: Methods in Communication, Security and Computer Science, pp. 329–334, 1993.
5. S. Haber y W.S. Stornetta, "Marcado de tiempo seguro de nombres", Proceedings of the 4th ACM Conference on Computer and Communications Security, pp. 28–35, 1997.
6. A. Back, "Hashcash — una medida contra el abuso", 2002.
7. R.C. Merkle, "Protocolos para criptosistemas de clave pública", Proceedings of the 1980 Symposium on Security and Privacy, IEEE Computer Society, pp. 122–133, 1980.
8. W. Feller, "Una introducción a la teoría de la probabilidad y sus aplicaciones", 1957.