ZK-Hunt：全チェーンゲームが隠された情報を実現する新しい試み

—— イントロダクション ——#

ZK Hunt は、異なる ZK ゲームメカニズムと情報の非対称性を探求する RTS に似たオンチェーン PvP ゲームです。これは、全体の契約アーキテクチャ、ネットワークとクライアントの同期ロジック、ZK 証明の生成と検証に使用される circom を処理する MUD フレームワークを使用して作成されました。

このゲームは、2022 年の 0xPARC Autonomous Worlds のレジデンス期間中に構築され、その時に他の多くのチームがそれぞれの素晴らしいプロジェクトを研究していました。ここで完全なデモリストを見つけることができます。ZK Hunt メカニズムの短い要約が必要な場合は、ここで私のデモビデオを確認できます。

ZK Hunt は、最初はオンチェーンゲームにおけるプライベートな移動を実現する新しい方法に関する単純なアイデアに過ぎませんでしたが、レジデンス期間中に、異なる暗号構造を利用するメカニズムが追加され、新しいゲーム体験が開かれました。

開発中に、私はそれを完全な EFT（Escape from Tarkov）スタイルのゲームに拡張する方法についてのアイデアを持っていました。このゲームでは、プレイヤーは一定量の戦利品 / 装備を持って狩り場に入り、他のプレイヤーを殺して彼らの戦利品を奪い、他の人に殺される前に彼らの戦利品を「抽出」しようとします。しかし、時間が経つにつれて、このプロジェクトは ZK ゲームメカニズムの可能性を探求する媒体としての方が良いと気づき、最終的には教育資源としての役割を果たすことになりました。

したがって、この記事では、ZK Hunt に存在するさまざまなメカニズム、これらのメカニズムを実現するための具体的な技術、プライベートステートの周りで開発したいくつかの思考モデル、そしてこれらのメカニズムがどのようにより広く一般化されるかを紹介します。

私は、コアコンセプトを高いレベルで説明しつつ、技術的な側面についてもより深く掘り下げようとしていますので、この記事がこれらのテーマに対する異なる熟練度を持つ読者にとって有益であることを願っています。もし、どの部分が技術的な詳細に過ぎると感じた場合は、気軽にスキップしてください。なぜなら、後の部分では、述べた技術的な詳細に依存しないさらなる価値を見出すことができるかもしれません。

スマートコントラクト、暗号、ハッシュ関数、ZK 証明について基本的な理解があると良いでしょう。

免責事項：

MUD（1.x と 2.x の 2 つのバージョンは異なる）上に構築されているため、ZK Hunt の契約は ECS パターンに従います。MUD がこのパターンをどのように実現しているかについての詳細はここで確認できますが、高いレベルでは、ゲーム内のすべての「エンティティ」は一意の数値 ID（EVM 内の uint256s）として表され、エンティティの属性は異なるコンポーネント契約に保存されます。これらの契約にはビジネスロジックは含まれておらず（本質的にはエンティティ ID から値へのマッピングに過ぎません）、プレイヤーは異なるシステム契約と対話します。これらの契約にはビジネスロジックが含まれますが、エンティティの状態は含まれておらず、異なるコンポーネント契約から読み書きされます。

私が「契約」と言うときは、特定の状況に関連する特定の契約を口語的に指しています。通常、各状況で異なる場合があります。

ZK 回路の実装の探求は、あなたが circom 言語にある程度の精通を持っていることを前提とし、標準文書には含まれていないいくつかの新しい circom 構文も使用しています。簡潔にするために、以下の回路コードの一部は省略されています。

—— ジャングル / 平原の移動 ——#

以下のビデオは、ZK Hunt のコアメカニズムである公共 / プライベート移動の二分法を示しています。ビデオでは、左側のプレイヤー A と右側のプレイヤー B の 2 人のプレイヤーが見えます。各プレイヤーは、以前に生成したユニットを制御し、白い輪郭で強調表示され、もう一方のプレイヤーのユニットは赤で示されて敵であることがわかります。

移動は、目的地を選択し、パスを確認することで実行されます。各移動は個別のトランザクションとして提出され、前の移動が確認されると、新しい移動が提出されます。ZK Hunt は、1 秒のブロック時間に設定された EVM チェーン上で動作し、ユニットは 1 秒あたり 1 タイルの速度で移動でき、他のユニットのアクションは低遅延で処理されます。

この世界には、2 種類のタイルがあります。草で示された平原タイルと、木で示されたジャングルタイルです。平原を横断することは公開されており、これはプレイヤー B がプレイヤー A の位置の更新を見て移動している事実によって示されています。ジャングルに入ることも公開されていますが、ジャングルを横断することはプライベートであり、プレイヤー A はジャングル内のプレイヤー B の位置を見失い、疑問符で示された潜在的な位置の集合をシミュレートすることしかできません。再びジャングルから平原に戻ることは公開されているため、潜在的な位置の集合は崩壊します。

この動作は ZK Hunt の基礎です。ユニットには状態の断片（位置）があり、ゲーム内のアクションに応じて公開からプライベートに、再び公開に変わることができます。ユニットの位置がプライベートになると、それは完全に曖昧になるのではなく、時間とともに増加する可能性のある有限の曖昧さを持つようになります。これは、タイルベースの移動の制限性によるものです。これにより、他のプレイヤーはユニットの位置に対してある程度の信頼を持つことができ、彼らが早く行動すればするほど、その信頼は大きくなります。

このメカニズムがどのように機能するかを深く理解する前に、ZK 証明の入力 / 出力とコミットメントに関するいくつかの前提条件の理解を構築する必要があります。

ZK 回路の入力出力に関するいくつかの見解#

ZK 回路の circom コードでは、公共入力、プライベート入力、出力を定義できます。ここで、入力はユーザーによって提供され、出力は回路内部で行われるいくつかの計算の結果であり、これらの結果は証明を作成する際に証明プロセスを通じてユーザーに返されます：

template Example() {
    signal input a, b;
    signal output c;
    a + b === 7; // a + bが7に等しいことを確認
    c <== a * b; // a * bを出力
}
// aは公共入力、bはリストから省略されているためプライベート入力
component main {public [a]} = Example();

しかし、重要なのは、出力は実際には構文の抽象に過ぎず、基礎的には追加の公共入力として見なされます。基本的に、ZK 回路は一連の入力を受け取り、これらの入力間の数学的制約のセットが満たされているかどうかを確認し、唯一の出力は「真」または「偽」です。上記の回路は、機能的には次のように等価です：

template Example() {
    signal input a, b, c;
    a + b === 7; // a + bが7に等しいことを確認
    a * b === c; // a * bがcに等しいことを確認
}
component main {public [a, c]} = Example();

ここでの違いは、c が出力として定義されている場合、ユーザーは c の値を計算する必要がなく、証明生成中に回路内部で定義されたロジックがそれを行うため、使用される値が回路を満たすことを保証するのに便利です。

出力が実際には追加の公共入力であるという事実は、契約内の証明検証ロジックを確認する際に関連します。solidity 検証者は、一連の入力（証明自体とともに）を受け取り、このリスト内で回路コードで定義された出力が最初に現れ、公共入力がその後に続き、唯一の真の「出力」は「成功」または「失敗」です。

それにもかかわらず、概念的には公共入力と出力の間に違いが存在すると考えることは依然として有用です。特に、計算プロセス（状態遷移）の検証に関与する回路の場合、これらの回路には自然な入力（古い状態）と出力（新しい状態）が存在します。

ZK Hunt の回路において、公共入力は通常、以前の証明で計算 / 検証され、契約に保存されている値であり、出力は新しい証明内部で実行される計算結果であり、これらの結果はその証明によって検証され、契約に保存されます。

最後に理解しておくべきことは、ZK 証明の検証コストは一定であると考えられています（少なくとも groth16 などの特定の証明システムに対して）が、実際には公共入力の数に基づいて増加するため、オンチェーン検証を行う際に重要になる可能性があります。公共回路入力と出力の間に機能的な違いが欠如していることを理解する前に、すべての公共入力を出力に変換することでこのコストを最小化できると考えるかもしれませんが、上記の説明に基づいて、これは明らかに不可能です。

コミットメント手法に関するいくつかの見解#

コミットメントは、ゼロ知識証明（ZK proof）がユーザーが以前に「コミット」したいくつかのプライベート状態を検証可能に参照するために使用できるツールの一つです。これにより、検証者（オンチェーン検証の場合は、チェーンを観察するすべての人）にその状態を明らかにすることなく、ユーザーはコミットメント C を公共入力として証明に提供し、プライベート状態 s をプライベート入力として提供し、証明は内部で s から生成されたコミットメントを計算し、それが C と一致するかどうかを確認します：

template Example() {
    signal input state; // プライベート
    signal input commitment; // 公共
    // 'state'からポセイドンハッシュコミットメントを計算
    signal result <== Poseidon(1)([state]);
    result === commitment;
    // 回路の残りの部分は今や'state'の有効性を信頼できます
    ...
}
component main {public [commitment]} = Example();

証明を検証する際、検証者は公共信号の値を取得するため、提供されたコミットメント値が正しい（すなわち、ユーザーが以前に提出した値と一致する）かどうかを確認する際に、生成証明に使用された正しいプライベート状態値を使用したことを確信できます。

さまざまなコミットメントスキームを使用できますが、最も単純な方法は状態のハッシュ値を取ることです。ZK Hunt でポセイドンハッシュを使用する理由は、回路内での計算が他の一般的なハッシュ関数よりも効率的だからです。プライベート状態が十分に大きな範囲からランダムに選ばれた十分にランダムな値（例えば、秘密鍵やランダムシード）である場合、その値のハッシュを取るだけでコミットメントとして十分です。

しかし、状態が取り得る値の範囲が比較的小さい場合（例えば、1 から 10 の間の値）、攻撃者はこれらの値の結果コミットメントを計算し、ユーザーが提出したコミットメントと一致するものを見つけることで、対応する状態値を特定し、コミットメントのプライバシーを破ることができます。

このようなブルートフォース攻撃を防ぐために、コミットメントに「ランダム数」値を追加し、poseidon（状態、ランダム数）の形式を取ることができます。ランダム数は回路にプライベート入力として提供され、十分に大きな範囲からランダムに選ばれ、すべての可能なコミットメントを事前に計算することが不可能であることを保証し、状態のプライバシーを保持します。

ある証明が特定のプライベート状態のコミットメントを入力として受け取り、内部でいくつかのルールに基づいて状態を変更し、その後新しい状態のコミットメントを出力する場合、その証明は効果的に検証可能なプライベート状態遷移を表すことができます。証明の出力コミットメントを別の証明の入力として使用することで、時間の経過とともに一連のプライベート状態遷移を作成できます。

Snip20231013_70

まさにこれらのプライベート状態へのコミットメントと、時間の経過とともにコミットメントを更新するプロセスが、ZK Hunt における移動方法の核心を形成しています。この前提条件の理解を構築したので、今、4 つの異なる移動シナリオを見てみましょう：

1. 平原から平原へ#

Snip20231019_74

ユニットの位置は PositionComponent に保存されています。ユニットが平原を横断するために、プレイヤーは期待される新しい位置を PlainsMoveSystem（MoveSystem から継承）に提出し、このシステムは移動が有効かどうかを確認し、その後位置コンポーネント内のユニットの位置値を更新します。

この検証ロジックは、ユニットの古い位置と新しい位置の両方が平原タイルであり、新しい位置がマップ内にあり、移動が単一の基本ステップ（マンハッタン距離が 1）であることを確認します。ユニットの公開位置に対する更新は、すべてのプレイヤーのクライアントに反映されます。

2. 平原からジャングルへ#

Snip20231019_75

ジャングルに入るプロセスは上記と同じですが、契約は移動先の新しい位置が平原タイルではなくジャングルタイルであることを確認します。さらに、プレイヤーは新しいユニット位置に対するコミットメント（同様の方法でコンポーネントに保存されます）と、コミットメントが新しい位置から正しく計算されたことを示す ZK 証明を提出します。このコミットメントは poseidon (x, y, nonce) の形式を取ります。

ZK Hunt のマップサイズは比較的小さく（31*31 ですが、より大きく / 小さく設定できます）、これは可能な位置の総数が限られていることを意味します。したがって、コミットメントがブルートフォースで破られないことを保証するために、ランダム数を含める必要があります。もちろん、入口位置はすでに公開されているため、コミットメントをブルートフォースで破る必要はありませんが、将来の位置コミットメントにはそうではないでしょう。

このコミットメントは、プライベートな位置をコミットするのではなく、その後ジャングル内でプライベートに移動するための出発点として機能します。ランダム数はプライベートに保つ必要がある（なぜなら後で詳しく説明します）ため、契約が位置と一致するコミットメントを確認できるようにするために ZK 証明が必要です。回路は非常にシンプルです：

template PositionCommitment() {
    signal input x, y, nonce;
    signal output out;
    out <== Poseidon(3)([x, y, nonce]);
}
component main {public [x, y]} = PositionCommitment();

検証中、契約は x と y の入力値を提供し、出力のコミットメントを関連する PositionCommitmentComponent に保存します。この回路は PositionCommitment（JungleEnter ではなく、ある時点でそうであるため）と呼ばれます。なぜなら、他の状況で再利用され、公開された位置がコミットメントと一致するかどうかを確認する必要があるからです。

3. ジャングルからジャングルへ#

Snip20231019_76

ジャングル内で移動する際、プレイヤーは新しい位置を契約に提出するのではなく、新しい位置のコミットメントと、以前のコミットメントからの移動が有効であることを示す ZK 証明を提出します。これにより、他のすべてのプレイヤーはそのユニットが何らかの移動を行ったことを知っていますが、実際にはそのユニットがどの正確な位置に移動したのかはわかりません。

ZK 証明は、プライベートな位置から別のプライベートな位置への状態遷移を検証し、古い位置のコミットメントを参照し、新しい位置のコミットメントを生成します。したがって、ジャングルに入るときに提出された位置コミットメントから始まり、1 つの証明の出力コミットメントが次の入力となる任意の長さのジャングルを通る移動チェーンを作成できます。

新しい位置コミットメントの有効性は、古い位置コミットメントの有効性に依存します（ここでの有効性は、コミットメントがユニットが移動ルールに従って到達すべきではない位置を示さないことを意味します）。したがって、入口位置が公開されている場合でも、ジャングルに入るときに初期位置コミットメントを提出する理由は、契約が有効であることが知られているコミットメントから移動チェーンを開始するためです。

プレイヤー A の視点から見ると、ユニットの位置の曖昧さは、存在する疑問符によって視覚的に示されます。各疑問符は、ユニットが存在する可能性のある潜在的な位置を表します。ジャングルに入ったばかりのとき、ユニットが新しい移動を行った場合、彼らは入口タイルに隣接する任意のジャングルタイルに移動した可能性があります。もし彼らが再び移動した場合、彼らは以前の潜在的な位置に隣接する任意のジャングルタイルに移動した可能性があります。これが、あなたが見ている洪水充填の動作です。

移動の正当性を検証する JungleMove 回路は非常にシンプルです：

template JungleMove(mapSize, merkleTreeDepth) {
    signal input oldX, oldY, oldNonce, oldCommitment;
    signal input newX, newY;
    // MerkleDataBitAccessテンプレートの信号説明を参照
    signal input mapDataMerkleLeaf, mapDataMerkleSiblings[merkleTreeDepth];
    signal input mapDataMerkleRoot;
    signal output newCommitment;
    // 提供されたoldX、oldY、oldNonceが契約に保存されたoldCommitmentと一致することを確認
    signal commitment <== Poseidon(3)([oldX, oldY, oldNonce]);
    commitment === oldCommitment;
    // 移動が単一の基準ステップであり、マップ内に留まることを確認
    signal xDiff <== CheckDiff(mapSize)(oldX, newX);
    signal yDiff <== CheckDiff(mapSize)(oldY, newY);
    xDiff + yDiff === 1;
    // 新しいマップセルがジャングルタイプ（1）であることを確認
    signal bitIndex <== newX + newY * mapSize;
    signal tileType <== MerkleDataBitAccess(merkleTreeDepth)(
        bitIndex, mapDataMerkleLeaf, mapDataMerkleSiblings, mapDataMerkleRoot
    );
    tileType === 1;
    // 新しいnonceを計算し、新しいコミットメントを出力
    signal newNonce <== oldNonce + 1;
    newCommitment <== Poseidon(3)([newX, newY, newNonce]);
}
component main {public [oldCommitment, mapDataMerkleRoot]} = JungleMove(31, 2);

最初の部分は、古い (x, y) 値が本当にコミットされた値であることを確認します。oldCommitment 公共入力は、検証中に契約によって提供され、プレイヤーが古い位置について嘘をつくことができないことを保証します。

2 番目の部分は、CheckDiff を使用して各軸の古い位置と新しい位置の間の絶対差を計算し、差が 1 を超えないことを確認します。また、新しい値がマップ内にないことを確認します：

template CheckDiff(mapSize) {
    signal input old;
    signal input new;
    signal output out;
    signal diff <== old - new;
    out <== IsEqualToAny(2)(diff, [1, -1]);
    // 絶対差が1または0であることを確認
    signal isZero <== IsZero()(diff);
    out + isZero === 1;
    // 新しい値がマップの外に出ていないことを確認
    signal isOutsideMap <== IsEqualToAny(2)(new, [-1, mapSize]);
    isOutsideMap === 0;
}

各軸の CheckDiff は、ユニットの移動距離を単一のタイルに制限しますが、xDiff + yDiff === 1; 行は、ユニットが x 軸または y 軸のいずれかでのみ移動することを確認し、対角移動を防ぎます。

3 番目の部分は、新しい位置がジャングルタイルであることを確認しますが、ロジックは少し複雑なので、後で説明します。

4 番目の部分は、新しい位置コミットメントを出力します。移動が成功した場合、契約はそれをユニットの新しい値として保存します。

signal newNonce <== oldNonce + 1;
newCommitment <== Poseidon(3)([newX, newY, newNonce]);

新しいコミットメントのために使用される新しいランダム数は oldNonce + 1 であり、追加のプライベート入力として提供される新しいランダム値ではありません。これは重要な選択であり、後で議論するいくつかのメカニズムに影響を与えます。したがって、ジャングルに入るときに初期ランダム数をプライベートに保つ必要があります。

4. ジャングルから平原へ#

Snip20231019_77

ジャングルを離れるために、プレイヤーは契約にユニットのジャングル内の現在位置を明らかにする必要があります（契約はこの位置を知らないため）、それによってジャングルタイルから平原タイルへの移動が有効であるかどうかを確認できます。プレイヤーが自分のいるジャングルエリアの境界上の任意のジャングルタイルを提供するのを防ぐために、彼らは明らかにしたジャングル位置が契約に保存された位置コミットメントと一致することを証明する必要があります。

ただし、これは ZK 証明を提出する必要はありません。プレイヤーはユニット位置の（x, y）座標と位置コミットメントに使用されたランダム数を直接明らかにし、契約はこれらの値のポセイドンハッシュが保存された位置コミットメントと一致するかどうかを単純に比較します。ジャングルを離れることは位置の曖昧さを消し、ユニットの位置は他のすべてのプレイヤーに公開されます。

回路内マップデータの検査 - I#

ZK Hunt のマップタイルは平原またはジャングルのいずれかであるため、その状態は単一のビットで表すことができます（平原は 0、ジャングルは 1）。理論的には、これらの値を単一の整数にパッケージ化し、単一の uint256 で全体の 16 * 16 タイルマップを表すことができます。

ただし、circom の素数フィールドサイズの性質により、circom 信号は最大約 2^253.6 の値しか表現できないため、単一の信号は 253 の「有用な」情報ビットしか運ぶことができません。つまり、単一の信号で 16 * 16 のマップを表すことはできませんが、15 * 15 のマップを表すことはでき、これは ZK Hunt の最初のプロトタイプが行ったことです。

回路内で特定の（x, y）でのタイル値を確認したい場合、tileIndex を計算します。つまり、x + y * mapSize（この例では mapSize = 15）で、マップデータ信号入力を単一のビットを表す信号の配列に分解し、circomlib の Num2Bits () を使用して、その配列から tileIndex ビットを選択します（circom では O (n) 操作であり、O (1) ではありません）。以下はその例です（簡略版）：

var mapSize = 15;
var mapTileCount = mapSize * mapSize;
signal input x, y;
signal input mapData;
signal mapDataTiles[mapTileCount] <== Num2Bits(mapTileCount)(mapData);
signal tileIndex <== x + y * mapSize;
signal tileType <== SelectIndex(mapTileCount)(mapDataTiles, tileIndex);
tileType === 1;

回路内マップデータの検査 - II#

では、22 * 22 のマップのような大きなマップを表現したい場合はどうでしょうか？その場合、そのようなサイズのマップは 484 ビットを必要とするため、2 つの信号に収まります。最初の信号は前 253 ビットを保存し、2 番目の信号は残りの 231 ビットを保存します。これらの信号を「マップデータチャンク」と呼びます。回路内では、Num2Bits () を使用してこれらの 2 つのチャンクを信号配列に分解し、配列を接続し、配列から tileIndex 要素を選択します：

var mapSize = 22;
var mapTileCount = mapSize * mapSize;
var chunk1TileCount = 253, chunk2TileCount = 231;
signal input x, y;
signal input mapDataChunks[2];
// 注意：ConcatテンプレートはcircomlibやZK Huntには実際には存在しませんが、実装は簡単です
signal mapDataTiles[mapTileCount] <== Concat(chunk1TileCount, chunk2TileCount)(
	Num2Bits(chunk1TileCount)(mapDataChunks[0]),
	Num2Bits(chunk2TileCount)(mapDataChunks[1])
);
signal tileType <== SelectIndex(mapTileCount)(mapDataTiles, x + y * mapSize);
tileType === 1;

この方法を使用して、マップデータチャンクの数を増やすことで、より大きなマップを表現できます。ただし、マップデータチャンクは契約から公共入力として提供される必要があるため、マップが大きくなるほど、検証コストが高くなります。この問題を解決するために、マップデータチャンクをプライベート入力として渡し、チャンクに対する公開コミットメントに基づいて検査することができます。これにより、マップのサイズに関係なく、公共信号を 1 つだけ渡す必要があります。

重要な点は、circomlib が実装したポセイドンハッシュは最大 16 の入力しかサポートしていませんが、次のようにハッシュをリンクすることでこの問題を解決できます：poseidon (x1, x2, ..., x15, poseidon (x16, x17, ...))。

回路内マップデータの検査 - III#

この方法は、公共入力の数とマップのサイズ（タイルの総数）との線形増加の問題を解決しましたが、マップデータコミットメントを検証するために必要な回路内計算は依然としてマップのサイズに対して線形増加し、非常に大きなマップの場合、非常に大きな回路（多くの制限）を引き起こし、証明生成時間が長くなる可能性があります。

これを改善するために、マップデータチャンクに対する線形 / チェーンコミットメントをメルクルツリーコミットメントに置き換えることができ、回路内で単一のタイルを検査する必要がある場合、メルクルツリーに関連するブランチに関するハッシュを計算するだけで済むため、コストはマップのサイズに対して対数的な関係になります。

4oGlDSa

関連するマップデータチャンク（移動先のタイルを含むチャンク）と、チャンクからルートを再構築するために必要なメルクル兄弟ノードをプライベート入力として渡し、生成されたメルクルパスのルートを契約に公開入力として渡されたツリーのルートと照合します。

これが ZK Hunt が最終的に採用した方法であり、JungleMove 回路の第 3 部が行っていることです。MerkleDataBitAccess 回路を利用し、記述されたメルクルチェックを実行するだけでなく、マップデータメルクルリーフのビット分解を行い、提供された bitIndex で関連するタイル値を返します。

この実装にはもう 1 つの利点があります。タイルを含むマップデータチャンクに対してのみ Num2Bits () を実行し、すべてではなく、1 つのチャンク内のタイルの数から選択するだけで済むため（O (n) 操作）、この最適化は線形コミットメント方法にも適用できます。したがって、両者の主な違いは、コミットメント検証の効率です。

回路内マップデータの検査 - IV#

上記の例は、ZK Hunt での実装方法に一致する二分木を示していますが、実際には最も効率的なツリー構造の証明方法ではありません。回路内で 2 つの入力を持つポセイドンハッシュ（Poseidon (2)(...)）を計算するには 240 の制約が必要ですが、興味深いことに、16 の入力を持つポセイドンハッシュ（Poseidon (16)(...)）を計算するには 609 の制約しか必要ありません。したがって、二分木の代わりに六叉木を使用することで、最大のリターンを得ることができますが、これはいくつかの追加の実装の複雑さを伴います。

当時、私はポセイドン回路実装に関するこの事実を知らなかったため、二分木を選択しました。しかし、それを考慮しても、ZK Hunt がマップを表現するために使用するチャンクの数（31 * 31 の 4 チャンク）に対して、線形コミットメントとツリーコミットメントの間に違いはありません。どちらの場合も、それは単に Poseidon (4)(...) であり、最大 16 チャンクのマップに対しては正しいでしょう。

16 チャンクを超えて違いが生じる場合（線形コミットメントはチェーン状の複数のハッシュを必要とし、ツリーコミットメントは複数のレベルを必要とします）、私は直感的に、追加のメルクルロジックのオーバーヘッドにより、ツリーコミットメントが実際には線形よりも効率が低くなる可能性があると感じています。マップが十分に大きい場合にのみ、ツリーコミットメントがより効率的になるでしょう。ツリーコミットメントは ZK Hunt にとって過剰であり、線形コミットメントはほとんどのユースケースに十分である可能性が高いですが、それでも概念証明を持つことは良いことです。

ZK Hunt のマップデータは、回路にハードコーディングされているのではなく、回路に渡される入力として提供されているため、マップは任意の内容を持つように設計でき（各試合ごとに）、実際には時間とともに変化することができます。開発中に、プレイヤーがジャングルタイルを焼却し、新しいジャングルタイルが時間とともに自然に成長することができるというアイデアがありましたが、これを行うと、潜在的な位置表示の計算に使用されるロジックが破壊されます。

ここで説明された方法は、任意のタイプの公共データセットを回路に渡し、そこから選択するために使用できます。これは、武器のダメージ値、アイテムの価格、NPC の位置などである可能性があります。ZK Hunt は、データセットの各要素を単一のビットで表現します。なぜなら、それらは 2 つのオプションのいずれかでしかないからですが、実装を変更して、各要素を任意のビット数で表現できるようにすることができ、各要素が任意の数の値を取ることができるようになります。

最後に知っておくべき便利なことは、circomlibjs が生成できる solidity 実装のポセイドンは最大 6 つの入力しか受け入れられない（EVM のスタック深度が限られているためだと思います）ため、契約内で直接計算して作成または検証することはできませんが、もちろん ZK 証明を使用してこの問題を解決することができ、各ハッシュは最大 16 の入力を持つことができます。

ジャングル / 平原の移動の概要#

ある程度の一般化のレベルで、上記の移動システムは、ゲームにステルス領域、非ステルス領域、およびエンティティがこれらの間を移動する能力を持たせることを可能にします。特定の平原 / ジャングルのシナリオは、異なるタイプのゲームに再設計できます：

明るい領域と影の領域に置き換えることができ、そこでは特定の光源が世界に配置され、これらの光源が放射状に光を発し、固体障害物がこれらの光を遮ることによって影の領域を作成します（このアイデアは lermchair に帰属します）。光源が移動可能である場合（例えば、手持ちのランタン）、明るい領域は時間とともに更新される可能性がありますが、これはプレイヤーが移動せずに明るい領域から影の領域に移行するのを処理するための追加のロジックを必要とします（チェーン上の動的影投影計算は言うまでもありません）。
上記のアイデアに基づいて、非対称のマルチプレイヤーゲームを作成できます。例えば、隠れんぼや『デッドバイデイライト』のようなゲームで、常に公開位置にいる捜索者がいて、障害物によって遮られる視野領域を発生させます。隠れたプレイヤーがいて、彼らの位置は捜索者に対してプライベートに保たれ、視界に入るまで、彼らの位置は公開されず、追跡されやすくなります。
プレイヤーが特定の領域にロックされるのではなく、いつでも隠れることができるシステムを作成できます。位置に関係なく、ただし限られた時間 / 移動回数で。これにより、プレイヤーは地下に潜り、他の場所にプライベートにトンネルを掘ることができるゲームを構築できますが、エネルギーを使い果たさないように再び浮上することを強いられ、最大の位置の曖昧さを制限します。
グリッドベースの位置 / 移動を、グラフベースの位置 / 移動（例えば、廊下を介して接続された離散部屋間の移動）に置き換えることができ、プライベートに移動中の位置の曖昧さの増加方法に影響を与えます。

より高いレベルの一般化では、平原 / ジャングルの移動システムは、プレイヤーに何らかの状態を与える方法を表しています。この状態は公開され、プライベートに移行でき（または場合によっては最初からプライベートであることも可能）、プライベートを維持しながら効果的に更新でき、公開されることができます。ZK Hunt では、この状態はユニットの位置を表すために使用されますが、他の任意のタイプの状態を表すことも容易にできます。任意の更新ロジックを持つ：

プレイヤーはプライベートな健康状態を持ち、他のプレイヤーからダメージを受けたときにプライベートに更新され、十分なダメージを受けて殺されるまで明らかにされません。
プレイヤーはプライベートなスタミナメーターとプライベートな位置を持ち、移動中に消費されるスタミナが移動できる距離を決定します。これにより、プレイヤーがプライベートに移動する際、他のプレイヤーは彼らが遠くに移動することを選択したのか、スタミナを節約するために短い距離を移動することを選択したのか、またはその中間であるのかを判断できなくなります。これにより、位置の曖昧さ（およびその曖昧さの視覚的表現の試み）がより複雑になります。
プレイヤーはプライベートなアイテムストレージを持ち、そこから公共またはプライベートな効果を持つアイテムを使用できます（例えば、他のプレイヤーに公開ダメージを与えるか、プライベートに自分を治療するか）。このようなプライベートなストレージを満たすために、プレイヤーは箱を開け、各アイテムが異なる発生確率を持つ可能性のあるアイテムの中から 1 つを得ることができます。箱に含まれるアイテムはプライベートに決定され、他のプレイヤーはプレイヤーがどのアイテムを受け取ったのかを知らず、彼らのストレージの内容はプライベートに保たれます。
あるいは、プレイヤーが他のプレイヤーのストレージの内容を発見し、そこからプライベートにアイテムを盗むことができるかもしれません。このようなことをどのように実現するかは、後の部分でより明確になります。

明らかに、ここでできることはたくさんあります。しかし、ここで関与する核心的なアイデアは決して新しいものではありません……

ダークフォレストの肩の上に#

このプライベート状態 / コミットメント / 変換スキームの明らかなインスピレーション、さらには ZK を利用してオンチェーンゲームを構築する一般的なアイデアは、明らかに『ダークフォレスト』（Dark Forest）から来ています。しかし、DF のアプローチは、ZK Hunt で使用されているアプローチとは少し異なります。まず、DF の動作を簡単に振り返ってみましょう：

DF では、特定の位置に惑星が含まれているかどうかは、その位置の整数座標の MiMC ハッシュ値がしきい値を超えているかどうか（mimc (x, y) > threshold）によって決まります。これは、プレイヤーが空間の特定の領域にどの惑星が含まれているかを見つけるために、単にその領域内のすべての一意の位置をハッシュし、各結果がしきい値を超えているかどうかを確認するだけで済むことを意味します。これが、DF で戦争の霧を「掘り進む」ことができる理由です（生成とチェックの一連のハッシュの方法は、ビットコインのマイニングの動作と非常に似ています）。

DF マップの巨大なサイズと惑星の自然な希薄性のため、マップ内のすべての位置を掘り進むにはかなりの時間がかかります（十分に強力なハードウェアを持っていない限り）、そのため、プレイヤーはマップの特定の領域を戦略的に選択してハッシュ計算を利用することを余儀なくされます。

eF5OO0n

DF では、プレイヤーは同時に複数の惑星にリソースを送信し、それらを占有できるため、1 人の「プレイヤー」が実際には同時に複数の位置にいることができます。ただし、ZK Hunt との比較を簡素化するために、プレイヤーが一度に 1 つの惑星にしかいないと仮定します。この説明は依然として成立します。

プレイヤーが初期の惑星に出現するか、別の惑星に移動する際、惑星位置のハッシュ値が位置コミットメントとして契約に提出され、直接位置を提出するのではなく、コミットメントの有効性を示す ZK 証明が添付されます（ハッシュに対応する位置が実際に惑星を含む場合、移動する場合は新しい惑星と古い惑星の距離がしきい値を超えないこと）。これが、プレイヤーが位置のプライバシーを保持できる方法であり、ZK Hunt の方法と同様です。

ある位置ハッシュに基づいて惑星が存在することがわかると、プレイヤーは最近提出した位置コミットメントとその位置ハッシュを比較することで、どのプレイヤー（もしあれば）がその惑星にいるかを確認できます。さて、少し時間をかけて、これらの惑星を見つけるプロセスとプレイヤーを見つけるプロセスが、より広範な概念フレームワークにどのように組み込まれているかを構築してみましょう。

オンチェーン世界発見 / プレイヤー発見#

DF で戦争の霧を掘り進むことで惑星を発見することは、私が「オンチェーン世界発見」の大きなカテゴリの中の特定の方法と呼んでいるものの一つです。簡単な定義は、ゲームの世界の（非プレイヤー）コンテンツ / 状態が最初はプレイヤーに隠されており、プレイヤーはそれを徐々に発見するために何らかの操作を実行する必要があるということです。

最も明白な例は、DF や従来の戦略ゲームで見られる戦争の霧システムであり、地形 / レイアウト、アイテム、NPC などの世界を明らかにすることができますが、世界発見の最も広範な定義には、NPC の背景ストーリーを理解することや、リソースの組み合わせを通じて新しいアイテムを作成することなども含まれます。

ZK Hunt のマップが最初から完全に公開されているため、世界発見のテーマは ZK Hunt とはあまり関係がないため、この記事ではこれ以上深く掘り下げるつもりはありませんが、ここで私が世界発見のさまざまな方法についての議論を見つけることができます。将来のプロジェクトでいくつかの新しい方法を探求する予定です。

一方、DF で戦争の霧を掘り進むことでプレイヤーを発見することは、私が「オンチェーンプレイヤー発見」の特定の方法であり、ZK Hunt とはより直接的な関係があります。再び簡単に定義すると、プレイヤー（および / またはプレイヤーが制御するエンティティ）がプライベートな位置を持ち、他のプレイヤーが特定の操作を実行することで発見できるということです。より完全な定義は、プレイヤーのすべてのプライベート属性（例えば、彼らの健康状態、彼らが持っているアイテムなど）を発見することに拡張されるかもしれませんが、今は位置にのみ焦点を当てます。

厳密な二分法として世界 / プレイヤー発見を定義することが意味があるかもしれません。すなわち、「プレイヤー」に属するものを発見することと、「非プレイヤー」に属するものを発見することですが、複雑な非プレイヤーエージェントの第三のカテゴリを構築することがより意味があるかもしれません。なぜなら、彼らの発見プロセスは世界発見とは十分に異なるからです。

プレイヤー発見のさまざまな方法を探求する中で、いくつかの異なるサブカテゴリに出会いました。私の現在のモデルは次のとおりです：

公開プレイヤー発見 - プレイヤーを発見すると、彼らの位置がすべての人に明らかになります。
プライベートプレイヤー発見 - プレイヤーを発見すると、発見者にのみ彼らの位置が明らかになります。

プライベート発見のサブカテゴリ：

対称プレイヤー発見 - プレイヤーを発見すると、彼らもあなたを発見します。

非対称プレイヤー発見 - 3 つのレベルに分かれ、各レベルは前のレベルの権限を継承します：

プレイヤーを発見するが、プレイヤーに発見されない（ただし、彼らは検索が成功したかどうかを知っています）。
プレイヤーに成功したかどうかを知られずにプレイヤーを発見する（ただし、彼らはあなたが彼らを検索したことを知っています）。
プレイヤーにあなたが彼らを検索したことを全く知られずにプレイヤーを発見する。

ご覧のとおり、モデルが深くなるほど、情報漏洩が少なくなります。ブロックチェーンの本質的な公開性を考慮すると、通常、カテゴリのプライバシーが強いほど、実装の難易度 / 複雑性が高くなることがわかります。将来的には、このフレームワークを使用して、DF と ZK Hunt がプレイヤー発見に使用する方法を評価できます。

ダークフォレストの分析#

DF の戦争の霧を掘り進むことと惑星 / プレイヤー位置のハッシュ比較は、完全に外部プロセスであり、ゲーム世界 / 契約ロジック / 他のプレイヤーと直接相互作用する必要がないため、DF のアプローチは最高レベルの非対称プレイヤー発見を実現しました。しかし、完璧ではなく、いくつかの欠点があります：

空間的に無制限：プレイヤーは自分の位置に関係なく、マップの任意の部分を掘り進むことができます。言うまでもなく、世界の物語（遠くの宇宙を望遠鏡で見る）を考慮すると、DF にとってはある程度意味がありますが、他のタイプのゲームでは、プレイヤーの位置に基づいて発見を制限できないことは、この方法の重大な欠点です。PvP ダンジョンゲームをプレイしている場合、遠くにいるプレイヤーを発見することはできないはずです。プレイヤー発見はローカライズ可能であるべきです。

時間的に無制限：プレイヤーが新しい惑星を発見する速度、およびそれによって発見される可能性のあるプレイヤーは、基本的に彼らのハッシュ計算速度に依存し、したがって彼らのハードウェアの強さに依存します。これは、本質的に不平等な競技場を生み出し、追加の資本を投入することでさらに不平等にすることができます。プレイヤーが他のプレイヤーを発見する能力は、世界のルール / 状態によって完全に決定されるべきです（例えば、キャラクターの移動速度、望遠鏡の強度、プレイヤー間の障害物など）。

永続性：一度惑星を見つけ、その位置ハッシュを特定すると、ゲームの残りの時間にわたってその惑星に出入りするプレイヤーの動きを見ることができます。世界を発見する際には（少なくとも静的属性に関して）、永続的な発見は良いかもしれませんが、プレイヤーを発見する際にはそうではありません。特定の領域にアクセスしたからといって、その領域を離れた後にアクセスしたプレイヤーを見えるようにすべきではありません。プレイヤー発見は動的で非永続的であるべきです。

DF において、プレイヤー発見はある程度世界発見の副産物と見なされるため、上記の欠点は実際には世界発見の同じ欠点の延長です。誤解しないでください。DF がプライベートな世界とプレイヤー発見を許可するためのシステム設計は非常に素晴らしく、そのユースケースでうまく機能していますが、これらの欠点の影響を受けない方法があれば、より良いでしょう。

DF でプレイヤー発見を支える基本的なメカニズムは、位置ハッシュを「推測して確認する」能力です。惑星の存在は、あなたが実際に確認する位置ハッシュを絞り込むためだけに存在します。これは可能です。なぜなら、プレイヤーが提出した位置コミットメントは単に位置のハッシュだからです；mimc (x, y)。DF マップは十分に大きいため、マップ全体を検索するのは簡単ではありませんが、マップ上にランダムに配置されたプレイヤーが互いに見つける機会が全くないというほどではありません。

ZK Hunt の位置コミットメントは、DF のそれとは異なり、プライベートなランダム数を含んでいます；poseidon (x, y, nonce)。poseidon を mimc の代わりに選択することには機能的な違いはありません（単に回路がより効率的です）。この追加は特に「推測して確認する」位置ハッシュの能力を阻止しますが、ZK Hunt のマップは明らかに DF のマップよりも小さいため、この方法でプレイヤーを見つけることはできません。もしそうであれば、ZK Hunt でのプレイヤー発見はどのように機能するのでしょうか？ジャングルで位置が不明なプレイヤーとどのように相互作用するのでしょうか？

— 矛 —#

矛は、プレイヤーから 32 の異なる方向のいずれかを狙うことができる 4 つの「ヒットタイル」（またはより一般的に「チャレンジタイル」）の線形配列です。矛のいくつかの側面を示すために、右下にいる第 3 のプレイヤー、プレイヤー C を導入します。プレイヤー C はユニットを制御せず、単に第三者の観察者として、ゲーム内の他のすべてのプレイヤーの視点を代表します。

上のビデオでは、プレイヤー A が平原のプレイヤー B のユニットに矛を投げ、彼らが殺されて戦利品を落とし、その後プレイヤー A のユニットがそれを拾います。次に、プレイヤー B は別のユニットをジャングルに送り、いくつかの位置の曖昧さを得ますが、プレイヤー A は彼らに矛を投げようとします。最初の試みはヒットせず、この曖昧さは保持されますが、2 回目の試みは成功し、そのユニットの位置が明らかになり、死亡して戦利品を落とします。

これは、ZK Hunt に含まれる最初のツールであり、ジャングルで位置が不明なユニットと相互作用することを可能にします。矛は戦闘能力であると同時にプレイヤー発見の方法でもありますが、これらの側面は独立して存在することができます。同じ方法で投げられる単純な石に置き換えることができ、もしそれが彼らに当たれば、ユニットは「大声で叫ぶ」ことになり、彼らのジャングルでの位置を明らかにし、殺すことなくします。

矛に当たると、すべてのプレイヤーにユニットの位置が明らかになり、プレイヤー C もユニット位置の事実を知ることになります。したがって、矛は公開プレイヤー発見の方法として分類されます。それがどのように機能するかを見てみましょう…

ヒットタイル#

この 4 つのヒットタイルの線形配列は実際には任意であり、任意の数のヒットタイルの任意の種類の配列を持つことができます。これを使用して、より小さな弧状のヒットタイルを利用したクラブを作成したり、あるいは爆弾を作成して、投げたユニットから離れたより大きな円形の領域のヒットタイルを生成したりすることができます。

矛を投げることができる方向の数と、各方向のタイルの配列も完全に任意です。完全な配列セットは契約にハードコーディングされており、各方向のオフセットリストとして提供されます。矛投げを実行するとき、選択された directionIndex が契約に送信され、その後、ユニットの位置にオフセットのセット（その方向に対応する）を加えることでヒットタイルの結果位置が決定されます。

ヒットタイルは 3 つの段階を経ます：

Snip20231019_78

潜在的（半透明の白で表示）：プレイヤーがまだ矛を狙っているとき。
待機中（実線の白で表示）：プレイヤーが投げることを確認し、契約に方向を提出したとき。
解決済み（赤で表示）：契約がヒットタイルが何かに当たったかどうかを判断したとき。ヒットタイルはタイルごとに解決されるため、他のタイルよりも先に解決される場合があります。

ジャングルに矛を投げる#

ビデオでは、プレイヤー A がジャングル内のプレイヤー B のユニットに矛を投げ、最初の試みはヒットせず、2 回目の試みは成功しました。しかし、待ってください。プレイヤー A と契約がユニットの正確な位置を知らない場合、彼らはどのように矛投げの試みが成功したかどうかを知るのでしょうか？答えは、プレイヤー B に自分がヒットされたかどうかを明らかにさせることを強制する、チャレンジ / レスポンスプロセスを使用することです。

矛投げを提出すると、契約は平原のタイルがどれがヒットしたかを即座に判断できますが、もしヒットタイルがジャングルに落ちた場合、ジャングル内の各ユニットには「待機中のチャレンジ」が置かれます。これは、そのユニットがチャレンジをクリアするまでアクションを実行できないことを意味します（ActionLib によって強制されます）。

ユニットの待機中のチャレンジをクリアするために、所有するプレイヤーには 2 つの有効な選択肢があります：

彼らはヒットされていない。この場合、彼らはその事実を示すゼロ知識証明（ZK proof）を生成し、契約に提出し、そうすることで彼らの位置の曖昧さを保持します。これが、最初の試みで見た状況です。
彼らはヒットされている。この場合、彼らはそのような証明を生成できないため、彼らの位置を契約に公開し、ヒットを受け入れ、戦利品を落とします。これが、2 回目の試みで見た状況です。

これが、ビデオでジャングルに落ちたヒットタイルが平原のヒットタイルよりも遅く解決される理由です。なぜなら、彼らはチャレンジされたプレイヤーの応答を待たなければならないからです。

オプション 1 に使用される JungleHitAvoid 回路は非常に直接的で、最初の部分は JungleMove 回路と一致します：

template JungleHitAvoid(hitTileCount) {
    signal input x, y, nonce, positionCommitment;
    signal input hitTilesXValues[hitTileCount], hitTilesYValues[hitTileCount];
    signal input hitTilesCommitment;
    // 提供されたxとyがコミットメントと一致することを確認
    signal commitment <== Poseidon(3)([x, y, nonce]);
    commitment === positionCommitment;
    // 提供された(x, y)がヒットタイルの一部でないことを確認し、ヒットタイルが提供されたヒットタイルコミットメントと一致することを確認
    signal wasHit <== CoordSetInclusion(hitTileCount)(
        x, y, hitTilesXValues, hitTilesYValues, hitTilesCommitment
    );
    wasHit === 0;
}
component main {public [positionCommitment, hitTilesCommitment]} = JungleHitAvoid(4);

JungleMove でマップデータを処理する方法と同様に、ヒットタイルの x と y 値は公共信号として渡されるのではなく、プライベート信号として渡され、コミットメント値のみが公共信号として渡されます。JungleMove では、特定のマップデータチャンクが回路にとって関連性があるため、チャンクの数が増えるとツリーコミットメントが意味を持ちますが、ヒットタイルには、各セット内の各タイルが必要であるため、タイルの総数に関係なく、線形コミットメントが十分です。

これは、JungleHitAvoid の 2 番目の部分に関連しており、CoordSetInclusion 回路は、ユニットが提供した位置がヒットタイルのいずれかと一致するかどうかを確認し、ヒットタイルが提出された矛投げ時に計算された公共コミットメントと一致するかどうかを確認します（poseidon (x1, poseidon (x2, poseidon (x3, ...))))。

現在の実装では、ジャングル内にヒットタイルがある場合、ジャングル内の任意のユニットに待機中のチャレンジが置かれます。これは明らかに非常に非効率的で、ヒットされる可能性のない多くのプレイヤーが応答する必要があります。特定のジャングル領域のユニットにのみ待機中のチャレンジを置くか、潜在的な位置に触れるユニットのみに置くなど、いくつかの最適化が可能ですが、私は最も簡単な方法を選びました。

応答しないことへの罰#

待機中のチャレンジがユニットに置かれると、上記の 2 つの選択肢に加えて、プレイヤーは実際には 3 つ目の選択肢を持っています。この選択肢は契約ロジックによって直接阻止されていませんが、「ゲームのルール」に違反します。彼らは、全く応答を提出しないことを選択できます。

これは、ユニットが実際には凍結されることを意味します。これは直接的に何の利益も提供しませんが、プレイヤーが複数のユニットを制御している場合や、他のプレイヤーと協力している場合、対戦相手を待たせることで時間を引き延ばすことが有利になる可能性があります。たとえそれを行っても利益がないとしても、他のプレイヤーを不快にさせるための簡単な方法です。では、私たちはこの行動をどのように防ぐのでしょうか？

最初に戻りましょう。ゲームに入ると、各プレイヤーはプレイするためにデポジットを置く必要があります。彼らがルールに従ってゲームをプレイした後にゲームを離れる場合、彼らはそのデポジットを取り戻すことができます。各待機中のチャレンジには、有限の応答期間があります。ユニットが待機中のチャレンジを受け取り、所有するプレイヤーがその期間内に応答しない場合、彼らは誰でも罰せられる（slashing）可能性があり、彼らのデポジットが清算され、すべてのユニットが消滅します。

このビデオでは、私はプレイヤー B のクライアントがチャレンジに応答するのを防ぎ、ジャングル内のユニットに矛を投げた後、約 5 秒の応答時間を待った後、プレイヤー A がプレイヤー B を罰し、彼らの 2 つのユニットが死亡し、戦利品を落とす結果となりました。プレイヤーのクライアントが応答期間が終了し、応答が提出されなかったことを検出すると、罰は自動的に実行され、清算契約を通じて行われます。

注意してください。コードベース全体で、このプロセスを「清算」と呼んでいましたが、後に「罰」がより適切な用語であると決定しました。また、実際にはプレイヤーがゲームに入るときにデポジットを置く能力を実装していないため、罰はプレイヤーのユニットを殺すだけで、言及されたデポジットを取り上げることはありませんが、この機能を追加するのは非常に簡単です。

罰の一般化#

矛の役割はユニットのプライベート位置を明らかにすることですが、基盤となるチャレンジ / レスポンス / 罰システムは、プレイヤーにプライベート状態を明らかにさせるために使用することができます。

より一般的に考えると、可罰のデポジットの存在は、プレイヤーが世界が要求する任意のタイプの相互作用を実行することを保証するために使用できます。契約と回路ロジックは、この相互作用の正確な性質を決定するために使用でき、ゼロ知識証明の使用は、プロセスにプライベート状態を含めることを許可します。ZK Hunt の後続のメカニズムは、このアイデアをさらに探求します。

応答期間は、応答を生成し、提出し、契約が受け入れるのに必要な時間の予想上限に合わせて調整されるべきであり、プレイヤーのハードウェア性能やネットワーク遅延の違いを考慮するために十分な誤差範囲を持つ必要があります。

罰の脅威が効果的であるためには、デポジットは十分に大きく / 重要でなければならず、その損失はプレイヤーにとって行動を取らないことによって得られる価値よりも重要である必要があります。このデポジットは、トークン、ゲーム内アイテム、評判、一定期間生存したキャラクターの経験