10 ms·

Bijou64: A variable-length integer encoding

261 points by justinweiss 4mo ago

cantalopes 4mo ago
I love the random hyperlink underlines on that page
- spiralganglion 4mo ago
  Credit to Roman Komarov who came up with the approach [1], and Todd Matthews [2] who made the art assets. 1: https://kizu.dev/svg-linked-parameters-workaround/ https://kizu.dev/svg-linked-parameters-workaround/ 2: https://www.seaofclouds.com https://www.seaofclouds.com
RedShift1 4mo ago
This seems quite convoluted just to avoid the "0 can be represented in more than one way" problem.
- nine_k 4mo ago
  It allows finding out the length (and allocating memory) after reading the first byte.
- ahoka 4mo ago
  I think it's neat.
- ape4 4mo ago
  Comparing a number to zero is something that's done a lot
  - Chaosvex 4mo ago
    True but also not particularly relevant?
- bjoli 4mo ago
  Having all numbers be valid in only one way is a great idea. So much that I believe webassembly enforced canonical leb128, at the cost of decoding speed. And say you have it as part of some other data. If you want to be able to hash it by the raw memory bytes, many different ways to represent a number becomes a problem.
- matja 4mo ago
  > canonicality matters — for signatures, content-addressing, or any kind of “two implementations must agree on the bytes” property If you don't do this properly, you end up with things like: - SAML XSW attack due to XML signature wrapping - ASN.1 BER/DER signature forgery - Bitcoin transaction malleability attacks
stebalien 4mo ago
I've used LEB128 (with canonicalisation) extensively and... this looks so much nicer for most use-cases (length prefixed, supports the full uint64 range without that extra 10th byte). The downside is the encoding size. LEB128 quickly grows to 2 bytes, but stays at 2 bytes all the way to 2^14. This is important if you're using these numbers as tags/identifiers as we were in the multicodec [1] project, or for network message lengths. bijou64 only gives you 500 <= 2 byte numbers. [1]: https://github.com/multiformats/multicodec https://github.com/multiformats/multicodec
- b_fiive 4mo ago
  sup steb, this is expede's work!
  - stebalien 4mo ago
    Sup b5! I always look forward to new work by expede (and n0).
- Someone 4mo ago
  > I’ve used LEB128 (with canonicalisation) extensively and... this looks so much nicer for most use-cases (length prefixed, supports the full uint64 range without that extra 10th byte) If you only want to encode uint64 numbers LEB128 could easily be tweaked to fit in 9 bytes in several ways: - using the offset trick described in this article would remove non-unique encodings (0x80 0x00 would encode 128) - never allowing encodings longer than 9 bytes would mean the MSB of any ninth byte would always be zero, so you could reuse that, and store 8 bits in any ninth byte, for a total of 7 bits in each of the first eight bytes plus 8 in the ninth = 64 Both tweaks would lose LEB128’s property that you can find where each number starts from any byte in the stream, but the encoding discussed here doesn’t have that property either.
willtemperley 4mo ago
Maybe someone can explain why an encoder would ever create the padding bytes allowed in LEB128. I contributed the parser for LEB128 in apple/swift-binary-parsing and I’m still none the wiser. I’m genuinely mystified.
- Chaosvex 4mo ago
  You wouldn't. It's a strange argument that can be countered with, "maybe don't do that?"
  - willtemperley 4mo ago
    So why does the spec allow it? Like a good engineer I read the spec and tested against the over-wide example encodings given.
    - Chaosvex 4mo ago
      Because it's not a real standard and there is no blessed RFC for it. The DWARF spec is as close as you'll get and it says, "The integer zero is a special case, consisting of a single zero byte." So in a way, it doesn't. Either way, a properly written decoder (and it's like ten lines) should really not have any problems with it. I was agreeing with you. Edit: to clarify, I was talking about the author's argument being strange, not yours.
      - willtemperley 4mo ago
        The WASM spec is more explicit about over-long LEB128 encoding. Edit: a properly written decoder is a lot more than 10 lines if you properly deal with integer overflow and both signed and unsigned ints.
- layer8 4mo ago
  The issue is that non-unique encodings are an attack vector, because parsers may in practice behave differently for noncanonical (or nominally invalid) encodings.
nine_k 4mo ago
In short: instead of a truly indefinite-length solution with a signal bit on the current byte saying whether to check the next byte, this uses a counter. Values 0x0 to 0xF7 are one-byte integers, 0xF8 to 0xFF use the upper 5 bits as a counter for the number of subsequent bytes. This limits the maximum magnitude to slightly less than 2 ^ 264 (almost all 33-byte values), which seems to be okay for practical computations. The proposed standard limits the supported size to u64 though. The upsides: the size of the integer is apparent upon reading the first byte, and every number has exactly one canonical representation. I wish C strings had been standardized around something similar, instead on null termination. > ...adversarial input, which is rarely in the test suite. This made my scratch my head. My tests for quite pedestrian APIs often contain adversarial input of obvious shapes. I though that for anything security-related (like the author's project) testing against adversarial input would be be a prominent part.
- onlyrealcuzzo 4mo ago
  > I though that for anything security-related (like the author's project) testing against adversarial input would be be a prominent part. They might have a different definition of adversarial than you. > My tests for quite pedestrian APIs often contain adversarial input of obvious shapes. This doesn't seem like what I would call adversarial. This seems like standard negative testing or boundary value analysis - which I would be shocked if they didn't do.
boricj 4mo ago
I'm working on a C++ library at work that binds wire data and application data through token and model layers, which includes among other things a fair amount of tokenizers/composers for various formats (JSON, CBOR, BSON, CSV...). This looks neat, but if encoding/decoding performance is important, payload size isn't and the integer is bounded, I would just put a fixed-size integer into the payload as-is. LEB128 (and JSON for that matter) can encode integer values of arbitrary length. This doesn't, which may or may not be important but it's different. I'll admit that I do not do any cryptographic work with my library and therefore canonical representations aren't a huge concern in my use-cases. I merely provide various configurable limits (max value length, max depth, max items per collection) in an effort to prevent infinitely long documents from hogging my tokenizers indefinitely.
HansHamster 4mo ago
It feels a bit unfair to say that it is faster by being able to tell the total length from the first byte and capping it at 64 bit, while some of the other formats can store arbitrarily large integers. I guess you could use another variable length encoding for the prefix at the cost of some performance and using even more space...
- petermcneeley 4mo ago
  esp when the number is capped at only 64 bits which is quite small for some bigInt style numbers.
omoikane 4mo ago
UTF-8 has the same issue ("overlong encoding") where multiple representations are possible the same code point. Someone proposed a similar tweak to remove the overlapping ranges by adjusting the base offset for byte sequences that are longer than 1. That was discussed here: https://news.ycombinator.com/item?id=44456073 https://news.ycombinator.com/item?id=44456073 - Corrected UTF-8 (2025-07-03, 54 comments) This "corrected UTF-8" has other problems, but I thought it's interesting how the shifted-offset idea carries over.
kstenerud 4mo ago
The problem is that this breaks down once you try to use SIMD instructions. I'd developed a similar kind of approach to encoding integers (and ieee774 floats) a couple of years ago (first byte encodes length and first bit of data: https://github.com/kstenerud/bonjson/blob/05b91f6fe7d6b0718686830abfb5028157c3fd28/bonjson.md#length-field https://github.com/kstenerud/bonjson/blob/05b91f6fe7d6b07186... ). It was very clever and used compiler intrinsics to get the length in 1 instruction, so 2 instructions got you the final value, with no branches. But testing proved that when you move to SIMD instructions, ULEB128 (https://github.com/kstenerud/bonjson/blob/main/bonjson.md#typed-array https://github.com/kstenerud/bonjson/blob/main/bonjson.md#ty...) or sentinel values (https://github.com/kstenerud/bonjson/blob/main/bonjson.md#long-string https://github.com/kstenerud/bonjson/blob/main/bonjson.md#lo...) win every time because of the parallelization opportunities. The true irony is that even SIMD text parsing would outperform this! SIMD is that powerful.
- nine_k 4mo ago
  I think these are different use cases. If you talk about SIMD, you talk about the CPU and efficient processing of large numbers of integers. I think that when a solution like this crops up, it's about storage or transmission, and dense packing at the cost of non-uniformity. It's more like time-series databases pack numbers by delta encoding.
  - kstenerud 4mo ago
    The thing is, most real-world numbers will fit within 1-3 bytes (even at 7 bits per byte), so ultradense packing doesn't actually buy much outside of benchmarks. I spent WAYYYYYYYY too much time exploring this...
    - deleted 4mo ago
      [deleted]
    - nwmcsween 4mo ago
      This is like string functions, there are some variants with just crazy SIMD when the mean string length is ~14-20 bytes
billpg 4mo ago
I forget where I encountered it, but I've seen similar encodings that eliminated the possibility of many possible encodings for the same number by making the length part of the value. Values 0-127 are a single byte, but if that first byte has the continuation bit set, not only does that indicate the next byte has 7 more bits to contribute, it also moves the base up to the next window. 10000000 00000000 is the only way to represent 128. 10000000 10000000 00000000 is the only way to represent 16512. Does this encoding have a name?
- pkulak 4mo ago
  UTF-8?
  - teo_zero 4mo ago
    UTF-8 notoriously doesn't prevent ambiguous encoding by construction, but only prohibiting it in the specs. It's known as overlong encoding. It's up to the encoder/decoder to prevent, correct, or reject it. This burden on the software is exactly what TFA tries to eliminate with the bijou64 format (unfortunately replacing it with another burden: overflow check).
- pta2002 4mo ago
  I believe that's how the varint encoding used by protobut works: https://protobuf.dev/programming-guides/encoding/#varints https://protobuf.dev/programming-guides/encoding/#varints
  - chrismorgan 4mo ago
    > Drop continuation bits. Clearly not.
    - pta2002 4mo ago
      Indeed, I was misinterpreting the OP's suggestion. Can't edit the comment anymore, unfortunately.
- 4mo ago
amluto 4mo ago
Just a quick reminder: > This causes problems for signed data if you ever want to do things like compression since you need to know the exact bytes that were signed. If you are verifying a signature by taking some logical data structure, turning it into a byte string, and calling the verification primitive on those bytes, you likely have a design error. You should instead collect bytes, verify the signature, and then parse the bytes after verifying the signature. And remember to include enough context in those bytes so a different message signed for a different purpose by the same key doesn’t confuse you.
alex-reyss 4mo ago
[dead]
michaelmure 4mo ago
One nice upside of having a single way to encode a value is fuzzing: when you work on an encoder/decoder, you can use a fuzzer and do round-trip comparison until you find crashes or inputs/outputs that don't match (and therefore issues in the code). But with LEB128 for example, the fuzzer quickly learn about those alternatives encoding and there is not much you can do from there.
aDyslecticCrow 4mo ago
Clever, but one thought crossed my mind; An adveserial package can claim to have a 255 tagged integer but not actually have any followup, tricking the payload parser into an incorrect offset and reading straight off into followup memory. It's a classic thing to check for when dealing with variable length strings or binary, but it may not cross the mind when it's hiding in the Bijou64_decode(*buff, *cr) function.
- gregschlom 4mo ago
  You have the same issue with LEB128 though, right?
  - pixelesque 4mo ago
    Very likely, but isn't this post claiming that bijou64 is safer than LEB128 for the situation of adversarial varints?
  - aDyslecticCrow 4mo ago
    LEB128 can only trick you by at most one byte, (depending on the followup data). Bijou64 can consistently trick you by 8 bytes. In a contrived example of a pbuf {length:int, payload:byte[1]} LEB128 can trick you into reading the payload as part of the length, but then hopefully trigger a code check against invalid buffer read. (or one byte outside the struct if the payload is also malicious) Binou64 can trick you to read 7 bytes into other memory, before any buffer size validation is done. It's then not uncommon to log with a helpful; "buffer with length: 26624894573377(7 bytes of stolen data) is invalid", or just crash. It's to the point that Bijou64_decode should perhaps take "end_adress" or "max_read" to catch this kind of attack. (If you dont validate a malicious pbuf, you're in for a bad time regardless of integer format, but these int formats add their own way to trigger a buffer overrun despite a proper check.)
yread 4mo ago
Wouldn't something like this also work: https://en.wikipedia.org/wiki/Elias_omega_coding https://en.wikipedia.org/wiki/Elias_omega_coding I've used to great effect for compression
harrisi 4mo ago
I'm surprised there's no mention in the post or here about SQLite's varint encoding. Not that it would necessarily satisfy the constraints, but it's one of the most used varint implementations.
- dgllghr 4mo ago
  It's not terribly fast. It's faster than LEB128 but not as fast as vu128 (at least according to https://github.com/Jiboo/varint_benchmark https://github.com/Jiboo/varint_benchmark)
  - harrisi 4mo ago
    The post says the purpose of exploring this space (which is a fun one) wasn't speed, but representation. The speed gain was an added value. I'm not saying SQLite's varint implementation is ideal for every application. It's just an implementation that is one of the most used implementations, if not the most (I'd bet it is by a large margin though). It just seemed like a missed opportunity to compare it with the implementation they landed on. EDIT: Just wanted to add, thanks for sharing that link. Interesting!
i2talics 4mo ago
Non-canonical encodings are actually quite useful for some applications that need variable length integers. DWARF and WASM both use LEB128. The problem is linking: a compiler needs to emit code into independent translation units, which contain "missing" references to symbols in other translation units, without yet knowing where all the code will end up in the final executable. Since we don't know where the location of other code is yet, we don't know how big the number representing that location is yet, which means that we don't know how wide the variable length encoding of that number will be. If the width changes after linking, then we have to push around the surrounding code to make space for the wider integer. Unfortunately, this changes the location of all the surrounding code, so we have to recompute all the references! The solution is to always emit un-linked var ints in the widest possible encoding (5 bytes for LEB128) that way when the references are patched during linking, no code is moved around. All integers can be converted to a non-canonical 5 byte form that is "wasteful" but its a worthwhile tradeoff because it solves this issue. Other integers that don't need to be linked can be packed in a smaller var int form to save space.
- __s 4mo ago
  I've often done same thing with encoding msgpack maps while streaming in key/value pairs
  - i2talics 4mo ago
    Neat! It's a useful technique whenever you don't know or want to defer knowing the size of an integer until a later time, but need to allocate space for it up front. I'm wary of introducing these forced-canonical encodings by someone hyper focused on "efficiency" and "security" without reconsidering additional use cases.
conaclos 4mo ago
This is pretty close to SQLite's varints [0] [0]: https://www.sqlite.org/src4/doc/1433690d7b/www/varint.wiki https://www.sqlite.org/src4/doc/1433690d7b/www/varint.wiki
- adzm 4mo ago
  I believe SQLite3 uses a somewhat different implementation: > A variable-length integer or "varint" is a static Huffman encoding of 64-bit twos-complement integers that uses less space for small positive values. A varint is between 1 and 9 bytes in length. The varint consists of either zero or more bytes which have the high-order bit set followed by a single byte with the high-order bit clear, or nine bytes, whichever is shorter. The lower seven bits of each of the first eight bytes and all 8 bits of the ninth byte are used to reconstruct the 64-bit twos-complement integer. Varints are big-endian: bits taken from the earlier byte of the varint are more significant than bits taken from the later bytes. from https://www.sqlite.org/fileformat2.html#varint https://www.sqlite.org/fileformat2.html#varint The one you linked for SQLite4 (abandoned project) is probably a better approach. I recall that the author has said that SQLite3's varint implementation is regretful.
arkenflame 4mo ago
I researched many different varint encodings for a GraphQL-specific binary format (resulting in Argo: https://github.com/msolomon/argo https://github.com/msolomon/argo ). I ended up choosing protobuf-style zig-zag varints, but I also found these interesting: vu128: https://john-millikin.com/vu128-efficient-variable-length-integers https://john-millikin.com/vu128-efficient-variable-length-in... metric/imperial varint: https://dcreager.net/2021/03/a-better-varint/ https://dcreager.net/2021/03/a-better-varint/ vectorizing VByte: https://arxiv.org/abs/1503.07387 https://arxiv.org/abs/1503.07387
wahern 4mo ago
This reminded me of ISO 7816-4 BER-TLV encodings, which uses the format defined in ISO/IEC 8825-1 (ASN.1 related spec). Length integer values of 0-127 are encoded in 1 byte. If the high bit is set, then the first 7 bits tell you the number of subsequent octets. So there's no offsetting involved, making it slightly less compact, but also dead simple. EDIT: BUT, BER-TLV does permit overlong encodings. And I once found and reported a Yubikey 4 bug related to this. My source code comment for the workaround: -- The Yubikey 4 has an off-by-one bug which -- declares tag length of 255 (for the 0x53 outer -- tag of a certficate DO) when there are only 254 -- bytes remaining in the reply. The reply is -- chained across two packets, but the off-by-one is -- probably related to the over-long encoded length -- (0x82 0x00 0xff instead of 0x81 0xff). -- -- [snip packet captures] -- -- Yubico's ykpiv_fetch_object function in ykpiv.c -- (confirmed 1.4.3-1.5.0) contains a read (memmove) -- overflow when the declared inner BER-TLV length -- (of the 0x53 tag) is longer than what was -- received over the wire. That makes Yubico's -- library oblivious to the issue. Relatedly, the -- set_length function has an off-by-one bug (length -- < 0xff instead of length <= 0xff) which produces -- an over-long encoded length. That doesn't by -- itself explain why the Yubikey 4 transmits a -- truncated logical reply unless the same code is -- being used.
MarkusQ 4mo ago
> This causes problems for signed data Given that the context up to this point had been representation of integers, I initially trip on this. :)
apitman 4mo ago
This reminds me of the varint encoding used by QUIC, but I've never implemented it. Anyone know the differences?
- raphlinus 4mo ago
  Similar, in that it encodes length in the first byte. The differences are: * It does not require canonicality, it allows multiple encodings of the same value. To make things even more fun, the QUIC spec requires shortest encoding in some uses but not others. * It uses 2 bits rather than cutting out a range. * It only encodes values up to 62 bits long. So, some similarities but also some differences. [1]: https://www.rfc-editor.org/rfc/rfc9000.html#name-variable-length-integer-enc https://www.rfc-editor.org/rfc/rfc9000.html#name-variable-le...
  - apitman 4mo ago
    Perfect, thanks!
juancn 4mo ago
I like the denormalization of VLE ints (with or without zig-zag encoding of negatives), it helps support out of band information, such as nulls and other signals in serialization protocols with minimal overhead. For example you can use a denormalized zero to signal null. You can still define a canonical encoding where denormalizations have specific meaning or signal an error.
dekdrop 4mo ago
How do I get to this page from the home page?
dzaima 4mo ago
Kinda surprised that there's no discussion on that this basically just does not solve the non-canonicality problem. Forgetting to do the range check on the first_byte==255 case and just letting it do 64-bit wraparound is exactly as much of a plausible bug as missing range checks on LEB128. Any test suite with the goal of covering canonicality will trivially cover both properly; and a programmer that implements things by reading 7 words into the spec, saying "oh yeah I got this" and goes to implement what seems simple, will write a broken version of both. Perhaps the biggest benefit is just not being associated with a format that tolerates non-canonicality in other places (though, if bijou64 gains traction, it'll only be a matter of time for wraparound-check-less versions to start appearing in places where the wraparound is fine); and I guess also it being less annoying to implement the canonicality check, though hopefully people writing security-sensitive software aren't ones to skip out on correctness checks due to annoyingness. In a sense, bijou64 could perhaps even be more problematic - it invites not doing any range checks for the smaller inputs because they obviously don't need it, and so you can just forget to special-case the max length case; whereas LEB128 makes you already care about it at the first point it is actually LEB128. (of course, the format does still have other benefits; enforced canonicality is just...not one of them)
- restalis 4mo ago
  Your range checking requirement is just one of many things that may or may not be necessary to someone using this. Taking them all into account (besides the fact that may be unfeasible, if there happen to be some conflicting requirements) would render the solution to be unnecessarily complex. It's better to focus on the minimal set of viable requirements and thus have a base design as simple as possible. For additional requirements, just go and complicate your design (and be the only one having to pay the costs that come out of that complication), hopefully only when and only for as long it makes sense to do so. For the need you mention, some kind of container wrapper may do, with the amount of number's words specified in it. A good thing is that you'd be able to limit the use of such container-wrapped numbers only to some situations (like the exchange of data to and from unsanitized areas).
alexpandey 4mo ago
[flagged]
Aardwolf 4mo ago
> The payload is a single contiguous big-endian integer Why not little endian like modern CPUs?
TZubiri 4mo ago
>The check is forgotten, optimised away, or never ported. The protocol’s security property silently degrades. This is the bug class bijou64 is designed to make impossible. Not by adding more checks, but by removing the one that mattered — and making the format such that, with no canonicality check at all, the only encoding that exists for any given value is the canonical one Here's two passing tests for software craftmanship: 1) it looks decades into the past 2) it looks decades into the future
jdougan 4mo ago
Reminds me of the Xanadu Humber encoding.
kakuremi 4mo ago
[dead]

261 points by justinweiss 4mo ago

cantalopes 4mo ago

I love the random hyperlink underlines on that page

spiralganglion 4mo ago
Credit to Roman Komarov who came up with the approach [1], and Todd Matthews [2] who made the art assets. 1: https://kizu.dev/svg-linked-parameters-workaround/ https://kizu.dev/svg-linked-parameters-workaround/ 2: https://www.seaofclouds.com https://www.seaofclouds.com

RedShift1 4mo ago

This seems quite convoluted just to avoid the "0 can be represented in more than one way" problem.

nine_k 4mo ago
It allows finding out the length (and allocating memory) after reading the first byte.
ahoka 4mo ago
I think it's neat.
ape4 4mo ago
Comparing a number to zero is something that's done a lot
- Chaosvex 4mo ago
  True but also not particularly relevant?
bjoli 4mo ago
Having all numbers be valid in only one way is a great idea. So much that I believe webassembly enforced canonical leb128, at the cost of decoding speed. And say you have it as part of some other data. If you want to be able to hash it by the raw memory bytes, many different ways to represent a number becomes a problem.
matja 4mo ago
> canonicality matters — for signatures, content-addressing, or any kind of “two implementations must agree on the bytes” property If you don't do this properly, you end up with things like: - SAML XSW attack due to XML signature wrapping - ASN.1 BER/DER signature forgery - Bitcoin transaction malleability attacks

stebalien 4mo ago

I've used LEB128 (with canonicalisation) extensively and... this looks so much nicer for most use-cases (length prefixed, supports the full uint64 range without that extra 10th byte). The downside is the encoding size. LEB128 quickly grows to 2 bytes, but stays at 2 bytes all the way to 2^14. This is important if you're using these numbers as tags/identifiers as we were in the multicodec [1] project, or for network message lengths. bijou64 only gives you 500 <= 2 byte numbers. [1]: https://github.com/multiformats/multicodec https://github.com/multiformats/multicodec

b_fiive 4mo ago
sup steb, this is expede's work!
- stebalien 4mo ago
  Sup b5! I always look forward to new work by expede (and n0).
Someone 4mo ago
> I’ve used LEB128 (with canonicalisation) extensively and... this looks so much nicer for most use-cases (length prefixed, supports the full uint64 range without that extra 10th byte) If you only want to encode uint64 numbers LEB128 could easily be tweaked to fit in 9 bytes in several ways: - using the offset trick described in this article would remove non-unique encodings (0x80 0x00 would encode 128) - never allowing encodings longer than 9 bytes would mean the MSB of any ninth byte would always be zero, so you could reuse that, and store 8 bits in any ninth byte, for a total of 7 bits in each of the first eight bytes plus 8 in the ninth = 64 Both tweaks would lose LEB128’s property that you can find where each number starts from any byte in the stream, but the encoding discussed here doesn’t have that property either.

willtemperley 4mo ago

Maybe someone can explain why an encoder would ever create the padding bytes allowed in LEB128. I contributed the parser for LEB128 in apple/swift-binary-parsing and I’m still none the wiser. I’m genuinely mystified.

Chaosvex 4mo ago
You wouldn't. It's a strange argument that can be countered with, "maybe don't do that?"
- willtemperley 4mo ago
  So why does the spec allow it? Like a good engineer I read the spec and tested against the over-wide example encodings given.
  - Chaosvex 4mo ago
    Because it's not a real standard and there is no blessed RFC for it. The DWARF spec is as close as you'll get and it says, "The integer zero is a special case, consisting of a single zero byte." So in a way, it doesn't. Either way, a properly written decoder (and it's like ten lines) should really not have any problems with it. I was agreeing with you. Edit: to clarify, I was talking about the author's argument being strange, not yours.
    - willtemperley 4mo ago
      The WASM spec is more explicit about over-long LEB128 encoding. Edit: a properly written decoder is a lot more than 10 lines if you properly deal with integer overflow and both signed and unsigned ints.
layer8 4mo ago
The issue is that non-unique encodings are an attack vector, because parsers may in practice behave differently for noncanonical (or nominally invalid) encodings.

nine_k 4mo ago

In short: instead of a truly indefinite-length solution with a signal bit on the current byte saying whether to check the next byte, this uses a counter. Values 0x0 to 0xF7 are one-byte integers, 0xF8 to 0xFF use the upper 5 bits as a counter for the number of subsequent bytes. This limits the maximum magnitude to slightly less than 2 ^ 264 (almost all 33-byte values), which seems to be okay for practical computations. The proposed standard limits the supported size to u64 though. The upsides: the size of the integer is apparent upon reading the first byte, and every number has exactly one canonical representation. I wish C strings had been standardized around something similar, instead on null termination. > ...adversarial input, which is rarely in the test suite. This made my scratch my head. My tests for quite pedestrian APIs often contain adversarial input of obvious shapes. I though that for anything security-related (like the author's project) testing against adversarial input would be be a prominent part.

onlyrealcuzzo 4mo ago
> I though that for anything security-related (like the author's project) testing against adversarial input would be be a prominent part. They might have a different definition of adversarial than you. > My tests for quite pedestrian APIs often contain adversarial input of obvious shapes. This doesn't seem like what I would call adversarial. This seems like standard negative testing or boundary value analysis - which I would be shocked if they didn't do.

boricj 4mo ago

I'm working on a C++ library at work that binds wire data and application data through token and model layers, which includes among other things a fair amount of tokenizers/composers for various formats (JSON, CBOR, BSON, CSV...). This looks neat, but if encoding/decoding performance is important, payload size isn't and the integer is bounded, I would just put a fixed-size integer into the payload as-is. LEB128 (and JSON for that matter) can encode integer values of arbitrary length. This doesn't, which may or may not be important but it's different. I'll admit that I do not do any cryptographic work with my library and therefore canonical representations aren't a huge concern in my use-cases. I merely provide various configurable limits (max value length, max depth, max items per collection) in an effort to prevent infinitely long documents from hogging my tokenizers indefinitely.

HansHamster 4mo ago

It feels a bit unfair to say that it is faster by being able to tell the total length from the first byte and capping it at 64 bit, while some of the other formats can store arbitrarily large integers. I guess you could use another variable length encoding for the prefix at the cost of some performance and using even more space...

petermcneeley 4mo ago
esp when the number is capped at only 64 bits which is quite small for some bigInt style numbers.

omoikane 4mo ago

UTF-8 has the same issue ("overlong encoding") where multiple representations are possible the same code point. Someone proposed a similar tweak to remove the overlapping ranges by adjusting the base offset for byte sequences that are longer than 1. That was discussed here: https://news.ycombinator.com/item?id=44456073 https://news.ycombinator.com/item?id=44456073 - Corrected UTF-8 (2025-07-03, 54 comments) This "corrected UTF-8" has other problems, but I thought it's interesting how the shifted-offset idea carries over.

kstenerud 4mo ago

The problem is that this breaks down once you try to use SIMD instructions. I'd developed a similar kind of approach to encoding integers (and ieee774 floats) a couple of years ago (first byte encodes length and first bit of data: https://github.com/kstenerud/bonjson/blob/05b91f6fe7d6b0718686830abfb5028157c3fd28/bonjson.md#length-field https://github.com/kstenerud/bonjson/blob/05b91f6fe7d6b07186... ). It was very clever and used compiler intrinsics to get the length in 1 instruction, so 2 instructions got you the final value, with no branches. But testing proved that when you move to SIMD instructions, ULEB128 (https://github.com/kstenerud/bonjson/blob/main/bonjson.md#typed-array https://github.com/kstenerud/bonjson/blob/main/bonjson.md#ty...) or sentinel values (https://github.com/kstenerud/bonjson/blob/main/bonjson.md#long-string https://github.com/kstenerud/bonjson/blob/main/bonjson.md#lo...) win every time because of the parallelization opportunities. The true irony is that even SIMD text parsing would outperform this! SIMD is that powerful.

nine_k 4mo ago
I think these are different use cases. If you talk about SIMD, you talk about the CPU and efficient processing of large numbers of integers. I think that when a solution like this crops up, it's about storage or transmission, and dense packing at the cost of non-uniformity. It's more like time-series databases pack numbers by delta encoding.
- kstenerud 4mo ago
  The thing is, most real-world numbers will fit within 1-3 bytes (even at 7 bits per byte), so ultradense packing doesn't actually buy much outside of benchmarks. I spent WAYYYYYYYY too much time exploring this...
  - deleted 4mo ago
    [deleted]
  - nwmcsween 4mo ago
    This is like string functions, there are some variants with just crazy SIMD when the mean string length is ~14-20 bytes

billpg 4mo ago

I forget where I encountered it, but I've seen similar encodings that eliminated the possibility of many possible encodings for the same number by making the length part of the value. Values 0-127 are a single byte, but if that first byte has the continuation bit set, not only does that indicate the next byte has 7 more bits to contribute, it also moves the base up to the next window. 10000000 00000000 is the only way to represent 128. 10000000 10000000 00000000 is the only way to represent 16512. Does this encoding have a name?

pkulak 4mo ago
UTF-8?
- teo_zero 4mo ago
  UTF-8 notoriously doesn't prevent ambiguous encoding by construction, but only prohibiting it in the specs. It's known as overlong encoding. It's up to the encoder/decoder to prevent, correct, or reject it. This burden on the software is exactly what TFA tries to eliminate with the bijou64 format (unfortunately replacing it with another burden: overflow check).
pta2002 4mo ago
I believe that's how the varint encoding used by protobut works: https://protobuf.dev/programming-guides/encoding/#varints https://protobuf.dev/programming-guides/encoding/#varints
- chrismorgan 4mo ago
  > Drop continuation bits. Clearly not.
  - pta2002 4mo ago
    Indeed, I was misinterpreting the OP's suggestion. Can't edit the comment anymore, unfortunately.
4mo ago

amluto 4mo ago

Just a quick reminder: > This causes problems for signed data if you ever want to do things like compression since you need to know the exact bytes that were signed. If you are verifying a signature by taking some logical data structure, turning it into a byte string, and calling the verification primitive on those bytes, you likely have a design error. You should instead collect bytes, verify the signature, and then parse the bytes after verifying the signature. And remember to include enough context in those bytes so a different message signed for a different purpose by the same key doesn’t confuse you.

alex-reyss 4mo ago

[dead]

michaelmure 4mo ago

One nice upside of having a single way to encode a value is fuzzing: when you work on an encoder/decoder, you can use a fuzzer and do round-trip comparison until you find crashes or inputs/outputs that don't match (and therefore issues in the code). But with LEB128 for example, the fuzzer quickly learn about those alternatives encoding and there is not much you can do from there.

aDyslecticCrow 4mo ago

Clever, but one thought crossed my mind; An adveserial package can claim to have a 255 tagged integer but not actually have any followup, tricking the payload parser into an incorrect offset and reading straight off into followup memory. It's a classic thing to check for when dealing with variable length strings or binary, but it may not cross the mind when it's hiding in the Bijou64_decode(*buff, *cr) function.

gregschlom 4mo ago
You have the same issue with LEB128 though, right?
- pixelesque 4mo ago
  Very likely, but isn't this post claiming that bijou64 is safer than LEB128 for the situation of adversarial varints?
- aDyslecticCrow 4mo ago
  LEB128 can only trick you by at most one byte, (depending on the followup data). Bijou64 can consistently trick you by 8 bytes. In a contrived example of a pbuf {length:int, payload:byte[1]} LEB128 can trick you into reading the payload as part of the length, but then hopefully trigger a code check against invalid buffer read. (or one byte outside the struct if the payload is also malicious) Binou64 can trick you to read 7 bytes into other memory, before any buffer size validation is done. It's then not uncommon to log with a helpful; "buffer with length: 26624894573377(7 bytes of stolen data) is invalid", or just crash. It's to the point that Bijou64_decode should perhaps take "end_adress" or "max_read" to catch this kind of attack. (If you dont validate a malicious pbuf, you're in for a bad time regardless of integer format, but these int formats add their own way to trigger a buffer overrun despite a proper check.)

yread 4mo ago

Wouldn't something like this also work: https://en.wikipedia.org/wiki/Elias_omega_coding https://en.wikipedia.org/wiki/Elias_omega_coding I've used to great effect for compression

harrisi 4mo ago

I'm surprised there's no mention in the post or here about SQLite's varint encoding. Not that it would necessarily satisfy the constraints, but it's one of the most used varint implementations.

dgllghr 4mo ago
It's not terribly fast. It's faster than LEB128 but not as fast as vu128 (at least according to https://github.com/Jiboo/varint_benchmark https://github.com/Jiboo/varint_benchmark)
- harrisi 4mo ago
  The post says the purpose of exploring this space (which is a fun one) wasn't speed, but representation. The speed gain was an added value. I'm not saying SQLite's varint implementation is ideal for every application. It's just an implementation that is one of the most used implementations, if not the most (I'd bet it is by a large margin though). It just seemed like a missed opportunity to compare it with the implementation they landed on. EDIT: Just wanted to add, thanks for sharing that link. Interesting!

i2talics 4mo ago

Non-canonical encodings are actually quite useful for some applications that need variable length integers. DWARF and WASM both use LEB128. The problem is linking: a compiler needs to emit code into independent translation units, which contain "missing" references to symbols in other translation units, without yet knowing where all the code will end up in the final executable. Since we don't know where the location of other code is yet, we don't know how big the number representing that location is yet, which means that we don't know how wide the variable length encoding of that number will be. If the width changes after linking, then we have to push around the surrounding code to make space for the wider integer. Unfortunately, this changes the location of all the surrounding code, so we have to recompute all the references! The solution is to always emit un-linked var ints in the widest possible encoding (5 bytes for LEB128) that way when the references are patched during linking, no code is moved around. All integers can be converted to a non-canonical 5 byte form that is "wasteful" but its a worthwhile tradeoff because it solves this issue. Other integers that don't need to be linked can be packed in a smaller var int form to save space.

__s 4mo ago
I've often done same thing with encoding msgpack maps while streaming in key/value pairs
- i2talics 4mo ago
  Neat! It's a useful technique whenever you don't know or want to defer knowing the size of an integer until a later time, but need to allocate space for it up front. I'm wary of introducing these forced-canonical encodings by someone hyper focused on "efficiency" and "security" without reconsidering additional use cases.

conaclos 4mo ago

This is pretty close to SQLite's varints [0] [0]: https://www.sqlite.org/src4/doc/1433690d7b/www/varint.wiki https://www.sqlite.org/src4/doc/1433690d7b/www/varint.wiki

adzm 4mo ago
I believe SQLite3 uses a somewhat different implementation: > A variable-length integer or "varint" is a static Huffman encoding of 64-bit twos-complement integers that uses less space for small positive values. A varint is between 1 and 9 bytes in length. The varint consists of either zero or more bytes which have the high-order bit set followed by a single byte with the high-order bit clear, or nine bytes, whichever is shorter. The lower seven bits of each of the first eight bytes and all 8 bits of the ninth byte are used to reconstruct the 64-bit twos-complement integer. Varints are big-endian: bits taken from the earlier byte of the varint are more significant than bits taken from the later bytes. from https://www.sqlite.org/fileformat2.html#varint https://www.sqlite.org/fileformat2.html#varint The one you linked for SQLite4 (abandoned project) is probably a better approach. I recall that the author has said that SQLite3's varint implementation is regretful.

arkenflame 4mo ago

I researched many different varint encodings for a GraphQL-specific binary format (resulting in Argo: https://github.com/msolomon/argo https://github.com/msolomon/argo ). I ended up choosing protobuf-style zig-zag varints, but I also found these interesting: vu128: https://john-millikin.com/vu128-efficient-variable-length-integers https://john-millikin.com/vu128-efficient-variable-length-in... metric/imperial varint: https://dcreager.net/2021/03/a-better-varint/ https://dcreager.net/2021/03/a-better-varint/ vectorizing VByte: https://arxiv.org/abs/1503.07387 https://arxiv.org/abs/1503.07387

wahern 4mo ago

This reminded me of ISO 7816-4 BER-TLV encodings, which uses the format defined in ISO/IEC 8825-1 (ASN.1 related spec). Length integer values of 0-127 are encoded in 1 byte. If the high bit is set, then the first 7 bits tell you the number of subsequent octets. So there's no offsetting involved, making it slightly less compact, but also dead simple. EDIT: BUT, BER-TLV does permit overlong encodings. And I once found and reported a Yubikey 4 bug related to this. My source code comment for the workaround: -- The Yubikey 4 has an off-by-one bug which -- declares tag length of 255 (for the 0x53 outer -- tag of a certficate DO) when there are only 254 -- bytes remaining in the reply. The reply is -- chained across two packets, but the off-by-one is -- probably related to the over-long encoded length -- (0x82 0x00 0xff instead of 0x81 0xff). -- -- [snip packet captures] -- -- Yubico's ykpiv_fetch_object function in ykpiv.c -- (confirmed 1.4.3-1.5.0) contains a read (memmove) -- overflow when the declared inner BER-TLV length -- (of the 0x53 tag) is longer than what was -- received over the wire. That makes Yubico's -- library oblivious to the issue. Relatedly, the -- set_length function has an off-by-one bug (length -- < 0xff instead of length <= 0xff) which produces -- an over-long encoded length. That doesn't by -- itself explain why the Yubikey 4 transmits a -- truncated logical reply unless the same code is -- being used.

MarkusQ 4mo ago

> This causes problems for signed data Given that the context up to this point had been representation of integers, I initially trip on this. :)

apitman 4mo ago

This reminds me of the varint encoding used by QUIC, but I've never implemented it. Anyone know the differences?

raphlinus 4mo ago
Similar, in that it encodes length in the first byte. The differences are: * It does not require canonicality, it allows multiple encodings of the same value. To make things even more fun, the QUIC spec requires shortest encoding in some uses but not others. * It uses 2 bits rather than cutting out a range. * It only encodes values up to 62 bits long. So, some similarities but also some differences. [1]: https://www.rfc-editor.org/rfc/rfc9000.html#name-variable-length-integer-enc https://www.rfc-editor.org/rfc/rfc9000.html#name-variable-le...
- apitman 4mo ago
  Perfect, thanks!

juancn 4mo ago

I like the denormalization of VLE ints (with or without zig-zag encoding of negatives), it helps support out of band information, such as nulls and other signals in serialization protocols with minimal overhead. For example you can use a denormalized zero to signal null. You can still define a canonical encoding where denormalizations have specific meaning or signal an error.

dekdrop 4mo ago

How do I get to this page from the home page?

dzaima 4mo ago

Kinda surprised that there's no discussion on that this basically just does not solve the non-canonicality problem. Forgetting to do the range check on the first_byte==255 case and just letting it do 64-bit wraparound is exactly as much of a plausible bug as missing range checks on LEB128. Any test suite with the goal of covering canonicality will trivially cover both properly; and a programmer that implements things by reading 7 words into the spec, saying "oh yeah I got this" and goes to implement what seems simple, will write a broken version of both. Perhaps the biggest benefit is just not being associated with a format that tolerates non-canonicality in other places (though, if bijou64 gains traction, it'll only be a matter of time for wraparound-check-less versions to start appearing in places where the wraparound is fine); and I guess also it being less annoying to implement the canonicality check, though hopefully people writing security-sensitive software aren't ones to skip out on correctness checks due to annoyingness. In a sense, bijou64 could perhaps even be more problematic - it invites not doing any range checks for the smaller inputs because they obviously don't need it, and so you can just forget to special-case the max length case; whereas LEB128 makes you already care about it at the first point it is actually LEB128. (of course, the format does still have other benefits; enforced canonicality is just...not one of them)

restalis 4mo ago
Your range checking requirement is just one of many things that may or may not be necessary to someone using this. Taking them all into account (besides the fact that may be unfeasible, if there happen to be some conflicting requirements) would render the solution to be unnecessarily complex. It's better to focus on the minimal set of viable requirements and thus have a base design as simple as possible. For additional requirements, just go and complicate your design (and be the only one having to pay the costs that come out of that complication), hopefully only when and only for as long it makes sense to do so. For the need you mention, some kind of container wrapper may do, with the amount of number's words specified in it. A good thing is that you'd be able to limit the use of such container-wrapped numbers only to some situations (like the exchange of data to and from unsanitized areas).

alexpandey 4mo ago

[flagged]

Aardwolf 4mo ago

> The payload is a single contiguous big-endian integer Why not little endian like modern CPUs?

TZubiri 4mo ago

>The check is forgotten, optimised away, or never ported. The protocol’s security property silently degrades. This is the bug class bijou64 is designed to make impossible. Not by adding more checks, but by removing the one that mattered — and making the format such that, with no canonicality check at all, the only encoding that exists for any given value is the canonical one Here's two passing tests for software craftmanship: 1) it looks decades into the past 2) it looks decades into the future

jdougan 4mo ago

Reminds me of the Xanadu Humber encoding.

kakuremi 4mo ago

[dead]