Minecraft バージョン Beta 1.8 から 1.12.2 ではブロックが壊れるたびに、ドロップされたアイテムの正確な座標によって他のプレイヤーの位置が明らかになります。
「Randar」は、LLL 格子削減を使用して、Minecraft サーバー内で誤って再利用されたjava.util.Randomの内部状態を解読し、そこから逆方向に動作して、現在ワールドにロードされている他のプレイヤーを特定する Minecraft のエクスプロイトです。
代わりに YouTube ビデオの形式で Randar について学ぶには、ここをクリックしてください。
タイムラプスを見てください:
その他のタイムラプスは、ここ (ファイル) またはここ (YouTube) でご覧いただけます。
目標は、どんなに離れていても、世界中の他のプレイヤーのゲーム内の位置 (つまり、座標) を特定することです。私たちは 2b2t でプレイしています。これは最も古く、最も有名な「アナーキー」な Minecraft サーバーです (これはルールがないことを意味します。つまり、プレイヤーは何らかの理由で禁止されません)。このようなことを行うことは、このサーバーの「ポイント」のようなものです。このサーバー上であなたのデータを安全に保つ唯一の方法は、マップが巨大 (3.6 千兆平方タイル) であり、あなたがどこにいるのか他の誰も知らないということです。したがって、座標エクスプロイトを持つことは大きな取引（ゲームを壊す取引）です。 (そういえば、Randar の前に、2018 年から 2021 年にかけて、Nocom という 2b2t で別のコードエクスプロイトもありました。その記事は、HackerNews スレッド、YT でご覧ください)
Minecraft のコードの間違いは、バージョン ベータ 1.8 (2011 年リリース) から 1.12.2 (2017 年リリース、ただし 2b2t は 2023 年 8 月 14 日までこのバージョンに留まりました) まで存在します。間違いは、乱数ジェネレーターjava.util.Randomのさまざまなインスタンスが、コードのさまざまな部分でずさんに再利用されていることです (そして、それらはそもそも安全ではありません)。具体的には、地形の生成とブロックの採掘などのゲーム内アクションの間で RNG が再利用されます。
エクスプロイトの概要は次のとおりです。
World.randシードはチャンク座標の関数にリセットされ、近くにある Woodland Mansion がどこにあるべきか (特にこのチャンクであるかどうか) を確認します。World.rand.nextFloat()呼び出しによって決定されます。ボットは、タイムスタンプと正確な XYZ 値を記録します。World.randの正確な内部状態を判断できます。大まかに言うと (詳細は後ほど説明します)、RNG の 1 つの出力を観察すると、RNG の考えられる約 1,600 万の内部状態のいずれか 1 つが暗示される可能性があります。ただし、RNG の出力 (ドロップされたアイテムの X、Y、Z 座標) を 1 回だけでなく 3 回連続でサンプリングしており、各呼び出しの間に内部状態がどのように更新されるかがわかります (単純な乗算)。 、追加、次にmod);したがって、格子メソッドを使用して、基本的に即座に唯一の可能性を絞り込むことができます。java.util.Randomの内部状態は、前方に進むのと同じくらい簡単に後方に進むことができ、後方に進むことによって、わずか数千ステップでそれを見つけることができます (多くのプレーヤーが存在するため重い 2b2t のようなビジーなサーバーであっても)これは、RNG の内部状態がリセットされた最新の時刻、つまりサーバーにロードされた最新のチャンクの場所を識別します。Minecraft の新しいバージョンに更新されたサーバー、または RNG 操作のパッチが適用されたサーバーでプレイしている場合でも、RNG データを遡及的に悪用できるため、座標は依然として Randar の危険にさらされています。一部の Minecraft プレイヤーはパケットをログに記録する ReplayMod などの MOD を使用しており、それらのログ ファイルがまだ残っている可能性があります。あなたが基地にいる間に誰かがそのようなMODを使用していた場合、ブロックを破壊することは非常に一般的なアクションであり、そのような記録やすべてのブロックで発生した可能性が高いため、彼らは（無意識のうちに）あなたの位置を明らかにする可能性のあるRNGデータを記録した可能性があります。 Break はサーバーの RNG 状態を明らかにし、したがって最後にロードされたチャンクの場所を明らかにします。これは、Randar がかなり重大な問題であることを意味します。遡及的に悪用されるリスクがあるため、すべてのMinecraft サーバーで、バージョン ベータ 1.8 から 1.12.2 でアクティブだったすべての場所は、たとえサーバーが 1.12 以降に更新されて久しい場合でも、侵害されたとみなされる必要があります。 .2 またはパッチを適用した RNG 操作。
Randar エクスプロイトを自分で使用したい場合は、rebane2001 が 1.12.2 から ReplayMod ファイルをドラッグして他のプレイヤーの座標を確認できる Web サイトを作成したここにアクセスしてください。クライアント側で実行されるため、記録がブラウザから離れることはありません。これは、Web サイトが実際にどのように動作しているかを示すビデオです。ここからダウンロードすると、そのビデオから ReplayMod ファイルのサンプルを実行できます。
Randar は n0pf0x (pcm1k) によって発見されました。この記事は leijurv によって書かれ、最後に n0pf0x によって追加のコメントが書かれています。悪用者は、0x22、Babbaj、TheLampGod、leijurv、Negative_Entropy、rebane2001 でした。 TheLampGod のビデオはこちらからご覧ください。 HermeticLock の 100% ユーモアたっぷり、0% 事実のビデオをここでご覧ください。
目次:エクスプロイト可能なコードについてさらに詳しく知るにはここをクリックしてください。ラティス削減がどのように使用されたかを知るにはここをクリックしてください。Randar から自分たちの隠し場所をどのように保護したかを見るにはここをクリックしてください。完全なエクスプロイト コードだけを見たい場合はここをクリックしてください。まだベータ 1.8 から 1.12.2 までのバージョンのサーバーを実行していて Randar にパッチを当てたい場合はここ、n0pf0x が私たちと異なる点について詳しく知りたい場合はここです。
間違いの図 (PDF):
エクスプロイトの図 (PDF):
エクスプロイトの実際の例の図 (PDF):
Minecraft はゲーム全体を通じて乱数に依存しています。 Mob のスポーンや天候に使用されるランダム性など、そのほとんどは実際にはランダムであると予想されますが、その一部は予測可能であると予想されます。たとえば、同じ場所の同じワールド シードが同じ地形を生成すると予想されます。 2011 年、Notch がベータ 1.8 で初めてゲームに構造物を追加したとき、世界に村を配置するために予測不可能であるはずの RNG を誤って再利用してしまいました。それ以来、1.13 まで、このずさんなコードにより、ワールド生成がゲーム内の他のほぼすべてのランダムなイベントに影響を与えてきました。 Earthcomputer とその友人たちがこの間違いを発見し、チャンク ロードが目に見える形でゲームの RNG に影響を与えることに気づいたのは 2018 年 5 月頃までかかりました。この説明を参照してください。ただし、これを逆方向に実行して、RNG を観察して最後にロードされたチャンクを特定することもできることを彼らは認識していないか、まったく公に明らかにしなかっただけです。その発見は、Randar 氏が、2022 年 10 月 7 日に n0pf0x (別名 pcm1k) によって行われました。彼は、その時発見したことを証明するために、約 2 週間後にこのエクスプロイトの暗号化された短い説明を Pastebin に投稿しました。彼はこのエクスプロイトを主に 9b9t で使用し、2b2t やその他のサーバーでは比較的少量のみを使用しました。 2b2t で、n0p はさまざまな場所を見つけて探索し、最終的にグリンゴッツの隠し場所にたどり着きました。彼は rebane2001 によって発見されましたが、当初、その場所をどのように見つけたかについては沈黙していました。しかし、約 1 か月後、彼はそのことについて SpawnMasons と話し合いを始めました。 n0p は、強力な座標エクスプロイトを使用したことを明らかにし、2023 年 4 月にその説明を私たちと共有することに決めました。なぜなら、石工たちは過去に大規模な 2b2t エクスプロイトを利用した経験があるためです。そのため、それが再び起こるのを見るのは楽しいでしょう。そして、n0p はとにかく少し飽きます。私たちは、すでに無関係なプロジェクトのために石/丸石を年中無休で採掘していたいくつかのアカウントでアイテムドロップ座標を受け入れ、記録し始めました（したがって、動作に変化はありませんでした）。 nocom のヘッドレス Minecraft システムを再利用し、測定値を記録するために Postgres データベースを追加しました。この Readme で後述するように、RNG 測定を解読するためにソフトウェアを何度か繰り返し、最終的には非同期 Cuda バッチ ジョブに落ち着きました。クラックされた測定値がデータベースに追加されると、常時、日次、時間ごとの間隔で各座標でのヒット数をカウントするヒートマップ情報を含む分析テーブルも更新しました。これにより、シンプルな Plotly Dash UI で、特定の時間範囲と粒度からヒートマップ データを選択してブラウザーに表示できるようになり、数時間以上にロードされた座標のみを考慮することで、Elytra スタッシュハンティング チャンク ロード スパムをすべて削除できるようになりました。マップ上の各ホットスポットで見つけたものを追跡するために、シンプルな共有注釈システムを追加しました。再び Nocom から再利用した、アイテムの隠し場所を盗み、結果を並べ替えるプロセス全体を完全に自動化する Baritone ボットがあります。多くのフリーメーソンは、悪用を知らずに、 munmapや1248_test_userなどのアカウントを使用して、この部分を支援しました。グリンゴッツの隠し場所は最終的に 13 億点に達し、その約半分はノーコム、残りの半分はランダーに帰属します。
完全な歴史は FitMC ビデオで説明されています。
Minecraft のマップは手続き的に生成され、世界の最初のシードに基づいて基本的に決定的です。プレイヤーがマップを探索すると、プレイヤーが近づくと新しいエリアがオンデマンドで生成されます。すべての生成は反復可能 (決定的) であることを意図しているため、多くの場所でjava.util.Random使用されているのは完全に合理的です。彼らはそれが予測可能であることを望んでいます。これが PRNG (実際には RNG ではない) であるため、 java.util.Randomが使用される理由です。 P は専門的には「疑似」を意味しますが、「予測可能な」ものと考えてください。予測可能な RNG。ランダムに見える数値を生成しますが、開始シードが同じであれば、実際には再現可能です。
Minecraft の世界には、村、海洋記念碑、要塞など、さまざまな構造物が生成されます。これらは手続き型生成の一部であるため、決定的に配置および生成されます。
これを理解するために必要な Minecraft コードはわずか 12 行ですが、これを簡略化して大幅にコメントしました。
// (chunkX,chunkZ) is being loaded, and this function checks if it should generate a Woodland Mansion
protected boolean canSpawnStructureAtCoords ( int chunkX , int chunkZ ) {
// divide by 80, rounding down, to determine which "Woodland region" (my made up term) we're considering
int woodlandRegionX = Math . floorDiv ( chunkX , 80 );
int woodlandRegionZ = Math . floorDiv ( chunkZ , 80 );
// seed the random number generator deterministically in a way that's unique to this Woodland region
Random random = this . world . setRandomSeed ( woodlandRegionX , woodlandRegionZ , 10387319 );
// pick which chunk within this region will get the Woodland Mansion
int woodlandChunkX = woodlandRegionX * 80 + ( random . nextInt ( 60 ) + random . nextInt ( 60 )) / 2 ;
int woodlandChunkZ = woodlandRegionZ * 80 + ( random . nextInt ( 60 ) + random . nextInt ( 60 )) / 2 ;
// but is it *this* chunk, that we're loading right now?
if ( chunkX == woodlandChunkX && chunkZ == woodlandChunkZ ) {
// and, is this chunk in a biome that allows Woodland Mansions? (e.g. roofed forest)
if ( this . world . getBiomeProvider (). areBiomesViable ( chunkX * 16 + 8 , chunkZ * 16 + 8 , 32 , ALLOWED_BIOMES )) {
return true ;
}
}
return false ;
}
// and here's what it calls in World.java:
public Random setRandomSeed ( int seedX , int seedY , int seedZ ) {
this . rand . setSeed ( seedX * 341873128712L + seedY * 132897987541L + seedZ + this . getWorldInfo (). getSeed ());
return this . rand ; // this.getWorldInfo().getSeed() is the overall seed of the entire map, which has been cracked long ago for 2b2t (it's -4172144997902289642)
}上記はわかりやすくするためにコメント化され、わずかに変更されていますが、機能的には実際のコードと正確です。
したがって、アイデアは、このウッドランド地域 (80 x 80 のチャンク) のどこにウッドランド マンションを配置するかを決定し、その場所がここにあるかどうかを確認し、そうであればここからウッドランド マンションを生成することです。
このコードは少しばかげているように見えるかもしれません。「すべてのチャンクに対してこれらすべてのチェックを行うのはばかげている。リージョンごとに 1 回、Woodland Mansions が移動する場所を選択するだけで完了する」と考えるかもしれません。その理由は、Minecraft のチャンクが互いに独立して、未知の順序で生成されるにもかかわらず、与えられたシードから決定論的な世界を生成したいためです。プレイヤーがどのような順序で世界を歩き回るのかはわかりませんが、ステートレスな方法でオンデマンドでチャンクを生成できるのは素晴らしいことです。良いゲーム体験ですよ。したがって、次のような奇妙に見えるコードになります。
とにかく、そのコードはチャンクをロードするたびに、ロードされるチャンクの周囲の大きな正方形内のすべてのチャンクに対して呼び出されます。理由を説明するのは少し複雑なので、ほとんど省略します (基本的な考え方は、これらの構造のサイズが 1 つのチャンクよりも (はるかに) 大きいため、これは正しくは現在のものです）。
これはオーバーワールドにのみ影響することに注意してください。ネザーはすべての構造生成で常に安全な RNG を使用しているため、安全です。ジ・エンドでのチャンクのロードはエンドシティの影響を受けますが、最初の世代のみであり、その後ロードされるたびに影響を受けるわけではありません。したがって、拠点の各チャンクが RNG に影響を与えるのは最初のロード時に 1 回だけであるため、ジ・エンドは比較的安全です。それ。ただし、これは完全に確実というわけではありません。プレイヤーは通常、基地に移動するたびに新しいチャンクを生成し、すでに基地にいる間に新しいチャンクを生成することもあります。
問題は、グローバルWorld.randのシードを変更することです。これはただの怠惰なコーディングです。彼らが行っているのは、 nextInt 4 回呼び出して X 座標と Z 座標を選択することだけです。 Random random = this.world.setRandomSeed(...をRandom random = new Random(the same stuff)に置き換えることもできました (つまり、他のすべてで使用されている既存の Random をいじるのではなく、ここで新しいRandomを作成しますか? ??)。
重要なのは、Woodland Mansion がどこに行くべきかをチェックするためにsetRandomSeedが呼び出されるということです。それは、チャンクロードごとに、どこでも、何があっても発生します。ウッドランド・マンションの中やその近くにいる必要はありません。
そうですね、 World.randは文字通り何百もの場所で使用されており、それらの場所の多くは通常にゲームをプレイすることで簡単に観察できることがわかりました。たとえば、ブロックをマイニングするときは次のようになります。
/**
* Spawns the given ItemStack as an EntityItem into the World at the given position
*/
public static void spawnAsEntity ( World world , BlockPos pos , ItemStack stack ) {
double xWithinBlock = world . rand . nextFloat () * 0.5F + 0.25D ;
double yWithinBlock = world . rand . nextFloat () * 0.5F + 0.25D ;
double zWithinBlock = world . rand . nextFloat () * 0.5F + 0.25D ;
EntityItem entityitem = new EntityItem ( world , pos . getX () + xWithinBlock , pos . getY () + yWithinBlock , pos . getZ () + zWithinBlock , stack );
world . spawnEntity ( entityitem );
}繰り返しになりますが、少し変更されていますが、機能的には私たちが話している内容に正確です。
ここでの考え方は、Minecraft ではブロックを採掘するとアイテムがドロップされるということです。アイテムはブロック内のランダムな位置にドロップされます。たとえば、ブロックが(10, 20, 30)にあった場合、項目は(10.25, 20.25, 30.25)と(10.75, 20.75, 30.75)の間のどこかに表示されます。
そして、その項目の正確な位置は、X、Y、Z に対してworld.rand.nextFloat()を 3 回連続して呼び出すことによって選択されます。
必要な Minecraft コードはこれですべてです。
さて、これらのnextFloat呼び出しで何かできると言いました。まず、 nextFloat呼び出しが何であるかを「逆算」して確認できるかどうかを見てみましょう。それはかなり幸運ですが、実際にそれが可能です。上記のコードで注意してください: ランダムな浮動小数点は 0.5 で乗算され、その後 0.25 に加算されます。アイデアは、0 ～ 1 の乱数から 0.25 ～ 0.75 の乱数に移行することです。整数を 2 で割ると、結果が切り捨てられるため、多少の情報が失われるのではないかと心配されるかもしれません。ありがたいことに、float に 0.5 を乗算することは完全に元に戻すことができます。これは、仮数部分はそのままにして指数をデクリメントするだけであるためです。次に、float は double にキャストされ、精度が大幅に向上します。 0.25を加算してからブロック座標を加算します。その後、ネットワーク経由でクライアントに完全な精度で送信されます。結論: このプロセス全体は可逆的であるため、 World.rand.nextFloat()が生成した正確な 3 つの float を取得できます。
java.util.Randomどのようにして float を生成するのでしょうか?まあ、実際には非常に簡単です。 0 ～ 2^24 の整数を生成し、それを 2^24 で割ります (結果は 0 ～ 1 の数値になります)。どうやってそのランダムな整数を取得するのでしょうか？こちらもかなりシンプル！それは線形合同生成器 (LCG) です。これは、次のシードが、前のシードに何かを掛けて、他の何かを加えた、何かを法としたものであることを意味します。
public float nextFloat () {
this . seed = ( this . seed * multiplier + addend ) % modulus ; // update the seed
int randomInteger = ( int ) ( this . seed >> 24 ); // take the top 24 bits of the seed
return randomInteger / (( float ) ( 1 << 24 )); // divide it by 2^24 to get a number between 0 and 1
}この場合、乗数は 25214903917、加数は 11、法は 2^48 です。
ここから得られた float を使用すると、それに 2^24 を乗算して RandomInteger を戻すことができ、したがって 48 ビット シードの「上半分」 (最上位 24 ビット) を取得できます。
つまり、測定から、シードがmeasuredRandomInteger * 2^24と(measuredRandomInteger + 1) * 2^24の間にあることがわかります。
これを X、Y、Z に対して 3 回続けて実行できます。
そして、X と Y の間、および Y と Z の間で、シードnewSeed = (oldSeed * 25214903917 + 11) mod 2^48に従って更新されたことがわかります。
有効なオプションの 1 つは、2^24 の可能な下位ビットをすべて試す for ループであることを言及しなければなりません。これを読んでいるプログラマーにとって、問題が何であるかが明確になることを願っています。
for ( long seed = firstMeasurement << 24 ; seed < ( firstMeasurement + 1 ) << 24 ; seed ++) {
// all these seeds will match the first measurement
if ( nextSeed ( seed ) >> 24 == secondMeasurement && nextSeed ( nextSeed ( seed )) >> 24 == thirdMeasurement ) {
// if nextSeed(seed) matches secondMeasurement, and nextSeed(nextSeed(seed)) matches thirdMeasurement
// then we found a seed that matches all three measurements! yay!
return seed ;
}
}これは機能しますし、実際に機能しますが、それほど高速ではなく、それほど楽しいものではありません。そこで、代わりに格子を使用します。
ただし、少し順番を外さなければならないような気がします。ここで格子削減の部分が登場しますが、それは非常に複雑で、読者の定着率が低いと思いますので、あなたを失いたくありません。したがって、for ループの解決策 (これは実際に機能します) だけを紹介し、エクスプロイトの次のステップに進みます。格子縮小法の説明はこの直後にあります:)
この種を手に入れたら、それをどうするのでしょうか？
まず、LCG を後方に進めることができることに注意してください。 11 を足すことは明らかに可逆的ですが、その大きな数を掛けることは可逆的でしょうか?乗数25214903917は奇数であり、2 で割り切れないことを意味します。したがって、法 2^48 と因数を共有しません (2^48 は文字通り単なる 2 の集まりであるため)。これは法に対して比較的素であるため、これを反転することができます。これはx * 25214903917 - 1は 2^48 で割り切れる、を満たす別の数値xを見つけることを意味します。言い換えると、 25214903917 * x mod 2^48 = 1 。その番号は246154705703781です。これは、たとえばsecret * 25214903917があり、 secretを計算したい場合、 secret * 25214903917 * 246154705703781 mod 2^48 = secret * 1 mod 2^48 = secret計算するだけで済むため、乗算を逆にするのに役立ちます。
さて、 java.util.Randomの内部シードを前後にステップ実行できます。前方はnewSeed = (oldSeed * 25214903917 + 11) mod 2^48で、後方はoldSeed = ((newSeed - 11) * 246154705703781) mod 2^48です。そして、これが機能するのは、これらの数値25214903917と246154705703781を掛け合わせると、mod 2^48 で1になるからです。
さて、後戻りしながら、このシードが最近世界のどこかで Woodland Mansion チェックが実行されたことを意味するかどうか (エクスプロイトの全体点) を各ステップで確認したいと思います。どうやってそれを行うのでしょうか？
Minecraft の世界の範囲は、-3,000 万ブロックから +3,000 万ブロックです。各「森林地域」(前に示したコードに従って、単一の森林邸宅がランダムに配置される世界のエリア) は 80 × 80 チャンク、つまり 1280 × 1280 ブロックです。これは森林地域 23437.5 ですが、すべてのコードで 23440 に切り上げました。これは概数であり、プレイヤーは 3,000 万を超えて移動することはできませんが、近くに立っているだけでそれを超えるチャンクをロードできるためです。そんなことを心配する必要はありませんでした。
したがって、X 軸と Z 軸の両方で -23440 から +23440 になります。これは(23440*2+1)^2 (別名2197828161 ) のウッドランド リージョンであり、それぞれが固有の「マンション シード」(誰かが特定のウッドランド リージョンにチャンクをロードしたばかりであることを明らかにするシードとして定義されます) を生成します。何かがマンションシードであるかどうかを確認できる必要があります。 22 億の邸宅シードすべてを反復処理して、それぞれをチェックすることはできるでしょうか?遅すぎるでしょう。 22 億のエントリを含むHashSetを作成できるでしょうか? nocom で行ったようにクロニクル マップを使用する場合でも RAM を消費しすぎ、 abseil-cpp使用する C++ でも 50 GB の RAM を使用します。そして、それは他の部分については言うまでもありません。私たちは実際に彼らが世界のどこにいるのかを知りたいのです（それが重要です）。したがって、これが邸宅のシードであることを知るだけでは十分ではなく、どのウッドランド地域がそれを引き起こしたのかを (効率的に) 知りたいと考えています。
Woodland Regional から邸宅のシードに移動する関数を思い出してください (注: わかりやすくするために、上記のコード以降、いくつかの定数を組み合わせています。この方程式は 2b2t のシードに特化されています)。
seed = x * 341873128712 + z * 132897987541 - 4172144997891902323 mod 2^48
( -4172144997891902323という数値は、 -4172144997902289642 + 10387319から来ています。これは、2b2t ワールド シード + (前に示した) ウッドランド リージョンのシードに使用されるマジック値です。他のワールドの場合は、代わりに独自のシードをこの式に入れるだけです。 。）
x 座標には偶数が乗算されるため、できることはあまりありません。しかし、z 座標の係数は何でしょうか?奇数っぽいですね！！！前と同じトリックを使用して再度反転すると、 211541297333629が得られます。
与えられたシードがあると想像してみましょう。 -23440 から +23440 までのすべての可能な X 座標を反復処理し、それぞれについて、この邸宅シードがある場合のウッドランド地域の Z 座標が何になるかを計算できたらどうなるでしょうか。言い換えれば、上記の方程式は、 xとzわかっていればseedを与えますが、 seedとxがわかっていればzを与える方程式を作成できるでしょうか?答え: はい。上記の式を整理し、Z の係数が奇数であるため、可逆 mod 2^48 であるという事実を利用します。
方程式は次のとおりです。
z = (seed + 4172144997891902323 - x * 341873128712) * 211541297333629 mod 2^48
したがって、合計 22 億回の反復を実行する 2 つのネストされたループ (1 つは X 用、もう 1 つは Z 用) の代わりに、46,881 回の反復だけを実行する X 用の 1 つの for ループを使用できるため、これは非常に優れたソリューションです。 Java では次のようになります。
private static WoodlandRegionCoord woodlandValid ( long internalSeed ) {
long seed = 25214903917 ^ internalSeed ; // java.util.Random XORs in the multiplier while doing setSeed, so XOR that back out to go from a "this.seed" to what the input to setSeed() would be
for ( int x = - 23440 ; x <= 23440 ; x ++) {
long z = (( seed + 4172144997891902323L - x * 341873128712L ) * 211541297333629L ) << 16 >> 16 ;
if ( z >= - 23440 && z <= 23440 ) {
return new WoodlandRegionCoord ( x , z );
}
}
return null ;
} (注: 奇妙な<< 16 >> 16は mod 2^48 を実行していますが、実際には符号付き型を使用してこれを実行したいので、z が -23440 と 0 の間の場合でも正しい答えが得られます。これは次の方法です。 48 ビット数値を 64 ビットに符号拡張し、上位 16 ビットを 2 の補数の正しい符号ビットで埋めます)
したがって、これは機能し、単一シードの場合はかなり高速です。ただし、RNG を数千ステップ戻す可能性があり、一致するものが見つかるまで各ステップでこのチェックを実行していることに注意してください。当時、私たちは最下層でひどい DigitalOcean ドロップレットを使用していましたが、実際にはすべてが遅れていて、リアルタイムに追いつくことができませんでした (ボットは 1 秒あたり多くのブロックをマイニングし、各ブロックをクラックするには数千の RNG ステップがかかります)各 RNG ステップではチェックに 23440*2+1 の操作が必要で、それらを掛け合わせると 1 秒あたり数億回の操作に達します。特に、その VPS も試行している場合に、なぜひどい VPS で問題が発生したかがわかります。 Minecraft の複数のヘッドレス インスタンスを実行します)。
とにかく、ルックアップ テーブルのアプローチに切り替え、数分ごとにバッチ ジョブとしてデスクトップ上で実行できるように Cuda で書き直しました。数千の cuda コアがそれぞれ独自のシードを並行して処理できるため、文字通り毎秒数百万の処理を行うことができます。考え方は次のとおりです。ルックアップ テーブルのキーは邸宅シードの下位 32 ビットで、値はウッドランド領域の X 座標です。このルックアップ テーブルは、どういうわけか、各マンション シードに固有の下位 32 ビットがあるため、衝突することなく機能します。なぜそうなるのか分かりませんが、興味深いですね。それはうまくいかないと思うでしょう。しかし、係数341873128712と132897987541は、これを機能させるために特別に選択されたのではないかと思います。たとえば、22 億個のビー玉と 43 億個のバケツがあり、各ビー玉をランダムなバケツに個別に入れた場合、各ビー玉が独自のバケツを取得する確率はどのくらいでしょうか?本質的にはゼロです。終わりに近づくと、新しいビー玉はそれぞれ、すでに満たされているバケツに当たる確率が 50% 以上になります。しかし、明らかに、これらは独立してランダムではないため、何らかの形で機能します。皮肉なことに、これを読んでこれがどのように機能するか、またはこれら 2 つの特定の係数がなぜこれを機能させるのかを理解している場合は、私に知らせてください。とにかく、それは機能します。ルックアップ テーブルには 2^32 のエントリがあり、各エントリは 2 バイト (-23440 から +23440 までの数値であるため) なので、GPU に約 9 ギガバイトの VRAM が必要です。
ウッドランド チェック関数は次のようになります (繰り返しになりますが、これは実際のコードですが、すべてのヘルパーと定数がインライン化されて簡略化されています)。
__global__ void computeSteps ( const int16_t * mansionTable, const int64_t * seedsArr, Result* resultArr, size_t numData) {
auto tid = blockIdx. x * blockDim. x + threadIdx. x ;
[[unlikely]] if (tid >= numData) {
return ;
}
auto seed = seedsArr[tid];
int steps = 0 ;
while ( true ) {
auto externalSeed = seed ^ 25214903917 ;
const auto x = mansionTable[externalSeed & (( 1LL << 32 ) - 1 )];
const auto z = ((externalSeed + 4172144997891902323LL - ( int64_t ) x * 341873128712LL ) * 211541297333629LL ) << 16 >> 16 ;
if (z >= - 23440 & z <= 23440 ) {
resultArr[tid] = {. startSeed = seedsArr[tid], . x = ( int16_t ) x, . z = ( int16_t ) z, . steps = steps};
return ;
}
seed = ((seed - 0xBLL ) * 0xdfe05bcb1365LL ) & (( 1LL << 48 ) - 1 ); // prevSeed(seed)
steps++;
}
}
// and that mansionTable was generated like this
// note: mansionTable must be calloc'd before this function because not every entry will be written to, and an x value outside -23440 to 23440 bounds could create a false positive later on while using the table
__global__ void writeToSeedTable ( int16_t * mansionTable) {
auto tid = blockIdx. x * blockDim. x + threadIdx. x ;
if (tid >= ( 23440 * 2 + 1 ) * ( 23440 * 2 + 1 )) return ;
auto x = tid / ( 23440 * 2 + 1 ) - 23440 ;
auto z = tid % ( 23440 * 2 + 1 ) - 23440 ;
auto seed = (( int64_t ) x * 341873128712LL + ( int64_t ) z * 132897987541LL - 4172144997891902323LL ) & (( 1LL << 48 ) - 1 );
mansionTable[seed & (( 1LL << 32 ) - 1 )] = ( int16_t ) x;
}これは巨大なバッチでうまく機能し、3090 では 1 秒あたり約 1,000 万個のシードを解読できます。ワープ内のスレッドの一部が早期に終了する場合はそれほど大したことではないことが判明し、実際には実行できませんでした。これよりも早くなります。 (その理由は、どのシードのステップ数が多いか少ないかを事前に知ることが基本的にできないためです)。
まあそれくらいです。シードを考えると、これにより、最新のチャンクロードが発生したワールド内のウッドランド リージョンを取得することができます。言い換えれば、誰かが 2b2t で歩き回り、世界の新しいエリアを読み込んだのは、先ほど特定したこの1280 × 1280 ブロックのウッドランド領域内のどこかであったことがわかりました。 (これは十分な精度なので、検索に数分しかかかりません)
実際には、RNG ステップは何ステップ必要でしたか?ローエンドでは、信頼性の高い測定は 4 RNG ステップから始まり、それ以下はすべて測定誤差/ランダム ノイズです。これは、Woodland Mansion コードが測定可能になる前に即座にrand.nextInt 4 回呼び出すため、これがわかっています。平均すると、各 Woodland シード間には約 128,000 ステップがありますが、実際には、2b2t ではほとんどの場合、数十ステップ以内に Woodland シードが見つかりました。これは、Minecraft ティックで何がどの順序で起こるかの詳細によるものです。ブロックを破壊するためのパケットが処理される場所であるため、測定は技術的にはティックの最初に行われます。一般に、チャンクは直前のティック中にごく最近の履歴にロードされています。ただし、場合によっては、イベントによってその間に多数の RNG ステップが発生することがあります。私たちは、このイベントは誰かがエンドクリスタルをパンチして爆破したり、ウィザースカルを爆破したりするような爆発であると考えています。エンドクリスタルの爆発は、プレイヤーのパンチパケットからのパケット処理中にも発生し、RNGステップ数も1354ステップで並びます（直方体のブロックダメージ計算から1352ステップ）
この図で実際の例として使用されている座標では、上記のコードが出力するものは次のとおりです。
jshell> crackItemDropCoordinate(0.730696, 0.294929355, 0.634865435)
Item drop appeared at 0.730696 0.294929355 0.634865435
RNG measurements are therefore 16129481 1507579 12913941
This indicates the java.util.Random internal seed must have been 270607788940196
Found a woodland match at woodland region 123 456 which would have set the seed to 261215197308064
Located someone between 157312,583552 and 158591,584831
jshell>
Woodland Regional 123,456どのように特定するか、そして最後の「間の誰かを特定する」に最初に入力した実際の座標 (x=157440 z=583680) がどのように含まれるかに注目してください。さらに、RNG 測定値は赤色の 16 進数と一致します。 0xf61dc9は16129481 、 0x1700fbは1507579 、 0xc50d15は12913941です。そしてシードの場合、 0xed92e70ba4a0 261215197308064に等しく、 0xf61dc9221ba4 270607788940196に等しくなります。
おそらく RNG 操作を無効にするパッチや設定オプションが見つかるでしょう。そのようなものは Randar にパッチを適用するのに役立ち、おそらくそれが最も簡単な方法です。 RNG 操作を無効にする簡単な方法が見つからない場合は、 Worldクラスで調整する必要があるコードを次に示します。
脆弱なバージョン:
public Random setRandomSeed ( int seedX , int seedY , int seedZ ) {
this . rand . setSeed ( seedX * 341873128712L + seedY * 132897987541L + seedZ + this . getWorldInfo (). getSeed ());
return this . rand ;
}完全な保護が必要な場合は、この関数を変更して、毎回異なるランダムを返すようにするだけです。
パッチ適用バージョン:
public Random setRandomSeed ( int seedX , int seedY , int seedZ ) {
return new Random ( seedX * 341873128712L + seedY * 132897987541L + seedZ + this . getWorldInfo (). getSeed ());
}これではパフォーマンスがあまり良くない可能性があるため、必要に応じて、他のものと共有されない新しいフィールドseparateRandOnlyForWorldGenを導入できます。例:
private final Random separateRandOnlyForWorldGen = new Random (); // new field on the World class
public Random setRandomSeed ( int seedX , int seedY , int seedZ ) {
this . separateRandOnlyForWorldGen . setSeed ( seedX * 341873128712L + seedY * 132897987541L + seedZ + this . getWorldInfo (). getSeed ());
return this . separateRandOnlyForWorldGen ;
}PaperMC 1.12.2 を使用している場合、適用できるパッチは次のとおりです。代替リンク。
これは、基本的なアイデア以外はほとんど独自に開発したものであるため、私の観点から説明する方が合理的である追加の項目について説明する追加セクションになります。
まず最初に言及したいのは、シードから座標を見つけるシステムです。メイソンズでは大規模なルックアップ テーブルと GPU 処理が使用されていましたが、私は代わりに速度のためにキャッシュに依存しました。ヒットが発生するたびに、その座標と半径内のすべての座標が HashMap に入れられます。シードは 2 つのパスで処理されます。最初のパスでは RNG をステップバックし、シードがキャッシュ内に存在するか、または前回処理されたのと同じシードであったかどうかを確認します (これは異なると考えられます)。 2 番目のパスは、最初のパスが失敗し、はるかに遅く、前述の比較的高価なアルゴリズムを使用する場合にのみ発生します。このシステムの嬉しい副作用は、最初のパスでは本来「有効」である場所を「スキップ」する可能性がありますが、正しい場所である可能性が低く、誤検知を防ぐことができることです。
そのコードは次のとおりです。
public class RandarCoordFinder
{
public static final long X_MULT = 341873128712L ;
public static final long Z_MULT = 132897987541L ;
public static final long Z_MULT_INV = 211541297333629L ;
public static final int MANSION_SALT = 10387319 ;
public static final int MANSION_SPACING = 80 ;
public static final int CITY_SALT = 10387313 ;
public static final int CITY_SPACING = 20 ;
// the last seed we processed
public long lastSeed = - 1 ;
// a mapping of seed -> x,z that is updated everytime we get a hit
public final HashMap < Long , Long > hitCache = new HashMap <>();
// set this according to the server's seed
public long worldSeed ;
// change these if you need to use different structures
public int salt = MANSION_SALT ;
public int spacing = MANSION_SPACING ;
public RandarCoordFinder ( long worldSeed )
{
this . worldSeed = worldSeed ;
}
// a simple class that extends java.util.Random and provides some extra methods and constants we need
public static class RandarRandom extends Random
{
public static final long MULT = 0x5DEECE66DL ;
public static final long ADDEND = 0xBL ;
public static final long MASK = ( 1L << 48 ) - 1 ;
public static final long MULT_INV = 0xDFE05BCB1365L ;
public long seed ;
public RandarRandom ( long seed )
{
this . seed = seed ;
}
@ Override
public void setSeed ( long seed )
{
this . seed = seed ;
}
@ Override
public int next ( int bits )
{
seed = ( seed * MULT + ADDEND ) & MASK ;
return ( int )( seed >> 48 - bits );
}
public int prevInt ()
{
seed = (( seed - ADDEND ) * MULT_INV ) & MASK ;
return ( int )( seed >> 16 );
}
}
public enum FindType
{
HIT ,
SKIP ,
FAIL ;
}
public record FindResult ( FindType type , int xCoord , int zCoord , int steps )
{
}
public FindResult findCoordsSeed ( long seed , int maxSteps )
{
seed &= RandarRandom . MASK ;
// remember and update lastSeed
long last = lastSeed ;
lastSeed = seed ;
RandarRandom random = new RandarRandom ( seed );
// first pass - this is meant to be quick
for ( int i = 0 ; i < maxSteps + 100000 ; i ++)
{
if ( random . seed == last && i > 0 )
{
// we encountered the last processed seed while stepping back, skip
return new FindResult ( FindType . SKIP , 0 , 0 , i );
}
else
{
Long hashValue = hitCache . get ( random . seed );
if ( hashValue != null )
{
// we found a hit in our cache
int xCoord = ( int )(( hashValue >> 32 ) & 0xFFFFFFFF );
int zCoord = ( int )( hashValue & 0xFFFFFFFF );
cacheNearby ( xCoord , zCoord , 8 );
return new FindResult ( FindType . HIT , xCoord , zCoord , i );
}
}
random . prevInt ();
}
random . seed = seed ;
// second pass - this is slow and should only happen if the first pass fails
for ( int i = 0 ; i < maxSteps ; i ++)
{
// undo worldSeed and salt
long seedValue = ( random . seed ^ RandarRandom . MULT ) - worldSeed -
( long ) salt ;
Coords coords = findCoords ( seedValue , 1875000 / spacing + 8 );
if ( coords != null )
{
// we found a hit
cacheNearby ( coords . x , coords . z , 8 );
return new FindResult ( FindType . HIT , coords . x , coords . z , i );
}
random . prevInt ();
}
// we could not find anything
return new FindResult ( FindType . FAIL , 0 , 0 , - 1 );
}
public static long getRandomSeed ( int x , int z , int salt , long seed )
{
return (( long ) x * X_MULT + ( long ) z * Z_MULT ) + seed + ( long ) salt ;
}
private void cacheNearby ( int x , int z , int radius )
{
for ( int xOff = - radius ; xOff <= radius ; xOff ++)
{
for ( int zOff = - radius ; zOff <= radius ; zOff ++)
{
int cacheX = x + xOff ;
int cacheZ = z + zOff ;
long cacheSeed = ( getRandomSeed ( cacheX , cacheZ , salt ,
worldSeed ) ^ RandarRandom . MULT ) & RandarRandom . MASK ;
hitCache . put ( cacheSeed , ( long ) cacheX << 32 | cacheZ &
0xFFFFFFFFL );
}
}
}
public record Coords ( int x , int z )
{
}
public static Coords findCoords ( long value , int distance )
{
value &= RandarRandom . MASK ;
for ( int x = - distance ; x <= distance ; x ++)
{
long testValue = ( value - X_MULT * x ) & RandarRandom . MASK ;
long z = ( testValue * Z_MULT_INV ) << 16 >> 16 ;
if ( Math . abs ( z ) <= distance )
{
return new Coords ( x , ( int ) z );
}
}
return null ;
}
}もう一つ言及しておきたいのは、これを『The End』でどのように使用したかということです。前述したように、The End のチャンクは最初に生成されたときに RNG に一度だけ影響します。オーバーワールドとは異なり、基地にチャンクをロードするだけではプレイヤーを見つけることができないため、これは物事をさらに複雑にします。
代わりに、依存しなければならない主なシナリオが他に 2 つあります。
最初のシナリオは本質的に、領域が何回個別に攻撃されたかを単純に数える単純な方法を引き続き使用できることを意味しますが、攻撃が非常にまれである可能性があり、誰かが単に領域を通過しただけで混乱する可能性があるため、大幅に制限されます。十分に明確な回数が数回。 2 番目のシナリオでは、これらの痕跡を特定して追跡する必要があります。
では、具体的にどのようにして痕跡をたどるのでしょうか？理論的には、トレイルを自動的に識別して追跡するシステムを作成することもできますが、私はこれを実装せず、手動でトレイルを視覚的に追跡するだけでした。トレイルをたどる際に役立つアイデアがいくつかあります。たとえば、同じ場所につながる複数の小道は、基地があることを意味する可能性があります。特定のヒットやトレイルが特定のプレイヤーによって引き起こされたものであることを知ることも役立ちます。これについては後で詳しく説明します。
では、どのプレイヤーが特定のヒットを引き起こしたかをどのように判断できるのでしょうか?オーバーワールドでは、プレイヤーが参加した直後に発生する「独特の」ヒットを簡単に探すことができます。ただし、ここではうまくいかない可能性が高いため、何か別のことを行う必要があります。実はこれにはきちんとしたシステムがあります。これは、ジ エンドで実際に一度にオンラインになるプレイヤーはそれほど多くないという前提と、これらのプレイヤーが誰であるかを識別できるという考えに基づいています。その考え方は、ティックごとの RNG 呼び出しの数が、現在ロードされているチャンクの数、つまりその次元のプレーヤーの数に部分的に相関しているということです。プレイヤーが参加または退出した直後にこれらの呼び出しの数が突然増加または減少することを監視することで、ジ エンドにいるプレイヤーを特定できます。このシステムを「End Occupancy Tracker」（EOT）と呼びます。
EOT は 2 つのセットを維持します。 1 つ目は、「現在」ジ・エンドにいると思われる人物を追跡します。これによりプレイヤーを見逃す可能性があるため、偽陰性が発生しやすくなると考えられます。 2 つ目は、ジ エンドに「全体的に」誰がいたと思われるかを、一定期間前後に追跡します。これは現在オンライン中のプレイヤーと組み合わされ、誤検知が発生しやすくなると考えられます。ヒットが発生したときにこれらのセットを確認し、手動で推論を行うことで、特定のヒットを引き起こした可能性のある人物について大まかなアイデアを得ることができます。
EOTは9B9Tでのみテストされており、現在2B2Tなどの他のサーバーでは当てはまらない条件に依存している可能性があることに注意する必要があります。 RNGは、あまり変動せずにすべてのダニをサンプリングできると想定しています。これは、ブロックプレイスの速度制限のために2B2Tの方が難しい場合があります。サーバー上で最終的にプレーヤーのアクティビティが大幅に増加する場合、物事はトリッキーになる可能性があります。これは、はるかに大きなサーバーであるため、2B2Tに当てはまる可能性があります。
