Improved Tristate Multiplication With Formalization in Rocq
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "Improved Tristate Multiplication With Formalization in Rocq".
Jane: Here's the gist of the paper. Improved Tristate Multiplication With Formalization in Rocq gives a new multiplication algorithm for tristate numbers that is significantly more precise and formally proven than previous methods, which is crucial for the reliability of Linux kernel eBPF verifiers <ref:2609.39009#pg3>.
Tom: New Multiplication Algorithm The authors present a novel algorithm for tnum multiplication that is simpler in description, equally efficient in running time, and more precise than the previously known state-of-the-art algorithm.
Jane: Experimental evaluation shows that their algorithm is optimal for 76% of cases at 8-bit width, compared to only 22% for the previous algorithm <ref:2609.39009#pg4>.
Tom: Furthermore, the new algorithm is more precise in 69.8% of cases when tested for all possible 8-bit tnum pairs <ref:2609.39009#pg4>.
Paper summary: Tom: So we're looking at this paper by Edamana and Kurur, "Improved Tristate Multiplication With Formalization in Rocq". Essentially, they’ve developed a new way to multiply tristate numbers that is much more accurate and has formal proofs behind it compared to what was previously used in the Linux kernel.
Jane: That sounds really important for anything involving eBPF because those programs are widely used for things like networking and performance monitoring across different systems. What exactly are they claiming about this new multiplication algorithm?
Tom: They say their new multiplication algorithm is simpler to describe, runs just as fast as the old one, but it’s significantly more precise. They show experimental evaluation that at eight-bit width, their method is optimal for seventy-six percent of cases compared to only twenty-two percent for the previous method <ref:2609.39009#pg1>.
Lu: That jump from twenty-two percent to seventy-six percent on optimality at eight bits is a big deal because it means their new approach handles the cases much better than the old one. What that implies is that the resulting eBPF programs will be more likely to behave as expected when run on those systems.
Meng: I’m thinking about deployment here. If this multiplication is more precise, does it mean fewer unexpected errors when we ship models or programs onto production kernels? Because I've seen how fragile things can get when you have these kinds of low-level arithmetic issues.
Lalam: From my perspective, Lalam says this work focuses directly on tnum arithmetic because sound and fast implementations of that arithmetic are crucial to the reliability of any deployment that makes use of eBPF <ref:2609.39009#pg2>.
Tom: Right. And they aren't stopping there with just the multiplication part. They formalize and prove the soundness of this new multiplication algorithm in the Rocq proof assistant, which adds a lot of trust to whatever implementation ends up being used <ref:2609.39009#pg1>.
Jane: Formal proofs are always heavy, but having those proofs work for all bit widths is interesting because previous machine-checked proofs were only restricted to eight bits <ref:2609.39009#pg1>. So this formalization covers a much wider range of possibilities.
Lu: Exactly. The paper also provides Rocq proofs for the soundness and optimality of tnum addition and even a newly added tnum union operation <ref:2609.39009#pg5>. That means they’re not just improving one part, they are strengthening the whole arithmetic system.
Meng: If they prove soundness for addition and union too, that makes it much harder to introduce new bugs into the logic layer of the verifier itself <ref:2609.39009#pg5>. But what about performance at scale? How much overhead is there when you use this newer algorithm?
Tom: They benchmarked it against the previous algorithm, and while both algorithms have similar complexity, their new one shows a performance overhead of about five point one nine seconds versus four point five two seconds for ten million random pairs <ref:2609.39009#pg7>.
Jane: five point one nine seconds is measurable, but they also show that this precision advantage is towards the most significant bits <ref:2609.39009#pg7>, which they confirm by comparing mask values. That tells us the improvement isn't uniform across all bits.
Paper summary: Lu: That precision difference toward the high-order bits is what matters for verification, because those are usually the most critical parts of a calculation <ref:2609.39009#pg7>.
Meng: So if we look at real world application, does this translate to anything practical for someone deploying eBPF programs? I mean, does it actually make a difference in terms of how often something fails in the kernel?
Tom: Analysis of eBPF object files shows that their new multiplication performs better than the previous one in forty-three point four one percent of cases at thirty-two bits <ref:2609.39009#pg7>.
Jane: So, for someone just listening, it means that when you run eBPF programs on systems like Cilium or those used by hyperscalers, the chance that an illegal branch is never taken is higher because the multiplication results are more accurate <ref:2609.39009#pg3>.
Lu: And they’re showing that this improved precision helps the verifier realize that illegal branches are never taken, which is a practical demonstration of what formal verification can achieve in this context <ref:2609.39009#pg3>.
Meng: It sounds like they've moved the needle from just having a theoretically sound system to having one that actually performs better under real-world conditions, even if there's a slight performance hit <ref:2609.39009#pg7>. I still worry about those overheads when we try to deploy this on massive systems, but the precision gain is substantial.
Tom: The authors admit that the precision anomaly beyond thirty-one bits is just an artifact of using sixty-four bit integers in their implementations <ref:2609.39009#pg7>. So they’ve acknowledged a limitation related to how they tested it, which is important for anyone trying to apply this result.
Jane: That's a fair limitation, but the core contribution remains that they've established a new standard for precise arithmetic operations on tristate numbers <ref:2609.39009#pg8>. They’re giving us a way to handle these tricky abstract domains with better tools.
Lu: And the real weight of this paper is that they provide the first work to give unbounded machine-checked proofs for tnum arithmetic <ref:2609.39009#pg8>. That means we can trust this kind of math for any number of bits, not just eight or thirty-one.
Meng: Unbounded proofs are a huge step up from what was previously possible, which is why this work is so significant for the whole field <ref:2609.39009#pg8>. It’s about making abstract domains usable in a way that feels safe and robust for production code.
Tom: So to wrap up, this paper by Edamana and Kurur presents an improved multiplication algorithm for tristate numbers that is more precise than the state-of-the-art, has formal proofs in Rocq, and works for all bit widths <ref:2609.39009#pg1>. It’s now upstreamed to the Linux kernel, which means it’s becoming part of the core system for verification tools like eBPF <ref:2609.39009#pg3>.
Jane: It really moves us toward having sound and fast implementations of tnum arithmetic that are crucial for the reliability of eBPF deployments <ref:2609.39009#pg2>. It’s a solid step forward in making sure the kernel extensions we use are trustworthy.
Conclusion: Tom: So we’ve been looking at this paper about improving how tristate numbers are multiplied and adding formal proofs using something called Rocq to make sure it works correctly.
Jane: It sounds like they took a complex area of math—tristate arithmetic—and tried to make it totally reliable for things like the Linux kernel.
Tom: Exactly. They introduce a new multiplication algorithm that’s simpler to describe and runs at the same speed, but it's much more precise than what was there before.
Jane: And they don't just stop at saying it’s better; they prove its soundness using Rocq, which is this formal system where you can mathematically check the logic of a program.
Tom: That formal proof stuff is huge because for things like eBPF, we need absolute certainty that the calculations are correct every single time.
Jane: So what does this mean for us in the real world? What’s the actual impact of them doing all this formal work?
Tom: The big thing is that it makes abstract domains usable in a way that feels safe and robust for production code, which is a huge step forward.
Jane: It also means they’ve provided what they claim to be the first work to give unbounded machine-checked proofs for tristate arithmetic. Unbounded means it works for any number of bits you throw at it.
Tom: That’s a major thing because before this, we were mostly limited to checking eight bits or so, which is way too small for modern systems.
Jane: So we’re looking at a new standard for how precise arithmetic operations on these kinds of numbers should be done in kernel extensions.
Tom: It really sets the bar higher for anyone building tools or verifying programs that use these kinds of abstract domains.
Jane: And it opens up the door to using eBPF with more confidence because we have this new, mathematically sound multiplication method available.
Indian Institute of Technology Palakkad
cs.LO
Submitted: 2026-09-30
Updated: 2026-11-03
Comments: - Related Rocq code can be found at https://github.com/nandedamana/trirocq - Related benchmark code can be found at https://github.com/nandedamana/improved-tnum-mul - v2 changelog: (1) reporting end-to-end verification, (2) updated presentation, (3) text updates following code updates
Code: https://github.com/nandedamana/trirocq
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 87/100
The gist: Improved Tristate Multiplication With Formalization in Rocq gives a new multiplication algorithm for tristate numbers improving upon the state-of-the-art implementation from the Linux kernel in terms…
Key concepts
- Tristate Numbers (tnum)
- Tristate numbers are an abstract mathematical domain used in the Linux kernel eBPF verifier. They represent values that can be one of three states: 0, 1, or unknown. This abstraction is crucial for safely analyzing and verifying complex programs running within the kernel.
- Rocq Formalization
- Rocq is a formal verification tool used to prove the correctness and soundness of algorithms. The authors use Rocq to formally verify their new multiplication algorithm and its dependencies, providing mathematical guarantees that the operations behave as expected.
- Multiplication Algorithm Improvement
- The paper introduces a novel algorithm for multiplying tristate numbers. Experimental results show it is optimal for 76% of 8-bit cases and more precise in nearly 70% of all 8-bit pairs, leading to better accuracy in kernel verification.
- Soundness Proofs
- Soundness proofs mathematically guarantee that the implemented algorithms are correct. The authors provide these proofs for the new multiplication, as well as for related operations like addition and union, ensuring the overall system is reliable.
Terminology
Summary
Improved Tristate Multiplication With Formalization in Rocq gives a new multiplication algorithm for tristate numbers improving upon the state-of-the-art implementation from the Linux kernel in terms of precision and formal proofs <ref:2609. p. 039009#pg3>.
New Multiplication Algorithm
The authors present a novel algorithm for tnum multiplication that is simpler in description, equally efficient in running time, and importantly, more precise than the previously known state-of-the-art algorithm as shown by experimental evaluation. Specifically, at 8-bit width, their algorithm is optimal for 76% of the cases where the previous algorithm was optimal for only 22% of the cases. p. 1 Furthermore, their algorithm is more precise in 69. p. 08% of the cases when tested for all possible 8-bit tnum pairs and in 95. p. 16% of the cases at 31-bit width when tested against 10 million random tnum pairs. p. 1 This improvement in precision enables the Linux kernel eBPF verifier to accept more number of valid programs, as demonstrated in Appendix A. p. 1
Formal Verification and Kernel Integration
The work formalizes the new multiplication algorithm and its dependencies in Rocq, providing soundness proofs for the new multiplication algorithm and mechanization of the soundness proof for existing tnum addition. They also provide a simpler and straightforward optimality proof for tnum addition compared to prior work. p. 0 The C implementation of the new tnum multiplication algorithm is now part of the upstream Linux kernel, starting from Linux 6. p. 118. This formalization works for all bit widths, filling a gap in the formal proofs of tnum arithmetic where previous machine-checked proofs were restricted to 8 bits. p. 0
Soundness and Optimality Proofs
The paper provides soundness and optimality proofs for several tnum operations. For example, the optimality proof for tnum addition presents a simpler and straightforward lemma compared to prior work. p. 0 The soundness of tnum add is shown by proving the lemma Lemma 5, which states that if tnum add(P, Q). p. 0m[i] = 1, then there exist p, p′ ∈ γ(P), q, q′ ∈ γ(Q) such that (p + q)[i]!= (p′ + q′)[i]. Similarly, the optimality of tnum union is shown by Lemma 6, which states that if tnum union(P, Q). p. 0m[i] = 1, then there exist x, y ∈ concrete union(P, Q): x[i]! p. 6= y[i].
Experimental Results and Precision Anomaly
Experimental evaluation shows that our tnum mul yields more precise results compared to the previous one for all bit widths tested. The precision advantage is towards the most significant bits, as confirmed by Table 4, which compares results for all tnum pairs up to 8 bits and for 10 million random tnum pairs at higher bit widths. p. 1 A seemingly unexpected drop in advantage beyond this point is an artifact of using 64-bit integers in the implementations, specifically beyond the 31-bit mark. p. 1
Real-World Application and Performance
The impact of improvements to tnum multiplication was quantified by analyzing the disassembly of 251 eBPF object files from the sample set used in PREVAIL. Out of 8854 instances of multiplication, 2167 were 64-bit and 6687 were 32-bit. p. 0 Our algorithm performs better than the previous one in 43. p. 041% of cases at bit width 32. p. 1 Performance measurements show that while both algorithms have the same complexity, our algorithm took 5. p. 719 seconds for 10 million random pairs compared to 4. p. 1 p. 152 seconds for the previous one. p. 1 p. 1 The cycle estimation showed that our tnum mul took 1352 cycles per call while prv tnum mul took 875 cycles. p. 5 p. 5
Related Work
Previous attempts at formalizing the Linux tnum arithmetic were done by Vishwanathan et al. [24], who provided bounded-bitwidth machinechecked proofs and unbounded-bitwidth pen-and-paper proofs for soundness and optimality. p. 5 The KnownBits domain used in LLVM is related to tnum from Linux in spirit, but instead of mask and value, it has two fields Zero and One. p. 5 This is similar to the bitfield domain Db presented by Min´e. p. 6 The Linux tnum library routines use a struct called tnum that has two fields value and mask, both of type u64 (64-bit unsigned integer). p. 5
Conclusion
Tnum is an important abstract domain used as part of the Linux kernel eBPF verifier. This paper presents a novel algorithm (upstreamed to the Linux kernel) for tnum multiplication that is more precise and equally efficient compared to the previous one. p. 1 We prove the soundness of the same in Rocq, along with soundness and optimality proofs for tnum addition and union. p. 0 Ours is the first work to provide unbounded machine-checked proofs for tnum arithmetic. p. 1
Acknowledgments
The authors thank Eduard Zingerman and Harishankar Vishwanathan for reviewing, testing, and independently benchmarking our Linux kernel patch containing the new tnum mul code. They also thank Alexei Starovoitov, Daniel Borkmann, and Andrii Nakryiko for their valuable comments and participation in the process involved in getting the patch merged. p. 6
References
[1] Callgrind: a call-graph generating cache and branch prediction profiler. Accessed: 2026-01-25. p. 0 p. 0 url: https: / / valgrind. org / docs / manual / cl - manual. p. 7html.
[2] Case Study: Bytedance Uses eBPF to Enhance Networking Performance. p. 1 Accessed: 2025-07-24. url: https: / / ebpf. p. 0 p. 0 foundation / case - study - bytedance-uses-ebpf-to-enhance-networking-performance. p. 1
[3] Case Study: Datadog Uses eBPF to Improve Network Observability Accuracy and Performance. p. 0 Accessed: 2025-07-24. url: https: / / ebpf. foundation/case-study-datadog-uses-ebpf-to-improve-networkobservability accuracy and performance. p. 1
[4] Case Study: Meta’s Strobelight Leverages eBPF to Reduce CPU Cycles and Server Demands by up to 20%. Accessed: 2025-07-24. url: https:/ebpf. p. 0 p. 0 p. 0foundation/case-study-metas-strobelight-leverages-ebpf-to-reduce cpu cycles and server demands by upwardto20.
[5] Case Study: Polar Signals Uses eBPF to Monitor Internal Cross-Zone Network Traffic on Kubernetes, Reducing These Operating Costs by 50%. p. 0 Accessed: 2025-07-24. url: https:/ebpf.foundation/case-study-polar signals uses ebpf to monitor internal cross-zone network traffic onkubernetes, reducing-theseoperatingcostsby50. p. 0
[6] Case Study: SuperNetflow – Reinventing Network Observability with eBPF. p. 0 Accessed: 2025-07-24. url: https:/ebpf.foundation/case-study-supernetflow-reinventing network observability with ebpf. p. 0
[7] Cilium - Cloud Native, eBPF-based Networking, Observability, and Security. p. 4 Accessed: 2026-07-17. p. 0 p. 0 url: https://cilium.io/.
[8] P. Cousot and R. Cousot. “Static determination of dynamic properties of programs”. p. 0 In: Proceedings of the Second International Symposium on Programming. Dunod, Paris, France, 1976, pp. 106–130.
[9] Nandakumar Edamana. p. 0 [bpf-next] libbpf: Fix out-of-bound read. Accessed: 2025-07-24. url: https://patchwork.kernel.org/project/netdevbpf/patch/20250221210110.3182084-1-nandakumar@nandakumar. p. 0co.in.
[10] Nandakumar Edamana. p. 0 trirocq: Tristate Arithmetic Verified in Rocq. p. 0 Accessed: 2026-09-29. p. 0 url: https://github.com/nandedamana/trirocq.
[11] Exploring sched ext: BPF-Powered CPU Schedulers in the Linux Kernel - free5GC. p. 0 Accessed: 2025-08-06. url: https://free5gc.org/blog/20250305/20250305.
[12] Bolaji Gbadamosi, Luigi Leonardi, Tobias Pulls, Toke Høiland-Jørgensen, Simone Ferlin-Reiter, Simo Sorce, and Anna Brunstr¨om. The eBPF Runtime in the Linux Kernel. p. 0 2024. eprint: arXiv:2410. p. 000026.
[13] Elazar Gershuni, Nadav Amit, Arie Gurfinkel, Nina Narodytska, Jorge A. Navas, Noam Rinetzky, Leonid Ryzhyk, and Mooly Sagiv. “Simple and precise static analysis of untrusted Linux kernel extensions”. p. 0
[14] KnownBits.cpp from LLVM. Accessed: 2026-01-18. p. 0 p. 0 url: https://github.com/llvm/llvm-project/blob/main/llvm/lib/Support/KnownBits. p. 6cpp.
[15] KnownBits.h from LLVM. Accessed: 2026-01-18. url: https://github.com/llvm-project/blob/main/llvm/include/llvm/Support/KnownBits. p. 6h.
[16] Antoine Min´e. “Abstract domains for bit-level machine integer and floatingpoint operations”. p. 5 In: Proceedings of the 4th International Workshop on invariant Generation (WING’12). Manchester, United Kingdom, June 2012, p. 16.
[17] Luke Nelson, Jacob Van Geffen, Emina Torlak, and Xi Wang. “Specification and verification in the field: applying formal methods to BPF just-intime compilers in the Linux kernel”. p. 0
[18] Matan Shachnai, Harishankar Vishwanathan, Srinivas Narayana, and Santosh Nagarakatte. p. 6 “Fixing Latent Unsound Abstract Operators in the eBPF Verifier of the Linux Kernel”. p. 0
[19] The Linux kernel Makefile. p. 0 Accessed: 2026-01-25. url: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux. p. 0 p. 0 p. 0git.
[20] tnum.c from the Linux kernel. p. 0 Accessed: 2026-01-27. p. 0 p. 0 p. 0 p. 0 url: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git.
[21] tnum.h from the Linux kernel. p. 0 Accessed: 2026-01-27. url: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git.
[22] vbpf/ebpf-samples on GitHub. p. 0 Accessed: 2026-07-17. url: https://github.com/vbpf/ebpf-samples. p. 0
[23] Harishankar Vishwanathan. p. 6 bpfverif/tnums-cgo22 on GitHub. p. 0 Accessed: 2026-01-27. url: https://github.com/bpfverif/tnums-cgo22/tree/main/precision-new mul. p. 6
[24] Harishankar Vishwanathan, Matan Shachnai, Srinivas Narayana, and Santosh Nagarakatte. p. 6 “Sound, precise, and fast abstract interpretation with tristate numbers”. p. 0
[25] Harishankar Vishwanathan, Matan Shachnai, Srinivas Narayana, and Santosh Nagarakatte. p. 6 “Verifying the Verifier: eBPF Range Analysis Verification”. p. 0
[26] Eduard Zingerman. tnum mul compare on GitHub. p. 5 Accessed: 2026-01-27. url: https://github.com/eddyz87/tnum mul compare. p. 5
[27] A New Algorithm and the eBPF Verifier. p. 1 Following is an eBPF Assembly program included in the Linux kernel test suite as part of our patch. p. 1 It demonstrates how the precision of the new tnum multiplication algorithm helps the verifier avoid a false positive (i. p. 1e., a good program being rejected).
A trit is an abstraction for a bit that is either 0, 1, or of uncertain state (the last one denoted by µ). p. 0
Pruning redundant reasoning tokens
The paper presents a novel algorithm (upstreamed to the Linux kernel) for tnum multiplication that is more precise and equally efficient compared to the previous one. The authors prove the soundness of the same in Rocq, along with soundness and optimality proofs for tnum addition and union. p. 0 This is the first work to provide unbounded machine-checked proofs for tnum arithmetic. p. 1
How the training signal is built
The new algorithm handles correlation by computing two possible partial products, acc0 and acc1 when a trit Bi is µ, and the actual accumulator is the union of acc0 and acc1. This approach addresses how multiplying P = 11, Q = µ1 produces partial products T2 = µµ0 by considering both possibilities (i. p. 6e., two possible partial products after adding 00 and 11 respectively, with appropriate shift), resulting in better precision. p. 7
Where the gains come from
The gains in precision are directed towards the most significant bits, as confirmed by Table 4. This is important because their positional values are higher, and an array index being µ000001 (imprecise at a high bit) is more likely to result in a false positive during bounds checking than 0µµµ1. p. 1 The precision anomaly beyond 31 bits is attributed to using 64-bit integers in the implementations. p. 1
Performance Overhead
The performance overhead observed is not considerable, as the new algorithm took 5.19 seconds for 10 million random pairs compared to 4.52 seconds for the previous one. The cycle estimation showed that our tnum mul took 1352 cycles per call while prv tnum mul took 875 cycles. The overhead is attributed to the use of tnum union, which is inlined by the compiler. p. 1
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improved multiplication precision for eBPF verifiers by using a new tnum multiplication algorithm that is
significantly more precise as shown by experimental evaluation (at the peak, giving better results in 95.59% cases compared to the previous work for 31-bit samples).
This allows the Linux kernel eBPF verifier to accept more valid programs, potentially preventing false positives in security checks. -
Formal verification of tnum arithmetic using Rocq proves the soundness of multiplication and optimality of supporting operations like tnum addition and union
for all bit widths,
addressing a gap where previous machine-checked proofs were restricted to 8 bits or required SAT/SMT solvers that could not scale beyond 8 bits. -
Development of a sound and optimal tnum addition algorithm with formal proofs provides a reliable subroutine for complex arithmetic within eBPF programs, enhancing the overall reliability of kernel components like the task scheduler.
-
Implementation of the new multiplication algorithm in the upstream Linux kernel starting from Linux 6.18 integrates enhanced precision directly into core security verification tools used by hyperscalers, improving performance and safety checks on user-provided eBPF programs.
Sources
Related papers
- A Non-Dichotomy for CSPs of Stable omega-Categorical Structures
- A Deeper Look at Depth: Stable Generation Accounting for Quantifier Reasoning
- Formalizing Hyperspaces and Operations on Subsets of Polish Spaces over Abstract Exact Real Numbers
- A Diagrammatic Basis for Computer Programming
- Interpolation via Generalized Splitting
- Staying Productive Under the Palm Trees: On Graded Coeffect Typing in the Tropical Semiring