2026-10-04 Reverse Engineering Jane Street’s ASIC Puzzle

An attempt at quantlarping in the year of our lord 2026

This year Jane Street decided to do an ASIC reverse engineering challenge, which i find interesting as hardware has been something i’ve been trying to get into lately. I thought i’d have more time to go on sidequests like this as last year i was bogged down by work, but unfortunately this year i also find myself bogged down by midterms at my postgrad work in NTU. Alas i find myself reading at some of the solutions made by people smarter than me, which got me wanting to try some of the work myself to see if there were any stones unturned (also to do a quantlarping blogpost lol).

The README’s layout.png labels the pins (clk, rst_n, enable, I on the left, O[7:0] and success on the right) and boxes off an “output generator” that you’re told to ignore at first. So the chip takes one bit at a time and answers on a byte-wide bus. Opening example_inputs.vcd in a waveform viewer shows the protocol. rst_n is held low for three rising clock edges. Then enable goes high for exactly 121 cycles while I wiggles, drops, and does the same again for a second attempt of 121 bits. 121 is 11², so something is reading an 11×11 grid one square at a time.

Shown as ASCII, O spells TRY AGAIN after each attempt.

The GDSII file format is a flat stream of records. Each one starts with a 2-byte length, a record type and a data type, followed by big-endian integers, ASCII, or 8-byte floats in IBM’s old excess-64 format.

def _real8(b):
    sign = -1 if b[0] & 0x80 else 1
    exp = (b[0] & 0x7F) - 64
    mant = int.from_bytes(b[1:], 'big') / (1 << 56)
    return sign * mant * 16.0 ** exp

The first pass found 81 cell definitions and one top cell, puzzle, with 9,875 references, 1,499 polygons, 7,061 paths and 17 text labels. Standard-cell names survived (sky130_fd_sc_hd__dfrtp_2, sky130_fd_sc_hd__a221oi_2), and so did every cell’s own pin labels on layer 67/5. Instance and net names were gone. Two cell names weren’t sky130 at all, INTERNAL_3 and INTERNAL_7, each one rectangle on layer 200. Those went on the oddities list straight away. Every polygon edge is horizontal or vertical (zero diagonal edges), and every one of the 7,061 routing paths has exactly two points, so every wire is one rectangle. Getting that rectangle right took one fix. The paths use three end styles: 6,232 are type 2 (extended by half the width), 751 are type 0 (flush), and 78 are type 4, whose extensions are given explicitly by BGNEXTN and ENDEXTN records.

def poly_rects(pts):
    """Manhattan polygon -> list of rects via horizontal slabs (even-odd)."""
    ys = sorted({y for _, y in pts})
    edges = [(pts[i], pts[(i + 1) % len(pts)]) for i in range(len(pts))]
    vert = [(a[0], min(a[1], b[1]), max(a[1], b[1])) for a, b in edges if a[0] == b[0] and a[1] != b[1]]
    out = []
    for y0, y1 in zip(ys, ys[1:]):
        ym = (y0 + y1) / 2
        xs = sorted(x for x, lo, hi in vert if lo < ym < hi)
        for i in range(0, len(xs) - 1, 2):
            out.append((xs[i], y0, xs[i + 1], y1))
    return out

Polygons to nets

sky130 has one local interconnect layer and five metals. Each cut layer joins the conductor with the same layer number to the one above it:

Layer 66/44 (licon) is left out on purpose. It connects li1 down to polysilicon and diffusion inside a cell, which is transistor business, and including it would short every cell’s internals together.

The extractor does five things:

1. Flatten every reference into die coordinates. Only four orientations occur: 8,881 R0, 546 mirrored, 233 R180 and 215 mirrored plus R180.
2. Cut each Manhattan polygon into rectangles with horizontal slabs.
3. Union every two rectangles on the same layer that touch or overlap, using a spatial hash with 3 µm buckets.
4. For each cut, take its centre point and union every shape on layer L and L+1 that covers it.
5. For each pin label inside a cell, find the shape under the label point on that layer, but only among shapes that belong to the same cell instance, so a label near a cell edge can’t pick up a neighbour’s shape.

for l, rects in cuts.items():                 # l = 67..71, datatype 44
    for r in rects:
        cx, cy = (r[0] + r[2]) // 2, (r[1] + r[3]) // 2
        lo = list(hits(l, cx, cy, cx, cy, False))       # shapes on layer l
        hi = list(hits(l + 1, cx, cy, cx, cy, False))   # shapes on layer l+1
        if lo and hi:
            for it in lo + hi: uf.union(lo[0][1], it[1])
        else:
            nocon += 1                        # a cut that lands on nothing

On the warm-up the extractor finds 79 logic cells with every pin on exactly one net, in 0.07 s. On the puzzle it finds 728 logic cells and 741 nets in 0.37 s, plus 676 tap, 204 decap and 10 diode cells with no logic. Zero cuts failed to land on both layers, and zero pins touched more than one net. One net has no driver at all (net 56476) which feeds input A1 of an a31oi and A1 of an a311o.

a221oi means AND groups of 2, 2 and 1 inputs, ORed together, then inverted. o32a means OR groups of 3 and 2, ANDed. The pins follow the groups: A1 A2, B1 B2, C1. So instead of loading the PDK’s Verilog models, cells.py generates every AND-OR and OR-AND function from the name, with a short table for the rest (inverters, buffers, XOR and XNOR, mux2, and AOI/OAI variants with one active-low input like a21boi). The puzzle uses 66 logic cell types, and the file is 59 lines. The plain gates with active-low inputs got me. The first version assumed the inverted pins always come first, as in and4bb (A_N, B_N, C, D), the variant the warm-up uses. The warm-up passed. The first puzzle simulation stopped with KeyError: 'A_N'. AND and NAND put the inverted pin first (and3b: A_N, B, C), while OR and NOR put it last (or3b: A, B, C_N). The fix was to read which inputs end in _N from the extracted pin names instead of guessing.

m = re.fullmatch(r'([ao])(\d+)(o|oi|a|ai)', base)      # a221oi -> 'a', '221', 'oi'
if m:
    first, digits, tail = m.groups()
    gs = _groups(digits)                               # [['A1','A2'], ['B1','B2'], ['C1']]
    inv = tail.endswith('i')
    pins = [p for g in gs for p in g]
    def fn(v, gs=gs, first=first, inv=inv):
        if first == 'a': r = any(all(v[p] for p in g) for g in gs)
        else: r = all(any(v[p] for p in g) for g in gs)
        return int(r) ^ inv
    return ('Y' if inv else 'X'), pins, fn

The flip-flops split the netlist into a combinational graph with no loops. A depth-first sort orders the 630 gates, one pass evaluates them, and then all 92 flops update together: 0 if RESET_B is low, 1 if SET_B is low, otherwise D. Each gate compiles to one inline truth-table lookup:

# a nand2_2 gate in the generated _eval(v). Bit m of 7 = 0b0111 is the output
# for input index m = A | B<<1, so only A = B = 1 gives 0.
v[69884] = (7 >> ((v.get(70528, 0) << 0) | (v.get(69889, 0) << 1))) & 1

That runs at about a third of a millisecond per clock cycle. My first version called a small model function per gate and built a dictionary of pin values for every call, and everything downstream took twice as long. Two checks before believing anything it says. The warm-up’s source is given, so its answer is known: for every a from 0 to 255 and b = 495−a, 496−a and 497−a, S equals a + b == 496. And replaying the puzzle VCD at all 312 rising edges reproduces O at every edge, including both TRY AGAINs, byte for byte. The thing is, my script printed only the last 12 cycles, all zero, and i kinda concluded O never left zero in the file.

The Black Box

At this point we have a functional gate-level model of the chip but we have no idea what it does, Manually reading 630 gates is possible but will take forever, so instead we characterize the circuit using three standard simulation primitives: (1) apply input vectors and observe outputs, (2) force a flip-flop to a known value, and (3) trace the fan-in cone of each flip-flop.

We run the chip with a 121-bit all-zeros input vector and latch the final state of every flip-flop as the baseline. We then run 121 additional simulations, each driving a single 1 at square t (one-hot input vectors), and record the set of flip-flops whose final state differs from the baseline. Each flip-flop is thereby annotated with the set of input squares that perturb it (i.e. its observable input-dependence set.)

base = run(set())
touched = collections.defaultdict(set)
for t in range(121):
    q = run({t})
    for f in q:
        if q[f] != base[f]: touched[f].add(t)

The columns confirm the 11×11 guess. For the irregular groups, an exact tiling search finds that all 11 together cover the 121 squares with no overlap, so the board is divided into 11 regions.

In row-major order, the squares that touch square t and appear earlier in the stream are t−1, t−10, t−11 and t−12, so a 12-element lookback exactly covers the backward neighbourhood. A board with a single star leaves that row holding one star, while the all-zero run leaves every row with none. If the chip only checks whether a row has the correct count, both cases are incorrect, and a flag recording “some row was wrong” is set either way. Which would explain why the probe can’t see rows.

To test this, I constructed a board with exactly two stars in every row, spaced so that no two touch (even rows use columns 0 and 2, odd rows 5 and 7), and compared it against variants in which row 4 alone holds 0, 1 or 3 stars. One flip-flop, 5638, differs between the all-two board and the all-zero board, but not between the all-zero board and any of the three row-4 variants. Varying row 4 alone:

two = {r * N + x for r in range(N) for x in ((0, 2) if r % 2 == 0 else (5, 7))}  # 2 per row, none touching
def with_row4(cols): return {p for p in two if p // N != 4} | {4 * N + x for x in cols}
q2 = run(two)
odd = {k: run(with_row4(cols)) for k, cols in [(0, ()), (1, (0,)), (3, (0, 2, 9))]}
rowflag = [f for f in q2 if f not in touched and q2[f] != base[f]
           and all(o[f] == base[f] for o in odd.values())]          # -> [5638]

So 5638 is a sticky “bad row” flag, and a row is good only with exactly two stars. The probe only shows the first bit of each column or region counter, since one star only ever moves the first bit. To find the second bit I used the netlist, but only to ask a structural question: which flop feeds this flop’s next-state logic and is fed by it in return? Each of the 22 counters has exactly one such partner. Then, putting k stars into column 3:

A 2-bit counter that saturates at three. The regions count the same way. The total is a plain binary counter: across 0 to 36 non-touching stars, its bits always read the star count. Now I could force the answer out. I ran the two-per-row board, then overwrote every column and region counter and the total with chosen values before the final clock, and watched success:

def verdict(total=22, col=None, reg=None):
    q = run(two)
    for i, (x, y) in enumerate(cols): q[x], q[y] = (col or {}).get(i, (0, 1))   # (0, 1) = two stars
    for i, (x, y) in enumerate(regs): q[x], q[y] = (reg or {}).get(i, (0, 1))
    for i, f in enumerate(tot): q[f] = (total >> i) & 1
    c.q = q
    hi = 0
    for _ in range(3):
        c.step({'rst_n': 1, 'enable': 1, 'I': 0, 'clk': 0}); hi |= c.out('success')
    return hi

So every column and every region needs exactly two stars, and 22 in total, which is 11 rows × 2 and therefore redundant once the rows are right.

The solution

Last rule. The 12-square memory suggested neighbours matter, so I probed pairs: one star at square 60 (row 5, column 5) and a second star d squares later, for d from 1 to 24, looking for flops that pairs move but single stars never do. Three show up. Two of them (8591 and 1808) are second counter bits, which only move when two stars share a region or a column. The third, 5337, is set only at distances 1, 10, 11 and 12. Moving the first star to the board’s edges shows it knows where rows end:

The solver operates on a fixed 2-per-row, 2-per-column, 2-per-region constraint set with an 8-neighbour (Moore neighbourhood, diagonals included) non-adjacency exclusion on star placement. Positions are indexed in stream order; for a star at index i, the four forward neighbours are checked against the four backward neighbours of the paired star at index j, such that the union of both sets spans all eight surrounding cells. Adjacency is defined topologically on the board lattice, not by stream proximity (e.g. cells 10 and 11 are stream-adjacent but edge-disjoint, and therefore not touching).

This defines the Star Battle (a.k.a. Two Not Touch) constraint satisfaction problem. The solver consumes only the rule set and the region map. It performs a DFS over the search tree, placing two stars per row in left-to-right order, and prunes a candidate cell if:

• its column already contains 2 stars,
• its region already contains 2 stars, or
• it lies within the Moore neighbourhood of a previously placed star. The search enumerates the full tree and yields exactly one valid solution.

def solve():
    sols, stars = [], []
    colc, regc = [0] * N, [0] * N
    def ok(p):
        r, x = divmod(p, N)
        return all(not (abs(r - q // N) <= 1 and abs(x - q % N) <= 1) for q in stars)
    def row(r, start, k):
        if k == 2:
            if r + 1 == N: sols.append(sorted(stars)); return
            return row(r + 1, (r + 1) * N, 0)
        for p in range(start, (r + 1) * N):
            x, g = p % N, region[p]
            if colc[x] < 2 and regc[g] < 2 and ok(p):
                stars.append(p); colc[x] += 1; regc[g] += 1
                row(r, p + 2, k + 1)
                stars.pop(); colc[x] -= 1; regc[g] -= 1
    row(0, 0, 0)
    return sols

The first time I fed it in, my script said success = 0. I had read success immediately after the 121st clock edge. It goes high one clock later and stays high. For the negative case I flipped each of the 121 bits in turn, and all 121 runs print TRY AGAIN. The output generator then emits one byte per clock:

00 28 2a 20 54 57 4f 20 53 54 41 52 53 20 2a 29 00 00 00 00
    (  *     T  W  O     S  T  A  R  S     *  )

The answer is (* TWO STARS *). The (* *) around it is OCaml comment syntax. In addition to this, the solutions page had listed several easter eggs ¹.

The waveform header

The leap second and “Leave no stone unturned!” were the first two entries on the list.

The night sky

This is the one I missed. Once you know the input is an 11×11 grid, the obvious thing is to draw the VCD’s two failed attempts as grids.

..#.#.#....      ##.#.##....
...#.##....      #..####....
#.#..##....      .....#.....
.....#.....      #....##....
.###.##....      ###.###....
#..#.##....      #....##....
###..##....      #..#.##....
...#.##....      ..#.###....
..#.###....      ##..###....
.....#.....      .....#.....
##..###....      .....#.....

The right four columns are empty in all 22 rows, which no real guess at a solution would do. Read the left seven columns of each row as a 7-bit number, least significant bit first, and every row is a printable character: the attempts spell “The night s” and “ky awaits”. I’d tried decoding the bit stream as ASCII earlier by cutting it into continuous 7- and 8-bit chunks, which runs straight across the row boundaries and finds nothing. The grid printout had the answer and i kinda missed it lol.

rows = [inp[i:i + N] for i in range(0, len(inp), N)]   # inp: the 242 enabled I bits from the VCD
''.join(chr(int(r[:7][::-1], 2)) for r in rows)        # -> 'The night sky awaits  '

Morse code under the die

The two INTERNAL cells are placed 36 times in a single row at y = −52.72 µm, below the 200 × 300 µm die boundary on layer 235/4. Every placement sits a whole number of 460 nm steps from the first one, 460 nm being the width of a sky130 placement site.² INTERNAL_3 is 1,380 nm wide, so 3 sites, and INTERNAL_7 is 4,140 nm, 9 sites. The gaps are 3 sites inside a group, 9 between groups and 21 in three places. A 1:3 ratio between short and long marks, with gaps of 1, 3 and 7 units, is standard Morse timing.³ Here everything is scaled by three.

It reads PER ARENAM AD ASTRA, “through sand to the stars”, a play on per aspera ad astra (silicon chips are made from sand).

JS logo in met2

The 1,366 met2 polygons are all 300 × 300 nm squares on a 57 × 57 grid with 300 nm pitch, starting at (34.9, 35.2) µm. A version-10 QR code is exactly 57 modules square,[^qr] so my first guess was a QR code, but turns out its the Jane Street logo.

The warm-up GDS has the identical bitmap at (65.9, 66.2) µm. While in the GDS I also checked whether any standard cell had been tampered with, by comparing each cell definition against the same cell in the warm-up GDS. 21 came back different, which was exciting for about a minute (nothing special came of it tho).

Five messages

Once the rules were known, the natural thing was to ask the chip what it says about inputs that are wrong in specific ways. All zeros prints EMPTY SKY. All ones prints BIG BANG. A board with the right counts everywhere but touching stars prints TWO"NOT TOUCH, the puzzle’s other name, with a stray character in it. Finding that board took two tries: the solver with its touching check removed was still running after two minutes when I killed it, and adding one prune (no region may need more stars than it has squares left below the current row) made it return instantly. Six random boards for every star count from 0 to 121 confirmed that only 0 stars gives EMPTY SKY and only 121 gives BIG BANG.

To check there was nothing else, I went into the output generator. The eight flops that mixed the whole input turned out to be a key. Forcing them to all 256 values on the all-zero run printed EMPTY SKY every time. On the winning run it gave 256 different strings, so the key encrypts the winning message and nothing else. Walking back from O[7:0] finds 23 flops: those 8 and 15 more. 2¹⁵ is 32,768, small enough to try every state and read O once for each. The letters that can appear include C, H and U, which only TWO NOT TOUCH uses, and nothing points to a sixth message. Along the way I misread which of two flops was the success flag and decoded the star counter with two bits swapped, neither of which changed the result.

The floating wire

That stray " in TWO"NOT TOUCH is byte 0x22, one bit away from a space (0x20). I had treated an undriven net as 0, and when tied to 1 instead, the message comes out as TWO NOT TOUCJ followed by two junk bytes, so neither value gives a clean string. The results post explains that thee TWO NOT TOUCH output path has an unconnected wire in it, which is why the TWO"NOT TOUCH happened in the simulation. This was a bug that the team had caught in an LVS pass but left it as an extra easter egg.

0x20   0010 0000   ' '
0x22   0010 0010   '"'