> ## Test state machine replication with a chain of blocks workload

> Learn how to test state machine replication. Use our chain of blocks workload to test your SMR.

> Fetch the complete documentation index at: https://antithesis.com/docs/llms.txt
> Use this file to discover all available pages before exploring further.

---

State machine replication (SMR; a.k.a. Replicated State Machine or RSM) is an architectural pattern for fault-tolerant, high-consistency distributed systems. It can be summarized as follows: a set of replicas start in the same state, then apply the same sequence of state-modifying commands to eventually progress through the same sequence of states. SMR is a foundational building block in distributed systems of all kinds, including databases, message queues, and blockchains. If a system uses Raft or Paxos, there's a good chance it implements some variant of SMR.

In this article, we'll discuss SMR informally. Then, we'll detail a generalized strategy, “Chain of Blocks”, for testing SMR frameworks (including, by extension, the consensus protocols used in their construction). “Chain of Blocks” is elegant and easy to implement, and we've already used it to uncover consensus issues in several Raft implementations.

You'll learn about:

- State Machine Replication
- Consensus protocols and Atomic Broadcast
- The Chain of Blocks workload

## State machine replication

In distributed systems, redundancy is often a key requirement. Whether it's for fault tolerance and availability, or scalability, it's frequently desirable to have multiple copies of the same state. For example, to increase the read throughput of a K/V store, we might add more replicas to service more reads simultaneously.

SMR provides a formal structure for deriving these copies. Under this approach, each replica starts in some known initial state (the empty state, or a snapshot of some valid earlier state), and changes to the state happen via commands that transform it. For example, in the case of our K/V store, creating a new value is a transition function between the states before and after the K/V pair exists in the store.

## Atomic broadcast

SMR is conceptually simple if we can guarantee that all replicas will receive all commands in the same order. If a replica skips a command, or applies it twice, or applies it out of order, it will diverge from the rest, leading to an inconsistent global state. Hence, the replication problem reduces to the problem of *total order delivery* -- that is, of providing this common sequence.

A protocol that can provide a set of replicas with a totally ordered sequence of commands sequence is said to be an [atomic broadcast](/docs/resources/blockchain_property_catalog/#consensus-layer). Atomic broadcast is most commonly implemented by using a distributed consensus algorithm (e.g. [Multi-Paxos](https://en.wikipedia.org/wiki/Paxos_\(computer_science\)#Multi-Paxos), [Raft](https://raft.github.io/raft.pdf), or [Viewstamped Replication](https://www.cs.princeton.edu/courses/archive/fall11/cos518/papers/viewstamped.pdf)) to incrementally build the sequence.

## Guarantees and test objectives

Consensus protocols are notoriously hard to implement. However, what they provide and how they behave is quite simple to describe: all replicas eventually deliver the same sequence of commands in the same order. We can summarize the main safety property as follows:

If any replica delivers command C as its nth command, then all replicas eventually deliver C as their nth command.

This concisely captures all the things we never want to see: messages delivered out of order, duplicated, corrupted, skipped.

On the liveness side, assuming we restart crashed replicas, we expect all our replicas to recover and eventually make forward progress, so our main property is:

A client submitting a command C is eventually successful, and C is eventually applied by all replicas.

Our objective is to develop a workload -- code that exercises a system under test -- that will unmistakably surface these issues. We want this methodology to be applicable to any replicated state machine, regardless of the underlying consensus protocol and its implementation details.

## Chain of Blocks

Chain of Blocks (CoB) is a workload designed to test the primary safety and liveness properties of replicated systems.

We start by defining our state machine. The state to be tracked is a simple tuple (n, h), where n is a count of applied commands, and h is a running checksum that incorporates each prior command's content. We implement a single command accordingly.

Next, we implement a stateless client whose only responsibility is submitting new commands, each consisting of an arbitrary array of bytes:

```
WHILE TRUE DO:
    block_size = random(min, max)
    block <- randomBytes(block_size)
    client.propose(block)
END
```

Block proposals may fail; this is expected when testing in the presence of failures.

### Safety monitoring

We expect each replica to (eventually) go through the exact same sequence of (count, hash) tuples. If we detect even a single case where two replicas have a different hash after the same number of blocks, we know we have a problem.

It follows that we need to track the hash at each replica after each transition and compare it with the hash with the same index at each other replica.

In practice, there are multiple ways to do this:

- Replicas could exchange this information with each other directly
- Replicas may record on disk for later offline analysis
- Some external process may poll replicas, or replicas may push to some external process

All of these approaches are valid, and have different tradeoffs. The observer that tracks replica transitions builds a table containing the hash after N blocks for each replica.

| n | Replica 1 | Replica 2 | Replica 3 |
| :---- | :---- | :---- | :---- |
| 0 | 0x00000000 | 0x00000000 | 0x00000000 |
| 1 | 0XFB870A32 | 0XFB870A32 | 0XFB870A32 |
| 2 | 0x387CCD3H | 0x387CCD3H | 0x387CCD3H |
| … | … | … | … |

Divergence can be trivially detected.

Moreover, perfect observability is not required, if the observer does not learn the hash after N blocks for some replica, it can still spot divergence after N+1 blocks.

| n | Replica 1 | Replica 2 | Replica 3 |
| :---- | :---- | :---- | :---- |
| … | … | … | … |
| 10 | 0xFD33289D | 0xFD33289D | 0xFD33289D |
| 11 | 0x487B3CE4 | Unknown | Unknown |
| 12 | 0xF7B2A890 | 0xF7B2A890 | 0xA38483F9 |

### Liveness Monitoring

The table-based approach described above can be used to also track progress of individual replicas to spot liveness violations. In the simplest form, the observer keeps track of the timestamp when each replica last incremented its command count. Any replica that fails to make progress for too long is considered stuck.

### Logging

A single logging statement after each transition of the state machine can provide a complete picture of the system's evolution over time. Consider the following example trace coming from a real system under test in Antithesis:

```
[...]
230.774 replica-0 Applied block 565 (8654C931) state: AAA25792 => D0A1C41D
230.877 replica-4 Applied block 565 (8654C931) state: AAA25792 => D0A1C41D
230.929 replica-3 Applied block 565 (8654C931) state: AAA25792 => D0A1C41D
[...]
296.227 replica-1 Applied block 565 (01C8F6D2) state: AAA25792 => C655FE21
296.302 replica-2 Applied block 565 (01C8F6D2) state: AAA25792 => C655FE21
296.413 replica-3 Applied block 565 (01C8F6D2) state: AAA25792 => C655FE21
```

First, three out of five replicas (replica-0, replica-4, and replica-3) each apply 8654C931 as the 565th block. Some time later, a different set (replica-1, replica-2, and replica-3) applies a different block (01C8F6D2) as the 565th. The states of the respective RSMs thus diverge (D0A1C41D versus C655FE21).

In this case, replica-3 is in both quorums, hinting at what may have happened. For example, one plausible hypothesis is that replica-3 truncated its logs, creating the conditions for the replica set to forget a previously-committed command and allowing replica-3 to participate in a rivalrous commit.

If we had failed to log this information and instead simply raised an error when divergence was detected, we wouldn't know where to look next. Armed with our logs, our workload captures everything we need to get to the bottom of this serious safety violation!