【メモ】仮想通貨のハッシュ関数に求められる性質について

自分の頭の中を整理するために調べたり、考えたりしたメモ書きです。 備忘としてこちらに残すことにします。

全射性/単射性について

順列の最小完全ハッシュ関数に書いてあるように、全射性も単射性も必須ではない。

全射

def:  f: A \to B全射

{\displaystyle \forall b\in B,\,\exists a\in A\;{\text{ s.t. }}f(a)=b}

射影した先(上記のB)に射影されない元があっても問題ない。
ただし、実装上は終域の大きさは小さくしたいので、全射だとうれしい。

単射

def:  f: A \to B単射
 (
\displaystyle{  \forall a_{1},a_{2} \in A
  ) \;
  \left[ a_{1} \neq a_{2}  \Longrightarrow  f(a_{1}) \neq f(a_{2})
\right]  \\
\Longleftrightarrow
(
\forall a_{1}, a_{2} \in A
) \;
\left[ f(a_{1}) = f(a_{2}) \Longrightarrow \ a_{1} = a_{2}  \right]
}

単射が満たされないことによって、いわゆる衝突が起こる。つまり、defの上段について、
 (
\exists a_{1},a_{2} \in A
  ) \;
  \left[ a_{1} \neq a_{2}  \Longrightarrow  f(a_{1}) = f(a_{2})
\right]
が反例となる。

→ハッシュ衝突がないハッシュ関数は、完全ハッシュ関数という。 さらに終域Bが最小になるような場合を最小完全ハッシュ関数といい、このときは全単射になる。

いいハッシュ関数とは

Wikipediaに挙げられている特性と、仮想通貨で求められる特性とを比較し、まとめると以下表の通り。

特性 内容 仮想通貨では?
低コスト 計算コストが低いこと PoWでは、ある程度の計算コストが要求される(計算コストが大きいことで、改竄に対する耐性を実現している)
決定性 同じ入力であれば同じ出力 同じく求められる
一様性 一様分布に近いこと 同じく求められる
可変な値域 値域が拡張できること SHA-256からSHA-512にしたいときなどには求められる
連続性 類似した入力は、類似した出力
(線形探索したい場合には有用)
逆に全く違う値であることが求められる

仮想通貨で考えるのに適しているのは、暗号学的ハッシュ関数Wikipediaから引用すると要求事項は、以下の通り。

  • 同一のハッシュ値であるのに、そっくりだが実は異なるというようなメッセージの作成が不可能であること。
  • ハッシュ値から、そのようなハッシュ値となるメッセージを得ることが(事実上)不可能であること(原像計算困難性、弱衝突耐性)。
  • 同じハッシュ値となる、異なる2つのメッセージのペアを求めることが(事実上)不可能であること(強衝突耐性)。

一般には以下の特性が必要

原像計算困難性
ハッシュ値からもとのキーを見つけることが困難であること

第2原像計算困難性
h(k) = h(k')となるようなk'が見つけることが困難であること
弱衝突耐性とも。

第2原像計算困難性では、kが与えられている前提での攻撃、つまり、攻撃対象のkと同じハッシュ値を持つk'を見つける攻撃に対して困難性があることを要求している

強衝突耐性
h(k) = h(k')となるようなk, k'が見つけることが困難であること

強衝突耐性では、任意のkk'に対して、同じハッシュ値を持つ入力を見つける攻撃に対して困難性があることを要求している。誕生日のパラドックスで言及されるように、こちらのほうが計算量は少ない(一般には、終域のサイズを2倍にする必要がある)

計算コストについて

仮想通貨の文脈では、ASIC耐性として、単位金銭あたりのハッシュレートに差がないことも求められる。 要は、同じハッシュ計算(主流はSHA-256)するのに、CPU、GPU、ASICで計算するのに掛かる金銭コストが異なるのが不平等だという点。 特にASICは、寡占状態という指摘もあるよう。

Cuckoo Cycleでは、memory-boundなアルゴリズムにすることで、この不平等さを解消しようとしている。 paper読んだらまとめたい。

References