Setiap kali sebuah blok dipecahkan di Minecraft versi Beta 1.8 hingga 1.12.2, koordinat yang tepat dari item yang dijatuhkan dapat mengungkapkan lokasi pemain lain .
"Randar" adalah eksploitasi untuk Minecraft yang menggunakan pengurangan kisi LLL untuk memecahkan keadaan internal java.util.Random yang digunakan kembali secara tidak benar di server Minecraft, kemudian bekerja mundur dari server tersebut untuk menemukan pemain lain yang saat ini dimuat ke dunia.
Klik di sini untuk mempelajari tentang Randar dalam bentuk video YouTube.
Tonton timelapsenya:
Lihat timelapse lainnya di sini (sebagai file) atau di sini (sebagai YouTube).
Tujuannya adalah untuk menentukan lokasi dalam game (yaitu koordinat) pemain lain di dunia, tidak peduli seberapa jauh jaraknya. Kami bermain di 2b2t, yang merupakan server Minecraft "anarki" tertua dan paling terkenal (yang berarti tidak ada aturan, yaitu pemain tidak dilarang karena alasan apa pun). Melakukan hal-hal seperti ini adalah "intinya" di server ini. Di server ini, satu-satunya hal yang menjaga barang-barang Anda tetap aman adalah petanya sangat besar (3,6 kuadriliun ubin persegi) dan tidak ada orang lain yang tahu di mana Anda berada. Jadi, merupakan suatu hal yang besar (kesepakatan yang memecahkan masalah) untuk memiliki eksploitasi yang terkoordinasi. (Ngomong-ngomong, sebelum Randar kami juga memiliki eksploitasi coord lain di 2b2t, Nocom, dari 2018 hingga 2021; lihat tulisan itu di sini, thread HackerNews, YT)
Kesalahan dalam kode Minecraft muncul dari versi Beta 1.8 (dirilis 2011) hingga 1.12.2 (dirilis 2017, tetapi 2b2t tetap pada versi ini hingga 14 Agustus 2023). Kesalahannya adalah berbagai contoh generator angka acak, java.util.Random , digunakan kembali secara sembarangan di berbagai bagian kode (dan awalnya tidak aman). Secara khusus, ada penggunaan kembali RNG antara menghasilkan medan dan aksi game seperti menambang blok.
Eksploitasi tersebut merangkum:
World.rand global telah menyetel ulang benihnya ke fungsi koordinat bongkahan, untuk memeriksa di mana seharusnya Woodland Mansion di dekatnya berada (dan apakah bongkahan ini khususnya).World.rand.nextFloat() berturut-turut untuk memilih koordinat XY dan Z antara 0 dan 1. Bot mencatat stempel waktu dan nilai XYZ yang tepat.World.rand yang menyebabkan ketiga float tersebut. Secara umum (detail lebih lanjut akan dijelaskan nanti), mengamati satu keluaran RNG dapat berarti salah satu dari sekitar 16 juta kemungkinan status internal RNG. Namun, kami telah mengambil sampel keluaran RNG tidak hanya sekali tetapi tiga kali berturut-turut (koordinat X, Y, dan Z dari item yang dijatuhkan), dan kami mengetahui bagaimana status internal diperbarui di antara setiap panggilan (perkalian sederhana , tambahkan, lalu mod); oleh karena itu kita dapat menggunakan metode kisi untuk secara instan mempersempitnya menjadi satu-satunya kemungkinan.java.util.Random dapat dimundurkan semudah maju, dan dengan melangkah mundur kita dapat menemukannya hanya dalam beberapa ribu langkah (bahkan pada server sibuk seperti 2b2t dengan banyak pemain dan karenanya berat penggunaan RNG), yang mengidentifikasi waktu terkini saat status internal RNG direset, dan juga lokasi potongan terbaru yang dimuat di server.Bahkan jika Anda bermain di server yang telah memperbarui ke versi Minecraft yang lebih baru, atau telah menambal manipulasi RNG, koordinat Anda masih berisiko dari Randar karena kemampuan untuk mengeksploitasi data RNG secara surut. Beberapa pemain Minecraft menggunakan mod seperti ReplayMod yang mencatat paket, dan mereka mungkin masih menyimpan file log tersebut. Jika ada orang yang menggunakan mod tersebut saat Anda berada di markas, mereka mungkin (tanpa sadar) merekam data RNG yang dapat mengungkapkan lokasi Anda, karena memecahkan blok adalah tindakan yang sangat umum yang mungkin terjadi dalam rekaman tersebut, dan setiap blok tersebut break mengungkapkan status RNG server dan lokasi potongan yang terakhir dimuat. Ini berarti Randar adalah masalah yang cukup besar: karena risiko eksploitasi secara surut, di setiap server Minecraft, setiap lokasi yang aktif dalam versi Beta 1.8 hingga 1.12.2 harus dianggap telah disusupi, meskipun server telah lama diperbarui setelah versi 1.12. .2 atau manipulasi RNG yang ditambal.
Jika Anda ingin menggunakan eksploitasi Randar sendiri , buka di sini di mana rebane2001 telah membuat situs web tempat Anda dapat menyeret file ReplayMod dari 1.12.2 dan melihat koordinat pemain lain. Ini berjalan di sisi klien sehingga rekaman Anda tidak akan meninggalkan browser Anda. Berikut video tampilan situs web tersebut, dan Anda dapat menjalankan contoh file ReplayMod dari video tersebut dengan mengunduhnya di sini.
Randar ditemukan oleh n0pf0x (pcm1k). Tulisan ini ditulis oleh leijurv, dengan beberapa komentar tambahan di bagian akhir ditulis oleh n0pf0x. Pengeksploitasinya adalah 0x22, Babbaj, TheLampGod, leijurv, Negative_Entropy, dan rebane2001. Lihat video TheLampGod di sini. Lihat video faktual 0% HermeticLock yang 100% lucu di sini.
Daftar isi: klik di sini untuk mempelajari lebih lanjut tentang kode yang dapat dieksploitasi, di sini untuk mempelajari tentang bagaimana pengurangan kisi digunakan, di sini untuk melihat bagaimana kami melindungi simpanan kami dari Randar, di sini jika Anda hanya ingin melihat kode eksploitasi lengkap, di sini jika Anda menjalankan server yang masih dalam versi antara Beta 1.8 dan 1.12.2 dan Anda ingin menambal Randar, atau di sini untuk detail tentang apa yang n0pf0x lakukan secara berbeda dari kami.
Diagram kesalahan (dalam bentuk PDF):
Diagram eksploitasi (dalam bentuk PDF):
Diagram contoh eksploitasi yang berhasil (dalam bentuk PDF):
Minecraft mengandalkan angka acak sepanjang permainan. Kebanyakan dari mereka kami harapkan benar-benar acak, seperti keacakan yang digunakan untuk pemijahan massa dan cuaca, namun beberapa dari mereka kami harapkan dapat diprediksi, misalnya kami mengharapkan benih dunia yang sama di lokasi yang sama untuk menghasilkan medan yang sama. Pada tahun 2011, ketika Notch pertama kali menambahkan struktur ke dalam game selama Beta 1.8, dia secara tidak sengaja menggunakan kembali RNG yang seharusnya tidak dapat diprediksi untuk menempatkan Desa di dunia. Sejak saat itu, hingga versi 1.13, kode yang ceroboh ini telah menyebabkan generasi dunia memengaruhi hampir semua kejadian acak lainnya di dalam game. Butuh waktu hingga sekitar Mei 2018, bagi Earthcomputer dan kawan-kawan untuk menemukan kesalahan ini, menyadari bahwa muatan bongkahan memengaruhi RNG game dengan cara yang dapat diamati, lihat penjelasan ini. Namun, mereka tidak menyadari, atau tidak pernah mengungkapkannya secara publik, bahwa Anda juga dapat melakukan ini secara terbalik, dengan menentukan potongan terbaru yang dimuat dari pengamatan RNG. Penemuan itu, Randar, dibuat oleh n0pf0x (alias pcm1k) pada 7 Oktober 2022. Dia memposting deskripsi singkat terenkripsi tentang eksploitasi tersebut di Pastebin sekitar dua minggu setelahnya, untuk membuktikan bahwa dia menemukannya pada saat itu. Dia menggunakan sebagian besar eksploitasi pada 9b9t, dan hanya dalam jumlah yang relatif kecil pada 2b2t dan server lainnya. Pada 2b2t, n0p menemukan dan menjelajahi berbagai lokasi, akhirnya sampai ke lokasi simpanan Gringotts. Dia ditemukan oleh rebane2001, dan awalnya diam tentang bagaimana dia menemukan lokasi tersebut. Namun, sekitar sebulan kemudian, dia memulai percakapan dengan SpawnMason tentang hal itu. n0p mengungkapkan bahwa dia telah menggunakan eksploitasi koordinat yang kuat dan memutuskan untuk berbagi penjelasan dengan kami pada bulan April 2023, karena para tukang batu memiliki pengalaman masa lalu dalam memanfaatkan eksploitasi 2b2t dalam skala yang lebih besar, jadi akan menyenangkan untuk melihat hal itu terjadi lagi, dan n0p adalah menjadi sedikit bosan dengan hal itu. Kami menerima dan mulai mencatat koordinat penurunan item di beberapa akun yang sudah menambang batu/batu bulat 24/7 untuk proyek yang tidak terkait (jadi, tidak ada perubahan perilaku). Kami menggunakan kembali sistem Minecraft tanpa kepala dari nocom dan menambahkan database Postgres untuk mencatat pengukuran. Seperti yang akan dibahas nanti di readme ini, kami melakukan beberapa iterasi perangkat lunak untuk memecahkan pengukuran RNG, dan akhirnya memilih pekerjaan batch Cuda asinkron. Saat pengukuran yang retak ditambahkan ke database, kami juga memperbarui tabel analitik dengan informasi peta panas yang menghitung hit di setiap koordinat pada interval sepanjang waktu, harian, dan setiap jam. Hal ini memungkinkan UI Plotly Dash sederhana untuk memilih data peta panas dari rentang waktu dan rincian tertentu untuk ditampilkan di browser, dan memungkinkan kami menghapus semua spam pemuatan potongan simpanan Elytra dengan hanya mempertimbangkan koordinat yang dimuat dalam lebih dari beberapa jam berbeda. Kami menambahkan sistem anotasi bersama sederhana untuk melacak apa yang kami temukan di setiap hotspot di peta. Sekali lagi menggunakan kembali dari Nocom, kami memiliki bot Bariton yang mengotomatiskan seluruh proses pencurian simpanan item dan menyortir hasilnya, sepenuhnya AFK. Banyak tukang batu yang membantu bagian ini, tanpa mengetahui eksploitasinya, menggunakan akun seperti munmap dan 1248_test_user . Semua simpanan Gringott yang dikumpulkan akhirnya bertambah menjadi 1,3 miliar item, yang sekitar setengahnya disebabkan oleh Nocom dan setengahnya lagi disebabkan oleh Randar.
Sejarah selengkapnya dijelaskan dalam video FitMC.
Peta Minecraft dihasilkan secara prosedural dan pada dasarnya deterministik berdasarkan benih awal dunia. Saat pemain menjelajahi peta, area baru dihasilkan sesuai permintaan saat pemain semakin dekat. Karena semua generasi dimaksudkan untuk dapat diulang (deterministik), sangat masuk akal jika mereka menggunakan java.util.Random di banyak tempat. Mereka ingin hal itu dapat diprediksi. Inilah sebabnya mengapa java.util.Random digunakan, karena ini adalah PRNG (bukan RNG sebenarnya). P secara teknis berarti "semu" tetapi menganggapnya "dapat diprediksi". RNG yang dapat diprediksi. Ini menghasilkan angka-angka yang tampak acak, tetapi sebenarnya dapat diulang jika diberi benih awal yang sama.
Minecraft memiliki berbagai struktur yang dihasilkan di dunia, seperti desa, monumen laut, benteng, dll. Ini adalah bagian dari generasi prosedural, sehingga mereka juga ditempatkan dan dihasilkan secara deterministik.
Hanya ada selusin baris kode Minecraft yang diperlukan untuk memahami hal ini, dan saya telah menyederhanakan dan banyak berkomentar:
// (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)
}Di atas diberi komentar dan sedikit dimodifikasi untuk kejelasan, tetapi secara fungsional akurat dengan kode sebenarnya.
Jadi idenya adalah untuk memutuskan ke mana Woodland Mansion harus berada di wilayah Woodland ini (yang berukuran 80 kali 80), periksa apakah tempat itu ada di sini , dan jika demikian, buatlah Woodland Mansion mulai dari sini.
Kode ini mungkin terlihat sedikit konyol, Anda mungkin berpikir "tidak masuk akal untuk melakukan semua pemeriksaan ini pada setiap bagian, cukup pilih ke mana Woodland Mansions harus pergi satu kali per wilayah dan selesaikan". Alasannya adalah bongkahan Minecraft dihasilkan secara independen satu sama lain, dan dalam urutan yang tidak diketahui, namun kami tetap ingin menghasilkan dunia deterministik dari benih tertentu. Kami tidak tahu dalam urutan apa pemain akan berjalan keliling dunia, dan senang rasanya bisa membuat potongan apa pun sesuai permintaan dengan cara tanpa kewarganegaraan. Ini pengalaman bermain yang bagus. Jadi, kodenya terlihat aneh seperti ini.
Bagaimanapun, kode itu dipanggil pada setiap bongkahan yang dimuat, untuk setiap bongkahan dalam kotak besar di sekitar yang sedang dimuat. Agak rumit untuk menjelaskan alasannya, jadi saya akan melewatkannya (ide dasarnya adalah bahwa struktur ini (jauh) lebih besar dari ukuran satu bongkahan, jadi kita perlu memeriksa asal struktur di banyak bongkahan terdekat untuk menghasilkan yang sekarang ini dengan benar).
Perhatikan bahwa ini hanya mempengaruhi Dunia Atas. Nether aman, karena semua pembuatan strukturnya selalu menggunakan RNG yang aman. Pemuatan bongkahan di The End terpengaruh karena kota-kota akhir, namun hanya pada generasi awalnya, tidak setiap kali dimuat berikutnya, sehingga The End relatif aman karena setiap bongkahan di basis Anda hanya memengaruhi RNG satu kali saat Anda pertama kali memuat dia. Namun, hal ini tidak sepenuhnya mudah dilakukan, karena pemain biasanya membuat bongkahan baru setiap kali melakukan perjalanan ke markasnya, dan terkadang membuat bongkahan baru saat sudah berada di markasnya.
Masalahnya adalah hal itu mengubah benih World.rand global. Ini hanya pengkodean yang malas. Yang mereka lakukan hanyalah memanggil nextInt empat kali untuk memilih koordinat X dan Z. Mereka bisa saja mengganti Random random = this.world.setRandomSeed(... dengan Random random = new Random(the same stuff) (dengan kata lain, buat Random baru di sini daripada mengotak-atik yang sudah ada yang digunakan oleh yang lain? ??).
Yang terpenting, setRandomSeed dipanggil untuk memeriksa ke mana Woodland Mansion harus pergi. Hal ini terjadi apa pun yang terjadi, pada setiap beban bongkahan, di mana pun. Anda tidak harus berdiri di/dekat Woodland Mansion atau semacamnya.
Ternyata World.rand digunakan di ratusan tempat, dan banyak dari tempat tersebut dapat dengan mudah diamati dengan memainkan game secara normal. Misalnya, saat Anda menambang satu blok:
/**
* 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 );
}Sekali lagi, sedikit dimodifikasi, tetapi secara fungsional akurat untuk hal yang sedang kita bicarakan.
Idenya di sini adalah bahwa di Minecraft ketika Anda menambang sebuah blok, ia menjatuhkan sebuah item. Item tersebut dijatuhkan pada posisi acak di dalam blok. Misalnya, jika blok berada di (10, 20, 30) , item akan muncul di antara (10.25, 20.25, 30.25) dan (10.75, 20.75, 30.75) .
Dan lokasi pasti item tersebut dipilih dengan memanggil world.rand.nextFloat() tiga kali berturut-turut, untuk X, Y, dan Z.
Hanya itu kode Minecraft yang dibutuhkan!
Sekarang, saya katakan bahwa kita dapat melakukan sesuatu dengan panggilan nextFloat ini. Pertama, mari kita lihat apakah kita bisa "bekerja mundur" untuk melihat panggilan nextFloat . Ini cukup beruntung, tapi sebenarnya kami bisa. Catatan pada kode di atas: random float dikalikan 0,5, lalu ditambah 0,25. Idenya adalah untuk berpindah dari angka acak antara 0 dan 1 ke angka acak antara 0,25 dan 0,75. Anda mungkin khawatir, karena jika Anda membagi bilangan bulat dengan dua, Anda akan kehilangan sedikit informasi karena hasilnya dibulatkan ke bawah. Untungnya, mengalikan float dengan 0,5 benar-benar dapat dibalik, karena ini hanya mengurangi eksponennya tanpa menyentuh mantissa. Kemudian, pelampung dicor menjadi ganda, yang memiliki presisi lebih tinggi. Ditambahkan 0,25, lalu ditambahkan koordinat bloknya. Kemudian, dikirim ke klien melalui jaringan dengan presisi penuh. Hasilnya: seluruh proses ini dapat dibalik sehingga kita bisa mendapatkan tiga float yang dihasilkan World.rand.nextFloat() .
Bagaimana java.util.Random menghasilkan float? Sebenarnya itu cukup sederhana. Ini menghasilkan bilangan bulat antara 0 dan 2^24, lalu membaginya dengan 2^24 (menghasilkan angka antara 0 dan 1). Bagaimana cara mendapatkan bilangan bulat acak itu? Juga cukup sederhana! Ini adalah generator kongruensial linier (LCG). Artinya, benih berikutnya adalah benih sebelumnya dikalikan sesuatu, ditambah sesuatu yang lain, modulo sesuatu yang lain.
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
}Dalam hal ini, pengalinya adalah 25214903917, penjumlahannya adalah 11, dan modulusnya adalah 2^48.
Dengan float yang keluar dari ini, kita dapat mengalikannya dengan 2^24 untuk mendapatkan kembali randomInteger, dan oleh karena itu mendapatkan "setengah atas" (24 bit paling signifikan) dari benih 48 bit.
Singkatnya, dari pengukuran kita, kita mengetahui bahwa seed berada di antara measuredRandomInteger * 2^24 dan (measuredRandomInteger + 1) * 2^24 .
Dan kita bisa melakukan ini tiga kali berturut-turut, untuk X, Y, dan Z.
Dan kita tahu bahwa antara X dan Y, dan antara Y dan Z, seed diperbarui menurut newSeed = (oldSeed * 25214903917 + 11) mod 2^48
Saya harus menyebutkan bahwa salah satu opsi yang valid adalah for-loop yang mencoba semua 2^24 kemungkinan bit yang lebih rendah. Bagi programmer yang membaca ini, saya harap ini menjelaskan apa masalahnya:
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 ;
}
}Ini akan berhasil, dan memang berhasil, tetapi tidak secepat dan tidak menyenangkan. Jadi kami menggunakan kisi sebagai gantinya!
Namun, saya merasa harus sedikit keluar dari urutan. Bagian pengurangan kisi memang ada di sini, tetapi ini sangat rumit dan saya yakin retensi pembacanya akan rendah dan saya tidak ingin kehilangan Anda. Jadi saya hanya akan memberi Anda solusi for-loop (yang TIDAK berfungsi), dan melanjutkan ke langkah eksploitasi berikutnya. Penjelasan tentang metode pengurangan kisi akan muncul setelahnya :)
Apa yang kita lakukan dengan benih ini setelah kita memilikinya?
Pertama, perhatikan bahwa kita dapat melangkah mundur pada LCG. Tentu saja, penjumlahan sebelas dapat dibalik, tetapi apakah mengalikan dengan angka sebesar itu dapat dibalik? Pengganda kita 25214903917 adalah bilangan ganjil, artinya bilangan tersebut tidak habis dibagi dua, dan oleh karena itu bilangan tersebut tidak berbagi faktor apa pun dengan modulus kita 2^48 (karena 2^48 secara harafiah hanyalah kumpulan dua). Karena bilangan tersebut relatif prima terhadap modulusnya, kita dapat membaliknya, artinya mencari bilangan x lain yang memenuhi x * 25214903917 - 1 habis dibagi 2^48. Atau dengan kata lain 25214903917 * x mod 2^48 = 1 . Nomor itu adalah 246154705703781 . Ini membantu membalikkan perkalian karena jika kita memiliki, misalnya, secret * 25214903917 dan kita ingin mencari tahu secret , kita tinggal menghitung secret * 25214903917 * 246154705703781 mod 2^48 = secret * 1 mod 2^48 = secret .
Oke, jadi kita bisa melangkahkan benih internal java.util.Random maju dan mundur. Maju adalah newSeed = (oldSeed * 25214903917 + 11) mod 2^48 dan mundur adalah oldSeed = ((newSeed - 11) * 246154705703781) mod 2^48 . Dan ini berhasil karena angka-angka itu 25214903917 dan 246154705703781 , jika dikalikan bersama-sama, akan menghasilkan 1 saat Anda mengambilnya mod 2^48.
Sekarang, saat kita melangkah mundur, kami ingin memeriksa di setiap langkah apakah benih ini dapat berarti bahwa pemeriksaan Woodland Mansion baru-baru ini dilakukan di suatu tempat di dunia (inti dari eksploitasi). Bagaimana kita melakukan itu?
Dunia Minecraft berkisar antara -30 juta hingga +30 juta blok. Setiap "wilayah Woodland" (wilayah di dunia di mana satu Woodland Mansion ditempatkan secara acak, sesuai kode yang ditunjukkan sebelumnya) berukuran 80 kali 80 bongkahan, yaitu 1280 kali 1280 blok. Ini adalah 23437.5 Wilayah hutan, namun untuk seluruh kode, kami baru saja membulatkannya menjadi 23440 karena ini adalah angka bulat dan meskipun pemain Anda tidak dapat melakukan perjalanan lebih dari 30 juta, Anda memuat bongkahan lebih dari itu hanya dengan berdiri di dekatnya, dan kami hanya tidak ingin harus khawatir tentang semua itu.
Jadi, -23440 hingga +23440 pada sumbu X dan Z. Itu (23440*2+1)^2 (alias 2197828161 ) kemungkinan wilayah Woodland, yang masing-masing menghasilkan "benih rumah besar" yang unik (didefinisikan sebagai benih yang mengungkapkan bahwa seseorang baru saja memuat bongkahan di wilayah Woodland tertentu). Kita harus bisa memeriksa apakah ada sesuatu yang merupakan benih rumah besar. Bisakah kita mengulangi 2,2 miliar benih rumah besar untuk memeriksa masing-masing benih? Akan terlalu lambat. Bisakah membuat HashSet<Long> dengan 2,2 miliar entri? Akan memakan terlalu banyak RAM bahkan menggunakan peta kronik seperti yang kami lakukan di nocom, dan bahkan di C++ menggunakan abseil-cpp digunakan seperti ram 50gb. Dan itu belum lagi bagian lainnya: kami sebenarnya ingin mengetahui di mana mereka berada di dunia (itulah intinya). Jadi tidak cukup hanya mengetahui bahwa ini adalah benih rumah besar, kami juga ingin (secara efisien) mengetahui wilayah Woodland mana yang menyebabkannya.
Ingat kembali fungsi yang berpindah dari Woodland Region ke mansion seed (catatan: Saya sekarang telah menggabungkan beberapa konstanta sejak kode di atas untuk kesederhanaan, persamaan ini sekarang dikhususkan untuk seed 2b2t ):
seed = x * 341873128712 + z * 132897987541 - 4172144997891902323 mod 2^48
(angka -4172144997891902323 berasal dari -4172144997902289642 + 10387319 , yang merupakan benih dunia 2b2t + nilai ajaib yang digunakan untuk menyemai wilayah Hutan (seperti yang ditunjukkan sebelumnya). Untuk dunia lain, Anda cukup memasukkan benih Anda sendiri ke dalam persamaan ini .)
Tidak banyak yang dapat kita lakukan dengan koordinat x, karena koordinat tersebut dikalikan dengan bilangan genap. Tapi berapakah koefisien pada koordinat z itu? Sepertinya angka ganjil!!! Mari kita gunakan trik yang sama seperti sebelumnya untuk membalikkannya lagi, dan kita mendapatkan 211541297333629 .
Bayangkan kita mempunyai benih tertentu. Bagaimana jika kita dapat mengulangi semua kemungkinan koordinat X dari -23440 hingga +23440, dan untuk masing-masing koordinat tersebut, hitung berapa koordinat Z wilayah Woodland, JIKA wilayah tersebut memiliki rumah besar seed . Dengan kata lain, persamaan di atas memberikan kita seed jika kita mengetahui x dan z , namun bisakah kita membuat persamaan yang memberikan z jika kita mengetahui seed dan x ? Jawaban: ya. Kita tinggal menyusun ulang persamaan di atas, dan menggunakan fakta bahwa koefisien Z dapat dibalik mod 2^48 karena merupakan bilangan ganjil.
Persamaannya adalah:
z = (seed + 4172144997891902323 - x * 341873128712) * 211541297333629 mod 2^48
Jadi ini adalah solusi yang cukup bagus karena daripada dua loop bersarang (satu untuk X dan satu untuk Z) yang melakukan total 2,2 miliar iterasi, kita dapat memiliki satu for-loop untuk X yang hanya melakukan 46.881 iterasi. Ini dia di Jawa:
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 ;
} (catatan: << 16 >> 16 yang aneh sedang melakukan mod 2^48, tetapi sebenarnya kami ingin melakukannya menggunakan tipe yang ditandatangani sehingga kami masih mendapatkan jawaban yang benar ketika z berada di antara -23440 dan 0, ini adalah cara untuk tanda-perpanjang bilangan 48-bit menjadi 64 bit, isi 16 bit teratas dengan bit tanda yang benar untuk komplemen dua)
Jadi ini berhasil dan cukup cepat.... untuk satu benih. Tapi ingat bahwa kita mundur dari RNG ke ribuan langkah, dan menjalankan pemeriksaan ini di setiap langkah sampai kita menemukan kecocokan. Pada saat itu, kami menggunakan tetesan DigitalOcean yang buruk pada tingkat terendahnya, dan ini benar-benar memperlambat semuanya dan tidak dapat mengimbangi waktu nyata (bot menambang banyak blok per detik, setiap blok membutuhkan ribuan langkah untuk memecahkannya, dan setiap langkah memerlukan 23440*2+1 operasi untuk diperiksa, kalikan semuanya dan Anda akan mendapatkan ratusan juta operasi per detik, sehingga Anda mengerti mengapa hal itu menimbulkan masalah pada VPS jelek, terutama ketika VPS tersebut juga mencoba menjalankan beberapa contoh Minecraft tanpa kepala).
Jadi kami beralih ke pendekatan tabel pencarian dan menulis ulang di Cuda untuk dijalankan di desktop saya sebagai pekerjaan batch setiap beberapa menit. Ia dapat melakukan jutaan per detik karena masing-masing dari ribuan inti cuda dapat bekerja pada benihnya sendiri secara paralel. Begini idenya: kunci tabel pencarian adalah 32 bit terbawah dari benih mansion, dan nilainya adalah koordinat X wilayah Woodland. Tabel pencarian ini berfungsi tanpa benturan karena setiap seed mansion memiliki 32 bit rendah yang unik. Saya tidak mengerti mengapa hal itu benar, ini menarik. Anda akan berpikir itu tidak akan berhasil. Namun menurut saya koefisien 341873128712 dan 132897987541 mungkin dipilih secara khusus agar ini berhasil? Misalnya, jika Anda mempunyai 2,2 miliar kelereng, dan 4,3 miliar ember, dan Anda secara mandiri memasukkan setiap kelereng ke dalam ember acak, berapa peluang setiap kelereng mendapatkan embernya sendiri? Intinya nol. Menjelang akhir, setiap kelereng baru memiliki peluang lebih dari 50% untuk mengenai ember yang sudah terisi. Namun, yang jelas, ini tidak acak secara independen, jadi entah bagaimana cara ini berhasil. Ironisnya jika Anda membaca ini dan memahami cara kerjanya atau mengapa kedua koefisien spesifik tersebut membuat ini berhasil, beri tahu saya. Bagaimanapun, itu berhasil. Tabel pencarian memiliki 2^32 entri, dan setiap entri berukuran 2 byte (karena ini hanya angka antara -23440 dan +23440), jadi ini memerlukan sekitar 9 gigabyte VRAM pada GPU Anda.
Fungsi pemeriksaan hutan sekarang terlihat seperti (sekali lagi, ini adalah kode sebenarnya tetapi disederhanakan, semua pembantu dan konstanta disisipkan, dll):
__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;
}Ini berfungsi dengan baik dalam batch besar dan dapat memecahkan sepuluh juta benih per detik pada 3090. Ternyata tidak menjadi masalah besar ketika beberapa thread dalam warp berakhir lebih awal, dan kami tidak dapat benar-benar membuatnya. itu lebih cepat dari ini. (alasannya adalah pada dasarnya kita tidak bisa mengetahui sebelumnya benih mana yang akan mengambil langkah lebih banyak/lebih sedikit).
Ya, itu saja. Mengingat benihnya, itulah cara kita mendapatkan kawasan Woodland di dunia tempat terjadinya muatan bongkahan terbaru. Dengan kata lain, kita baru mengetahui bahwa terakhir kali seseorang berjalan di sekitar 2b2t dan memuat area baru di dunia, adalah di suatu tempat di wilayah Woodland berukuran 1280 x 1280 blok yang baru saja kita identifikasi. (itu cukup tepat sehingga menemukannya hanya membutuhkan beberapa menit pencarian)
Dalam praktiknya, berapa banyak langkah RNG yang diperlukan? Pada tingkat rendah, pengukuran yang andal dimulai dari 4 langkah RNG, semua yang di bawah ini adalah kesalahan pengukuran/kebisingan acak, yang kita ketahui karena kode Woodland Mansion segera memanggil rand.nextInt empat kali sebelum kita dapat mengukurnya. Rata-rata, terdapat sekitar 128.000 langkah di antara setiap benih Woodland, namun dalam praktiknya, sebagian besar waktu di 2b2t, kami menemukan benih Woodland dalam jarak beberapa lusin langkah. Hal ini disebabkan oleh rincian tentang apa yang terjadi dalam urutan centang Minecraft. Pengukuran kami secara teknis terjadi di awal tick, karena di sanalah paket untuk memecahkan blok diproses. Secara umum, sebuah potongan telah dimuat dalam riwayat terkini pada tick sebelumnya. Namun, terkadang, suatu peristiwa dapat menyebabkan banyak langkah RNG di antaranya. Kami percaya bahwa peristiwa ini adalah ledakan, seperti seseorang meledakkan kristal ujung dengan cara meninju, atau mungkin membuat tengkorak menjadi layu. Ledakan kristal akhir juga akan terjadi selama pemrosesan paket dari paket pukulan pemain, dan jumlah langkah RNG juga berbaris pada 1354 langkah (1352 dari perhitungan kerusakan blok dalam sebuah kubus
Dan pada koordinat yang digunakan sebagai contoh kerja pada diagram ini, inilah yang dihasilkan oleh kode di atas:
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>
Perhatikan bagaimana lokasinya Woodland Region 123,456 , dan perhatikan bagaimana "menempatkan seseorang di antara" terakhir menyertakan koordinat sebenarnya yang awalnya kita masukkan, yaitu x=157440 z=583680. Selain itu, pengukuran RNG cocok dengan heksadesimal berwarna merah: 0xf61dc9 sama dengan 16129481 , 0x1700fb sama dengan 1507579 , dan 0xc50d15 sama dengan 12913941 . Dan untuk seed, 0xed92e70ba4a0 sama dengan 261215197308064 dan 0xf61dc9221ba4 sama dengan 270607788940196 .
Anda mungkin dapat menemukan tambalan atau opsi konfigurasi untuk menonaktifkan manipulasi RNG, sesuatu seperti itu akan berfungsi untuk menambal Randar dan mungkin itu cara termudah. Jika Anda tidak dapat menemukan cara mudah untuk menonaktifkan manipulasi RNG, berikut adalah kode yang perlu diubah di kelas World :
Versi rentan:
public Random setRandomSeed ( int seedX , int seedY , int seedZ ) {
this . rand . setSeed ( seedX * 341873128712L + seedY * 132897987541L + seedZ + this . getWorldInfo (). getSeed ());
return this . rand ;
}Cukup ubah fungsi ini untuk mengembalikan Acak yang berbeda setiap kali, jika Anda menginginkan perlindungan sempurna:
Versi yang ditambal:
public Random setRandomSeed ( int seedX , int seedY , int seedZ ) {
return new Random ( seedX * 341873128712L + seedY * 132897987541L + seedZ + this . getWorldInfo (). getSeed ());
} Itu mungkin tidak memiliki kinerja yang bagus, jadi jika mau, Anda dapat memperkenalkan bidang baru, separateRandOnlyForWorldGen , yang tidak dibagikan dengan bidang lain, misalnya:
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 ;
}Jika Anda menggunakan PaperMC untuk 1.12.2 , berikut adalah patch yang dapat Anda terapkan. Tautan alternatif.
Ini akan menjadi bagian tambahan di mana saya membahas beberapa hal tambahan yang lebih masuk akal untuk dijelaskan dari sudut pandang saya, karena selain ide dasar, kami kebanyakan mengembangkan sesuatu secara mandiri.
Hal pertama yang ingin saya sampaikan adalah sistem untuk menemukan koordinat dari sebuah seed. Mason menggunakan tabel pencarian besar dan pemrosesan GPU, saya mengandalkan cache untuk kecepatan. Setiap kali terjadi serangan, koordinatnya, dan semua koordinat dalam radius dimasukkan ke dalam HashMap. Benih diproses dalam dua tahap. Proses pertama akan mengembalikan RNG, dan memeriksa apakah seed ada di cache, atau merupakan seed yang sama yang diproses terakhir kali, yang dianggap berbeda. Pass kedua hanya terjadi jika pass pertama gagal, jauh lebih lambat, dan menggunakan algoritma yang relatif mahal yang dijelaskan sebelumnya. Efek samping yang menyenangkan dari sistem ini, adalah bahwa lintasan pertama berpotensi "melewati" lokasi yang "valid", tetapi kecil kemungkinannya menjadi lokasi yang benar, sehingga membantu menghasilkan kesalahan positif.
Ini kode itu:
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
