Which Rust varint decoders match Go's binary.ReadUvarint (OP Stack span-batch / ENR uvarint) — differential harness + results

README.md

Which Rust varint decoders match Go's binary.ReadUvarint?

Reference data for OP Stack wire formats that specify an "unsigned Base128 varint, as defined in protobuf spec" — span-batch uvarint fields, and the opstack ENR entry.

op-node decodes both with Go's standard library encoding/binary.ReadUvarint. Any Rust decoder used on the same bytes must accept exactly the same set, or the two clients disagree on identical input. Background: ethereum-optimism/protocol-team#223, fixed for span batches in ethereum-optimism/optimism#22126.

Summary

crate	mismatches vs Go	no_std	verdict
prost 0.14	0 / 649,092	yes (default-features = false)	conformant
prost 0.13	0 / 649,092	yes	conformant
leb128 0.2	0 / 649,092	no (io-based)	conformant, std-only
integer-encoding 4	0 / 649,092	no	conformant, std-only
unsigned-varint 0.8	18,239 (14,444 over-strict)	yes	wrong varint family
quick-protobuf 0.8	3,795 (all over-lenient)	yes	truncates by design
leb128fmt 0.1	293,538	yes	not a drop-in

quick-protobuf (pulled in transitively by libp2p) exposes a public BytesReader::read_varint64, but discards bits past 63 on a ten-byte varint rather than erroring — its own source calls this "ESSENTIALLY A SILENT TRUNCATION", done deliberately for parity with Google's C++ implementation. Every one of its 3,795 mismatches is it accepting a value Go rejects.

unsigned-varint is not a buggy protobuf decoder — it implements the multiformats varint, which is minimal-only by definition. That is the trap: the crate name suggests generality, and the failure only shows on inputs a malicious peer or batcher controls.

Boundary behaviour

Every vector below is a legal question to ask of a Base128 decoder. value/+n = decoded value with n bytes left unconsumed.

vector	Go stdlib	prost .14	prost .13	leb128	int-enc	unsigned-varint
[] empty	reject	reject	reject	reject	reject	reject
[01] minimal	1/+0	1/+0	1/+0	1/+0	1/+0	1/+0
[81 00] non-minimal	1/+0	1/+0	1/+0	1/+0	1/+0	reject
[81 00 aa bb] trailing	1/+2	1/+2	1/+2	1/+2	1/+2	reject
10 bytes, terminator 00	1/+0	1/+0	1/+0	1/+0	1/+0	reject
10 bytes, terminator 01	2^63+1	2^63+1	2^63+1	2^63+1	2^63+1	2^63+1
10 bytes, terminator 02	reject	reject	reject	reject	reject	1/+0 (truncates)
10 bytes, terminator 7f	reject	reject	reject	reject	reject	2^63+1 (truncates)
[ff*9 01] = u64::MAX	u64::MAX	u64::MAX	u64::MAX	u64::MAX	u64::MAX	u64::MAX
[80*10] never terminates	reject	reject	reject	reject	reject	reject
[80*10 01] 11 bytes	reject	reject	reject	reject	reject	reject
[81] truncated	reject	reject	reject	reject	reject	reject

The two divergent rows are the whole bug: unsigned-varint rejects valid non-minimal encodings and silently truncates a value that overflows u64.

quick-protobuf (omitted from the table for width) matches Go on every row except the two overflow rows, where it returns 1 and 2^63+1 instead of rejecting — the truncation half of the same defect, without the minimality half.

Does "the protobuf spec" actually pin this?

Yes. The spec text cites protobuf rather than Go, so it is worth checking whether the two agree — they do. Go's own protobuf implementation, google.golang.org/protobuf/encoding/protowire.ConsumeVarint, returns the same verdict as binary.ReadUvarint on every vector above, including accepting [81 00] and rejecting a tenth byte above 0x01.

So spec-conformance and reference-implementation-conformance coincide here, and a decoder that matches one matches the other. There was no spec-vs-op-node conflict to adjudicate.

What #22126 shipped

A ~20-line port of binary.ReadUvarint (rust/kona/crates/protocol/protocol/src/batch/varint.rs) rather than a crate dependency. prost was the only conformant no_std candidate, and it was rejected for that crate specifically because kona-protocol compiles into the fault proof VM, where prost's unsafe fast path and its allocating DecodeError on the reject path both matter. Outside the FPVM those objections do not apply and prost is a reasonable choice.

Re-running this

# 1. Record Go's verdict for 649,092 byte strings.
go run gen_corpus.go > corpus.txt

# 2. Compare every candidate Rust decoder against it.
mkdir -p varintcmp/src && mv varintcmp-Cargo.toml varintcmp/Cargo.toml
mv varintcmp-main.rs varintcmp/src/main.rs && mv varintcmp-boundary.rs varintcmp/src/boundary.rs
cd varintcmp && cargo run --release -- ../corpus.txt   # full corpus
cargo run --release --bin boundary                     # the table above

Corpus composition: all 1- and 2-byte strings; exhaustive over an 11-symbol alphabet to depth 5; every tenth byte after nine-byte continuation prefixes, plus an eleventh byte; 400k random continuation-biased strings of length 0–12.

Add a row before trusting a new crate or version. A spec citation does not distinguish two varint families; only a differential run against binary.ReadUvarint does.

gen_corpus.go

// Generates a differential corpus for span-batch uvarint decoding: for each byte string, records
// what Go's binary.ReadUvarint (op-node's decoder) produces.
//
// Output line format: <hex> <ok:0|1> <value> <remaining_len>
package main

import (
	"bufio"
	"bytes"
	"encoding/binary"
	"encoding/hex"
	"fmt"
	"math/rand"
	"os"
)

func emit(w *bufio.Writer, b []byte) {
	r := bytes.NewReader(b)
	v, err := binary.ReadUvarint(r)
	ok := 0
	if err == nil {
		ok = 1
	} else {
		v = 0
	}
	remaining := r.Len()
	if ok == 0 {
		remaining = 0
	}
	fmt.Fprintf(w, "%s %d %d %d\n", hex.EncodeToString(b), ok, v, remaining)
}

func main() {
	w := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer w.Flush()

	// Empty input.
	emit(w, []byte{})

	// All 1- and 2-byte strings.
	for i := 0; i < 256; i++ {
		emit(w, []byte{byte(i)})
		for j := 0; j < 256; j++ {
			emit(w, []byte{byte(i), byte(j)})
		}
	}

	// Exhaustive over a reduced alphabet covering terminator/continuation and bit-width edges.
	alphabet := []byte{0x00, 0x01, 0x02, 0x03, 0x7E, 0x7F, 0x80, 0x81, 0x82, 0xFE, 0xFF}
	var rec func(prefix []byte, depth int)
	rec = func(prefix []byte, depth int) {
		if depth == 0 {
			return
		}
		for _, c := range alphabet {
			next := append(append([]byte{}, prefix...), c)
			emit(w, next)
			rec(next, depth-1)
		}
	}
	rec(nil, 5)

	// Nine-byte continuation prefixes crossed with every possible tenth byte: the boundary where
	// the two decoders disagreed.
	prefixes := [][]byte{
		{0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80},
		{0x81, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80},
		{0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
		{0x81, 0xFF, 0x80, 0xFE, 0x82, 0x80, 0xFF, 0x81, 0x80},
	}
	for _, p := range prefixes {
		for i := 0; i < 256; i++ {
			emit(w, append(append([]byte{}, p...), byte(i)))
			// And an eleventh byte, past the maximum width.
			for _, extra := range []byte{0x00, 0x01, 0x7F, 0x80, 0xFF} {
				emit(w, append(append(append([]byte{}, p...), byte(i)), extra))
			}
		}
	}

	// Random strings, biased toward continuation bytes so long varints are well covered.
	rng := rand.New(rand.NewSource(0x5eeded))
	for n := 0; n < 400000; n++ {
		b := make([]byte, rng.Intn(13))
		for i := range b {
			if rng.Intn(3) == 0 {
				b[i] = byte(rng.Intn(0x80)) // terminator
			} else {
				b[i] = byte(0x80 | rng.Intn(0x80)) // continuation
			}
		}
		emit(w, b)
	}
}

varintcmp-boundary.rs

//! Prints each candidate decoder's verdict on the consensus-critical boundary vectors.

use std::io::Cursor;

fn kona(buf: &[u8]) -> Option<(u64, usize)> {
    const MAX: usize = 10;
    let mut value = 0u64;
    let mut shift = 0u32;
    for (i, &byte) in buf.iter().take(MAX).enumerate() {
        if byte < 0x80 {
            if i == MAX - 1 && byte > 1 {
                return None;
            }
            return Some((value | ((byte as u64) << shift), buf.len() - i - 1));
        }
        value |= ((byte & 0x7F) as u64) << shift;
        shift += 7;
    }
    None
}

fn uvi(b: &[u8]) -> Option<(u64, usize)> {
    unsigned_varint::decode::u64(b).ok().map(|(v, r)| (v, r.len()))
}
fn prost14(b: &[u8]) -> Option<(u64, usize)> {
    let mut c = Cursor::new(b);
    prost::encoding::decode_varint(&mut c).ok().map(|v| (v, b.len() - c.position() as usize))
}
fn prost13(b: &[u8]) -> Option<(u64, usize)> {
    let mut c = Cursor::new(b);
    prost013::encoding::decode_varint(&mut c).ok().map(|v| (v, b.len() - c.position() as usize))
}
fn leb(b: &[u8]) -> Option<(u64, usize)> {
    let mut c = Cursor::new(b);
    leb128::read::unsigned(&mut c).ok().map(|v| (v, b.len() - c.position() as usize))
}
fn intenc(b: &[u8]) -> Option<(u64, usize)> {
    use integer_encoding::VarInt;
    u64::decode_var(b).map(|(v, used)| (v, b.len() - used))
}

fn qpb(b: &[u8]) -> Option<(u64, usize)> {
    let mut r = quick_protobuf::reader::BytesReader::from_bytes(b);
    r.read_varint64(b).ok().map(|v| (v, r.len()))
}

fn show(v: Option<(u64, usize)>) -> String {
    match v {
        None => "reject".to_string(),
        Some((val, rem)) => format!("{val}/+{rem}"),
    }
}

fn main() {
    let c9 = [0x80u8; 9];
    let mk = |first: u8, last: u8| {
        let mut v = vec![first];
        v.extend_from_slice(&c9[..8]);
        v.push(last);
        v
    };
    let cases: Vec<(&str, Vec<u8>)> = vec![
        ("[] empty", vec![]),
        ("[01] minimal", vec![0x01]),
        ("[81 00] non-minimal", vec![0x81, 0x00]),
        ("[81 00 aa bb] trailing", vec![0x81, 0x00, 0xAA, 0xBB]),
        ("10B term 0x00", mk(0x81, 0x00)),
        ("10B term 0x01 (bit63)", mk(0x81, 0x01)),
        ("10B term 0x02 OVERFLOW", mk(0x81, 0x02)),
        ("10B term 0x7f OVERFLOW", mk(0x81, 0x7F)),
        ("[ff*9 01] u64::MAX", vec![0xFF; 9].into_iter().chain([0x01]).collect()),
        ("[80*10] no term", vec![0x80; 10]),
        ("[80*10 01] 11 bytes", vec![0x80; 10].into_iter().chain([0x01]).collect()),
        ("[81] truncated", vec![0x81]),
    ];

    let names = ["go/kona", "prost .14", "leb128", "int-enc", "uvarint", "quick-pb"];
    let fns: [fn(&[u8]) -> Option<(u64, usize)>; 6] =
        [kona, prost14, leb, intenc, uvi, qpb];

    print!("{:<26}", "vector");
    for n in names {
        print!("{n:>14}");
    }
    println!();
    for (label, bytes) in &cases {
        print!("{label:<26}");
        for f in fns {
            let r = std::panic::catch_unwind(|| f(bytes)).map(show).unwrap_or("PANIC".into());
            print!("{r:>14}");
        }
        println!();
    }
}

varintcmp-Cargo.toml

[workspace]

[package]
name = "varintcmp"
version = "0.0.0"
edition = "2021"

[[bin]]
name = "varintcmp"
path = "src/main.rs"

[[bin]]
name = "boundary"
path = "src/boundary.rs"

[dependencies]
prost = "0.14.3"
prost013 = { package = "prost", version = "0.13.5" }
unsigned-varint = "0.8.0"
leb128 = "0.2"
integer-encoding = "4"
leb128fmt = "0.1"
bytes = "1"
quick-protobuf = "0.8.1"

varintcmp-main.rs

//! Compares candidate Rust varint decoders against a corpus of verdicts recorded from Go's
//! `binary.ReadUvarint` (op-node's span-batch decoder).
//!
//! Corpus line format: `<hex> <ok> <value> <remaining_len>`

use std::io::Cursor;

/// The port committed in kona.
fn kona_read_uvarint(buf: &[u8]) -> Option<(u64, &[u8])> {
    const MAX_VARINT_LEN_64: usize = 10;
    let mut value = 0u64;
    let mut shift = 0u32;
    for (i, &byte) in buf.iter().take(MAX_VARINT_LEN_64).enumerate() {
        if byte < 0x80 {
            if i == MAX_VARINT_LEN_64 - 1 && byte > 1 {
                return None;
            }
            return Some((value | ((byte as u64) << shift), &buf[i + 1..]));
        }
        value |= ((byte & 0x7F) as u64) << shift;
        shift += 7;
    }
    None
}

type Verdict = Option<(u64, usize)>; // (value, remaining bytes)

fn via_kona(b: &[u8]) -> Verdict {
    kona_read_uvarint(b).map(|(v, rest)| (v, rest.len()))
}

fn via_unsigned_varint(b: &[u8]) -> Verdict {
    unsigned_varint::decode::u64(b).ok().map(|(v, rest)| (v, rest.len()))
}

fn via_prost(b: &[u8]) -> Verdict {
    let mut cursor = Cursor::new(b);
    prost::encoding::decode_varint(&mut cursor).ok().map(|v| (v, b.len() - cursor.position() as usize))
}

fn via_leb128(b: &[u8]) -> Verdict {
    let mut cursor = Cursor::new(b);
    leb128::read::unsigned(&mut cursor).ok().map(|v| (v, b.len() - cursor.position() as usize))
}

fn via_integer_encoding(b: &[u8]) -> Verdict {
    use integer_encoding::VarInt;
    u64::decode_var(b).map(|(v, used)| (v, b.len() - used))
}

fn via_leb128fmt(b: &[u8]) -> Verdict {
    let mut fixed = [0u8; 10];
    let n = b.len().min(10);
    fixed[..n].copy_from_slice(&b[..n]);
    leb128fmt::decode_uint_slice::<u64, 10>(&fixed, &mut 0).ok().map(|v| (v, 0)).map(|(v, _)| (v, 0))
}

fn via_quick_protobuf(b: &[u8]) -> Verdict {
    let mut r = quick_protobuf::reader::BytesReader::from_bytes(b);
    r.read_varint64(b).ok().map(|v| (v, r.len()))
}

fn main() {
    let path = std::env::args().nth(1).expect("usage: varintcmp <corpus>");
    let corpus = std::fs::read_to_string(path).unwrap();

    let decoders: Vec<(&str, fn(&[u8]) -> Verdict, bool)> = vec![
        // (name, decoder, compare_remaining)
        ("kona read_uvarint", via_kona, true),
        ("unsigned-varint 0.8", via_unsigned_varint, true),
        ("prost 0.14", via_prost, true),
        ("leb128 0.2", via_leb128, true),
        ("integer-encoding 4", via_integer_encoding, true),
        ("leb128fmt 0.1", via_leb128fmt, false),
        ("quick-protobuf 0.8", via_quick_protobuf, true),
    ];

    let mut stats: Vec<(usize, usize, usize, Vec<String>)> =
        decoders.iter().map(|_| (0, 0, 0, Vec::new())).collect();
    let mut total = 0usize;

    for line in corpus.lines() {
        let mut parts = line.split(' ');
        let hex = parts.next().unwrap();
        let go_ok = parts.next().unwrap() == "1";
        let go_value: u64 = parts.next().unwrap().parse().unwrap();
        let go_remaining: usize = parts.next().unwrap().parse().unwrap();
        let bytes: Vec<u8> = (0..hex.len())
            .step_by(2)
            .map(|i| u8::from_str_radix(&hex[i..i + 2], 16).unwrap())
            .collect();
        total += 1;

        for (idx, (_, decode, cmp_remaining)) in decoders.iter().enumerate() {
            let got = std::panic::catch_unwind(|| decode(&bytes)).unwrap_or_else(|_| {
                stats[idx].3.push(format!("{hex}: PANIC"));
                None
            });
            let agrees = match (got, go_ok) {
                (Some((v, rem)), true) => {
                    v == go_value && (!*cmp_remaining || rem == go_remaining)
                }
                (None, false) => true,
                _ => false,
            };
            if agrees {
                stats[idx].0 += 1;
            } else {
                stats[idx].1 += 1;
                if go_ok && got.is_none() {
                    stats[idx].2 += 1; // rejected something Go accepts
                }
                if stats[idx].3.len() < 4 {
                    stats[idx].3.push(format!(
                        "{hex}: go={:?} got={:?}",
                        if go_ok { Some((go_value, go_remaining)) } else { None },
                        got
                    ));
                }
            }
        }
    }

    println!("corpus: {total} vectors recorded from Go binary.ReadUvarint\n");
    for (idx, (name, _, cmp_remaining)) in decoders.iter().enumerate() {
        let (ok, bad, over_strict, examples) = &stats[idx];
        let note = if *cmp_remaining { "" } else { " (value only)" };
        println!(
            "{name:<22} agree={ok:<7} MISMATCH={bad:<7} (of which over-strict: {over_strict}){note}"
        );
        for e in examples {
            println!("    {e}");
        }
    }
}