Owner: @David Rusu

Reviewers: 🟡@Daniel Sanchez Quiros 🟡@Giacomo Pasini 🟡@Álvaro Castro-Castilla

<aside> 💡

POSTPONED

Some recent findings have raising some doubts about safety of GHOST

• https://eprint.iacr.org/2024/1830.pdf
• https://ar5iv.org/html/2203.01315

We don’t have the capacity right now to resolve the issues so we’ll continue with the longest chain fork choice rule for now.

</aside>

The cryptarchia fork choice rule is an combination of the Ouroborous Genesis fork choice and GHOST.

Definitions

• $T$ a block tree

• $c_{loc}\in T$ : the block that this node considers to be the tip of the chain (local chain)

• $F \subseteq T$ : the set of blocks which are the tips of competing forks:

• $k$ : safety parameter, i.e. the depth at which a block is considered immutable

• $s$ : sufficient time measured in slots for $k$ blocks to be produced w.h.p.

  In practice we say $s = 3\frac{k}{f}$, where $f$ is the active slot coefficient from the leader lottery

• $\textbf{common\_prefix\_depth}(b_1\in T, b_2 \in T) \rarr (\mathbb{N},\mathbb{N})$

  Returns the depth at which the two branches diverge from each other.

  For example:

  $\textbf{common\_prefix\_depth}(b_1, b_2) = (0, 4)$ implies that $b_2$ is ahead of $b_1$ by 4 blocks

  i.e. $5^{th}\text{-grandparent}(b_2)=b_1$

  $\textbf{common\_prefix\_depth}(b_1, b_2) = (31, 8)$ implies that $b_1$ and $b_2$ have diverged, the divergence occured at the 31st grandparent of $b_1$ and at the 8th grandparent of $b_2$

  i.e. $32^{nd}\text{-grandparent}(b_1)=9^{th}\text{-grandparent}(b_2)$

• $\textbf{weight}(b\in T)$

  Returns the size of the subtree rooted at block $b$

  return $| \{c \in T\space |\space \exist n\in \mathbb{N} \space s.t. \space b = n^{th}\text{-grandparent(c)}\}|$

• $\textbf{density}(b \in T, d\in \mathbb{N}, s\in\mathbb{N})$

  Returns the number of blocks in the chain with tip $b$ in the subsequent $s$ slots after the $d^{th}\text{-grandparent}(b)$

Pseudocode

$\textbf{ghost\_maxvalid\bg}(c{loc}, F, k, s)$ {

$c_{max}\coloneqq c_{loc}$

for $f \in F$ {

$(d_{c_{max}}, d_{f}) \coloneqq \textbf{common\_prefix\depth}(c{max}, f)$

if $d_{c_{max}} \le k$ {

We use the GHOST rule when the forking depth is shorter or equal to $k$

if $\textbf{weight}(d_{c_{max}}^{th}\text{-grandparent}(c_{max})) < \textbf{weight}(d_{f}^{th}\text{-grandparent}(f))$ {

Strict inequality is necessary here to ensure the first seen chain is kept in case of a tie

$c_{max} \coloneqq f$

}

} else {

We use the Ouroboros Genesis chain density rule when forking depth exceeds $k$

if $\textbf{density}(c_{max}, d_{c_{max}} s) < \textbf{density}(f, d_{f}, s)$ {

$c_{max} \coloneqq f$

}

}

}

return $c_{max}$

}