This writeup is a followup analysis of The v2-prime Protocol and Security Definitions for DAG-based Ledger/Consensus : the v2-prime protocol can be viewed as the original v2-protocol, i.e., Alvaro’s ‣ protocol, in the Idealized Block Generation and Idealized Network: Refined Model. At the end of the writeup, we will discuss the remaining steps towards a complete security analysis.

DAG Common Past, Growth, and Quality

1. DAG Common Past

Common Prefix Property: Definition

The common prefix property states that for any two honest parties at times $t$ and $t'$, if we remove the last $k$ blocks from their local chains, the resulting prefixes are identical. That is, for any two chains $C_1$ and $C_2$ held by honest parties at times $t$ and $t'$, $C_1[0 : |C_1| - k] = C_2[0 : |C_2| - k]$;

Proof of Common Prefix Property (GKL)

The proof in the GKL paper proceeds by showing that, under the idealized Bitcoin backbone protocol (with synchronous network and random block generation), the probability that two honest parties have diverging chains beyond the last $k$ blocks is negligible, provided the adversary controls less than half of the mining power.

The key steps are:

1. Chain Growth and Block Propagation: Honest miners continuously extend the longest chain they see. Due to the synchronous network, all honest blocks propagate quickly, so most honest miners work on the same chain tip.
2. Adversarial Forking Power is Limited: If the adversary controls less than half the mining power, it cannot consistently produce longer chains than the honest majority. Thus, any adversarial fork will eventually be overtaken by the honest chain.
3. Deep Blocks Become Immutable: Once a block is buried under $k$ additional blocks (i.e., is $k$-deep), the probability that an adversarial fork can catch up and override it decreases exponentially in $k$. Therefore, any block that is $k$-deep in any honest chain will, with overwhelming probability, remain in the chains of all honest parties, even as the chains grow.
4. Formal Statement: For any two honest parties and any $k$, the prefixes of their chains up to the last $k$ blocks must coincide: $C_1[0 : |C_1| - k] = C_2[0 : |C_2| - k]$ The probability that this fails decays exponentially in $k$.

DAG Common Past Property: Definition

The "DAG common past" property states that for any two honest parties at times $t$ and $t'$, the intersection of their DAGs contains all blocks that are ancestors of any block $B$ with at least $k$ descendants (i.e., blocks referenced directly or indirectly by at least $k$ subsequent blocks). Formally, for all honest parties $P_1, P_2$ at times $t, t'$, let $D_1, D_2$ be their DAGs. Then, for any block $B$ with $|\text{descendants}(B)| \geq k$, $\text{Ancestors}(B) \subseteq D_1 \cap D_2$.

Proof of DAG Common Past Property (v2-prime Protocol)