2つの集合の対称差を求めるアルゴリズムを実装したMinisketch

techmedia-think.hatenablog.com

のコアとなる実装の1つがMinisketch。

Minisketchは、2つの集合の対称差を求めるアルゴリズムPinsketchを実装したライブラリ。つまりAとBという2つの集合があったとして、Aには含まれているがBには含まれていない要素＋Bには含まれているけどAには含まれていない要素を帯域幅効率良い方法で算出できるライブラリ。Erlayでは、2つのフルノード間でmempool内のトランザクションの差分を求めるのに、このMinisketchを利用している。

Minisketchの特性

Minisketchは、

要素の集合からスケッチを作成し、
2つのスケッチを組み合わせて、2つの元の集合間の対称差のスケッチを計算する。
（スケッチには予め決められた容量があり、集合内の要素の数がこの容量を超えない限り）スケッチから集合の要素を復元することができる。

スケッチは、以下の3つのパラメーターを持つ：

容量（c）：スケッチが照合可能な、要素の差異の数。
フィールドサイズ（b）：スケッチに格納する要素のビット数。集合の要素のサポートされる範囲は ${1..2^{b}-1}$ までの整数。
実装（implementation）：実装の指定値で0をデフォルトでサポート。ハードウェアによってより効率的なアルゴリズムを使用できることも。

容量がcで要素がbビットのスケッチは、b✕cビットを格納できる。なお、加算はXORなので、同じ要素をスケッチに2回追加するとスケッチから削除されるので注意。

具体的な利用手順は、アリスとボブがそれぞれ要素の集合を持っていて、その要素の多くが重なっている場合、以下のようになる：

アリスとボブは自身の集合の要素を計算する。
アリスは自分のスケッチをボブに送信する。
ボブは2つのスケッチを組み合わせ、対称的な差分スケッチを入手する。
ボブは差分スケッチから要素を復元する。
ボブは差分の各要素をアリスに送信して、自身の不足要素を要求する。

minisketchのライブラリをFFIでラッパーしたminisketchrbを利用すると↑のプロセスはRubyで以下のように書ける。

require 'minisketch'

b = 12
impl = 0
c = 4

# アリスがスケッチを作成
sketch_a = Minisketch.create(b, impl, c)

# アリスが要素をスケッチに追加
(3000...3010).each do |i|
  sketch_a.add(i)
end

# アリスはスケッチをシリアライズ
serialized_a = sketch_a.serialize

# ボブがスケッチを作成して要素を追加
sketch_b = Minisketch.create(b, impl, c)
(3002...3012).each do |i|
  sketch_b.add(i)
end

# ボブはアリスから受け取ったデータからアリスのスケッチを復元
sketch_ba = Minisketch.create(b, impl, c)
sketch_ba.deserialize(serialized_a)

# ボブは両者のスケッチをマージ
sketch_b.merge(sketch_ba)

# 差分の要素を復元
_, difference = sketch_b.decode(c)
puts difference # 3000, 3001, 3010, 3011が出力される

Minisketchのアルゴリズム

続いて、Minisketchがどうやって↑を実現しているのか、アルゴリズムをちょっと見とく。

フィールド要素への変換とべき級数の集合

まず集合の各要素は ${1..2^{b} - 1}$ の範囲の整数（bはスケッチのフィールドサイズ）である。この各要素は、スケッチに追加する際に有限体 ${GF(2^{b})}$ のフィールドにマッピングされる。（b=32の場合）有限体の要素は ${x^{32} + x^{7} + x^{3} + x^{2} + 1}$ を法とするGF(2^b)上のxの多項式として表され、整数の各ビットi（値 ${2^{i}}$ ）を多項式表現における ${x^{i}}$ の係数として扱う。たとえば、整数 ${101 = 2^{6} + 2^{5} + 2^{2} + 1}$ は、フィールド要素 ${x^{6} + x^{5} + x^{2} + 1}$ にマッピングされる。このため、整数と有限体の要素はそれぞれ加算と乗算をサポートする。

続いて、要素（mとする）を以下の形式のべき級数にマッピングする関数をSとする。

${S(m) = 1 + mx + m^{2}x^{2} + m^{3}x^{3} + ...}$

※ 無限に続いていくけど、任意の値xに対して実際にこの式を評価することはないので、収束は気にしなくていいみたい。

単一の要素に対する↑を集合 ${M = m_1, m_2, ...}$ に拡張する。

${S(M) = S(m_1) + S(m_2) + ... = (1 + 1 + ...) + (m_1 + m_2 + ...)x + (m_1^{2} + m_2^{2})x^{2} + ...}$

また、同じ要素の加算はXORとなるため、m + m = 0となり、これをSにも適用すると、以下のような計算が成立するようにする。

${S(m_1, m_2) + S(m_2, m_3) = S(m_1) + S(m_2 + m_2) + S(m_3) = S(m_1, m_3)}$

要素の復元

ポイントは、このようなべき級数から集合内の要素を復元する方法。

↑から単一の要素のべき級数S(m)は等比級数であることから、 ${(1 - mx)^{-1}}$ に収束し、

${(1 - mx)S(m) = 1}$

が成立し、さらに複数の要素に拡張していく。たとえば要素が2つの場合は、

${(1 - m_1x)(1 - m_2x)S(m_1, m_2) = (1 - m_1x)(1 - m_2x)(S(m_1) + S(m_2)) = (1 - m_2x) + (1 - m_1x)}$

3つの場合は、

${(1 - m_1x)(1 - m_2x)(1 - m_3x)S(m_1, m_2, m_3) = (1 - m_1x)(1 - m_2x)(1 - m_3x)(S(m_1) + S(m_2) + S(m_3)) = (1 - m_2x)(1 - m_3x) + (1 - m_1x)(1 - m_3x) + (1 - m_1x)(1 - m_2x)}$

と、任意の要素 ${m_i \in M}$ について ${1 - m_ix}$ をS(M)に乗算するとn-1次の多項式になる。

このことから、P = S(M)Lがn-1次の多項式になるような、いろんな ${m_i}$ のn個の異なる ${(1 - m_ix)}$ 係数の積である多項式Lを見つけることができたら、それらの値 ${m_i}$ がMの要素として復元できるということらしい。

多項式S(M)の係数を ${s_i}$ 、多項式Lの係数を ${l_i}$ として ${S(M) = s_0 + s_1x + s_2x^{2} + s_3x^{3} + ...}$ および ${L = l_0 + l_1x + l_2x^{2} + l_3x^{3} + ...}$ （ ${l_0 = 1}$ ）とした場合、上記が成立するためには、次数n以上の多項式Pの係数はすべて0になることから、