La codificación de enteros de longitud variable (varints) es una técnica fundamental en sistemas distribuidos y protocolos binarios para representar números de manera compacta, especialmente cuando la mayoría de los valores son pequeños pero ocasionalmente grandes. Sin embargo, un problema recurrente en diseños como LEB128 es la falta de canonicidad inherente: un mismo número puede tener múltiples representaciones binarias. Esta ambigüedad no es solo una ineficiencia de almacenamiento, sino una vulnerabilidad de seguridad crítica en contextos donde la integridad de los datos (ej. firmas criptográficas, content-addressing) depende de una representación binaria única y determinista.
bijou64 aborda este problema fundamental de la computación al diseñar un varint que es canónico por construcción. Esto significa que, para cualquier entero dado, existe una y solo una secuencia de bytes que lo representa. Esta propiedad elimina la necesidad de validaciones de canonicidad explícitas en tiempo de ejecución, que son costosas en rendimiento y propensas a errores de implementación. Al integrar la canonicidad en el formato mismo, bijou64 no solo fortalece la seguridad de los protocolos que lo utilizan, sino que también optimiza el rendimiento de codificación y decodificación al simplificar la lógica de procesamiento y mejorar la predictibilidad del flujo de ejecución en la CPU.
Arquitectura del Sistema
La arquitectura de bijou64 se basa en dos principios clave para lograr la canonicidad por construcción y el alto rendimiento. Primero, el primer byte de la codificación cumple una doble función: si su valor está entre 0 y 247, representa directamente el número. Si el valor está entre 248 y 255, actúa como un 'tag' que indica la longitud total de bytes que siguen para representar el número. Esta estrategia permite al decodificador determinar la longitud del varint en O(1) operaciones, a diferencia de LEB128 que requiere escanear bits de continuación en O(n).
Segundo, bijou64 utiliza un sistema de 'offsets' para garantizar que cada número tenga una representación única. En lugar de permitir que los bytes subsiguientes repitan rangos de valores ya cubiertos por codificaciones más cortas, bijou64 desplaza el valor de los bytes adicionales. Por ejemplo, si el primer byte es un tag que indica dos bytes de datos, el valor decodificado se calcula sumando un offset predefinido (ej. 0xF8 para dos bytes) al valor de los bytes de datos. Este mecanismo asegura que no haya solapamiento entre las representaciones de diferentes longitudes. La carga útil de los datos es un entero big-endian contiguo, lo que permite a las CPUs modernas utilizar instrucciones de byte-swap (bswap) para una decodificación eficiente, en contraste con el enmascaramiento y desplazamiento bit a bit requerido por LEB128. La única excepción a la canonicidad 'pura' es un chequeo de límites para los valores más grandes (9 bytes), donde el valor decodificado se compara con 2^64 para asegurar que no exceda el rango de un u64, aunque esto no introduce ambigüedad de codificación.
Flujo de Decodificación de bijou64
- 1 Leer Primer Byte Decodificador lee el primer byte del stream.
- 2 Evaluar Primer Byte Si 0-247, es el valor final. Si 248-255, es un tag de longitud.
- 3 Determinar Longitud Si es un tag, se usa para saber cuántos bytes de datos adicionales leer (O(1)).
- 4 Leer Bytes de Datos Se leen los bytes de datos restantes, si los hay.
- 5 Aplicar Offset Se suma el offset correspondiente a la longitud para obtener el valor base.
- 6 Decodificar Big-Endian Los bytes de datos se interpretan como un entero big-endian (con bswap).
- 7 Validar Rango (Solo 9 bytes) Si el tag es 255 (9 bytes), se verifica que el valor no exceda 2^64.
- 8 Retornar Valor El entero decodificado y canónico es retornado.
| Capa | Tecnología | Justificación |
|---|---|---|
| data-processing | bijou64 | Codificación de enteros de longitud variable canónica y de alto rendimiento para protocolos binarios y almacenamiento de datos. vs LEB128, VLQ, Protocol Buffers varint |
| compute | CPU (M2 Pro, Zen 5, Zen 3) | Ejecución de las operaciones de codificación/decodificación, aprovechando instrucciones de byte-swap y predicción de ramas. |
Trade-offs
Ganancias
- ▲ Canonicidad por construcción
- ▲▲ Rendimiento de decodificación
- ▲ Rendimiento de codificación (general)
- ▲ Seguridad (eliminación de ataques de canonicidad)
- ▲ Predecibilidad de latencia (baja varianza)
Costes
- △ Rendimiento de codificación para números pequeños-medianos (248-65535)
- ▲ Madurez de la implementación (nuevo formato)
- △ Compactación (ligeramente menos compacto en algunos casos)
Fundamentos Teóricos
El problema de la canonicidad en la representación de datos tiene profundas raíces en la teoría de la información y la criptografía. Un ejemplo clásico es el Abstract Syntax Notation One (ASN.1), ampliamente utilizado en certificados X.509 y protocolos como LDAP. Los ataques de canonicidad contra ASN.1, como los documentados en PKCS#1, demuestran cómo la ambigüedad en la codificación puede ser explotada para manipular firmas criptográficas o evadir controles de seguridad. Estos ataques surgen cuando una especificación define una forma canónica, pero la implementación no la valida rigurosamente, permitiendo que diferentes secuencias de bytes se interpreten como el mismo valor lógico.
La solución de bijou64, que garantiza la canonicidad por construcción, se alinea con el principio de 'seguridad por diseño' y 'corrección por construcción'. En lugar de añadir validaciones post-facto, el formato mismo está diseñado para que solo exista una representación válida para cada valor. Esto reduce la superficie de ataque y elimina una clase completa de errores de implementación, un concepto que resuena con los principios de diseño de lenguajes de programación y sistemas que buscan eliminar clases enteras de errores mediante restricciones en el sistema de tipos o el diseño del lenguaje, como se ve en Rust o en el uso de tipos algebraicos de datos para modelar estados válidos.