今回はブロックチェーン技術の基礎にある数学について、勉強会で勉強したことの備忘録を兼ねて解説したいと思います。
ここ数年はWeb 3.0という言葉をよく聞きますが、これはブロックチェーン技術と極めて密接な関係があります。
来るべき時代に備えてブロックチェーンについて学んでおくのも良いでしょう。
そして単にブロックチェーン技術を学ぶといっても、その技術を担保している数学理論をブラックボックスにしていたら、本当に理解しているとは言えないでしょう。
私は普段の業務ではブロックチェーンを扱うことはないのですが、
個人的に参加している社外の勉強会で学んだことのアウトプットにしたいと思います。
ざっくり言って、ブロックチェーン技術の基礎となる数学は二つあります。
一つは「有限体」。
そしてもう一つが「楕円曲線」です。
ブロックチェーンで使う暗号は、これら二つの数学上の概念をうまく組み合わせることにより成り立っています。
今回の記事では、まず、「有限体」について解説します。
有限体
抽象数学への免疫を作る
先ほど基礎となる数学をブラックボックスにしていたら本当の理解はできないと申し上げたばかりなのですが、高等数学の抽象的な考え方に慣れていない人は、まずはこういうものなのかと雰囲気を掴むだけで十分かと思います。
そしてその雰囲気を醸し出しているものがブロックチェーン技術のもとになっているんだな〜と思ってくれれば大丈夫です。
まず、「有限体」とは、「体」という数学の概念の一つです。
「体」は、簡単に言えば、どの二つの要素に対しても足し算・引き算・かけ算・わり算の四種類の計算方法を行うことができるような集合のことです。
ですから例えば、実数は「体」です。
なぜなら、テキトーに実数の集まりから数字を1.23と2.71を取ったとしたら、これらの二つの数字に対して「足し算・引き算・かけ算・わり算」のどの計算を行った結果もまた実数になるからです。(1.23+2.71=3.94, 1.23-2.71=-1.48, 1.23x2.71=3.3333, 1.23/2.71=0.4538...)
何を当たり前のことを言っているのだと思われるかもしれませんが、これが抽象数学の特徴なのです。
どういうことかと言うと、抽象数学では、「ある性質を満たすものをある概念と定義する」というような構成になっているのです(公理主義と言います)。
上の例で言えば、「どの二つの要素に対しても足し算・引き算・かけ算・わり算の四種類の計算方法を行うことができる」という性質を持つものを、「体」と定義しているわけです。
それに対して、小学一年生の算数で習った足し算から高校数学までは、この「ある性質を満たすものをある概念と定義する」とは逆向きの「ある概念はある性質を満たす」という直感的な考え方をします。
この非直感的な論理の逆転現象が、抽象数学への参入障壁を高くしていると(わたしは勝手に)考えています。
それではこうした抽象数学が直感的な数学よりも「正しい」ものなのかというとそうは言い切れません。
これはあくまで流儀の問題であって、20世紀初頭以来の哲学の課題にもなっています。(本当はこの話題もしたいのですが、本題から外れすぎてしまいますので、ここではしません)
ただし抽象数学は、「抽象」だからこそ共通点や規則性を見つけ出したりすることに対しては力を発揮します。
そうした力が、ブロックチェーン技術はもとより様々な分野での実用的な応用につながっているのです。
有限体の定義
「体」とは、任意の二つの要素$a$と$b$が以下の性質をすべて満たすような集合です。
- $a+b$および$ab$がその集合に含まれる
- $0$がその集合に含まれて、$a+0=a$である
- $1$がその集合に含まれて、$1a=a$である
- $-a$がその集合に含まれて、$a+(-a)=0$である
- $a^{-1}$がその集合に含まれて、$a^{-1}a=1$である
そして、「有限体」とは上記の$a$と$b$が含まれる集合が有限集合であるときの「体」のことを言います。
例えば実数全体の集合は「体」ですが、実数は無限に存在するので、これは無限集合であって「有限体」ではないのです。
ブロックチェーン技術で使われる「有限体」
ブロックチェーン技術で使われる有限体は具体的にどのような集合なのでしょうか?
それは、
$$
{0,1,2,3,...,p-2,p-1}
$$
のような集合です。
ただし、$p$は素数です。
この場合はp個の要素があるので、$p$をこの有限体のオーダーと呼びます。
また、オーダーが$p$の有限体を$F_p$と表記することが多いです。
つまり、$F_p={0,1,2,3,...,p-2,p-1}$です。
しかし、この集合のもとで足し算とかけ算などを行ったらこの集合の中に収まらないのではないか、と疑問に思うかもしれません。
ここがまた抽象数学のとっつきにくい所だと思うのですが、
ここでいう「足し算、引き算、かけ算、割り算」は、我々の慣れ親しんでいる「足し算、引き算、かけ算、割り算」とは異なるものなのです。
そもそも「足し算、引き算、かけ算、割り算」というもの自体が、それをどう定義するかに依存する操作にすぎないという考え方が抽象数学にはあります。
それではここではどのようにそれらを定義するのかというと、モジュラー計算というものを使って定義します。
モジュラー計算というものは聞き慣れないかもしれませんが、高校の数学の教科書のコラムにも載っていたようなものなので、そこまで難しいものではありません。
一言でモジュラー計算を説明するならば、「余りを求める計算」です。
プログラミングでは「%」を使って計算する言語が多いアレです。
例えば、数学的には$10\equiv7(mod3)$で表され、プログラミングでは$10%7=3$のように計算するのがモジュラー計算です。
それでは、さっそくこのモジュラー計算を使って、$F_p$における「足し算・引き算・かけ算・わり算」を定義していきましょう!
モジュラー計算を用いて、$F_p$における足し算$+_f$を次のように定義します。
$a+_fb=(a+b)%p$
例えば、$3+_f5=(3+5)%7=1\in F_7$です。
モジュラー計算を用いて、$F_p$における引き算$-_f$を次のように定義します。
$a -_f b = (a-b)%p$
例えば、$7-f2=(7-2)%11 = 5 \in F{11}$です。
モジュラー計算を用いて、$F_p$におけるかけ算$\times_f$を次のように定義します。
$a \times_f b = (a\times b)%p$
例えば、$6\times_f4=(6\times4)%13=11\in F_{13}$です。
モジュラー計算を用いて、$F_p$におけるわり算$\div_f$を次のように定義します。
・・・と、言いたい所ですが、わり算は足し算と引き算とかけ算に比べてかなり複雑です。
モジュラー計算におけるわり算を自然に導入するために、フェルマーの小定理を使います。
フェルマーの小定理
$n$と素数$p$の最大公約数が$1$である時、$n^{p-1}\equiv p(mod1)$である。
このフェルマーの小定理の$p$と、有限体$F_p$の$p$を関連づけます。
どうやって関連づけるのかというと、それは以下のように関連づけます。
まず、「わり算」は「かけ算」の逆の操作であることは理解できると思います。
ですから、自然な定義では、
$a\div_fb=a\times_f(b^{-1})$
となってほしいところです。
ところで、$F_p$におけるかけ算の定義から、$b\times_f b = (b \times b)%p = b^2% p$でした。
ここからさらに、$b^2 \times_f b = (b^2\times b)%p=b^3%p$です。
これを繰り返せば、$b^{(p-1)}%p$が登場します。
また、有限体$F_p={0,1,2,...,p-2,p-1}$の要素は、どれも素数$p$と2以上の最大公約数を持ちません。
$b$と$p$の最大公約数は1なので、フェルマーの小定理の出番より、$b^{p-1}%p=1$です。
従って、$b^{-1}=b^{-1}\times_f1=b^{-1} \times b^{(p-1)}=b^{p-2}$と変形できるので、
$a\div_f b = a \times_f b^{p-2}$
となります。
以上より、
モジュラー計算を用いて、$F_p$におけるわり算$\div_f$を次のように定義します。
$a \div_f b = a \times_f b^{p-2} = (a \times b^{p-2})%p$
例えば、$2\div_f7=2\times_f7^{19-2}=465261027974414%19=3$です。
まとめ
- ブロックチェーン技術における数学の二本柱のうちの一つは「有限体」
- オーダー$p$は素数で、有限体$F_p={0,1,2,3, ..., p-2, p-1}$である。
- 有限体$F_p$で定義された四則演算(足し算、引き算、かけ算、わり算)は普通のそれとは異なる
正直な所、なぜこのような有限体なるものがブロックチェーン技術に用いられているのかは、現段階では見当もつかないと思います。
しかしこの有限体を、ブロックチェーン技術における数学の二本柱のうちのもう一つである「楕円曲線」と組み合わせることで、強力な暗号を作り出すことができ、それがブロックチェーンになくてはならないものなのです。
次回は、ブロックチェーン技術における数学の二本柱のうちのもう一つである、「楕円曲線」について解説していこうと思います!
参考文献
- Programming Bitcoin: Learn How to Program Bitcoin from Scratch, Jimmy Song, O'REILLY, 2019
- 『代数学入門』, 石田信, 実教出版株式会社, 1978