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 証明についての基本的な理解があると良いでしょう。

免責事項：

ZK Hunt は 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 のスタック深度が制限されているためだと思います）ため、契約内で直接計算して 6 つを超える入力のポセイドンハッシュを作成または検証することはできませんが、もちろん ZK 証明を使用してこの問題を解決し、各ハッシュに最大 16 の入力を持たせることができます。

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

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

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

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

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

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

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

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

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

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

eF5OO0n

DF では、プレイヤーは同時に複数の惑星に資源を送信し、それらを占有できるため、「プレイヤー」は実際には同時に複数の位置にいることができますが、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 つの「ヒットタイル」（またはより一般的に「チャレンジタイル」）のセットです。矛のいくつかの側面を示すために、右下にいる第三のプレイヤー 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 では、特定のマップデータチャンクのみに関連するため、チャンクの数が増えるとツリーコミットメントが意味を持ちますが、ヒットタイルの場合、各集合内のすべてのタイルが必要であるため、タイルの総数に関係なく線形コミットメントが十分です。

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

応答しないことへの罰#

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

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

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

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

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

罰の一般化#

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

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

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

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

ゲームの一部を、特定のデポジット額を持つプレイヤーのみに制限する（例えば、異なるマッチングレベル、ダンジョンの難易度レベルなど）ことができますが、プレイヤーがゲーム内の行動を通じて時間とともにデポジットを増やすことを許可することは、デポジットの前期コストによってゲームのいかなる部分への参加を制限するのを防ぐ良い方法です。

罰の脅威は、ルールを破らないようにするための十分なインセンティブを提供する必要がありますが、ルールがどのように破られても、リバースロジックを持つ