Emulating dropper RNG with redstone

I built an absolute unit of a redstone machine that emulates droppers. The machine does the same calculation that occurs internally on a minecraft server when a dropper is powered.

  • The lime green component is for user input. Here, the user enters a 48-bit number (the dropper RNG seed) in base 8 using an item frame rotation interface.
  • The yellow component is a 48-bit multiply-add unit. In other words, it calculates a*b+c for any a,b,c. It can do 5 of these operations per second with a 34-second delay to see the output for a corresponding input.
  • Orange is a ROM storing 512 precomputed 48-bit numbers (1.6 bits per block). It reads out 10 numbers per second.
  • Black is the output display. The right display is the random output from 256 droppers filled with 8 items each and set to detect selection of the 8th slot. The left display is the output from the machine.

I use high signal strength (base 24) for size and speed reasons. That means I used command blocks, not for executing commands, but for the high signal strength from their SuccessCount value.

Using a seed cracker for droppers, one can obtain the internal seed of the RNG instance used by droppers on the server. By entering the cracked seed into the machine’s input (lime green), the machine is able to determine all future dropper output globally on a minecraft server. The linked cracker takes a few seconds to run on an IRL computer, so doing the cracking step in redstone is probably out of reach. The cracker makes use of a lattice reduction algorithm and branch and bound in order to do the cracking on a CPU in reasonable time. The author of the cracker is Matthew Bolan.

You can use this dropper emulator/prediction for:

  • wireless redstone, including between dimensions since the Random instance is used globally in the game’s code.
  • replacing your redstone computer’s RNG that uses droppers with an equivalent one that does not use droppers.
  • detecting when a dropper is powered on the server.
  • using a super complicated RNG built in a super complicated video game running on a super complicated computer for dungeons and dragons dice rolling or selecting moves when you’re playing rock-paper-scissors or anything else you need random numbers for.

The remainder of this post includes some finer details.

The random number source used by droppers is an instance of Java’s java.util.Random class which is a linear congruential generator (LCG). An LCG has a state called a seed which is updated by the formula
seed = (multiplier * seed + increment) % modulus each time a new random number is needed. java.util.Random will then return some number of the upper bits of the new seed to be used to determine the next random number. multiplier, increment, and modulus are hard-coded constants. The modulus is 2^48, so we just need to do arithmetic in binary with results truncated to 48 bits.

I will call an update of the seed by the above formula a step.

The composition of a linear function and a linear function is another linear function, so it turns out that for any n, there exists m_n, i_n (with nice formulas to compute these) such that the seed value after n steps is given by (m_n * seed + i_n) % modulus. In other words, an LCG advanced by n steps instead of 1 is just another LCG. If we know n in advance, we can precompute m_n and i_n so that if we know the value of seed at some point, we need to do only one multiply-add to calculate what the seed will be after n steps.

Now, the way droppers use java.util.Random is weird, but the long story short is there are n steps of the LCG when a dropper with n nonempty slots is powered. Additionally, if the number of nonempty slots is 2^k, then the last slot is selected if and only if the most significant k bits of the seed are all 0. Our droppers have 8 nonempty slots and we’re firing 256 of them. Putting it all together, the ROM (orange) stores precomputed numbers m_8, i_8, m_16, i_16, … , m_2048, i_2048 which are fed into the multiply-add unit (yellow) along with the seed, and at the output end, the corresponding lamp on the display goes on if the result is less than 2^45.

Clarifications to some white lies:

The observant will have noticed that the droppers mentioned have 8 nonempty slots and are set to detect selection of the last slot, but typically when you’re using droppers for a random source of bits, you use droppers with 2 nonempty slots. Adapting the machine to predict these droppers requires trivial changes. You need a different set of precomputed numbers and you’re detecting if the result is less than 2^47 instead. 8 was used to make this demonstration of the machine function also as a display for Matthew’s cracker.

The machine is not set up to determine whether a slot is selected when its slot number (1-indexed) is not a power of 2.

Lastly, ORE runs each ‘world’ in a separate server instance, so you can’t use this for wireless redstone between worlds on ORE.

Appendix

public int getRandomSlot() {
    int i = -1;
    int j = 1;

    for (int k = 0; k < this.items.size(); ++k) {
        if (!((ItemStack) this.items.get(k)).isEmpty()
                && TileEntityDispenser.RANDOM.nextInt(j++) == 0) {
            i = k;
        }
    }

    return i;
}
public int nextInt(int bound) {
    if (bound <= 0)
        throw new IllegalArgumentException(BAD_BOUND);
    int r = next(31);
    int m = bound - 1;
    if ((bound & m) == 0)  // i.e., bound is a power of 2
        r = (int)((bound * (long)r) >> 31);
    else { // reject over-represented candidates
        for (int u = r;
             u - (r = u % bound) + m < 0;
             u = next(31))
            ;
    }
    return r;
}
protected int next(int bits) {
    long oldseed, nextseed;
    AtomicLong seed = this.seed;
    do {
        oldseed = seed.get();
        nextseed = (oldseed * multiplier + addend) & mask;
    } while (!seed.compareAndSet(oldseed, nextseed));
    return (int)(nextseed >>> (48 - bits));
}
1 Like

Cool theoretically, but unfortunately the practical uses are mitigated.

  • we have better ways to do wireless redstone related to item IDs
  • there are genuine uses for avoiding dropper rng in redstone computers, mostly that mchprs does not support droppers, but purpose-built systems are generally going to be much simpler and faster for comparably strong RNG
  • I’m pretty sure that the aforementioned wireless redstone system is somewhat capable of detecting droppers firing if configured properly
  • LCGs are frankly fairly weak as far as RNG goes. I’m sure you can get better quality with a pure redstone implementation. simpler CSPRNGs even might not be off the table

Test :waffle:

This is very cool