Video2NAND – Abusing video codecs for great computational power

Shared Object Video2NAND July 11, 2026 Much has been written about turning NAND gates into computers, yet knowledge of how to build these NAND gates is not as common. You may think that it’s in the realm of transistors and electrical engineering, but we’ll explore a much more exotic substrate: the video codec. Specifically, we’ll talk about the VP8 video codec and how to abuse its prediction mechanisms to simulate combinatorial logic. Our goal is to build up a set of composable “gadgets” which can construct arbitrary logic circuits. .wire { stroke: #000; stroke-width: 1px; fill: none; } .gate { stroke: #000; stroke-width: 1px; fill: none; stroke-linecap: square; } A Tiny Bit About Video Codecs Video codecs are standards which describe a method of encoding a video (a series of images) into some bitstream, and how to decode that bitstream back into the original video. Instead of prescribing exactly how to encode a video, they usually define a general structure and some set of primitives which can be used to encode the video. As such, different video encoder implementations (or even the same encoder with different settings) may encode the same video differently, but all decoders are expected to be able to reconstruct the video regardless. We will not explain the whole inner-workings of VP8, our video codec of choice, and instead focus on a subset relevant to our purposes. Furthermore, the following explanations are not entirely accurate, in an attempt to simplify the prerequisite knowledge to its essence. If you are interested in learning more about video codecs, I’d recommend reading the Theora spec, which is surprisingly readable. You can also read this follow-up post which describes some glossed over details. In a sense, a video is just a series of images. In video codec jargon, these images are called “frames” where each frame is grid of pixels. Frames are generally divided into to two kinds: key-frames and inter-frames. A frame divided into 8x8 blocks of pixels Key-frames are frames which are encoded independently of other frames. All data required to reconstruct the image is contained within the representing frame. The pixel data may be encoded directly into the frame, or predicate using intra-frame prediction. Intra-frame prediction allows the encoder to state that a certain block of the image can be predicted from another nearby block. Since VP8 decodes these blocks row-by-row, from the top-left down to the bottom-right, the intra-frame prediction primitives it offers allow predicting a block using the row above it, the column to the left of it, and the top-left pixel between them. top left top[0] top[1] top[2] top[3] left[0] left[1] left[2] left[3] A block and the pixels it uses for prediction Inter-frames are frames which exploit the fact that subsequent frames don’t change much, and allow predicting blocks of pixels based on previously decoded frames. They offer the same encoding primitives as key-frames, as well as allowing inter-frame prediction: describing a block by referencing a block from a previous frame. We will build our combinatorial circuits purely using key-frames. Partly because the semantics of combinatorial-vs-sequential logic map well to key-frames-vs-inter-frames, and partly because the extra challenge of a limited toolkit is more interesting. Wires and Gates Combinatorial circuits are built up out of inputs, outputs, wires and gates. In our case, instead of electrical current representing True and False, each block in the frame will either be completely white (all pixel values set to 255) or completely black (all pixels values