Last week, a user on the DF discord server by the name of nightman.eth shared research found about artifact minting randomness being gameable in v0.5. This research got me intrigued in investigating if this was easily exploitable, and whether or not it was exclusive to “contract players” (a smart contract that plays the game) or if normal users could do it through a plugin.
Note from DF Devs: A few weeks ago, @BlaineBublitz and nightman.eth communicated an analysis of a potential weakness in Dark Forest’s pseudo-random generation to us. Blaine spoke with us about his interest in writing a proof-of-concept script to demonstrate how to exploit insecure blockchain randomness to increase a player’s legendary artifact minting rate, and asked us about whether this would still be in the spirit of the game. Given (1) the potential educational value of such a script and associated writeup, (2) the lack of any financial/economic mechanics currently built out around Dark Forest items/assets, and (3) the fact that Dark Forest artifacts stop being mintable on 1/25/21, only a few days after Blaine reached out to us, we decided together that it would not be against the spirit of the game for Blaine to try building out a script and running it for a few hours.
@adietrichs also independently implemented a similar script to exploit artifact mining randomness, to be used in combination with another exploit he found (which we’ll post about soon!). You can find his code here.
A little about artifact rarity
In v0.5, Dark Forest artifact rarity is a combination of the planet’s level and a “bonus”, which is calculated by the randomness generator.
The maximum level of an artifact is 7, with level 6 and 7 being “legendary” rarity—which means that a level 6 or level 7 planet is guaranteed to mint a legendary artifact. However, a level 3 or more planet can generate a legendary by getting a higher bonus.
There’s about a 32% chance of getting 1 bonus point, ~8% chance of getting 2 bonus points, and ~1.5% chance of getting 3 bonus points. The exploit described in this post takes advantage of that bonus calculation to ensure 3 bonus points every time you mint an artifact.
The Exploit
Here is a recap of the research from discord:
findArtifact()callsDarkForestUtils._artifactSeed()with three arguments:planetId,planetEventsCount, andplanetId_artifactSeed()hashes these three arguments to create a seed (confusingly, one parameter is calledblockTimestamp, butblock.timestampis not used in this function. editor’s note: as you’ll see below, this seemed to be a bug - and it was definitely exploitable!)DarkForestUtils._randomArtifactTypeAndLevelBonus()uses this seed to determine the type and rarity of the artifact- A user can increment
planetEventsCountby sending a move to the planet (thus, generating a new seed hash). Each time counts as a “reroll” for what rarity the unfound artifact will become. They can precompute this process as many times as needed to generate a desirable artifact, send the correct number of moves required, then callfindArtifact()
More simply put, the randomness used to generate an artifact’s level/rarity is a combination of the planet’s ID and the total number of moves performed in the Dark Forest universe. As was noted, there is a bug that makes this randomness even more exploitable: the randomness function is supposed to take a block’s timestamp, but accidentally uses the planet ID a second time.
The way a player can exploit this is by combining the ID of any given planet and any exact number of moves in the future. By doing this in a loop, you can determine the exact time to initiate a findArtifactcontract call to generate a legendary artifact!
How Common?
The first thing I did was write a simple JavaScript snippet to see how often one of these exploitable moves appeared.
let { default: web3Utils } = await import('https://cdn.skypack.dev/web3-utils');
let { locationIdToDecStr } = df.getCheckedTypeUtils();
let { toBN } = web3Utils;
function isExploitMove(locationIdInDec, x) {
// https://blog.8bitzen.com/posts/18-03-2019-keccak-abi-encodepacked-with-javascript/
let seed = web3Utils.soliditySha3(
locationIdInDec,
locationIdInDec,
x
);
let artifactSeed = toBN(seed);
let lastByteOfSeed = artifactSeed.mod(toBN(0xFF));
let secondLastByteOfSeed = artifactSeed.sub(lastByteOfSeed).div(toBN(256)).mod(toBN(0xFF));
return (secondLastByteOfSeed < 4);
}
And then I can use it in a loop:
let start = 1312205;
let planet = ui.getSelectedPlanet();
let id = locationIdToDecStr(planet.locationId);
for (let x = start; true; x++) {
if (isExploitMove(id, x)) {
console.log('[LEGENDARY] At Planet event:', x);
console.log('[LEGENDARY] Events from now:', x - start);
break;
}
}
After writing this script, I noticed that exploitable moves were really common—usually a chance every few hundred moves. Being this common, I showed this proof-of-concept to the DF team in case it needed to be patched right away.
Accuracy
Upon showing it to the DF team, it was pointed out that blocks on the blockchain can have multiple moves (usually 1-5) and minting artifacts/moves are randomly distributed throughout it. That limitation, plus network latency, seemed like it would be a showstopper for this exploit outside of “contract players”.
Not one to be deterred, I tried thinking of a way to have more chances at hitting the exploit. Eventually, I came upon the idea of calculating out a “window” of moves where the exploit would be guaranteed, so I edited my loop a little bit:
let start = 1312205;
let planet = ui.getSelectedPlanet();
let id = locationIdToDecStr(planet.locationId);
for (let x = start; true; x++) {
if (isExploitMove(id, x) && isExploitMove(id, x + 1) && isExploitMove(id, x + 2)) {
console.log('[LEGENDARY] At Planet event:', x);
console.log('[LEGENDARY] Events from now:', x - start);
break;
}
}
What you’ll notice above is that I’m looking for the first chance at the exploit where the current move number, the next move number, and the next-next move number all can be exploited. This means that if my minting ends in the block with 1, 2, or 3 moves, I will still be guaranteed a legendary artifact! Even if there are more than that, I still have a pretty high chance of minting one.
The downside of this 3-move window is that they only happen every 20,000+ moves; however, gameplay in the universe has slowed down a lot, so I wanted to try the accuracy of 2-move windows. While the 2-move windows should be more risky, they happen every few hundred or couple thousand moves. In the first 8 attempts using this 2-move window, I minted 7 legendary artifacts.
I bundled up this code into a plugin, which you can find at https://plugins.zkga.me. As I continued cleaning up my plugin, I missed a few more attempts at the exploit, but I’m not sure if it was the bugs in my code or actually missing the window. You can adjust the plugin for the “move window” that you are comfortable attempting.
What now?
As of Monday morning, artifacts can no longer be minted in the Dark Forest v0.5 universe. This was planned all along, and not a product of this exploit; however, I think it is still in the best interest for future education to fix the bug in the contract to use block timestamp. That change would have made it nearly impossible for my JavaScript plugin to exploit the randomness calculation; however, a smart contract would have access to the timestamp at execution time and should still be able to exploit it.
Additionally, nightman.eth offered the following suggestions to the DF team:
Reasonably secure prng is possible. The random number needs to use information that’s unavailable at execution, like a future blockhash one possible solution would be to save the block number when the planet first becomes owned by a player.
Then use the blockhash of that block + 1 as part of the seed generation and require that findArtifact() is called at least one block after the planet becomes owned. That prevents single block gaming as described above.
The downside to this method is that historical blockhash is only available for the last <256 blocks (not sure if this is the same on xDai, but probably).
Maybe there is also some zksnark magic that could help.
For v0.6, there’s already been discussion in discord about implementing a “commit reveal scheme” for minting artifacts. And someone also mentioned there is supposed to be a random number generator in the Eth2 beacon chain.
Bonus!
I’ve mentioned “contract players” a couple times, but I didn’t attempt to create a smart contract to perform this exploit. If my understanding is correct, they wouldn’t need all of my workarounds or move windows because they can just force the transaction to revert if they didn’t get a legendary—whoa! Since it would also work around the block timestamp patch, I think it would be a much more robust solution to implementing the exploit. Additionally, nightman.eth put together a theoretical contract that should be able to perform the exploit, and it would guarantee a legendary!
// SPDX-License-Identifier: UNLICENSED
pragma solidity 0.6.12;
pragma experimental ABIEncoderV2;
import "./DarkForestCore.sol";
import "./DarkForestUtils.sol";
contract ArtifactHack {
using DarkForestUtils for *;
DarkForestCore dfCore = DarkForestCore(0x678ACb78948Be7F354B28DaAb79B1ABD81574c1B);
function parsePlanetInfo(uint256 _planetId)
public
view
returns (
address _owner,
uint256 _population,
uint256 _populationCap,
DarkForestTypes.PlanetResource _planetResource,
uint256 _planetLevel
) {
// deconstruct tuple
(
_owner,,,,
_population,
_populationCap,,
_planetResource,,,,
_planetLevel
)
= dfCore.planets(_planetId);
}
function hasTriedFindingArtifact(uint256 _planetId)
public
view
returns (bool _hasTriedFindingArtifact)
{
// deconstruct tuple
(,,,,,,,,,_hasTriedFindingArtifact,,) = dfCore.planetsExtendedInfo(_planetId);
}
function getPlanetEventsCount()
public
view
returns(uint256 _planetEventsCount)
{
return dfCore.planetEventsCount();
}
function getPlanetSeed(uint256 _planetId, uint256 _eventsCount)
public
pure
returns(uint256 _planetSeed)
{
return uint256(
keccak256(
abi.encodePacked(
_planetId,
_planetId,
_eventsCount
)
)
);
}
function getRandomArtifactLevelBonus(uint256 _artifactSeed)
public
pure
returns(uint256 _bonus)
{
uint256 lastByteOfSeed = _artifactSeed % 0xFF;
uint256 secondLastByteOfSeed = ((_artifactSeed - lastByteOfSeed) / 256) % 0xFF;
uint256 bonus = 0;
if (secondLastByteOfSeed < 4) {
bonus = 3;
} else if (secondLastByteOfSeed < 16) {
bonus = 2;
} else if (secondLastByteOfSeed < 64) {
bonus = 1;
}
return bonus;
}
function movesRequiredForLegendary(
uint256 _planetId,
uint256 _planetLevel,
uint256 _planetEventsCount,
uint256 _max
)
public
pure
returns(uint256 _moves)
{
uint256 bonusRequired;
bool solutionFound;
if (_planetLevel >= 6) {
// level 6 and 7 planets are automatically legendary
solutionFound = true;
return 0;
} else {
// the maximum bonus multiplier is 3, which is added to the planetLevel
bonusRequired = 6 - _planetLevel;
}
for (uint256 i = 0; i < _max + 1; i++) {
uint256 seed = getPlanetSeed(_planetId, _planetEventsCount + i);
uint256 bonus = getRandomArtifactLevelBonus(seed);
if (bonus >= bonusRequired) {
solutionFound = true;
return i;
}
}
require(solutionFound, "no solution found");
}
function findLegendaryArtifact(
uint256 _planetId,
// requires an array of valid possible moves with move proof
uint256[15][] memory _m,
// requires a valid biome proof to call findArtifact()
uint256[10] memory _f
) external {
dfCore.refreshPlanet(_planetId);
(
address owner,
uint256 population,
uint256 populationCap,
DarkForestTypes.PlanetResource planetResource,
uint256 planetLevel
)
= parsePlanetInfo(_planetId);
// sanity checks for valid planet with unfound artifact
require(DarkForestUtils._isPlanetMineable(_planetId, planetLevel),
"no artifact on planet");
require(!hasTriedFindingArtifact(_planetId),
"artifact already found");
require(msg.sender == owner,
"you do not own this planet");
require(planetLevel >= 3,
"level too low for legendary");
require( (population * 100) / populationCap > 95,
"you must have 95% of the max energy");
require(planetResource == DarkForestTypes.PlanetResource(0),
"cannot mint artifact on silver mine");
// get plant events count at execution time
uint256 eventsCount = getPlanetEventsCount();
// get required moves needed to increment planetEventsCount
uint256 movesRequired = movesRequiredForLegendary(_planetId, planetLevel, eventsCount, _m.length);
if (movesRequired >= 0 && movesRequired < _m.length) {
// send the correct number of moves to increment planet event Counts
for (uint256 i = 0; i < movesRequired; i++) {
// reformat the array of moves into the correct fixed-length array arguments
uint256[2] memory aMove =
[_m[i][0], _m[i][1]];
uint256[2][2] memory bMove =
[[_m[i][2], _m[i][3]], [_m[i][4], _m[i][5]]];
uint256[2] memory cMove =
[_m[i][6], _m[i][7]];
uint256[7] memory inputMove =
[_m[i][8], _m[i][9], _m[i][10], _m[i][11], _m[i][12], _m[i][13], _m[i][14]];
// call move()
dfCore.move(aMove, bMove, cMove, inputMove);
}
// reformat the arguments for findArtifact() into fixed-length arrays
uint256[2] memory aFind = [_f[0], _f[1]];
uint256[2][2] memory bFind = [[_f[2], _f[3]], [_f[4], _f[5]]];
uint256[2] memory cFind = [_f[6], _f[7]];
uint256[2] memory inputFind = [_f[8], _f[9]];
// call findArtifact() and generate a legendary
dfCore.findArtifact(aFind, bFind, cFind, inputFind);
}
}
}