In this post we construct Chained Simplex from single-shot Simplex. The chained construction is a simple modification of the single-shot protocol and applies to any Simplex variant with the same inner certificate properties and outer proposal structure. See here for more generic constructions.
We will use the decomposition from deconstructing Simplex to make the construction explicit. That post separates Simplex into:
- an inner protocol, which produces value certificates, decision certificates, and skip certificates per view; and
- an outer protocol, which forms proposals and tells honest parties which proposals to vote for.
We keep the inner protocol unchanged and only slightly change the outer protocol.
The Inner Protocol
In view $v$, the inner protocol may produce:
- $\mathrm{VC}_v(x)$, a value certificate for $x$.
- $\mathrm{DC}_v(x)$, a decision certificate for $x$.
- $\mathrm{SC}_v$, a skip certificate for view $v$.
We use the following properties of the inner protocol.
Same View Agreement. There are no two valid value certificates $\mathrm{VC}_v(x)$ and $\mathrm{VC}_v(y)$ with $x\neq y$.
Decision Implies Value. A valid $\mathrm{DC}_v(x)$ implies a valid $\mathrm{VC}_v(x)$.
Skip Decision Exclusion. There is no valid pair $\mathrm{DC}_v(x),\mathrm{SC}_v$.
Every valid value certificate contains an honest vote for its value. Honest parties vote only after the outer protocol accepts the proposal for that value.
Certificates are forwardable. After GST, if an honest party obtains a valid value, decision, or skip certificate, then every honest party eventually obtains it.
After GST, in each entered view, some honest party eventually obtains either a valid value certificate or a valid skip certificate.
In an honest leader good case, if the leader has a valid proposal, the view produces the corresponding decision certificate within the usual good case latency.
Single-Shot Simplex Outer Protocol
In single-shot Simplex, honest parties vote for a proposal in view $v$ in one of two cases.
First, the proposal repeats the value from a previous value certificate and includes skip certificates for the intervening views:
value:
x
vote when:
VC_w(x)
SC_{w+1}, ..., SC_{v-1}
where $0<w<v$.
Second, the proposal uses a fresh value and includes skip certificates for the intervening views:
value:
x
vote when:
x passes external validity
SC_1, ..., SC_{v-1}
Thus, a proposal either repeats a previous value, or starts from a fresh externally valid value.
Chained Simplex Outer Protocol
The chained outer protocol always uses a previous value certificate, and also checks a new block against the chain in that certificate.
Values are chains. Write $C\preceq D$ when $C$ is a prefix of $D$. There is a public genesis chain $\bot_{\mathsf{gen}}$, with public value certificate $\mathrm{VC}_0(\bot_{\mathsf{gen}})$.
The chain represents a state machine execution. We assume an external application validity relation
\[C \xrightarrow{\mathrm{valid}} C\circ B,\]meaning that block $B$ is valid relative to the state reached by $C$.
For the first block, use $w=0$ and $C=\bot_{\mathsf{gen}}$. Honest parties vote for a proposal in view $v$ when:
value:
C^+ = C o B
vote when:
VC_w(C)
SC_{w+1}, ..., SC_{v-1}
C -> valid C o B
where $0\leq w<v$.
The core change is small: the leader does not merely propose the certified value again. It uses the certified chain as a prefix and proposes one valid extension of it.
If view $v$ produces $\mathrm{DC}_v(C^+)$, then $C^+$ is decided. If it produces only $\mathrm{VC}_v(C^+)$, then $C^+$ is not decided yet, but later views may extend it. If view $v$ produces $\mathrm{SC}_v$, then no new chain is decided in view $v$.
Chained Simplex Properties
A chain $C$ is decided if there is a valid decision certificate $\mathrm{DC}_v(C)$ for some view $v$.
The chain protocol has the following properties.
Chain Agreement. If $\mathrm{DC}_i(C)$ and $\mathrm{DC}_j(D)$ are valid, then $C\preceq D$ or $D\preceq C$.
We only require prefix agreement for decided chains. Value certificates without decisions need not become decided chains.
Chain Validity. If $\mathrm{VC}_v(C)$ is valid, then $C$ is valid from genesis: each block is externally valid after its prefix. Therefore, the same holds for every valid $\mathrm{DC}_v(C)$.
Chain Growth. After GST, if valid blocks remain available and honest leaders occur infinitely often, the height of decided chains grows without bound.
Why It Works
Agreement. If $i=j$, then decision implies value and same view agreement give $C=D$. So it remains to show that if $\mathrm{DC}_i(C)$ and $\mathrm{VC}_j(D)$ are valid with $i<j$, then $C\preceq D$.
Since $\mathrm{VC}_j(D)$ contains an honest vote, $D$ came from an accepted chain proposal. Thus, $D=D^\prime\circ B$ for some predecessor certificate $\mathrm{VC}_w(D^\prime)$ and skips $\mathrm{SC}_{w+1},\ldots,\mathrm{SC}_{j-1}$.
If $w=i$, then decision implies value and same view agreement give $C=D^\prime$, so $C\preceq D$. If $w<i<j$, then the proposal included $\mathrm{SC}_i$, contradicting $\mathrm{DC}_i(C)$ by skip decision exclusion. If $i<w$, repeat the same argument with $\mathrm{VC}_w(D^\prime)$ in place of $\mathrm{VC}_j(D)$. The view number decreases, so this eventually proves $C\preceq D$.
Chain agreement follows because every decision certificate implies a value certificate for the same chain.
Validity. We prove by induction on $v$ that every valid $\mathrm{VC}_v(E)$ has an externally valid chain. The genesis certificate is valid. For $v>0$, a value certificate contains an honest vote, so its proposal was for $E=C\circ B$, used a valid predecessor $\mathrm{VC}_w(C)$ with $w<v$, and checked $C \xrightarrow{\mathrm{valid}} C\circ B$. By induction, $C$ is valid, so $E$ is valid. A decision certificate implies a value certificate for the same chain.
Growth. Consider an honest leader in a post-GST view $v$ after it has obtained, for every earlier view, either a value certificate or a skip certificate. Let $w<v$ be the highest view for which it has a value certificate $\mathrm{VC}_w(C)$. By the catch-up assumption, every view $y$ with $w<y<v$ has either a value certificate or a skip certificate. Since $w$ is the highest view with a value certificate, all such views have skip certificates. If a valid next block is available, the chained outer protocol lets the leader propose $C\circ B$, and the good case gives a decision certificate for the extended chain.
Takeaway
Chained Simplex uses the same inner protocol as single-shot Simplex. The only change is in the outer proposal rule: each leader extends a certified chain by one valid block.
This is why we often use a single-shot presentation: it isolates the core consensus mechanism, while chaining is just an outer-protocol change.
Your thoughts on X.