Skip to main content

5. DAG Structure & Ordering

5.1 Why a DAG Instead of a Chain​

A linear blockchain serialises all transactions into a single sequence of blocks, which fundamentally caps throughput at one block producer at a time. Quantos replaces the chain with a Directed Acyclic Graph (DAG) of vertices (quantos/src/dag/). The DAG implementation permits concurrent vertex creation and parent references. This can reduce a single-producer bottleneck in the intended design, but network throughput and availability depend on validator coordination and configuration.

5.2 Vertices and Parent References​

Each DAG vertex (types/vertex.rs) bundles a set of transactions and references between 2 and 8 parent vertices (min_dag_parents = 2, max_dag_parents = 8). Multiple parents serve two purposes: they weave concurrent vertices into a single connected structure, and they act as votes of availability — referencing a parent asserts that the referencer has seen and validated it.

The DAG enforces strict structural invariants (dag/graph.rs), each mapped to an explicit error:

  • Parent-count bounds: fewer than min parents (TooFewParents) or more than max (TooManyParents) is rejected.
  • Acyclicity: a reference that would create a cycle (CycleDetected) is rejected — the graph must remain acyclic for ordering to terminate.
  • Parent existence: references to unknown vertices (InvalidParent, VertexNotFound) are rejected.
  • Resource bounds: per-vertex children limits, per-shard limits, traversal limits, and height-overflow checks (ChildrenLimitExceeded, ShardLimitExceeded, TraversalLimitExceeded, HeightOverflow) bound memory and CPU so that a malicious vertex cannot trigger unbounded work.

5.3 Ingress and Validation​

New vertices enter through the ingress path (dag/ingress.rs), which validates structure, signatures, and parent availability before admitting a vertex to the graph. Invalid vertices are rejected at ingress and never pollute the graph, so the ordering layer always operates over a well-formed DAG.

5.4 Deterministic Topological Ordering​

The ordering engine (dag/ordering.rs) provides deterministic ordering logic over the available DAG. Consensus integration, parent completeness, tie-breaking, and state-transition equivalence must be tested across independent nodes; an ordering function alone is not a distributed proof of total-order agreement.

5.5 Conflict Resolution​

The state executor validates transactions against the committed state and can reject later conflicting transactions after ordering. Conflict behavior, rollback, and equivalence across nodes must be covered by multi-node tests, especially under concurrent gossip and speculative execution.