Reading a chip off its layout

The problem

Uncharted

The puzzle is the file puzzle.gds, which is the physical layout of a chip. You get a short recording of some inputs going in and some outputs coming out. There is a pin called success that seems important 😁. The task is to find the inputs that make success go high. Looking at the structure of the chip, it seems likely that there will be some sort of string output on success, and that this string is the solution.

The layout has nothing written on it. It is a heap of polygons on numbered layers, with the wiring on the metal layers and the transistors underneath. Somewhere in there sits a circuit that computes something, and I had to work out what.

Day one

Practising on the warmup

The repo ships a small example so you can build your tools against a known answer. The toy design is two shift registers feeding an adder, the adder feeding a comparator, with success coming on when the two numbers add to 496. It comes with the original Verilog, the synthesized netlist, the placed layout, and the final GDS.

I spent the first stretch here, especially because I wanted to try an idea - write a JAX based simulator allowing me to try many combinations of inputs in parallel. If my extractor could not rebuild the warmup netlist from the warmup GDS, it stood no chance on the real thing. Since I was planning to build an entirely new tool, this seemed like a really important proving ground.

Extraction

Turning polygons into a netlist

A GDS file is pure geometry. There are rectangles of metal, little squares where one metal layer connects to the layer above it, and the transistor shapes below. The logic hides in which shapes touch which other shapes.

So the extraction runs like this. Merge every piece of metal that overlaps into a single conductor. Walk the vias and join the conductor under each one to the conductor above it. That gives you the electrically connected nets. Then match each standard cell against the published SkyWater library, whose shapes and pin positions are all documented, so you never have to read a transistor. Once you know which cell is which and which net each pin sits on, you have the netlist back.

I ran this on the warmup and compared it to the netlist Jane Street shipped alongside. Same nets, same connections, every wire. The pipeline held.

Simulation

Running the netlist

I wrote the cycle simulator in JAX, hand coding the function for every cell type. Every gate becomes a small lookup table and every flip-flop updates on the clock edge. To test it I replayed the sample recording that came with the puzzle, feeding the same inputs and checking the outputs. I also implemented tests against the SkyWater library. I ended up really happy with the simulator; I feel like it could be a useful standalone library.

The real chip

Looking at what came out

I pointed the same extractor at puzzle.gds. Larger, same idea. Then I drew a floorplan and coloured each cell by what it is. You can pick out the blocks by eye: tight clumps of flip-flops that behave like registers, wide bands of logic between them, and a heavy lump of gates off to the right.

I also had the simulator dump the state of every flip-flop on every cycle and drew that as a raster, with time going left to right and one row per flip-flop. Some rows blink fast and some barely move. The repeated diagonal streaks are data marching through a shift register. The band near the top that only wakes up late is the part that drives the output.

The machine

What it actually does

Piecing this together took a while. The chip reads a serial input, one bit per clock, while an enable line stays high. Inside, a counter runs with a period of eleven, which chops the input stream into frames of eleven ticks. Each frame has to carry exactly two pulses. Feed any other number and a hidden flip-flop latches, and after that the output pins spell TRY AGAIN no matter what you do.

Eleven of these frames go by. If the pulse positions across all eleven satisfy an internal comparator, the success pin latches high. The design is a combination lock. One frame is one symbol, a symbol is a choice of two positions out of eleven, and there are eleven symbols to get right.

The wall

Search does not get there

My first instinct was to search. I have a fast simulator, so I can throw millions of candidate inputs at it and keep whichever ones nudge the internal state toward what success wants. I tried a beam search. Then a local search. Then a small genetic loop that mutated the frame symbols.

They all stopped in the same place, with fifty-five of the fifty-six internal conditions met and the last one refusing to move without wrecking ten others. The comparator is a hash. It runs the input through enough nonlinear logic that flipping one input bit scrambles the internal state completely, so being one bit from the answer puts you nowhere near it in the state the search can see. There was no slope to climb, and the search sat down.

The turn

Solving it instead of searching

I set the whole thing up as one logic problem. Take the netlist and unroll it in time: a hundred and thirty copies of the circuit, one per clock, wired so each flip-flop feeds the next cycle. Every gate turns into a boolean clause. Add one clause that says the success flip-flop goes high somewhere in those cycles. Hand the pile to a SAT solver.

A few seconds later it handed back an input that works. I banned that input and asked for another. It reported that none exists. A single input drives success high, and the solver had it.

The answer

Reading it off the pins

The puzzle wants a string, and the string comes out of the output pins while success is high. I fed the winning input, read the pins, and got fifteen bytes of garbage.

The problem was when I read them. In the sample recording, the output only plays after the input window closes and the enable line drops low. I had been holding enable high through the readout, so I was reading the pins mid-computation. I matched the timing from the sample instead: feed the input, drop enable, then read. The pins spelled it out, one character per clock.