Longest Chain Cryptarchia (current state)

We are currently following Cardano / Bitcoin in using the “longest chain” fork choice rule. This rule is simple but it is highly sensitive to the interaction between network delay (induced by the mixnet) and block times.

If we try to increase our mixnet latency to provide better privacy, we expose ourselves to block withholding attacks where a powerful adversary quickly builds a longer fork that is able to re-org the main chain.

An adversary controlling 30% of stake’s ability to re-org the main chain.
i.e. A reorg of depth 20 happens once every $10^3$ blocks when mixnet delay was 22.8s

An adversary controlling 30% of stake’s ability to re-org the main chain. i.e. A reorg of depth 20 happens once every $10^3$ blocks when mixnet delay was 22.8s

In longest chain Cryptarchia, if we want to increase mixnet delay, we need to also increase block times to maintain the same level of network security, here we keep mixnet delay constant and adjust block time to try to compensate for the network.

The adversary is able to keep forks alive indefinitely if block times are shorter than mixnet delays

Adversary is able to keep forks alive indefinitely if block times are shorter than mixnet delays

Takeaway Block times need to be larger than network delay in order to ensure an exponential decay in frequency of long re-orgs

GHOST Cryptarchia

https://eprint.iacr.org/2013/881.pdf

The GHOST protocol was a proposal to change Bitcoin’s fork choice rule to one that maintains network security under turbulent network conditions.

Instead of following the longest chain, nodes follow the block with the heaviest subtree extending from it. In the following example, nodes will choose to follow blocks that have the most weight built on top of them, ie. count the size of the sub-tree extending from each block.

1B block has a much heavier sub-tree than the attackers 1A block, thus nodes will choose 1B over 1A.

With this rule, adversaries need to compete against the entire block production rate of the network rather than the networks ability to build a long chain.

This change makes Cryptarchia removes any advantage the adversary had due to mixnet delays:

Cryptarchia w/ GHOST

Cryptarchia w/ Longest Chain

And network security becomes invariant to block times as well.

Cryptarchia w/ GHOST

Cryptarchia w/ Longest Chain