Finality

Definition

=nil; offers strong guarantees for each confirmation step involved in reaching probabilistic and absolute finality. Here is a high-level overview of the finality procedure:

1. At the execution shard level, local consensus ensures that only valid blocks are built
2. Execution shards generate ZKPs verifying the correctness of execution. These ZKPs are then sent to the consensus shard along with block headers
3. The consensus shard verifies the ZKPs received from execution shards and generates a 'master' ZKP
4. The 'master' ZKP and state diffs of block headers are sent to Ethereum

Generating ZKPs

Generating ZKPs is a resource-intensive process. While ZKPs are generated, =nil; relies on a separate security protocol to ensure that local and global consensus and reached. Learn more about the consensus shard.

The below sub-sections provide additional remarks on state transition proofs, and probabilistic and absolute finality.

State consensus checks

In =nil;, validators verify entire neighborhoods of shards based on the Hamming distance between shards.

$$committee(shardId) = \bigcup_{\substack{s\in shardIds\\dist(s,shardId)\le R}}assignment(s)$$

, where $R\ge 0$ is the neighborhood size set at the protocol level. The exact value of $R$ depends on what committee size is sufficiently large to afford acceptable safety guarantees.

State transition proofs

A state transition proof is a cryptographic construct that validates a state transition without the need to rerun the transactions causing the transition.

Here is the formula for a state transition proof:

$$F(S_i, T, S_{i+1}, PI) \to (\pi)$$

, where

• $S_i$ is the initial state
• $T$ represents the transaction(s) that caused the transition
• $S_{i+1}$ is the new state after $T$ is applied to $S_i$
• $PI = [C_t, C_s, C_{S+1}]$ is a representation of $S_i$, $T$, and $S_{i+1}$ in the form of a public input
• $\pi$ is the ZKP verifying the correctness of the transition without revealing $T$

A state transition proof is verified by the verifier function:

$$V(PI, \pi) \to \begin{Bmatrix} true, \space if \space the \space transition \space is \space valid \\ false, \space otherwise \end{Bmatrix}$$

Applying formulas

In the formulas above, $S_i$ can mean the global state of =nil; or the local state of a specific execution shard.

The following formula provides a more precise representation of the state transition proof for the global state of =nil; given $k$ execution shards.

$$F(S^0_i, ..., S^{k-1}_i, S^0_{i+1}, ..., S^{k-1}_i+1, T^0, ..., T^{k-1}, PI^0, ..., PI^{k-1}) \to (\pi)$$

Global state transition proof

The global state transition proof can be represented via the following formula:

$$F(S^0_i, S^0_{i+1}, \overline{T}, \overline{PI})$$

, where

• $0$ is the sequence number of the consensus shard
• $\overline{T}$ and $\overline{PI}$ contain data about transactions that have been processed at the execution layer

The global state transition proof can be attained from the state transition proof of the consensus shard when given the state differences that include verifications of the state transition proofs of all execution shards.

Note that a single validator node cannot handle producing state transition proofs for every state change in every shard. Such an action would be resource-intensive and require the node to possess the state of the entire sharded cluster.

To address this problem, proof generation is made a multi-party protocol whose participants are known as proof producers.

Proof generation protocol

A proof producer is a special participant of =nil; whose main task is generating state transition proofs.

Proof generation occurs in slots, which are defined as individual tasks for producers. Producers can bid on slots by specifying the fee they want to receive for their work. These auctions are won by the lowest possible fee, and the winning proof producer receives this fee on successful proof generation.

There are three possible types of proofs generated by proof producer:

• $\pi_S$ is a general state transition proof described above
• $\pi_A$ is an aggregation proof combining two state transition proofs:

$$F_A(\pi_1, \pi_2) \to \pi_A$$

• $\pi_O$ is an output proof:

$$F_O(\pi_{A, 1}, \pi_{A, 2}) \to \pi_O$$

Output proof

An output proof is a unique type of proof: it exists only if the execution layer adopts a proof system that promises various optimizations and cost benefits.

In this case, output proofs allow for achieving these benefits by aggregating proofs made for different proof systems. In any other case, output proofs are fully optional.

Whenever a new block is sent to the consensus shard, the following process occurs:

1. A part of the total block reward is locked as a reward for proof producers. The size of this reward is set by the protocol parameters
2. New slots are open. Each slot has the max_fee field that defines the maximum possible fee a proof producer may ask for proof generation
3. The proof producer auction concludes by choosing the producer who set the lowest fee
4. The producer submits the proof and is provided with the fee in return

Probabilistic finality

Probabilistic finality occurs when a data availability transaction posted by the consensus shard is placed in a verified block on L1. There are no additional mechanisms for ensuring probabilistic finalization as Ethereum validators are deemed sufficiently reliable.

Absolute finality

Absolute finality is only possible after all ZKPs are verified. This requires the global state proof along with finalized state differences as shown in the following formula.

$$Finalization_t = \begin{Bmatrix} true, \space if \space V_{zk}(proof_t) \bigwedge V_{diff}(Diff_t), \space where \space : \space V - verification \space function \\ false, \space otherwise \end{Bmatrix}$$