[WIP] Resilient Secret-Shared Validator Protocol

# [WIP] Resilient Secret-Shared Validator Protocol :::info # This document has moved to https://notes.ethereum.org/@adiasg/ssv-rbb ::: **Thanks to Carl Beekhuizen for discussion** ## Notation | Description | Notation | |:-------------------------------------- | ----------:| | Total number of shared-validator nodes | $N$ | | Threshold signature scheme | $m$ of $N$ | ## Objectives 1. **Safety:** Conflicting attestations should not be produced unless $\geq min(\frac{N}{3}, m)$ nodes are corrupted. 2. **Liveness:** An attestation must be produced for each designated slot, unless $\geq min(\frac{N}{3}, N-m+1)$ are corrupted. (Another precondition is that that no $k$ consequtive leaders are Byzantine, so that $T \cdot k < SECONDS\_PER\_SLOT$ where $T$ is the time req. for our protocol to produce an attestation using a honest leader) ## Protocol The leader uses a broadcast protocol to propose attestations to the shared-validator nodes. The broadcast protocol should satisfy: - Properties: - **Agreement:** If a correct node delivers a message, then all correct nodes eventually deliver the same message - **Validity:** If a correct leader performs $broadcast(a)$, then all correct nodes eventually $deliver(a)$ - **Leader-change:** If the leader is Byzantine, no correct node performs $deliver$ in that epoch, and all correct nodes change the leader in their respective views to the same new leader. - **Integrity:** Every correct node performs $deliver$ on at most one value (in each epoch). If the leader is correct, then the leader had performed $broadcast(a)$ (in that epoch). - Protocol terminates in a fixed number of rounds The following protocol satisfies our requirements for upto $t$ Byzantine nodes (where $N > 3\cdot t$): ### Protocol Specification This is **Bracha's Reliable Broadcast** protocol. More information in the [original paper](https://core.ac.uk/reader/82523202), and this [summary](https://dcl.epfl.ch/site/_media/education/sdc_byzconsensus.pdf). :::info **THERE'S SOMETHING MISSING FROM THE PROTOCOL!** **Leader-change** property does not hold! Byzantine leader is not detected! However, all cases of Byzantine are not necessary to detect for this protocol. Only cases where an attestation is not produced because of a faulty leader should be detected, and leader should subsequently be changed.  ::: - **Initialize** - Each node $i$ initializes: - $next\_epoch_i = 1$ - $leader_i = 0$ - **Round 1** - **A:** For node $i$ s.t. $i = leader_i$ (i.e., this node is leader) - Upon $broadcast(a)$, send $sign_{i}(PROPOSE, a)$ to all nodes, where $epoch(a) = next\_epoch_{i}$ - **B:** For node $i$: - Upon receving $sign_{leader_i}(PROPOSE, a)$, send $sign_i(ECHO, a)$ to everyone if: - no other message $sign_{leader_i}(PROPOSE, a')$ has been received with $epoch(a)=epoch(a')$, and - $epoch(a) = next\_epoch_i$ - **Round 2** - For node $j$: - Upon receiving $sign_i(ECHO, a)$ messages from $\lceil\frac{N+t+1}{2}\rceil$ nodes, send $sign_j(READY, a)$ to everyone - **Round 3** - For node $j$: - If a $READY$ message was not previously sent in Round 2 then: - Upon receiving $sign_i(READY, a)$ messages from $t+1$ nodes, send $sign_j(READY, a)$ to everyone - **Round 4** - For node $j$: - If $sign_i(READY, a)$ messages from $2 \cdot t + 1$ nodes: - have been received, then $deliver_j(a)$ - have not been received, then $change\_leader_j(next\_epoch_j)$ - Functions local to each node $i$: - $deliver_i(a)$: - set $next\_epoch_i = next\_epoch_i + 1$, and - send $threshold\_sig_i(a)$ to everyone - $change\_leader_i(next\_epoch_i)$: - $leader_i = next\_epoch_i \bmod N$ ### Proof - Intuition: - A node sending $(ECHO, a)$ is a claim that it has seen a $(PROPOSE, a)$ message from the leader for only that $a$ at the epoch. When we see a Byzantine quorum of nodes sending an echo message for $a$, we know that enough nodes have seen the same $PROPOSE$ message. - A node sending $(READY, a)$ is a claim that it has seen a Byzantine quorum of $(ECHO, a)$ messages. - Re-broadcasting $READY$ messages in Round 3 is to satisfy the **Agreement** criterion. - It's easy to check that **Validity** and **Integrity** properties hold. Also clear that the protocol terminates in 4 rounds. - By the end of Round 2, there will be at most one $a$ for which there is a Byzantine quorum ($=\lceil\frac{N+t +1}{2}\rceil$) of nodes sending $ECHO$ messages. This follows from the fact that any two Byzantine quorums intersect in at least one honest node. If there is an $a$ for which a Byzantine quorum of $ECHO$s was made, then no other $a'$ at that epoch can have the same. - Checking **Agreement**: In Round 4, if any correct node has executed $deliver_i(a)$, then it has received $2 \cdot t + 1$ messages of $READY$. At least $t+1$ of these must be from correct nodes, and when these $t+1$ messages reach other correct nodes, they will send $READY$ messages as per their Round 3 protocol. Since the total number of correct nodes is $\geq 2 \cdot t + 1$, there will be at least $2 \cdot t + 1$ messages of $READY$, leading to all correct nodes triggering $deliver_i(a)$ in their Round 4.