DSS 2026 / Day 2 / Amber Hall
Effectively exploring and testing state space of consensus protocols
Aarnav Bos
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
- Names, organizations, technical terms, code and numbers may be misrecognized.
- Source wording and disfluencies are preserved; no editorial corrections were applied.
- Export contains whole-second cue starts only; cue ends and subsecond timing are unavailable.
- A full caption-track export does not establish that every spoken word is represented.
- Automatic YouTube captions; not human-verified against the audio.
Source export SHA256: 199ba4c8dfc6bc676d60ff2202110f51c09dd7acd42c07dcb851d51084c27aaf