Resumen Técnico: Un Análisis de Costos de la Adición en Tiempo Constante para Registros On-Chain

Declaración del Problema

Los árboles de procedencia (PTs, por sus siglas en inglés) son grafos acíclicos dirigidos (DAGs) de solo adición utilizados como el sustrato de datos para la infraestructura de procedencia con control de operadores. Mientras que trabajos previos afirmaban que la operación de adición subyacente para los PTs es $O(1)$ en costo de gas —independiente del tamaño del registro y la profundidad del árbol—, esta afirmación carecía de aislamiento formal como primitiva independiente, de límites constantes explícitos o de una validación empírica frente al estándar de la industria: el Árbol de Merkle Incremental (IMT).

El IMT, dominante en protocolos de conocimiento cero (por ejemplo, Tornado Cash, Semaphore) y compromisos de estado de rollups, ofrece pruebas de inclusión sucintas de $O(\log N)$, pero incurre en un costo de adición que crece logarítmicamente con la profundidad del árbol ($\Theta(\log N)$). Para aplicaciones donde las pruebas de membresía sucintas no son la consulta principal (como los registros de procedencia), el compromiso de costo del IMT es menos favorable, aunque el punto de cruce donde una alternativa resulta más económica no ha sido establecido rigurosamente.

Metodología

El artículo aisla el Grafo Acíclico Dirigido de Hash de Padre (PHDAG) como una primitiva distinta y lo compara con el Árbol de Merkle Incremental (IMT) a través de tres lentes:

1. Análisis de Complejidad Formal: Los autores formalizan la operación de adición del PHDAG, demostrando que se ejecuta un número acotado de operaciones de la EVM independientemente del tamaño del registro ($n$) o la profundidad. Contrastan esto con el bucle de actualización de la frontera del IMT, que escala linealmente con la profundidad ($d$).
2. Modelado Estocástico de Costos: Reconociendo que los costos de adición del IMT varían según la representación binaria del índice de la hoja (peso de Hamming), los autores modelan el costo de inserción por variable aleatoria. Derivan expresiones de forma cerrada para la media y la varianza de los costos del IMT bajo una distribución uniforme de índices de hojas, distinguiendo entre "niveles de escritura" (actualización de la frontera) y "niveles de lectura" (traza sin escribir).
3. Validación Empírica: Se desplegaron contratos independientes para ambas primitivas en la red de prueba Base Sepolia. Los experimentos cubrieron profundidades de árbol desde 1 hasta 25.
   • IMT: Probado mediante un "barrido de profundidad proporcional" realizando $\max(d, 2)$ adiciones por profundidad para capturar la varianza.
   • PHDAG: Probado mediante una ejecución de 200 adiciones para caracterizar la distribución de costos y la varianza.
   • Métricas: El consumo de gas se midió a partir de los recibos de las transacciones, excluyendo los costos iniciales de inicialización de almacenamiento en frío para enfocarse en el rendimiento en estado estacionario.

Principales Contribuciones

1. Complejidad Formal del PHDAG

El artículo establece que la adición del PHAGD es estrictamente $O(1)$ en costo de gas.

• Mecanismo: Cada adición escribe en tres ranuras de almacenamiento previamente no tocadas (SSTOREs en frío) claveadas por un identificador único, además de una escritura en caliente a un contador.
• Invarianza: El costo es invariante al tamaño global del registro $n$ y a cualquier noción de profundidad del árbol. La lista de acceso para una transacción se reinicia al comienzo de cada transacción; dado que el PHDAG escribe en nuevas ranuras cada vez, el costo depende solo del número fijo de operaciones, no del estado del contrato.
• Reconstrucción: El artículo demuestra que el registro completo puede reconstruirse a partir de los registros de eventos públicos en $O(|V|)$ de tiempo sin dependencia off-chain, ya que el flujo de eventos transporta la historia canónica.

2. Modelo Estocástico para el IMT

Los autores derivan que el costo por inserción del IMT es una variable aleatoria $g$ dependiente del índice de la hoja $i$:

• Media: $E[g] = c_0 + \frac{d}{2}(c_L + c_R)$, donde $c_L$ y $c_R$ son los costos marginales de los niveles de escritura y lectura, respectivamente.
• Varianza: $Var[g] = (c_L - c_R)^2 \frac{d}{4}$.
• Implicación: Aunque la varianza relativa (coeficiente de variación) disminuye a medida que la profundidad aumenta, la desviación estándar absoluta crece como $\Theta(\sqrt{d})$, introduciendo imprevisibilidad operativa para registros de alta profundidad.

3. Punto de Cruce Empírico y Validación

• Rendimiento del PHDAG: Medido en un valor constante de 76,276 gas por adición (desviación estándar $\approx 6$ gas), confirmando la invariancia de la profundidad.
• Rendimiento del IMT: Los costos crecieron linealmente con la profundidad.
• Punto de Cruce: La profundidad en la que el PHDAG se vuelve más barato que el IMT se identificó en $d \approx 6$ a $7.2$.
  • En $d=6$, el costo medido del IMT ($\approx 78,000$ gas) superó el costo del PHDAG.
  • El cruce promedio de por vida (distribución de índice uniforme) se calcula en $d^* \approx 7.2$.

Resultados

Los datos empíricos validan los modelos teóricos:

• PHDAG exhibe una varianza insignificante y un costo constante a través de todas las profundidades probadas.
• IMT exhibe un crecimiento de costo lineal y una varianza absoluta creciente con la profundidad.
• Contexto de Producción: Cada registro de producción analizado (Tornado Cash, Semaphore, zkSync, Scroll, Linea) opera en profundidades $d \ge 20$. En consecuencia, todos estos sistemas operan actualmente en el régimen donde el PHDAG es estrictamente más barato y ofrece costos predecibles, siempre que la aplicación no requiera pruebas de membresía sucintas.

Significado y Reivindicaciones

El artículo sostiene que la primitiva PHDAG es la opción superior para los registros de procedencia de solo adición donde:

1. No se requieren pruebas de membresía sucintas: Las consultas de procedencia suelen implicar la traza de la cadena de padres o verificaciones de existencia por ID único, las cuales son soportadas por la reconstrucción basada en logs de $O(|V|)$ en lugar de pruebas de Merkle de $O(\log N)$.
2. La predictibilidad del costo es crítica: Para operadores que gestionan servicios de adición de alto volumen, la varianza cercana a cero del PHDAG elimina la necesidad de presupuestar para colas de gas de peor caso, una ventaja operativa significativa sobre el IMT en profundidades de producción.
3. La robustez es primordial: El diseño log-canónico del PHDAG asegura que la historia del registro sea indestructible y reconstruible a partir de los registros de eventos públicos por sí solos, independientemente de cualquier servicio de indexación off-chain o del estado actual del almacenamiento del contrato.

Los autores concluyen que el PHDAG es un fuerte candidato para la estandarización como una interfaz uniforme para la infraestructura de procedencia de Ethereum, ofreciendo una alternativa de costo constante e invariante de la profundidad frente al IMT dependiente de la profundidad para aplicaciones no-ZK.