Since its inception, the field of computer science has sought tools for better understanding the capabilities of computer systems. From the early works of Ada Lovelace to the mathematical frameworks of Alanzo Church and Alan Turing, the early pioneers looked for ways to characterize these exciting new machines.
The problem remained open or decades, frustrating theorists and practitioners alike. Fortunately, all of that changed with id Software’s release of DOOM for DOS in 1993, which not only launched the “first person shooter” genre of video games, but also provided the first relevant, practical, and understandable measure of computer performance.
Therefore it should come as no surprise that modern experts typically split computer systems into two categories: those that can run DOOM, and those that can’t.
A breakthrough of Gaussian proportions
Today we are pleased to announce that RISC Zero’s zkVM has joined the pantheon of systems that can run DOOM. You can checkout the source code here.
Here’s how it works: the user runs our DOOM port in the zkVM and provides a “demo” file (a transcript of their game inputs) as input. DOOM then replays the demo file, and as it does so, renders the in-game graphics to the zkVM’s journal (a cryptographically signed and verifiable output log) which can then be displayed onscreen. The GIF shown above was generated by capturing these frames.
Because DOOM is running in the zkVM, we obtain a ZK proof that the frames contained in the journal really did come from DOOM. And because it’s a zero knowledge proof, no information about the demo file gets revealed (beyond that which can be seen onscreen).
A fun, easy project
The original DOOM was written for DOS, an archaic operating system for IBM PC-compatible systems. So how did we get it to run in the zkVM?
DOOM* is open source, so one might start by grabbing the code and compiling it for RISC-V (the processor core used by the zkVM). Unfortunately, this approach doesn’t quite work: the source compiles just fine, but at runtime things fall apart. So what goes wrong?
The problem is that DOOM is written to run on a conventional computer running a conventional operating system. And while it’s possible to boot a conventional operating system in ZK, we felt that doing so was overkill for this project. After all, no one really cares about DOOM’s behavior as a process running within an operating system; what people really care about is the game logic itself.
And fortunately for us, this is exactly what’s provided by the PureDOOM project. PureDOOM can be thought of as DOOM sans operating system integration. It works by replacing the libc dependencies with a small, easy-to-support abstraction layer. To run in the zkVM, all we had to do was provide an implementation of those abstractions.
Because PureDOOM is written in C, we started by wrapping the C interface with Rust bindings using Bindgen, a tool that generates Rust FFI bindings. At compile time, we use clang to build the C code since it can cross-compile to riscv32im (the CPU core used by zkVM). This involved applying some patches to PureDOOM to make it compatible with RISC-V. The patches were minor and concerned idiosyncrasies of the C language, like whether char is signed or unsigned by default; see puredoom-rs/build.rs in the zkDOOM source code for more details.
Once we were able to build our code we moved on to implementing the system interface for PureDOOM. The majority of the interface was pretty easy to implement in Rust, simply by wiring up to the zkVM’s corresponding interface (such as print, exit etc), with two exceptions: filesystem and time.
For the filesystem, we implemented a basic HashMap backed, in-memory mock. This allows us to include the WAD file inside the guest Image itself which buys us two nice features:
We don’t have to read it in via inputs, which saves us some cycles of execution.
Embedding the WAD means the guest’s ImageId is directly tied to a specific WAD, which is useful for competitive play.
The final challenge was the gettime() interface. In the zkVM there is no concept of time by default (in general, there is no way to cryptographically prove what time it is). To work around this, we chose to emulate a timer that will allows the game logic to work as expected. We took the approach of incrementing a global counter each time the doom_update() call runs, and in order to get a visually clear frame output for the visualizations we picked 100000 usecs per update. This simple hack seems to do the job.
All in, the project took about a day, including breaks to play with the dog.
Performance
Of course, an exciting ZK project wouldn’t be complete without some exciting performance. We begin by looking at the amount of compute (measured in clock cycles) required to play DOOM:
Cycles for init: 50,560,806
Cycles per game tick (no rendering): 37,519
Cycles per game tick (rendering): 2,438,613
Total cycles for the included demo (no rendering): 119,537,664
Total cycles for the included demo (rendering): 7,809,794,048
Unsurprisingly, DOOM doesn’t require much compute. Amusingly, when rendering is enabled, the workload seems comparable to the compute needed to build an Ethereum block — something we’ve been doing in the zkVM for a while now!
Now that we have a sense of the scale, let’s turn to the work required to generate a proof. For this, we took advantage of Bonsai, which gave us access to 250 g4dn.xlarge instances running in AWS.
With rendering
Without rendering
Proof time
33 minutes 8 seconds
1 minute 44 seconds
Segments
7410
114
Game ticks
3186
3186
Effective clockspeed
3.7 MHz
1 MHz
Game ticks per second
1.6 ticks/sec
30.4 ticks/sec
We ran two tests: one with rendering enabled, and one without.
Based on these data we can make a few observations:
When rendering is disabled, the proof can be completed fairly quickly. Even though the zkVM is effectively running at 1 MHz, the game engine is still able to perform 30 game ticks per second — nearly as fast as DOOM’s original 35 ticks per second.
When rendering is enabled, the workload increases by a factor of 65, but the proving time increases only by a factor of 19. This is an elegant example of the power of parallel proving: rendering requires more work to prove, but the work can be done in parallel, which means the time required to complete the work scales favorably. This is reflected by the effective clockspeed, which is much higher for the rendering test than the non-rendering test.
Speedrunning with ZK
The ability to run popular games in ZK creates new opportunities for speedrunning: tool assisted speedruns with secrets, or TASS for short*.*
As with other tool-assisted categories, players are allowed to use tools to craft their demo files; but unlike other categories, players are not required to disclose the contents of those demo files. Instead, records are verified by submitting a ZK proof that the record was indeed attained. Because the records are verified using ZK proofs, the leaderboard could be managed by a smart contract, thereby eliminating the need for a committee of human referees.
Our work stops short of that vision, but perhaps some enterprising hacker will see fit to make it happen …
What this means for the world
The ability to run DOOM in a zkVM is a widely recognized problem of tremendous significance. When we started RISC Zero, we dared to dream that it would one day be possible. Looking back, this goal required several years of ZK R&D and about 1 day of DOOM coding.
We saw it with Zeth and we’re seeing it again with DOOM: if you have big ZK goals, check out the RISC Zero zkVM and see what it can do for you.
