Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationEventAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
253
Help us understand the problem. What are the problem?
Organization

hashアルゴリズムとハッシュ値の長さ一覧(+ハッシュ関数の基本と応用)

「ハッシュ値の衝突(コリジョン)」や「データの改ざん防止」など、複数のハッシュ・アルゴリムを組み合わせるために、ハッシュ値の「長さ」と「速度の目安」一覧が欲しい

... ってか、それ以外に用途あるの?!ハッシュって、そんなにおいしいの?

TL; DR (今北産業)

  1. この記事はハッシュ関数の出力結果を桁数ごとに、まとめたものです。

    • ハッシュ関数の各々の「アルゴリズムが何文字の 16 進数で返してくるか」の事前確認にご利用ください。
  2. TS; DR ではハッシュ関数を完全に理解した気になれる基礎知識と応用例が読めます。

    • 読み物です。ゴロ寝して読んでください。読み終わると、ブロックチェーン[?] や NFT[?] の仕組みの理解、分散ファイル・システム[?] が使える気になります。
  3. マスター、一番強いヤツをくれ。

    • OS やプログラム言語間の互換性・強度・速度で、一番バランスが取れているハッシュ・アルゴリズム
      • sha3-512(64 Byte, 128桁, 2020/12/22 現在)
        (ここでいう互換性とは「どの言語でも標準・・で大抵は実装しているアルゴリズム」のことです)
    • OS やプログラム言語間の互換性無視で「速度優先」の新参ハッシュ・アルゴリズム
      • BLAKE3(64 Byte, 128桁, 2021/09/02 現在)
        (まだ検証中らしいのでプロダクションに使えませんが、強度は SHA-2 と SHA-3 の中間くらいと見られています。 一覧に含めてませんが爆速です。Go 版だと実測で FNV1 より 6 倍以上速かったです ... まじか)
    • パスワード・ハッシュ[?]の強度で一番強いアルゴリズム(速いとは言ってない)

  • ハッシュ関数とは: ハッシュ関数の基本・特徴
  • なんで長さなの?: ハッシュ関数の応用
  • n バイトって HEX 文字列で最大何文字だっけ?:
    • 単純に n を2倍してください。
      :point_right: 1バイト=0xFF、例:4バイト=HEXで8桁=FF FF FF FF
  • なに?4DrlX のような短いハッシュ値を作りたい?:
  • この記事は、LGTM が付くたびに、何かしら見直したり、手を加えてスパイラル・アップさせています。そのため適宜内容が変わります。なお、変更通知は送りませんのでストックくださった方はお暇な時に覗きに来てください。

ハッシュ・アルゴリズムとビット長の一覧
(ハッシュ値の長さ一覧)

ハッシュ・アルゴリズム一覧

WIP

250 LGTM 頂いたので "List of hash functions" @ Wikipedia の和訳を載せていきたいと思います。が、途中でバテたので LGTM がつくたびに少しずつ充実していきたいと思います。

CRC 系(Cyclic Redundancy Check, 巡回冗長検査

アルゴリズム名
(関数名含む)
データ長 算出タイプ
(系統)
備考
cksum (Unix) 4 Byte (32 bit) CRC 名残で checksum と付いているが、POSIX:2008 (IEEE Std 1003.1-2008) に準拠した CRC-32 アルゴリズムを使ったコマンドであるため CRC に分類される。改竄かいざん耐性はなく、簡単に衝突(ことなる値で同じ出力に)させることができる。
CRC-16 2 Byte (16 bit) CRC
CRC-32 4 Byte (32 bit) CRC
CRC-32 MPEG-2 4 Byte (32 bit) CRC
CRC-64 8 Byte (64 bits) CRC
  • Adler-32 は CRC であると思われていますが、実質的にはチェックサムの部類に分類されます。

チェックサム系(Check Sum, 誤り検出符号)

アルゴリズム名
(関数名含む)
データ長 算出タイプ
(系統)
備考
BSD checksum (Unix) 16 bits sum 巡回シフトによる巡回符号のチェックサム・アルゴリズム。古くから BSD に実装されており sum コマンド などで使われている。CRC-32 型の cksum コマンドよりもエラー検知が弱く、CRC 同様に改竄かいざん耐性はない。データワードの順序の変更や、すべてのビットがゼロに設定されたワードの挿入または削除など、一度に多くのビットに影響するいくつかの一般的なエラーを検出できず「単純なチェックサム」の部類に入る。
SYSV checksum (Unix) 16 bits sum 巡回シフトによる巡回符号のチェックサム・アルゴリズム。System V の初期から実装されており sum コマンド などで使われている。CRC-32 型の cksum コマンドよりもエラー検知が弱く、CRC 同様に改竄かいざん耐性はない。「単純なチェックサム」の部類に入る。
sum8 8 bits sum データが 0 になるまで上位から 8 ビットごとにシフトして(取り出して)得られた数値を加算していき合計を出す。次に合計から下位 8 ビットを取り出し、反転させてから 1 を加えたもの(補数)を SUM 値として使う。確認する側は、同じようにデータを 8 ビットごと加算していき、SUM 値も含めて加算すると(SUM 値は合計の補数であるため)合計の最後の 8 ビットが 0 になる。そして合計が 0 以外の場合はエラーとする考え方。
単純な足し算であるため、データの並び順は関係なくなり、意図的な改竄かいざんには極めて弱い。しかし、検出率自体は単純計算で 99.6% 以上あり、計算しやすく高速であるため、簡易な誤り検出で速度が必要な場合に使われる。TCP/IP の IP パケットを転送(ルーティング)する際の確認などで使われる。
sum16 16 bits sum 上記の 16 ビット版
sum24 24 bits sum 上記の 24 ビット版
sum32 32 bits sum 上記の 32 ビット版
fletcher-4 4 bits sum Adler-32 の原型ともなったチェックサム・アルゴリズム。単純なチェックサムよりも計算コストは高くなるものの信頼性が高い。TCP のチェックサムのオプションの 1 つにも採用されている。Solaris 系のファイルシステムのチェックサムとしても採用されている。素数の積(合成数)を利用しておりビット長に合わせたバリエーションがある。
fletcher-8 8 bits sum
fletcher-16 16 bits sum
fletcher-32 32 bits sum
Adler-32 32 bits sum zlib の圧縮ライブラリの圧縮や展開/解凍のチェックのために fletcher-16 を改善して開発された。信頼性と引き換えに高速性を追求しているタイプ。同じ長さの CRC よりも速い。信頼性は fletcher-16 と fletcher-32 の中間くらい。IETFRFC1950 で定義されており、素数の剰余(mod)を利用している。
xor8 8 bits sum
Luhn algorithm 1 decimal digit sum
Verhoeff algorithm 1 decimal digit sum
Damm algorithm 1 decimal digit Quasigroup operation

Universal hash function families

アルゴリズム名
(関数名含む)
データ長 算出タイプ
(系統)
備考
Rabin fingerprint variable multiply
tabulation hashing variable XOR
universal one-way hash function
Zobrist hashing variable XOR

Non-cryptographic hash functions

アルゴリズム名
(関数名含む)
データ長 算出タイプ
(系統)
備考
Pearson hashing 8 bits (or more) XOR/table
Paul Hsieh's SuperFastHash[1] 32 bits
Buzhash variable XOR/table
Fowler–Noll–Vo hash function (FNV Hash) 32, 64, 128, 256, 512, or 1024 bits xor/product or product/XOR
Jenkins hash function 32 or 64 bits XOR/addition
Bernstein's hash djb2 32 or 64 bits shift/add or mult/add or shift/add/xor or mult/xor
PJW hash / Elf Hash 32 or 64 bits add,shift,xor
MurmurHash 32, 64, or 128 bits product/rotation
Fast-Hash 32, 64 bits xorshift operations
SpookyHash 32, 64, or 128 bits see Jenkins hash function
CityHash 32, 64, 128, or 256 bits
FarmHash 32, 64 or 128 bits
MetroHash 64 or 128 bits
numeric hash (nhash) variable division/modulo
xxHash 32, 64, 128 bits product/rotation
t1ha (Fast Positive Hash) 64 and 128 bits product/rotation/XOR/add
pHash fixed or variable see Perceptual hashing
dhash 128 bits see Perceptual hashing
SDBM 32 or 64 bits mult/add or shift/add also used in GNU AWK

Keyed Cryptographic Hash Functions

アルゴリズム名
(関数名含む)
データ長 算出タイプ
(系統)
備考
BLAKE2 arbitrary keyed hash function (prefix-MAC)
BLAKE3 arbitrary keyed hash function (supplied IV)
HMAC
KMAC arbitrary based on Keccak
MD6 512 bits Merkle tree NLFSR
One-key MAC (OMAC; CMAC)
PMAC (cryptography)
Poly1305-AES 128 bits nonce-based
SipHash 32, 64 or 128 bits non-collision-resistant PRF
HighwayHash 64, 128 or 256 bits non-collision-resistant PRF
UMAC
VMAC

Unkeyed cryptographic hash functions

アルゴリズム名
(関数名含む)
データ長 算出タイプ
(系統)
備考
BLAKE-256 256 bits HAIFA structure[14]
BLAKE-512 512 bits HAIFA structure[14]
BLAKE2s up to 256 bits HAIFA structure[14]
BLAKE2b up to 512 bits HAIFA structure[14]
BLAKE2X arbitrary HAIFA structure,[14] extensible-output functions (XOFs) design[15]
BLAKE3 arbitrary Merkle tree
ECOH 224 to 512 bits hash
FSB 160 to 512 bits hash
GOST 256 bits hash
Grøstl up to 512 bits hash
HAS-160 160 bits hash
HAVAL 128 to 256 bits hash
JH 224 to 512 bits hash
LSH 256 to 512 bits wide-pipe Merkle–Damgård construction
MD2 128 bits hash
MD4 128 bits hash
MD5 128 bits Merkle–Damgård construction
MD6 up to 512 bits Merkle tree NLFSR (it is also a keyed hash function)
RadioGatún arbitrary ideal mangling function
RIPEMD 128 bits hash
RIPEMD-128 128 bits hash
RIPEMD-160 160 bits hash
RIPEMD-320 320 bits hash
SHA-1 160 bits Merkle–Damgård construction
SHA-224 224 bits Merkle–Damgård construction
SHA-256 256 bits Merkle–Damgård construction
SHA-384 384 bits Merkle–Damgård construction
SHA-512 512 bits Merkle–Damgård construction
SHA-3 (subset of Keccak) arbitrary sponge function
Skein arbitrary Unique Block Iteration
Snefru 128 or 256 bits hash
Spectral Hash 512 bits wide-pipe Merkle–Damgård construction
Streebog 256 or 512 bits Merkle–Damgård construction
SWIFFT 512 bits hash
Tiger 192 bits Merkle–Damgård construction
Whirlpool 512 bits hash


ハッシュ値の長さ一覧と速度の目安

すべて同じメッセージをハッシュ化したもの(「Hello Qiita!」のハッシュ値)なのに、ハッシュ値の長さ、つまりビット長が同じでも値がまったく異なることに注目ください。

🐒   各アルゴリズムの PHP 7.2.6 での計算速度も記載していますが、環境だけでなく PHP のバージョンによってかなり速度が異なります。速度は目安程度にご利用ください。まずは強いアルゴリズムで組んでから、「推測するな、測定せよ」の精神でご自分の環境に最適化することをお勧めします。
なお、SHA-3 に含まれる SHAKE256 などの可変長のアルゴリズム、および SHA-3 の最終選考まで残った BLAKE2 や、その後続で爆速と噂の BLAKE3 は、まだライブラリが枯れて(OS やプログラム言語で浸透)していないため含めていません。

仕様

  • 検証環境:macOS HighSierra(OSX 10.13.6), PHP 7.2.6(cli), MacBookPro Early 2015, 2.7GHz Corei5, Mem 8GB 1867MHz DDR3
  • ハッシュするメッセージ:「Hello Qiita!」
  • ループ回数:1,000,000 回(100 万回)
  • 速度:上記ループの 10 回ぶんの平均値
  • 並び順:桁数の少ない順 → 速い順
  • メッセージダイジェストは横スクロールをさけるため 8 桁(4バイト)ごとのブロックに分けています
  • 測定のソースコード @ Paiza.IO

8 桁のハッシュ値

アルゴリズム バイト長 速度 ハッシュ値
fnv132 4 Byte 0.157887 sec b04649f6
fnv1a32 4 Byte 0.157962 sec 129b42dc
adler32 4 Byte 0.165301 sec 1bf5042e
crc32 4 Byte 0.169681 sec dd54ff69
crc32b 4 Byte 0.172050 sec ad6adc0d
joaat 4 Byte 0.173369 sec 2cbbf315

16 桁のハッシュ値

アルゴリズム バイト長 速度 ハッシュ値
fnv164 8 Byte 0.168120 sec 97bfaffd 885daad6
fnv1a64 8 Byte 0.176964 sec 07c72cc2 7b5f8b5c

32 桁のハッシュ値

アルゴリズム バイト長 速度 ハッシュ値
md4 16 Byte 0.284748 sec e2500f3f 1eb028a4 563ca3d4 35028996
md5 16 Byte 0.337097 sec 7c414ef7 535afff2 1e05a36b 1cfc9000
tiger128,3 16 Byte 0.341727 sec 60bd4df9 e039716f 07c9ecd4 4c203d34
tiger128,4 16 Byte 0.397596 sec 7c20d9b5 d9e79da7 b5241a08 a353018a
ripemd128 16 Byte 0.553369 sec 0ff7eaf1 38540680 8e92e642 28a79243
haval128,3 16 Byte 0.954699 sec a8fe5c62 4c856077 d07db6bc 9a7f1275
haval128,4 16 Byte 1.027350 sec b5ee64c0 6a003d55 65108356 08c6a34c
haval128,5 16 Byte 1.197690 sec ad189ff3 183c9cfe cf5a39e3 45ba95f8
md2 16 Byte 4.762099 sec 8cd3c9c1 f1079b15 639ddab1 2227d400

40 桁のハッシュ値

アルゴリズム バイト長 速度 ハッシュ値
sha1 20 Byte 0.348829 sec 5d8793ae d96d808a b6af8e47 5ce244e8
a604e478
tiger160,3 20 Byte 0.367638 sec 60bd4df9 e039716f 07c9ecd4 4c203d34
6f07e46a
tiger160,4 20 Byte 0.399170 sec 7c20d9b5 d9e79da7 b5241a08 a353018a
bf178a02
ripemd160 20 Byte 0.694799 sec 99a6c172 52ae4e64 e8d22853 c54ee2ad
44089160
haval160,3 20 Byte 0.900242 sec aba140dc e20ac7a2 615053de 4336e343
37a49b46
haval160,4 20 Byte 1.033398 sec 6bc4fecd c33d5d21 14c695ff f449d333
58f3030d
haval160,5 20 Byte 1.197252 sec d87a41cb 73469426 42faf2ae 7d62e81a
eba5dcc6

48 桁のハッシュ値

アルゴリズム バイト長 速度 ハッシュ値
tiger192,3 24 Byte 0.394713 sec 60bd4df9 e039716f 07c9ecd4 4c203d34
6f07e46a 9c308ef7
tiger192,4 24 Byte 0.410200 sec 7c20d9b5 d9e79da7 b5241a08 a353018a
bf178a02 0a74f3fb
haval192,3 24 Byte 0.874294 sec e2b0c018 6b1cc119 0eebe1be 9d61953d
2dd78ba4 8136086c
haval192,4 24 Byte 1.031765 sec 7540fa22 a5714124 cf942e1b 31a890b9
bb59d58c e5a61157
haval192,5 24 Byte 1.211350 sec e4a6b10a d8286eaf 8cb3f225 950c2f93
b6fdab8c 601626c8

56 桁のハッシュ値

アルゴリズム バイト長 速度 ハッシュ値
sha224 28 Byte 0.713225 sec d72d6ef7 0a788b3e 7f720b5d 88f20a13
bf161c31 b260fd34 6573094d
sha3-224 28 Byte 0.817025 sec e833eab3 4fbefbe8 9e44dcf1 d4ea9990
10981761 22f51708 df9cd9d0
sha512/224 28 Byte 0.825188 sec e205b15d 16eda0ce e195d210 73edca14
a69198e9 0070b9b0 09f7cb16
haval224,3 28 Byte 0.842655 sec a69049ca 88565098 a6f5e2bc adb22980
e59da983 9a779b63 c214e019
haval224,4 28 Byte 1.045480 sec 090b25d0 e8a0f5ef ecf6b683 5be72fe5
6913b34e 2d086922 3b1ac5d1
haval224,5 28 Byte 1.209415 sec 5343b4b1 a16119c5 dcd7726e 53128841
fecb7607 88e9008f 6c6f2cb6

64 桁のハッシュ値

アルゴリズム バイト長 速度 ハッシュ値
ripemd256 32 Byte 0.574046 sec e0fe9c49 b1a59fae 47096909 83e62829
4887b161 5722a62c 2c4187be 816b058d
sha256 32 Byte 0.668654 sec e863d36c 24ada694 fa77454b 33e8f9b9
545d372a ae251e87 79fc25df 16943fed
sha3-256 32 Byte 0.824698 sec cedaea23 33478d77 bc9ed3e3 3303f455
85af1917 4a451ce9 3029fedc dd4d1ecb
sha512/256 32 Byte 0.833001 sec aaa2e875 112de9b6 1744d4a0 ae757e40
cd12008a 0f3948fb 7c42a8cd 48c361b8
haval256,3 32 Byte 0.845439 sec 5f788c8a 5359387b acf7bf60 ff4dd08d
e7176205 a0aae1ce 4f485b40 126c0d2f
haval256,4 32 Byte 1.048196 sec 4ebb9e6f a6c045b0 cbba419e f06ac973
b2fd4914 f746e142 bb6b840f bd836158
haval256,5 32 Byte 1.218753 sec c99614ae a2985f43 f480d029 bcb7974b
f5aface5 8730c9d6 f3141a67 58270431
gost 32 Byte 1.828385 sec 667f4328 0ff9e0a5 9c15de57 022becf3
cd1a48f8 d37a165c 87576b6f 814fa482
gost-crypto 32 Byte 1.849877 sec 7ebf0f97 0f1246b6 aea110d7 32cbcdfd
b0169cf1 7336bae7 814e99f1 8abfbd21
snefru 32 Byte 2.841073 sec ad081810 0ab15234 b13b8d09 ad0c519a
35469221 adbf8c5f a71594ca f7dfddc2
snefru256 32 Byte 2.850217 sec ad081810 0ab15234 b13b8d09 ad0c519a
35469221 adbf8c5f a71594ca f7dfddc2

80 桁のハッシュ値

アルゴリズム バイト長 速度 ハッシュ値
ripemd320 40 Byte 0.725499 sec 6d152e32 fee2b979 024b8cff e416c898
16032680 779f7c3a 93c9aa26 35441245
8d4a9010 ad8fdfa5

96 桁のハッシュ値

アルゴリズム バイト長 速度 ハッシュ値
sha384 48 Byte 0.831855 sec b10497cf 49601678 4d8413a4 662983a8
dc4ac470 039ea755 d5ec985f 1aab04ee
26dc3d67 71bbe404 75ea7d13 5a97ba58
sha3-384 48 Byte 0.835068 sec e83e54ee 323dafb5 ca2d800f d479e1cc
94502362 93d5ad74 36228519 aa657ea3
d1da8bb6 2d07035d ec1ece2f 428ec8dc

128 桁のハッシュ値

アルゴリズム バイト長 速度 ハッシュ値
sha3-512 64 Byte 0.851400 sec 9d1aaed0 79bac194 6a5fbafb 4285ec5b
dcf0053a 9e005590 46884a14 8f28fcb9
02441b49 cb3a8277 5834a244 4dd183ed
a36cee90 0f5662f8 2353fae7 e7111740
sha512 64 Byte 0.860255 sec cac9036c 1dd3652f c550e99a 4ec2b066
d69d6a40 a369bc85 e3078960 e6f26012
4138f5d0 f4e9a6e0 47dfb833 c9dd9b33
76d02d49 be37de26 dd6234d4 e79cc09e
whirlpool 64 Byte 1.041927 sec 488c6cd6 eccb5348 8a7c7617 8c89d514
16b8eb2b 88a30b79 71f1f176 70e27659
fc477cd9 6ade86e4 b6176c5e f2f67068
89606786 4ce15443 eff90733 fd4fcf4c

TS; DR 最速のDBキー検索を求めて with SQLite3

ハッシュ値の衝突は別のアルゴリズムでは衝突しない (限りなく)

衝突のイメージ
// 値が微妙に異なる $a と $b
$a = 'xxxxxxxxx..1..xxxxxxxxx'; // 長ったらしい文字列 a
$b = 'xxxxxxxxx..0..xxxxxxxxx'; // 長ったらしい文字列 b

$result_sha1 = (hash('sha1', $a) === hash('sha1', $b));
$result_md5  = (hash('md5',  $a) === hash('md5',  $b));

 // $result_sha1 -> true, 偶然にも衝突が発生!
 // $result_md5  -> false, アルゴリズムが異なると衝突しない(可能性が高い)

古くはダウンロード・ページなどでファイルの改ざんや破損がないかを比べるのに使われていたり、身近なところではアクセス・トークンの作成、いつもお世話になっているパッケージマネージャーのパッケージ管理や、みんな大好き Git のコミットID にも使われている「ハッシュ関数」。

後述する、近年話題の IPFSブロックチェーンや、そのマッシュアップである NFT などではかなめの関数とも言えるなど、今後もさまざまな場面で活躍が期待される関数です。

この記事では、「ハッシュ関数の基本と基礎知識」、そして「ハッシュ関数を活用した SQLite3 の 1 つのアイデア」をシェアしたいと思います。

🐒   2021/02/19 追記: Qiita の Markdown の仕様変更により、今まで <details> タグで「必要な人だけみれる」ように隠していた基本的な情報も表に表示されています。そのため、やたら長い記事になっています。 🐒   2021/03/05 追記: Qiita の Markdown で、<details> タグの仕様変更は β 版の一時的なものだったらしいのですが、また再々編成するのも面倒なので、そのまま表示した状態にします。そのため、やたら長い記事のままになっています。目次を見て、ハッシュ関数の基本や活用方法は「完全に理解した」と感じた方は、本題の「長さを知ったところで何?」まで、スキップしてください。答えを先に言っちゃうと「データのハッシュ値 n 桁を SQLite3 の rowid に使う」って模索した時の話しです。

ハッシュ関数を完全に理解した気になるコマケーこと

ハッシュ関数の基本と特徴

先に、一言で恐れずに言うなら「ハッシュ値はデータの指紋」です。

人間の指紋が個人を識別するために使われるように、データの指紋(ハッシュ値)も特定のデータを識別するのに使われます。

指紋からは直接本人を特定できませんが、本人の指紋と比較したり、対応表さえあれば誰の指紋であるか特定できるのも同じです。

そして、同じ指紋を持つ 2 人は必ず 1 ペア以上いる(0 %ではない)ように、異なるデータなのに同じ指紋(ハッシュ値)を持つデータは必ず作れます。(簡単とは言ってない)

その「なんちゃって指紋」の精度が、アルゴリズムやハッシュ値の長さによって変わる謎の箱がハッシュ関数であると考えて良いと思います。

しかし、ハッシュ関数の基本を「正しく」知ろうと Wikipedia を開くも、何を言っているのかわかりません。

これは法律や音楽理論や機械学習などのドキュメントと同じように、「同じプロトコルの人向けのドキュメント」だからです。つまり、ハッシュ関数を正しく知ろうとすると、数学や暗号の基礎知識が必要なのです。

「変数」や「配列」と言う用語がわからないのにソート・アルゴリズムの説明を覗きに行ったり、メモリアドレスやポインタが理解できていないのに高速化ドキュメントを読んだり、ビットや XOR がわからないのに TCP や JPEG の仕様書を覗くようなものなのです。

偉そうにゆうて、筆者も数学や暗号学に強いわけではありません。

そこで、bash などを触ったり、自分で何かしらのプログラム言語で俺様関数を作ったことがあればわかるプログラマー的な表現方法で「知っておいた方が良いハッシュの基礎知識」を説明したいと思います。

なお、この記事には計算式やアルゴリズムの詳細はありません

あくまでも筆者が考える「ハッシュ関数の基礎きそ概論がいろん」的なものです。そのため、丁寧に説明しているつもりですが、いささかくどい・・・部分があります。

そのかわり、ジャンクフード的な記事らしく、ハッシュ関数が好きになる話題や実例をてんこ盛りにしています。

興味のあるキーワードが出て来たら自分なりに掘り下げて、より正確なものに堀り下げて欲しいと思います。キーワードの概要を理解した上で各種文献をご覧になると、より理解度が高まった、そんな記事になるといいなと思います。

そして間違いを見つけたら、戻ってきて、こっそりコメント欄に書いていただけると嬉しいです。

【余談】「ハッシュ」の語源を掘り下げる ハッシュ関数の「ハッシュ」は「hash」と書き、単純に日本語に訳すと「ごた混ぜ」「細切れ」「台無しにする」などの意味があります。しかし、その語源を辿ると面白いルーツわかります。 美術の古典技法で「hatch」という平行線で描画する技法[]があり、フランス語の「hach」から来ています。 諸説あるのですが、そこから「英国」英語では平行線で構成された「の字」や「の字」のような状態のものを hatch もしくは hash と呼ぶようになりました。「潜水艦のハッチを開ける」などの「ハッチ」も「の字型の出入り口」であることから来ています。(いまは丸型ですが) そして英国では電話の「」キーを「ハッシュ・キー」と呼ぶようになりました。これが現在の「ハッシュ・タグ」(ハッシュ記号 によるタグ付け)の語源です。そして肉やジャガイモなどを縦横に、どんどんカットしていき、細切れになったものを「ハッシュド(hashed)なんとか」と呼ぶようになったのです。 ちなみに「ミンチ肉」などの「ミンチ」は、ラテン語の「小ささ」の意である「minutia」が、フランスで「mincier」になり、英国の「mince」になったものです。「ふん」の minute がミンチ肉と同じ語源なのも面白いですね。

ハッシュ関数とは何か

何はともあれ、ハッシュ関数は、任意のデータを渡すと「ハッシュ値」と呼ばれる値が返ってくる関数のことです。

まぁ、そうですよね。でも「ただの関数である」という認識は意外に重要なのです。

機械学習などで「ニューラル・ネットワーク」とか見聞きして、「○」がたくさんの線でつながっている図を見て、怖いと感じた方もいると思います。

実は、あの「○」って関数やメソッド(クラス関数)のことなんです。そして、関数の出力を別の関数の引数に「配列で渡している」のが「線」なんです。そう考えながら見ると単純です。(簡単とは言ってない)

「ハッシュ関数」も、なんだかんだ言っても結局のところ「ただの関数」なのです。

「函数」つまり「引数が同じなら期待する値が出てくる謎のはこ」です。そして、その戻り値が「ハッシュ値なる謎の値である」と言うだけです。(「ハッシュ値」については後述します)

ほとんどのプログラム言語で「ハッシュ関数」は実装されていますが、使用できるアルゴリズムは環境によって異なります。標準ライブラリ(最初から同梱されているモジュールなど)に含まれているかに依存するからです。

一般的に「ハッシュ関数」と呼ばれる場合、ハッシュ関数には4つの大きな特徴があります。

同じ結果になる
アルゴリズムと引数が同じ場合は、同じハッシュ値が返ってくる。
予測が困難である
入力の規則性に対して出力に規則性がないため、ハッシュ値から元の値の予測は難しい。※1
逆算ができない
ハッシュ値から元の値(引数の値)は計算式による算出ができない。※1
同じ長さの値になる
ハッシュ値は固定長の数値で返ってくる(一般的に n 桁の HEX 文字列)※2

※1) 無限ループ(総当たり攻撃)による算出や辞書攻撃による予測の場合除く。また「暗号学的ハッシュを利用しない」アルゴリズムは、暗号学的ハッシュと比べ、より予測・衝突可能になります。衝突や暗号学的ハッシュに関しては後述します。

※2) 本記事未掲載である SHAKE256 などの一部のアルゴリズムでは戻り値が可変長になるものがあります。しかし、「引数が同じ場合は、戻り値も同じ」と言う点で、同じ引数であれば長さは同じものが返ってきます。

つまり、ユーザー目線だと「結果からオリジナルの予測が難しい」のと「同じ結果が得られる」のがハッシュ関数の一番の特徴です。

このハッシュ関数の戻り値である「ハッシュ値」を生成するには、本記事の一覧で紹介しているように、色々なアルゴリズムがあります。

各々異なった思想や目的で設計されていますが、いずれのアルゴリズムでも「引数が同じであれば戻り値も同じ」という特徴は変わりません。

ここで「ハッシュ関数のアルゴリズムとして CRC を含めるのは違うんジャマイカ」と言う方もいると思います。これは「CRC はチェック・サムみたいなものだから、ハッシュではないんジャメイカ🔈」と言う意見ですね。鋭い。

しかし、このタイミングでアルゴリズムの話しは、いささか勇み足なので、順を追って行きたいと思います。

ハッシュ値とは何か

さて、ハッシュ関数の戻り値である「ハッシュ値とは何か」の前に、以下の "beef" という文字列をハッシュ値にした例をご覧ください。

本記事で使用する言語は、bashPHP です。コマンドが 1 行でおさまると言うだけで選びました。

bashopenssl コマンド、PHP では hash() 関数を使っています。アルゴリズムは md5sha512 です。

ポイントは、bash php に限らず、どのプログラム言語を使っても「引数が同じ場合は結果も変わらない」「塩を 1 足すだけで結果が大きく変わる」ことに注目です。

ハッシュド・ビーフの例
引数が同じ(同じ具材)
$ # 粗挽き牛ミンチ
$ echo -n 'beef' | openssl md5
34902903de8d4fee8e6afe868982f0dd

$ # 粗挽き牛ミンチ(言語が違っても同じアルゴリズムと引数なら同じミンチ肉)
$ php -r 'echo hash("md5", "beef"), PHP_EOL;'
34902903de8d4fee8e6afe868982f0dd
具材を変えてみる
$ # ハッシュド・ポテト
$ echo -n 'poteto' | openssl md5
147f31c730caa77f8a3440e549264a2e

$ # トマト・ペースト
$ echo -n 'tomato' | openssl md5
006f87892f47ef9aa60fa5ed01a440fb
引数を少し変化させる(味付けしてみる)
$ # 粗挽き牛ミンチ + 1g の塩入り(beef1)
$ salt=1; echo -n 'beef'$salt | openssl md5
30017279d6a5bac241e764eeed261dd8

$ # 粗挽き牛ミンチ + 1g の塩入り(コックが違っても同じレシピなら同じ味)
$ php -r '$salt=1; echo hash("md5", "beef" . $salt), PHP_EOL;'
30017279d6a5bac241e764eeed261dd8
より細かいアルゴリズムに変えてみる
$ # 絹ごし牛ミンチ
$ echo -n 'beef' | openssl sha512
8cd8bb0cef938ef9cd054c2c2cb965e83310ab5c197cb5fc8f35892a44c1a028bac9e1bcd6248580fa2739cc96074885ea3ee116ef35c2d8f6124270aeff50b7

$ # 絹ごし牛ミンチ(コマンドの言語が違っても同じアルゴリズムと引数なら同じミンチ肉)
$ php -r 'echo hash("sha512", "beef"), PHP_EOL;'
8cd8bb0cef938ef9cd054c2c2cb965e83310ab5c197cb5fc8f35892a44c1a028bac9e1bcd6248580fa2739cc96074885ea3ee116ef35c2d8f6124270aeff50b7

$ # 絹ごし牛ミンチ + 1g の塩入り
$ salt=1; echo -n 'beef'$salt | openssl sha512
a528829f370819123ad3fb04d8066b77ec79ce6eddad07e5b2c925bbd9b2e699e73428d23315875c29b45500b8c767262cf5546e33974e4f7a6102abd1bb045e

$ # 絹ごし牛ミンチ + 1g の塩入り(コックが違っても同じレシピなら同じ味)
$ php -r '$salt=1; echo hash("sha512", "beef" . $salt), PHP_EOL;'
a528829f370819123ad3fb04d8066b77ec79ce6eddad07e5b2c925bbd9b2e699e73428d23315875c29b45500b8c767262cf5546e33974e4f7a6102abd1bb045e

beef の原型はありませんが、元は beef もしくは beef1 であることはハッシュ値から確認できそうです。

つまり、成分表(?)上は同じだが「原型を留めていない状態を数値の文字列にした値」がハッシュ値です。

ハッシュ関数のオプションによっては 16 進数の数値の文字列ではなく、バイナリとして取得できるものもありますが、いずれにしても数値として認識できる値で返ってきます。

ハッシュしたてのビーフはミミズにしか見えませんが、「覆水盆に返らず」でも「水である」ことはわかるようなイメージです。

そして、どのようにミンチ(ハッシュ)にするかが「アルゴリズム」になります。

カードをシャッフルするかのように何度も XOR をする物もあれば、データを 1 バイトずつ読み込みながらゴニョゴニョしたりと、どのアルゴリズムも使用目的や思想によって設計が異なります。

暗号学的ハッシュ関数とチェックサム的ハッシュ関数

ハッシュ関数によっては、暗号化にも使われているアルゴリズム考え方を利用しているものがあります。そのためか、ハッシュ関数を暗号の一種のように説明しているブログもありますが、違います

暗号は「可逆」、つまり元に戻せる(復号できる)とわかっているから暗号と呼ばれます。

反対にハッシュ関数は「非可逆」、つまり「元には戻せないことが特徴」であるため、ハッシュ化は暗号化ではありません

しかし、この違いは意外に重要なのです。

ハッシュ関数を知らないし興味もない相手に説明するのが大変面倒なため「暗号化の一種です」と言ってしまうものだから「ハッシュ値を復号したい」という人が後を断ちません。「ハッシュ化」=「暗号化 + 圧縮」と勘違いさせているパターンです。

また、「暗号学的ハッシュ関数」を説明する時に「暗号学的な特性をもたなければいけない」という言葉からも誤解が生まれているようです。「(ということは復号できるんだな)」と。

この言葉が意味することは、以下の条件に「暗号でも使われる考え方」(アルゴリズム)を利用しているだけのことです。

  • A → (処理) → B」としたとき
    1. A から B を作成したときは同じ結果でなくてはいけない」
    2. B から A がバレてはいけない」

このような「片方向の処理は簡単だが、逆方向は難しい」系の関数(AB は簡単だが BA は難しい値を返すもの)を One-Way 一方向性-Function関数 と言います。

例えば「素数を掛け算して自然数を返す」関数などがそうです。なぜなら逆の「自然数から素数を算出する」処理は大変だからです。そのため「一方向性関数」は暗号用途に限らないのですが、大半は暗号系の関数です。

この「ハッシュ関数が暗号の一種という誤解」に、翻訳の問題もあると思います。

暗号の論文をわからないながらも読むと "〜 by one-way encryption using hash ..." という言い方が多く出てきます。丁寧に訳すと「...の、復号が難しい暗号化を行うためにハッシュ値で〜する」という意味です。

しかし、理屈がわかっている人には長ったらしいため「一方向暗号をハッシュで行う」みたいに訳してしまうのだと思います。一方向性関数を理解していれば間違ってはいないとわかるのですが、「ハッシュ関数で一方向に暗号化する」と捉えてしまいそうです。(ました)

まとめると、ハッシュ関数のうち「暗号学的アルゴリズム」は、他のアルゴリズムと比べて「元の値を隠しつつも特定できること」を目的としたタイプと言えます。つまり、別のデータなのに同じハッシュ値にならないことを優先する場合に使われます。

逆に「暗号学的ハッシュ関数ではない・・もの」には CRCfnv などがあります。非可逆性や特定よりも「データが壊れていないかの確認」を目的としたタイプです。

破損チェック用の値はチェックサムとも呼ばれるのですが、学術的には CRC とチェックサムは別物です。各々のアルゴリズムが存在するからです。

しかし、実用面でチェックディジット的に使われる値全般を「チェックサム」と呼ぶことがあります。

チェックディジットというのは、例えば、バーコードの最後の 1 桁の数値(ディジット)などです。

バーコード・リーダーは、値を読み取ると「最後の 1 桁を除く値をゴニョゴニョと計算したら最後の 1 桁と同じになるか」と確認することで正常に読み取れたか確認しています。

この読み取りエラーを検知するのに使われる数値がチェックディジットです。そして、ハッシュ値を似たような目的のために使われる場合に「チェックサム」と呼ばれることがあります。

そのため、アルゴリズムとしての「チェックサム」と、用途としての「チェックサム」があることに注意します。この記事では CRC およびチェックサムの両アルゴリズムを「チェックサムアルゴリズム」と総称します。

なお、暗号学的アルゴリズムに比べ、チェックサム的アルゴリズムは速いものの、改竄かいざんに弱く、パターンが表れやすい傾向があります

特に改竄に対しては、とてつもなく弱いです。異なる値なのに簡単に衝突させる(同じハッシュ値にさせる)ことができてしまいます。結果、ダミーで差し込んだデータによってパターンが現れます。

これは、チェックサム的アルゴリズムが「たとえ演算結果から元のデータは逆算できなかったとしても、データの傾向が伺いやすい」と言うことです。

つまり、ハッシュ値のやりとりを傍受された場合に、内容は分からずとも「はは〜ん」と流れを読まれてしまう可能性がある、と言うことでもあります。

そのため、「流れてきたデータに問題はないか」の確認で、「破損チェック」にはチェックサム的アルゴリズムを使い、「改竄チェック」には暗号学的アルゴリズムを使うという適材適所の判断が必要になります。

とは言え「数マイクロ秒の差が売り上げに大きく影響する」など、よほどシビアな条件でない限り、暗号学的アルゴリズムを使うのがいいでしょう。暗号学的アルゴリズムはチェックサムとしても使えるからです。(逆はできない)

SHA-512 よりは SHA3-512 など、強めのアルゴリズムなら、なおベストです。処理時間などのコストが許す限り良いものを選びましょう。便利で丁度いいサイズの MD5 アルゴリズムを大事な局面で使っていると暗号警察がやってきますよ。

CRC をハッシュ関数のアルゴリズムに含める理由

この記事で CRC などのチェック・サム的アルゴリズムを、ハッシュ関数のアルゴリズムに含めた理由ですが、単純に List of Hash Functions に含まれており、たいていのプログラミング言語のハッシュ関数が使うモジュールに含まれているからです。

ここで先の「チェックサム的ハッシュ関数はハッシュと呼んでいいのか問題」が出てきます。つまり「CRC やチェックサムはハッシュではない」と言う話しです。

CRC が「ハッシュではない」と言われる主な理由に 2 つあります。

  1. CRC は多項式で足したり XOR しただけの値だから「予測困難」とは言えない。
  2. CRC は「誤り検出訂正」にも使えるので、元に戻せるから「逆算不可」とは言えない。

暗号学的ハッシュと比べパターンが現れやすいことから、最初の「予測困難とは言えない」はわかります。次に 2 の「誤り検出訂正に使える」ですが、「ん?訂正」と思われるかも知れません。

CRCCyclic Redundancy Check(巡回冗長検査)の略です。つまり Check(検査)とあるため、誤りを「検出」するためのもので「訂正」には使えないと重いコンダラ状態だったのですが、なんと訂正にも使えるそうです。

  • Bitfilters | Mathematics of Cyclic Redundancy Checks @ Wikipedia

しかし、これはデータを修復する時に CRC のアルゴリズム(考え方)が使えることがあるだけで、「CRC のアルゴリズムでハッシュ化する」のとは根本的に目的が違います。

🐒   ちなみに「誤り検出訂正」ですが、コンピュータでは データが壊れていた場合に自動修復する機能が、そこかしこで使われています。例えば CD や HDD の読み込みや通信のパケットなどです。英語なのですが、以下の動画が基本的な考え方をわかりやすく説明しています。 - Hamming codes and error correction | 3Blue1Brown @ YouToube(英語) - ハミング符号 @ Wikipedia(日本語)

そうすると、次に「いや、そもそもチェックサムなんだからハッシュとは言えない」と言う、最初の議論が出てきます。

これは「学術寄りの正しい目線」と「一般定義されたユーザ目線」の違いのようなものです。なぜなら、確かに厳密な意味では CRC の値はハッシュ値ではないからです。この議論は、海外の掲示板や SNS でもしばし見受けられます。

しかし、これはプログラムで言う「文字列データ」と「バイナリ・データ」の違いを「文字列だってバイナリだから」と言う議論や、「ランダムと言ってもランダムではない」と言った議論と似た性質を持っています。ユーザーと、内部(の仕組み)を知るものの間での食い違いです。

「ドローンの研究をしています」と言っているのに「ラジコンの研究をしてるんですって」とか言われたり、「モニタとにらめっこ」してるのに「テレビばかり見てる」と言われれば、正したくなると思います。どうやら、それくらいのモヤモヤ感がある違いなのです。

「ハッシュ関数」の定義

ここで、この記事における「ハッシュ関数」の定義を(いまさら)したいと思います。

A hash function is any function that can be used to map data of arbitrary size to fixed-size values.

Hash Function @ Wikipedia より)

【筆者訳】
ハッシュ関数は、任意のサイズのデータをマッピングして固定サイズの値として使用することができる関数のことを言います。

つまり、暗号学的なアルゴリズムであっても、チェックサム的なアルゴリズムであっても「その関数を通すと固定長で返ってくるもの」を、この記事ではハッシュ関数と呼んでいます。

ここまで読んで下さった上で、あえて言うと「風邪と言う病気がない」のと同じように「ハッシュと言うアルゴリズムはない」のです。そして、「その関数を通すと固定長で返ってくるもの」を「ハッシュ関数」と一括りにするのは、「症状だけでコロナを風邪と言っちゃう」のと同じくらい気をつけないといけないと言うことです。

「ハッシュ値」と「暗号」の関係

さて「ハッシュ化は暗号化ではない」とは言ったもののハッシュ値は暗号と密に関係しています。

これは、ハッシュ値は暗号データの担保情報としても使われるためです。特に暗号通信においては「切っても切れない関係」にあります公開鍵・秘密鍵暗号では、公開鍵を担保する情報としても使われるからです。

🐒 【余談】「公開鍵・秘密鍵暗号」とは  「公開鍵・秘密鍵暗号」とは、ペアとなる A と B の2つの鍵があり、片方の鍵で暗号化したものは、もう片方の鍵でしか復号できないタイプの暗号です。  つまり A 鍵 で暗号化したものは同じ A 鍵 では復号できません。ペアとなる B 鍵 でしか復号できません。また、その逆もしかり・・・です。  この特徴により、片方の鍵を公開しておき、その公開している鍵で相手に暗号化してもらえれば、もう片方の鍵を持つものでなければ復号できないデータが作れます。鍵を公開してるのに、安全に暗号通信やファイルのやりとりが行える魔法が使えます。鍵を公開してるのに、です。  ちなみに「鍵」とは、実質的に、いわゆるパスワードと同じ役割をするものです。ワード(単語)ではなく、覚えられないくらいの長い不規則な文字列、もしくはそれをファイルにしたものを「鍵」と呼びます。そして一般的なパスワードとの違いは自分で決められるものではないことです。伝わるかわかりませんが、「復活の呪文」をファイルに落としたようなものです。
しかし、本質的には「〜のカギとなる」や「キーポイント」のように「重要な部分を引き出すもの」を「KEY」と言います。配列の「キー」なども同様です。(具体的な鍵の例 @ GitHub)
 秘密鍵暗号で重要なのが A 鍵B 鍵 は「親」と「子」の 1:1 の関係になっていることです。「親の鍵」からは同じ「子の鍵」は何度でも作成できますが、その逆(子から親の鍵)は作成できません。  そのため「親」の鍵で暗号化したデータは同じ「親」の鍵では復号できませんが、復号に必要な「子」は作れてしまうということです。つまり、ユーザーは「親の鍵」さえ大切に保管しておけばよく、必要な時に「子の鍵」を作成し、外部に「子の鍵」を公開するのが一般的です。  このことから親の鍵を「秘密鍵」、子となる鍵を「公開鍵」と呼びます。秘密鍵は「シークレット・キーSecret Key」もしくは「プライベート・キーPrivate Key」、そして公開鍵は「パブリック・キーPublic Key」とも呼ばれます。  また、「公開鍵で暗号化」し「秘密鍵で復号する」といった説明の記事が多いのですが、どちらの鍵でも暗号化できますし、反対の鍵で復号できます  この2つの鍵ですが、一般的(?)な方法として素数の概念が活用されています。  例えば、自然数 15 を素因数分解すると 3 と 5 です。しかし、3 という数からは 15 はわかりません。3 を素数とする自然数は無限にあるからです。また、同様に 5 からも 15 はわかりませんが、3 と 5 からは 15 が簡単にわかったり、15 と 3 からは 5 が作成できるような考え方から、さらに工夫されています。もちろん他のアルゴリズムもあり、どれも難しすぎてわかりません。  しかし、「公開鍵・秘密鍵暗号」は欠点も持っています。「大きなデータの暗号化が苦手」なのと「遅い」ことです。特に大きなデータを暗号化する場合は、データをチャンク(ぶつ切り)にしてから各々を個別に暗号化して 1 つにくっ付ける必要があり、復号も逆の手順が必要であるため結構なコストが発生します。サイズも必要以上に大きくなります。  逆に従来の1つのパスワード(鍵)で暗号化および復号できる暗号方式を「共通鍵暗号」と呼びます。決して「共通鍵暗号」がオワコンと言うわけではなく、「共通鍵暗号」は強いアルゴリズムでも処理速度が速く「公開鍵・秘密鍵暗号」と比べデータサイズが小さいという特徴があります。現在では、大きなファイルや復号に速度が求められる場合は「共通鍵暗号」で暗号化し、その「共通鍵を、公開鍵・秘密鍵暗号でやりとりする」というハイブリッドな手法が多くとられます。 暗号の話し自体は、この記事のスコープ(範囲)から外れるため、興味を持たれた方は以下の記事が勉強になります。 - 2つの公開鍵暗号(公開鍵暗号の基礎知識) @ Qiita

このハッシュ関数の「非可逆」な特徴は、一般的に「パスワードの保存」などに使われます。特に「パスワードはサーバーに保存しておきたくない」が「パスワードが登録したものと同じか確認したい」という、覚えたくないけど答えられるようになりたい、みたいなわがままです。

具体的には「パスワードをハッシュ化して保存する」ことで可能です。パスワードが正しいかの確認はハッシュ値を比較すれば良く、「ハッシュ値が流出したとしても元のパスワードはわからない」だけでなく「管理者すら元のパスワードはわからない」といったメリットがあるからです。パスワード流出事件があると「自分たちでもわからない状態で保存されているから云々うんぬん」という話しがでるのもこのためです。

しかし、単純にハッシュ化したからといって安心できません

まず、ハッシュ関数のアルゴリズムに CRC 系やチェックサム系を使ってしまうと、簡単に衝突する(異なるパスワードなのに同じハッシュ値になりやすい)だけでなく、わざと衝突させて改竄する攻撃にまったく耐性がありません。

そのため、後述する salt(塩)を使ったテクニックも役に立ちません。(しかし、CRC や checksum は改竄耐性がない以前に、そもそも用途が違います)

次に、「鳩の巣原理」という「鳩の巣箱が鳩の数より少ない場合は、必ず 1 つ以上の巣箱で衝突する」原理があります。椅子取りゲーム的なものです。

つまり、ハッシュ値のビット長が短かいほど、同じ原理で衝突しやすくなります。

では、ハッシュ値のビット長が長ければ安心かと言うと、暗号学的ハッシュ関数を使ったからといって安心できません

「引数が同じ場合は戻り値も同じ」という、もう1つの特徴により流出したデータがハッシュ化されていても意味をなさないことがあるからです。

具体的には、別途パスワード・リストなどがあった場合です。なぜならパスワード・リストからパスワードをハッシュ化して同じ値を探せばいいからです。つまり「辞書攻撃が使える」ということにもなります。

ハッシュしただけでは味気ないので塩を足そう

さて、ハッシュ関数や暗号関数を触っていくと「salt」という言葉が出てきます。一般的に「ソルト」(英語でソルト、ラテン語圏ではサルト)と発音し、日本語で「塩」のことです。

これは、各々のデータに加えるランダムな数値や文字列のことです。先の例で言えば beef に加えた salt=1 です。

料理でいう「塩加減」のように「同じ具材でも塩の加減1つで味が変わるため、毎回調整が必要で加減も秘伝hidden」と言ったイメージが近いのですが、「塩土化」、つまり「戦時中の敵国が占領地の土地に塩を撒いて使えなくする」から来ている説もあるようです。

これまでの例のように、salt の値は「データの前」もしくは「データの後ろ」につなげてハッシュ化する方法によく使われます。

$a = hash( 'md5', $data . $salt); // 後から塩を足す
$b = hash( 'md5', $salt . $data); // 先に塩を足す
bashでの例
salt=1
data='beef'

# 先に塩を足す
hash_prepend_salt=$(echo -n "${salt}${data}" | openssl md5)
echo $hash_prepend_salt; # b14ab03be97e0b8deb2fa930cfdd4f4a

# 後から塩を足す
hash_append_salt=$(echo -n "${data}${salt}" | openssl md5)
echo $hash_append_salt;  # 30017279d6a5bac241e764eeed261dd8

上記のように、前後の salt を入れ替えるだけでハッシュ結果が大きく異なります。

では、前に足すか、後ろに足すか、どちらのパターンが良いのでしょう。

塩は後から足そう

料理の場合、味を見て後から塩を足すのが基本であるように、単純に salt をデータに足す場合も、後から足すようにしましょう。

$a = hash( 'md5', $data . $salt); // 👍 ベター
$b = hash( 'md5', $salt . $data); // 👎 問題あり

これは、Length extension attack(「伸長攻撃」)と呼ばれるハッシュ値の衝突攻撃に弱いからです。

特に、MD5, SHA-1 や SHA-2 などの Merkle–Damgård と呼ばれる構造を使うハッシュ関数の場合についてまわります。発音は「マークル・ダンガード」のようです。ヒーロー・ロボットのような名前ですが、ブロック・チェーンに興味のある方は、この名前と salt を覚えておいてください。後から出てきます。

さて、この「伸長攻撃」攻撃を恐れずに短く説明すると以下の通りになると思います。

Y = hash( salt . X )XY がわかっている場合、salt の長さがわかれば salt が逆算できなくても Y = hash( salt . X . Z) の計算ができる。(. は文字列の結合子)

そのため Z に良しからぬ文字列を入れて Y の値を同じにすることができる可能性がある。

逆に Y = hash( X . salt) と後に付け加える場合は、この攻撃を回避できるので、「味付け(salt を加えるの)は後から行う」と覚えておきましょう。

塩だけでなく胡椒も足そう

この「salt」(塩)は基本的に個々のデータに加えるのですが、DB の場合、全体に加える「pepper」(胡椒)と呼ばれる値もあります。

例えば、下記はプレーンな(加工や手を加えていないの状態の)パスワード情報です。偶然にも user1user2 のパスワードが同じです。

ユーザ名 パスワード
user1 passw0rdA
user2 passw0rdA

上記だと流出時にバレバレなので、次のような処理をします。

passwdとsaltとpepperの文字列変数をつなげてMD5でハッシュ化する例
$passwd_hashed = md5($passwd . $salt . $pepper);

スクリーンショット 2019-09-08 22.46.20.png

DB の保存で考えると、定数に pepper='pepperA' と設定しておき、テーブルは以下のようなイメージになります。

ユーザ名 パスワード
user1 7915e17989dcbb1d2132c1d207ef9e1d
user2 5ee508cb664f91000826933e626cd5df
ユーザ名 ソルト
user1 saltA
user2 saltB

DB ファイル自体が流出したらテーブルをわけても同じことであるため、パスワードとソルトを同じテーブルに格納する場合もあります。どこに格納するかは運用の考え方しだいだと思います。

また、実際には以下のように、より複雑にシェイクします。

  1. "saltA" などの単純な文字列でなくランダムな数値や文字列を使う
  2. アルゴリズムを sha256sha512 などのより複雑なアルゴリズムを使う
  3. hash('sha256', hash('sha256', $value))二重・三重にハッシュ化させたりする(時に数万回)

🐒   3 番目のループですが「Key stretching」(ストレッチング)と呼ばれる「総当たり攻撃対策」の 1 つです。一言で説明すると「1 回の処理に手間をかけさせる」対策です。
主にローカルでの総当たり攻撃の対策で、1 つの値を確認するのにループで手間をかけさせて衝突を見つけるまでの時間を劇的に伸ばす(ストレッチする)と言う手法です。他にも、サーバ側で行うストレッチングには「遅延」があります。例えば、リクエストを受けてハッシュ値を確認する際のタイミングに、わざと sleep を入れて遅延させ、「リトライ回数の制限」と組み合わせることで 1 回の攻撃に手間をかけさせることで総当たり攻撃をし辛くさせます。

とりあえず、どのアルゴリズムにするか悩んだら、2020/10 現在、OS やプログラム言語間で互換性が高く一番強いハッシュ・アルゴリズムは「SHA3-512」だと思われます。(後述の「ハッシュ関数の衝突(コリジョン)とセキュリティ」参照)

しかし、強い(複雑さが増す)アルゴリズムほど処理速度やレスポンスの問題も出て来ます。どの程度 複雑化させるのかも運用の考え方しだいになると思います。予算、運用コスト(計算コスト)や UX と相談しながら、強いものから低い方へ測定しながら検討してください。(「憶測するな、測定せよ」です)

いずれにしても、引数に $salt$pepper およびハッシュ化のループ回数という絶対公開しない値を引数に加えることで、予測を難しくさせているのです。

もちろん salt 値や pepper 値が流出してしまうと意味がありません。シオシオのパーです。つまり、秘密鍵と同じくらい扱いには気をつけないといけないので、「ハッシュ化しても安心できない」とわかると思います。

ところが、せっかく塩・胡椒をして独自の味付けをしたのに「同じ味や歯ごたえなのに実は合成肉だった」みたいな、なりすましが発生するご時世になってきました。

詳しくは後述の「MD5SHA-1 のセキュリティについて」でも説明しますが、塩・胡椒しただけの粗挽き肉ではグルメセキュリティ重視の人を唸らせることは難しくなってきているのです。

ハッシュ関数はセキュリティ用途だけではない

さて、ここまではパスワードの保存に関する話がメインでした。しかし、本記事はセキュリティのための記事ではありません。あくまでもハッシュ関数の基礎知識と「活用」に関する記事です。

「安全なパスワード保存」にハッシュ値を使いたいのであれば、パスワード管理専用の関数やフレームワークが各々のプログラム言語には数多くあります。一般的にハッシュ値をパスワード管理に特化したものを「パスワード・ハッシュ」と呼びます。

自分で実装するよりは、それらを利用した方がらくだし、何より安全です。例えば PHP の場合であれば password_hash() という、まんま・・・の関数があります。

先の「ストレッチング」のように「パスワード・ハッシュ」は計算のしづらさ(面倒くささ)に重点をおいているので、速度の速さと強度が重視される「ハッシュ関数」とは目的が違います。

2021/03/01 現在、最強のパスワード・ハッシュは Argon2 と思われます。2013 から 2015 にかけて行われた PCH というパスワード・ハッシュの競技会で優勝したのが Argon2 だからです。

Argon2 には大きく 2 つあり、処理時間やハードの電圧など物理的に観察して情報を盗むサイドチャンネル攻撃に耐性がある Argon2i と、GPU 攻撃に強い耐性がある Argon2d を持ったアルゴリズムです。例えば PHP 7.3 以降では両方に対応した PASSWORD_ARGON2ID が使えます。(オンラインで動作をみる @ paiza.IO)

セキュリティが心配でハッシュ関数を勉強に来られた方は、かの Web セキュリティのバイブルとも言える「徳丸本」で有名な徳丸先生の動画チャンネルを入り口としてご覧になることをお勧めいたします。その上でバイブルの1冊くらいは持っておくと良いと思います。

データの「指紋」としてハッシュ値を使う

ハッシュ関数はセキュリティ用途ばかりがクローズアップされますが、「処理」に目を向けると「数値で返ってくる」という特徴はデータの管理に活かすことができます

ハッシュ値の王道の使い方は「変更の検知」です。1バイトどころか1ビットでも違いがあるとハッシュ値の結果は大きく変化します。この特徴により、大量の文書(データ)であっても1文字の変化を検知できるのです。(変化した場所の特定は別の話し)

この「本編を詳細に見なくてもザッと見るだけで把握できる」的な意味で「ハッシュ値」を「ダイジェスト値」もしくは「メッセージ・ダイジェスト」と呼ぶこともあります。また「ハッシュ関数」は「要約関数」とも呼ばれますが、個人的に「『要するに...』と言われても、まったく意味がわからないのと似た関数」だと思っています。

むしろ、海外ドラマなどの冒頭で流れる「前回までのなんとか」のダイジェストのように「以前が何であったか、わかっている人にしか伝わらない確認をするためのもの」といったイメージです。

🐒 「ハッシュ値」「メッセージ・ダイジェスト」どちらも同じものですが、暗号関連などの確認に使う場合に「ダイジェスト値」と呼ぶことが多い気がします。この記事では「ハッシュ関数」の値という意味で「ハッシュ値」と統一します。

「データに変更がないか」の、最も一般的なハッシュ値の活用方法は、おそらくダウンロード・ファイルの確認でしょう。

ZIP や ISO といった巨大なアーカイブ・ファイル(複数ファイルを1つにまとめたファイル)をダウンロードする際に、リンクと一緒にファイルのハッシュ値が添えてある、アレです。ダウンロードしたファイルのハッシュ値と比べることで、破損もしくは改ざんされていないことが確認できます。

逆に言えば、「ハッシュ値が同じであれば、データに変更はない」という使い方でデータの管理にも利用できます。

みんな大好き git などは、ファイルの diff のハッシュ値を比較して変更があったかを検知していたり、いつもお世話になっているアプリやライブラリなどのパッケージマネージャーも競合や改ざんを防ぎつつ共通の動作をさせるために ライブラリ名<ハッシュ値> のような形式で内部管理していたりします。

他にも BitTorrent(P2P 型ファイル転送システム)や、後述する IPFS(P2P 型分散ファイルシステム)などは、ファイルのハッシュ値を使うことで、ネットワーク上に同名のファイルがあっても、個別に認識できるようになっています。

身近なところでは、Web サーバーなどに画像やファイルがアップロードされた際、既に同じものがあるかをファイルのハッシュ値で確認をしたりもできます。

このように「ファイル名が異なっていても、中身が同じファイルであった場合はハッシュ値は同じ」ということを、逆手に利用したデータの管理方法に使えます。そのため、ファイルの中身を特定する目的で作成されたハッシュ値を「フィンガー・プリント」(指紋)と呼ぶこともあります。

ハッシュ関数がセキュリティ目的が多いのは、指紋と同じ目的で識別 ID として使えるからなのです。

預言者の予言を担保する(当たるとは言ってない)

さて、この「ハッシュ値が同じならデータに変更はない」仕組みをさらに工夫すると、俺様電子証明書が作れます。

どういう事かと言うと、「ハッシュ値」と「公開鍵・秘密鍵暗号」を組み合わせることで簡易的な電子証明書が作成できるのです。つまり「内容が本物である」ことを証明できるのです。(内容が信用できるとは言ってない)

具体的に言うと、ファイルのハッシュ値を自分の「秘密」鍵で暗号化して公開すれば、それが俺様電子証明書になるのです。

  1. 自分が正しいと認めたファイルのハッシュ値を自分の「秘密鍵」で暗号化し、それを証明書としてファイルと一緒に公開し(相手に渡し)ます。
  2. 相手は、そのペアとなる「公開鍵」で証明書を復号して対象のファイルのハッシュ値と比較します。
  3. 同じハッシュ値であれば、相手は「自分が認めたファイルである」ことが確認できます。

これは秘密鍵の「片方の鍵で暗号化したものは、もう片方の鍵でしか復号できない」という特徴を活かした手法です。

ここで「別にハッシュ値じゃなくてもファイル自体を秘密鍵で暗号化すれば、(復号できたら)それ自体が証明書になるじゃないか」とお気づきかもしれません。鋭い。

電子証明書は「本物であることが証明できればいい」ので様々な手法があります。データサイズを小さくできるという点がハッシュ値を使うメリットです。

しかし、この方法だと、復号・ハッシュ計算・照合と、いささか手間が発生します。また、少ないファイルを確認するぶんには問題ないのですが、大容量で大量の数の処理をする場合には、この手法はボトルネックになります

そこで、ちまちま暗号化せずに「対象のファイルと片方の鍵をセットでハッシュ化したもの」を署名(サイン)とし、もう片方の鍵で検証する「1 発で両方美味しい」シュノア署名と呼ばれるシンプル・効率的かつ堅牢な手法が主流です。

秘密鍵による署名では RSA 署名が有名ですが、最近は Ed25519 が主流になりつつあるようです。

いずれにしても、秘密鍵をベースに作成され、不特定多数が公開鍵で確実に確認できれば、何だって署名(サイン)となります。あとはプロトコル双方の合意の問題です。

署名の例として、GitHub などのリポジトリや、OS などのリリースページで、リリースされたファイルと共に *.sha256 *.sha256.sig といったファイルがあったりしますが、それらです。

*.sig 以外の拡張子もあり得ますが、これはリポジトリ・オーナーが「対象のファイルが正式なものであるとサイン(署名、signサイン)した」という意味で、*.sig ファイルが捺印のような役割を持ちます。そして、捺印と判子を透かして照会する役割をするのがリポジトリ・オーナーの公開鍵です。

もちろんサイン(*.sig)があっても、盲判、俗に言う「めくら印」である可能性もあるため、必ずしも「安全である」とは言えないことを念頭に置きましょう。

しかし、著者自身がサインをする(証明書を置いておく)ことは重要です。

以下が署名の仕方と検証の例です。*.sha256 が各ファイルの(SHA2の 256,SHA256 による)ハッシュ値一覧で *.sha256.sig がその署名ファイルです。

$ # ハッシュ値の算出
$ openssl dgst -sha256 sample.txt >sample.hash

$ # 「秘密」鍵で署名(sign, signature)
$ openssl rsautl -sign -inkey privatekey.pem -keyform PEM -in sample.hash >sample.sig

$ # 「公開」鍵で検証(verify)
$ openssl rsautl -verify -inkey publickey.pem -pubin -keyform PEM -in sample.sig

🐒 上記で sample.txt から直接署名を作成せず、ハッシュ値のファイル sample.hash を署名している理由ですが、対象のファイルが複数あり、サイズが大きい場合の手法の 1 つです。 もちろん対象のファイルが 1 つの場合は、直接そのファイルを署名した方が本当は効率的です。 しかし、ファイルサイズが大きく大量にある場合に、各々署名するのも面倒ですが、検証側の計算量も多くなってしまいます。そこで、各々のファイルのハッシュ値を 1 つのファイルに記録しておき、そのファイルを署名すれば、すべてのハッシュ値も署名されたことになります。 ファイルのハッシュ値の計算は署名の検証より計算コストが低いので、各々のファイルに対してハッシュ値の確認を行うことで、トータルとして計算コストを下げられます。

いずれの方法でも、このような、「暗号鍵のペアの作成」「証明書の作成」「暗号の復号および検証」といった一連の仕組みを総合して「デジタル署名」と呼びます。証明書の作成は、これらの応用でしかありません。

デジタル署名の面白い使い方としては「予言の書」などがあります。

事前に予言と予言した日付を書いておき、「秘密」鍵で暗号化したその予言(ファイル)と、その電子証明書を同時に公開します。そして予言後に「公開」鍵を公開するなどです。まぁ、予言なので普通に公開しちゃっても良いんですけど。

このように、デジタル署名は難しいものではありません。

ファイルを秘密鍵で署名して、公開鍵を公式な場所に公開すれば、何にでも「公式なもの」として示せます。

デジタル作品の作家の方には、自身を守るためにも、ぜひ覚えてもらいたい仕組みです。

肥大化しないパターン ID

「引数がどれだけ長くても、ハッシュ値は固定長の数値」であることもメリットです。つまり、データがそれ以上増えないということです。

例えば、Web サイトのページ遷移せんいのパターンを固定長の ID にすることもできます。

ページせん移をID化する
$list_url_visited=[
  'http://hoge.com/p1',
  'http://hoge.com/p6',
  'http://hoge.com/p4',
  ...
];

asort($list_url_visited); //配列をソート
$string     = implode(' ', $list_url_visited); //配列を文字列に結合
$id_visited = hash('md5', $string); //文字列をハッシュ化

この行動パターンに固定長の ID を振れるメリットは機械学習などにも応用できます。

身近なところでは、リンクを開こうとして URL を見るとやたらとハッシュ値っぽいものがあるのを見たことがあると思いますが、アレです。

なぜなら、ハッシュ値は数値なので機械学習における「離散値」の特徴量としても使えるからです。

🐒   機械学習における「離散値」を簡単に説明すると、数値の大きい小さいに意味がないものや、数値と数値の差に関係がないものです。「リンゴは 1」「ミカンは 2」といった、特徴に ID 番号を振った数値のようなものです。

もちろんページ遷移だけでなく、5x5 ピクセルや 10,000x10,000 ピクセルといった、どんなサイズのピクセル・データにも固定長の ID を振ることもできます。

つまり、ハッシュ関数の特徴をよく理解すれば、アイデア次第でさまざまな活用方法がある関数でもあるのです。

そのハッシュ関数やハッシュ値の活用方法の例として「IPFS」と「ブロックチェーン」そして「NFT」をあげたいと思います。

ハッシュ関数と次世代ファイルシステム IPFS の関係

IPFS と言う用語を耳にしたことはあるでしょうか。以前から存在しているのですが、2020 〜 2021 年にかけて色々な理由で話題になっているものです。

一言で説明すると「惑星・・規模の分散型ファイル・システム」で、InterPlanetary File System の略です。

とても野心的な名前ですし、説明にもなっていませんが、内容はシンプルです。

従来のファイル・システムは「場所」を指定してコンテンツを取得していたのに対し、IPFS は「内容」を指定してコンテンツを取得するファイル・システム。

つまり「URL」や「ファイルのパス」を指定していたものが、「ハッシュ値」を指定してデータを取得するのです。

詳しくは後述しますが、イメージとして、世界規模で 1 つの共有フォルダを P2P でシェアして、ファイルのハッシュ値をファイル名にして突っ込む感じです。(あくまでも使い勝手のイメージ)

BitTorrentgit をご存知であれば、「リポジトリを P2P でシェアする」と言えばピンと来ると思います。

もう少し噛み砕いて言うと、「P2P 型を応用した分散システム上で、ファイルのハッシュ値をファイルの ID にしてファイルを共有する」ことで全体を 1 つのファイル・システムとして使う。そして「ユーザがファイルをリクエストしたらリポジトリにキャッシュして自分も共有する」と言うアイデアです。

いささか噛み砕き過ぎて、喉に詰まってしまいそうです。ゆっくり咀嚼そしゃくして行きましょう。

具体的な使い方は後述しますが、まずは同じ「ハッシュ値をベースにしたリポジトリ」同士である gitIPFS の共通点と違いを理解しましょう。

gitIPFS の相違点

git の場合、addcommit コマンドでファイルを登録すると、その版のハッシュ値(コミット ID、CID)が作成されます。また push すると登録したファイルが git リポジトリのレジストリ(GitHub など)に反映・公開(シェア)されます。そして、他のユーザは、その CID(コミット ID)を叩けば同じ版を確認することができます。

IPFS の場合も似ており、ファイルを add するとファイルがローカルのリポジトリに登録されハッシュ値(コンテンツ ID、CID)が作成されます。また name publish すると IPFS ネットワークに CID が公開(シェア)されます。そして、他のユーザは、その CID(コンテンツ ID)を叩けば同じ版のファイルを確認することができます。

コミット ID もコンテンツ ID も、同じ CID と略されるのは偶然です。

🐒   BitTorrent で言うと、`add` そして `name publish` した自分が「シーダー」となります。
BitTorrent の「シーダー」というのは、ファイルの全てのパーツを持っているピアのことを言います。というのも BitTorrent や IPFS は、ファイルが大きい場合 TCP/IP などのパケットようにデータを小さなパーツに分けて共有されます。これにより、ファイル全体を 1 つのピアから受け取らずに複数のピアから受け取れるため負荷分散できます。そして、すべてかき集めて完成したファイルを「シード」(種)といい、このファイルを共有しているピアを BitTorrent では「シーダー」と呼びます。
ちなみに P2PPeer To Peer)などの「ピア」とは、サービスを利用 & 提供しているコンピュータのことで、1 台で「サーバー」であり「クライアント」でもあるものを言います。類似用語に「ノード」がありますが、「ピア」も「ノード」も同じです。違いは、ピアが他のピアからリクエストを受けた場合、つまりサービスを提供する(サーバ)状態のピアを「ノード」と言います。

さて、この時の gitIPFS の違いは、受け取った CID のコンテンツがローカルにない場合の動きです。

git は相手が pull もしくは fetch などでローカルを同期しておかないとコミット ID を受け取っても確認できないのに対し、IPFS の場合は CID を叩いてローカルに該当するファイルがない場合は IPFS ネットワーク上の他のピア(IPFS ノード)に問い合わせてローカルにキャッシュすることで確認できるようになります。

この時の「中間のピア」、つまりリクエストしたピアと、該当する CID のファイルを持っていたピアの「間にいる他のピア」の動きですが、同じ動きをします。「ローカルになかったら他のピアに問い合わせる」です。

  1. リクエストされた CID のファイル、もしくはその一部がキャッシュにある場合はリクエストしてきたピアにデータを渡す。
  2. キャッシュにファイル、もしくはその一部がない場合は、さらに他のピアに問い合わせる。
  3. 見つけたらキャッシュして、リクエストしてきたピアにデータを渡す。

上記で「その一部が」というのは、ファイルが大きい場合は小さく分割されて管理されるからです。

BitTorrent でいう「リーチャー」(未完成のファイル、もしくは完成まであと一歩のリーチのかかったファイルを持っているピア)みたいなイメージです。

これにより「参照頻度の高いファイル」もしくは「その断片」は色々なピアにキャッシュされるため、総合的にダウンロードが速くなります。逆に「参照頻度の低いファイル」の場合、探し出すのに時間がかかります。ここらへんの動きも BitTorrent などと同じ感覚です。

そうなると、自分のピア(IPFS ノード)のキャッシュが「どの程度ストレージを圧迫するか」が気になります。

キャッシュ・ファイルの容量

基本的に IPFS は、IPFS リポジトリのあるローカル・ドライブ(パーティション)の空きがなくなるまでキャッシュされます。容量が、いっぱいになると、古くて参照頻度の低いキャッシュを削除していきます。macOS でいう TimeMachine と同じ考えです。

そして、このような Winny 時代にも問題でもあった「肥大化するローカル・キャッシュ」に対してはガベージコレクションというオプション(--enable-gc)が用意されています。

IPFS デーモン(サービス)起動時にガベージコレクションを定期的に走らせる設定をするとリポジトリの使われないキャッシュは、デフォルトで 90 GB をトリガーに 1 時間おきに参照されないもの順に削除され自然淘汰されます。

また、BitTorrent で言う「シーダーになりたい」つまり「永続的にキープ(提供)したいデータはリポジトリにコミット(add)する」と言う考え方です。具体的には、リポジトリに add して name publish します。(データが同じなので add しても CID は変わりません)

このように、恐れずに言ってしまえば IPFS は BitTorrent と git を足したようなものを公開専用のファイル置き場にしたものです。

コンテンツ ID(CID)は git で言うコミット・ハッシュや、Docker で言うレイヤーのハッシュと何ら変わりはありませんし、それらのリポジトリやレジストリを P2P で 1 つにしたようなものです。

じゃぁ BitTorrent と git でいいじゃん

良いと思います。しかし、IPFS の目指すところは「WEB(http/https)の代替となる次世代公開文書のプロトコル」と、名前だけでなく内容も野心的です。

  • 「みんなで共有すれば Web サーバいらないじゃん」
  • コンテンツの ID === hash(コンテンツの中身) なので改竄の心配ないじゃん」
  • 「誰かのマシンにデータがあれば、消えることないじゃん」
  • https と同じようにコンテンツを暗号化しておけば公開ネットワークでもいいじゃん」

と、現在の Web サイトやインターネットの公開情報が持つ問題(例えばデータ改竄や DNS 改竄など)を、「ファイルのハッシュ値を使う」と言う、シンプルかつ大胆な新世代の情報公開ネットワークを作ろうと言うものです。

IPFS と、その他のプロトコルの違い

Web における HTTP などの、従来のプロトコルと IPFS が根本的に違うのがコンテンツを取得する概念です。

  1. Web(HTTP)の場合は、コンテンツの場所を指定してコンテンツを取得する。
    つまり「どこ」から取得するかが重要になります。
  2. IPFS の場合は、コンテンツの中身(ハッシュ値)を指定してコンテンツを取得する。
    つまり「なに」を取得するかが重要になります。

もちろん、この IPFS プロトコル(仕様)以外にも HyperCore プロトコルICN など、似たアイデアはあり、多数存在します。

しかし、IPFS は Wikipedia が不当な検閲の回避に使ったり、Brave ブラウザが標準で IPFS プロトコルが使えるようになったり、Android 版 Opera ブラウザも標準でサポートしているなど、注目を浴びています。

何より 👌予算 の使い方が上手く、issue やドキュメント作成に対して懸賞金をかけることでコミッターに還元したりしているので、他のプロトコルよりドキュメントが整っていて使いやすい印象を受けます。

そのため、数あるコンテナ技術のうち Docker が一強になったように、公開分散ファイルシステムの Docker 的なメジャーなものになりつつあります。(たぶん。知らんけど。)

つまり、今後はブラウザのアドレスに ipfs://<IPFSハッシュ値> と打てば、このハッシュ値のファイルを持った最寄りのノード(ipfs を立ち上げているマシン)から取得されるようになるのです。このファイルが HTML の場合は静的 Web サイトが表示され、ZIP などのアーカイブの場合はダウンロードが始まると言うことです。

実際に 2021/05/20 現在の時点で Brave ブラウザやモバイル版 Opera ブラウザは標準で実装済みで、Chrome・Firefox・Edge は拡張機能/アドオンをインストールすることで使えるようになります。

  • IPFS の URI 例:
    • ipfs://QmSuyo747aBeA4yzXy354VUH3Z3pUBC3rULAQ5oF62fy5B (Brave などの対応ブラウザで開いて見てください)

IPFS の使い勝手

さて、ここからが Qiita 的に IPFS の真骨頂です。つまり「IPFS の使いやすさは、いかほどのものか」というところです。

ipfs は Go 言語で書かれているので、ビルドされたバイナリは単体のプログラムとして動きます。つまり、使うのにアレコレとインストールする必要がないのです。

ipfs.exeipfs のバイナリをパスが通った先に設置するだけです。

もちろん brewchoco などのパッケージマネージャー経由でインストールも可能ですし、CLI が苦手なら IPFS のデスクトップ版もあります

CLI 版であれば、環境にあったバイナリをダウンロードしてパスを通せば、以下のようにコマンド・ラインで使えます。CLI 版の使い勝手ですが、git に似ているものの git より直感的なので、おそらく「え?これで動くの?」と思うことでしょう。

IPFSコマンドの利用例
$ ipfs --version
ipfs version 0.7.0

$ # ipfs リポジトリの初期化。通常 ~/.ipfs に作成される。(専用の秘密鍵&公開鍵、リクエストしたファイルのキャッシュなどの置き場)
$ ipfs init

$ # ipfs デーモン(同期機能)の起動。バックグラウンド実行とログ出力付き。これで P2P の 1 つのピアとして起動する。
$ ipfs daemon > ipfs.log &

$ # ipfs ネットワーク上もしくはリポジトリ上にあるファイルを開く。ネットワーク上にあった場合は、リポジトリにキャッシュする。
$ ipfs cat QmcbMZW8hcd46AfUsJUxQYTanHYDpeUq3pBuX5nihPEKD9
hello, world!

$ # 新規サンプル・データの作成(データはテキストに限らず画像などのバイナリでも問題ない)
$ echo 'Hello, Qiita!' > hello.txt

$ # データのリポジトリ追加と、そのハッシュ値の確認
$ ipfs add hello.txt
added QmSuyo747aBeA4yzXy354VUH3Z3pUBC3rULAQ5oF62fy5B hello.txt
 14 B / 14 B [=== ... ===] 100.00%

$ # 追加したリポジトリ内のデータの公開。戻り値はコンテンツの IPNS の Key(後述)とコンテンツの IPFS URI
$ ipfs name publish QmSuyo747aBeA4yzXy354VUH3Z3pUBC3rULAQ5oF62fy5B
Published to k51qzi5uqu5dloao8jzqletz2tz06su210ddl0hn7vwo5hoi1an40zs57wjh3y: /ipfs/QmSuyo747aBeA4yzXy354VUH3Z3pUBC3rULAQ5oF62fy5B

$ # 公開したファイルの確認(他のマシンで確認してもよい)
$ ipfs cat QmSuyo747aBeA4yzXy354VUH3Z3pUBC3rULAQ5oF62fy5B
Hello, Qiita!

$ # IPFS ネットワークを HTTP に転送するゲートウェイ経由であれば cURL でも取得できる
$ curl https://ipfs.io/ipfs/QmSuyo747aBeA4yzXy354VUH3Z3pUBC3rULAQ5oF62fy5B
Hello, Qiita!

$ # データを公開した際に得た IPNS の Key でゲートウェイ経由で cURL してみる
$ curl https://ipfs.io/ipns/k51qzi5uqu5dloao8jzqletz2tz06su210ddl0hn7vwo5hoi1an40zs57wjh3y
Hello, Qiita!

$ # ローカルの HTTP ゲートウェイ経由でファイルを取得(ipfs デーモンが簡易 Web サーバの機能を持っています)
$ curl http://localhost:8080/ipfs/QmSuyo747aBeA4yzXy354VUH3Z3pUBC3rULAQ5oF62fy5B
Hello, Qiita!

上記のように、意外に簡単に公開分散ファイルシステムが使えてしまいます。

途中で https://ipfs.io/ipfs/<CID>https://ipfs.io/ipns/<Key> でもアクセスできることに「(おっ!curlwget でも使えるってか!)」と感じたかもしれません。

https://ipfs.io/ipfs/ は IPFS ネットワークを HTTPS につなげるゲートウェイの 1 つです。自分でも建てられますし、CloudFlare などの CDN プロバイダーも建てています。

CDN を通すと何が良いかというと、CloudFlare の速度で Web サーバー・レスで静的ファイルを提供できるということです。つまり後述する Raspberry Pi や使っていない PC などにコンテンツを突っ込んで IPFS 上で共有しておけば、CDN を通して提供できるということです。

ファイルの更新

若干の復習ですが、CID は実質的にコンテンツの内容のハッシュ値なので、コンテンツの内容が変わるたびに CID も変わります。

つまり「そのコンテンツの ID」と言うよりは「そのコンテンツの版(バージョン)の ID」という表現が似合うかもしれません。git で言うところのコミット ID(CID)や、Docker で言うイメージレイヤーのハッシュ値(Image ID)と同じです。

これによりデータの一意性が増すのですが、逆にデータの内容を更新して共有したい場合には CID は適しません。何かを更新するたびに新しい CID を相手に伝えないといけないからです。

この問題を解決する方法の 1 つが IPNS(InterPlanetary Name System)です。

IPNS とは

IPNS(InterPlanetary Name System)は、名前に CID を紐づける仕組み。

これを活用してディレクトリを紐づけるとコンテンツを更新しても変わらない一意のアドレスを作ることができる

IPNS を完全に理解した気になるためには ipfs name コマンドは何をするのか理解しないといけないのですが、まずは具体的な動きを見ながら逆算して(紐解いて)いった方が、ちょっとできるくらいには理解できると思います。

🐒   説明が長ったらしいので「IPNS は IPFS の PKI の名前空間で、ノードの公開鍵のハッシュ値を名前(Key)に、CID と、ノードの秘密鍵による CID の署名と、公開鍵を Value にして空間に設置し、ディレクトリを CID にすることでディレクトリ内の複数ファイルを共有できる」と言われてピンとくるせっかちさんは次の章に進んでください。以下は、これをかなり咀嚼そしゃくしながら説明します。

コンテンツを登録して、その CID を公開すると、最終的に 2 つのハッシュ値が得られます。/ipfs/Qm から始まるハッシュと、k5 から始まるハッシュです。

以下の具体的なログで、ipfs add <コンテンツのパス> で登録して得たコンテンツの ID(CID)のハッシュ値と、ipfs name publish <CID> で公開した時に得られるハッシュ値に注目ください。

コンテンツの登録と公開
$ # コンテンツの登録(データをリポジトリに追加。そのハッシュ値が確認できる)
$ ipfs add hello.txt
added QmSuyo747aBeA4yzXy354VUH3Z3pUBC3rULAQ5oF62fy5B hello.txt
 14 B / 14 B [=== ... ===] 100.00%

$ # 追加したリポジトリ内のデータの公開。戻り値はコンテンツの IPNS の Key とコンテンツの IPFS URI
$ ipfs name publish QmSuyo747aBeA4yzXy354VUH3Z3pUBC3rULAQ5oF62fy5B
Published to k51qzi5uqu5dloao8jzqletz2tz06su210ddl0hn7vwo5hoi1an40zs57wjh3y: /ipfs/QmSuyo747aBeA4yzXy354VUH3Z3pUBC3rULAQ5oF62fy5B

2 つ目の最初が k5 から始まるハッシュ値ですが、これは IPNS の仕組みで使われるファイルを更新しても変わらない ID のようなもので Key と呼ばれます

Key と呼ばれる理由は後述しますが、厳密にはコンテンツを登録したノード(IPFS が走っているマシン)の公開鍵をハッシュ化した値で「名前」(name)とも呼ばれます。

この Key を使って、ひと工夫するとコンテンツが更新されても変わらないアドレスが作成できます。先に「ひと工夫」の答えを言ってしまうと「ディレクトリを共有する」ことです。

その「ひと工夫」の前に、先ほど公開したコンテンツにアクセスしてみましょう。実際の動作を見ることで、復習もかねて、より正確に理解できます。

まずは CID を使った /ipfs/<CID> でアクセスする方法と、IPNS を使った /ipns/<Key> でアクセスする方法です。どちらも同じ内容が返って来ます。

$ # IPFS の CID でアクセス
$ curl https://ipfs.io/ipfs/QmSuyo747aBeA4yzXy354VUH3Z3pUBC3rULAQ5oF62fy5B
Hello, Qiita!

$ # IPNS の Key でアクセス
$ curl https://ipfs.io/ipns/k51qzi5uqu5dloao8jzqletz2tz06su210ddl0hn7vwo5hoi1an40zs57wjh3y
Hello, Qiita!

次に、同じ手順で同じファイルを更新(内容を書き換え)して、再度公開してみます。つまり、ipfs add で CID を発行したのち、その CID を ipfs name publish で公開します。

この時、Published to の前半の k5 から始まるハッシュ値(Key)は変わらないことに注意します。

同じhello.txtに違う内容を上書き
$ # コンテンツの変更(内容の書き換え)
$ echo "Hello, I'm KEINOS!" > hello.txt

$ # 変更コンテンツの登録
$ ipfs add hello.txt
added Qme36EKDmxfnhWhFcZQ7pZUnoCLCinxNShS66JwM7z4Fvx hello.txt
 19 B / 19 B [=== ... ===] 100.00

$ # 変更コンテンツの公開(更新の反映)
$ ipfs name publish Qme36EKDmxfnhWhFcZQ7pZUnoCLCinxNShS66JwM7z4Fvx
Published to k51qzi5uqu5dloao8jzqletz2tz06su210ddl0hn7vwo5hoi1an40zs57wjh3y: /ipfs/Qme36EKDmxfnhWhFcZQ7pZUnoCLCinxNShS66JwM7z4Fvx

そして同様に、公開されたコンテンツを cURL で確認してみます。IPNS(/ipns/<key>) でアクセスする方は Key の値が変わっていないことに注目します。

$ # IPFS の CID でアクセス(CID が変わったが、当然内容も変わる)
$ curl https://ipfs.io/ipfs/Qme36EKDmxfnhWhFcZQ7pZUnoCLCinxNShS66JwM7z4Fvx
Hello, I'm KEINOS!

$ # IPNS の Key でアクセス(Key は変わっていないが、内容が変わった)
$ curl https://ipfs.io/ipns/k51qzi5uqu5dloao8jzqletz2tz06su210ddl0hn7vwo5hoi1an40zs57wjh3y
Hello, I'm KEINOS!

どちらも同じ変更された内容になりました。つまり /ipns/<Key> を使うと同じアドレスが使えることがわかりました。

しかし、1 つ落とし穴があります。

「別のファイルと内容」で、同じように登録 & 公開してみましょう。今度はファイル名を hello.txt から greetings.txt に変えて、内容は定番の "Hello, world!" にしてみます。

新規コンテンツの登録と公開
$ echo "Hello, world!" > greetings.txt

$ ipfs add greetings.txt
added QmeeLUVdiSTTKQqhWqsffYDtNvvvcTfJdotkNyi1KDEJtQ greetings.txt
 14 B / 14 B [=== ... ===] 100.00%

$ ipfs name publish QmeeLUVdiSTTKQqhWqsffYDtNvvvcTfJdotkNyi1KDEJtQ
Published to k51qzi5uqu5dloao8jzqletz2tz06su210ddl0hn7vwo5hoi1an40zs57wjh3y: /ipfs/QmeeLUVdiSTTKQqhWqsffYDtNvvvcTfJdotkNyi1KDEJtQ 

当然のように CID は変わったのですが、Key は変わっていません。

するどい人は「(あ〜、なるほど)」と、お気づきかもしれません。にぶチンの私は、公開コンテンツにアクセスして「えっ?」となるまでわかりませんでした。てへ

早速、新規公開コンテンツにアクセスしてみましょう。

新規公開コンテンツにアクセス
$ # IPFS の CID でアクセス(CID が変わったが、当然内容も変わる)
$ curl https://ipfs.io/ipfs/QmeeLUVdiSTTKQqhWqsffYDtNvvvcTfJdotkNyi1KDEJtQ
Hello, world!

$ # IPNS の Key でアクセス(Key は変わっていないが、内容が変わった)
$ curl https://ipfs.io/ipns/k51qzi5uqu5dloao8jzqletz2tz06su210ddl0hn7vwo5hoi1an40zs57wjh3y
Hello, world!

なんと、先ほどの Hello, I'm KEINOS! が上書きされてしまいました!

つまり、ターゲットとなるファイルは関係なく IPNS の Key でアクセスできるのは最後に登録された CID のみということです。

1 ページものの静的 Web ページを公開するなら良いのですが、これでは複数ファイルには使えません。かといって、コンテンツごとに別の IPFS ノード(IPFS のデーモン)を用意するのも非合理です。

実は、この Key の値は現在の「ノードの公開Key」をハッシュ化した値です。そのため、何を登録しても Key の値は変わらなかったのです。

$ ipfs name publish <CID>
Published to <Key>: /ipfs/<CID> 

IPNS の NSName System とは言うものの、どちらかと言うと Name SpaceSystem(名前空間の仕組み)と考えるとしっくりきます。

IPFS ネットワークには IPNS という名前空間があり、この Key のハッシュ値を「ノードの名前(name)」として使います。

そして、各々の nameKey-Value 型の連想配列のようになっており、値(Value)は 3 つの要素で構成されています。

  1. ノードの公開鍵
  2. CID
  3. CID をノードの秘密鍵で署名した証明書

つまり ipfs name publish <CID> というのは、「コンテンツの公開」と言うよりは、厳密には「コンテンツを署名した name の公開」なのです。

具体的には、ipfs name publish <CID> を実行すると、ノード(name)の「秘密鍵」で CID を署名して IPFS ネットワークに公開(publish)する」というコマンドなのです。

これが /ipns/<Key> でアクセスすると上書きされてしまう原因です。ipfs name publish によって証明している CID が変わってしまったからです。

ここで、いったん落ち着いて「複数の CID を公開する」場合を考えると、2 つの方法が考えられます。

  1. ipfs name publish する際に複数の CID を指定する。
  2. コンテンツごとに新しい公開鍵と秘密鍵のペアを作成して使う。

前者は、ディレクトリに複数コンテンツを入れておき、ディレクトリを ipfs add することで、まとめて 1 つの CID にできます。また、1 つの鍵のペアで済むため、管理が楽になります。

しかし、全てが同じグループ(ディレクトリ)になってしまうため、異なる内容も含めてしまうと、ファイルやディレクトリ構成が煩雑になるというデメリットもあります。(ちなみに、ディレクトリ下のファイルにアクセスするには /ipns/<Key>/<ファイル名> とファイル名でアクセスできます)

後者は、管理は煩雑になりますが、前者の「ディレクトリ」の仕組みと組み合わせると、内容のグループごとに鍵のペアを作成しておけば、ファイルやディレクトリ構成が綺麗になるというメリットがあります。

🐒 ちなみに鍵のペアを作成するコマンドは ipfs key gen です。詳しくは ipfs key --help をご覧ください。

Web3.0 時代の Web サーバを建てずに Web サーバを建てる

この、ディレクトリを共有した /ipns/<MyKey>CDN を、従来の DNS の仕組みに紐づければ、Web サーバを建てなくても高パフォーマンスの Web サーバを公開できるのです。

「建てなくても建てられる」とか、何を言っているのかと思うかもしれません。

例えば、俺様ドメインの https://mydomain.com/ にアクセスすると /ipns/<MyKey>/ で共有している俺様ディレクトリを参照させたいとします。

後述しますが IPFS ノードは RaspberryPi Zero でも建てられます。また、前述したように IFPS デーモンは標準で HTTP ゲートウェイ(IPFS → HTTP)を持っているので、自宅のルーター設定で俺様 IPFS ノードに HTTP ポートを向けて解放して、Dynamic DNS ツールなどを使えば公開できます。

しかし、これは昔ながらの自鯖(自宅サーバ)の方法です。つまり、ルータの設定や自鯖のパフォーマンスが問われ、何より不特定多数が自宅のルーター経由でアクセスしてくるのは避けたいものです。

そこで、IPFS のゲートウェイサービス(HTTP → IPFS)を提供している CDN に俺様ドメインの DNS を向けるのです。

CloudFlare を例にすると、以下のような設定をします。

  1. 俺様ドメインの DNS 設定
    1. CNAME を CloudFlare の HTTP ゲートウェイに向ける(cloudflare-ipfs.com
    2. TXTdnslink=/ipns/<MyKey> を追加する

これだけで、https://mydomain.com/sample.html とアクセスがあった場合、https://cloudflare-ipfs.com/ipns/<MyKey>/sample.html にアクセスした場合と同じになり、共有しているディレクトリ直下にある sample.html が表示されます。この仕組みを DNSLink と言います。

この時のポイントは、俺様 IPFS のノードのあるネットワークのルータの設定をいじる必要がないことと、一度アクセスすれば CloudFlare だけでなく IPFS ノードから自宅までの中間の IPFS ノードにキャッシュされることです。

つまり、低いスペックのマシンでも専用機にするなら IPFS デーモンを十分走らせることができます。

何より、CloudFlare 経由の HTTP 接続でなくても IPFS 対応のブラウザなどで /ipns/<MyKey>/sample.html とアクセスする際も CloudFlare のノードのキャッシュを使ってくれるなど、いいとこ取りです。

「(でも静的ページのみで動的ページのコンテンツは公開できないじゃん)」と思うかもしれません。そういう方は WebAssembly を掘り下げてみてください。

外部に向けたサーバを建てなくてもコンテンツを公開できるこの IPFS の仕組みから、何か色々と見えて来たのではないでしょうか。

さらに、この IPFS の技術と、後述するブロックチェーンと組み合わせるなど、なさらなる色々な技術(マッシュアップ)が産まれようとしています。

いよいよティム・バーナーズ=リーさんの言う「セマンティック・ウェブ」もしくは Web 3.0 の時代が来つつありそうです。たぶん。知らんけど。

プライベートな IPFS ネットワーク

IPFS は、基本的に公開文書向けのネットワークとして始まったのですが、やはり「プライベートな分散ファイルシステムとして使いたい」と思うかもしれません。

基本的には可能ですが、プライベート IPFS は、どちらかと言うとハッシュの話しより、暗号寄りの話しなので割愛しますが 3 行で説明します。

  1. IPFS のリポジトリ(.ipfs)直下に共通鍵を置くと通信を暗号化することができる。
  2. 同じ共通鍵を持つ(設置した)ピア同士で仮想的なネットワークが作れる。(HTTPS や VPN と似た発想)
  3. 共通鍵は ipfs-swarm-key-gen コマンドで作成する。

IPFS はラズパイ Zero(W) でも動く

「(IPFS 試してみたいけど、ローカルに入れるには、いささか躊躇ちゅうちょしてしまうな)」という方には、2千円程度で手に入る RaspberryPi Zero W で試されてはいかがでしょう。

Linux と SSH 接続の知識が必要ですが、IPFS 専用機にチューニング(GUI なし、解像度低め、GPU メモリ割り当て少なめ、スワップサイズ 2GB)すれば十分に使えます。

GitHub に IPFS のインストールとアンインストールのスクリプトを置いてありますので、よろしければご覧ください。

ハッシュ関数とブロック・チェーンの関係

さて、ちょいちょい出てきた、仮想通貨(暗号通貨)で有名なブロック・チェーンですが、その仕組みのベースに使われているのがハッシュ関数です。(ハッシュ関数の特徴に関しては上記「ハッシュ関数の基本と特徴」参照)

ブロック・チェーンでは、以下の3つのハッシュ関数の特徴が活かされています。

  1. 非可逆である(元に戻せない)
  2. 同一性(同じものであること)が確認できる
  3. 衝突を探すのは大変だが、探したものを確認するのは簡単

ここで言う「衝突」とは「異なる値なのにハッシュ値が同じになっちまった」という状態です。業界用語で collision と言い、発音はチョッと照れる感じで「これじゃん?」寄りに「コリジョン」です。

しかし、ブロック・チェーンの何が「すごい」のでしょう。

「中央集権型に依存しなくていい」とか「お金に変わる何とか」とか聞きます。しかし、エンジニアを続けていると peer-to-peer(or 分散型)が必ずしも良いわけではないことを体感していたり、メンコとかトレーディングカードとかと何が違うのか、と。パチンコやスロットの換金コインと何が違うのか、と。「世間との熱量の違い」を感じてしまいます。

恐らく、エンジニア的にブロック・チェーンが面白いのは「ビザンチン将軍問題」もしくは「二人の将軍問題」を解決できることかもしれません。

「ビザンチン将軍問題」「二人の将軍問題」の概要

「ビザンチン将軍問題/二人の将軍問題」は、一言で説明すると「A から B へ情報を伝達するルートが信用できない場合に、正しい情報を伝えることができるか」という問題です。

おおざっぱにサーバーで例えると以下のイメージです。

A 国にサーバー A 、B 国にサーバー B があり、お互いの準備が整うと各々「処理 X」を始めます。しかし、どちらかの準備が整っていないで「処理 X」を始めると、核核然然かくかくしかじかな理由で「両国が崩壊する」と仮定します。

問題は A 国と B 国のネットワークが複数の国を経由しないといけないことです。

その経由先には敵対する C 国があるだけでなく、寝返る「かも」しれない同盟国 D 国と E 国もあります。「寝返る『かも』」と言うのは、D 国も E 国もお賃金が安く、役人でさえ小遣い稼ぎで賄賂をもらうような人が多い国である、という設定です。

「準備ができていない」と伝えたのに「準備できた」と伝わってしまった場合、両国が崩壊します。つまり敵対国は中継経路で改ざんするのが狙い目であるため、同盟国といっても安心できないのです。

この、「準備が整った」と伝達するルートの途中で改ざんされる可能性があるのが最大の問題です。

途中の経路が絶対的に信頼できない状態は、まさにサーバー間通信が持つネットワークの問題と同じだと感じると思います。

この問題に対して現在ネットワークで使われているのが TLS/SSL 通信です。

HTTPS などの TLS/SSL 通信の場合は、サーバの証明書を通してサーバとクライアントのお互いの秘密鍵・公開鍵暗号から作成された公開鍵を使って、「傍受ぼうじゅ」されたり「改ざん」されることを防いでいます。

しかし、残念なことに復号された内容そのものが「正しいか」まではわかりません。https://〜 で始まるからといって安心できるサイトではないのと同じです。(秘密鍵・公開鍵暗号の概要に関しては、本記事上部にある「ハッシュ関数の基本と特徴」を参照ください)

ここで、著者が発行したデータのハッシュ値も別ルートで送れば「復号された内容が正しいこと」を検知できそうです。しかし、どの通信ルートも信用できないため、そのハッシュ値すら正しいか確信が持てません。

同じインターネットのルートでなく、電話網、トークンキースニーカーネットワークといった別の媒体のルートを介して確認することを「2要素・・認証」と呼んだりしますが、肝心の電話会社やトークンキー開発会社も運び屋も信用できない状態です。

話した内容がマスメディアを通すと違っていたり、出版物が勝手に書き換えられたり、決算報告で大丈夫と思っていた銀行や企業が突然なくなったり、ホームセキュリティ会社の社員が隠しカメラを設置していたり、脅されているのか血迷ったのか公文書を改ざんしたりする政治家がいる世の中だと、なおさら確信が持てないかもしれません。

そう考えると、意外にリアルな話だと思います。

パスワード付き ZIP が、なぜか共通鍵暗号として全盛だった時代、メールを送ったら届いたか電話で確認するのが流行りました。

ちょうどその頃、プライバシーマークを取得するため「添付ファイルはパスワード付き ZIP でメールに添付して送り、パスワードは次のメールで同じアドレスに送る」のが企業で流行りました。今で言う失敗した「2段階・・認証」の走りです。

しかし、プライバシーマークに限らず ISOJIS などもそうですが、規格の認証団体は以下のように要件(チェック事項)は定義するものの具体的な実装方法については言及しません

「個人情報を含む添付ファイルを取扱う際に、セキュリティ対策(データの暗号化、パスワード設定など)の措置を講じること」(第23条)

そして、プライバシーマーク取得の要件を網羅するため昔の企業が独自解釈で取った手法が、パスワード付き ZIP + 別メールであり、「措置を講じている」としたのです。

この時代から「クライアントが本当に欲しかったもの」系の「嘘は言ってないし、要件は網羅しているよね」と、肩書きや体裁を優先しようとした過去の悪しき習慣の 1 つとも言えます。

もちろん、そんなのはダメちんなので、現在は公開鍵暗号と、ちゃんと・・・・した共通鍵暗号を組み合わせた方法が主流になりつつあります。

また、公開鍵は公開鍵基盤を通して安全に取得できるようになりました。つまり、取得した公開鍵を公開鍵基盤に問い合わせて正しい公開鍵であるか確認できるのです。

その認証局、信用できますか?

ここで、先の「ビザンチン将軍問題/二人の将軍問題」がチラついてきます。

現在の SSL/TLS 通信は、認証局を銀行や政府のように「信用するしかない」という状態で動いています。つまり、証明書(公開鍵が正しいものであるかの証明書)を発行する組織や企業を信用するしかないのです。

もし、その組織や企業の担当者が洗脳されたり、幹部が敵対国と手を組んでいた場合、偽の公開鍵の証明書を発行する可能性はゼロではないのです。これは、某北の挑戦的な国の公開鍵基盤を某北の挑発的な国が使いたがらないように、お互いの公開鍵基盤を信用していないのと同じです。

世界の海底ケーブルですら、「どの国にケーブルが引き上げられるか」で揉めるのです。

「別にケーブルの中を通るデータが暗号化されてるんだったら、途中で見られてもいいじゃん」と言うわけには行かないのです。役人ですら、パスワード付き ZIP のパスワードを FAX で送ったり、httphttps の違いを知らなかったり確認しないでフォームに大事な情報を入れちゃうようなご時世ですから。

このように「二人の将軍問題」はネットワークの問題だけでなく、中間に位置するものを信用できない状況で起きる現代の問題でもあるのです。

この「二人の将軍問題」を道徳でなく仕組みで解決できるかもしれないというのが話題のブロック・チェーンです。なんと「賄賂などの小銭で寝返る小悪党を味方にしちゃえばいいんじゃね?」という逆転の発想です。

ブロック・チェーンの概要

ブロック・チェーンの基本構造は割と単純で、「1つのデータが、前のデータのハッシュ値も持つ」というものです。

そして、後述する「プルーフ・オブ・ワーク」(もしくは「プルーフ・オブ・ステーク」)と言う概念とセットとなったものを「ブロック・チェーン」と言います。

ブロック・チェーンは「サトシ・ナカモト」なる日本人と思わしき謎の人物が提唱したと言うのは聞いたことがあると思います。

実際にそうなのですが、厳密には「従来からある 2 つの考え方を組み合わせたものから発想を得たもの」と言えます。以下がおそらくその 2 つです。

  1. マークルの木(ハッシュ木)
  2. マークルのパズル

ここで、先のハッシュ関数の基礎知識で「塩(salt)は後から足す」の話しに出てきたヒーロー・ロボットのような名前の「マークル・ダンガード」を思い出してください。

実は、この「マークル」はラルフ・マークル氏のマークルなのですが、個人的に「もっと評価されるべき」的な人物だと思います。(いや、業界では超有名人なので一般に認知されるべき人と言うか)

どうもマークル氏は、日本で言えば南部陽一郎さんのような、アイデアをポンポンと投げては他の人に影響させるタイプの人だったらしく、公開鍵暗号の基礎となるアイデアを作ったり、暗号学的ハッシュの元となるマークル・ダンガードを発明したり、ファインマン氏が予言&提唱した量子コンピュータを「物質を原子レベルの大きさで制御しデバイスとして使う」という「コンピューターと分子ナノテクノロジーの融合のパイオニア」と呼ばれたかと思えば「人体冷凍保存の人」と言われたり。まぁ変な人です。存命の方なので Youtube などでググれば色々な講演が聞けます。

さて、「1つのデータが、前のデータのハッシュ値も持つ」と言いましたが、この構造の概念自体は git のコミットハッシュなど、ブロックチェーン以前から存在しており、そのベースとなるのが「ハッシュ木」です。

そして、「プルーフ・オブ・ワーク」の元になるのが「マークルのパズル」です。

木と言うよりチェーン

ハッシュ木の場合は、木を逆にしたような構造で「子」となるブロックのハッシュを「親」が持つと言うものです。

ハッシュ木

ブロック・チェーンは、それをシンプルに 1 本にした感じのものです。

ブロック・チェーン

各ブロックには「データ」と「ハッシュ値」があり、ハッシュ値は 1 つ前のブロックのデータとハッシュ値をハッシュ化したものです。

ブロックチェーンのハッシュフロー

このハッシュの値がブロックとブロックのつなぎとなりチェーンになっているため、ブロック・チェーンと呼ばれます。チェーンに見えますでしょうか。

実は、ブロック・チェーンは「データ」に工夫がされており、保存したいデータのフィールドと nonce と呼ばれるフィールドがあります。

nonce って、なんっスか?

Qiita ユーザには下手な概念図で示すより、データで見た方がピンとくるかもしれません。

ブロック・チェーンのデータを JSON 形式で簡略表現すると以下のようになります。hash data nonce の1セットを1ブロックとします。

[
    {
        "hash": "<hash1>",
        "data": "<data1>",
        "nonce": "<nonce1>"
    },
    {
        "hash": "<hash2>",
        "data": "<data2>",
        "nonce": "<nonce2>"
    },
    ...
]

上記の hashdatanonce の 3 つのキーの内容は以下の通り。

  1. hash キーの値は、前のデータの hashdatanonce の値をつなげてハッシュしたものです。(<hash2> = hash('sha256', <hash1> + <data1> + <nonce1>);)
  2. data キーの値は「何かしらのデータ」で平文でも暗号文でも構いません。プログラムのスクリプトであっても構いません。
  3. "nonce"(ナンスもしくはノンス)キーですが、これがブロック・チェーンのキモ・・です。この nonce の値を算出することを「マイニング」と呼んでいます

マイニング(発掘)と呼ぶのは、この nonce の値を最初に見つけ、承認を得られた人は報酬がもらえるからです。ブロック・チェーンがビットコインの場合は、ビットコインがもらえます。

つまり、nonce を見つけることが現金につながるだけでなく、みんなのマイニング作業や承認作業によって「データのハッシュ値が正確であるか」を複数人で確認しあっていることになるため、データが堅牢になって行きます。

🐒   たまにマイニングを仮想通貨(暗号通貨)そのものを発掘するような意味とも思える記述を見かけますが、違います。

「金を発掘したら俺のもの」的な宣伝が多いのでわかりづらいのですが、どちらかと言うと「レアメタルを発掘したら報酬でお金がもらえる」イメージが近いと思います。ビットコインの場合は「nonce 値」がレアメタルで、「ビットコイン」が報酬のお金です。
仮想通貨自体は1コインごとに、コインの秘密鍵とコインの ID となるハッシュ値がセットになったようなデータで、各コインは 0〜1 の float 値を持っており分割可能です。ビットコインの場合は、1.00000000 まで分割可能です。このコインは、一般的に ICO と呼ばれるステップで作成(発行)され、ユーザーは購入もしくはもらいます。
受け取ったコインは、ユーザーごとに作成される秘密鍵とフォルダをセットにした「ウォレット」と呼ばれる先に保存されます。この時、ユーザー間のウォレットでコインが移動したときの取り引き内容が「ノード」と呼ばれる先の DB にブロック・チェーン形式で記録されます。

ノード
ブロックチェーンにおける「ノード」はブロックチェーンのピアのうち「DB の管理をしているピア」です。コイン取引所やメンテナやマイナー(マイニングをする人)などが「ノード」に該当します。各々のノードの DB は同期されており、これがブロック・チェーンを「分散台帳」とも呼ぶゆえん・・・です。「ノード」はネットワークの常時接続やディスク容量が必要といったデメリットもありますが、「ノード」になるメリットはブロックチェーン追加時に報酬のためのコインを作成(発行)することができる点と DB 追加の手数料がもらえる点です。そのため、初期の頃は、ノードとマイナー(マイニング)を兼任するサーバーも多く、これが「マイニング=コインの発掘」というイメージを産んだ理由でもあります。

いずれにしても、ブロック・チェーンは DB の1種であると考えて差し支えないと思います。そのため、ブロック・チェーンの仕組みは仮想通貨/暗号通貨でなくても活用できます。

ブロック・チェーンは "nonce" センスなゲーム

ブロック・チェーンにおける nonce は、一言で言うと「ハッシュ値の衝突を探すゲームで、最初に見つかった値」です。

このゲームとは「現在の datahash に、nonce を加えてハッシュ化すると、最初の n 桁が 0(ゼロ)になる nonce の値を探す」といったものです。

00の衝突を探す例
// 1 つのブロック・データ
$data = 'something';
$hash = '34902903de8d4fee8e6afe868982f0dd';
$nonce = 'd9'; // <- 見つけた nonce 値

// md5 でハッシュ($data.$hash.$nonce)
$result=hash(md5, 'something34902903de8d4fee8e6afe868982f0ddd9');

// ゲームの結果確認
echo $result; // -> 00603ea2b0f451d9531b6caeb0e96afb
// result の最初の 2 桁が 0 (ゼロ)なのでクリア!

その桁数や 0(ゼロ)の値などはブロックチェーンによってルールは異なりますが、いずれも nonce を加えてハッシュ化した時に出る値に対するルールです。

nonce を探すイメージを Bash で書いてみました。

bashでマイニングする(nonceを探す)例
#!/bin/bash

# RULE
VALUE_HEAD='0000'
LEN_HEAD=${#VALUE_HEAD}

# Function
function dechex() {
    printf '%x' $1
}

function isValidNonce() {
    [ "${1:0:$LEN_HEAD}" = "${VALUE_HEAD}" ]
    return $?
}

function hash() {
    algo=$1
    value=$2
    echo $(echo -n $value | openssl $algo | awk '{print $2}')
}

# Data
data='something'
hash='34902903de8d4fee8e6afe868982f0dd'
nonce=''

# Mining/Search nonce
counter=0
while true
do
    nonce=$(dechex $counter)
    string_to_hash="${data}${hash}${nonce}"
    hash_temp=$(hash 'md5' $string_to_hash)
    isValidNonce $hash_temp && {
        break
    }
    counter=$((counter+1))
done

echo "Nonce found: ${nonce}"

しかし、ブロックチェーンは「一度、生でブロックチェーンを見たら分かる」と言われるくらいなので、全体の流れをプログラムで見た方がピンとくるかもしれません。

PHP で簡単に書いてみました。

既存のブロック・チェーンのデータ
// 2つ前のブロック・データ
$block_chain[] = [
    'data'  => 'sample1',
    'hash'  => 'a4626f9d3e6802aebbff46697248e0b9',
    'nonce' => 'xxxxxx',
];
// 1つ前のブロック・データ(Latest)
$block_chain[] = [
    'data'  => 'sample2',
    'hash'  => '3152851bf5419247cf948e871b0adfe8',
    'nonce' => '32648',
];
Nonceのルール
// 最初の4文字が 0 である
define('VALUE_HEAD', '0000');
define('LEN_HEAD', strlen(VALUE_HEAD));

/* 検証用の関数 */
function isValidNonce(string $nonce): bool
{
    // ルール:$nonce の頭 n 文字が VALUE_HEAD と同じ( n = LEN_HEAD )
    return (substr($nonce, 0, LEN_HEAD) === VALUE_HEAD);
}

function isValidHashInLatestBlock(array $block_chain): bool
{
    // 現在のブロックの長さ
    $len_block_chain = count($block_chain);

    // 2つ前のブロックのデータ取得
    $key_2block_ago = $len_block_chain - 2;

    $data_2block_ago  = $block_chain[$key_2block_ago]['data'];
    $hash_2block_ago  = $block_chain[$key_2block_ago]['hash'];
    $nonce_2block_ago = $block_chain[$key_2block_ago]['nonce'];

    // 期待するハッシュ値の算出
    $hash_previous_expect = hash('md5', $data_2block_ago. $hash_2block_ago . $nonce_2block_ago);

    // 1つ前のブロックのハッシュ値取得
    $key_block_previous   = $len_block_chain - 1;
    $hash_previous_actual = $block_chain[$key_block_previous]['hash'];

    // 1つ目のブロックのハッシュ値の検証
    return ($hash_previous_expect === $hash_previous_actual);
}

function getBlockLatest(array $block_chain):array
{
    $len_block_chain = count($block_chain)-1;
    return $block_chain[$len_block_chain];
}
ブロックチェーンにデータを追加したい人の作業
/* 1つ前のブロックの検証 */
if(! isValidHashInLatestBlock($block_chain)){
    echo 'Error: Not a valid hash value. Block-chain broken.' . PHP_EOL;
    exit(1);
}

/* 新規ブロックのデータ作成 */
// 追加したいデータ
$data_current = 'sample3';
// ブロックのハッシュ値を計算(1つ前のブロックより)
$block_previous = getBlockLatest($block_chain);
$hash_current   = hash('md5', $block_previous['data'] . $block_previous['hash'] . $block_previous['nonce']);
$block_current  = [
    'data' => $data_current,
    'hash' => $hash_current,
];
echo 'Request to add to the block-chain.' . PHP_EOL;
echo '  Data:' . $data_current . PHP_EOL;
echo '  Hash:' . $hash_current . PHP_EOL;
マイナー(マイニングする人)の作業
/* 1つ前のブロックの検証 */
if(! isValidHashInLatestBlock($block_chain)){
    echo 'Error: Not a valid hash value. Block-chain broken.' . PHP_EOL;
    exit(1);
}

$data_current  = $block_current['data'];
$hash_current  = $block_current['hash'];
$nonce_current = '';
// Nonce 探索
$i = 0;
while( true ){
    $nonce_current = dechex($i);
    $hash_temp = hash('md5', $data_current . $hash_current . $nonce_current);
    if(isValidNonce($hash_temp)){
        echo 'Nonce found: ' . $hash_temp . PHP_EOL;
        break;
    }
    $i++;
}

/* マイニングの結果(これを検証依頼する) */
echo 'Block Data to add:' . PHP_EOL;
echo '  Data: ' . $data_current . PHP_EOL;
echo '  Hash: ' . $hash_current . PHP_EOL;
echo '  Nonce: ' . $nonce_current . PHP_EOL;
ブロック・チェーンに追加する人の検証作業
/* 1つ前のブロックの検証 */
if(! isValidHashInLatestBlock($block_chain)){
    echo 'Error: Not a valid hash value. Block-chain broken.' . PHP_EOL;
    exit(1);
}

$hash_verify = hash('md5', $data_current . $hash_current . $nonce_current);

echo 'Hash result: ' . $hash_verify . PHP_EOL;
if(! isValidNonce($hash_verify)){
    echo '  Error: Nonce not valid.' . PHP_EOL;
    exit(1);
};

// ブロック・チェーンに追加
$block_chain[] = [
    'data'  => $data_current,
    'hash'  => $hash_current,
    'nonce' => $nonce_current,
];
echo '  Success: New data added to block-chain.' . PHP_EOL;

// ブロック・チェーンの内容表示
echo 'Current Block-Chain:' . PHP_EOL;
print_r($block_chain);

上記で重要なのが、マイナー(マイニングする人)の処理にある「Nonce 探索」の while ループの箇所です。

一部のマッチが true になるのか、全文マッチが true になるか以外はマッチ対象が違うだけでハッシュ値の衝突を探す手法そのままです。つまり、総当たりで根性で探しているのです。

実際には文字列の比較でなく、FF000...and 処理(ビットマスク)した方が速いなどありますが概念的に、こういうことです。😳

🐒   実際の「ブロック・チェーン」のデータは高速化なども配慮してもっと複雑です。しかし基本概念は同じです。

また、ブロック・チェーンではデータのかたまりを「ブロック」と呼ぶのですが、ネットワークの「パケット」と「フレーム」のように、ブロックと呼ばれる区分けがレベル(レイヤー)によって違います。ここでは仕組みがわかりやすいように「登録したい1つのデータ」を「ブロック」と呼びます。参考として、ビットコインなどは「n 分間の取引データ」を1ブロックと時間単位で区切っています(現在は n=10)。そして登録される個々のデータを「トランザクション」と呼んでいます。

どのような nonce の探し方であっても、平均して特定の時間前後かかるように 0(ゼロ)の長さのルールが自動調整されます。ビットコインの場合は、およそ 10 分前後になるように調整されます。

ここで大事なのが、「nonce を探すのは大変だ(時間がかかる)がハッシュ関数で確認することは一瞬」ということです。

プルーフ・オブ・ワーク(仕事の証明)

ブロック・チェーンの重要な基本ルールに「現在一番長いチェーンを『正』とする」があります。

つまり、せっかく計算しているのに短い方のブロックチェーンを使っていた場合は無効になるということです。自分より早く「nonce を見つけた!」という人がいた場合、計算を続けても電気や時間のリソース(👌)が無駄になってしまいます。noncenone になってしまいますのん。

そこでマイナー(マイニングする人)は、本当に見つけたのかを確認する作業を行い、正しければ早々にブロックチェーンを更新して、次の登録待ちデータのマイニングを始めるのです。

この仕組みにより、ブロック・チェーンの途中にあるデータを改ざんしようとした場合、大変なコストが発生します

改ざんしたブロックより後のブロックのハッシュ値の計算だけでなく nonce の値まですべて再計算してリリースしないといけないからです。それだけでなく、世界中のマシンに散らばったブロック・チェーンのデータにも不正アクセスして書き換える必要もあります。

しかし、改ざんして再計算したり、他のマシンをハッキングしてデータをクラックしている間にも、よほど過疎っているブロックチェーンでない限りデータはどんどん長くなり更新されていきます。改ざんさせる暇を与えづらい状況が作られるのです。

ビットコインの場合は、ウォレット間の移動がある(取引がある)たびに 10 分おきに長くなって行くので、とうてい間に合わないのがわかると思います。

さらに、2020 年 07 月の現在のビットコインのブロックチェーンの長さは約 270 GB です。これを改ざんするには、10 分以内に「改ざん箇所以降の全て」の nonce 値を計算する必要があります。しかし、肝心の nonce 探索は 1 つ見つけるまでに 10 分前後になるように自動調整されているため、かなり難しいことが実感できると思います。

つまり「データを改ざんして小銭を稼ぐよりはマイニングした方が稼げる」ということです。

そして、当然これらの処理は自動で行われます。つまり、スパムメール/フィッシング/詐欺商品/ゴミ記事の広告収入など、単純作業を自動化して「数を打って薄利多売で稼ぐ」という昔ながらの手法を使う人にとっては「楽して稼げる」だけでなく、「他人のマイニング結果の粗探し」が結果としてブロック・チェーンの正当性(データのハッシュ値が同じであること)を保証することになります。

そのため、「ホワイト」しかも「ウィン・ウィン」となるため、中小規模の悪党の犯罪心理学を逆手に応用した、敵を味方に付ける有効な概念なのです。

もちろん、国家レベルの資金がある大規模な悪党が、相手を潰すために鬼のようなマシンを大量に用意できれば、以下の攻撃でブロックチェーンを改ざんデータ入りで更新させることはできます。

  • 改ざん後、残りのすべてを再計算し、現在のブロック・チェーンより少しだけ長いチェーンを作成してリリースする
  • 改ざんデータを、オリジナルのデータと同じハッシュ値になるような値とセットで改ざんデータとして埋め込む

しかし、利用者が多ければ多いほど多彩な人がおり、nonce のマイニングでなく過去のデータの検証だけを行う人も出てきます。また、後述するように前のブロックのデータサイズも含めるようにすれば、より堅牢なブロックチェーンを構築できることになります。

つまり、ブロック・チェーンは「複数人でチェックしあい、チェックしてもらったら早い者勝ちで報酬を与える」「チェーンの長さがセキュリティにつながる」「利用者が多ければ多いほど堅牢になる」という仕組みなのです。

この、データのハッシュ値を確認し nonce の値を探す、それを他者が粗探し(検証)をし、問題なければ各々のチェーンに追加する。これを「プルーフ・オブ・ワーク」(仕事の証明)と呼びます。

nonce のゲームとマークルのパズル

さて、ここまで来て「マークルのパズル」について説明したいと思います。

「マークルのパズル」とは、公開鍵暗号や暗号学的ハッシュの種をまいていた例のマークル氏が考えたパズルです。Wikipedia によると以下のような説明がされています。

マークルのパズル(英: Merkle's Puzzles)とは、ラルフ・マークルが 1974 年に考案した初期の公開鍵暗号システムであり、1978 年に発表された。事前に秘密を共有していなくとも、メッセージを交換することで秘密を共有できる方式である。

マークルのパズル @ Wikipedia)

ここで注目して欲しいのが「事前に秘密を共有していなくとも、メッセージを交換することで秘密を共有できる方式」の一文です。

これは「二人だけの秘密」と言う点で、先の「公開鍵・秘密鍵暗号」にも言えることだし、「二人の将軍問題」にも言える内容だと思います。

このパズルのシチュエーションですが、「離れ離れのアリスとボブが、メッセンジャーとなるイブにバレずに秘密のメッセージを送ることができるか」と言う状況です。もぅ、まんまですね。

そこでマークルは、パズルを使った方法で解決しようとします。

まず、ボブは、そこそこ難しいが適度な時間(例えば n 日)で解けるパズルをたくさん用意してアリスに送ります。どのパズルも、パズルを解くと、一意の「暗号鍵」と「識別 ID」がわかるようになっています。

ある日、ボブに秘密のメッセージを送りたくなったアリスは、ボブからもらった、たくさんのパズルから 1 つランダムにピックアップしてパズルを解きます。

そして、そこから得られた暗号鍵でメッセージを暗号化して、識別 ID と一緒にメッセンジャーのイブに託します。

イブはこっそりと盗聴したいと思うも、どのパズルが使われたか分かりません。そこでイブは、唯一わかっている情報である「識別 ID」がヒットするまでボブのパズルを 1 つ 1 つ解いていかないと盗聴(復号)できません。

問題はパズルを解くのに 1 つあたり n 日かかることと、ボブが送りつけてたパズルが図書室が埋まるくらいの数である、しかも定期的に新規パズルが送られてくるため、「実質的に無理」と言う状況がおきます。

もちろん王様クラスの命令で、うん千人が同時にパズルを解くような👌リソースを持っていれば話しは別です。しかし、パンピーのボブとアリスがちちくり合うだけのメッセージにそのようなコストはかけてもらえません。

どうでしょう。ブロックチェーンの nonce 検索も「マークルのパズル」に近い考え方だ、とわかると思います。

ブロックチェーンのセキュリティ

ちなみに、巷で何度か「暗号通貨(仮想通貨)が盗まれた」という事件が発生していますが、これはブロックチェーンの仕組みが崩れたわけではありません。

単純に、パソコンがクラッキングされ、暗号通貨用の秘密鍵が盗まれてしまい、別の口座に移されてしまったという、クレジットカードや銀行口座のそれ・・と同じでセキュリティ管理上の問題による事件です。「ほらな」と言いたいメディアが仕組みを把握せずに印象操作をしているだけです。

51%攻撃(数の暴力)

おそらくブロックチェーンのセキュリティでシステム的に一番有名な攻撃が 51% 攻撃と呼ばれるものです。一言で言うと「多様性に欠けた際の、多数決による意思決定の情報操作」です。

ブロックチェーンは基本的に主となるサーバーが存在しません。そのため、意思決定はノードによる多数決で決めることになります。「ノード」とは、先述したように分散された各々のブロックチェーンの DB サーバーのことです。各ノード(サーバー)には、各々マイナー(マイニングする人)やユーザー(ブロックチェーンにデータを追加したい人、例えば仮想通貨の場合は取引内容を登録したい人)が所属しています。

この時、間違った登録内容であってもノードやマイナーの過半数が「問題ない」と答えると登録されてしまうのです。ここで言う「間違った」と言うのは、ハッシュ値が合わないデータではなく、データそのものを改竄した物を言います。

つまり、現実世界の多数決と同じように、数と資産(処理能力)を持った組織でコントロールすることができてしまうのです。

🐒   資本主義と犯罪学の観点からは、残念なことにブロック・チェーンを仮想通貨(暗号通貨)に使うにも昔からある問題が出てきています。

ビットコインの場合、マイニングにかかる時間(nonce が発見されるまでの時間)が自動的に 10 分前後になるようにルール(ゼロの個数)を調整しています。逆に言えば、マシン・パワーを持つ人が常に優位になるということです。
「今からマイニング事業を始めても儲けが少ない」と言われるのは、初期のころからルールにあわせて設備投資していた人と比べ、必要なマシンスペックの費用対効果が薄いからです。そうなると、すでに資本(マシンパワー)を持っている人にしか稼げない土壌ができつつあります。せっかくの「小悪党を味方に付ける」仕組みが崩壊する可能性もあるのです。
また、マイナー(マイニングする人)のバラエティが少ないと、イレギュラー時に全滅する可能性も高くなります。特に上記の 51% 攻撃をさせやすくなってしまいます。
そういった多様性の欠落問題に対して、マイニングの処理を分散させて、資本が少ない(マシン・スペックが低い)人でもマイニングに参加できるような仕組みも出てきました。事件にもなった Coinhive などです。この事件は Winny と同じく「犯罪の温床となりうるから」と検挙された事例で、どちらも「賢くない人」が「ズル賢くやろう」と迷惑をかけた・配慮に欠けたことによる弊害で、技術そのものがトバッチリを受けた事件です。どちらの技術も「分散技術における重要なもの」ではありました。
アンチ資本主義(資本を持っている人を脅かす考え方)に対する弾圧とまでは言いませんが、少なくとも Winny の件は日本の分散技術が世界から遅れた理由ではあります。
「賢くない人から賢い人にお金が集まる」ことを資本主義の特徴の1つと仮定すると、犯罪における資本主義は「賢くない人からズル賢い人にお金が流れる仕組み」とも言えます。つまり「賢くない手下にマシンを走らせ、ズル賢い元締めに流れる仕組み」が生まれてきます。犯罪組織の王道の仕組みです。つまり、マイニングから得たクリーンな資金が犯罪組織の資産にもなりうるということです。
しかし、これらはブロック・チェーンに限らず、自動的にお金が発生すると必ず起きる問題です。そのため、ブロック・チェーンの仕組みとは分けて考えるべきです。

さて、DB の改ざんにスポットを当てると、不特定多数で多様性に富んだ組織においては、一見ブロック・チェーンがベストな方法に見えます。しかし、nonce のように「そもそも時間をかけることでセキュリティを高めている」仕組みである以上、ブロック・チェーンは遅いのでケース・バイ・ケース(適材適所)と言えると思います。

また、ブロック・チェーンが「分散台帳」とも呼ばれるように、DB の分散に関しては、ハッシュ関数とは別の話しなので割愛しますが、以上のようにブロック・チェーンにはハッシュ関数の特徴が存分に活かされているのがわかると思います。

いずれにしても、この性善説(相手を信用する)でなく性悪説(悪党は楽をして稼げる方を選ぶ)を逆手に取った社会的な心理も加味したプルーフ・オブ・ワークの仕組みにより「A → B への(遅いけど)正確なデータの伝達が可能になった」のがプログラマとして面白いなー、と思うところです。

暗号通貨使ってないけど。

ブロックチェーンの環境問題について

ブロックチェーンや、後述する NFT について語る場合、必ずと言って良いほど環境問題が取り上げられます

これは、ブロックチェーンの PoW(プルーフ・オブ・ワーク)の処理において「電気を食いすぎるので環境に悪い」という意見です。

確かにブロックチェーンは、ブルートフォース祭り状態、つまり「nonce の値を探すためだけ・・に、鬼のような for ループを走らせる」ため、そのトータルの消費電力は馬鹿にできません。

これに関して結論(「ブロックチェーンは環境破壊なのか」という問題の答え)を出すには時期が早く、さまざまな意見があるのですが、筆者の 1 意見を述べたいと思います。

答えを先に言うと「ブロックチェーンの堅牢性は認知されてきているのだから、電気を大量に消費しない方法を考えればいい」ということです。後述するイーサリアムの PoS(プルーフ・オブ・ステーク)などの改良版がそれに当たります。

確かにビットコインで言えば、ちょっとした国 2 つぶんくらいの消費量と言われます。そのため、その電気消費量は無視できるものではありません。

しかし、nonce 探索というゲームのようなものに電気を食うとはいえ、決して意味のない処理をしているわけではありません。

本質的に、それは「分散データの改竄防止のための処理」として電気を食っているからです。そして、それから得られるメリットは「中央集権型ではない」ことを維持できることです。

つまり 1 社が倒産したりサービスを止めると、全てがなかった・・・・ことになる中央集権型のサービスと違い、ブロックチェーンは特定の会社だけがサービスを提供しているわけではないため、利用者がいる限り残るということです。

恐れずに言うと、サービスというよりはインターネットに近い「インフラ」なのかもしれません。

逆に、GAFA始め「中央集権型のサービス」の提供側と利用側が消費する電力はどうなのかも考えないといけない、ということです。

ここで、先の「ビザンチン将軍問題」と「マークルのパズル」を思い出してください。つまり、この問題を解決できるのであれば、別に PoW
プルーフ・オブ・ワーク) に固執する必要もないのです。

事実、イーサリアムなどのブロックチェーンは PoS(プルーフ・オブ・ステーク)を改良して消費電力を大幅に減らしています

PoW(プルーフ・オブ・ワーク)と PoS(プルーフ・オブ・ステーク)の違い

PoW(プルーフ・オブ・ワーク)と PoS(プルーフ・オブ・ステーク)は、どちらもデータを登録したいノードからの「ハッシュ値のチェック」と「nonce の探索」の依頼をし、その結果を他のノードの多数決で承認し登録する点では同じです。

PoWPoS の違いは、依頼をする先のアルゴリズム(処理の考え方)にあります

PoW が「 nonce 探索を行うのは誰でもいいから早いもの勝ち」「誰も信用しない」であるのに対し、PoS は「 nonce 探索を行うのはランダムに指定されたノード」で「信用という資産(steak)を重視」します。

「ノード」はブロックチェーンのデータを保持している DB サーバもしくは、そのアプリです。そして PoSSsteak で、「資産」「利害関係」「差し出す」「提供する」といった意味を持ちます。

nonce 探索を行うノードはランダムとは言え、もちろん、どのノードでもいいわけではありません。データを登録したいノードや依頼されたノードの資産量によって確認するノード数が変わります。

ここで言う「資産」とは、イーサリアムの場合は(コインとしての)イーサリアム「保有量」と、それまでの取引量による「信用度」です。一言で言えば「実績重視」ということです。

これにより、信用度の低い(取引実績が少なかったり、保有イーサリアムが少ない)ノードの場合は、比例して多くのノードに nonce 探索依頼をし、そのチェックも多くのノードで行われます。

おそらく、「そもそも」の nonce 探索を使わない方法も出てくると思います。そのため、ブロックチェーンの技術と、暗号資産(ビットコインやイーサリアムのコイン)は別のものとして考えることが大事です。

その上で「環境問題」を見ると、暗号資産としての相場を煽るために問題にしている人が裏にいるように思えてなりません。

NFTとは = IPFS + ブロックチェーン?

さて、ここまでブロックチェーンIPFS の話しをしました。その仕組みの応用というかマッシュアップ(合わせ技)の新しい試みに NFT というものがあります。新型コロナの流行った 2020〜2021 年にかけて話題になりました。記憶に新しい方も多いかもしれません。

NFT を一言で説明すると「デジタル・データのオリジナルを所有していることを担保するもの」です。

概要から入り、詳細に行きたいと思います。

まず、NFT でデジタル作品を扱う良いところは 2 つあります。

  1. データのハッシュ値に対する「所有権の売買」が可能である。
  2. 「転売されても作者にマージンが行く」仕組みである。

これにより、コピーして転売しても「所有権」を持っていなければ、たとえデータの内容がまったく同じであっても違法コピーと断定できます。また内容をいじってハッシュ値が変わったとしたら贋作と断定できます。

具体的には「デジタル作品(データ)のハッシュ値」と「所有者」を紐付けたものをブッロクチェーンで管理します。

暗号通貨がウォレットからウォレットに移動したのをブロック・チェーンで追跡できる同じ仕組みを使って、コインの変わりに「所有権」を移動できます。この仕組みにより、作品のハッシュ値から現在の所有者を知ることができるのです。

NFT を「デジタル・データをコピーできない技術」と言っているメディアもありますが、違います。コピーできます。

しかし「100% 同じデジタル・データなのに、どちらが本物かを証明できるインフラ」が NFT なのです。技術と言わずインフラと呼んでいるのは、実装方法は問わないからです。

もちろんデメリットもあります。「作者がオリジナルであることを証明しないといけない」などです。これは、誰でも NFT でデータを公開できるため、勝手に NFT 化されることがあるからです。

NFT の仕組みを理解するのに必要なポイントが 4 つあります。

  1. ファイルのハッシュ値
  2. 公開鍵と秘密鍵による暗号化・復号と署名
  3. ブロックチェーンの DB による取引記録(変更が不可能な取引台帳)
  4. IPFS による半サーバレスなコンテンツの配布

これらは本記事で説明済みですが、理解していると NFT は以下のようなものであると説明できます。

  1. デジタル作品(データ)にシリアル番号を埋めてハッシュ化した値を「トークン」とする。
  2. トークンもしくはシリアル番号付きデータを、著者(作家もしくは著作権関係者など)の「秘密鍵」で署名する。
  3. トークンの所有者と署名ファイルをブロックチェーンで管理する。
  4. 著者の「公開鍵」によって署名が確認でき、所有者も確認できる。

トークンについては後述しますが、これによりネットに出回っているデジタル作品の「公式」な所有者が確認できます

つまり、データのハッシュ値(ここではトークン)および著者の公開鍵による検証が通れば、そのデータは改竄されていない(偽物でない)ことが確認できるのです。

そして、そのハッシュ値(トークン)を専用のブロックチェーンの DB で確認することで、その作品の「公認の所有者」であることが保証されます。

投資における NFT は、この所有権(トークン)を絵画や骨董品と同じ仕組みで売買しているのです。

しかし、NFT と暗号資産を組み合わることで、その従来の絵画や骨董品の売買といったものと違うメリットが出てきます。

おそらく、その組み合わせの最大のメリットは、その後、NFT 作品が転売されても作家にマージンが入るということでしょう。(NFT サービスによって異なりますが、後述するイーサリアム・ベースの NFT の場合は仕組み上、できるはずです)

これは、古本など中古品商売で泣いていた作家さんを救済できる可能性を秘めています。このことを聞かされず NFT を勧めてくる業者・出版さんがいたら作家さんは要注意です。不要なマージンを抜かれていると思います。

NFT のデータは、一般的に IPFS 上のネットワークやブロックチェーンで共有され、作品自体はチップや QR コードの入った物理的な媒体で提供されたり、トークンを持っている人のみダウンロードできるサーバで提供されたりします。これもサービス会社によって違います。

恐れずに言うと、NFT は作家がデジタル作品に「証明書」を添えることで、作者の公開鍵により「鑑定書」(もしくは「保証書」)の役割を果たし、現在の所有者をブロックチェーンで確認できる「仕組み」です。

「インターネット」や「ブロックチェーン」同様、NFT という商品や特定サービスや会社を指すわけではありません。インフラの仕組みの 1 つです。

このように、NFT は「所有者を特定できる仕組み」により、コピーされて内容が 100% 同じデータが市場に出回ったとしても「贋作」と認定できることが強みです。もちろん、同じ作品でハッシュ値が違えば、そもそも「贋作」ですし、ブロックチェーンの DB 上の所有者が違えば「盗品」です。

NFT と言えど、対象データは著作物です。そのため、必要であれば違法コピーに対する逮捕につなげる情報にも使えます。

そのため NFT の本来の目的は以下の 2 点と言えます。

  1. デジタル作品を所有することに価値を見い出すコレクターを保護するためのもの。
  2. デジタル・アーティストの作品に対するリスペクトを示すもの。

しかし、現在は、日本でのラッセンに代表される「絵画商法のように使える」と、これに目を付けた企業が「後生大事に使いもしないデュエルカードに大金を出すような人々をターゲット」に参入しているので注意が必要です。本来の目的は「デジタル作品に対するファンのリスペクト」であることを念頭に置いてください。

NFT の意味

NFT とは Non Fungible Token の略で「『等価交換できないもの』のためのトークン」という意味です。

ちまたでは「非代替性トークン」と言われるので、「コピーできないもの」的な誤解が生まれているのだと思います。

ここでいう「等価交換できない」(Non Fungible)の「等価交換」(Fungible)について先に説明します。「トークン」の説明は、そのあと行います。

まず、「等価交換」(Fungible)とは、金や銀などのように「形が違っていても同じ質量であれば同じ価値を持つため交換可能である」ということです。

つまり、100g の金の塊と 100g の金の指輪は同じ金の値段を付けられる(価値がある)ということで、その場合に Fungible と言います。

同様に、10 枚の 100 円玉と 1,000 円紙幣は交換可能なので Fungible つまり「等価交換可能」と言えます。また、為替レートに合わせてドルと円の交換や、ドルとビットコインの交換はできるので Fungible となります。

元々はラテン語の fungi(そのものを楽しむ、価値を見い出す)から来ており、「形が変わっても楽しめる、価値がある」ものの意になりました。(ちなみに、真菌の fungus とは語源が違い、別のものです。真菌の fungus はスポンジと同じ語源の spongos から来ています)

逆に言えば、装飾や造形といった「形」に価値がある場合などは、Non Fungible ということになります。

例えば 100g のプラスチックと有名モデラーが組み立てた 100g のガンプラは「等価交換できない」(Non Fungible)ものと言うことになります。絵画なども、同じ質量の絵具と紙とは「等価」ではありません。

同様に、16 桁のハッシュ値と、それを並べ替えた値は「等価ではない」(価値が違う)ので Non Fungible となります。逆に 16 進数のハッシュ値と同じ値の 10 進数のハッシュ値は「等価」(価値が同じ)なので Fungible となります。

身近な例で言うと、1,000 円札の通し番号が異なっても同じ 1,000 円の価値を持つのが Fungible です。しかし、通し番号が 0000001 など、番号に価値を感じる場合は Non Fungible となり 1,000 円(等価)ではなくなるのです。

つまり Non Fungible Token は「『等価交換できないもの』のためのトークン」という意味になります。

転じて「唯一無二を示すためのトークン」となり、誤解を招きかねない「非代替性トークン」とカッコ付けた日本語名が付いているのです。

ちなみに、話題のイーサリアムはコインなどの Fungible トークンと、一意性を持った Non Fungible トークンを発行することができます。

では、肝心の「トークン」とは何でしょう。

トークンの意味

「トークン」ですが、これも一言で説明すると「同じ価値観を持つもの同士でのみ・・通用する・価値を持つ何かの発行物」をトークンと言います

その「何か」は何でもいいのです。例えば、ゲームのコイン、遊園地の入場チケットや銀行のワンタイム・パスワードなどのランダムな数値です。

そして「同じ価値観を持つもの同士でのみ・・通用する」というのは、例えばモノポリーのお金をゆうちょ銀行に持っていっても振り込めないようなものだったり、USJ のチケットでは TDL に入場できなかったりするようなものです。

我々の業界で言えば、アクセス・トークンは同じサービスでは価値があり、異なる環境ではだたのランダムな数値でしかないのと同じです。

シリアル番号による価値化

NFT の詳しい仕組みの話しの前に、シリアル番号と価値についても少し説明します。

トレーディング・カードゲームなどでは、個数限定のカードが発行されたりすることがあります。「1/100」(100 枚中 1 枚目)といったシリアル番号が振られているアレです。アートの世界ではシルクスクリーン作品や版画の作品などでも見かけます。

これは「複製可能な作品にシリアル番号を付けることで付加価値を付けている」のです。

さて、「複製可能な作品」の代表格と言えばデジタル作品です。

データのコピーなんて誰でもできてしまいますし、コピーガードとして DRM なども有名ですが、ガードが外れてしまえば同じことです。

このこと(DRM 解除)は、そもそも違法ですし、何よりデジタル作品を作る作家さんの収入を減らすことにもなりかねません。しかも、デジタルであることから、どれがオリジナルなのかも判断が難しくなります。

例えば、自分の好きな作家さんが亡くなり、未発表の描き下ろしデジタル・イラストがネットに公開され、その作品にとても感銘を受けたとします。しかし、ネットに公開されている以上、誰でもローカルに保存できてしまいます。

では、デジタル作品を「作品」として存在させるにはどうすれば良いのでしょう。

NFT は、その 1 つの可能性を示すものと言えます。

例えば、デジタル作品・作者による署名ファイル・公開鍵などをセットにしたものをチップやメモリに焼き、「使用していたペン先」や「髪の毛」など、なんでもいいので付加価値を付けて物理的に n 個、セットとして作成します。レイヤーデータなども付いていたら最高の付加価値だと思います。

そして、各々のセットの作品にはシリアル番号が描かれてあり、そのデータのハッシュ値を作者の秘密鍵で署名したもの、もしくはデータと秘密鍵をセットでハッシュ化したものをトークンとして確認できるようにするなどです。

NFT のサービスによってはセットからワンタイム・パスワードも確認できるようにして、それらを使ってサーバや IPFS ネットワークを参照すると作品が閲覧できるようになっていたり、物理的なセットではなく単純にオンラインでデータをダウンロードするタイプがあったりと、ここら辺はサービスによって異なります。

データのシリアル番号、ハッシュ値と所有者の追跡ができれば、物理・オンライン、方法論は何でもいいのです。

そして、各セットを作品としてオークションにかけるのです。もちろん 1 点いくらで売っても構いません。

落札・購入した人は、このセットの所有者となりトークンと紐付けられブロック・チェーンの DB に保存・共有されます。

いくらで売られたかは関係なく、あくまでも「トークンの所有者が誰であるか」が確認できるようになっているのです。

支払いは現金でも仮想通貨でも構わないのですが、「支払い」「ブロックチェーンへの記録」「NFT 情報を記録できる」「転売された時にマージンを作家に送る設定ができる」などを 1 つでできることから Ethereum が多く使われます。

NFT の仕組みを知らなくても、知っておかないといけない重要なことがあります。それは NFT は著作権(複製権や著作隣接権)の譲渡ではないことです。

つまり、あくまでも物理的に発行されたセットと、その「トークンの所有を示すも」のである、と言うことです。

「お金を払ったんだから、その NFT 作品のグッズを作ったりビジネスしても良い」と言う考えは「CD を買ったから俺のもの。だからコピーして売っても良い」「グッチのバッグを買ったから私のもの。だから同じ柄のカバンを自分で作って売っても良い」と言う考えと同じで、思いっきり違法です。

また、作者非公認で勝手に NFT として出す業者も出てくるでしょう。

購入する側は作者公認なのかを確認する必要がありますし、デジタル・アート作家も「よく知らないけど秘書が勝手にやりました」的な結果にならないように勉強が必要です。公開・秘密鍵によるデータの署名の仕方くらいは知っておいた方がいいのではないでしょうか。

NFT が話題になったのは BeepleBeeple-Crap 名義で有名な Mike Winkelmann 氏が NFT 作品群をオークションに出したところ、総額 75 億円で落札されたことからです。

これが、ビットコインなどの暗号通貨(仮想通貨)の投資家の「NFT は次のビジネスになる」と投資対象としても話題になっていたり、俺様暗号通貨の発行に躊躇ちゅうちょして出遅れていた企業が、暗号通貨よりわかりやすい商材ということもあり「オタク相手の古くも新しいビジネス」の匂いを感じ張り切っているからなのです。

そのため、「いま NFT が熱い」と購入を薦められたら「将来、高い値段が付くから、自己投資として 1 枚は持っておくべき」とラッセンの絵の購入を薦められるようなもの、と考えて良いと思います。

しかし、金額だけがメディアに取り沙汰されるのですが、Beeple 氏は 2007 年から "Everydays" と言う作品シリーズで「毎日」欠かさず 1 作品をネットに上げることを 14 年以上続けて来たのです。「振り込めない詐欺」を繰り返してきた氏に対するファンの気持ちが値段に反映したものなのです。

つまり NFT で作品を出したから売れるというものでもないのです。

しかし、これは DLsiteとらのあなで作品を出しても同じことです。

逆に言えば、ファンが付いた場合は、よりファンごころをそそるサービス(付加価値)を NFT では提供可能であるということでもあります。

何度か言及していますが、イーサリアムなどを使ったタイプの NFT では転売されると作家にマージンが入るものがあります。つまり、いまのようにデジタル漫画や動画をオンラインで購入しても、それが NFT であれば中古として転売できるし、転売されても作家にマージンが入る世の中になる可能性がある、ということです。

(テレビでジブリ作品が定期イベントのように流れますが、放送されるたびにジブリ・スタジオや宮崎駿先生にいくら入るのか調べてみてください。また、なんとか屋やブック・なんとかで売られている中古本や中古 DVD が売れるたびに、作家にいくら入るかも調べてみてください。ビックリすると思います)

そのため、「お気に入りの作家さんをファンとして支援する 1 つの形」としては、NFT は、とても価値のある仕組みであり、デジタル・データのオリジナル(原本)性を担保する新しい仕組みでもあるのです。

ハッシュ関数の衝突(コリジョン)とセキュリティ

そんな便利なハッシュ関数ですが、「メッセージダイジェストのコリジョン」(異なる入力値なのにハッシュ値が同じという「衝突」)が悩みのタネです。つまり、「改ざんされているのにハッシュ値が変わらない」状態です。

しかし、上記記事のように特定のアルゴリズムでハッシュ値が衝突してもアルゴリズムを変えると衝突しません

ハッシュ値の衝突と回避

アルゴリズムを変えると「衝突しない」と言いましたが限りなく本当に近い嘘ですが、本当です。それでは以下の md5sha1 の検証をご覧ください。

MD5 の衝突(検証と実証)
検証実証withPHP
<?php
// MD5 で衝突するサンプルデータ
$str1 = '4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518'
      . 'afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2';
//              ↑                                      ↑
$str2 = '4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518'
      . 'afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2';
//              ↑                                      ↑

// バイナリに変換
$bin1 = hex2bin(trim($str1));
$bin2 = hex2bin(trim($str2));

// 衝突させる
$algo  = 'md5';
$md5_a = hash($algo, $bin1);
$md5_b = hash($algo, $bin2);
echo ( $md5_a === $md5_b ) ? '衝突しました' : '衝突していません', PHP_EOL;

// 別のアルゴリズムで確認
$algo   = 'sha1';
$sha1_a = hash($algo, $bin1);
$sha1_b = hash($algo, $bin2);
echo ( $sha1_a === $sha1_b ) ? '衝突しました' : '衝突していません', PHP_EOL;

/* 出力結果 */
// 衝突しました
// 衝突していません
SHA-1 の衝突(検証と実証)

SHA1 の衝突はデータサイズが大きすぎるので paiza.IO で動作サンプルを作れませんでした。簡単なスクリプトとローカルで実行してみた結果結果を載せます。

検証スクリプト
<?php

$url_pdf1='https://shattered.io/static/shattered-1.pdf';
$url_pdf2='https://shattered.io/static/shattered-2.pdf';

$algo = 'sha1'; //衝突する
echo hash($algo, file_get_contents($url_pdf1)), PHP_EOL;
echo hash($algo, file_get_contents($url_pdf2)), PHP_EOL;

$algo = 'md5'; //衝突しない
echo hash($algo, file_get_contents($url_pdf1)), PHP_EOL;
echo hash($algo, file_get_contents($url_pdf2)), PHP_EOL;
exit
実行結果
$ php -a
Interactive shell

php > $url_pdf1='https://shattered.io/static/shattered-1.pdf';
php > $url_pdf2='https://shattered.io/static/shattered-2.pdf';

php > $algo = 'sha1'; //衝突する
php > echo hash($algo, file_get_contents($url_pdf1)), PHP_EOL;
38762cf7f55934b34d179ae6a4c80cadccbb7f0a
php > echo hash($algo, file_get_contents($url_pdf2)), PHP_EOL;
38762cf7f55934b34d179ae6a4c80cadccbb7f0a

php > $algo = 'md5'; //衝突しない
php > echo hash($algo, file_get_contents($url_pdf1)), PHP_EOL;
ee4aa52b139d925f8d8884402b0a750c
php > echo hash($algo, file_get_contents($url_pdf2)), PHP_EOL;
5bd9d8cabc46041579a311230539b8d1
php > exit

md5sha-1 のセキュリテイについて

先日(2018年夏頃)、とある居酒屋の隣の席で「md5 は破られたから安全ではない」という会話を耳にしました。詳しくは聞いてませんが、「パスワードがバレちゃう」的な話しでした。

しかし、調べてみたら厳密には破られたわけではないようです。いや、確かに破られてはいるんですが。

と言うのも、ハッシュ・アルゴリズムが「破られた」(break)と言われる場合3つの意味があり、業界によって使い方が違うので注意が必要そうです。

  1. ハッシュ前の元の値を計算で出せるようになった
    • インパクト:大。身元がバレる。
  2. ハッシュ値を衝突させる効率的な方法を見つけた
    • インパクト:中。身元はバレないが、なりすましされる。
  3. ハッシュ値が衝突する異なる2つの値を見つけた
    • インパクト:少。単体を狙ったなりすましには有効。

🐒   ちなみに、上記の「身元がバレる」と「なりすましされる」の違いですが、ここでは「(ハッシュ値からの逆算で)パスワードがバレてログインされた」と「(ハッシュ値が衝突する)違うパスワードでログインされた」、みたいな違いを指しています。
例えば、「ハッシュ値が衝突するパスワードを見つけた」としても、それは(少なくとも)1つのサービス内において起きることです。その反面、「ハッシュ値からパスワードが逆算できる」となると、同じパスワードの他のサービス全てにアクセスできることになります。(「衝突」に関しては上記「ハッシュ関数の基本と特徴」を参照してください。)
なお、ハッシュ値の衝突を探すことを「攻撃」(attack)と呼んだりしますが、前述のブロック・チェーンなどのように、ハッシュ値の衝突を探すこと自体は全て悪意のあるものではないことを念頭においてください。

どうやら「md5 が破られた」というのは2番目の「衝突する値の効率的な探し方」を指しているようです。先の md5sha-1 の衝突の検証実証例も、その手法を使って発見された値です。

現在(2020年4月)でも、やはり md5sha-1 も「ハッシュ値から引数の値は逆算できない」状態ではある(1番目の状態は破られていない)ようです。しかし...

増える MD5、SHA-1 脱獄者

しかしながら、時代は「脱 MD5」を経て「脱 SHA-1」に動いており、そして SHA-2 全盛のいまは SHA-3 に変わろうとしています。

例えば、Apple 社内で移植・開発していた OpenSSL「Apple 版 OpenSSL」を OpenSSL 098-76.200.2 で開発をめました。その、主な理由が「SHA-1 をベースにしていたから」です。

同時に、SSL/TLS の暗号通信に使うライブラリ(ハッシュ関数や暗号関数を担うライブラリ)も、 ベースを 「Apple 版 OpenSSL」から「LibreSSL」に macOS High Sierra(OSX 10.13)から切り替えました。

For this reason, the programmatic interface to OpenSSL is deprecated in macOS and is not provided in iOS. Use of the Apple-provided OpenSSL libraries by apps is strongly discouraged.

OpenSSL | Transmitting Data Securely @ developer.apple.com より)

ご利用の macOS がどちらのライブラリを使っているかは、ターミナルから $ openssl version コマンドで確認できます。

🐒   「開発を止めた」というだけで、Apple 版 OpenSSL の旧バージョン「OpenSSL098-76.200.2」(2016 年版)は Mojave (OSX 10.14.6) の公開ソースコードには、現在でも存在しています。

また、最近では SSH 接続ツールの OpenSSH も v8.3 から、SHA-1 を使った公開鍵の署名は「将来的に無効になる」旨の表示がデフォルトになりました。

The OpenSSH 8.3 release is out. This primarily a bug-fix release with a handful of minor new features. It does, however, carry a prominent notice that ssh-rsa signature algorithm will be disabled in "a near-future release".

OpenSSH 8.3 released (and ssh-rsa deprecation notice) | LWN.net より)

🐒   元記事が素人向けにわかりやすく書いていないこともありますが、いくつかの記事で SSH で RSA 公開鍵が使えなくなるなるような記載がありますが、違います。
ssh-rsa というのは、SSH 通信において SHA-1 を使って作成された RSA 公開鍵の「署名ファイル」のことで、SSH でログインすると接続先サーバーに保管される署名ファイルのことです。RSA 暗号自体のことを指すわけではありません。

なぜ、みんな「脱 MD5」「脱 SHA-1」を目指しているのかと言うと、とある・・・論文のせいです。

先の sha-1 の衝突実証ですが、そのデータは Google が見つけたものです。その手法は、発見から 10 年以上前に発表されたとある・・・論文をベースに世界の暗号学者や Google が改良を重ねたもので、Google のクラウドりょくを利用すれば 13 万米ドル(約 1,400 万円)程度で衝突を発見できることを証明したのです。

たかが 1つの衝突に 1,000 万円以上かかるというのは、個人としては大きな金額かもしれません。しかし、大企業が広告費を億単位でかけるのはザラであることを考えると、決して大きい金額というわけでもないことがわかります。

逆に言えば、とあるサーバーの、とあるユーザーの SSH 接続をターゲットにした場合、10 数万ドルもあればハッキングできてしまう可能性があるということです。そして、それだけのコストをかける価値のある情報を持った企業や行政機関は狙われる可能性がある、ということでもあります。

とある女性暗号学者の衝撃論文

md5 は以前よりオワコンと言われていたのですが、ダメチンと言われる大きなキッカケとなった、いや、むしろとどめを刺した 2 つの論文があります。

王 小雲(Wang Xiaoyun)さんという中国の山東大学の女性暗号研究者が 2004 年の中旬に発表した論文と、同年末に発表した論文です。

CRYPTO と呼ばれる世界的な暗号学会があるのですが、その 2004年の学会で発表され、話題をさらいました。

しかし、2004 年の CRYPTO 登壇者一覧を見ても、王(ワン)さんの名前の登壇記録がありません

どうやら運営側から「んなこたーない」と論文を却下されたため登壇できなかったそうです。

「それならば」と急遽きゅうきょ生徒を連れてアメリカまで飛んで行き、学会の発表後に行われるランプセッション(持ち時間 15 分程度の発表、学会版 LT)で、目の前でハッシュ値の衝突を見せたところ驚かれ、話題となったそうです。特に MD4 に関しては、コンピューターなしでも衝突を見つけることができたからです。

しかし、彼女の英語がわかりづらいのと論文の内容が難しく、周りも「なんかすごいことが起きてるっぽい」という状態だったそうです。ところが、同年末から翌年頭(2004 - 2005 年)にかけてさらなる衝撃的な論文を発表します。

SHA-1 の衝突を見つけるアルゴリズムの論文です。

かねてより SHA-1 の脆弱性を指摘していた暗号・情報セキュリティの巨匠で「シュナイアーの法則」でも知られるブルース・シュナイアー氏が 2005 年 2 月に、この論文を認めたことで、一気に注目のまと・・になります。総当たりで最低でも 2^80 回の処理が必要だったものが、理論上 2^69 回で衝突を発見できるからです。

そして、今度は CRYPTO 学会の方から彼女を招待し、2005 年の CRYPTO に登壇依頼します。ところが、またもや登壇できないということがわかりました。VISA の発行手続きが遅れたからです。

このことは、この論文の解析が難しく検証も遅れていたため、彼女の登壇を心待ちにしていた暗号学者だけでなく、シュナイアー氏も憤慨ふんがいしている記事を書いたくらいの話題性がありました。

その後、時間はかかったものの各種論文も認められ、暗号学会において王(ワン)さんは無事、認知されたそうです。当時の暗号学者たちは、この彼女の論文をパズルを解くようでワクワクしたそうです。

で、結局一番強いアルゴリズムはどれなのよ?

王さんの衝撃論文の発表後、GOOGLE による攻撃(衝突)の検証実証などにより、MD5 や SHA-1 だけでなく SHA-2(SHA-224〜SHA-512 の総称)の見直しが計画されました。

NIST(アメリカ国立標準技術研究所)が次世代 SHA となる SHA-3 のシリーズを作るべく公募したところ、従来の SHA-1 や SHA-2 とは根本的に思想の違う「Keccak」(ケシャック, ケチャック)と呼ばれるアルゴリズムが優勝し SHA-3 に採用されることになりました。そして採用から3年の期間を経て FIPS と呼ばれる連邦情報処理標準に制定されました(FIPS PUB 202)。なお、SHA-3 には SHA3-224SHA3-512 だけでなく、可変長で出力される SHAKE128SHAKE256 も含まれます。

そのため、2020/10 現在、OS やプログラム言語間で互換性の高いハッシュ・アルゴリズムで一番堅牢なのは「SHA3-512」と言って良いと思います。

SHA-3 の注意点としてリリース時期があります。実は Keccak が採用された後、SHA-3 として FIPS に制定されるまでの間に仕様の変更がありました。そのため、KeccakSHA-3 では出力結果が異なります。

つまり、ハッシュ関数のライブラリが制定後の更新をしておらず Keccak == SHA-3 の古い仕様ままだと、同じ SHA3 でも異なったアルゴリズムを使っているので出力結果が異なると言うことです。

どちらのアルゴリズムを利用しているかは、実際に「ハッシュ値の例」を元に計算して確認するのが早いと思われます。SHA-3 を利用する場合は以下をテストに含めるか、アプリの初期化時に確認するのがいいでしょう。

Keccakの場合
$ echo -n '' | openssl sha3-224
(stdin)= f71837502ba8e10837bdd8d365adb85591895602fc552b48b7390abd
FIPS_PUB_202準拠の場合
$ echo -n '' | openssl sha3-224
(stdin)= 6b4e03423667dbb73b6e15454f0eb1abd4597f9a1b078e3f5b5a6bc7
ブルートフォースおまえもか

さて、閑話休題。

つまり、「効率的に衝突する方法は見つかった」ものの、md5sha-1 でハッシュ化されたパスワードが流出しても「オリジナルのパスワードが計算で出せるわけではない」ということです。

ところがブロックチェーンの台頭により、やはり md5sha-1 は危険とは言えるようです。

と言うのも、ブロックチェーンのプルーフ・オブ・ワーク、俗に言うマイニングと呼ばれる作業が、まさに「ハッシュ値の衝突を探す作業」だからです。(ブロックチェーンの概要は前項の「ハッシュ関数とブロック・チェーン」参照)

マイニングは、基本的に総当たり攻撃の手法を使うわけですが、先の論文を応用すれば他より早くマイニングができることになります。中国のマイナー(マイニングする人)が多いのも、おそらく論文が中国語で読めたからなのかもしれません。たぶん。

同じハッシュ値の改ざん作業でも、ブロックチェーンを崩すよりはマイニングした方が直接的にお金(暗号通貨)を得られるし、そのぶんブロックも堅牢になっていくという良いところ取りなのが、仮想通貨(特にビットコイン)が広まった理由とも言われます。

逆に言うと「その衝突させるノウハウやインフラは悪意を持って改ざんするのにも使える」ということでもあります。そういう意味でも、やはりクリティカルな情報は計算コストが高いとはいえ sha-256sha-512、可能なら sha3-512 を使った方が安全であるとは言えそうです。

それでも md5 は使いやすく軽量であるため、頻繁に使い捨てされるようなものには依然有用です。やはり、結局のところ機能や特徴をきちんと理解した上で、コストと相談した運用の方針によると思います。

🐒   SHA-1 の後続である SHA-2 は、SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224, SHA-512/256 などの総称です。

ハッシュ値のベストな提供方法

以上のことから、「セキュリティの強度」や「同一性の確実度」を高めるには、以下の3点を同時に提供するのが効果的とわかりました。

  1. 複雑な計算が必要な、長いハッシュ値を提供する(SHA256 など)
  2. 異なるアルゴリズムのハッシュ値も一緒に提供する(SHA512MD5 など)
  3. データの長さ(ファイル・サイズ)を提供する

OS のイメージ・ダウンロードで SHA-1MD5 などの複数ハッシュ値を提供しているのは「SHA-1 ハッシュが使えない人のため」なのかと思っていましたが、どうやらそれだけではないようです。というのも、SHA-1MD5 の両方といった複数のアルゴリズムのハッシュ結果を「単一の改ざん」で衝突させるのは難しいからです。

最近は、SHA-1MD5 の変わりに sha-256 のハッシュ値と GPG などの署名を同時に提供するのが主流なって来ています。これは異なるアルゴリズムのデータを提供するのと同じ考え方がベースにあります。sha-256 の、より堅牢なハッシュ値と、ハッシュ値を秘密鍵で暗号化した署名を提供することで、さらに難しさを増しています。sha-256 による「データが壊れていないか」の確認と、署名を相手の公開鍵で検証することによって出どころと中身を保証するとを同時に行えるからです。

さて、3番目の「データ・サイズ」ですが、ウィルス本体 + 衝突用データ もしくは 改ざんデータ + 衝突用データ と言ったデータが埋め込まれた場合の対策です。と言うのも、オリジナルのデータと同じハッシュ値にさせつつ悪意あるデータを埋め込んで、かつ同じサイズにするには、とても大変な労力(コスト)を必要とするからです。

アルゴリズムの種類と長さ

いまや CSV のように小馬鹿にされる MD5 ですが、SHA-1, SHA-256 などのメジャーどころ以外に、どんなアルゴリズムがあるのか気になりました。

そこで PHP の hash_algos() 関数 でサポートしているハッシュ・アルゴリズム一覧を出力したところ「こんなにハッシュ関数(のアルゴリズム)ってあるの?!」とビックリ。

アルゴリズム一覧を見て、「ってか MD2 なんてあったんだ!」と知ったと同時に「MD2 って MD5 と同じ 16 バイト長(128bit= 32 桁の HEX 文字列)なんだ!」と気付きました。

調べてみると英語版の Wikipedia にはハッシュ関数のアルゴリズム一覧があり、その数たるや各々のアルゴリズムの仕組みを把握する気力さえ失せる勢い。(LGTM 頂いたので翻訳を始めたものの途中でバテてしまいました。)

そこで、各々のアルゴリズムはどれくらいの長さの値を返すのか調べ、一覧にしてみました。(ついでに速度も)

Multibase(ハッシュ値の n 進数圧縮と規格)

さて、ここまで読んでいただいて「え?16 進数の『数値の文字列・・・』ってことは、64 進数の Base64 とかの n 進数にすればもっと短く表現できるんじゃね?」と思ったかもしれません。

実は私も思いました。「a-zA-Z0-9 に記号を足して 64 文字が ASCII の限界なら漢字を使えばいいじゃない。どうせ UTF-8 なんだし」と。

そして、おふざけで漢字 8118 文字を使って 8118 進数(Base 8118)で表現してみたところ MD5 は 10 桁まで圧縮できました。

$ php ./sample.php
Number of characters:   8118
Original String:    This is a sample string to be hashed.
Pure MD5 hashed string: baad33e1e97f316b9750c27c86bf64d6
Multibyte base encoded: 䙔倁屩劷䋾彨䏔䂌䤘剒

しかし、薔薇や檸檬どころか醤油すら漢字で書けるか微妙な私には使い物になりませんでした。特に 8118 進数に使った文字も共通ではない(適当に選んだ)ためです。

ところが、同じようなことを考える人はいるもので「Base N(N 進数)で使われる文字を制定しよう」という動きがあります。すでに Base64 に関してはインターネットの制定団体である IETFRFC-4648 で制定したものがありますが、この概念をさらに拡張したものです。

具体的には、ハッシュ値の頭に識別コードを加えるという仕様です。このコードにより、どの文字を使ってエンコードされたのか(何進数のハッシュなのか)がわかるので、デコードできる(任意の進数の数値に戻せる)ようになります。

例えば、以下のハッシュ値を見せられた場合、コメント(#)がなければデコードできません。つまり文字列から数値に戻して使うことができなくなります。

4D756C74696261736520697320617765736F6D6521205C6F2F # base16 (hex)
JV2WY5DJMJQXGZJANFZSAYLXMVZW63LFEEQFY3ZP           # base32
3IY8QKL64VUGCX009XWUHKF6GBBTS3TVRXFRA5R            # base36
YAjKoNbau5KiqmHPmSxYCvn66dA1vLmwbt                 # base58
TXVsdGliYXNlIGlzIGF3ZXNvbWUhIFxvLw==               # base64

そこで頭に 1 文字のプレフィックス(接頭辞)を加えて、それを識別子として使います。(上記と見比べてみてください)

F4D756C74696261736520697320617765736F6D6521205C6F2F # base16 F
BJV2WY5DJMJQXGZJANFZSAYLXMVZW63LFEEQFY3ZP           # base32 B
K3IY8QKL64VUGCX009XWUHKF6GBBTS3TVRXFRA5R            # base36 K
zYAjKoNbau5KiqmHPmSxYCvn66dA1vLmwbt                 # base58 z
MTXVsdGliYXNlIGlzIGF3ZXNvbWUhIFxvLw==               # base64 M

これは "12345678" という文字列の数値を渡された場合に「何進数かわからない」と考えればピンとくるかもしれません。感覚として 16 進数の場合は 0x、10 進数の場合は 0d、2 進数の場合は 0b と付けるのと似ています。

このような仕様を「Multibase プロトコル」と呼んでいます。2021/07/16 現在、制定および検討されているものは以下の通りです。

Multibase(2021/07/16)
encoding,          code, description,                                              status
identity,          0x00, 8-bit binary (encoder and decoder keeps data unmodified), default
base2,             0,    binary (01010101),                                        candidate
base8,             7,    octal,                                                    draft
base10,            9,    decimal,                                                  draft
base16,            f,    hexadecimal,                                              default
base16upper,       F,    hexadecimal,                                              default
base32hex,         v,    rfc4648 case-insensitive - no padding - highest char,     candidate
base32hexupper,    V,    rfc4648 case-insensitive - no padding - highest char,     candidate
base32hexpad,      t,    rfc4648 case-insensitive - with padding,                  candidate
base32hexpadupper, T,    rfc4648 case-insensitive - with padding,                  candidate
base32,            b,    rfc4648 case-insensitive - no padding,                    default
base32upper,       B,    rfc4648 case-insensitive - no padding,                    default
base32pad,         c,    rfc4648 case-insensitive - with padding,                  candidate
base32padupper,    C,    rfc4648 case-insensitive - with padding,                  candidate
base32z,           h,    z-base-32 (used by Tahoe-LAFS),                           draft
base36,            k,    base36 [0-9a-z] case-insensitive - no padding,            draft
base36upper,       K,    base36 [0-9a-z] case-insensitive - no padding,            draft
base58btc,         z,    base58 bitcoin,                                           default
base58flickr,      Z,    base58 flicker,                                           candidate
base64,            m,    rfc4648 no padding,                                       default
base64pad,         M,    rfc4648 with padding - MIME encoding,                     candidate
base64url,         u,    rfc4648 no padding,                                       default
base64urlpad,      U,    rfc4648 with padding,                                     default
proquint,          p,    PRO-QUINT https://arxiv.org/html/0901.4016,               draft

「(え?比較に使うなら関係ないじゃん。むしろ 1 文字長くなってるし)」と感じるかもしれません。

この規格がもたらすメリットは、使っているハッシュ・アルゴリズムに脆弱性が発見された場合のバージョン・アップ時に互換性を持たせることができることです。つまり、頭の数文字を見るだけで、「アルゴリズム」「ハッシュの長さ」「エンコードの種類」がわかるようになるのです。

もう少し具体的に行きましょう。

例えば、"multihash" の文字列を SHA2-256 のアルゴリズムを使ってハッシュ化した値の場合は 16 進数で以下になります。

"multihash"をSHA2-256でハッシュ化した16進数の値
9cbc07c3f991725836a3aa2a581ca2029198aa420b9d99bc0e131d9f3e2cbe47

この場合、16 進数であることを示すために f を頭につけます。上記対応表に照らし合わせると 16 進数の小文字の場合は f だからです。

16進数小文字のハッシュ値である
f9cbc07c3f991725836a3aa2a581ca2029198aa420b9d99bc0e131d9f3e2cbe47

しかし、これではどのアルゴリズムを使ったハッシュ値かわかりません

そこで、SHA2-256 のアルゴリズムを使った場合は A を最初に付けるというル俺様ルールを設けたとします。その場合、最終的に以下のようになります。

16進数小文字のSHA2-256ハッシュ値である
Af9cbc07c3f991725836a3aa2a581ca2029198aa420b9d99bc0e131d9f3e2cbe47

「(俺様ルールて。そんな実装で大丈夫か?)」と思ったあなた。もぅ、お分かりでしょう。「神は言っている、アルゴリズムの種類も制定して欲しい」と。

はい、同じ団体が「Multihash」という規格を制定しています。

基本的に以下のような TLVtype-length-value)と呼ばれるフォーマットになっています。

  • <ハッシュアルゴリズムの種類><データのバイト数><データ(ハッシュ値)>
    • 8 ビット(2バイト)の符号なし整数によるアルゴリズム・コード
      • 8 ビット(2バイト)の符号なし整数によるデータのバイト数 (ハッシュ値の頭 n 桁だけ渡される場合があるため)
        • データ(ハッシュ値)
  • 122041dd7b6443542e75701aa98a0c235951a28a0d851b11564d20022ab11d2589a8
    • SHA2-256
      • 32 文字(=0x20
        • ハッシュデータ 41dd7b6443542e75701aa98a0c235951a28a0d851b11564d20022ab11d2589a8

実は、先述のビットコインのトークンや IPFS の CID は、ハッシュ値のフォーマットに MultibaseMultihash を使っています。

長さを知ったところで何?

ですよねー。実は、私は SQLite31INTEGER PRIMARY KEY フェチなのです。

さら・・で SQL 文も書けないくせに、「SQLite3」と聞かれれば「主キー♥️」と答えるくらいです。

これは、SQLite3 の場合は DB をキー検索する際に「DB の PRIMARY キー(主キー)を INTEGER 型にすると最もパフォーマンスが良い」というのを盲信しとるのです。(INT 型でなく INTEGER 型)

元々 SQLite3 では rowid で検索するのが一番速いとされます。rowid とは、SQLite では行番号のことです。DB に行(レコード)が作成されると 64 bit/8 byte(HEX 値で max 16桁)の行 ID が自動で割り振られます。

Searching for a record with a specific rowid, or for all records with rowids within a specified range is around twice as fast as a similar search made by specifying any other PRIMARY KEY or indexed value.
ROWIDs and the INTEGER PRIMARY KEY | SQL As Understood By SQLite @ SQLite.org より)

特定の rawid でのレコード検索、もしくは特定の範囲内の全てのレコードを複数の rawid で検索をする場合、PRIMARY KEY やインデックスを使った場合に比べて2倍近い速さの速度が得られます。(筆者訳)

この時、テーブルの主キーが rowid と同じであれば、主キーでも同じ速度が得られるのです。

厳密には、テーブル作成時に主キーの列を INTEGER PRIMARY KEY で定義し、テーブルが1次元配列(1つのキーに対して1行が構成される DB)だった場合、つまり複数の主キーを持たない場合に各行の主キーが rowid のエイリアスとなる仕様を使います。(この時 INTEGER PRIMARY KEY でなく INT PRIMARY KEYINT で宣言するとダメなので注意)

If a table has the primary key that consists of one column, and that column defined as INTEGER, exactly INTEGER in any cases, such as, INTEGER, integer, etc., then this primary key column becomes an alias for the rowid column.

表(テーブル)の主キーが1つの列で構成され、かつその主キーが大文字・小文字関係なく INTEGERINTEGER, integer, INTteger, etc.)と定義されていた場合、この主キーは rowid 列のエイリアスになります。(筆者訳)

主キーが rowid のエイリアスになるサンプル

実際に INT で宣言したテーブルと INTEGER で宣言したテーブルの SQLite3 内のデータ構造の違いを確認してみたいと思います。SQLite3 自身の挙動であるため、プログラム言語に依存しない証拠に bash で書いてみたいと思います。sh zsh どのシェルでも大丈夫だと思います。

テーブル作成の SQL 文は CREATE TABLE [テーブル名]([テーブル構成]) です。SQL のコマンドは、大文字・小文字は関係ありません。(CREATEcreate も同じ)

まず、主キー名は「myID」とし、主キーの宣言には PRIMARY KEY を指定します。

そして、主キーの型を INT で宣言したテーブル名を table1INTEGER で宣言したテーブルを table2 とします。table1 が従来のテーブル、table2 が倍速のテーブルです。

また、オプションの NOT NULL で「空の値は許さない」ことにし、挿入するデータは両テーブル同じものとしてみたいと思います。

なお、挿入順を見るために myID の値をわざと降順にしていることに注意してください。(SQLite3 v3.22.0)

#!/bin/bash

name_db='sample.db'

# Create table 1 and 2 and insert same data
sqlite3 $name_db <<'HEREDOC'
  create table table1(myID INT not null primary key, myName Varchar);
  insert into  table1 values(100, "First  value with ID 100");
  insert into  table1 values(10,  "Second value with ID 10 ");
  insert into  table1 values(1,   "Third  value with ID 1  ");

  create table table2(myID INTEGER not null primary key, myName Varchar);
  insert into  table2 values(100, "First  value with ID 100");
  insert into  table2 values(10,  "Second value with ID 10 ");
  insert into  table2 values(1,   "Third  value with ID 1  ");
HEREDOC
echo '- DB created with sample.'

次に、DB の中身を確認してみます。SQL 文 select rowid, * [テーブル名]rowid の表示および全てのデータを選択しています。

まずは、主キーが rowid のエイリアスではない table1 です。

table1の中身確認
# .header on と .mode column は見栄えを整える SQLite3 コマンドです
echo '- Table1'
sqlite3 $name_db <<'HEREDOC'
.header on
.mode column
  select rowid, * from table1;
HEREDOC
出力結果(1列目がrowid)
- Table1
rowid       myID        myName
----------  ----------  ------------------------
1           100         First  value with ID 100
2           10          Second value with ID 10
3           1           Third  value with ID 1

rowid 順に並んでおり、rowidmyID の値が同じでないことを確認してください。

このテーブル構成の場合、myIDmyName を検索すると、まずは myIDrowid を紐づけるために自動作成されるハッシュテーブルを検索して該当する rowid を見つけます。次に、見つけた rowid に該当する myName の値を返します。つまり myIDrowidmyName とワンクッション入ることになります。(これ自体は RDB として正しい動きです)

次に、rowid が主キーのエイリアスになっている table2 です。

table2の中身確認
echo '- Table2'
sqlite3 $name_db <<'HEREDOC'
.header on
.mode column
  select rowid, * from table2;
HEREDOC
出力結果(1列目がmyID)
- Table2
myID        myID        myName
----------  ----------  ------------------------
1           1           Third  value with ID 1
10          10          Second value with ID 10
100         100         First  value with ID 100

SQL 文で select rowid, * としているのに rowidmyID と同じ(エイリアス)であること、そして1列目の myID 順に並んでいることを確認してください。(DB の登録順は 100→10→1)

このテーブル構成の場合、myIDmyName を検索すると、直接 rowid(のエイリアスの myID)の myName を返します。

rowid が主キー

この、主キーが rowid のエイリアスになる仕様により「主キー名」から「rowid」への変換ステップが省略され、テーブルの主キーが rowid と同じ扱いになるので速い、という塩梅です。

元々はバグだったそうなのですが下位互換のため残され、仕様となったそうです。

そして、主キー(PRIMARY KEY)が rowid と同じということは、任意の rowid を振れるということでもあります。

となると、SQLite3 で扱えるキー(rawid)の最大長である 8 バイトの数値(64 ビット。文字でいうと 16 文字の HEX 文字列)をいかに作るかが問題になります。

Except for WITHOUT ROWID tables, all rows within SQLite tables have a 64-bit signed integer key that uniquely identifies the row within its table. This integer is usually called the "rowid".

ROWIDs and the INTEGER PRIMARY KEY | CREATE TABLE @ SQLite.org より)

【筆者訳】
WITHOUT ROWID で定義されたテーブルを除いて、SQLite のテーブル内のすべての行には、テーブル内の行を一意に識別する 64 ビットの符号付き整数キーを持ちます。この整数は通常「rowid」と呼ばれます。
(筆者注: 64 ビットの符号付き整数とは -9,223,372,036,854,775,8089,223,372,036,854,775,807 の範囲の整数。HEX の場合は -8000000000000000 7fffffffffffffff

やはり、王道の自動連番が一番楽で、キーの衝突もなく効率的です。基本設計がしっかりしていれば、これが一番だと思います。

しかし、(私の)ユーザにとっては変なバイアスがかかる忖度が発生することがわかりました。

というのも、歴史的事情でデータの ID を DB の主キーと同じにしているというダメちん仕様のため、当然の結果として「情報の ID 番号が時系列に並ぶ」、つまり登録順に並ぶのです。すると(私の)ユーザは無意識に内容の優劣を決めてしまうのです。

「ID が小さい → 古参の情報」「ID が大きい → 新参の情報」といった具合です。そのため、(私のようなオッチャン層は特に) ID が小さい方が質が良い・有益であると思い込んでしまうのです。観測すると、実は打ちやすい・覚えやすいだけで、番号に質は無関係だったのですが。

かといって、対オッチャン対策のためにランダムな ID の対応表を別途作るのも面倒なのです。また、すでに現行データの ID は周知されているので入れ替えは容易ではありません。

そこで、近々起こりうるであろうデータの棚卸しに備えてハッシュ関数を使って ID を固定長にできないかと模索をはじめました。

Hash now, don't you cry

ここからは、SQLite3 の主キーが rawid と同等の場合に、主キーの最大長である 8 バイトの数値をハッシュ関数でいかに作成したかの具体的な内容になります。

PHP の場合、fnv1 系(fnv164 もしくは fnv1a64)のアルゴリズム一発で 8 バイト(64 bit, 16 桁の HEX 文字列)のハッシュが作れます。

そのため、古いキーを単純にハッシュ化して再登録すれば楽に移行できます。しかも、速い。

$key_prime_new = hash('fnv164', $key_prime_old);

ところが、いくつか問題があるのです。

現在この記事で話題にしている DB が扱っているデータは登録後の変更はありません。いや、むしろ変更してはいけないものなのです。

ところが自由度の高い設計であるためか、自分の独断と都合により何故か勝手に値を変えちゃう一部の層(上流やオッチャン層)がありました。その層に弱い上司からコッソリと指示を受けるたび、バックアップから元に戻す作業のイタチごっこが定期的に発生していました。

これではいつかは盛大なポカをやりかねません。仕組みとしてのポカよけが必要と感じ、もう少し工夫をしたいなと思いました。

昨今の行政の改ざん問題でも提案されている文書のハッシュ化を ID として取り入れたいと考えたのです。

つまり、イメージではこういうことです。

// 旧IDでデータ取得
$value = fetchValueFromDB($key_prime_old);
// データ → ハッシュ化(16進)→ 10進 → 整数
$key_prime_new = (integer) hexdec(hash('fnv164', $value));

先の「要オッチャン対策 DB」は「ユーザが測定したデータの値と同じ値のものを DB から探し、関連情報(ヒットした行のデータ)を返す」用途に使われています。ピピピッピッと打つか、ピッとバーコードを読み込むと、ポッとデータが表示されるシンプルなものです。

つまり、ユーザ側(クライアント側)で測定したデータをハッシュ化して渡し、 DB(サーバー側)は受け取ったキーを検索すれば速度改善・改ざん防止・オッチャン対策の良いとこ取りになります。DB もシンプルに実装・構成できます。

ここで、もし1つ前の登録データのキーもハッシュ化してフィールドに内包(列を追加)すれば、ブロックチェーンに近い考え方になりますよね。そもそも SQLite なので、同期されたデータは各クライアント(ユーザ)のローカルにありますし。

さて、この方法でテストしたところ、今のところ1億件ちょっとの既存データで衝突もなく問題なさそうなのですが、1つのアルゴリズムに依存したくないという気持ちもありました。そう、ハッシュ値の衝突が怖いのです。

そもそも、この程度(10 年で 1〜2 億件程度)のデータ量であれば、SQLite3 の 1844京6744兆737億件以上も使える 8 バイト(64ビット)のキーをそのまま使うのはもったいないのです。大は小を兼ねるとは言え、貸し倉庫クラスなのにデズニーランド・クラスのスペースを使うようなものです。

十分な年数に耐えつつ、衝突に関しては鳩の巣原理(鳩の数より巣箱の数が少ないと、1つ以上の巣箱で衝突が起きる原理)は少なくとも網羅できるバイトの長さを検討した結果、最長 4 バイト長(= 42.9 億個)のキーとしました。

そして、先の「衝突しても別のアルゴリズムだと衝突しない(可能性が高い)」屁理屈を取り入れて、「4 バイトの A 型ハッシュ値 + 4 バイトの B 型ハッシュ値 = 8 バイトのキー」を作ってみたいと思いました。

具体的には 4 バイト長のハッシュ・アルゴリズムである crc32fnv132 の2つをあわせて以下のような Primeキーの算出を考えました。

$key_prime_hex = hash('fnv132', $value) . hash('crc32', $value);

厳密に言うと CRC-32 はハッシュではなくチェックサムなのですが、計算コストをケチってしまいました。これが後に懸念を産むことになります。

  • crc32 @ Wikipedia(日本語)
  • fnv-1 32 @ Wikipedia(英語)

先の fnv-1 64(8 バイト長のアルゴリズム)単体と比べて2倍くらい速くなるのですが、移行のための一括登録のデータ量が 500 万件を越えたあたりから、むしろ遅くなりました。アルゴリズムの組み合わせにもよると思いますが、アルゴリズムによっては初期化に原因がありそうです。

しかし、本番データは一括 INSERT させる予定です。つまり、一旦 DB をダンプ出力して主キーを整形しておき、データを新規 DB に一括で INSERT させる感じです。

また、実際の用途では新規登録時の速度はさほど必要とされておらず、登録頻度も高くありません。むしろ登録より日々の引き出し時の速度が速くなったことのほうが改善感があって良いと思います。

手元の2億件弱のサンプル・データで、このアルゴリズムの組み合わせで衝突は発生しませんでした。しかし、アルゴリズムの仕様を調べていくうちに確信が持てなくなりました。

非暗号学的ハッシュに悩む

CRC はチェックサムなのでデータが連番の場合に弱いのと、fnv-1 系(Fowler–Noll–Vo)のアルゴリズムは非暗号化型ハッシュ、つまり暗号学的ハッシュ関数ではないため、スティッキーステートと呼ばれる問題を孕んでいます。(暗号学的ハッシュについては上部「ハッシュ関数の基本と特徴」参照)

Sticky State – Being an iterative hash based primarily on multiplication and XOR, the algorithm is sensitive to the number zero. Specifically, if the hash value were to become zero at any point during calculation, and the next byte hashed were also all zeroes, the hash would not change. This makes colliding messages trivial to create given a message that results in a hash value of zero at some point in its calculation. Additional operations, such as the addition of a third constant prime on each step, can mitigate this but may have detrimental effects on avalanche effect or random distribution of hash values.
Non-cryptographic hash | Fowler–Noll–Vo hash function @ Wikipedia より)

【筆者訳】
スティッキーステートFowler–Noll–Vo 関数は、主に乗算と XOR に基づく反復ハッシュであるため、このアルゴリズムは数値ゼロに敏感です。具体的には、ハッシュ値が計算中のいずれかの時点でゼロになり、続くバイトのハッシュがすべてゼロであった場合、ハッシュは変化しません。これにより、計算のある時点でハッシュ値がゼロになるメッセージが与えられた場合、衝突するメッセージを簡単に作成できます。各ステップで第3の素数を定数として追加するなどの操作で、これを軽減できますが、アバランシェ効果またはハッシュ値のランダム分布に有害な影響を与える可能性があります。

筆者も良く理解出来ていないのですが、fnv-1 は主にハッシュテーブルやチェックサムで使用するために速度を優先して設計されたハッシュ関数として開発されたため、暗号学的ハッシュ関数と比較してランダム性に欠けるということのようです。つまり fnv-1 も CRC と 似た連番に弱い問題を持っていたのです。

この DB の仕組みも、ある種のハッシュテーブルと似てはいるものの、この CRC と fnv-1 の組み合わせではコンテンツの高速な確認には使えても ID としては厳しい予感がします。なんたるジレンマ。

となると、より分散性の高いアルゴリズムである SHA などの暗号学的ハッシュの一部を使った方が良いことがわかりました。

問題はコスト(速度)です。

しかし、記事上部の各アルゴリズムの測定速度を見てもわかるように PHP7 の場合 100 万回ぶん回して 0.n 秒の差です。PHP8 だとさらに数倍速くなるので、微々たる差だと思います。

そのため、CRC-32 や fnv-1 を使うよりは Git のコミット ID のように SHA-256, SHA-512 や SHA3-512 などのハッシュ値の頭 4 バイトを使うのがよろしいかと思われます。

🐒   私はそうすることにしました。この仕組みが認められるころには PHP8 もリリースされると思うし。いつか Wikipedia のデータをぶっ込んで検証してみたいと思います。どうも、変更できない仕組みが一部で都合が悪いらしく採用されなさげ、ってかその仕事も辞めちゃったので実装することもなさげです。たくさんの「いいね」をいただけたので模索してよかったと思います。

イメージとしてはこんな感じ
$len   = 8; //4バイトのHEX文字列長
$value = fetchValueFromDB($key_prime_old);
$hash1 = substr(hash('sha3-512', $value), 0, $len);
$hash2 = substr(hash('sha512', $value), 0, $len);

// 8バイトの主キー
$key_prine_new = (integer) hexdec($hash1 . $hash2); // 実際には ± の符号確認のため $hash1 の一番左の文字をゴニョゴニョしてます

(え? 「もう、KVS でいいじゃん」って?ま、まぁ…ねぇ、、、枯れた技術を好むのも歳なんですかねぇ)


  1. SQLite3とは、著作権の発生しないオープンソースのデータベース管理システムです。名前からわかるように SQL の構文でデータにアクセスでき、リレーショナル・データベース(RDBMS)の1つです。
     特徴としては「本体も動作も軽量である」ことと「サーバーを立てずに使えること」があります。サーバー型でないため、複数ユーザーや複数アプリからの同時利用には向かないのですが、アプリごとにデータを保存する場合に威力を発揮するタイプです。
     モバイル・アプリやゲームなどのダウンロードやキャッシュ・データであったり、macOS の場合は標準でインストールされており、Spotlight などの検索用の DB としても使われています。(sqlite3 -help で確認可能)
     リアルタイムに激しく変動するデータでない場合、アプリ起動時に本艦となるサーバーからデータ・ベースをダウンロードしてローカルに保存することで、ネットワークのトラフィックを減らしたり、オフラインで利用させたり、レスポンスの向上に使われたりする便利なプログラムです。
    関連リンク:SQLite @ Wikipedia 日本語 

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
253
Help us understand the problem. What are the problem?