BECH32 のチェックサム

2019-12-10

segwit アドレスなどに使われる BECH32 エンコードは BIP173 に記述されていて、チェックサム部分は python のソースコードで示されています:

1 def bech32_polymod(values):
2   GEN = [0x3b6a57b2, 0x26508e6d, 0x1ea119fa, 0x3d4233dd, 0x2a1462b3]
3   chk = 1
4   for v in values:
5    b = (chk >> 25)
6    chk = (chk & 0x1ffffff) << 5 ^ v
7    for i in range(5):
8      chk ^= GEN[i] if ((b >> i) & 1) else 0
9  return chk

このアルゴリズムは BCH 符号であり、このようにパラメータを決めた理由が色々挙げられています。

bitcoin-core のソースコード にはもうちょっと詳しくコメントが書かれています。 これを手掛かりにもう少し深く理解したいと思います。

有限体 GF(2), GF(32)

BCH 符号は有限体の剰余になります。有限体 GF(q) は、要素数が q で要素間の四則演算の結果もまたその集合の要素になるような集合です。

まず GF(2) は 2の剰余体で表されます。整数を 2 で割った余りに丸めたものです。 たとえば $1+1 = 2$ ですので、それを 2で割った余りの 0 が結果となります。 差は和の逆演算で、2 の剰余の剰余の場合は和と同じになります。 さらに 0,1 をビットとみなすと、和や差は xor と同じ演算になります。

続いて GF(32) ですが、これは係数が GF(2) の要素からなる多項式の集合を、5次の素な多項式で割った余りで表せます。BECH32 では $a^5 + a^3 + 1$ を用いているようです。 5次の多項式で割った余りなので、結果は 4次になり、係数は 5つあります。この係数を並べて書くと、例えば $a^4 + a^3 + a$ は $11001$ と表記することができます。さらにこれを二進数表記された数値とみなして十進数で表すと、この例では $25$ になります。bitcoin-core ではこれを整数と区別するため、$\{25\}$ と書いています。

GF(32) の和と積を考えましょう。 元々が多項式の係数であるわけで、各ビットは独立して和を取ればよいことになります。さらに係数は GF(2) の要素ですから、和は xor です。つまり、GF(32) の和は、その値をビット xor すればよいわけです。コメントにあるように、

$$\{27\} + \{13\} = \{27 xor 13\} = \{22\}$$

次に積ですが、これは素直に多項式の積を計算して $a^5 + a^3 + 1$ で割った余りを取ります。

$$\begin{aligned} \{5\} * \{26\} &= (a^2 + 1) * (a^4 + a^3 + a) \\ &= (a^4 + a^3 + a) * a^2 + (a^4 + a^3 + a) \\ &= a^6 + a^5 + a^4 + a \\ &= a^3 + 1 (mod a^5 + a^3 + 1)\\ &= \{9\} \\ \end{aligned}$$

BCH の生成多項式

BCH符号は有限体の剰余でした。 有限体の大きさや剰余に使う多項式(=生成多項式)は、エラーの発見能力で制限されます。

BIP173 にあるように、BECH32 では 1023文字中の 3つのエラーを発見する能力を選びました。 このためには有限体 $GF(1024) = GF(32^2)$ を用いればよいことになります。

生成多項式は $GF(32)$ を係数とする 2次の多項式 3つの積になります(正しくは、連続する原始多項式3つの最小公倍数)。これが

$$g(x) = x^6 + {29}x^5 + {22}x^4 + {20}x^3 + {21}x^2 + {29}x + {18}$$

になるようです(導出方法は分からなかった)。

アルゴリズム

入力データを $GF(32)$ を係数とする多項式とみなし、それを $g(x)$ で割った余りを計算します。 5ビットの値を $GF(32)$ の要素とみなして取り扱います。

多項式の除算ですが、これは筆算を想像してください。 分かりやすく整数係数の多項式の除算、$(12x^3 + 11x^2+7x+5) / (3x+2)$ を考えましょう

                 4x^2 +  1x
  3x+2 / 12x^3 + 11x^2 + 7x + 5
        -12x^3 +  8x^2
                  3x^2 + 7x
                 -3x^2 + 2x
                         5x + 5

と筆算して、$(12x^3 + 11x^2 + 7x + 5) / (3x + 2) = 4x^2 + 1x \ldots 5x+5$ と計算できます。

筆算の計算は、

• 除数の項数と同じだけ被除数の上から取り出して除算 ($(12x^3 + 11x^2) / (3x+2) = 4x^2 \ldots 3x^2$) し、
• その余りに被除数の次の桁を追加($3x^2 + 7x$)して除算し…

と繰り返す形になっています。

GF(32) 係数多項式の余りも同様に計算できます(途中で出てくる掛け算と引き算は GF(32) で行います)

これをアルゴリズムへ落とすと、一桁ずつ取り出して中間結果に追記するループになります。 追記処理は桁をずらしてから加算するのですから、シフトしてから xor でいけます。

3  chk = 1
4  for v in values:
5    b = (chk >> 25)
6    chk = (chk & 0x1ffffff) << 5 ^ v

chk は除算の中間多項式です。 多項式の係数は GF(32) 数で、GF(32) 数は 5bit で表すことができました。 よって、各係数を二進数表記でずらっと並べて連結した数字例を多項式の係数リストとみなすことができます。 計算の都合上、低位ビットが次数の高い項の係数になるような並び方になります。

3行目の初期値の 1 は、入力多項式の最大項の係数を 1 にするためのトリックです。 これが無いと、例えば 101... と 0101... の区別がつかなくなります。

さて、6行目ではまず chk の下位25 ビットを取り出しています。 下位25ビットを取り出すというのはつまり、入力多項式の次数上位5項の係数を取り出しているわけです。

さらに 5ビット左シフトしてから v を xor しています。 v も GF(32) 数なので 5ビットで表されます。左シフトして 00000 になった下位 5ビット部分に xor するのは、加算と同じです。 これは筆算処理における前段階の余りに被除数の次項を加える処理に相当しています。

次に各段階における除算を考えます。 $f(x)$ を 5次多項式として被除数 $c(x) = c*x^6 + f(x)$ と置き、6次多項式 $g(x)$ での余りを計算すると、

$$\begin{aligned} c(x) \mod g(x) &= (c*x^6 + f(x)) \mod g(x) \\ &= c*x^6 (\mod g(x)) + f(x) \mod g(x) \\ \end{aligned}$$

f(x) は 5次なので、6次式で割った余りは自分自身だから、

$$\begin{aligned} c(x) \mod g(x) &= (c_0*x^6 \mod g(x)) + f(x) \end{aligned}$$

つまり、6次の項を g(x) で割った余りに、5次以下の項を加えたものになります。 ソースコードで言えば、6 行目の chk に、5行目の b を 6次の係数とした式の剰余を加えればよいわけです。

次の問題は、$c * x^6 \mod g(x)$ です。 $c$ は $GF(32)$ の要素なので 5ビットのベクトルで表すことができます。 このベクトルの成分を $c = (c_4, c_3, c_2, c_1, c_0)$ とすると、

$$\begin{aligned} c * x^6 \mod g(x) &= & &(&c_4&, &c_3&, &c_2&, &c_1&, &c_0&) * x^6 \mod g(x) \\ &= & &(&c_4&, &0&, &0&, &0&, &0&) * x^6 \mod g(x) \\ & & + &( &0&, &c_3&, &0&, &0&, &0&) * x^6 \mod g(x) \\ & & + &( &0&, &0&, &c_2&, &0&, &0&) * x^6 \mod g(x) \\ & & + &( &0&, &0&, &0&, &c_1&, &0&) * x^6 \mod g(x) \\ & & + &( &0&, &0&, &0&, &0&, &c_0&) * x^6 \mod g(x) \end{aligned}$$

$c_4$ は $GF(2)$ の要素なので 0 か 1 です。

0 の場合は

$$\begin{aligned} (0,0,0,0,0) * x^6 \mod g(x) &= (0,0,0,0,0) \mod g(x) \\ &= \{0\} \end{aligned}$$

1 の場合は

$$\begin{aligned} (1,0,0,0,0) * x^6 \mod g(x) &= \{16\}x^6 \mod g(x) \\ &= \{16\} * (x^6 \mod g(x)) \end{aligned}$$

となります。

各項も同様に展開できます。

$k(x) = x^6 \mod g(x)$ とおき、三項演算子を使ったコードに書き下すと、

$$\begin{aligned} c * x^6 (mod g(x)) &=& ( (c0==0)?0 : ({1} * k(x)) \\ &+& ( (c1==0)?0 : ({2} * k(x)) \\ &+& ( (c2==0)?0 : ({4} * k(x)) \\ &+& ( (c3==0)?0 : ({8} * k(x)) \\ &+& ( (c4==0)?0 : ({16} * k(x)) \\ \end{aligned}$$

と書けます。 これがソースコードの

7    for i in range(5):
8      chk ^= GEN[i] if ((b >> i) & 1) else 0

に相当しているわけです(python は三項演算子無いので後置if表記)。

次は GEN の中身を少し見ます。 まず GEN[0] ですが、これは ${1} * k(x) = k(x)$ です。

$$\begin{aligned} k(x) &= x^6 \mod g(x) \\ &= x^6 \mod (x^6 + \{29\}x^5 + \{22\}x^4 + \{20\}x^3 + \{21\}x^2 + \{29\}x + \{18\}) \\ &= \{29\}x^5 + \{22\}x^4 + \{20\}x^3 + \{21\}x^2 + \{29\}x + \{18\} \end{aligned}$$

です。 各係数を 5ビットに書き下して連結し、それを二進数値とみなして十六進表記すると、

      29    22    20    21    29    18
-> 11101 10110 10100 10101 11101 10010
-> 11 1011 0110 1010 0101 0111 1011 0010 
->  3 b 6 a 5 7 b 2

と表現できます。 これは

2   GEN = [0x3b6a57b2, 0x26508e6d, 0x1ea119fa, 0x3d4233dd, 0x2a1462b3]

GEN[0] に一致しました。

同様に、

$$\begin{aligned} GEN[1] &=& {2}*k(x) \\ &=& {2} * ({29}x^5 + {22}x^4 + {20}x^3 + {21}x^2 + {29}x + {18}) \\ &=& {2}*{29} x^5 + {2}*{22} x^4 + {2}*{20} x^3 + {2}*{21} x^2 + {2}*{29} x + {2}*{18} \\ \end{aligned}$$

GF(32) の積は最初の方で見たように、多項式の積を $a^5 + a^3 + 1$ で割った余りです。 {2} は多項式で表すと一次の項があるだけの x ですから、掛ける和の多項式を1次上げただけです。 ビット表現だと左シフトだけなることに注意して、

  {2}*{29} = {00010}*{11101} = 111010 (mod 101001) = 10011
  {2}*{22} = 101100 (mod 101001) = 00101
  {2}*{20} = 101000 (mod 101001) = 00001
  {2}*{21} = 101010 (mod 101001) = 00011
  {2}*{29} = 10011
  {2}*{18} = 100100 (mod 101001) = 01101
並べて十六進表記すると、
  10 0110 0101 0000 1000 1110 0110 1101
   2    6    5    0    8    e    6    d

となり、GEN[1] に一致しました。

以下同様に GEN が導出できます。