セーブに作品データの指紋を入れ、一字でも違えば変換せずに断る
Saves carry a fingerprint of the game data and refuse, unconverted, if one character differs
D12-4-T24-save-and-data-fingerprint・技術・日本語入力でプレイする仕組み
台本のファイルの末尾に改行を一つ足しただけで、昨日のセーブは読めなくなります。
読み込んだ 98 ファイルの FNV-1a を畳んだ 16 桁が、セーブに入っている値と一致しないからです。
前の回（T23）で、同じセーブと同じ入力からは同じ返事が返る、と書きました。
ただしそれは、同じ作品データの上での話です。
言い換えを 1 本足せば、同じ入力が別の意図に着地しうる。段の条件を変えれば、セーブの中のフラグの意味が変わる。
そこで、セーブが「どのデータの上で作られたか」を、64 ビットの指紋で持たせています。
この回の位置と、前後の回#
区切り: T03〜T24 日本語入力を解いて返すまで（22 回のうち 22 回目）
先に読むとよい回: T23（同じ入力に同じ出力）・T07（同じベクトルを出す ONNX Runtime）
次に読む回: T25（入力欄の中の IME）
名前 — FNV-1a#
- 正式名
- FNV-1a（Fowler–Noll–Vo hash function の変形の一つ）。指紋の取り方は content fingerprint（内容の指紋）
- 略称
- FNV
- 日本語
- FNV ハッシュ。content fingerprint は「内容の指紋」「内容ハッシュ」
- 初出
- FNV は、Glenn Fowler と Phong Vo が 1991 年に IEEE POSIX P1003.2 委員会へ査読のコメントとして出した案に、Landon Curt Noll が改良を加えたもの（Wikipedia と IETF の草案 "The FNV Non-Cryptographic Hash Algorithm"〈draft-eastlake-fnv〉による）。FNV-1a の変形を誰がいつ出したかは確かめられませんでした。content fingerprint という語の初出も確かめていません
FNV-1a とは#
FNV-1a（Fowler–Noll–Vo hash function の変形の一つ）とは、バイトの列を、一つずつ畳んでいく単純なハッシュです。
64 ビット版の式はこうなります。
h = offset_basis
for each byte b:
h = h XOR b
h = h × FNV_prime (mod 2^64)
offset_basis = 14695981039346656037（0xcbf29ce484222325）
FNV_prime = 1099511628211（0x100000001b3）
FNV-1 は、同じ式で掛け算と XOR の順が逆です。
IETF の草案は、一般の用途には FNV-1a を勧めています。
offset basis は、"chongo <Landon Curt Noll>" で始まる 32 オクテットの文字列に、初期値 0 の FNV（FNV-0）をかけて作った値で、任意に選んだ数ではありません。
32・128・256・512・1024 ビットの版もあり、作者たちは特許を主張せず、参照実装は public domain です。
ふつうの使われ方は、ハッシュ表の鍵、重複の検出、軽いチェックサム、DNS やコンパイラの中の文字列の表などです。
速く、実装が数行で、表を持たず、どの言語でも同じ値が出せる。
よく知られた弱点もはっきりしています。
暗号学的なハッシュではありません。衝突は狙って作れます。
攻撃者が鍵を選べるハッシュ表に使うと、わざと同じ値に集めて遅くする攻撃（hash flooding）を受けます。
また、下位のビットの混ざり方が弱く、表の大きさが 2 の冪だと偏ることがあります。
うちの FNV-1a#
core/AdvInput.hpp の 2 つの関数です。
// 64bit FNV-1a（決定論・環境非依存。版の照合と記録に使う）
inline std::uint64_t Fnv1a64(const std::string& S, std::uint64_t H = 1469598103934665603ULL)
{
for (unsigned char C : S) { H ^= C; H = 1099511628211ULL; }
return H;
}
inline std::string HexOf(std::uint64_t V)
{
static const char D = "0123456789abcdef";
std::string Out(16, '0');
for (int i = 15; i >= 0; --i) { Out[i] = D[V & 0xF]; V >>= 4; }
return Out;
}
std::uint64_t の掛け算は 2^64 で回るので、mod を書く必要はありません。
文字列は std::string のバイト列（UTF-8）のまま畳みます。
16 進は小文字・ゼロ詰め 16 桁に固定し、printf の書式に頼りません。
初期値を見てください。
1469598103934665603 です。
標準の 14695981039346656037 から、末尾の「7」が一桁落ちています。
これについては「名前どおりでない所」で書きます。
作品の指紋の取り方#
作品を読み込む AdvSessionLoader.hpp は、読んだファイルを全部、パスと中身の hash の表に控えます。
bool readTracked(const std::string& Rel, std::string& Out)
{
if (!LoadFile || !LoadFile(Rel, Out)) { return false; }
if (bTracking && (Rel.size() < 4 || Rel.compare(Rel.size() - 4, 4, ".bin") != 0))
{
Tracked[Rel] = HexOf(Fnv1a64(Out));
}
return true;
}
共通の言語資源（Game/common/adv/）は、鍵に "common:" を付けて同じ表に入れます。
.bin（焼いたベクトル）は外します。ベクトルは別の指紋で見ているからです（後で書きます）。
読み込みが成功したら、表を畳みます。
std::string All;
for (const auto& [Rel, Hex] : Tracked) { All += Rel + "=" + Hex + "\n"; }
ContentFingerprint = HexOf(Fnv1a64(All));
Tracked は std::map<std::string, std::string> なので、並びはパスのバイト順です。
「adv.json=0f8a329878ddebf8\n」のような行をパス順に連結し、もう一度 FNV-1a をかけた 16 桁が、作品の指紋です。
ポイントは、ディレクトリを列挙しないことです。
エンジンは作品のフォルダを走査しません。adv.json が指すファイルを読み、読んだものだけが指紋に入ります。
だから、読まない README を書き換えても指紋は変わらず、読む台本を一字でも変えれば変わります。
今日の値を、CLI の session-info で出しました。
指紋 492790bfabfe9b44、入ったファイル 98。
同じ計算を node（BigInt）で書き直すと、98 ファイルの hash が全部一致し、畳んだ値も 492790bfabfe9b44 になりました。98 ファイルで合計 1,211,076 バイトです。
C++ と JavaScript で同じ値が出るのは、FNV-1a がバイト列と 64 ビットの掛け算だけでできているからです。
セーブ adv-save/2#
セーブの頭はこうなっています（AdvSession.hpp の saveState）。
J["schemaVersion"] = "adv-save/2";
J["workId"] = WorkId;
J["contentFingerprint"] = ContentFingerprint;
J["interactionVersion"] = Engine.data.work.interactionVersion;
J["where"] = Engine.state.where;
…
workId は作品の id（adv.json の workId）。
interactionVersion は、入力の扱いの約束の版で、adv.json に整数で書きます（今日は 2）。
そのあとに、場所・相手・章・フラグ・手帳・既読の段・言い直しの回数など、進行に関わる全部が続きます。
新規 → 港 → 佐伯に 1 問、の後のセーブは 3,651 バイト、最上位の欄は 34 でした。
読み込みは、中身に触る前に 4 つを確かめます。
bool checkSaveCompatible(const nlohmann::json& J, std::string& outError) const
{
if (!J.is_object() || J.value("schemaVersion", "") != "adv-save/2")
{ outError = "ADV_SAVE_INCOMPATIBLE: schemaVersion (want adv-save/2)"; return false; }
const std::string SavedWork = J.at("workId").get<std::string>();
if (SavedWork != WorkId) { outError = "ADV_SAVE_INCOMPATIBLE: workId mismatch (…)"; return false; }
if (J.at("contentFingerprint").get<std::string>() != ContentFingerprint)
{ outError = "ADV_SAVE_INCOMPATIBLE: contentFingerprint mismatch (…)"; return false; }
if (J.at("interactionVersion").get<int>() != Engine.data.work.interactionVersion)
{ outError = "ADV_SAVE_INCOMPATIBLE: interactionVersion mismatch"; return false; }
return true;
}
（エラー文の括弧の中は略しました。）
一つでも違えば、変換も補完もせずに断ります。
断っても、いまのセッションの状態は変えません。元のファイルも消しません。
UE・CLI・ブラウザ版のサーバは、ADV_SAVE_INCOMPATIBLE で始まるエラーを見て、画面には中立な一文だけを出します。
今日、セーブの指紋を 0000000000000000 に書き換えて読ませると、こう返りました。
"error": "save load failed: ADV_SAVE_INCOMPATIBLE: contentFingerprint mismatch (save=0000000000000000, work=492790bfabfe9b44)",
"ok": false,
"publicMessage": "この記録は現在の版では使えません。最初から始めてください"
次に、作品データの写しで、佐伯の台本 scripts/saeki.json の末尾に改行を一つ足しました。
指紋は 492790bfabfe9b44 から 34dfa25b53bfb475 に変わり、元のセーブは同じエラーで断られました。
読み込まない README.md と acceptance.json に一字足しても、34dfa25b53bfb475 のままでした。
ほかの指紋#
同じ考え方の指紋が、あと三つあります。
- 入力の規則の hash（RulesHash）。共通の言語資源 input.json と、作品の inputPolicy の原文をつないで FNV-1a をかけます。セーブの照合には使わず、「どちらの話から確かめますか」と聞き返している途中の状態を、規則が変わっていたら捨てる判定に使います。
- 焼いたベクトルのモデルの指紋。vectors.bin（KADVVEC2）の頭に「e5-small.onnx=118308185,vocab.bin=4081385」のような、ファイル名とバイト数の文字列を入れます。hash ではありません。UE の起動のたびに 117 MB を hash するのを避け、バイト単位の改変は全件のコサインを測る embedcheck に任せる、という判断です（T07）。
- 配る組の manifest。adv-sim の実行ファイル・bake・モデルは SHA-256 で束ね、作品データはエンジン自身の指紋をそのまま使います。ブラウザ版のサーバは起動のときにこれを照合し、違えば起動しません。
なぜ暗号学的なハッシュでないか#
指紋が守るのは、事故です。
作品を更新したのに古いセーブを読んでしまう、別の作品のセーブを読んでしまう、片方だけ古いデータを配ってしまう。
相手は攻撃者ではないので、衝突を狙って作られる心配をしていません。
64 ビットの偶然の衝突は、この用途では気にしなくてよい確率です。
一方で、要るものもはっきりしていました。
- core はヘッダだけで、標準ライブラリと nlohmann/json しか使わない（T27）。SHA-256 を入れるには実装を持ち込むか、UE と Linux で別のライブラリを呼ぶことになる
- 読み込みのたびに 98 ファイル・1.2 MB を通すので、軽い方がよい
- 同じ値を node でも出せる（検査の道具は .mjs）
配る組の manifest だけ SHA-256 なのは、そちらは node の crypto がそのまま使え、配る物の取り違えを確実に落としたいからです。
名前どおりでない所 — FNV-1a#
式は FNV-1a どおりですが、初期値が標準と違います。
標準の offset basis は 14695981039346656037 で、core の値は 1469598103934665603。末尾の一桁が無い値です。
そのため、標準の FNV-1a のライブラリとは値が合いません。
"a" の 1 バイトで比べると、標準なら af63dc4c8601ec8c、うちは 44bd8ad473cd9906 です。
気づいたのは、core の単体テストを足したとき（10 月 18 日）でした。
いまは直さず、実装の値で固定しています。core-input-tests.cpp の注記です。
// 初期値は標準の FNV offset basis（14695981039346656037）ではなく末尾 1 桁の無い値。記録済みの hash と
// 揃えるため実装の値で固定する（標準値なら "a" は af63dc4c8601ec8c。Issue #67 の報告に記録）。
check(Fnv1a64("") == 1469598103934665603ULL, "fnv: empty is the offset basis");
check(HexOf(Fnv1a64("a")) == "44bd8ad473cd9906", "fnv: one FNV-1a step for 'a'");
直すと、全部のセーブと記録済みの hash が一斉に読めなくなるからです。
同じ実装を別の言語で書き直す人は、標準の値ではなく、この値を使ってください。
offset basis が「任意の数ではない」ことの意味（FNV-0 から導いた値）は、うちの値では失われています。単体テストの上では、指紋として困る性質は見つかっていません。
もう一か所、同じ定数を使う所があります。
状態の全探索（reach）の表の hash で、FNV で畳んだあとに MurmurHash3 の仕上げ（fmix64）と同じ定数で撹拌しています。
FNV だけだと下位のビットが偏り、線形探査の塊ができて、件数が増えるほど遅くなった（20 万件で毎秒 32,000 件 → 300 万件で毎秒 15,000 件）からです。上に書いた FNV の弱点を、実際に踏んだ例です。
弱点と、採らなかった案 — FNV-1a#
いちばん大きい弱点は、厳しすぎることです。
指紋は原文のバイト列から取るので、意味の変わらない書き換え（JSON の整形・末尾の改行・コメント）でも変わります。
作品を更新するたびに、それまでのセーブは全部使えなくなります。ブラウザ版のセーブも同じです。
新しい版で最初から遊び直してもらうことになる。今はそれを受け入れています。
二つ目は、外側ごとの読み込みの違いです。
UE のローダは、ファイルを FString に読み、UTF-8 に戻してから core に渡します。
BOM の付いたファイルがあれば、UE と CLI で指紋がずれるかもしれません。今日は UE の上で指紋を取っていないので、確かめていません。
三つ目は、指紋に入らない読み込みです。
読み込みの途中だけ控えるので、プレイ中に初めて読むファイルがあれば指紋に入りません（台本は読み込みのときに参照の検査で一度読むので、入っています）。
採らなかった案です。
- 旧いセーブを新しいデータへ変換する。どのフラグがどの意味に変わったかを、版ごとに書く必要があります。セーブの形を adv-save/2 に上げたとき（10 月 7 日）、旧形式との互換は作らないと決めました。
- JSON を正規化してから hash をとる（鍵の順・空白をそろえる）。整形では変わらなくなりますが、正規化の規則がもう一つの契約になります。
- 作品の版の番号を人が付ける。上げ忘れたとき、静かに古いセーブが通ります。指紋は忘れません。
- SHA-256 にする。上に書いた理由で、core には持ち込みませんでした。
セーブは、データとの組でだけ意味を持つ。
その組を、16 桁の一致で確かめています。
検索語#
FNV-1a hash
Fowler–Noll–Vo hash function
draft-eastlake-fnv
content fingerprint hash
『霧走町 流氷に眠る』の第一章はブラウザで、途中で保存しながら遊べます。プロフィールのリンクから試してみてください。