GF(2) R1CSのための二進体タワーをRubyで実装してみる

前回はR1CSを扱い、最後にGF(2)上では「制約1本 = ANDゲート1個、XORはタダ」になるところまで見た。ただしあれは制約の書き方の話で、証明系ではない。

今回はその先、GF(2)上のR1CSの充足性を実際に検査する側に進む。最初に立ちはだかるのは、体を小さくしたことの代償で、その解決に二進体のタワーを用いる。今回はそこまでをRubyで書いてみた。

GF(2)には元が2つしかない

多くの算術系の証明系では、「多項式の等式が成り立つ」ことを示す形に問題を変換する。ただし全部の点で確かめると点の数に比例する手間がかかるので、ランダムな1点だけ確かめて済ませる。これが成立するのは、2つの多項式が違えばその差は0でない多項式であり、0でない多項式の根の個数は次数以下しかないから。体の元がたくさんあれば、ランダムに選んだ点がたまたま根に当たる確率は小さい。次数 ${d}$ の多項式が大きさ ${|S|}$ の集合からランダムに取った点で0になる確率は高々 ${d / |S|}$ （Schwartz-Zippelの補題）。

問題は ${\mathbb{F}_2}$ だと元が2つしかないこと。これでは「たまたま根に当たる確率が小さい」という前提が成立しない。実際、 ${f(x) = x^{2} + x = x(x+1)}$ は0でも1でも0になる。

解決策は単純で、以前のBabyStarkの記事でもやったようにwitnessは ${\mathbb{F}_2}$ に置いたまま、チャレンジだけ大きな体から取る。ここで小さいのが問題になるのはチャレンジ空間であって、witnessではない。witnessはGF(2)のままでも、GF(2)係数の多項式を拡大体上の多項式として評価することができる。チャレンジを拡大体から選ぶことで、ランダム評価の健全性を確保できる。 ${\mathbb{F}_{2^{128}}}$ からチャレンジを取れば、次数 ${d}$ の多項式を見逃す確率は ${d/2^{128}}$ 。sumcheckなどではdは小さいので実質的に ${2^{-128}}$ のオーダーになる。

そのためには ${\mathbb{F}_2}$ の拡大体が要る。そして拡大体の作り方として二進体で使われるのがタワー構成。

二進体のタワー

たとえば、 ${\mathbb{F}_{2^{16}}}$ を作る場合。元の個数は65536個。16ビットの整数がちょうど65536通りなので、16ビット整数を「体の元のビット表現」として使える。

元どうしの演算のうち、足し算は簡単。標数2の体で加算はXORなので、0xBEEF + 0xCAFEは0xBEEF ^ 0xCAFE。問題は掛け算の方で、0xBEEF × 0xCAFEを整数として計算すると65536を軽く超えて体の外に出てしまう。そこで結果が65536個の元の中に収まるような掛け算の規則を、別に決める必要がある。

掛け算の規則を決める

この規則を決めるために使われるのが既約多項式（それ以上因数分解できない多項式）。

16ビットの整数を「0か1の係数が16個並んだ多項式」とみなす。たとえば 0b1011 なら ${x^{3} + x + 1}$ 。多項式どうしは普通に掛け算できるけど、掛けると次数が上がってしまうので、選んでおいた16次の既約多項式で割って余りを取るようにする。すると、次数が15以下に戻り、また16ビットに収まる。整数の剰余計算と同じ発想で、既約多項式が法の役割をしている。

どういった既約多項式を選ぶかは自由で、選んだ多項式が変われば0xBEEF × 0xCAFEの結果も変わる。体としてはどれを選んでも同じもの（同型）になるので数学的な優劣はないけど、実装のしやすさは変わる。

2次拡大を積み重ねる

↑のような16次の既約多項式を1つ選ぶ方式だと、元は「係数が16個並んだ多項式」になるけど、二進体では拡大体を作るにあたって2次拡大を何段も積み重ねる構成が使われる。元の表し方も変わり、係数を16個並べるのではなく「1つ下の段の元を2つ組にする」という入れ子で表す。

${\mathbb{F}_2 \to \mathbb{F}_{2^{2}} \to \mathbb{F}_{2^{4}} \to \mathbb{F}_{2^{8}} \to \mathbb{F}_{2^{16}}}$

元の表現が1ビット → 2ビット → 4ビット → 8ビット → 16ビット。各段で、1つ下の段の元を2つ組み合わせて上の段の元を作る。塔のように段を積むのでタワー構成と呼ばれている。ここでは、各段を ${T_0, T_1, \ldots, T_4}$ と書くことにする。 ${T_k}$ の元は ${2^{k}}$ ビットで、この記事で使うのは ${T_4 = \mathbb{F}_{2^{16}}}$ 。実際の利用では、 ${T_7 = \mathbb{F}_{2^{128}}}$ を取るけど、読みやすいようこの記事では ${T_4 = \mathbb{F}_{2^{16}}}$ を使用する。

なかでもよく使われるWiedemannの構成では、 ${T_k}$ への拡大に

k = 1の場合は、 ${X_0^{2} + X_0 + 1}$
k ≧ 2の場合は、 ${X_{k-1}^{2} + X_{k-2} X_{k-1} + 1}$

という2次既約多項式を使う。各段は2次拡大なので、必要な既約多項式も2次式1本で済む。

${T_k}$ の元は、上位半分と下位半分がそれぞれ ${T_{k-1}}$ の元になっていて、

${a = a_{hi} X_{k-1} + a_{lo}}$

と分解できる。2つの元を掛けて展開すると ${X^{2}}$ の項が出てくるので、 ${X^{2} = X X_{k-2} + 1}$ で還元して1次に戻す。これをRubyで書くと、

module Tower
  module_function

  # T_k の元 +a+ と +b+ の積を返す。
  # @param a [Integer] T_k の元（2^k ビットに収まる非負整数）
  # @param b [Integer] T_k の元
  # @param k [Integer] タワーの段。T_k = F_{2^(2^k)} を表す
  # @return [Integer] 積。T_k の元
  # @example F_{2^16}（4段）の乗算
  #   Tower.mul(0xBEEF, 0xCAFE, 4) # => 0xB8D3
  def mul(a, b, k)
    return a & b if k == 0 # F_2 の乗算は AND

    half = 1 << (k - 1)  # T_{k-1} のビット数
    mask = (1 << half) - 1
    a_lo, a_hi = a & mask, a >> half
    b_lo, b_hi = b & mask, b >> half

    lo_lo = mul(a_lo, b_lo, k - 1)
    hi_hi = mul(a_hi, b_hi, k - 1)
    cross = mul(a_lo ^ a_hi, b_lo ^ b_hi, k - 1) ^ lo_lo ^ hi_hi # カラツバ法

    gen = k == 1 ? 1 : (1 << (1 << (k - 2)))  # X_{k-2}
    hi = cross ^ mul(hi_hi, gen, k - 1) # X^2 = X*X_{k-2} + 1 で還元
    lo = lo_lo ^ hi_hi

    (hi << half) | lo
  end
end

標数2なので加算はどの段でも単なるXORで済む。

一番下の段まで降りると乗算はa & b、つまりビット単位のANDになる。

mul(a, b, 4)
  └─ mul(..., 3)
       └─ mul(..., 2)
            └─ mul(..., 1)
                 └─ mul(..., 0) → a & b ←ここ

前回の「GF(2)では乗算 = AND」が、ここで実際の演算として現れる（実際には各段でmulを4回呼ぶので、末端のANDは1個ではなく多数になる）。

体になっていることを確かめるには逆元が要るので、冪と合わせて用意しておく。逆元は、乗法群の位数が ${2^{2^{k}} - 1}$ なので ${a^{2^{2^{k}} - 2}}$ で求まる。

module Tower
  module_function

  # 繰り返し二乗法で T_k の元 +a+ の +e+ 乗を返す。
  def pow(a, e, k)
    r, b = 1, a
    while e > 0
      r = mul(r, b, k) if e.odd?
      b = mul(b, b, k)
      e >>= 1
    end
    r
  end

  # T_k の非ゼロ元 +a+ の乗法逆元を返す。
  def inv(a, k) = pow(a, (1 << (1 << k)) - 2, k)
end

実際に動かしてみよう。まず ${T_1 = \mathbb{F}_{2^{2}}}$ の体のすべての元の組み合わせについて乗算表を出してみる。

(0...4).each { |a| puts (0...4).map { |b| Tower.mul(a, b, 1) }.join(" ") }

2の冪乗が2→3→1 と巡回していて、位数3の乗法群になっているのが分かる。0以外の3つの元がちゃんと群をなしている。

乗法の結合則・分配則・逆元を総当たりで確認してみる（ ${T_2 = \mathbb{F}_{2^{4}}}$ の16元で）。

els = (0...16).to_a
k = 2

# 結合則
els.product(els, els).all? { |a, b, c|
  Tower.mul(Tower.mul(a, b, k), c, k) == Tower.mul(a, Tower.mul(b, c, k), k)
} # => true

# 分配則
els.product(els, els).all? { |a, b, c|
  Tower.mul(a, b ^ c, k) == (Tower.mul(a, b, k) ^ Tower.mul(a, c, k))
} # => true

# 逆元
els.drop(1).all? { |a| Tower.mul(a, Tower.inv(a, k), k) == 1 } # => true

${T_4 = \mathbb{F}_{2^{16}}}$ も同様に動く。

ab = Tower.mul(0xBEEF, 0xCAFE, 4)      # => 0xB8D3
Tower.mul(ab, Tower.inv(0xCAFE, 4), 4) # => 0xBEEF

タワーのメリット

タワーで作ると、下の段の元が上の段のビット列にそのまま入る。

${T_4}$ の元0xBEEFは、上位の0xBEと下位の0xEFに分ければ、それぞれが ${T_3}$ の元になっている。逆に ${T_3}$ の元 0xEF を ${T_4}$ の元として扱いたければ、上位を0埋めして0x00EFとするだけ。整数としては同じ値なので、変換という作業が存在しない。

このタワーで一番効果があるのがこれ。

Tower.mul(a, b, 2) == Tower.mul(a, b, 3)   # a, b < 16 なら true
Tower.mul(a, b, 3) == Tower.mul(a, b, 4)   # a, b < 256 なら true

下の段に属する元同士なら、どの段で掛けても同じ答えを返す。 ${T_2 \subset T_3 \subset T_4}$ という包含が、ビット列の表現としてそのまま実現されている。通常の有限体の拡大だと元の表現を変換する必要があるけど、ここでは変換が発生しない。

特に ${\mathbb{F}_2}$ の元、つまり0と1については

${0 \cdot b = 0, \quad 1 \cdot b = b}$

なので、 ${\mathbb{F}_2}$ の元と拡大体の元の積は「選ぶだけ」になる。乗算をする必要もない。

# 0 と 1 については、どんな相手でも計算が要らない
(0...(1 << 16)).step(97).all? { |x|
  Tower.mul(0, x, 4) == 0 && Tower.mul(1, x, 4) == x
} # => true

「witnessは ${\mathbb{F}_2}$ 、チャレンジは ${\mathbb{F}_{2^{16}}}$ 」という構成を効率よく実装できるのは、GF(2)が拡大体の部分体として自然に埋め込まれ、さらにGF(2)の元との積が「選ぶだけ」で済むから。

まとめ

${\mathbb{F}_2}$ は元が2つしかないので、チャレンジをそこから取るとランダム評価による十分な健全性を確保できない。witnessは ${\mathbb{F}_2}$ のまま、チャレンジだけ拡大体から取る
拡大体を作るには掛け算の規則、つまり既約多項式を選ぶ必要がある。選び方は自由だが実装のしやすさが変わる
二進体では2次拡大を積み重ねるタワー構成を使う。Wiedemannの構成なら各段で同じ形の2次既約多項式を使える
タワーの効果は部分体の埋め込みがタダなこと。下の段の元が上の段のビット列にそのまま入り、変換が要らない
結果として小さい体との積が安くなり、witnessとチャレンジで体を使い分けられる

次回は、このタワーの上でsumcheckを動かす。GF(2) R1CSの充足性を「全部の制約が0」から「重み付き総和が0」に変換し、それを1点での評価まで縮める。witnessが ${\mathbb{F}_2}$ であることが実際にどこで効くのかを、ラウンドごとの乗算を数えて確かめる。

Develop with pleasure!

福岡でCloudとかBlockchainとか。