Base58 を BigInt で一気に変換したら、先頭の 0x00 が消えて 112 が 2 になった

背景

自分のツールサイトに、テキストを Base58 に変換するページを置いています。
https://hashitosystem.com/tools/base58/
Node.js で同じ変換を書くなら BigInt で数行で済むのでは、と思って試してみました。
結果は、いくつかの入力で短すぎる文字列が出てきました…。
先頭のゼロのバイトの扱いだったので、備忘録として残しておきます。

Base58 をざっくり

Base58 は、バイト列を58種類の文字だけで表す符号化だ。
Base64 と目的は似ていますが、見間違えやすい 0（ゼロ）O（オー）I（アイ）l（エル）と、URL などで扱いにくい + / を使いません。
Bitcoin のアドレスで使われている形式として知られています。

使う文字は下記の58文字で、この並び順がそのまま 0〜57 の値になります。

123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz

先頭の 1 が値0の文字です。
Base64 は3バイトずつ区切って変換しますが、Base58 は区切れないので、バイト列全体を1つの大きな数とみなして58進数に直す、という仕組みだ。

最初に書いたもの

下記が最初に書いた、BigInt で一気に変換する版です。
bytes は 0〜255 の数値の配列で、文字列なら Buffer.from('hello') を [...] で展開したものを渡す想定です。

const ALPH = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz';

function naiveBase58(bytes) {
  let n = 0n;
  for (const b of bytes) n = n * 256n + BigInt(b); // バイト列を1つの大きな数にする
  let out = '';
  while (n > 0n) { out = ALPH[Number(n % 58n)] + out; n /= 58n; }
  return out;
}

console.log(naiveBase58([...Buffer.from('hello')]));
console.log(naiveBase58([0x00, 0x00, 0x01]));
console.log(naiveBase58([0x00, 0x01]));
console.log(naiveBase58([0x01]));

結果は下記です。

Cn8eVZg
2
2
2

hello は正しく Cn8eVZg になります。
ところが [0x00, 0x00, 0x01] と [0x00, 0x01] と [0x01] が全部 2 になってしまいました。
3つの違うバイト列が同じ文字列になるので、もうデコードで元に戻せません。

なぜ消えるのか

[0x00, 0x00, 0x01] を1つの数として読むと、0x000001 で、ただの 1 だ。
数としては、先頭にいくつ 0 が並んでいても値は変わらない。
なので数に直した時点で、先頭の 0x00 が何個あったかという情報が落ちてしまいます。

これを避けるため、Base58 には「先頭の 0x00 は1個につき 1 を1文字付ける」という決まりがあります。
1 はアルファベットの0番目なので、ゼロのバイトをゼロの文字で残しておく、という考え方だと思います。

ツールでやっていること

下記がツールのエンコード処理を Node.js 向けに書き直したものです（中身は同じです）。
先頭の 0x00 を数えて zeros に取っておき、残りを58進数に直してから、最後に zeros 個の 1 を前に付けます。

function bytesToBase58(bytes) {
  let zeros = 0;
  while (zeros < bytes.length && bytes[zeros] === 0) zeros++;
  const digits = [0]; // 58進数の各桁（下の桁から）
  for (let i = zeros; i < bytes.length; i++) {
    let carry = bytes[i];
    for (let j = 0; j < digits.length; j++) {
      carry += digits[j] << 8;          // 今の値を256倍してこのバイトを足す
      digits[j] = carry % 58;
      carry = (carry / 58) | 0;
    }
    while (carry > 0) { digits.push(carry % 58); carry = (carry / 58) | 0; }
  }
  let out = '1'.repeat(zeros);
  for (let m = digits.length - 1; m >= 0; m--) out += ALPH[digits[m]];
  return out;
}

for (const b of [[0x00, 0x00, 0x01], [0x00, 0x01], [0x01]]) {
  console.log(JSON.stringify(b), '->', bytesToBase58(b));
}

Node.js v24 で実行した結果です。

[0,0,1] -> 112
[0,1] -> 12
[1] -> 2

先頭の 0x00 の数だけ 1 が付いて、3つが別々の文字列に戻ったのがわかると思います。
デコードはこの逆で、先頭の 1 の数を数えて、その数だけ 0x00 を先に並べてから残りを256進数に直します。

ツールは BigInt を使わず、桁の配列で筆算のように変換しています。
先頭ゼロの扱いは、数に直す前に分けておくのが要点で、変換の書き方とは関係ありません。
BigInt 版でも、zeros を数えて '1'.repeat(zeros) を前に付けるだけで同じ結果になります。

どこで困るか

テキストを変換するだけなら、先頭が 0x00 になることはまずありません。
困るのはハッシュ値や鍵など、ただのバイナリを Base58 にするときだ。
たまたま先頭バイトが 0x00 のものだけ1文字短くなり、デコードすると1バイト短いデータが返ってきます。
普段はほとんど起きないので、テストを書いていても気づきにくい種類のバグな気がします。

結論

Base58 はバイト列を1つの数として58進数に直すので、先頭の 0x00 は数値の中で消えてしまいます。
エンコードでは先頭の 0x00 を先に数えてその数だけ 1 を付け、デコードでは先頭の 1 の数だけ 0x00 を戻してください。
自前で書いたら、[0x00, 0x00, 0x01] が 112 になることを1行のテストで確かめておくのが確実です。

---

本記事はAI補助で執筆した、個人開発の紹介記事です。