Owner: @Álvaro Castro-Castilla

Introduction

This document accompanies the main "New Cryptarchia" specification, providing comprehensive worst-case simulations to demonstrate that the results reported in the primary document are inherently conservative in nature. These simulations have been specifically designed to stress-test the protocol under extreme conditions, revealing that the protocol's real-world resilience is substantially stronger than what is explicitly outlined in the "New Cryptarchia" writeup. By intentionally modeling adverse scenarios that exceed typical operational conditions, we establish a robust lower bound on performance, ensuring that practical implementations will benefit from even greater security margins and operational stability than the formal specification suggests.

Despite their utility, the adversarial DAG optimization techniques face inherent complexity limitations. The task—given $N$ nodes and a set of admissible edges, identify the maximum-edge acyclic subgraph—corresponds to the Maximum Acyclic Subgraph (MAS) problem, which is NP-hard. This implies that no polynomial-time algorithm is known (or expected) to solve the problem exactly in the general case. Consequently, practical approaches must rely on heuristics, approximation algorithms, or problem-specific relaxations rather than exact optimization. The results thus gives us a very close approximation (ILP in particular), that can be employed to study the system's behavior under different scenarios and parameterizations.

On using f to configure parallelism

This technique has its flaws. It's a simple way to tune up to certain degree, but the higher the parallelism is, the more advantage it gives to the adversary who chooses to accumulate all its adversarial stake in a single node-identity.

Note that this is actually strengthening the case of Cryptarchia's v2 design:

• It can only be exploited if the stake is accumulated in a single node-identity, which is exactly what the simulations do. In other words, the simulations are already reflecting this advantage.
• If improved, we expect the simulations will show better results

On exhaustive sliding-window ILP optimization vs heuristic global optimization

In these simulations we use two main techniques to optimize the adversary's DAG construction, which ultimately is the way in which it can produce reorgs and attack the honest chain. In all scenarios, we are assuming that the adversary has all the advantages to be had:

• Concentrates all its stake in a single node. See the section above.
• It observes the network with zero communication delay. This is unrealistic to implement, but gives us a theoretical worst-case scenario in this dimension.
• It can compute its optimal DAG at all times, with full knowledge of the honest chain, and only releasing it when chosen.

Benchmark 30% adversary

<aside> ℹ️

Binned frequencies show time-equivalency with C1 blocks.

</aside>

Reference: Cryptarchia v1, Cardano

f=0.25 (5x parallelism)