Reverse engineering
an ASIC.

Approach, briefly

I recovered the netlist directly from the GDS's raw file by polygon merging with union find; no cell names exist other than what a standard-cell library provides. Used python to build a gate-level simulator. Validated the pipeline on a known warm-up circuit before using it on the real chip, faced bugs that ate a lot of time.

After building the gate level simulator; I tried forcing success to high directly (didn't work; the output depends on the real input data, not just the flag), then decoded the 8-bit output stream as ASCII and found the chip output changes based on the answer (TRY AGAIN, EMPTY SKY, BIG BANG, TWO"NOT TOUCH). Guessing doesn't seem to find a 121-bit answer by hand, so switched to Z3 solver, unrolling the chip's clocked behavior symbolically and asking it directly to find a input that makes the success high; then I used the sequence given to me by the solver which is how (* TWO STARS *) got found for the first time.

Still not knowing what that 121-bit input actually mean, I went back and analyzed the whole circuit carefully; the internal counters, how bits get routed and latched, all the way to the success itself; rebuilt a few of the more interesting pieces as real working circuits , just to watch them run; You can see them here: CircuitVerse ; before finally hunting for the Easter eggs they mentioned, I found few of these easeter eggs before solving the circuit and few after solving the circuit. Found three which I think are real and one which I think is not: The letters JSC the short form of "Jane Street Capital" visible from the shapes of 3 extracted regions of the puzzle, Morse code buried in negative-Y coordinate far from the actual die area placement, that spells PER ARENAM AD ASTRA, and a leap second timestamp in the VCD file. A strong fourth; the word "EGG" in a png file's raw bytes; turned out almost certainly coincidental; no characters around the area make sense to me other than seeing the EGG there.

That answer (* TWO STARS *) made sense once found the chip is checking an 11×11 Star Battle puzzle's solution, found from the clues hidden in the ROM. Extracting the region map; the one part of the puzzle that was never asked directly; was recovered in two ways: once by sending selected pairs of inputs (fixed a reference and moving the pair) through the chip and watching which flops react, filtered down using a few geometrical constraints, and other by symbolically tracing which grid cells each internal flop depends on; and both methods agreed on the regions; cell for cell.

Now this is going to be a loooooong read;

Grab a Coffee!

How I ended up here

A bit of context first, because that is why I actually wanted to complete it this time. A few months before this, Jane Street ran the Advent of FPGA challenge, which is a set of problems to actually implement on an FPGA. I found it late, didn't have enough time to solve everything, and missed the submission deadline.

One thing I did that time which is good: I subscribed to Jane Street's blog right after missing that deadline, so I will know about the next one in time if there is any. Which is exactly why I ended up seeing this puzzle the same day they released, and got the email.

The puzzle

You know about this already, probably; but just in case you don't: Jane Street published a puzzle called "Can You Reverse Engineer an ASIC?". They designed a small chip, ran it through a physical-design flow, and gave only what you actually need to manufacture it -- a puzzle.gds file (the raw physical layout), a image of the layout with few lables, and a VCD waveform file of somebody entering a wrong answer. Also, they mentioned that there are a few Easter eggs hidden, including in the places that you don't need to look at to solve the actual puzzle.

Along with the real puzzle, they also gave a small warm-up: an 8-bit adder whose output is true when A + B == 496, gave every stage intermediate files of the flow; the original Verilog source, the synthesized netlist, the placed-and-routed layout, and the final GDS. The idea is: build some tool and test it on the warm-up puzzle first, for which you already know the right answer, before trying it on the real puzzle.

The real chip have six pins: clk, rst_n, enable as controls, a single-bit I which is a serial input, an 8-bit O[7:0] output bus, and a success flag. Send something and make the success go high, this is the target.

Extracting the netlist from gds file

A GDS file is just geometry; lots of rectangles on a few numbered layers, arranged in a hierarchy of cell placements. So the first real task is recreating an actual netlist from it (which pin connects to which pin) entirely from the raw file.

One thing that made this solvable in first place is: the GDS had the standard-cell library names as instance references (sky130_fd_sc_hd__a21bo_2, sky130_fd_sc_hd__and2_2, and so on). If they had give us only the layout, recognizing a gate from raw transistor layout is the part which would have taken me a year to figure out :just kidding but its true, and they gave us this; every instance is a known, pre-characterized SkyWater cell, and each one's library definition carries text labels naming its pins. So the whole now the problem is just one question: which pins are wired together?

1. Flatten the GDS's hierarchy into relative coordinate with a reference point.
2. Convert every path into a polygon; GDS stores shapes like this too.
3. Merge touching/overlapping polygons on the SAME metal layer into one net.
4. For every via there on in the gds, merge the shapes below and above it.
5. This results in a netlist.
6. Then, we can simulate the netlist, and see what it does, by pulling the actual definations from the library we know what each cell does.

Same-layer overlap = connected. Different layers = if via connect them, it means they are connected.

Built with gdstk to read/flatten the GDS and shapely and then actually merge the geometry into nets. For gate semantics, I referred to the real functional model for every cell type straight from SkyWater's open-source library, because this is the only way to be sure of what a cell does.

Bug Bug Bug . . .

This is the part the single biggest chunk of time lost on this whole puzzle without a progress. It happened before I even touch the real puzzle.

I was taking AI's help writing the actual extraction code; describing what I wanted, getting Python back, running it. Ran it against the warm-up, and something was clearly wrong; not everything, but enough that I can tell it wasn't right.

Sat with the code later that day, slowly working through it line by line, before it clicked: rotation units. The raw GDS file format itself stores rotation in degrees; that's just how GDSII defines it. But gdstk, the library actually reading the file, converts that value to radians internally before ever handing it to me. So by the time my own code read cell's rotation, it was already in radians; but I didn't know that first, and ran it through one more degrees-to-radians conversion on that. Every rotated pin's computed position must be wrong, which doesn't crash anything; but it silently put the cells in the wrong places depending on whether the rotation is involved. I had spent time trusting the code that looked completely reasonable, because it was reasonable; it just made one very simple, but very wrong assumption about the units which the library is giving us the numbers in.

Validating this on the warm-up and going to real puzzzle

Once that was fixed, the warm-up adder simulated correctly end to end. Fed it two 8-bit values, watched the success go high when they sum up to 496. This woked; now I can move to the real puzzle.

So, I moved to the actual puzzle. Extracted the same way: gates and connectivity. And then the obvious question in mind: okay, I have a netlist. What does it do? What's the input, what's the output, what is this circuit for?

The puzzle's page had one useful line there:

"There is one section of the design that is used to generate the output but does not affect the success output. You can safely ignore it for the initial reverse-engineering steps."

Which felt like the goal is making success go high, and the string comes as the output from the circuit, simple!.

Seeing the waveform file, and a hint

Before touching the real input search, I looked at the example trace they gave; example_inputs.vcd, a dump file of somebody entering wrong input. Its version string said, verbatim: "Leave no stone unturned! But for this file, consider looking at it in a waveform viewer instead." So I did.

Obviously success never goes high in it; They won't reveal the correct answer in example traces. But watching two back-to-back attempts in the trace made something click: the circuit takes 120+ clock cycles after the first input bit before it produces its output. That's a big number already in my mind 2 power 120 possible inputs?, and cycle count is something that tells us something about the sequence length; I didn't know how yet.

Forcing the success to high

First idea: what if I just force success high directly, without looking for what the actual input needed, and read whatever comes out the output pins?

Didn't work; the output generator clearly also depends on the actual input data, not just on the success flag as a trigger. Forcing the flag with the wrong data, and you just get the same kind of stream you get from any other wrong attempt.

Okay, then: what does this 8-bit output stream even mean? It comes out in parallel, 8 bits at a time.

Writing down the raw values made no sense at first; looked like random bits. Then, they mentioned about the string in write-up yeah: they are ASCII. And once I did:

TRY AGAIN

The guessing phase

Once I it outputs the messages in ASCII, the obvious next move was trying the obvious inputs.

• All zeros → EMPTY SKY
• All ones → BIG BANG
• Alternating patterns (0101..., 1010...) → TRY AGAIN
• Random bit flips in an otherwise-zero sequence → TRY AGAIN

Then something really confusing: I tried all-zeros, then all-zeroes except a single 1 at a random positions. EMPTY SKY... then TRY AGAIN... and then, right at the very last bit position when made it high, EMPTY SKY again.

I still don't know the actual input sequence length required, other that what i inferred from the cycle count in VCD file

Same when flipping just the last bit of an all-ones sequence; still BIG BANG, no matter what that final bit was.

That's when I started thinking about a number: 122 total cycles, but if the very last one genuinely doesn't matter... maybe the circuit only actually cares about 121 of them. And 121 is a perfect square; 11×11.

I kept trying structured guesses anyway; walking a single 1 bit one position at a time, various prefixes; TRY AGAIN, every time.

But forcing and guessing clearly wasn't giving me what I want; the search space is very large, and nothing when used the random bits was converging.

At this point the only real way i think exist was using some equation solver; specifically Z3 which I used. Instead of trying guesses, we can unroll the chip's behavior symbolically over a number of cycles, treat every input bit as a variable, and then ask the solver directly; does any combination of values to these variables make success go high? If it returns true, it gives us back the exact bits. If it says no, that can be a proof that no such input exists at that length; though I dont know how these solvers work, not just "I didn't happen to find one."

Tried it against the warm-up first; gave back correct, verifiable (A, B) pairs whose sum results in 496. Then used the same solver on the real puzzle. Output is a sequence of bits; 122 of them cuz I unrolled for 122 cycles by seeing the example VCD; and feeding that sequence in gave:

(* TWO STARS *)

Yeah; it should to be.

Wait. What is (* ... *)?

and then i recalled it: from trying to solve Advent of FPGA, going for bonus points by using Hardcaml. That's exactly the Hardcaml's (and OCaml's) comment syntax: (* like this *). Jane Street builds basically everything in OCaml, so it being written different style means it has to be the answer.

But then, what does this input that i got represent? No pattern in it. Tried splitting it into bytes for ASCII; nothing readable. Tried laying it out as two rows of 61; still nothing. I didn't know what I was looking at yet.

Exploring the circuit

I had the answer; (* TWO STARS *), found using the symbolic solver; but no idea why it worked, or what the input sequence actually meant. So I went looking for the one pin I actually care about: success itself. Traced its own gate directly and found a single a32o_2 cell, reading its own current output back as one of its own inputs; it is more like a sticky latch, once it is high it's high till cleared, but this gate isnt that exactly but close!

One inputs of that gate is fed by an AND-tree, and the AND-tree is fed by some other logic further back. I tried following it backward, gate by gate.

Tracing back to input port from the success is harder than expected. So I flipped the approach: instead of tracing from the answer back to the start, I'd start from the input pin and watch what happens as bits actually move through design.

The flops that are doing the same; everytime I ran

I started with sending sequences of 1's and 0's, and watching the internal flops, there are total 92 flops in the design, and what changes there in each cycle. I ran this almost 7-8 times then looking the bits then, a few of them caught my attention; not because of what they are computing, but because they looked identical no matter what sequence I fed in. Tried all-zeros, alternating, different patterns, even the winning sequence didn't change them; same flops, same exact thing happeneing, every time.

Checked this happening in multiple runs, not just one run: out of all 92 flops in the design, exactly 10 are identical and doesn't depend on the input. 4 of them repeat with a period of exactly 11, and I read them together, thought its some sequence generator 4 more of the remaining 6, changed every 11 cycles and bacame zero at the end, idk why, but they change together, must be another seuqnece generator; now the last two, one of them goes high only at the 121st clock cycle (0-indexed), must be the last-bit flag, so the required sequence length is 121, not 122; the other one I don't know yet. Let's call the first one counter type 1. I found I am incorrect here a bit later, not right now.

So, there exist a counter that resets every 11 cycles and another reset at 121 cycles, I am almost certain for a giveb bit-index they are in same stateif either index%11 is equal or index/11 is equal.

cycle  1: 0010 -> 4 (LSB is starting index)
cycle  2: 0001 -> 8 
cycle  3: 0011 -> 12
cycle  4: 1000 -> 1
cycle  5: 1010 -> 5
cycle  6: 1001 -> 9
cycle  7: 1011 -> 13
cycle  8: 0100 -> 2
cycle  9: 0110 -> 6
cycle 10: 0101 -> 10
cycle 11: 0000 -> 0   (back to the reset state; the loop closes here)

Built this one out afterward as a real circuit, using the same gates I found in the gds file, to watch it happen with my own eyes:

Nice, so something must be happening every 11 cycles. And this is resetting every 11 cycles. Didn't observe it as a mod-11 counter, but something to relate with the number 11, at least.

I thought it's not a plain counter - was wrong

Seeing it I thought it's not a clean 0,1,2,...,10 counter; the numbers (states) are different. Looked at the actual gates behind it: only 11 gates total for all four bits are interdependent, now I am sure they are doing something together. A textbook mod-11 counter; a plain binary incrementer, a comparator for the value 10, a mux to force the reset; needs closer to 19 (this is the number I got when I used my code).

wire [3:0] count;
wire is_ten = (count == 4'd10);

always @(posedge clk)
  if (is_ten)
    count <= 4'd0;
  else
    count <= count + 1;

wire g1 = !ctrl & 1'bx;
wire g2 = !c & !a & b & d;
wire g3 = ~(c ^ g1);
wire g4 = !((c & g1) | d);
...
always @(posedge clk) begin
  a <= g_a; b <= g_b;
  c <= g_c; d <= g_d;
end

A normal 11-cycle counter, looks like the left side; an adder with a reset condition. This doesn't. My first thought was that someone had hand-picked this exact scrambled sequence to save a few gates. Thinking about it more, nobody sits down and hand-derives an 11-state scramble to save 8 gates (maybe they do this at the JS, for them smaller and faster is better). This is type of thing we do; writing a plain case statement for it and let the synthesis tool implement however it wants to optimize the implementation. This is intentional, maybe; just might not be intentional by a person.

There's a second one of these, running slower; changing once every 11 cycles instead of every cycle:

distinct values visited, in order: 0, 4, 8, 12, 2, 6, 10, 14, 1, 5, 9, (back to 0)

What are these actually for?

Before getting to that, I found that the thing I mentioned earlier was wrong. I thought about 2 things:

First, if this is a normal increment-and-compare mod-11 counter, the states should just go 0 to 10, in order. Maybe a tool optimized something about it, but it is not supposed changed the counting behaviour itself.

Second, if this is a case statement given to the tool, with the tool free to pick whichever 11 state values it likes; how it even land on this specific sequence? Doing this manually felt like over-engineering for 8 gates. Thought it is like some well-known thing like the grey-code optimized for sequence

Looked at the numbers in binary,and noticed; one of them flips every 1 cycle. Another flips every 2 cycles. Another every 4. Another flipped at 9th cycle, but then reset before 16th cycle.

Then I re-read the sequence I have in the correct order:

cycle 1: old(abcd)=0010 -> 4    |   re-read(badc)=0001 -> 1
cycle 2: old(abcd)=0001 -> 8    |   re-read(badc)=0010 -> 2
cycle 3: old(abcd)=0011 -> 12   |   re-read(badc)=0011 -> 3
cycle 4: old(abcd)=1000 -> 1    |   re-read(badc)=0100 -> 4
... similarly for 5, 6, 7, 8, 9, 10, then back to 0

This also answers the first point there's no separate comparator type of thing near it; like is_equal_to_10. Which felt like it should be like the second thought; a case statement, left for the tool to turn into whatever gates it wanted, which creates an FSM.

Going forward from both counters to see where the output goes; some decoding logic; the bits arriving at the same state of the fast counter get routed to the same logic, every time. Confirmed this by seeing a few of the flops post elimination. So when the bits are sent, they go to the same place; when the counters are in same state, confirmed this by sending a lot of sequences. Different sequences when sent, for each counter1 state there are 2 tihings happening: whenever there is a bit in the column (index%11) one of the flop toggles, the other observation is whenever there is 2nd bit in the same counter's state the other flop goes high and never back to zero again till reset. Here, the first flop's input is getting fed into the second flop's input, so they are working together.

They are keeping track if they've seen at least two incoming bits at their own specific states; not raw counters, but sticky flops

Sent 0, 1, 2, and 3 . . . stars into the same column and watched both bits directly. First one goes high on the first high bit; the second goes high on next high bit, and next bit both stays high, so its counting whther the column have 0 or 1 or 2 or >2 bits.

Flops and routing together means something

Bits landing on the same state of the fast counter goes into the same flops; So, it's clear the same index % 11 is a column(when arranged as 11x11).

Then looked for the equivalent for the slow (type-2) counter; the "every consecutive block of 11" grouping, which is a row (when arranged as 11x11), didn't find anything. To check this properly, I paired three different bits as high in the same row; gave three different and non-overlapping flops a few times, different from how the column check is happening. Not checking rows the same way (>=2 checker), then?.

Some flops take input by both counters. Given each counter's value maps to a row or a column, a signal depending on both, may be somegrouping; diagonals was my next guess, especially with two independent counters there trying to define one.

When checked against the cells these flops responds to, a diagonal needs every cell of it to have same row − column (or row + column) value. The cells spread across 6 different row−col values and 8 different row+col values.

The flops that are reacting are a for some scattered cells I went looking elsewhere for a clue, which sent me toward the output generator next.

Also, followed two of these anyway, one from this checking unknown, one from a column. Both are feeding into a shared AND gate, which fed into another AND stage, which fed straight into the exact logic driving success at the end.

One more counter

The two counters I found don't care about input. So I was thinking if there is another counter that cares about input bits,like maybe counting the stars?

Sent inputs with the total number of 1's ranging from 0 to 121, in multiple simulations, and captured every flop every clock cycle. Looked for the pattern a real binary counter's bits show: one flop toggling on every new star, another toggling every 2, another every 4, every 8, and so on.

I found the counter that counts the bits.

stars:  0  1  2  3  4  5  6  7  8  9 10 ... 22 ...
bit0:   0  1  0  1  0  1  0  1  0  1  0 ...  0
bit1:   0  0  1  1  0  0  1  1  0  0  1 ...  1
bit2:   0  0  0  0  1  1  1  1  0  0  0 ...  1
bit3:   0  0  0  0  0  0  0  0  1  1  1 ...  0
bit4:   0  0  0  0  0  0  0  0  0  0  0 ...  1

Checked this properly by sending the same number of stars in different patterns and watching the same flops. They all behaved the same way regardless of position, so this is a real, genuine bits counter.

Went looking for a flop that goes high only at one specific count and stays zero everywhere else. Found a few candidates at first, but none of them held up once I re-tested with different placements of the same count — each one turned out to already be a comparator or the overflow detector I'd found earlier, just coincidentally triggered early by whatever arrangement I'd used the first time. No dedicated single-count flop turned up anywhere.

Traced success's own complete dependency chain anyway, out of curiosity, and this counter was genuinely in there — all five bits. Which was strange, given I'd just failed to find any flop reading them for a specific count.

My search had only ever looked at flops — stored values. But nothing requires the actual check to live in a flop; it could just as easily be a plain, unstored, combinational gate sitting between the counter and whatever reads it. Went looking again, this time tracing forward from the counter bits directly instead of scanning every flop in the design.

Found it three gates downstream. One gate ANDs together bits 1, 2, and 4. A separate little chain NORs together bit 0, bit 3, and one more flop, which comes out to !bit0 & !bit3 once the extra term (which turned out to just sit at 0 for every count I tested, not actually part of this) drops out. Combine both halves together and you get bit4, bit2, bit1 all high, bit3 and bit0 both low — which is exactly 22 in binary, and nothing else.

stars:   0  1  ... 21  22  23  24 ... 30  31 ... 33
output:  0  0  ...  0   1   0   0 ...  0   0 ...  0

Checked the whole range from 0 to 33, and it fires at exactly one value. Confirmed with different placements of 22 stars, several times over — same result every time.

Traced it one gate further; it feeds directly into success's own decision gate, confirmed net-for-net, not just somewhere in the same neighbourhood. Checked whether the reverse also exists somewhere — a flop or gate reading low only at exactly 22 — but this specific signal only ever gets used once, in this one direction, feeding forward into success and nowhere else.

Only five bits though, so this thing can only count up to 31 before it wraps back around to 0 and starts over. Went looking for a sixth bit specifically, sending well past 31 stars to see if something new kicked in around there. Nothing did — checked the whole range up to 121, and no new flop ever showed up. Five bits, no more.

How "more than 2" gets caught

Seeing the input sequence we already have, I am sure if arranged as a 11x11 grid, rows and columns have exactly 2 bits. But whats there in by mind is if a the flop I first assumed the answer freeze and can't tell difference between 2 and 3, how does the circuit know if there are additional 1's? Then checked the states: flop1 and flop2 together go through four states; 0 seen, 1 seen, 2 seen, then >=3 seen. And each have different states for the 2 flops that are counting number of bits there. So both flops together can tell the difference between 0,1,2,>=3.

My best guess reasoned from the wiring: something later in the circuit reads both flops per group, turns the success off if any hits state 11 i.e. >=3 1's.

Tested this directly: the actual solution with one extra star forced into an satisfied group gave TRY AGAIN, every time. Found another flop, separate that flips from 0 to 1 the moment this happens and stays there; which deeds into one of the three conditions success's gate that needs all to true. When it flags a violation, that condition breaks, and success never become high.

So, what does the winning input actually need to look like

Tracing back through all of this: every group of cells sharing the same index % 11 — a column — needs exactly 2 bits high. Same for every irregular region the two counters together identify. That's 121 real positions worth caring about, out of the 122 the waveform showed; dropping the last one suddenly made a lot more sense.

The second input to success's own gate only reaches 1 right at the very last real cycle — traced to a flag that flips exactly once, at cycle 121, and nowhere else. Whatever the solver handed back as a 122-bit answer, the circuit itself is telling me plainly: it's 121 bits that matter.

Having only looked closely at the fast counter and what comes right after it, the pattern was already consistent enough to draw the obvious conclusion: every block of 11 consecutive input positions, and every set of positions sharing the same index % 11, should end up with exactly 2 bits high. Arrange the dropped 121 bits into an 11×11 grid, and those two conditions read exactly like rows and columns.

Constructed an input satisfying that — 2 per row, 2 per column, nothing else assumed — and ran it through.

TRY AGAIN

Checking the ROM

Wanted to understand how the output generator itself actually produces these messages. Turned out to be built around a small ROM — not a state machine quietly generating the bit sequence live, which is what I'd assumed up to this point. Looked through its contents from there, and everything else follows the same way it did before:

EMPTY SKY
BIG BANG
(* TWO STARS *)
TRY AGAIN

To check properly, I needed to understand how the output generator actually works. Found that it's built around a small ROM.

Inspecting its full contents gave me exactly one more string:

TWO"NOT TOUCH

Read it again: two [somethings], never touching.

Reconsidering the 122nd "don't-care" bit from earlier observations; dropping it left exactly 121, which arranges cleanly as an 11×11 grid. Checked the Z3 solver's winning sequence showed something: sure, no two of the "high" bits sat next to each other, not even diagonally.

Searching for what this string can mean: found existing puzzles called Star Battle; place stars on an N×N grid (divided into N regions) such that every row, every column, and every region contains exactly two stars, and no two stars touch, even diagonally, so now it is clear that we need to look at 121 bits not 122.

The "2 stars per region" variant (as opposed to the more common "1 star" version) is a completely standard, a commonly-played version of the same puzzle. Which also finally explained the ROM string: TWO"NOT TOUCH is literally the game Star Battle's alternate name; "Two Not Touch."

One more thing I wanted to check: given I found this string by reading the ROM contents, was there some input that can accidentally would have revealed that last string itself thought i might have missed some pattern in initial exploration , or was it just hiding there, permanently unreachable? Ran it through the solver, asking for any input that can ever produce those bytes; solver returned no solution at all, but when I send input that satisfies 3 of the rules, but not the touching rule, I saw the output TWO"NOT TOUCH. So it IS reachable from input sequence but the solver was not able to converge

So: I found the solution and functionality, Right?.

Which means the real remaining task is recovering the puzzle's actual region layout from a chip that only ever outputs pass/fail on a full grid.

Approach 1: reading the flops directly

While looking into the output generator earlier, I'd already been wondering what all these internal flops were actually counting or storing.

Tracing backward from success gave a list of flops that directly, combinationally feed its decision. From there the natural thing to do was just start looking at them directly; feed all zeros, all ones, a single 1 bit walked across every position, and watch which flops actually change.

One thing that fell out of that early exploration was a sawtooth, which you just read about before a min.

Connecting this to the circuit exploration, if a flop only cares about "has this row seen 2 stars" or "has this column seen 2 stars"; that's not actually useful to me. Rows and columns?; I already know exactly where they are, just from the grid's own shape. What I don't have for free are the regions; the one part of the puzzle, and now I'm interested in this.

Regions have exactly one rule worth exploiting: exactly 2 stars per region. So, the obvious first idea: place 2 stars somewhere on the grid, see which flop goes high. Do that for every possible pair of cells; C(121, 2) = 7,260 combinations.

But wait: I don't need every pair to check with. If I fix one cell and pair it with every other cell in turn, whichever flop goes high consistently for that one reference cell already tells me its whole region in one pass.

So: started with cell 0, paired it with all 120 other cells, and recorded which flops changed for each pairing. The working assumption: seeing 1 in any flop means "these two cells are in the same region"; though that's clearly not exactly known yet, since a flop could possibly go high for many unrelated reasons. There should be some flop, among the noise, that should also be going high for the actual reason I am looking for.

flops with any nonzero high-count: 24
  reg 2293: high for 110 of 120 partners
  reg 8219: high for 107 of 120 partners
  reg 2542: high for  28 of 120 partners
  reg 2708: high for  21 of 120 partners
  reg 8086: high for  13 of 120 partners
  reg 1228, 1230, 1250, 1258, 1259,
  reg 1260, 1261, 1264, 1809, 2037, 8602: all tied at exactly 11
  reg 8092: high for   9 of 120 partners
  ... (and a handful more, with single digits)

Intuitively, numbers like 110 and 107 obviously made no sense; but "obviously" it isn't a real reason to throw them. The smaller end had an actual, defensible reason to eliminate: the minimum possible region size is 3, since 2 cells that are adjacent can never hold 2 non-touching stars in the first place. That removed a few outright.

Still a lot of them left. Then new thought: if one region ate up 100+ cells, the other ten regions; which each need at least 3 cells of their own; will not have room left to exist. That's a real, ceiling, not just my feeling, and it eliminates the 110-partner and 107-partner flops.

Next, a simpler geometric thought: if a set of cells genuinely belongs to one region, every cell in it should share an edge with at least one other member of the same region; the whole thing has to be a single connected component (every cell is reachable from every other). Applying that; was able to strike out most of what was left.

This got it down to just two real contenders; both looked like legitimate, connected, sensibly-sized shapes:

Both connected, both have sensible size, both passed every geometric check I had at that point. New idea: if these cells genuinely belong to one region, then every pair within it should light up the same way; not just pairs involving my original reference cell (cell-0 in this case). But checking every possible pair inside both candidates is not necessary to remove one.

The shortcut: just take a cell that sits in the overlap of both candidates, and re-test it against every cell in both candidate lists. Whichever flop stays perfectly consistent; firing for every true member, silent for everything outside; is the real one.

using overlap cell 12 as the new reference:

  against candidate A's cells:  reg 8086 high 13/13 — every single time
  against candidate B's tail:   reg 8086 high  0/6  — never once

  against candidate B's own cells: reg 1250 high only 1/11 times
  (it doesn't even agree with itself anymore)

Now, it's obvious; candidate A(region A) still fits perfectly from a different angle, candidate B should be eliminated. And the winning bit sequence I already had from the solver has also satisfied exactly this region's rule, cleanly, no coincidences.

So: found a region. Marked it. Then picked a fresh, still-unmarked cell and repeated the whole process; this time adding one more elimination rule: if a candidate's cells overlap with a region I had already confirmed, throw it out, since no cell can belong to two regions at once. Repeat that enough times and the whole puzzle will be what we get; and the very last region doesn't even need whole extraction: whatever cells are left over once ten regions are found have to be the eleventh, by elimination.

mark all cells as unclassified
confirmed_regions = []

while unclassified cells remain:
    ref = any unclassified cell
    for each other cell j:
        place 2 stars at (ref, j), run the chip, record which flops went high

    candidates = every flop whose "fired-with" set, plus ref itself:
        - has at least 3 cells                      (2 adjacent cells can't hold 2 stars)
        - has at most ~100 cells                     (other regions need room too)
        - forms a single 4-directionally connected blob   (regions aren't scattered)
        - can actually fit 2 non-touching cells inside it
        - doesn't overlap any already-confirmed region

    if exactly one candidate survives:
        confirm it as the next region
    elif multiple survive:
        pick a cell in their overlap, re-test it against every cell in each
        candidate, keep whichever flop stays perfectly self-consistent
    mark all of that region's cells as classified

# whatever's left after 10 regions are found is automatically the 11th

Approach 2: symbolic dependency tracing

The eventual approach: symbolically trace, for each of the relevant internal counter flops, exactly which of the 121 grid positions it provably depends on; not by guessing-and-checking specific inputs, but by building an actual symbolic formula for each flop and reading its dependencies straight from that formula. That came back with 11 irregular groups of cells; the regions; which, combined with the winning bit sequence, reconstructs the entire puzzle: question and answer, verified by hand against every rule.

Now look at the puzzle. Found something?

Solve it yourself

Since I ended up with the actual puzzle question and not just its answer, it felt it right to let you solve the exact same grid the chip is checking, by hand, rather than just look at the picture above. Click a cell to place a star, click again to mark it excluded, click once more to clear it. Regions are colored the same way as the grid above.

Closing thoughts

So, what does "reverse engineer this ASIC" actually mean, in the end? Make success go high? Extract the string? I ended up with both, plus the actual logical function the circuit computes, plus the puzzle it's secretly checking, plus few Easter eggs. Maybe that's what was strictly asked for.

Whatever it is, I'm satisfied with where this landed; which matters more to me than it probably should, given the AOF one still stings a little. Not the "I got everything" kind of satisfaction; but the "I actually finished this one" kind. That's really the whole point of writing this up.

One random line

• When a puzzle tells you it contains Easter eggs, it's probably worth looking at the weird stuff you initially decided to ignore.

After getting stuck on what the winning input meant, I remembered the puzzle's note:

"We hid a few fun Easter eggs in the circuit and in the repository (including in parts you don't need to look at to solve the main puzzle)."

Maybe hunting for those will give me some clue to work with.

A leap second

First thing I actually remembered finding; though I lost track of which file it was in; it was a date with year 2016 somewhere. Went through everything looking for it again, and found it in the VCD: Sat Dec 31 23:59:60 2016. I didn't even notice the ":60 seconds" part at first; just that the year seemed like an odd thing to include. Checked for what have happened that day, and: a leap second got added to the time right at that exact moment. A real, valid, unusual timestamp. One Egg found, YAY!.

The row of cells that don't connect to anything

Earlier, while reconstructing the netlist, I remembered seeing two odd custom cell types: INTERNAL_3 and INTERNAL_7; sitting at odd; negative Y coordinate, completely disconnected from the rest of the circuit. Didn't matter for making success go high, so I ignored it at the time. But why at that specific position? And why 21 of one type and 15 of the other? Felt like it had to mean something, I didn't see them yet.

I tried looking at the GDS in the browser-based tinytapeout viewer first, deselecting every other layer to isolate just those two cell types. Got... nothing. A blank screen.

Next attempt: extract just those specific cells into their own tiny standalone GDS file so there'd be less to go wrong. Got back a file; I expected all 36 placed copies, but only found 1 rendered. Opened it anyway.

Gave up on the browser viewer and opened the whole thing in KLayout instead; I looked at the full circuit in KLayout before, just to look, without doing anything with it.

Went hunting for that negative-Y row specifically this time. Toggled layer visibility one at a time, didn't see it at first,

then scrolled down past the main circuit boundary and there it was.

A row of small rectangles, colored a clean green, clearly not part of any real logic. Some short, some long.

Went back to the properly-extracted 36-cell version with this in mind; this time the dots and dashes were very clear. Wrote the pattern out on paper by hand:

… which spelled out:

PER ARENAM AD ASTRA

Latin. Ran it through a translator: "through the sand, to the stars"; google search revealed that it's a play on the actual Latin motto per aspera ad astra, swapped "hardships" with "sand." Genuinely nice tweak for a chip made of silicon.

And the custom cell names suddenly made sense too: INTERNAL_3 and INTERNAL_7; the dot:dash width ratio is exactly 3, and the gap timing ratio is 1:3:7. The names are the Morse timing specifications.

Went looking. Search results (both a Google Search and AI research) revealed nothing real. must be overthinking it, almost certainly.

A string that is inside the raw data

Thinking about that VCD file's hint; "leave no stone unturned"; I thought if metadata anywhere else might reveal something. Checked file modification timestamps: nothing. Checked git commit history: one single commit, just the initial upload. Ran a basic steganography extractions on the PNG image: nothing.

Then I tried something: since the files stores the data in bytes, I scanned the raw file bytes directly for all files, looking for any run of at least 3 consecutive bytes that read as alphabets. Found many, one of them that got my attention to: EGG', sitting right there in the raw file bytes of the layout image.

Looked at lot of of bytes on either side; nothing else is readable for around 200 characters either way. Given I am already hunting for Easter eggs, finding the literal word "EGG'" in the file felt too perfect to be coincidence. But there was nothing more I can reason about it; tried extracting that segment, and the moment I actually decompressed that section of the file, the string disappeared; it only existed in the compressed bytes, never in the real image data.

• github.com/avnlk/reverse-engineering-an-ASIC — the code for this writeup (extraction, simulation, solver, region discovery)
• Jane Street — Can you reverse engineer an ASIC?
• Jane Street — Advent of FPGA Challenge 2025
• Perfect numbers
• Star Battle (puzzle genre)