Solving the Jane Street reverse engineering challenge
jestoph.com
jestoph.com
This resonates so much. I had a similar feeling after going to my very first operations research lecture. Solving seemingly incomprehensibly complex problems by framing them as a bunch of simple constraints and getting a solution seemed like such magic.
Many people say that the way to tackle a hard problem is to break it down into smaller problems. I disagree. The best way to tackle a hard problem is to break it down into a defined search space and as many seemingly-redundant constraints as you can possibly list, then dump it all into a solver, go take a nap for a few hours or possibly a month, then come back to the problem solved for you.
Question: Can one or another of those thresholds in sibling or parent nodes ever be met if some number of the samples are below some floor reading? Or, how many zeros does it take to silence a threshold check on the node itself, a sibling, or a parent?
To make this tractable I have tried gridding fit parameters, freezing randomness, and using simplified algs like original Metropolis-Hastings
It's a moderately technical and (hopefully) entertaining run through of the process. I hope you enjoy reading it as much as I enjoyed doing the challenge (though, as you'll read, it was also quite a frustrating process). My github is on the post if you were interested in seeing a bit more in detail what my solution looked like, though I intend to write some follow up posts that are a bit more in the weeds of the solution. And frankly, the code I used is pretty ugly but it got the job done.
This is my first blog post, so if you have any feedback please let me know. All the writing, all the code was done by me, by hand, in vim.
[0] https://blog.janestreet.com/can-you-reverse-engineer-an-asic...
Very cool seeing someone completely naive going into this :)
If you want to read more about a bit more... cheaty way to do this, I have written about using formal verification machinery to straight up force the solution out of the netlist here: https://atx.name/electronics/asic-re/ . Could be a bit of an infohazard, but I think journey is the goal and yours was certainly more educational :)
This is the route I ended up going! I posted my own writeup here: https://pradyun.net/blog/reverse_engineering.html
I should add I have an EE degree (but have never worked as an EE), so even though I don't know industry standards like this sky130 thing, it's not completely foreign to me.
Curiosity is good but maturity is trusting that the problem will get hard at some point anyways, that improving the most efficient way is usually also interesting and is more likely to deliver desired things on time or at all, which can be a big deal if what you're trying to deliver it worth it, like.. a new MRI machine that detects new types of cancers, etc.
If you don't care about what you're trying to deliver, that's another problem that requires at least some questioning, though I understand people have families to take care of etc.
As for what to do next, I used to spend way too much of my late-2000s time on puzzle hunts (particularly the Melbourne Uni one [1]) and this tickled the same part of my brain. Unfortunately they're no longer a thing, but it definitely sounds like you'd enjoy something similar.
You can install librelane to get the whole open silicon tool suite and the sky130 PDK. Circuit extraction can be done with magic. Going from a spice netlist to verilog netlist is pretty mechanical and not a hard transform to write. You almost immediately have something that can be simulated and a good baseline for further reversing.
So that was the missing part for me! I did it from scratch (with custom Python script with gdstk and shapely) (the GDS file does have the cells annotated, so not a big problem but still). I was thinking about scripting the "trace net" tool in klayout but decided that's going to probably bring its own can of worms...
I'd like to do a full writeup but haven't had the time.
That's very kind of you. At some point I had put so much of myself in to it that I was in too deep and the only was out was to keep digging.
I'll take a look at librelane thanks!
Now if he is presenting his tools as a good way to solve this problem, something you should use, or any such - that would be a bad thing. Good tools for this are complex and need to be done as part of a large team. If good tools that others should use is the goal then he should join some other group making those tools. I'm sure there is an existing open source project (maybe KiCAD - I'm not in this space so that is the only name I can come up with but maybe their goals are different?) that does this and would welcome more help.
Also, yosys has support for doing “assertion checking”, which I used in my solution: https://sunaabh.com/systems/2026/08/18/jspuzzle.html
It should be `/img/two-stars.png` instead it's right now `/img/two-starts.pgn`.
For those interested in the image itself: https://jestoph.com/img/two-stars.png
The neural net engineering challenge was so awesome, I got really into it, spent way too much time and then was shocked when I actually managed to solve it. Since then I've gotten interested in... hardware. God help me
just for info: https://en.wikipedia.org/wiki/GDSII will tell you about the GDS format. It apparently stands for Graphic Data System II (originally developed by Calma in the late 1970s).
I also briefly wrote about my approach here, with less pictures but going into slightly more detail about how to convert circuits to z3 equations: https://gist.github.com/KarelPeeters/dba417c2690cf0505ac9079...
I'm not actually using formal verification at $DAYJOB, there we're using MILP solvers (which are closely related to SAT solvers) as part of the compilation flow when scheduling operations onto hardware accelerators.
I have been interested in formal verification for hardware for a while, but so far haven't found an opportunity to apply it. There are some great resources online though: the ZipCpu blog at https://zipcpu.com/formal/formal.html and SymbiYosys website at https://symbiyosys.readthedocs.io/en/latest/. I hindsight I could probably have used SymbiYosys instead of Z3, it would have saved me from having to walk the graph and map the gates to equations myself.
But, they do have a hardware division, and Jane Street has a podcast that talks about some of the things they do https://signalsandthreads.com/?tag=hardware
(Or did they close yesterday?)
https://blog.janestreet.com/can-you-reverse-engineer-an-asic...
In any case, I had it all worked out already. But looking at other people's submissions today showed me that I found some easter eggs other hadn't. That was encouraging. (And I missed some that others found, of course.)
I also realised I'd missed a lot of easter eggs, like the morse code - I wish I'd spotted that!
I just can't tinker for the sake of tinkering. Too goal oriented I guess.
Just me? (that is also why school started to bore me right before high school and why I learn better on my own, I did go too College but thank god I didn't do CompSci or that would have disgusted me...)
These GDS design files have a lot more structure to them.
Let me help you: work on figuring out how to spend the millions of dollars every year Jane Street will pay you to clock in. I've heard private aviation is expensive, for example. :)
At least by the looks of it, Jane Street appears to be an odd one to genuinely value competence.
https://pubmed.ncbi.nlm.nih.gov/38497251/ (if "engineering and computer science" means "IT")
I don't know if it's actually true but the idea is interesting.
No. FAANG companies and quant firms want people who are independent and self-directed, not people who need to be told what to do.
It's a thing, I assure you. And it's pretty common parlance in online / technical culture. We don't need to word police this thing.
Does Jane Street really pay that much? Of course 7 figures is possible, but these median comps seem lower than FAANG (and with much higher workload): https://www.levels.fyi/companies/jane-street/salaries/softwa...
Let them taste their own medicine. :)
Personally, I did not learn that much from that experience. So I am glad that there's other people working on it as well. I am mostly interested in the techniques used to solve this.
What did you expect?
That itself is a learning experience. What is even the point of technical interview questions or take home questions? This means that I am now open to hiring completely non-technical person, as long as they have a good personality and management skills more than a competent developer.
This is sad conclusion. Maybe you're more right than wrong, but my answer to the "value" question would be:
Solving even harder problems based on lessons from solving easier ones? Pretty similar to the trajectory in this blog post. Perhaps aided additionally by llms and other tools that can solve the subproblems so you can focus on the less obvious/automatable aspects of the problem?
But note the tension, only by being involved in the problem solving to some extent do you become better at it. So if your default is to say "An LLM can or will soon be able to solve it, why bother?", then your situation will become more desperate and your outlook more negative in a self-reinforcing way.
I recently solved a (in)famously hard challenge (disobey conference hacker ticket) more or less by accident. I say by accident because I have always ignored this challenges as they generally require a lot of patience and motivation to solve. Some years they haven't been solved at all. This year I had a GPT sub with some unused quota so I thought let's see how far it gets.
And it crunched through the whole thing in an evening and morning (occasional poking from me to keep going and steer it right).
Like anon, I learned nothing except that the agents have become really good at solving puzzles. Last time I had thrown a puzzle on them was Advent of code, with GPT3 I think and it struggled so much I gave up my experiment on day 7 or something.
>Personally, I did not learn that much from that experience
Fire is hot, water is wet, etc
If success was the intent, then it's a win.
While challenges are fun, sometimes the requirement is simply to achieve the end goal, with no other point than that.
If your job is to stop terrorists, and that includes hacking into a system and extracting their plans, the "fun" of it isn't the point, only the end goal it's important. Sometimes when we do things like this for fun we forget that someone else out there absolutely needs to achieve the result and doesn't care how it's achieved.
It's the part of penetration testing some people miss. (It's not generally a fun job, almost everyone I know that did it got out as soon as possible. They weren't solving problems, they just running audit scripts and generating reports.)
> Worked for 12m 36s
> Solved
https://chatgpt.com/s/t_6a9aed0b09988191b0f2850dee056b48
Edit: It didn't independently solve it.
> 1. Used the public reconstruction to obtain the recovered RTL/constraint structure, including the 11×11 region map and the fact that it is a two-stars-per-row/column/region, non-touching puzzle.
> 2. Then independently wrote and ran my own exhaustive solver against that recovered constraint system.
I have no doubt that modern agents can solve challenges like this even without external help, but you should at least briefly look at the output before posting it online!