Designing a technical puzzle
Breaking down the process behind the puzzle at Systems Distributed '24.
I've just returned from the recently concluded Systems Distributed '24 conference in NY, which beat the already high bar set by the inaugural one last year in Cape Town. The speakers were some of the most accomplished people in their fields, and hearing them talk about their individual topics was an absolute joy. What an amazing & inspiring community! I hope they put up the videos soon.
My talk was titled Systems Resurgent?, and was one of the few "non-technical" ones, so obviously I had to complement it with a technical puzzle to keep up the street cred. The audience was presented with a single clue: "If you look carefully at where you bought your tickets from, it's easy peasy" (credit to Federico for coming up with that one). The prize was a copy of the book The Art of doing Science and Engineering by one of the greats in our field, Richard Hamming.
If you don't want to be spoiled, and want to give the puzzle a shot yourself first, this is the time (the tickets were bought at the conf website linked above). Spoilers ahead!
What makes for a good puzzle?
I can't speak for everyone, but the kind of puzzles I enjoy solving, are those that tease a just around the corner kind of feeling. So I usually end up using the following recipe:
- Use something that involves a deeper understanding of a well known tech. The familiarity creates a sense of being within reach, while the deeper understanding part creates the just out of bounds tease.
- Keep the need for non-foundational esoteric knowledge to a minimum.
- At the end of solving it, I should feel like I pushed the boundary of a knowledge I had.
For this puzzle, I chose to center it around git, something that I was sure all the attendees of the conference would be faimilar with. Simply by that choice, criteria #1 is satisfied. Great! Now we need to now figure out how to use the design/behaviour of git in a way that involves a little more than just knowing git workflows.
Structuring the core
At this point, feel free to ponder over how you would go about structuring a puzzle around git? And if you do come up with something that's different than what I'm about to enumerate, I'd love to know more about it in the comments.
At the outset, I had a choice between whether to structure the puzzle around the workflows of git (rebase, merge, bisect etc), or the structure of git (how it stores data). After thinking about it for a while, I concluded that the structure dictated the workflows, and thus was more fundamental. Also, while it's possible to hide clues inside workflows, it'd require too much of a cognitive jump and the total state space of possibilities for the user ends up being too much. So I decide to proceed with using the structure of git to hide the clues.
One trivial way to hide the clues would be to store in one of the files, inside an older commit. But it feels brutish - it relies on increasing the search space instead of relying on some deeper understanding of git. So this approach is a no-go.
Another way could be to hide the clues as an obfuscated script in a git hook. I discarded this approach because it doesn't really have much to do with git, in the sense that it doesn't rely on any deeper git specific idea. Hooks are common place in the VCS world, and have been in existence much before git.
It's common knowledge that git uses an object storage model, i.e. everything is an object - commits, files, directory trees etc. So that gives us something to work with to hide clues. e.g. with my README.md committed, here's what the list of all objects looks like:
amod@mikasa sd24-puzzle % git cat-file --batch-all-objects --batch-check 82cdf829d7d713f5b963f91e2f7317267b54606b tree 37 9f078c14f8b04c6d85e560f831e13fba2e2f8b49 commit 413 b37f16e4d391386b3531ba2554447a5e76db0345 blob 59
We can inspect any one of these objects via git cat-file, e.g. let's look at the contents of the README.md file.
amod@mikasa sd24-puzzle % git cat-file -p b37f16e4d391386b3531ba2554447a5e76db0345 Hello, intrepid explorer! All that you need is right here.
With this understanding, let's create our custom object outside of the file tree.
amod@mikasa sd24-puzzle % echo 'Congratulations, you git!' | git hash-object -w --stdin ac3f875959dd3d3d6a5653d021ffc1af0c5da6d6 amod@mikasa sd24-puzzle % amod@mikasa sd24-puzzle % git cat-file --batch-all-objects --batch-check 82cdf829d7d713f5b963f91e2f7317267b54606b tree 37 9f078c14f8b04c6d85e560f831e13fba2e2f8b49 commit 413 ac3f875959dd3d3d6a5653d021ffc1af0c5da6d6 blob 26 b37f16e4d391386b3531ba2554447a5e76db0345 blob 59 amod@mikasa sd24-puzzle % amod@mikasa sd24-puzzle % git ls-files README.md
Great! As you can see, our newly created object is there, but does not show up in the file tree - great for a puzzle! But there's one problem - if we push it (to say Github), this object won't get pushed. The reason is that it's a dangling object, as you can see by running a git fsck.
amod@mikasa sd24-puzzle % git fsck Checking object directories: 100% (256/256), done. dangling blob ac3f875959dd3d3d6a5653d021ffc1af0c5da6d6
Any object that is not reachable by a git ref is considered dangling. What's a ref? Let's see.
amod@mikasa sd24-puzzle % amod@mikasa sd24-puzzle % git show-ref 9f078c14f8b04c6d85e560f831e13fba2e2f8b49 refs/heads/main amod@mikasa sd24-puzzle % amod@mikasa sd24-puzzle % git cat-file -p 9f078c14f8b04c6d85e560f831e13fba2e2f8b49 tree 82cdf829d7d713f5b963f91e2f7317267b54606b author Amod Malviya ... amod@mikasa sd24-puzzle % amod@mikasa sd24-puzzle % git cat-file -p 82cdf829d7d713f5b963f91e2f7317267b54606b 100644 blob b37f16e4d391386b3531ba2554447a5e76db0345 README.md
As you can see, the HEAD of main branch points to the commit, which points to the tree, which includes a ref to README.md as its child. That's what usually makes all objects reachable. But our custom clue object isn't reachable by any known ref, so it's considered dangling.
But what if we include a custom ref?
amod@mikasa sd24-puzzle % git update-ref refs/sd24/main ac3f875959dd3d3d6a5653d021ffc1af0c5da6d6 amod@mikasa sd24-puzzle % amod@mikasa sd24-puzzle % git show-ref 9f078c14f8b04c6d85e560f831e13fba2e2f8b49 refs/heads/main ac3f875959dd3d3d6a5653d021ffc1af0c5da6d6 refs/sd24/main
Let's look at git fsck again
amod@mikasa sd24-puzzle % git fsck Checking object directories: 100% (256/256), done.
No dangling objects! Awesome! Now we're at a stage where our clue won't show up in git ls-files - we can push it to github via git push origin refs/sd24/main, and the participants can only reach our clue via traversing the objects. Great!
The decorations & the red herrings
Now that we have our core workflow ready, let's add some bells & whistles!
The first one is to figure out how to present the puzzle to the participants. One of my common techniques is to encode something in BIP39, because any combination of more than 8 BIP39 words immediately stands out. In this case, we encode a short URL (amodm.com/7364323470) as a BIP39 mnemonic (gesture hidden suit surge tower response regret tragic creek random art good crew breeze senior). I like this approach because we often associate concepts so strongly to the topic we first learnt it in, that we rarely tend to look deeper. Most online BIP39 decoders will give you a hex encoded string, when in fact each of those hex is simply an ASCII character.
We take this mnemonic and put it as a <meta name="pz"> tag on each page of SD24 - hence the original clue easy peasy. When a participant opens the URL encoded in the mnemonic, they're taken to a secret gist which informs them that they've made progress, and points them to the actual git repo.
The next item is a red herring. We create another hidden object, and associate it with a tag reference.
amod@mikasa sd24-puzzle % echo 'Nice try! But this isn't the place you're looking for :(' | git hash-object -w --stdin 35dca4905dc27ae43862314e126d36016cd4f344 amod@mikasa sd24-puzzle % amod@mikasa sd24-puzzle % git update-ref refs/tags/v1.0 35dca4905dc27ae43862314e126d36016cd4f344 amod@mikasa sd24-puzzle % amod@mikasa sd24-puzzle % git show-ref 9f078c14f8b04c6d85e560f831e13fba2e2f8b49 refs/heads/main ac3f875959dd3d3d6a5653d021ffc1af0c5da6d6 refs/sd24/main 35dca4905dc27ae43862314e126d36016cd4f344 refs/tags/v1.0
I'd originally meant it as a red herring alone, but it had the added effect of screwing up Github's tag page as tags usually refer to tree objects, not blobs. So in the puzzle's repo you'll see 1 Tags, but if you go to the tags page it shows nothing, which adds to the intrigue!
This also has the added benefit of nudging a curious participant to explore the refs a little more. When you clone a repo from github, by default it doesn't download all refs - only the well known ones (like branches, tags etc). Because of the weird tags behaviour, hopefully the participant is nudged to try a git ls-remote or something, which would show up our custom ref.
For our last trick, instead of having a congratulatory message directly, we encode a URL as a Brainfuck program. One can argue that it seems a bit esoteric (not everyone knows of it), but my talk had a reference to Brainfuck, so any participant blocked on it would've immediately recognised it and be able to move on.
As a last-last trick, instead of encoding the URL, we include a LOTR reference, so the Brainfuck program produces an output that says: speak friend and enter: https://amodm.com/7364323470-friend(you know what to do here). Again, it might seem esoteric, but if you search online for "speak friend and enter", you'll immediately know what to do.
Note: while I've used refs/sd24/main for this post, I used refs/xz/main in the actual puzzle to ref the blob containing the BF program.
Plan vs Results
So now, with all the bells & whistles, we have a 3 stage puzzle: 1) the BIP39 stage, 2) the main git stage, 3) the BF stage. I was unsure of whether the puzzle is too easy or too complicated, but it was a systems conference so I had hope. Late in the first day of the conference, I saw Luiz Aoqui be the first one to star the puzzle repo, which means stage 1 had been crossed. Over the next some time, there were a few more people who'd starred/forked the repo.
But it was only close to the end of the conference that I finally saw Emil Stolarsky leave his name on the final secret gist. And he was not alone, a group of 4 people had come together to crack different parts of the puzzle. Congratulations to all of them!
Conversations with them at the end of the conference was fantastic. Turns out they didn't actually do a git ls-remote, and instead took a look at events log for the repo, which showed a push to the custom ref. That feels like a wonderfully legitimate hack to me 😄. So I got to learn their trick, and they got to hear about custom refs.
Great fun & learning all around! Many thanks to Fed, Jihyun & Evan of TigerBeetle in helping get the puzzle organised.