DSS

DSS 2026 / Day 2 / Amber Hall

Effectively exploring and testing state space of consensus protocols

Aarnav Bos

5:34 · Recording

Watch on YouTube ↗Open recording viewerOriginal programme entry
Download plain textDownload timestamped JSON

Source: YouTube automatic caption track · Exported 2026-11-16. Timestamps link to the source video. Cue end times were not supplied.

Transcript

0:00Um thanks for coming everybody. I'm

0:02pretty excited to present um some of the

0:05work my colleagues and I have been doing

0:07while testing Alpenlow which is Salana's

0:10new consensus protocol. I'll be

0:12presenting two approaches bisfuzz and

0:14forkraph and how we measured coverage.

0:17So state coverage for both of these

0:19approaches. A quick overview on openlow.

0:22It's um yeah new consensus protocol

0:25which has parallel processing of blocks

0:27complex interactions between components

0:29and is built with fast finality in mind.

0:32So while testing we have throughput

0:34correctness and parallelism right this

0:37is difficult to test effectively but

0:39like we have to be very rigorous and an

0:42overview on the assurance asymmetric

0:44research is a security partner for the

0:47Salana foundation and anza we do

0:49continuous assessment of changes and

0:51fixes for anza and we also did a

0:54differential review with fire dancer

0:56which is another client for Salana and

0:59for this we needed to build reusable and

1:01scalable tooling Right? Because you when

1:03you do a continuous audit, you just you

1:05don't want to duplicate efforts

1:07essentially. Um I'd start with bisfuzz

1:10which is um I think a well-known paper

1:12in testing consensus protocols um where

1:15you initialize the state of a network

1:17and then you perform a set of actions on

1:19it. And our assumption is that the bugs

1:23lie in the interactions or in the

1:26formation of the state, right? And as

1:28you can see here, these are like all the

1:29different kinds of configurations for

1:31the network. And to cover these

1:33exhaustively, we'd need like 1,024

1:36tests, which honestly like takes around

1:393 hours considering that each test is 10

1:42seconds because you have to run a

1:43cluster, you have to run a node and so

1:45on. Now this gets pretty difficult to do

1:47in a continuous fashion, right? So what

1:50you can then do is use something called

1:52T-way coverage. Um this is a research um

1:56under the umbrella of combinatorial

1:57testing where you select a subset of

2:01interactions. So since we believe that

2:03the interactions are in the way the

2:05state is formed or the bugs are um in

2:08the way the state is formed, you can say

2:10okay I have tested window start with a

2:1350/50 partition where everyone receives

2:16a corrupted message. I have done a

2:18window start um where the first round is

2:23mutated and again everyone gets the

2:25message. So it's not about exhaustively

2:29covering every feature with every um

2:33parameter with every value sorry but

2:35it's about a subset of parameters with

2:37all values and this again reduces the

2:40search space gives you some guarantee

2:42and allows you to measure the state

2:44space. Um, and this reduced our testing

2:47time to 10 minutes, which was pretty

2:48reasonable to do as part of continuous

2:50integration, right? And it found a lot

2:52of bugs and allowed us to be sure of

2:54what we had tested. Um, and I think one

2:58thing that's important to mention is

2:59generating these um, parameters and

3:02values can be done by a fuzzer, they can

3:04be done randomly, they can be done using

3:05genetic algorithms. It's really up to

3:07you. This is just one way to measure it.

3:11Um another uh approach that we took to

3:14test was using the classic fork graph.

3:17Um since we have parallelism um our

3:19assumption is that the bugs lie in the

3:22order of events and since you know over

3:25the network there's no guarantee in the

3:26order. Um we want to test state after a

3:31series of actions. Now this is pretty

3:32common with interpreters where executing

3:34bite code or any sort of state machine,

3:36right? So sequence coverage can be used

3:39for that. And to give you an example,

3:41let's say we have eight slots with two

3:43blocks each cuz everyone loves

3:45equivocation. Um, and five different

3:48resolutions of how a block can end. You

3:50have like a finalized block, you have a

3:51skip block, you have a block with a

3:53fallback, and maybe just a block that

3:55was proposed, but no one actually voted

3:56on it. This is like an insanely large

3:59number to test exhaustively, right? So

4:02what you can then do is use something

4:03called sequence coverage where you say

4:06okay I don't care about the adjacency of

4:09the events but I care that they happen

4:10in order. So suppose for the same block

4:14one uh for the same slots sorry you get

4:16block 1 B and 1 A while 1 B is complete

4:21but 1 A is finalized. So you should

4:24still be able to finalize after you get

4:26a competing block first slot. Um yeah,

4:30in general. So this tests the order of

4:32events but not adjacency. Um and again

4:34allows you to reduce the amount of tests

4:36that you need to do and allows you to

4:38measure what you've tested.

4:41Um so to summarize, if you want to test

4:44actions after state, so you want to

4:46measure the diversity of your state, you

4:48use TVA coverage. And if you want to

4:50measure um or if you want to test after

4:54um if you want to test your state after

4:56a series of actions, you would use

4:57sequence coverage.

5:00Um yeah, one more thing to mention is

5:03that this suffers the same problem as

5:06fuzzing does, right? Where you need to

5:07model your input space and you still are

5:10constrained by time. But I think this

5:13offers a pretty good compromise on

5:17knowing what you're testing, right? cuz

5:18if you just have like a series of

5:20events, you don't really know how much

5:22of the state space you've tested. Thank

5:25you. And happy to chat more after the

5:28talk if anybody has any questions about

5:30applicability or whatever.

Source and accuracy details

Source export SHA256: 199ba4c8dfc6bc676d60ff2202110f51c09dd7acd42c07dcb851d51084c27aaf