Bijou64：比 LEB128 快 10 倍的新型变长整数编码，安全性还更强

2026 年 4 月，知名研究实验室 Ink & Switch 发布了一篇关于变长整数编码（Variable-length Integer Encoding）的技术报告，介绍了一种名为 Bijou64 的新编码方案。这个编码最初是为 CRDT 同步协议设计的，目标是解决 LEB128 等传统编码的「非唯一表示」安全漏洞——结果意外发现，它的解码速度比 LEB128 快了 2-10 倍。对于任何需要处理二进制协议、数据序列化或高性能网络通信的开发者来说，这都是一个值得关注的技术突破。

📌 **记住：**变长整数编码是现代二进制协议的基石。从 Protocol Buffers 到 CRDT，从 WebSocket 帧到数据库 WAL，几乎所有高效数据传输都在用 varint。选错编码方案，不仅影响性能，还可能引入安全漏洞。

🔐 一、LEB128 的安全死穴：一个数字，多种写法

为什么「非唯一表示」是个大问题？

LEB128（Little Endian Base 128）是最常见的变长整数编码，被 DWARF 调试格式、WebAssembly、Ethereum 等广泛使用。它的原理很直观：每个字节的低 7 位存储数据，最高位作为「继续标志」（continuation bit）。

数字 5 的 LEB128 编码: 0x05（1 字节）
数字 300 的 LEB128 编码: 0xAC 0x02（2 字节）

看起来很完美，但这里藏着一个致命问题：同一个数字可以有无限多种编码方式。

数字 0 可以编码为：
  ✅ 0x00                    （标准，1 字节）
  ❌ 0x80 0x00               （前导零，2 字节）
  ❌ 0x80 0x80 0x00          （前导零，3 字节）
  ❌ 0x80 0x80 0x80 0x00     （前导零，4 字节）
  ...无限延伸

这不仅仅是「浪费空间」的问题。在任何涉及签名验证的场景中，这种非唯一表示会直接导致安全漏洞。

真实世界的安全事故

这种攻击模式在密码学历史上反复出现：

⚠️ **警告：**如果你的协议涉及签名验证、数据去重或内容寻址存储，使用 LEB128 等非唯一编码而不同步实现规范性检查（canonicality check），等于在安全防线上留了一个「可单独删除的 if 语句」——而历史上，这类检查总会在某个版本中被遗漏或优化掉。

LEB128 的规范性检查为什么不可靠？

问题的核心在于：规范性检查是一个独立于解析逻辑的额外步骤。

// ❌ LEB128 解码器 —— 规范性检查是「可选的额外 if」
function decodeLEB128(bytes) {
  let result = 0;
  let shift = 0;
  let byte;
  let bytesRead = 0;
  
  do {
    byte = bytes[bytesRead++];
    result |= (byte & 0x7F) << shift;
    shift += 7;
  } while (byte & 0x80);
  
  // ⚠️ 这个检查可以被「安全地」删除而不影响任何正常测试
  // 只有对抗性输入才会触发
  if (bytesRead > 1 && bytes[0] === 0x80) {
    throw new Error("Non-canonical encoding");
  }
  
  return result;
}

这个 if 语句在以下情况下会被移除：

• 开发者觉得「性能优化」时删掉
• 代码审查时被认为「不必要」
• 测试用例中从未触发过
• 新同事重构时不理解其含义

💡 **提示：**Bijou64 的设计哲学是「不要加更多检查，而是让格式本身只有一种合法编码」——把安全性从运行时检查变成结构性保证。

🚀 二、Bijou64 的设计原理：两个巧妙的技巧

技巧一：首字节双重职责（First Byte Double Duty）

Bijou64 的第一个字节同时承担「数据」和「标签」两种角色：

字节值 0x00 - 0xF7（0-247）：直接表示数值，1 字节搞定
字节值 0xF8 - 0xFF（248-255）：这是一个「标签」，告诉你后面还有几个字节

这个设计带来一个巨大的解码优势：读完第一个字节，你就知道总共需要读多少字节（O(1) 复杂度）。而 LEB128 必须持续读取直到看到没有继续标志的字节（O(n) 复杂度）。

技巧二：偏移量消除重复表示（Offsets）

仅有标签还不够——如果第二个字节又从 0 开始计数，就会出现重复表示。Bijou64 的解决方案是：每个长度级别的数值都从上一级别的最大值 + 1 开始。

1 字节：0 - 247
2 字节：248 - 503（偏移 248 = 0xF8）
3 字节：504 - 66,039（偏移 504 = 0x1F8）
4 字节：66,040 - 16,843,255（偏移 66,040 = 0x0101F8）

偏移量的规律一目了然：

💡 **提示：**这个偏移量表是一个基于首字节的查找表（lookup table），解码时只需要一次数组索引，不需要循环或位扫描。

解码示例：1738 是怎么编码的？

1738 落在 3 字节范围（504 - 66,039）

步骤 1：减去偏移量
  1738 - 504 = 1234

步骤 2：将 1234 拆分为 2 个字节（大端序）
  1234 = 0x04D2 → 字节 [0x04, 0xD2]

步骤 3：首字节 = 标签 0xF9（表示后面有 2 字节）
  最终编码：[0xF9, 0x04, 0xD2]

验证：解码时，首字节 0xF9 → 标签 2 → 读 2 字节 → 0x04D2 = 1234 → 1234 + 504 = 1738 ✅

📊 三、性能基准测试：为什么更快？

解码速度对比

Ink & Switch 在 ARM（Apple M2 Pro）和 x86（AMD Zen 5）上进行了完整的基准测试，结果令人震惊：

⚡ **关键结论：**Bijou64 在全范围 u64 数据上解码速度是 LEB128 的 10 倍，在小数值上也有 2 倍优势。更关键的是，LEB128 还需要额外 20-50% 的开销来做规范性检查——而 Bijou64 完全不需要。

为什么 Bijou64 更快？

核心原因有三个：

1. O(1) 长度确定：读完首字节就知道要读多少字节，不需要逐字节扫描继续标志
2. 无分支解码：标签查表 + 简单的加法和位移，CPU 流水线不会被打断
3. 无规范性检查：省去了 LEB128 必须的「前导零检测」分支

内存占用对比

编码数字 1,000,000（典型业务场景）：
  LEB128:   3 字节 [0x84 0x89 0x3C]
  Bijou64:  3 字节 [0xF9 0x03 0xE3]
  固定 8 字节: 8 字节 [0x00 0x00 0x00 0x00 0x00 0x0F 0x42 0x40]

编码数字 300（常见 ID 范围）：
  LEB128:   2 字节 [0xAC 0x02]
  Bijou64:  2 字节 [0xF8 0x34]
  固定 8 字节: 8 字节

对于典型业务数据（ID、计数器、时间戳偏移），Bijou64 和 LEB128 的空间效率几乎相同。

🔧 四、JavaScript/TypeScript 完整实现

下面是 Bijou64 的完整 TypeScript 实现，支持编码和解码：

// Bijou64 变长整数编码 - TypeScript 实现
// 参考: https://www.inkandswitch.com/tangents/bijou64/

const OFFSETS = [
  0x00n,
  0xF8n,
  0x01F8n,
  0x0101F8n,
  0x010101F8n,
  0x01010101F8n,
  0x0101010101F8n,
  0x010101010101F8n,
  0x01010101010101F8n,
];

const MAX_VALUE = (1n << 64n) - 1n;

/**
 * 将 BigInt 编码为 Bijou64 字节数组
 */
export function encode(value: bigint): Uint8Array {
  if (value < 0n || value > MAX_VALUE) {
    throw new RangeError(`Value out of range: ${value}`);
  }

  // 单字节范围: 0 - 247
  if (value < 248n) {
    return new Uint8Array([Number(value)]);
  }

  // 确定需要的字节长度
  let length = 2;
  while (length <= 9 && value >= OFFSETS[length]) {
    length++;
  }
  length--; // 回退到正确的长度

  // 减去偏移量
  let remaining = value - OFFSETS[length];

  // 分配结果数组
  const result = new Uint8Array(length);
  result[0] = 0xF8 + (length - 1); // 标签字节

  // 从后往前填充数据字节（大端序）
  for (let i = length - 1; i >= 1; i--) {
    result[i] = Number(remaining & 0xFFn);
    remaining >>= 8n;
  }

  return result;
}

/**
 * 从字节数组解码 Bijou64 值
 * @returns [解码值, 消耗的字节数]
 */
export function decode(bytes: Uint8Array, offset = 0): [bigint, number] {
  const first = bytes[offset];

  // 单字节范围: 0 - 247
  if (first < 0xF8) {
    return [BigInt(first), 1];
  }

  // 标签范围: 0xF8 - 0xFF
  const dataBytes = first - 0xF7; // 数据字节数（1-8）
  const totalLength = 1 + dataBytes;

  if (offset + totalLength > bytes.length) {
    throw new Error("Unexpected end of data");
  }

  // 读取数据字节（大端序）
  let value = 0n;
  for (let i = 1; i <= dataBytes; i++) {
    value = (value << 8n) | BigInt(bytes[offset + i]);
  }

  // 加上偏移量
  value += OFFSETS[totalLength - 1];

  // 边界检查（9 字节时可能超出 u64 范围）
  if (value > MAX_VALUE) {
    throw new RangeError(`Value exceeds u64 range: ${value}`);
  }

  return [value, totalLength];
}

// 使用示例
const encoded = encode(1738n);
console.log("编码 1738:", encoded); // Uint8Array [0xF9, 0x04, 0xD2]

const [decoded, consumed] = decode(encoded);
console.log("解码结果:", decoded, "消耗字节:", consumed); // 1738n, 3

批量编码/解码工具函数

// 批量编码一组整数
export function encodeArray(values: bigint[]): Uint8Array {
  const chunks: Uint8Array[] = [];
  let totalLength = 0;

  for (const v of values) {
    const chunk = encode(v);
    chunks.push(chunk);
    totalLength += chunk.length;
  }

  const result = new Uint8Array(totalLength);
  let offset = 0;
  for (const chunk of chunks) {
    result.set(chunk, offset);
    offset += chunk.length;
  }
  return result;
}

// 批量解码
export function decodeArray(data: Uint8Array): bigint[] {
  const values: bigint[] = [];
  let offset = 0;

  while (offset < data.length) {
    const [value, consumed] = decode(data, offset);
    values.push(value);
    offset += consumed;
  }

  return values;
}

// 性能基准测试
function benchmark() {
  const testValues = Array.from({ length: 4096 }, () => 
    BigInt(Math.floor(Math.random() * 1_000_000_000))
  );

  console.time("Bijou64 编码 4096 个值");
  const encoded = encodeArray(testValues);
  console.timeEnd("Bijou64 编码 4096 个值");

  console.time("Bijou64 解码 4096 个值");
  const decoded = decodeArray(encoded);
  console.timeEnd("Bijou64 解码 4096 个值");

  // 验证正确性
  const allMatch = testValues.every((v, i) => v === decoded[i]);
  console.log("正确性验证:", allMatch ? "✅ 通过" : "❌ 失败");
}

benchmark();

⚡ 五、什么时候用什么编码？

编码方案选型决策表

💡 **提示：**如果你正在设计新的二进制协议，且没有历史包袱，Bijou64 是目前综合最优的选择——安全性最强、性能最好、实现也不复杂。

⚠️ 注意事项与坑点

• ❌ 不要在文本协议中使用：varint 是二进制编码，在 JSON 或 XML 中没有意义
• ❌ 不要手动实现偏移量计算：用查找表，不要在循环中计算偏移量
• ✅ 始终做边界检查：9 字节编码可能超出 u64 范围
• ✅ 使用 BigInt：JavaScript 的 Number 在超过 2⁵³ 后会丢失精度
• ✅ 写入时用大端序：Bijou64 规定大端序，和网络字节序一致

📝 总结

Bijou64 的故事告诉我们一个深刻的工程教训：正确的设计约束可以同时优化安全性和性能。它不是在 LEB128 上「加补丁」，而是从根本上消除了非唯一表示的可能性——结果不仅更安全，还更快。

对于开发者来说，选择编码方案的核心决策点是：

1. ✅ 如果你在设计新协议 → 优先考虑 Bijou64
2. ✅ 如果你需要签名/去重 → 必须用唯一表示编码
3. ⚠️ 如果你在用现有生态（Protobuf、WASM）→ 继续用规范编码
4. ❌ 如果你在文本协议中用 varint → 你可能选错了协议类型

⚡ **关键结论：**Bijou64 用「结构性安全」取代「运行时检查」，用「O(1) 长度确定」取代「逐字节扫描」，在安全性和性能上同时实现了突破。这是编码设计领域的「小而美」典范。

🔗 相关资源

• Bijou64 原始论文 — Ink & Switch 官方技术报告
• LEB128 规范 — 维基百科详细介绍
• Protocol Buffers 编码 — Protobuf varint 实现
• MDN: DataView — JavaScript 二进制数据处理