Bijou64: 解決變長整數編碼中的正規化問題
在二進位協定中，變長整數 (varint) 編碼對於維持緊湊性至關重要。大多數協定需要表示通常較小但偶爾非常大的數字；varints 允許它們僅使用必要的位元組數量。然而，許多流行的設計中存在一個微妙但危險的缺陷：缺乏結構上的正規化 (canonicality)。
這正是 bijou64 的催化劑，這是一種為 Subduction CRDT 同步協定開發的編碼方式。雖然其主要目標是透過確保每個數字都有且僅有一個唯一的表示方式來修復簽章驗證錯誤，但其結果卻是一種經常優於業界標準 LEB128 的格式。
非正規化編碼的危險性
要理解為什麼存在 bijou64，必須首先了解 LEB128 的缺點。LEB128 將數字編碼為 7 位元組段序列，並使用每個位元組的高位元作為續接標記 (continuation flag)。雖然這很實用，但這種設計允許使用多種方式來表示同一個值。例如，數字 0 可以編碼為 0x00，但也可以表示為 0x80 0x00 或 0x80 0x80 0x00。
對於大多數應用程式而言，這不是問題。然而，對於有簽章的數據或內容定址系統 (content-addressed systems)，這是一個關鍵的漏洞。如果一個協定對位元組字串進行簽章，攻擊者可以在不改變其值的情況下更改整數的編碼，從而改變簽章，並可能繞過安全檢查或導致去重 (deduplication) 失敗。
從歷史上看，這曾導致廣泛使用系統中的重大漏洞，包括 ASN.1 (X.509 憑證)、JWTs 和 Bitcoin 交易。典型的失敗模式是可預測的：
- 規範要求正規化形式。
- 實作中加入了運行時檢查以強制執行此要求。
- 該檢查可以被單獨刪除且不會破壞標準測試，因此最終會因為優化而被移除、被遺忘或在移植過程中被省略。
- 安全屬性在不知不覺中降級。
藉由結構實現正規化：bijou64 如何運作
bijou64 透過使格式「藉由結構實現正規化」來消除這類錯誤。它透過兩個主要機制確保任何給定整數都只有一種可能的位元組序列。
1. 首位元組標記 (First-Byte Tagging)
不同於 LEB128 需要掃描每個位元組來尋找續接位元，bijou64 將第一個位元組用於雙重用途。0–247 的值被表示為單個位元組。248–255 的值充當 tag，明確指出後續有多少個位元組。這使得解碼器可以在 $O(1)$ 時間內知道所需的確切切換記憶體配置。
2. 範圍偏移 (Range Offsetting)
為了防止一個數字同時被表示為單個位元組和標記序列（例如，防止 0xF8 0x00 等於 0x00），bijou64 採用了偏移量。每個長度層級 (tier) 的起始值都略高於前一個層級的最大值。
例如，一個 2 位元組序列 (tag + 1 byte) 並不從 0 開始；它是偏移了 248。這確保了 0xF8 0x00 代表 248，而不是 0。隨著長度增加，偏移量會根據查找表以可預測的模式增長。
| 總長度 | 偏移量 |
|---|---|
| 1 | 0x00 |
| 2 | 0x0F8 |
| 3 | 0x01F8 |
| 4 | 0x0101F8 |
效能增益：免費的午餐
令人驚訝的是，這些安全約束反而導致了更快的解碼器。在 ARM (M2 Pro) 和 x86 (Zen 5) 上的基準測試顯示 bijou64 解碼速度比 LEB128 快 2–10 倍。
為什麼它更快？
沒有續接掃描： 解碼器可以立即從第一個位元組得知長度，這對 CPU 分支預測器非常友好。
連續載入的有效載荷 (Contiguous Payloads)： 數據是以大端序 (big-endian) 整數形式儲存，而不是 7 位元組段。現代 CPU 可以使用單個 load 指令與
bswap指令，而 LEB128 需要對每個位元組進行遮罩與位移。可預測的分支： 層級選擇是一個簡單的匹配，這會導致非常一致的效能（如基準測試中近乎垂直的 CDF 曲線所示）。
雖然編碼速度通常較快，但 LEB128 在特定的「小」分佈（值在 248 到 65,535 之間）中仍保有微弱優勢。
關鍵權衡與社群觀點
儘管有其優點，bijou64 並非所有 varint 需求的通用替代方案。技術討論強調了幾個關鍵考量因素：
SIMD 並行化
一位貢獻者指出，長度前綴 (length-prefix) 方法可能會阻礙 SIMD (Single Instruction, Multiple Data) 優化。當可以進行大規模並行化時，例如 ULEB128 或基於哨兵 (sentinel-based) 的編碼方式，其效能可能優於 bijou64，因為它們允許在 SIMD 暫存器中具有更一致的數據模式。
空間效率
LEB128 在某些範圍內可能更緊湊。例如，LEB128 對於值在 $2^{14}$ 以內的數值，可以維持在 2 位元組，而 bijou64 的 2 位元組範圍非常小（結束於 500）。對於那些識別碼或標籤 (tag) 的開銷比每一位元組都關鍵的協定而言，這可能是一個缺點。
「連結」使用案例
在 DWARF 或 WASM 等系統中，非正規化編碼其實是一種特性。編譯器經常為尚未解析的引用 (reference) 發出「浪費」的 5 位元組 LEB128 整數，以避免在二進位檔中平移移位所有後續代碼。這允許連結器 (linker) 在修補 (patch) 值時不需要重新排列整個二進位檔。嚴格的正規化格式會迫使二進位檔在引用尺寸改變時進行大規模重組。
殘餘風險
一些批評者認為 bijou64 並未完全解決正規化問題。對於最大的 9 位元組案例，解碼器仍必須執行手動邊界檢查以確保值不超過 $2^{64}$。如果程式設計師忘記了這個特定的檢查，同樣類型的「被遺忘的檢查」錯誤就會再次出現，儘管僅限於最大的可能值。
結論
bijou64 證明了安全性與效能並非總是相互衝突的。透過將正規化要求從運行時檢查轉移到編碼結構本身，它消除了常見的加密漏洞來源，同時簡化了現代 CPU 的對解碼過程的優效化。雖然它可能不適合所有使用案例——特別是需要 SIMD 優化或連結器風格的填充 (padding) 的案例——但它為安全性與速度至上的新協定提供了一個極具吸引力的替代方案。