Cada vez que um bloco é quebrado nas versões Beta 1.8 a 1.12.2 do Minecraft, as coordenadas precisas do item descartado podem revelar a localização de outro jogador .
"Randar" é um exploit para Minecraft que usa redução de rede LLL para quebrar o estado interno de um java.util.Random reutilizado incorretamente no servidor Minecraft e, em seguida, trabalha de trás para frente para localizar outros jogadores atualmente carregados no mundo.
Clique aqui para saber mais sobre Randar na forma de um vídeo no YouTube.
Assista ao lapso de tempo:
Veja mais timelapses aqui (como arquivos) ou aqui (como YouTube).
O objetivo é determinar as localizações no jogo (ou seja, as coordenadas) dos outros jogadores no mundo, não importa a distância que estejam. Estamos jogando no 2b2t, que é o mais antigo e famoso servidor de "anarquia" do Minecraft (o que significa que não há regras, ou seja, os jogadores não são banidos por qualquer motivo). Fazer coisas assim é o "ponto" deste servidor. Neste servidor, a única coisa que mantém suas coisas seguras é que o mapa é enorme (3,6 quatrilhões de peças quadradas) e ninguém mais sabe onde você está. Portanto, é um grande negócio (um acordo revolucionário) ter uma exploração coordenada. (falando nisso, antes de Randar também tivemos outra exploração coordenada em 2b2t, Nocom, de 2018 a 2021; veja esse artigo aqui, tópico HackerNews, YT)
O erro no código do Minecraft está presente desde as versões Beta 1.8 (lançada em 2011) até 1.12.2 (lançada em 2017, mas 2b2t permaneceu nesta versão até 14 de agosto de 2023). O erro é que várias instâncias do gerador de números aleatórios, java.util.Random , são reutilizadas de maneira descuidada em várias partes do código (e, para começar, são inseguras). Especificamente, há reutilização de RNG entre a geração de terreno e ações de jogo, como mineração de blocos.
A exploração resumiu:
World.rand global tem sua semente redefinida para uma função das coordenadas do pedaço, a fim de verificar onde deveria estar uma Woodland Mansion próxima (e se é este pedaço em particular).World.rand.nextFloat() para escolher as coordenadas XY e Z entre 0 e 1. O bot registra o carimbo de data/hora e os valores XYZ precisos.World.rand que causou essas três flutuações. Em termos gerais (mais detalhes virão mais tarde), observar uma saída do RNG poderia implicar qualquer um dos cerca de 16 milhões de estados internos possíveis do RNG. No entanto, amostramos a saída do RNG não apenas uma, mas três vezes seguidas (as coordenadas X, Y e Z do item descartado) e sabemos como o estado interno é atualizado entre cada chamada (uma simples multiplicação , adicione e modifique); portanto, podemos usar métodos de rede para reduzi-lo instantaneamente à única possibilidade.java.util.Random pode ser retrocedido tão facilmente quanto avançado, e retrocedendo podemos encontrá-lo em apenas alguns milhares de passos (mesmo em servidores ocupados como 2b2t com muitos jogadores e, portanto, pesados). uso de RNG), que identifica o momento mais recente em que o estado interno do RNG foi redefinido e, portanto, a localização do bloco mais recente que foi carregado no servidor.Mesmo se você jogar em um servidor que foi atualizado para uma versão mais recente do Minecraft ou que corrigiu a manipulação de RNG, suas coordenadas ainda estarão em risco devido ao Randar devido à capacidade de explorar dados RNG retroativamente. Alguns jogadores do Minecraft usam mods como o ReplayMod que registram pacotes e ainda podem ter esses arquivos de registro por aí. Se alguém estava usando tal mod enquanto você estava em sua base, eles podem ter (sem saber) gravado dados RNG que poderiam revelar sua localização, porque quebrar blocos é uma ação extremamente comum que provavelmente aconteceu nessas gravações, e cada um desses blocos break revela o estado RNG do servidor e, portanto, a localização do bloco carregado mais recentemente. Isso significa que Randar é um grande negócio: devido ao risco de exploração retroativa, em todos os servidores do Minecraft, todos os locais que estavam ativos nas versões Beta 1.8 a 1.12.2 devem ser considerados comprometidos, mesmo que o servidor já tenha sido atualizado há muito tempo para além da versão 1.12. .2 ou manipulação RNG corrigida.
Se você quiser usar o exploit Randar sozinho , clique aqui, onde rebane2001 criou um site onde você pode arrastar seus arquivos ReplayMod de 1.12.2 e ver as coordenadas de outros jogadores. Ele é executado no lado do cliente para que suas gravações não saiam do navegador. Aqui está um vídeo da aparência desse site em ação, e você pode executar o arquivo ReplayMod de exemplo desse vídeo baixando-o aqui.
Randar foi descoberto por n0pf0x (pcm1k). Este artigo foi escrito por leijurv, com alguns comentários adicionais no final escritos por n0pf0x. Os exploradores foram 0x22, Babbaj, TheLampGod, leijurv, Negative_Entropy e rebane2001. Veja o vídeo de TheLampGod aqui. Veja o vídeo 100% humorístico e 0% factual do HermeticLock aqui.
Índice: clique aqui para saber mais sobre o código explorável, aqui para saber como a redução de rede foi usada, aqui para ver como protegemos nossos próprios stashes do Randar, aqui se você quiser apenas ver o código de exploração completo, aqui se você executa um servidor que ainda está em uma versão entre Beta 1.8 e 1.12.2 e deseja corrigir Randar, ou aqui para obter detalhes sobre o que n0pf0x fez de diferente de nós.
Diagrama do erro (como PDF):
Diagrama da exploração (como PDF):
Diagrama de um exemplo prático de exploração (como PDF):
O Minecraft depende de números aleatórios ao longo do jogo. Esperamos que a maioria deles seja realmente aleatória, como a aleatoriedade usada para a geração de mobs e o clima, mas esperamos que alguns deles sejam previsíveis, por exemplo, esperamos que a mesma semente mundial no mesmo local gere o mesmo terreno. Em 2011, quando Notch adicionou estruturas ao jogo pela primeira vez durante o Beta 1.8, ele acidentalmente reutilizou um RNG que deveria ser imprevisível para colocar Aldeias no mundo. Desde então, até 1.13, esse código desleixado fez com que a geração do mundo influenciasse quase todos os outros eventos supostamente aleatórios do jogo. Demorou até cerca de maio de 2018 para que Earthcomputer e amigos descobrissem esse erro, percebendo que as cargas de pedaços afetam o RNG do jogo de forma observável, veja esta explicação. No entanto, eles não perceberam, ou simplesmente nunca revelaram publicamente, que você também pode fazer isso de trás para frente, determinando o pedaço carregado mais recentemente a partir da observação do RNG. Essa descoberta, Randar, foi feita por n0pf0x (também conhecido como pcm1k) em 7 de outubro de 2022. Ele postou uma descrição curta e criptografada da exploração no Pastebin cerca de duas semanas depois, para provar que a descobriu então. Ele usou o exploit principalmente no 9b9t, e apenas uma quantidade relativamente pequena no 2b2t e em outros servidores. Em 2b2t, n0p localizou e explorou vários locais, eventualmente chegando a um esconderijo de Gringotes. Ele foi localizado por rebane2001 e inicialmente não falou sobre como encontrou o local. No entanto, cerca de um mês depois, ele iniciou uma conversa com os SpawnMasons sobre isso. n0p revelou que usou um poderoso exploit de coordenadas e decidiu compartilhar uma explicação conosco em abril de 2023, porque os maçons têm experiência anterior em tirar vantagem de exploits 2b2t em maior escala, então seria divertido ver isso acontecer novamente, e n0p foi ficando um pouco entediado com isso de qualquer maneira. Aceitamos e começamos a registrar as coordenadas de queda de itens em diversas contas que já estavam minerando pedras/paralelepípedos 24 horas por dia, 7 dias por semana, para um projeto não relacionado (portanto, não houve mudança de comportamento). Reutilizamos o sistema Minecraft sem cabeça da nocom e adicionamos um banco de dados Postgres para registrar as medições. Conforme discutido posteriormente neste leia-me, passamos por várias iterações de software para quebrar as medições RNG, eventualmente optando por um trabalho em lote Cuda assíncrono. À medida que medições quebradas foram adicionadas ao banco de dados, também atualizamos uma tabela analítica com informações de mapa de calor que contava ocorrências em cada coordenada em intervalos de tempo, diariamente e de hora em hora. Isso permitiu que uma interface simples do Plotly Dash selecionasse dados de mapa de calor de intervalos de tempo e granularidades específicos para exibição em um navegador, e nos permitiu remover todo o spam de carregamento de pedaços de stashhunting do Elytra, considerando apenas as coordenadas que foram carregadas em mais de algumas horas distintas. Adicionamos um sistema simples de anotação compartilhada para acompanhar o que encontramos em cada ponto de acesso no mapa. Novamente reutilizando do Nocom, temos bots Barítono que automatizam todo o processo de roubo de estoques de itens e classificação dos resultados, completamente AFK. Muitos pedreiros ajudaram nessa parte, sem conhecer o exploit, usando contas como munmap e 1248_test_user . Todos os estoques de Gringotes juntos cresceram para 1,3 bilhão de itens, dos quais cerca de metade é atribuível à Nocom e a outra metade à Randar.
A história completa é explicada no vídeo FitMC.
O mapa do Minecraft é gerado processualmente e essencialmente determinístico com base na semente inicial do mundo. À medida que os jogadores exploram o mapa, novas áreas são geradas sob demanda conforme os jogadores se aproximam. Como toda a geração deve ser repetível (determinística), é perfeitamente razoável que eles tenham usado java.util.Random em vários lugares. Eles querem que seja previsível. É por isso que java.util.Random é usado, já que é um PRNG (não realmente um RNG). O P significa tecnicamente “pseudo”, mas pense nele como “previsível”. RNG previsível. Ele gera números que parecem aleatórios, mas na verdade são repetíveis com a mesma semente inicial.
O Minecraft possui diversas estruturas que são geradas no mundo, como vilas, monumentos oceânicos, fortalezas, etc. Estas fazem parte da geração processual, portanto também são colocadas e geradas de forma determinística.
São necessárias apenas uma dúzia de linhas de código do Minecraft para entender isso, e eu simplifiquei e comentei bastante:
// (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)
}O texto acima foi comentado e ligeiramente modificado para maior clareza, mas é funcionalmente preciso em relação ao código real.
Então a ideia é decidir onde a Mansão da Floresta deve ficar nesta região da Floresta (que tem 80 por 80 pedaços), verificar se esse lugar é bem aqui e, em caso afirmativo, gerar uma Mansão da Floresta começando aqui mesmo.
Este código pode parecer um pouco bobo, você pode estar pensando "é um absurdo fazer todas essas verificações em cada pedaço, basta escolher onde Woodland Mansions deve ir uma vez por região e pronto". A razão é que os pedaços do Minecraft são gerados independentemente uns dos outros e em ordem desconhecida, mas ainda queremos gerar um mundo determinístico a partir de uma determinada semente. Não sabemos em que ordem o jogador irá percorrer o mundo, e é bom poder gerar qualquer pedaço sob demanda de maneira sem estado. É uma boa experiência de jogo. Portanto, um código de aparência estranha como este.
De qualquer forma, esse código é chamado a cada pedaço carregado, para cada pedaço em um grande quadrado ao redor daquele que está sendo carregado. É um pouco complicado explicar o porquê, então vou ignorá-lo (a idéia básica é que essas estruturas são (muito) maiores do que um pedaço em tamanho, então precisamos verificar se há uma origem de estrutura em muitos pedaços próximos para gerar este atual corretamente).
Observe que isso afeta apenas o mundo superior. O Nether é seguro, pois toda a sua geração de estrutura sempre utilizou RNG seguro. O carregamento de pedaços em The End é afetado devido às cidades finais, mas apenas em sua geração inicial, não em todas as vezes subsequentes em que são carregados, portanto, The End é relativamente seguro porque cada pedaço em sua base afeta o RNG apenas uma vez quando você carrega pela primeira vez isto. No entanto, isso não é totalmente infalível, já que os jogadores geralmente geram novos pedaços cada vez que viajam para sua base e, ocasionalmente, geram novos pedaços enquanto já estão em sua base.
O problema é que isso modifica a semente do World.rand global. Isso é apenas codificação preguiçosa. Tudo o que eles estão fazendo é chamar nextInt quatro vezes para escolher as coordenadas X e Z. Eles poderiam ter substituído Random random = this.world.setRandomSeed(... por Random random = new Random(the same stuff) (em outras palavras, fazer um novo Random aqui em vez de mexer com o existente que é usado por todo o resto? ??).
Crucialmente, o setRandomSeed é chamado para verificar onde a Woodland Mansion deve ir. Isso acontece não importa o que aconteça, em cada carga de bloco, em qualquer lugar. Você não precisa estar perto da Woodland Mansion ou algo assim.
Bem, acontece que World.rand é usado em literalmente centenas de lugares, e muitos desses lugares podem ser facilmente observados jogando normalmente. Por exemplo, quando você extrai um bloco:
/**
* 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 );
}Novamente, ligeiramente modificado, mas funcionalmente preciso para o que estamos falando.
A ideia aqui é que no Minecraft, quando você extrai um bloco, ele deixa cair um item. O item é largado em uma posição aleatória dentro do bloco. Por exemplo, se o bloco estava em (10, 20, 30) , o item aparecerá em algum lugar entre (10.25, 20.25, 30.25) e (10.75, 20.75, 30.75) .
E a localização exata desse item é escolhida chamando world.rand.nextFloat() três vezes seguidas, para X, Y e Z.
Isso é todo o código do Minecraft necessário!
Agora, eu disse que podemos fazer algo com essas chamadas nextFloat . Primeiro, vamos ver se podemos "trabalhar de trás para frente" para ver quais são as chamadas nextFloat . É muita sorte, mas realmente podemos. Observe no código acima: o float aleatório é multiplicado por 0,5 e depois adicionado a 0,25. A ideia é passar de um número aleatório entre 0 e 1 para um número aleatório entre 0,25 e 0,75. Você pode estar preocupado, porque se dividir um número inteiro por dois, perderá um pouco de informação, pois o resultado é arredondado para baixo. Felizmente, multiplicar um float por 0,5 é totalmente reversível, pois apenas diminui o expoente, deixando a mantissa intacta. Então, o float é convertido em um double, que tem muito mais precisão. 0,25 é adicionado e, em seguida, a coordenada do bloco é adicionada. Em seguida, ele é enviado ao cliente pela rede com total precisão. O resultado: todo esse processo é reversível para que possamos obter exatamente os três carros alegóricos que World.rand.nextFloat() produziu.
Como java.util.Random gera carros alegóricos? Bem, na verdade é bem simples. Ele gera um número inteiro entre 0 e 2 ^ 24 e depois o divide por 2 ^ 24 (resultando em um número entre 0 e 1). Como ele consegue esse número inteiro aleatório? Também muito simples! É um gerador congruencial linear (LCG). Isso significa que a próxima semente é a semente anterior vezes alguma coisa, mais alguma outra coisa, módulo outra coisa.
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
}Nesse caso, o multiplicador é 25214903917, o adendo é 11 e o módulo é 2^48.
Com o float resultante disso, podemos multiplicá-lo por 2 ^ 24 para retornar o randomInteger e, portanto, obter a "metade superior" (os 24 bits mais significativos) da semente de 48 bits.
Resumindo, com nossa medição, aprendemos que a semente está entre measuredRandomInteger * 2^24 e (measuredRandomInteger + 1) * 2^24 .
E podemos fazer isso três vezes seguidas, para X, Y e Z.
E sabemos que entre X e Y, e entre Y e Z, a semente foi atualizada de acordo com newSeed = (oldSeed * 25214903917 + 11) mod 2^48
Devo mencionar que uma opção válida é um loop for que tenta todos os 2 ^ 24 bits inferiores possíveis. Para os programadores que estão lendo isto, espero que isso deixe claro qual é o problema:
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 ;
}
}Isso funcionaria e funciona, mas não é tão rápido nem tão divertido. Então, usamos treliças!
No entanto, sinto que tenho que sair um pouco fora de ordem. A parte da redução da rede entra bem aqui, mas é muito complicada e aposto que teria baixa retenção de leitores e não quero perder você. Então, darei a você aquela solução for-loop (que FUNCIONA) e continuarei para a próxima etapa da exploração. A explicação do método de redução de rede virá logo a seguir :)
O que fazemos com esta semente quando a tivermos?
Primeiro, observe que podemos recuar o LCG. Obviamente, somar onze é reversível, mas multiplicar por esse grande número é reversível? Nosso multiplicador 25214903917 é um número ímpar, o que significa que não é divisível por dois e, portanto, não compartilha nenhum fator com nosso módulo 2 ^ 48 (já que 2 ^ 48 é literalmente apenas um monte de dois). Como é relativamente primo ao módulo, podemos invertê-lo, o que significa encontrar outro número x que satisfaça x * 25214903917 - 1 é divisível por 2^48. Ou em outras palavras, 25214903917 * x mod 2^48 = 1 . Esse número é 246154705703781 . Isso ajuda a inverter a multiplicação porque se tivermos, por exemplo, secret * 25214903917 e quisermos descobrir secret , podemos apenas calcular secret * 25214903917 * 246154705703781 mod 2^48 = secret * 1 mod 2^48 = secret .
Ok, então podemos avançar e retroceder a semente interna de java.util.Random . Para frente é newSeed = (oldSeed * 25214903917 + 11) mod 2^48 e para trás é oldSeed = ((newSeed - 11) * 246154705703781) mod 2^48 . E isso funciona porque esses números 25214903917 e 246154705703781 , quando multiplicados juntos, resultam em 1 quando você usa o mod 2 ^ 48.
Agora, ao retrocedermos, gostaríamos de verificar a cada passo se esta semente poderia significar que uma verificação da Woodland Mansion foi realizada recentemente em algum lugar do mundo (o objetivo da exploração). Como fazemos isso?
O mundo do Minecraft varia de -30 milhões a +30 milhões de blocos. Cada "região da Floresta" (uma área do mundo onde uma única Mansão da Floresta é colocada aleatoriamente, conforme o código mostrado anteriormente) tem 80 por 80 pedaços, ou seja, 1280 por 1280 blocos. Isso é 23.437,5 regiões da floresta, mas para todo o nosso código arredondamos para 23.440 porque é um número redondo e mesmo que seu jogador não possa viajar além de 30 milhões, você carrega pedaços além dele apenas ficando perto dele, e nós apenas não queria ter que se preocupar com tudo isso.
Portanto, -23440 a +23440 nos eixos X e Z. Isso é (23440*2+1)^2 (também conhecido como 2197828161 ) possíveis regiões da floresta, cada uma das quais gera uma "semente de mansão" exclusiva (definida como uma semente que revela que alguém acabou de carregar um pedaço em uma determinada região da floresta). Precisamos ser capazes de verificar se algo é uma semente de mansão. Poderíamos iterar todas as 2,2 bilhões de sementes de mansão para verificar cada uma delas? Seria muito lento. Poderia fazer um HashSet com 2,2 bilhões de entradas? Ocuparia muita RAM mesmo usando o mapa de crônica como fizemos no nocom, e mesmo em C++ usando abseil-cpp ele usava cerca de 50 GB de RAM. E isso sem falar na outra parte: na verdade, queremos saber onde eles estão no mundo (esse é o ponto principal). Portanto, não basta saber que esta é uma semente de mansão, também queremos saber (de forma eficiente) qual região da Floresta a causou.
Lembre-se da função que vai da região da floresta para a semente da mansão (nota: agora combinei algumas constantes desde o código acima para simplificar, esta equação agora é especializada para a semente de 2b2t ):
seed = x * 341873128712 + z * 132897987541 - 4172144997891902323 mod 2^48
(o -4172144997891902323 número vem de -4172144997902289642 + 10387319 , que é a semente mundial 2b2t + o valor mágico usado para semear a região da Floresta (como mostrado anteriormente). Para qualquer outro mundo, você simplesmente colocaria sua própria semente nesta equação .)
Não podemos fazer muito com a coordenada x, pois ela está sendo multiplicada por um número par. Mas qual é esse coeficiente na coordenada z? Parece um número ímpar!!! Vamos usar o mesmo truque de antes para invertê-lo novamente e obteremos 211541297333629 .
Vamos imaginar que temos uma determinada semente. E se pudéssemos apenas iterar por todas as coordenadas X possíveis de -23440 a +23440 e, para cada uma, calcular qual seria a coordenada Z da região da Floresta, SE tivesse esta semente de mansão . Em outras palavras, a equação acima nos dá seed se conhecermos x e z , mas podemos fazer uma equação que nos dê z se conhecermos seed e x ? Resposta: sim. Apenas reorganizamos a equação acima e usamos o fato de que o coeficiente de Z é invertível mod 2 ^ 48, pois é um número ímpar.
A equação é:
z = (seed + 4172144997891902323 - x * 341873128712) * 211541297333629 mod 2^48
Portanto, esta é uma solução muito boa porque, em vez de dois loops aninhados (um para X e outro para Z) que fazem um total de 2,2 bilhões de iterações, podemos ter um único loop for para X que faz apenas 46.881 iterações. Aqui está em 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 ;
} (nota: o estranho << 16 >> 16 está fazendo o mod 2 ^ 48, mas na verdade queremos fazer isso usando tipos assinados para que ainda obtenhamos a resposta correta quando z estiver entre -23440 e 0, esta é uma maneira de estender o sinal do número de 48 bits para 64 bits, preenchendo os 16 bits superiores com o bit de sinal correto para complemento de dois)
Então isso funciona e é razoavelmente rápido... para uma única semente. Mas lembre-se de que estamos recuando o RNG potencialmente em milhares de etapas e executando essa verificação em cada etapa até encontrarmos uma correspondência. Na época, estávamos usando um droplet de merda da DigitalOcean em seu nível mais baixo, e isso estava atrasando tudo e não conseguia acompanhar o tempo real (bots minerando muitos blocos por segundo, cada bloco levando milhares de passos para quebrar, e cada etapa do rng leva 23.440 * 2 + 1 operações para verificar, multiplique-as e você chega a centenas de milhões de operações por segundo, então você vê por que isso teve problemas em um VPS de baixa qualidade, especialmente quando esse VPS também está tentando para executar várias instâncias sem cabeça do Minecraft).
De qualquer forma, mudamos para uma abordagem de tabela de pesquisa e a reescrevemos em Cuda para rodar em minha área de trabalho como um trabalho em lote a cada poucos minutos. Ele pode fazer literalmente milhões por segundo porque cada um dos milhares de núcleos cuda pode trabalhar em sua própria semente em paralelo. A ideia é a seguinte: a chave da tabela de pesquisa são os 32 bits inferiores da semente da mansão e o valor é a coordenada X da região Woodland. Esta tabela de pesquisa funciona sem colisões porque cada semente da mansão tem 32 bits inferiores exclusivos, de alguma forma . Não entendo por que isso é verdade, é fascinante. Você pensaria que não funcionaria. Mas acho que os coeficientes 341873128712 e 132897987541 podem ter sido escolhidos especialmente para fazer este trabalho? Por exemplo, se você tiver 2,2 bilhões de bolinhas de gude e 4,3 bilhões de baldes, e colocar independentemente cada bolinha de gude em um balde aleatório, quais são as chances de cada bolinha de gude receber seu próprio balde? Essencialmente zero. Perto do fim, cada nova bola de gude tem mais de 50% de chance de atingir um balde que já está cheio. No entanto, claramente, estes não são independentemente aleatórios, então de alguma forma funciona. Não ironicamente, se você está lendo isso e entende como isso funciona ou por que esses dois coeficientes específicos fazem isso funcionar, por favor me avise. De qualquer forma, funciona. A tabela de pesquisa tem 2 ^ 32 entradas e cada entrada tem 2 bytes (já que é apenas um número entre -23440 e +23440), portanto, são necessários cerca de 9 gigabytes de VRAM em sua GPU.
A função de verificação da floresta agora se parece com (novamente, este é o código real, mas simplificado, todos os auxiliares e constantes embutidos, etc.):
__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;
}Isso funciona muito bem em lotes gigantes e pode quebrar na ordem de dez milhões de sementes por segundo em um 3090. Acontece que não é grande coisa quando alguns dos threads em um warp terminam mais cedo e não conseguimos realmente fazer isso. é mais rápido que isso. (a razão é que fundamentalmente não podemos saber de antemão quais sementes darão mais/menos passos).
Bem, é isso. Dada a semente, é assim que obtemos a região Woodland no mundo onde ocorreu o carregamento de pedaços mais recente. Em outras palavras, acabamos de saber que a última vez que alguém andou em 2b2t e carregou uma nova área do mundo foi em algum lugar dentro desta região de floresta de 1.280 por 1.280 blocos que acabamos de identificar. (isso é preciso o suficiente para que localizá-los leve apenas alguns minutos de pesquisa)
Na prática, quantas etapas de RNG foram necessárias? Na extremidade inferior, medições confiáveis começam em 4 etapas RNG, tudo abaixo disso é erro de medição/ruído aleatório, que sabemos porque o código da Woodland Mansion chama imediatamente rand.nextInt quatro vezes antes que seja possível medi-lo. Em média, existem cerca de 128.000 passos entre cada semente Woodland, mas na prática, na grande maioria das vezes em 2b2t, encontramos uma semente Woodland dentro de algumas dezenas de passos. Isso se deve aos detalhes do que acontece e em que ordem em um tick do Minecraft. Nossa medição tecnicamente acontece logo no início do tick, pois é onde são processados os pacotes para quebra de blocos. Geralmente, um pedaço foi carregado no histórico muito recente durante o tick anterior. No entanto, às vezes, um evento pode causar várias etapas de RNG entre elas. Acreditamos que este evento sejam explosões, como alguém explodindo um cristal final ao socá-lo, ou possivelmente crânios murchados. Explosões de cristal final também ocorreriam durante o processamento do pacote do pacote de perfuração do jogador, e o número de etapas RNG também se alinha em 1354 etapas (1352 do cálculo do dano do bloco em um cubóide
E nas coordenadas usadas como exemplo resolvido neste diagrama, é isso que o código acima gera:
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>
Observe como ele localiza a região da floresta 123,456 e observe como o "alguém localizado entre" final inclui a coordenada real que inserimos originalmente, que era x=157440 z=583680. Além disso, as medições RNG correspondem ao hexadecimal em vermelho: 0xf61dc9 é igual a 16129481 , 0x1700fb é igual a 1507579 e 0xc50d15 é igual a 12913941 . E para as sementes, 0xed92e70ba4a0 é igual 261215197308064 e 0xf61dc9221ba4 é igual a 270607788940196 .
Você provavelmente pode encontrar patches ou opções de configuração para desabilitar a manipulação de RNG, algo assim funcionará para corrigir Randar e é provavelmente a maneira mais fácil. Se você não consegue encontrar uma maneira fácil de desabilitar a manipulação de RNG, aqui está o código que precisa ser ajustado na classe World :
Versão vulnerável:
public Random setRandomSeed ( int seedX , int seedY , int seedZ ) {
this . rand . setSeed ( seedX * 341873128712L + seedY * 132897987541L + seedZ + this . getWorldInfo (). getSeed ());
return this . rand ;
}Simplesmente altere esta função para retornar um Random diferente a cada vez, se quiser uma proteção perfeita:
Versão corrigida:
public Random setRandomSeed ( int seedX , int seedY , int seedZ ) {
return new Random ( seedX * 341873128712L + seedY * 132897987541L + seedZ + this . getWorldInfo (). getSeed ());
} Isso pode não ter um ótimo desempenho, então, se desejar, você pode introduzir um novo campo, separateRandOnlyForWorldGen , que não é compartilhado com mais nada, por exemplo:
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 ;
}Se você usa PaperMC para 1.12.2 , aqui está um patch que você pode aplicar. Link alternativo.
Esta será uma seção adicional onde abordarei algumas coisas extras que fariam mais sentido explicar do meu ponto de vista, já que além das ideias básicas, desenvolvemos coisas principalmente de forma independente.
A primeira coisa que gostaria de mencionar é o sistema de localização das coordenadas a partir de uma semente. Os Mason usaram uma grande tabela de pesquisa e processamento de GPU; em vez disso, contei com um cache para obter velocidade. Sempre que ocorre um acerto, suas coordenadas e todas as coordenadas dentro de um raio são colocadas em um HashMap. As sementes são processadas em duas passagens. A primeira passagem retrocede o RNG e verifica se a semente está presente no cache ou se foi a mesma semente processada da última vez, o que é considerado diferente. A segunda passagem só acontece se a primeira falha, é muito mais lenta e usa o algoritmo relativamente caro descrito anteriormente. Um efeito colateral agradável desse sistema é que a primeira passagem tem o potencial de "pular" uma localização "válida", mas com menor probabilidade de ser a correta, o que ajuda com falsos positivos.
Aqui está esse código:
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 ;
}
}Outra coisa que gostaria de mencionar é como usei isso no The End. Como mencionado anteriormente, os pedaços no The End afetam o RNG apenas uma vez quando são gerados pela primeira vez. Isso torna as coisas muito mais complicadas, pois, diferentemente do Overworld, um jogador não pode ser encontrado simplesmente carregando um pedaço em sua base.
Em vez disso, existem dois outros cenários principais nos quais devemos confiar:
O primeiro cenário significa essencialmente que ainda podemos usar o método ingênuo de simplesmente contar quantas vezes distintas uma região foi atingida, no entanto, seremos fortemente limitados, uma vez que os acertos podem ser muito raros e podem ser confundidos por alguém simplesmente voando por uma área em algumas vezes distintas o suficiente. O segundo cenário exige que identifiquemos e sigamos essas trilhas.
Então, como exatamente seguimos trilhas? Em teoria, você poderia criar um sistema para identificar e seguir trilhas automaticamente, mas nunca implementei isso e apenas segui manualmente as trilhas visualmente. Ao seguir trilhas, existem algumas ideias que podem ajudar. Por exemplo, várias trilhas que levam ao mesmo lugar provavelmente significam que existe uma base. Saber que determinado golpe ou rastro foi causado por um jogador específico também pode ajudar, falaremos mais sobre isso depois.
Então, como podemos saber qual jogador causou um determinado acerto? No Overworld, podemos simplesmente procurar por golpes “distintos” que acontecem logo após a entrada de um jogador. No entanto, é pouco provável que isso funcione aqui, por isso temos de fazer outra coisa. Na verdade, existe um sistema bacana para isso. É baseado na suposição de que não há muitos jogadores online no The End ao mesmo tempo, e na ideia de que podemos dizer quem são esses jogadores. A ideia é que o número de chamadas RNG por tick esteja, em parte, correlacionado ao número de pedaços atualmente carregados e, portanto, ao número de jogadores nessa dimensão. Observando um aumento ou diminuição repentino no número dessas chamadas logo após um jogador entrar ou sair, respectivamente, podemos identificar os jogadores que estão no Fim. Chamaremos esse sistema de "Rastreador de Ocupação Final" (EOT).
O EOT mantém dois conjuntos. O primeiro rastreia quem achamos que está no The End “agora”. Isso pode causar falta de jogadores, por isso é considerado mais propenso a falsos negativos. O segundo registra quem achamos que estava no The End “no geral”, indo e voltando por um determinado período de tempo. Isso é combinado com os jogadores que estão online no momento e é considerado mais propenso a falsos positivos. Observando esses conjuntos quando ocorre um acerto e fazendo algumas inferências manuais, podemos ter uma ideia aproximada de quem pode ter causado um determinado acerto.
Deve-se notar que o EOT só foi testado no 9b9t e atualmente pode depender de condições que podem não ser verdadeiras em outros servidores, como o 2b2t. Ele pressupõe que o RNG possa ser amostrado em todos os carrapatos sem muita flutuação, o que pode ser mais complicado para 2B2T devido ao limite de velocidade do Block Place. As coisas também podem ser tornadas mais complicadas se houver uma atividade significativamente mais jogadora no final do servidor, o que provavelmente pode ser verdadeiro para o 2B2T, pois é um servidor muito maior.
