This report presents the fork-choice rules as defined in the Cryptarchia v2 and v2-prime protocols, as well as an alternative approach discussed inOn the Closest Common Ancestor (CCA) Rule in v2/v2-prime (draft). We conclude with a comparative analysis and discussion of the different fork-choice strategies.
Please also see the writeup in PDF format:
The v2 protocol resolves conflicts between blocks in a DAG via the Closest Common Ancestor (CCA) rule, using a bounded reference window for weight calculation. The following pseudocode formalizes the rule:
\\begin{algorithm}[H]
\\caption{Fork-Choice Rule in Cryptarchia v2}
\\KwIn{Conflicting blocks $i$ (honest) and $j$ (adversarial), reference window size $w$}
\\KwOut{Winning branch (either $i$ or $j$)}
\\textbf{Step 1:} Compute ancestor sets:
\\[
\\mathrm{Anc}(i),\\quad \\mathrm{Anc}(j)
\\]
\\textbf{Step 2:} Compute common ancestors:
\\[
\\mathrm{CA}(i, j) = \\mathrm{Anc}(i) \\cap \\mathrm{Anc}(j)
\\]
\\textbf{Step 3:} Find the closest common ancestor (CCA) $c$:
\\[
c = \\arg\\max_{c' \\in \\mathrm{CA}(i, j)} \\mathrm{slot}(c')
\\]
\\textbf{Step 4:} For each branch (from $i$ and $j$), compute descendant sets:
\\[
\\mathrm{Desc}(i),\\quad \\mathrm{Desc}(j)
\\]
\\textbf{Step 5:} For each descendant $d$ in $\\mathrm{Desc}(i)$, count window-filtered references:
\\[
\\mathrm{refs}_w(d) = \\{ r \\mid r \\text{ is a reference in } d,\\, \\mathrm{slot}(d) - \\mathrm{slot}(r) < w \\}
\\]
\\textbf{Step 6:} Compute total branch weights:
\\[
W_i = \\sum_{s=0}^{S-1} \\sum_{\\substack{d \\in \\mathrm{Desc}(i) \\\\ \\mathrm{slot}(d) = s}} |\\mathrm{refs}_w(d)|
\\]
where $S = \\min\\left\\{\\max\\{\\mathrm{slot}(i), \\mathrm{slot}(j)\\} - \\mathrm{slot}(c),\\, w\\right\\}$
\\textbf{Step 7:} Repeat for branch $j$ to obtain $W_j$.
\\textbf{Step 8:} \\textbf{Decision:}
\\begin{itemize}
\\item If $W_i > W_j$, select branch $i$ as canonical.
\\item If $W_j \\geq W_i$, select branch $j$ as canonical.
\\end{itemize}
\\end{algorithm}
This rule ensures only recent network activity (within the window $w$ after the CCA) is counted, mitigating long-range attacks and promoting fair conflict resolution in the DAG.
In v2-prime, the protocol removes the reference window, summing all references in all descendants from the CCA forward. The pseudocode is as follows:
\\begin{algorithm}[H]
\\caption{Fork-Choice Rule in Cryptarchia v2-prime (Unbounded Window)}
\\KwIn{Conflicting blocks $i$ and $j$}
\\KwOut{Winning branch (either $i$ or $j$)}
\\textbf{Step 1:} Compute ancestor sets:
\\[
\\mathrm{Anc}(i),\\quad \\mathrm{Anc}(j)
\\]
\\textbf{Step 2:} Compute common ancestors:
\\[
\\hrm{CA}(i, j) = \\mathrm{Anc}(i) \\cap \\mathrm{Anc}(j)
\\]
\\textbf{Step 3:} Find the closest common ancestor (CCA) $c$:
\\[
c = \\arg\\max_{c' \\in \\mathrm{CA}(i, j)} \\mathrm{slot}(c')
\\]
\\textbf{Step 4:} For each branch, compute all descendants:
\\[
\\mathrm{Desc}(i),\\quad \\mathrm{Desc}(j)
\\]
\\textbf{Step 5:} For each descendant $d$ in $\\mathrm{Desc}(i)$, count all references:
\\[
\\mathrm{refs}(d) = \\text{all references in } d
\\]
\\textbf{Step 6:} Compute total branch weights:
\\[
W_i = \\sum_{d \\in \\mathrm{Desc}(i)} |\\mathrm{refs}(d)|
\\]
Repeat for $W_j$.
\\textbf{Step 7:} \\textbf{Decision:}
\\begin{itemize}
\\item If $W_i > W_j$, select branch $i$ as canonical.
\\item If $W_j \\geq W_i$, select branch $j$ as canonical.
\\end{itemize}
\\end{algorithm}
This unbounded approach is vulnerable to adversarial withholding attacks, as an adversary can accumulate more descendants (and thus weight) by privately mining and releasing their branch later; details can be found in On the Closest Common Ancestor (CCA) Rule in v2/v2-prime (draft) .
To address vulnerabilities in the above rules, an alternative approach proposes that the weight of a candidate branch includes both all its descendants and all blocks between the CCA and the candidate block (excluding the endpoints). This helps ensure honest progress between the fork and the candidate block is credited, mitigating withholding attacks.
\\begin{algorithm}[H]
\\caption{Alternative Fork-Choice Rule: Descendants and Between-Blocks}
\\KwIn{Conflicting blocks $i$ and $j$}
\\KwOut{Winning branch (either $i$ or $j$)}
\\textbf{Step 1:} Compute ancestor sets and common ancestors as before.
\\textbf{Step 2:} Find the closest common ancestor (CCA) $c$.
\\textbf{Step 3:} For each candidate block $i$:
\\begin{itemize}
\\item Compute all descendants: $\\mathrm{Desc}(i)$.
\\item Compute all "between" blocks:
\\[
\\mathcal{B}(c, i) = \\{ b \\mid c \\leadsto b \\leadsto i,\\ b \\neq c,\\ b \\neq i \\}
\\]
\\end{itemize}
\\textbf{Step 4:} Compute total weight for $i$:
\\[
W_i = \\sum_{d \\in \\mathrm{Desc}(i)} w(d) + \\sum_{b \\in \\mathcal{B}(c, i)} w(b)
\\]
where $w(\\cdot)$ is the weight function (e.g., reference count or 1).
\\textbf{Step 5:} Repeat for $j$ to obtain $W_j$.
\\textbf{Step 6:} \\textbf{Decision:}
\\begin{itemize}
\\item If $W_i > W_j$, select branch $i$ as canonical.
\\item If $W_j \\geq W_i$, select branch $j$ as canonical.
\\end{itemize}
\\end{algorithm}
This rule credits the honest branch for its progress between the fork and the candidate block, making it harder for adversarial branches to win by withholding. The honest branch's continuous extension accumulates extra weight, which adversaries cannot match if they delay revealing their fork.