DSS 2026 — Effectively exploring and testing state space of consensus protocols Aarnav Bos Source video: https://www.youtube.com/watch?v=fd9DFOBbrP8 Automatic captions — not human-reviewed. Complete spoken-audio coverage is unverified. Source language tag: en (English). Source export SHA256: 199ba4c8dfc6bc676d60ff2202110f51c09dd7acd42c07dcb851d51084c27aaf [0:00] Um thanks for coming everybody. I'm [0:02] pretty excited to present um some of the [0:05] work my colleagues and I have been doing [0:07] while testing Alpenlow which is Salana's [0:10] new consensus protocol. I'll be [0:12] presenting two approaches bisfuzz and [0:14] forkraph and how we measured coverage. [0:17] So state coverage for both of these [0:19] approaches. A quick overview on openlow. [0:22] It's um yeah new consensus protocol [0:25] which has parallel processing of blocks [0:27] complex interactions between components [0:29] and is built with fast finality in mind. [0:32] So while testing we have throughput [0:34] correctness and parallelism right this [0:37] is difficult to test effectively but [0:39] like we have to be very rigorous and an [0:42] overview on the assurance asymmetric [0:44] research is a security partner for the [0:47] Salana foundation and anza we do [0:49] continuous assessment of changes and [0:51] fixes for anza and we also did a [0:54] differential review with fire dancer [0:56] which is another client for Salana and [0:59] for this we needed to build reusable and [1:01] scalable tooling Right? Because you when [1:03] you do a continuous audit, you just you [1:05] don't want to duplicate efforts [1:07] essentially. Um I'd start with bisfuzz [1:10] which is um I think a well-known paper [1:12] in testing consensus protocols um where [1:15] you initialize the state of a network [1:17] and then you perform a set of actions on [1:19] it. And our assumption is that the bugs [1:23] lie in the interactions or in the [1:26] formation of the state, right? And as [1:28] you can see here, these are like all the [1:29] different kinds of configurations for [1:31] the network. And to cover these [1:33] exhaustively, we'd need like 1,024 [1:36] tests, which honestly like takes around [1:39] 3 hours considering that each test is 10 [1:42] seconds because you have to run a [1:43] cluster, you have to run a node and so [1:45] on. Now this gets pretty difficult to do [1:47] in a continuous fashion, right? So what [1:50] you can then do is use something called [1:52] T-way coverage. Um this is a research um [1:56] under the umbrella of combinatorial [1:57] testing where you select a subset of [2:01] interactions. So since we believe that [2:03] the interactions are in the way the [2:05] state is formed or the bugs are um in [2:08] the way the state is formed, you can say [2:10] okay I have tested window start with a [2:13] 50/50 partition where everyone receives [2:16] a corrupted message. I have done a [2:18] window start um where the first round is [2:23] mutated and again everyone gets the [2:25] message. So it's not about exhaustively [2:29] covering every feature with every um [2:33] parameter with every value sorry but [2:35] it's about a subset of parameters with [2:37] all values and this again reduces the [2:40] search space gives you some guarantee [2:42] and allows you to measure the state [2:44] space. Um, and this reduced our testing [2:47] time to 10 minutes, which was pretty [2:48] reasonable to do as part of continuous [2:50] integration, right? And it found a lot [2:52] of bugs and allowed us to be sure of [2:54] what we had tested. Um, and I think one [2:58] thing that's important to mention is [2:59] generating these um, parameters and [3:02] values can be done by a fuzzer, they can [3:04] be done randomly, they can be done using [3:05] genetic algorithms. It's really up to [3:07] you. This is just one way to measure it. [3:11] Um another uh approach that we took to [3:14] test was using the classic fork graph. [3:17] Um since we have parallelism um our [3:19] assumption is that the bugs lie in the [3:22] order of events and since you know over [3:25] the network there's no guarantee in the [3:26] order. Um we want to test state after a [3:31] series of actions. Now this is pretty [3:32] common with interpreters where executing [3:34] bite code or any sort of state machine, [3:36] right? So sequence coverage can be used [3:39] for that. And to give you an example, [3:41] let's say we have eight slots with two [3:43] blocks each cuz everyone loves [3:45] equivocation. Um, and five different [3:48] resolutions of how a block can end. You [3:50] have like a finalized block, you have a [3:51] skip block, you have a block with a [3:53] fallback, and maybe just a block that [3:55] was proposed, but no one actually voted [3:56] on it. This is like an insanely large [3:59] number to test exhaustively, right? So [4:02] what you can then do is use something [4:03] called sequence coverage where you say [4:06] okay I don't care about the adjacency of [4:09] the events but I care that they happen [4:10] in order. So suppose for the same block [4:14] one uh for the same slots sorry you get [4:16] block 1 B and 1 A while 1 B is complete [4:21] but 1 A is finalized. So you should [4:24] still be able to finalize after you get [4:26] a competing block first slot. Um yeah, [4:30] in general. So this tests the order of [4:32] events but not adjacency. Um and again [4:34] allows you to reduce the amount of tests [4:36] that you need to do and allows you to [4:38] measure what you've tested. [4:41] Um so to summarize, if you want to test [4:44] actions after state, so you want to [4:46] measure the diversity of your state, you [4:48] use TVA coverage. And if you want to [4:50] measure um or if you want to test after [4:54] um if you want to test your state after [4:56] a series of actions, you would use [4:57] sequence coverage. [5:00] Um yeah, one more thing to mention is [5:03] that this suffers the same problem as [5:06] fuzzing does, right? Where you need to [5:07] model your input space and you still are [5:10] constrained by time. But I think this [5:13] offers a pretty good compromise on [5:17] knowing what you're testing, right? cuz [5:18] if you just have like a series of [5:20] events, you don't really know how much [5:22] of the state space you've tested. Thank [5:25] you. And happy to chat more after the [5:28] talk if anybody has any questions about [5:30] applicability or whatever.