Actualizado: 4 de agosto de 2023
Por Suthan Somadeva y Michael Burke
Introducción a ECDSA vs RSA
La creación de un contrato que otorga permisos a ciertas direcciones recibe varios nombres: airdrops, presales, whitelists, allowlists, entre otros. Pero la esencia de la idea es que hay un conjunto de direcciones que tienen un permiso especial para comprar un token de alta demanda por un precio atractivo (a veces gratis).
Existen tres soluciones establecidas para esto: mappings, Árboles de Merkle y firmas ECDSA.
Los méritos relativos de estos enfoques ya han sido discutidos en otros lugares, por lo que resumiremos los resultados:
- Verificación de firma ECDSA (Gas: 29,293)
- Uso de pruebas de Merkle (Gas: 30, 517, 128 direcciones)
Una presale basada en mapping funciona cuando el vendedor introduce las direcciones de los clientes en un mapping que va de dirección a booleano para indicar si la dirección tiene privilegios o no. El mapping se establece en false después de que el comprador completa la transacción. Esto asegura que solo las direcciones que están marcadas como true puedan realizar una compra. Esto es muy eficiente en términos de gas para el comprador, pero el vendedor podría gastar millones de gas añadiendo miles de direcciones a la allowlist (costará al menos 22,100 de gas añadir una dirección a la allowlist).
Debido a esto, los Árboles de Merkle y las firmas ECDSA (usando el precompile de ethereum ecerecover, o mejor aún, el wrapper más seguro a su alrededor publicado por OpenZeppelin), a menudo se prefieren a los mappings. El costo de gas (para el comprador) de ejecutar la verificación de la firma ECDSA es de 29,293 de gas. Esto incluye los 21,000 para iniciar la transacción, por lo que el costo de ECDSA es de 8,293. Ten en cuenta que esto incluye leer la dirección firmante desde el storage, pero este costo es necesario o no podremos invalidar las firmas.
Los Árboles de Merkle varían en costo según el tamaño del árbol (los árboles más grandes requieren pruebas de Merkle más grandes), pero si hay más de 1,000 direcciones en el Árbol de Merkle, costará al menos 32,000 de gas (o más) verificar la dirección. Este costo es claramente inferior al de ECDSA.
El objetivo entonces, es superar a ECDSA, el cual cuesta 8,293 de gas. Para mantener una comparación justa, la solución alternativa debe:
- Ser capaz de anular direcciones en la allowlist. Los Árboles de Merkle pueden cambiar su raíz, ECDSA puede cambiar su dirección de firma y los mappings pueden establecer el valor en false.
- No imponer una carga de costo sustancial sobre el vendedor como lo hacen los mappings.
- Costar menos de 8,200 de gas para el comprador (incluyendo una carga desde storage).
- No ver comprometida su seguridad.
Prerrequisitos
Para entender la metodología propuesta, el lector debe estar familiarizado con los siguientes temas:
- Contratos inteligentes precompilados (lectura recomendada, stackexchange)
- Contratos metamórficos (introducción, lectura recomendada)
- Listas de acceso (lectura recomendada)
- Cómo usar firmas digitales y sus casos de uso apropiados en aplicaciones blockchain.
- Cómo se calcula el costo del gas, especialmente en lo que respecta al uso de calldata, opcodes, storage y memoria.
El Algoritmo RSA
Si queremos superar sustancialmente a ECDSA, necesitamos encontrar un algoritmo criptográfico diferente que permita la prueba de pertenencia a un conjunto. ECDSA es en realidad la versión más nueva de la firma digital original, RSA. ECDSA se basa en que los logaritmos discretos sobre curvas elípticas sean difíciles (de ahí el nombre: algoritmo de firma digital de curva elíptica). RSA (nombrado así por sus autores, Rivest, Shamir, Adleman) se basa en que los enteros grandes sean difíciles de factorizar. En términos de antigüedad, RSA se publicó en la década de 1970, pero ECDSA se convirtió en una especificación formal a principios de la década de 2000.
El Almirante Piett aprueba la criptografía RSA
No explicaremos RSA en detalle aquí, pero algunos conocimientos previos son necesarios.
El firmante elige dos números primos grandes p y q, y los multiplica entre sí para producir n. Este n es la primera parte de la clave pública. En segundo lugar, el firmante elige un número primo pequeño e (puede codificarse de forma fija a 3 para nuestro caso de uso), y publica el par (n, e) como la clave pública. Detrás de escena, el firmante calcula
t = (p - 1) * (q - 1)
d = t^(-1) % n
El número d es la clave privada. Si un adversario pudiera descomponer n en p y q, entonces calcular d sería trivial. Pero se sabe que la factorización de enteros es difícil. Para firmar un mensaje, el firmante realiza un hash del mensaje m para obtener h y eleva h a la potencia d. Es decir,
s = h(m) ^ d % n
Luego, el firmante publica (m, s) como el mensaje y la firma.
El verificador luego aplica un hash a m y lo eleva a la potencia e mod n. Recuerda, e y n son la clave pública. Si y solo si
s == s ^ e % n
entonces la firma es válida para la clave pública (n, e). Ten en cuenta que si n es extremadamente grande, la probabilidad de que s == s ^ e % n por pura casualidad es infinitamente pequeña. Si la igualdad se verifica, entonces sabemos que la firma es válida para la clave pública.
Para hacer esto en Ethereum, simplemente firmaríamos una dirección como
s = buyerAddress ^ d % n
y el contrato inteligente verificaría
msg.sender == s ^ e % n
Usar solo 256 bits es inseguro
Decimos que “factorizar enteros es difícil”, pero claramente esto implica que el número debe ser lo suficientemente grande. Por ejemplo, 33 se compone de dos números primos y es trivial de descomponer. Afortunadamente, tenemos benchmarks del mundo real sobre lo que puede lograr el estado del arte en el RSA Factoring Challenge.
Para aclarar, la cantidad de “bits” se refiere al tamaño de la clave pública. Por lo tanto, cuando decimos “RSA 2048”, esto significa que el número n, el módulo, tiene 2048 bits. Al comparar los tamaños de clave, es importante recordar que cada bit adicional duplica el tamaño del número. Así que 700 bits es exponencialmente más seguro que 350 bits, no el doble de seguro.
La clave más grande en ser descifrada (factorizada) hasta ahora tenía 829 bits, y se requirió una supercomputadora moderna para hacerlo. El equipo utilizó aproximadamente 2700 años-núcleo de CPU, usando una CPU Intel Xeon Gold 6130 a 2.1 GHz. La CPU de 16 núcleos más barata en AWS cuesta $0.40 centavos por hora, por lo que el costo de descifrar esta clave es del orden de los $9.4 millones de dólares. Incluso asumiendo generosos descuentos del proveedor de la nube, el costo es de millones.
Aritmética modular con más de 256 bits en Solidity
Ethereum solo soporta tipos de datos de 32 bytes, por lo que, por defecto, no podemos llevar a cabo
s ^ e % n
Afortunadamente, la blockchain de Ethereum añadió un contrato precompilado en el EIP 198 específicamente para soportar aritmética modular. Para usarlo, la base, el exponente y el módulo deben cargarse en memoria en formato abi encoded. Luego se invoca el contrato que reside en la dirección 0x05.
Almacenar la clave pública se convierte en un pequeño problema si usas una cantidad segura de bits. Si el tamaño de la clave es de 1024 bits, esto requiere 4 ranuras de storage. Leer la clave pública desde storage requeriría cuatro operaciones SLOAD, para un total de 8,400 de gas. Esto por sí solo ya es menos eficiente que la solución ECDSA evaluada anteriormente.
Si usamos variables inmutables, este costo se elimina en gran medida, pero esto crea una debilidad si no podemos eliminar retroactivamente a alguien de la presale. En el enfoque tradicional de ECDSA o Árboles de Merkle, simplemente reemplazaríamos la dirección de firma o el Merkle Root. Esto no es posible si usamos una variable inmutable.
Sin embargo, almacenar la clave pública en el bytecode en lugar de en el storage es la idea clave. Leer el bytecode de un contrato externo (EXTCODECOPY) cuesta 2,600 de gas, lo cual es mucho menos que los 8,400 de gas por leer cada parte de la clave pública en cuatro fragmentos.
Para invalidar una clave pública, simplemente podríamos crear un nuevo contrato y actualizar una variable de storage para que apunte a la nueva dirección. Pero eso vuelve a añadir 2,100 de gas adicionales.
Resulta que es posible almacenar la dirección del contrato externo (cuyo bytecode almacena la clave pública) en una variable inmutable, pero aún así invalidar la clave pública mutando el bytecode del contrato inteligente externo.
Invalidando la clave pública con el patrón de contrato metamórfico
Un contrato inteligente se crea cargando el deployment bytecode en memoria, para luego devolver el rango del bytecode que contiene el runtime code.
Cuando un contrato inteligente se crea con el comando create2, la dirección del contrato se puede predecir de antemano. La dirección se calcula a partir de la combinación de un salt, el deployer y el initialization bytecode. Si el contrato se autodestruye (selfdestructs), entonces se puede desplegar un nuevo contrato en la misma dirección.
Ten en cuenta que la dirección es una función del código de inicialización, no del código desplegado. Es posible desplegar un bytecode diferente haciendo que el código de inicialización cargue un runtime code distinto. Al autodestruirse y volver a desplegarse con el mismo código de inicialización pero un código de despliegue diferente, el bytecode del contrato puede mutar.
Por lo tanto, podemos tener un contrato inteligente cuyos primeros k bytes son para autodestruirse bajo una cierta condición, pero el resto de los bytes son simplemente la clave pública RSA.
Como la dirección se determina de antemano, podemos almacenar la dirección de este contrato metamórfico en una variable inmutable. Podemos hacer EXTCODECOPY desde esa dirección cuando necesitemos la clave pública. Para reemplazar la clave pública, le indicamos al contrato que se autodestruya y luego desplegamos un nuevo contrato en esa dirección.
Ahorrando 100 de gas adicional con listas de acceso
El EIP 2930 añadió un nuevo tipo de transacción que permite al usuario especificar de antemano a qué direcciones y ranuras de storage se accederá. Esto permite que los nodos pre-obtengan esos valores desde el storage, acelerando así el tiempo de ejecución. Usar una transacción con lista de acceso al llamar a un contrato externo puede ahorrar 100 de gas. Ten en cuenta que este ahorro no se aplica cuando un contrato inteligente accede a su propia variable de storage. Debido a que este diseño de airdrop de presale RSA se basa en un contrato externo para almacenar la clave pública, el uso de una lista de acceso es apropiado.
Benchmarks: Costo de gas vs tamaño de clave
La mayor parte del costo de gas proviene de tener un calldata muy grande como resultado de firmas grandes. Si el tamaño de la clave se establece en 1024 bits, entonces el calldata será de 128 bytes. Cada byte cuesta 16 de gas, por lo que el costo total de gas solo por tener un calldata tan grande es de 2,048 de gas.
En comparación con la mayoría de los demás casos de uso, el nuestro usa una cantidad considerable de memoria y Ethereum cobra por ello.
Por qué esto ahorra gas en relación a ECDSA
Los benchmarks dejan en claro que cuanto más grande es la clave (y por tanto la firma), mayor es el costo de gas. Nuestro diseño explota el hecho de que el precompile asigna un precio bajo a elevar números a una potencia baja. El costo de ejecutar el contrato precompilado bajo esas condiciones en 0x05 es de solo unos pocos cientos de gas en comparación con miles por ejecutar el precompile para ECDSA.
Eligiendo un tamaño de clave
Aunque se ha logrado factorizar una clave de 829 bits, esto requiere una supercomputadora moderna para lograrlo. Para aplicaciones como realizar airdrops de tokens de menor valor o poner NFTs en presale, un atacante no tiene incentivos para gastar entre seis cifras y un millón de dólares para factorizar una clave pública y obtener un NFT en una presale. Los tokens de Ethereum más caros al momento de escribir este artículo (Fidenza y Bored Ape Yacht Club) cuestan aproximadamente $100,000 cada uno, por lo que para la gran mayoría de las aplicaciones, no es rentable para un atacante intentar factorizar la clave pública.
Recuerda, cada bit duplica la dificultad de factorizar el entero, así que a partir de 2022, la mayoría de las presales de tokens de bajo valor probablemente sean seguras con 896 bits. En este caso, ahorrar a los usuarios más de 2,500 de gas en comparación con ECDSA es muy atractivo.
Benchmarks por Tamaño de Clave
- RSA-896 (Gas: 26,850)
- RSA-960 (Gas: 26,925)
- RSA-1024 (Gas: 27,033)
- RSA-2048 (Gas: 29,271)
Conclusión
Presentamos un método novedoso para asignar direcciones a una presale o airdrop que es más eficiente que las soluciones conocidas hoy en día. Combinando el precompile de exponenciación modular con el patrón de contrato metamórfico y la transacción de lista de acceso, podemos validar firmas RSA seguras on-chain de una manera eficiente en gas.
Nuestro trabajo es solo una prueba de concepto en esta etapa. Se aconseja a los desarrolladores tener precaución al usar el código en producción.
Este proyecto fue creado por Suthan Somadeva y Michael Burke como parte del RareSkills Solidity Bootcamp. La implementación del código y las pruebas unitarias están en github.
Publicado originalmente el 7 de diciembre de 2022