ハッシュ関数は、任意のデータから別の値を得るための関数のことです。ハッシュ関数から得られた値をハッシュ値または単にハッシュといいます。長い文字列であっても短い固定長の文字列に変換することができるのです。今回はハッシュ関数をつかってマークル木を実装します。
ハッシュ関数の実装とオーバーフロー対策
その前提としてハッシュ関数を実装します。ハッシュ関数は以下を用いることにします。
H(s) = (s の 1 文字目の文字コード * Bm-1 + s の 2 文字目の文字コード * Bm-2 + … + s の m 文字目の文字コード * B0) % mod（ただし、B = 100,000,007, mod = 1,000,000,007）
ハッシュ値を出力させたいのですが、以下のコードはうまくいきません。オーバーフロー(桁あふれ)がおきるからです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Program { public static void Main() { long B = (long)Math.Pow(10, 8) + 7; long mod = (long)Math.Pow(10, 9) + 7; Console.WriteLine(B); string str = "鳩でもわかるC#"; long sum = 0; for (int i = 0; i < str.Length; i++) sum += ((long)str[i] * (long)Math.Pow(B, str.Length - 1 - i)); Console.WriteLine(sum % mod); } } |
合同式とその性質
割り算の余りが等しいことを表現した式を合同式といいます。
例えば7を3で割るとあまりは1です。10を3で割ってもあまりは1で同じです。このようなとき 7≡10(mod3）と書きます。
a ≡ b(mod m) のとき以下のような性質があります。
|
1 2 3 |
a + c ≡ b + c a - c ≡ b - c ac ≡ bc |
足し算引き算かけ算の場合は普通の数と同じような性質があります。割り算の場合は無条件では成り立ちません。
a と m が互いに素という条件が満たす場合に限り、ax ≡ ay ならば x ≡ y が成り立ちます（逆も成り立つ）。
ということで剰余を計算するときは以下が成り立ちます。
(a + c) % m = ((a % m) + c) % m
(a * c) % m = ((a % m) * c) % m
これを使うと以下の方法でオーバーフローすることなくハッシュ値を計算することができます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
class Program { // xのy乗をmodで割ったときのあまりを求める public static long PowMod(long x, long y, long mod) { long ret = 1; for (int i = 0; i < y; i++) { ret *= x; ret %= mod; } return ret; } public static void Main() { long B = (long)Math.Pow(10, 8) + 7; long mod = (long)Math.Pow(10, 9) + 7; string str = "鳩でもわかるC#"; long hash = 0; for (int i = 0; i < str.Length; i++) { hash += str[i] * PowMod(B, str.Length - 1 - i, mod); hash %= mod; } Console.WriteLine(hash); } } |
出力：477702323
データの検証とマークル木
ハッシュ関数を用いることでデータの検証が可能になります。そのひとつがマークル木（マークルツリー）です。マークル木はノードにハッシュ値をもつ二分木で、それぞれ親ノードには子ノードのハッシュ値を結合したものから得られるハッシュ値が割り当てられています。そして木構造のルート部分のハッシュ値をルートハッシュと呼びます。
|
1 2 3 4 |
りんご バナナ ドーナツ チョコレート |
これらのハッシュ値をそれぞれ計算します。
りんご ⇒ 80583901
バナナ ⇒ 680587148
ドーナツ ⇒ 634711725
チョコレート ⇒ 244903041
計算が終わったらそれらを2つずつつなげます。
80583901 と 680587148 ⇒ 80583901680587148
634711725 と 244903041 ⇒ 634711725244903041
そしてこれらのハッシュを計算します。これを得られるハッシュ値がひとつになるまで繰り返します。
80583901680587148 ⇒ 996712791
634711725244903041 ⇒ 198935277
996712791 と 198935277 ⇒ 996712791198935277
996712791198935277 ⇒ 431870295
JavaScriptでマークル木を実装する
それでは動作確認できるようにJavaScriptで実装してみることにします。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
<!DOCTYPE html> <html lang="ja"> <head> <meta charset="UTF-8"> <title>鳩でもわかるマークル木</title> <meta name = "viewport" content = "width=device-width, initial-scale = 1.0"> </head> <body> <div id = "container"> <textarea rows = "10" cols = "32" id = "items"></textarea> <p>B:<input type="number" id = "B"></p> <p>mod:<input type="number" id = "mod"></p> <p><button onclick="calc()">計算</button></p> <p id = "result">ここに計算結果が表示されます</p> </div> <script> </script> <script src= "./index.js"></script> </body> </html> |
定数を示します。
index.js
|
1 2 3 4 |
const $B = document.getElementById('B'); const $mod = document.getElementById('mod'); const $items = document.getElementById('items'); const $result = document.getElementById('result'); |
ページが読み込まれたらBとmodの値をセットします。
|
1 2 3 4 |
window.onload = () => { $B.value = Math.pow(10, 8) + 7; $mod.value = Math.pow(10, 9) + 7; } |
[計算]ボタンがクリックされたらハッシュ値を計算します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
function calc(){ // テキストエリアの文字列を改行区切りで配列に変換（空白行は除去） let items = $items.value.split('\n'); items = items.filter(item => item != ''); // 入力されている値を取得する const B = BigInt($B.value); const mod = BigInt($mod.value); // Bのn乗 % mod を何回も使うので先に計算してそれを使う // Bのn乗 % modはどこまで計算する必要があるかを調べる。それがmaxLength。 // modの桁数の2倍より大きな値まで計算しておく必要がある let maxLength = $mod.value.length * 2 + 1; // それよりも長い文字列があるならmaxLengthの値を更新する for(let i = 0; i < items.length; i++){ if(maxLength < items[i].length) maxLength = items[i].length; } // Bのn乗 % mod を計算する const pows = []; pows.length = maxLength + 1; let pow = BigInt(1); pows[0] = pow; // 0乗なら1 for(let i = 1; i < maxLength; i++){ pow *= B; pow %= mod; pows[i] = pow; } while(items.length > 1){ const hashs = []; for(let i = 0; i < items.length; i+=2){ // getHash関数（後述）でハッシュ値を計算する hashs.push(getHash(items[i], pows, mod)); if(i + 1 < items.length) hashs.push(getHash(items[i+1], pows, mod)); else hashs.push(getHash(items[i], pows, mod)); // 文字列が存在しない場合は前のハッシュ値をコピーする } items = []; for(let i = 0; i < hashs.length; i+=2){ // つぎにハッシュ値を求める文字列を生成する（ハッシュ値をつなげるだけ） items.push(hashs[i].toString() + hashs[i + 1].toString()); } } // itemsが1つだけになったらループをぬけてそのハッシュ値を結果として表示する $result.innerText = getHash(items[0], pows, mod); } |
getHash関数は事前に計算しておいたpowsを使って第一引数のハッシュ値を求めます。
|
1 2 3 4 5 6 7 8 |
function getHash(str, pows, mod){ let hash = BigInt(0); for (let i = 0; i < str.length; i++){ hash += BigInt(str.charCodeAt(i)) * pows[str.length - 1 - i]; hash %= mod; } return hash; } |
