ハッシュ#
皆さんはハッシュ関数の動作原理に比較的慣れていると思いますが、暗号学で使用されるハッシュ関数はcrypto-graphic hash functionと呼ばれます。
それには二つの重要な性質があります。一つは collision resistance（衝突耐性）と呼ばれます。この場合の collision はハッシュ衝突を指します。
もし二つの入力 x, y があり、x ≠ y で、ハッシュ関数がH(v)であるとき、H(x) = H(y)となる場合、これをハッシュ衝突と呼びます。
異なる二つの入力から計算されたハッシュ値が等しいのです。ハッシュ衝突は非常に一般的です。私たちがハッシュテーブルを使用する過程でハッシュ衝突に遭遇することがあります。
異なる入力がハッシュテーブルの同じ位置にマッピングされる可能性があります。一般的に、ハッシュ衝突は避けられません。
なぜなら、入力空間は出力空間よりもはるかに大きいためです。例えば、256 ビットのハッシュ値があるとしましょう。では、出力空間はどれくらいの大きさでしょうか。
すべてのハッシュ値の可能性は 2 の 256 乗であり、出力空間はこの大きさしかありません。しかし、入力空間は無限大であり得ます。
したがって、任意の多様な可能性があります。鳩の巣原理に従えば、必ず二つの入力が同じ出力にマッピングされる状況が発生します。
したがって、ここで言うcollision resistanceはハッシュ衝突が発生しないことを意味します。ある📖ではこの性質をcollision freeと呼んでいます。
この表現はあまり好きではありません。なぜなら、それは人に誤解を与えやすいからです。まるで衝突が発生しないかのように思えるからです。実際には衝突は客観的に存在します。
この意味は、実際には効率的にハッシュ衝突を人為的に生成する方法がないということです。与えられたxに対して、他のyを見つける良い方法はありません。
H(x)とH(y)のハッシュ値がちょうど等しくなるようなyを見つける良い方法はありません。強引に探そうとすれば、力任せの解法を使うことができます。
例えば、xとyがある場合、すべての入力の可能性を列挙して、どれが計算されたハッシュ値とちょうど等しいかを確認します。これをbrute-forceと呼びます。
すべての値を列挙し、最終的にハッシュ値がちょうど衝突するものを見つけます。もし入力空間が非常に大きい場合、例えばハッシュ値が 256 ビットの場合、
実際には力任せの解法を使用することは不可能です。その作業量は非常に大きすぎます。
では、collision resistanceという性質は何に役立つのでしょうか？
それはメッセージのダイジェストを求めるために使用できます。
例えば、私たちにはmというメッセージがあります。そのハッシュ値をH(m)とします。
このハッシュ値はこのメッセージのダイジェストと見なすことができます。これはこのメッセージの改ざんを検出するために使用されます。
例えば、誰かがこのメッセージの内容を変更すると、そのハッシュ値は変わります。
collision resistanceという性質は、あなたが別の m'を見つけてH(m')がH(m)とちょうど等しくなることができないことを意味します。
内容を改ざんする方法はありません。そして、検出されることはありません。例えば、あなたが非常に大きなファイルを持っているとします。あなたはそれをあるクラウドストレージサービスに保存したいと思っています。
必要なときに再度ダウンロードするわけですが、どうやってあなたがダウンロードしたバージョンが、最初にアップロードしたバージョンと同じであることを確認するのでしょうか？
これにはハッシュ関数の衝突耐性の性質を利用できます。このファイルをアップロードする前に、まずハッシュ値を計算します。
このハッシュ値はローカルに保存されます。将来的にダウンロードした後、再度ハッシュ値を計算します。そして、元々保存していたハッシュ値と比較します。もし同じであれば、
アップロードしたこのファイルは改ざんされていないことを示します。ダウンロードしたのは元々のバージョンです。これが衝突耐性の一つの用途です。
一点注意してください。数学的に衝突耐性が証明されているハッシュ関数は存在しません。
つまり、私たちが今話している非常に重要な性質は、理論的には証明できないのです。
これは実践の経験に依存するしかありません。いくつかのハッシュ関数は長い時間の検証を経ています。
世界中には多くの暗号学の専門家がいますが、誰も人為的にハッシュ衝突を生成する方法を見つけていません。
したがって、これらのハッシュ関数は衝突耐性があると考えられています。つまり、実践的な経験です。
また、私たちが衝突耐性があると考えているいくつかのハッシュ関数もありますが、
後に人々がハッシュ衝突を生成する方法を見つけました。ここで非常に重要な例は MD5 です。MD5 はかつて非常に人気のあるハッシュ関数で、安全だと考えられていました。
しかし、今ではそれは通用しません。私たちはすでに人為的にハッシュ衝突を生成する方法を知っています。
暗号学で使用されるハッシュ関数にはもう一つの性質があります：hiding（隠蔽）。hiding とは何でしょうか？hiding はハッシュ関数の計算過程が一方向であることを意味します。
逆算できず、与えられたxからそのハッシュ値H(x)を計算できますが、ハッシュ値H(x)から元の入力xを逆算することはできません。言い換えれば、
このハッシュ値H(x)は入力xに関する情報を漏らしていません。これを hiding と呼びます。しかし、実際にはこの入力を知りたい場合、
方法はあります。どうするかというと、やはり力任せの方法を使います。私はこの入力のすべての可能な値を列挙し、どの入力の値がH(x)と元のH(x)と等しいかを確認します。
そうすれば、元の入力xが何であるかを推測できるのです。したがって、力任せの解法は一つの方法です。hiding という性質が成立する前提は、この入力空間が十分に大きく、
そのためこの力任せの解法が実行不可能であることです。また、この入力の分布が比較的均等である必要があります。さまざまな可能な値の可能性がほぼ同じである必要があります。もしこの入力空間が非常に大きいとしても、
ほとんどのケースで値が少数のいくつかの値に集中している場合、比較的簡単に破られる可能性があります。
hiding という性質は何に役立つのでしょうか？それは衝突耐性という性質と組み合わせて、デジタルコミットメントを実現するために使用できます。このデジタルコミットメントは、密封された封筒のデジタル同等物とも呼ばれます。
現実生活における密封された封筒は何に使われるのでしょうか？
例えば、ある人が株式市場を予測でき、翌日どの株がストップ高になるかを予測できるとします。
その人の予測が正確かどうかをどうやって証明するのでしょうか？一つの方法は、その人が前日にテレビで予測結果を発表することです（私は xxx 株が翌日ストップ高になると予測します。）。
翌日の取引終了後、その株が本当にストップ高になったかどうかを確認すれば、予測が正確かどうかわかります。
こうすることに問題はありますか？これは予測が正確かどうかを確認する方法のようですが、問題があります。もし予測結果が事前に公開されると、
株式市場に影響を与える可能性があります。例えば、その人が非常に有名で、皆がその人を株の神と見なしている場合、本来その株はストップ高にならないはずですが、彼が公に予測したことで、
皆が必死に買いに走る結果、ストップ高になってしまいます。当然、逆の状況もあり得ます。この株は本当にストップ高になる必要があるのに、
誰かが場を乱そうとするかもしれません。「あなたはストップ高になると予測したのだから、私はストップ高にさせない」と言って、必死に売りに出すこともあり得ます。これらはすべて起こり得ることです。これは予測結果を事前に公開できないことを示しています。
しかし、予測結果を事前に公開せず、翌日の取引終了後に公開する場合、どうやってその予測結果が改ざんされていないかを確認するのでしょうか？
最終的に公開された結果が、前日に作成されたものであるかどうかをどうやって確認するのでしょうか？これには、私たちが言う密封された封筒が必要です。
あなたは予測結果を紙に書き、それを封筒に入れて封をします。この封筒は第三者の公正機関に保管してもらいます。
翌日の取引終了後にそれを開封し、その結果が正確かどうかを確認します。現実の密封された封筒はこれです。
では、電子の世界では、デジタル密封された封筒をどのように実現するのでしょうか？予測結果を入力xとしてハッシュ値を計算します。そして、このハッシュ値を公開することができます。私たちはこの hiding の性質を持っているので、
このハッシュ値から予測結果が何であるかはわかりません。そして翌日の取引終了後に、予測結果を公開します。衝突耐性の性質があるため、私の予測結果は改ざんされることはありません。もし改ざんされた場合、最初に公開されたハッシュ値と一致しなくなります。これが密封された封筒の機能を果たします。実際の操作には注意すべきいくつかの詳細があります。私たちが言う hiding の性質の前提は何でしょうか。入力空間が十分に大きく、分布が比較的均等である必要があります。この入力がこの性質を満たさない場合、例えばこの例のように、翌日どの株がストップ高になるかを予測する場合、株は数千銘柄しかないため、入力空間は十分に大きくありません。一般的な方法は、この入力の後ろにランダムな数をランダムに結合し、それを一緒にハッシュを取ることです。つまり、これはxではなく、xの後ろに nonce を結合し、全体をハッシュします。H(x | Nonce)。この nonce は私たちが選んだランダムな数であり、選挙後に全体の入力が十分にランダムであることを保証します。そして、分布も十分に均等です。これは実際の操作で注意すべきいくつかの詳細です。
暗号学で要求されるこの二つの性質に加えて、ビットコインで使用されるハッシュ関数には三つ目の性質が要求されます。それは puzzle friendly（パズルフレンドリー）と呼ばれます。これは、ハッシュの計算が事前に予測できないことを意味します。入力を見ただけでは、そのハッシュ値が何であるかを知るのは難しいのです。したがって、あなたが計算したハッシュ値がある範囲内にあることを考えると、良い方法はなく、あなたは一つ一つ試すしかありません。どの入力が計算されたハッシュ値が要求される範囲内にちょうど収まるかを確認します。例えば、あなたがハッシュ値を得たい場合、前のkビットがすべて 0 である必要があります。0000000…0000000xxxxxxx..xxx 全体が 256 ビットで、最初のk個のゼロで始まる必要があります。どのような入力がこのハッシュ値を計算するのでしょうか？それはわかりません。puzzle friendly という性質は、事前にはわからないことを意味します。どの入力がこのハッシュ値を計算する可能性が高いかはわかりません。したがって、このハッシュ値を得るためには、一つ一つ試すしかありません。近道はありません。この性質がなぜ puzzle friendly と呼ばれるのかは、後でビットコインのマイニングプロセスについて説明します。皆さんは「マイニング」という言葉を聞いたことがあるかもしれません。マイニングは実際には nonce を探すことです。この nonce はブロックのヘッダーの他の情報と組み合わされ、入力としてハッシュを取り出します。そのハッシュ値は特定の目標閾値以下でなければなりません。これはH(block header) ≤ targetです。ビットコインはブロックチェーンであり、ブロックチェーンは一つ一つのブロックで構成された連結リストです。各ブロックにはブロックヘッダーがあります。ブロックヘッダーには多くのフィールドがあります。その中に設定可能なランダム数 nonce があります。マイニングプロセスは、さまざまな nonce を試し続け、全体のブロックヘッダーをハッシュした後、指定された範囲内に収まるようにすることです。例えば、これが全体の出力空間 outspace です。私たちが求めるハッシュ値は、この一点だけが合法である必要があります。これが target space です。この puzzle friendly という性質は、マイニングプロセスに近道がないことを意味します。大量の nonce を試し続けなければ、要求される解を見つけることはできません。したがって、このプロセスは作業証明として使用されます。これを proof of work と呼びます。あなたがマイニングを行い、要求される nonce を見つけた場合、それは必ず大量の作業を行った結果です。近道はありません。
ここで注意してください。マイニングプロセスは、多くの作業量を必要とし、要求される nonce を見つけることが非常に難しいですが、一旦誰かがそのような nonce を見つけて公開すると、他の人がその nonce が要求を満たしているかどうかを検証するのは非常に簡単です。ハッシュを一度計算するだけで済みます。この nonce はヘッダーの一部として、ハッシュ値を一度計算し、それが目標の閾値以下であるかどうかを確認します。マイニングは難しいが、検証は簡単です。この性質は difficult to solve, but easy to verify（解決は難しいが、検証は簡単）と呼ばれます。このようなマイニングパズルを設計する際には、この性質に注意が必要です。
ビットコインで使用されるハッシュ関数は SHA-256 であり、この sha は secure hash algorithm を意味します。私たちが言及したこの三つの性質はすべて満たされています。ある学生は puzzle friendly と collision resistance が非常に似ていると感じるかもしれません。この二つの性質には一定の関連性がありますが、完全に同じではありません。私たちはビットコインが暗号学の二つの機能を利用していることを言いました。一つはハッシュ、もう一つは署名です。
署名#
ここで、最初の機能であるハッシュについての説明を終えます。次に署名について説明します。
署名について説明するためには、ビットコインシステムにおけるアカウント管理について触れる必要があります。日常生活でアカウントを開設したい場合、身分証明書を持って銀行に行き、口座開設手続きを行います。これは中央集権的なシステムにおけるアカウント管理の方法です。しかし、ビットコインは非中央集権的であり、銀行のような機関は存在しません。では、どうやってアカウントを開設するのでしょうか？各ユーザーが自分でアカウントを開設することを決定します。誰の承認も必要ありません。アカウント開設のプロセスは非常に簡単で、公開鍵と秘密鍵のペアを生成することです（public key, private key）。ローカルで公私鍵のペアを生成することが、ビットコインにおけるアカウントを表します。この公私鍵の概念は非対称暗号の体系から来ています。これを asymmetric encryption algorithm と呼びます。最初の暗号体系は対称的でした。これを symmetric encryption algorithm と呼びます。例えば、二人が通信を行う場合、私はあなたに特定の情報を送信したいとします。しかし、この通信ネットワークは盗聴される可能性があります。では、どうするか？私たちは事前に秘密鍵を合意します。これを encryption key と呼びます。私はこの情報を暗号化してあなたに送信します。あなたは受け取った後、その鍵を使って復号します。暗号化と復号に同じ鍵を使用するため、これを対称的な暗号体系と呼びます。この前提は、通信の両者に鍵を配布するための安全なチャネルがあることを仮定しています。明らかに、鍵をネットワーク上で平文の形式で送信することはできません。私たちはネットワーク自体が安全でないと仮定しています。盗聴される可能性があるため、これが対称暗号体系の弱点です。鍵の配布があまり便利ではありません。この問題を解決するために非対称暗号体系が提案されました。私たちは一つの鍵ではなく、鍵のペアを使用します。公鍵と私鍵があります。暗号化には公鍵を使用し、復号には私鍵を使用します。例えば、私はあなたに情報を送信したい場合、あなたの公鍵を使ってその情報を暗号化し、あなたは受け取った後、自分の私鍵を使って復号します。元の情報を得ることができます。皆さん注意してください。この暗号化と復号には同じ人の公鍵と私鍵が使用されます。受信者の公鍵と私鍵です。
これにはどんな利点があるのでしょうか？公鍵は秘密にする必要がなく、暗号化に使用される公鍵は秘密にする必要がなく、誰にでも知らせることができます。ある人は自分のホームページに公鍵を掲載しています。皆が知ることができます。私鍵は秘密にする必要があり、復号には私鍵が必要ですが、私鍵はローカルに保存しておけばよく、相手に渡す必要はありません。通信相手はあなたの私鍵を知る必要はありません。彼はあなたの公鍵で暗号化します。あなたが彼に返信する場合、彼の公鍵で暗号化します。お互いに相手の私鍵を知る必要はありません。これにより、対称暗号体系における鍵の配布の不便さの問題が解決されます。ビットコインシステムでは、アカウントを作成するためにローカルで公私鍵のペアを生成します。この公鍵はあなたの銀行口座に相当します。他の人があなたに送金するには、あなたの公鍵を知っていればよいのです。この私鍵はあなたのアカウントのパスワードに相当します。この私鍵を知っていれば、アカウントの資金を移動させることができます。では、問題があります。前述のように、ビットコインシステムは暗号化されていないと述べました。彼は暗号通貨と呼ばれていますが、実際には暗号化されていません。情報はすべて公開されています。では、この公鍵と私鍵は何のためにあるのでしょうか？実際には署名を行うために使用されます。
例えば、私はあなたに 10 ビットコインを送金したいとします。そして、この取引をブロックチェーンに公開しますが、他の人はどうやってこの取引が確かに私から発信されたものであることを確認するのでしょうか？誰かが私になりすまして、こっそりと私のアカウントからお金を移動させることはないのでしょうか？これには、私がこの取引を公開する際に自分の私鍵を使ってこの取引に署名する必要があります。他の人がこの取引を受け取った後、私の公鍵を使ってこの署名の正当性を検証します。署名には私鍵が使用され、署名の検証にはその人の公鍵が使用されます。
依然として同じ人です。すべての人が独立してアカウントを生成します。ローカルで独立して公私鍵のペアを生成します。誰の承認も必要ありませんが、万が一二人が同じ公私鍵のペアを生成した場合、どうすればよいのでしょうか？例えば、誰かがビットコインを盗もうとする場合、一つの方法は公私鍵を生成し続け、生成した公鍵がブロックチェーン上の既存の公鍵と同じかどうかを比較することです。もし同じであれば、私鍵を使ってそのアカウントの資金を盗むことができます。この攻撃方法は理論的には可能のように思えますが、実際には不可能です。例えば、256 ビットのハッシュ値の場合、同じ公私鍵を生成する可能性は微々たるものです。例えば、あなたがスーパーコンピュータを持っていて、毎日大量の公私鍵のペアを生成しても、二人の公私鍵のペアが同じになる確率は無視できるほど小さいです。この確率は地球が爆発する確率よりも小さいです。これまでのところ、この方法で成功した攻撃の前例はありません。ここで強調したいのは、私たちが仮定しているのは、公私鍵を生成する際に良いランダムソースがあることです。これを a good source of randomness と呼びます。公私鍵を生成するプロセスは明らかにランダムです。もし選択したランダムソースが悪い場合、前述の分析は成り立たなくなります。二人の公私鍵のペアが同じになる可能性があります。ビットコインで使用される署名アルゴリズムは、公私鍵を生成する際に良いランダムソースが必要なだけでなく、その後の各署名の際にも良いランダムソースが必要です。一度でも署名に使用するランダムソースが悪ければ、私鍵が漏洩する可能性があり、その場合は全てが終わります。この点には十分注意してください。
私たちは二つの機能、すなわちハッシュと署名について説明しました。この二つの機能は組み合わせて使用することができます。ビットコインシステムでは、一般的にまずメッセージのハッシュを求め、その後このハッシュ値に署名します。