By the Dedaub team

The Assignment

A few weeks ago, we were approached with a request to work on a project unlike any we’ve had before.

Cyrus Adkisson is the creator of Etheria, a very early Ethereum app that programmatically generates “tiles” in a finite geometric world. Etheria has a strong claim to being the first NFT project, ever! It was first presented at DEVCON1 and has been around since October 2015 — six years and counting. It is as much Ethereum “history” as can get.

Cyrus heard of us as bytecode and decompilation experts. His request was simple: try to reproduce the 6-yr old deployed bytecode of Etheria from the available sources. This is a goal of no small importance: Etheria tiles can be priced in the six digits and the history of the project can only be strengthened by tying the human-readable source to the long-running binary code.

Easy, right? Just compile with a couple of different versions and settings until the bytecode matches. Heck, etherscan verifies contracts automatically, why would this be hard?

Maybe for the simple fact that Cyrus had been desperately trying for months to get matching bytecode from the sources, to no avail! Christian Reitwiessner, the creator of Solidity and solc, had been offering tips. Yet no straightforward solution had been in sight, after much, much effort.

To see why, consider:

• The version of solc used was likely (but not definitely) 0.1.6. Only one build of that version is readily available in modern tools (Remix) but the actual build used may have been different.
• The exact version of the source is not pinned down with 100% confidence. The source code available was committed a couple of days after the bytecode was deployed.
• Flags and optimization settings were not known.
• The deployed code was produced by “browser-solidity”, the precursor of Remix. Browser-solidity is non-deterministic with respect to (we thought!) blank space and comments. (“Unstable” might be a better term: adding blank space seems to affect the produced bytecode. But we’ll stick with “non-deterministic”, since it’s more descriptive to most.)
• Solc was not deterministic even years later.

If you want to try your hand at this, now is a good time to pause reading. It’s probably safe to say that after a few hours you will be close to convinced that this is simply impossible. Too many unknowns, too much unpredictability, produced code that is tantalizingly close but seemingly never the same as the deployed code!

Dead Ends

Our challenge consisted of finding source code or a compilation setup that would produce compiled code identical to the 6-yr old deployed Etheria bytecode.

The opening team message for the project set the tone: “We are all apprehensive but also excited about this project. It looks like a great mystery, but also a very hard and tedious search that will possibly fail.” Intellectual curiosity soon overtook all involved. People were putting aside their regular weekly assignments, working overtime to try to contribute to “the puzzle”. Some were going down a rabbithole of frantic searches for days — more on that later.

Some encouraging signs emerged at the very first look of the compiled code: when reverse-engineered to high-level code (by the lifter used in contract-library.com) it produced semantically identical Solidity-like output.

But our hopes were squashed upon more careful inspection. The low-level bytecode would always have small but significant differences. Some blocks were re-used (via jumps) in the deployed version but replicated (inlined) in the compiled version. The ordering of blocks would always be a little different. Even matching the bytecode size was a challenge: with manual tries of the (non-deterministic) compilation process, we would almost never get the deployed bytecode size down to the byte, always 2–4 bytes away.

Dead ends started piling up, but every one was narrowing the search space.

• The version of solc used was definitely 0.1.6, based on the timeline of releases. However, the exact build might have made a difference. And, in fact, our compiler was not solc but solc-js, the Javascript wrapper of solc. There are 17 different versions of solc-js v0.1.6. There are even different versions with the exact same filename — e.g., there are 4 different builds (different md5 hashes) all called soljson-v0.1.6–2015–11–03–48ffa08.js. However, no optimizations or compilation gadgets that would explain the difference were introduced in the different builds. We could see no correlation between the compiled code artifacts and the exact build of solc-js, just the occasional non-determinism.
• Different optimization settings made too-drastic a difference. Browser-solidity did not even allow configuring optimization runs, so the only question was whether optimization was on at all, and it very clearly was, based on the deployed bytecode.
• Non-determinism seemed to creep in, even for changes as simple as the filename used.

With so little left to try, frustration started building up. Was this just a random search? And over what? Blank space in the compiled file? Reordering of functions? Small source code changes that yielded equivalent code? Removing dead code from the source?

We tried many of these, ad hoc or systematically and the tiny but persistent differences from the deployed bytecode never went away. Private function reordering looked very promising for a little while. But a full match was nowhere to be seen.

A Breakthrough

Although still several days away from the solution, an important insight arose, after lots of trial and error.

Non-determinism was due to solc-js, the Javacript wrapper, not to individual invocations of the solc executable itself. Solc-js is using emscripten to run the native solc executable inside a Javascript engine. Emscripten back in the day was translating a binary into asm.js (not yet WASM). Something in this pipeline was introducing non-determinism.

But what kind? Since the solc executable was itself deterministic when invoked freshly, the insight was that the apparent non-determinism of solc-js depended on what had been compiled before, and not only on no-op features of the compiled file (e.g., comments, blanks, filename)! In fact, we saw blank space in the compiled file rarely make a difference in the output bytecode. However, earlier compiled files reliably affected the later output.

Christian Reitwiessner later confirmed that non-determinism was due to using native pointers (i.e., machine addresses) as keys in data structures, so that a re-run from scratch was likely to appear deterministic (objects were being allocated to the same positions on an empty address space) whereas a followup compilation depended on earlier actions.

We now had a more reliable lever to apply force to and cause shuffles in the compiled bytecode. And we could get systematic — we would basically be fuzzing the compiler! Our workhorse was the functionality below, which you can try for yourself:

https://dedaub.com/etheria/fuzzer.html

Open the dev console on your browser (F12) and hit “go”. It starts compiling random (unrelated) files before it tries the main file we aim to verify. The (pseudo-)randomization process is controlled by a seed, so that if a match is found it can be reproduced. The seed gets itself updated pseudo-randomly and the process repeats. The output looks like this:

current seed 449777 automate.js:116:11
...
compile 0 NEW soljson-v0.1.6-2015-10-16-d41f8b7.js etheria-1pt2_nov4.sol(1968d2bc81cfd17cd7fd8bfc6cbc4672) 1700cdc5e2c5fbb9f4ca49fe9fae1291 -4 5796 automate.js:72:11
--------- NEW BEST ------------- 5796 1700cdc5e2c5fbb9f4ca49fe9fae1291

Notice the highlighted parts: this compilation output is “new” (i.e., not seen with previous seeds), has a length distance of -4 from the target, and an edit distance of 5796, which is a new best.

If you observe the execution, you can appreciate how much entropy is revealed: new solutions arise with high frequency, even many hours into the execution.

This got our team tremendously excited. Our channel got filled with reports of “new bests”. 0-605 (same size, edit distance 605) gave way to 0-261. We requisitioned our largest server to run tens of parallel headless browser jobs using selenium. The 0–261 record dropped to 0–150. On every improvement we thought “it can’t get any closer!” And with many parallel jobs running for hours, we let the server crunch for the night.

Finale

The next morning found the search no closer to the goal. 0–150 was derived from several different seeds. This is just a single basic block of 5 instructions in the wrong place, which also causes some jump addresses to shift. But still, not a zero.

By the next evening, it was clear that our fuzzing was running out of entropy. A little disheartened, we tried an “entropy booster” of last resort: adding random whitespace to the top and bottom of all compiled programs. (In fact, this improved-entropy version is the one at the earlier link.) Within hours, the “new best” became 0–114! And yet the elusive zero was still to be seen. Could it be that we would never find it?

Nearly 24 hours later, with the server fuzzing non-stop during the weekend, the channel lit up:

GUYS

WE GOT IT

All that was left was cleanup,tightening, and packaging. We soon had a solution that required merely compiling two unrelated files before the final compilation of the Etheria code. We repeated the process with the compiler running in multi-file mode. We found similar seeds for present-day Remix. Everything became streamlined, optimized, easy to reproduce and verify. You can visualize a successful verification (for one compiler setup) here:

https://dedaub.com/etheria/verify.html

We notified Cyrus a couple of hours later. It was great news, delivered on a Saturday, and the joy was palpable. We had a Tuesday advising call with Christian that was quickly repurposed to be a storytelling and victory celebration. Within a few days, etherscan verified the contract bytecode manually, since solc 0.1.6 is too old to be supported in the automated workflow.

Looking back, there are a few remarkable elements in the whole endeavor. The first is the amount of random noise amplified during a non-deterministic compilation. For a very long time, the sequence of “new” unique compiled bytecodes seemed never ending. A search that now seems, clearly, feasible appeared for long to be hopeless. Another interesting observation is how quickly people got wrapped up into a needle-in-a-haystack search. The challenge of a tough riddle does that to you. Or maybe it was some ancient magic from the faraway Etheria land?