2021 is the first year during which I held a full-time job
continuously. My disposable income and discretionary spending have both
increased the most sharply since, well, ever. It’s weird.
We are still in a pandemic. Greek letters continue to be associated
with uncool things. I got vaccinated and started taking measured (but
still small) risks. Funny story: my first vaccination was a complete
surprise, as my roommate knocked on my door mid-day to inform me that
somebody he knew had extra vaccines to give out — except that the night
before I had a dream about being vaccinated, which was weird enough that
I wrote that dream down, something I do only once every few months. I
also got boosted just a few days ago.
A famous Trail of Bits post says to stop using
RSA: it’s simple enough to make people think they can implement it
correctly, but full of invisible traps. In contrast, although elliptic
curve cryptography (ECC) implementations could also fall into subtle
traps, they usually don’t. The post conjectures that this is because ECC
intimidates people into using cryptographically sound libraries instead
of implementing their own.
If you do want to understand ECC just enough to produce your own
trap-ridden implementation, though, this post aims to get you there.
(Assuming some mathematical background chosen in a not particularly
principled way, approximately what I had before writing this post.)
Hence the title. Because I have a cryptographic conscience, I will still
point out the traps I know of; but there are probably traps I don’t know
about.
This post contains a lot of handwaving and straight-up giving up on
proofs. You don’t need to know the proofs to be dangerous. The ethos is
sort of like Napkin,
but way shoddier and with zero pretense of pedagogical soundness. Still,
here are some concrete questions that I learned the answer to while
writing this post:
Why does the group law hold, sort of intuitively?
Why do people have to modify Curve25519 before using it to compute
digital signatures?
What is a “quadratic twist” and why should I care about it to pick a
secure elliptic curve?
How is it possible that an isogeny can be described as surjective
but not injective while mapping a finite elliptic curve to another
elliptic curve of the same cardinality?
How many claws does an alligator have?
Elliptic curves have a lot of complicated algebra. If you ever
studied algebra in high school and did exercises where you had to
simplify or factor or graph some really complicated algebraic
expression, and you learned that algebra is also the name of a field in
higher mathematics, you might have assumed that working algebraists just
dealt with even more complicated expressions. If you then studied
algebra in college, you’d probably have realized that that’s not really
what algebra is about at all; the difficulty comes from new
abstractions, like a bunch of the terms above.
Well… the study of elliptic curves involves a bunch of complicated
expressions like what your high school self might have imagined.
Sometimes, notes will just explode into a trainwreck of terms like
“This is REAL Math, done by REAL Mathematicians,” one is tempted to
quip. The Explicit-Formulas
Database is a fun place to take a gander through. I will copy
formulas into this post from time to time when there’s something about
them I want to call attention to, but in general we won’t do any
complicated algebraic manipulations in this post. Just be prepared.
Because I’m focusing on conceptual understanding (and am lazy), this
post contains almost no code, and definitely no code that’s runnable in
any real programming language.
Imagine you had a button you could press whenever you saw or heard
something you wanted to remember. By holding that button down for about
a minute, you’ll be able to remember that thing forever. There
are no undesirable side effects. Sounds like a pretty good deal,
right?
There’s only one catch: you have to regularly find new things to
press the button on. If you stop for more than a few days, the effects
wear off. If you ask me, it still seems almost too good to be true! But
it’s not. It’s the magic of spaced
repetition.1
I had known about this magic for a long time and read blog posts from
all directions telling me to use it, typically but not necessarily
through Anki. Examples include
Nicky Case’s interactive guide
and Alexey Guzey’s guide; and because
this has been so well-covered, I won’t go into how or why spaced
repetition works or how one would use Anki in this post. Still, for a
long time, I found the one “catch” to be of the -22 variety: I didn’t
use Anki regularly because I didn’t have any flash cards of things I
wanted to remember; but I didn’t make any flash cards of things I wanted
to remember because, given that I didn’t use Anki regularly, making
those flash cards wouldn’t actually help me remember those things.
Here is the One Weird Anki Trick that got me to finally turn spaced
repetition into a habit: I created an Anki deck with a bunch of amusing
but utterly useless cards,2 in order to make
studying the Anki deck an entertaining activity I actually wanted to do.
(Getting the mobile app and syncing my deck online also helped a lot.)
Only after I started to habitually check my Anki deck did I start adding
cards for the things I actually wanted to learn. I keep everything in
one deck,3 so that my fun cards are spread out
among my “work” cards, and when I find myself losing motivation, I add
more useless entertainment cards.
I subscribed to Discord Nitro a month ago, but only recently did I
start thinking about the full range of powers the subscription granted
me. I could create my own reactions, dump them in my personal server,
and use them to react anywhere.
However, when I finally started trying to create some reactions, I
hit an interesting snag: Discord can be used in dark and light mode,1 and a reaction will have the same
color on both modes. If I wanted my reaction to be as clearly readable
in both modes as possible, what color should I make it?
(I could, of course, just outline my reaction with a contrasting
color, but let’s say that’s cheating. With the limited space in a
reaction, outlining isn’t that great of a solution anyway.)
Now, one can’t really just compute the “contrast of two
colors” given only their RGB components; there’s no universally
agreed-on definition of contrast in
vision, and even if there were one, the contrast of two given colors
would depend on the color space and possibly the viewer’s biology. But,
to get a concrete answer to this question, we can use the standard sRGB
model and the W3C’s definitions of contrast ratio
and relative
luminance.2 As of time of writing on my
computer,3 Discord reactions have background
#2f3136
on dark mode and #f2f3f5 on
light mode. Reactions you’ve reacted with have background #3b405a
on dark mode and #e7e9fd on
light mode. Because the dark mode background gets lighter and the light
mode background gets darker, we’ll use the latter colors so we’re
optimizing the worst-case contrast.
There are smarter approaches, but the 2563 = 16,777,216
possible 8-bit colors are perfectly feasible to brute force, so I wrote
a short Python script to check all of them, which is at the bottom of
this post. Under the parameters I’ve outlined, the optimal color for a
Discord reaction is rgb(255, 65, 3) or
#ff4103. A demo:
#ff4103 #ff4103 ●
CR: 2.90738237
#ff4103 #ff4103 ●
CR: 2.90738217
That was simple enough, but this color’s worst-case contrast ratio is
less than 0.0000002 better than the runner-up. Surely even very mild
aesthetic considerations will outweigh that. (It’s highly doubtful that
the formulae I used were intended to have this degree of precision in
the first place.)
After playing with a few ways to get a spread of options, I settled
on categorizing colors into six buckets of saturation and twelve buckets
of hue in the simple
HSV model, and then finding the optimal color within each bucket.
Here is a table of my results:
This post is motivated by reasons very similar to the ones that
motivated my React and Redux
“tutorial”. Again, it should be more accurately but less
informatively titled “How I wish SQL SELECTs were explained to me”.
Again, it does not imply that this method of explanation is suitable for
anybody else. One difference is that this time, I mostly only wanted to
learn about SQL SELECTs to the extent it would help me perform and
optimize queries in Django’s ORM, but to prevent this post from
languishing forever in my drafts folder, that material has been
sectioned off into a possible future post, because I figured out what I
wanted, ran out of steam, and am now trying to learn TLA⁺. Just me
things.
Background
The SQL standard is confusing and almost never completely
implemented; there are huge inconsistencies between SQL implementations.
I will focus on SQLite because it’s popular and easy to play with, but
generally try to stay away from unpopular or nonstandard features. SQLite’s SELECT
documentation is good reading for one particular SQL
implementation.
A SQL database is a place where you store and query a bunch of data
that’s organized into tables. A table is a homogeneous list of rows. A
row is a heterogeneous tuple of values of various simple data types. The
data types supported depend on the SQL implementation; typical examples
are integers and strings of various sizes, floating point numbers, and
dates/datetimes. All of these types can be nullable; NULL is a SQL value
that can appear just about anywhere. (Like many of the other SQL
features, NULL is handled somewhat inconsistently across SQL
implementations, but as a first-order approximation it’s closer to a
floating-point NaN than, say, Java’s “null”. We’ll talk more about it
later.) However, note that you can’t have a variable-size list of other
things in a row. And just to make sure it’s clear, all the rows in a
given table must have the same data types in the same order.
A “column” is just what you’d intuitively expect it to be: it’s the
homogeneous list of all values in a particular position in each row of a
table, which all have the same data type. One thing I haven’t mentioned
yet is that table columns all have names. This is true both for tables
stored in the database and for the ephemeral tables that are the output
of queries.
Since I’ll also be referring to more complex types like lists and
tuples often seen in conventional programming languages, I’ll call these
simple data types “scalar types” and values of those types “scalars”.
This is not SQL terminology; documentation usually just calls these
“data types”. Here’s SQLite’s page on data
types.
To play along, install SQLite and run it. You should get dropped into
a connection to an ephemeral in-memory database, which is plenty enough
for our purposes. Make a table and mutter some magic incantations to
make the output a little prettier for us:
CREATETABLE a (idint);INSERTINTO a VALUES (1), (2), (3), (4);.headers on.modecolumn
Did you know that it’s harder to become an MIT admissions blogger as
an MIT student than it is to get into MIT as an applicant? It was true
my year, in which 18,306 students applied and 1,467 were admitted
(8.0%),1 whereas 69 students applied for 5
blogging spots (7.2%).2 Anecdotally it might also be true
for future years.
I was among the 92.8% who got rejected in the latter process.
Although I obviously would have preferred things go the other way, I
can’t say I was surprised, firstly because, objectively, the odds were
against me (as they were for every other individual applicant); secondly
because, to the extent I can make educated guesses about the criteria
the folks at MIT Admissions would have chosen bloggers by, I would have
been close to the worst possible candidate;3
thirdly because my application probably wasn’t very good.4
I didn’t dwell on it; I just thought to myself some vague consoling
thoughts and moved on. No matter what I missed out on, at least I
retained complete freedom: to choose what to write about, when to post
it, and how to format and typeset it, down to the very last
box-shadow.
Right? But, although I mostly successfully avoided thinking about it,
there really was a lot to like about being an admissions blogger! I
liked writing — or perhaps, I liked being a person who has written a
lot more, and having a commitment to blog regularly would be a way
to force myself to become that person. I liked the idea of getting to
share things with thousands of readers, or less euphemistically I liked
the thought of being, if ever so slightly, famous.5 I
liked the idea of having a sketched portrait and being part of official
events with “Blogger” in the title and all that jazz. Collectively these
things just felt cool.
The thing is, though, that there were things I could do to try to get
those things for myself, and I didn’t do them. I know how to force
myself to blog regularly, which is just by announcing publicly to nobody
in particular that I’ll blog regularly (it’s worked effectively at least
twice). I know many places I could promote my blog and try to get more
readers. I can buy a sketched portrait.6
It’s not that hard.
Note: if you are viewing this shortly after it’s published and
somehow don’t want to be spoiled on Mystery Hunt, make sure this spoiler
formatting shows up: this text should be
spoilered; if it doesn’t, try shift-refreshing. (There are
Correct Ways to fix this, but I’m too lazy to do them. Sorry.)
Somehow, it slipped my mind until trying to write the 2020 year-end
post that I’d probably want to write a post on all this. In fact, there
was one major project that I started in 2019, but that I didn’t think of
mentioning in my 2019 year-end post because it wasn’t ready to be
announced at that time, and that I almost forgot that I had never
mentioned. But this post is a pretty good place to announce it.
Planning Mystery Hunt is a massive year-long endeavor. I didn’t have
any leadership or otherwise high-responsibility roles, which made sense
because I was busy writing a masters thesis for the first four months of
Mystery Hunt planning. Because of that, and because I know many many
other people on our team have written and will be writing blog posts (Rahul’s
post, Nathan’s post,
CJ’s
post, maybe more to come?) I will focus on the things I did
specifically. (So there is minimal discussion of the theme, overall
organization, or big decisions like our COVID-19 response; I think the
linked posts cover these well already.)
Puzzle-Writing Software
One part I did largely have “ownership” of, and that I sank a lot of
time into, was maintaining our software for writing puzzles — the
website where authors submitted puzzle ideas and drafts, testsolvers
tested puzzles, and editors tracked and discussed the statuses of all
the puzzles. This role was largely a continuation of me owning the same
component for Galactic Puzzle Hunt since 2018, which itself grew out of
the comparative advantage of having worked on it a little when writing with Random Fish for the 2015
MIT Mystery Hunt. There is some life lesson about specialization or
pigeonholing to be learned here. But, to start at the beginning:
Puzzletron is
a piece of PHP software used for organizing puzzle writing for
puzzlehunts. The first
commit on GitHub says it was imported from Metaphysical Plant in
2011; it’s likely older. There are active commits each year until
January 2018, and AMA responses from Setec
(2019) and Left
Out (2020) mentioning it, so I believe most if not all Mystery Hunt
writing teams used and improved Puzzletron and passed it down over those
years.
It’s a strange and darkly funny story — Tim Minchin wrote the album
this is from, Apart
Together, well before the pandemic hit and social distancing
became the norm, and I assume I am not alone in finding that the song
resonates unusually strongly as a result.1 By
Jove, it resonates.
Nobody needs me to say that it’s been a rough year. People have been
complaining that each of the last few years were terrible, and looking
forward to the next one, and being disappointed — as if years were
coherent bundles of quality, and there was any reason to expect
discontinuities in how things are going to occur around January 1st —
and as if there were additionally any reason to expect such
discontinuities, if they did exist, to be positive ones.
Seriously, do you remember when we thought 2015–2018 were bad?
And yet… I feel like overall, 2020 went quite a bit better than
expectations for me. Which maybe means it’s astronomically better than
the average person’s 2020. I had a long draft for this post that slowly
accumulated words over the year as usual, but a lot of the ramblings I’d
usually include now seem unusually vapid, and a lot of the deeper trends
and experiences I might normally reflect on are things I don’t think
I’ve really gone through or thought about for long enough to achieve
closure on. This is partly due to the pandemic scrambling a lot of plans
and partly because last January, nearly a full year ago, ✈✈✈ Galactic Trendsetters ✈✈✈ won
Mystery Hunt and so we’re writing the 2021 hunt. The ramifications
are still being felt and will accelerate until it actually happens two
weeks from now, and that’s all I’ll say about it here.
Advent of Code (briefly,
“AoC”) is a series of 25 festive programming puzzles1
released daily December 1–25. Each puzzle has two parts, which use the
same text input and are related; to solve a part, you submit the right
output corresponding to the input on the website.
If you’re reading this, I suspect there’s a good chance you knew that
already, but in case you’re new to Advent of Code, let me try to briefly
explain why I like Advent of Code, from the perspective of somebody
who’s spent a lot of their life so far doing programming competitions.2
The event has a fantastic community surrounding it. I’m the most
familiar with the
subreddit, which is full of helpful people, interesting discussions,
non-programming community games, and the occasional wonderfully,
spectacularlyoverengineeredsolution
to a puzzle; but I know there are also many smaller chatrooms and
subcommunities focused on, say, specific timezones or programming
languages.
Another aspect is the unique two-part format of each puzzle. Even
though they use the same input, you don’t get to see the second part
until after you’ve solved the first one, a feature that Eric Wastl
(AoC’s creator) has taken full advantage of in designing puzzles. The
second part is often a surprising twist on the first part, which keeps
you on your toes and challenges you to keep your code moderately general
or refactorable in a way that I think almost no other programming
challenges do. This sometimes even happens between days in a calendar,
when a puzzle turns out to be about some model of computation you
implemented two or five or ten days ago — hope you kept your code and
remember how it works!
Finally, AoC also has some non-rigorous puzzles that force you to
use your intuition and “human intelligence”, either by interpreting the
problem statement heuristically or writing code to let you explore the
input. There are quite a few puzzles where it’s infeasible to write code
that handles every step of obtaining the output from the input. The
result is that Advent of Code can feature quite a few challenges that
I’ve found particularly compelling because I think they simply could not
be posed on any other contest platform.3
These are the things that make AoC stand out to me, but it also does
a lot of other things well — the challenges are fun, approachable, and
varied even aside from their interrelations; there is a long, dramatic
story tying everything together (although it’s an Excuse
Plot if there ever was such a thing); and, although this is
obviously subjective, I find the website’s minimalist-adjacent,
terminal-esque aesthetic really charming (there is a lot of
detail in 2019’s calendar…
after you solve everything). I’ve only done the last two years of Advent
of Code, but it really seems like a one-of-a-kind event to me.
Anyway, one particular feature Advent of Code has is a leaderboard,
which you can get on by being one of the first 100 people worldwide to
solve each puzzle. The competition is fierce — every year, thousands of
people compete to get on the leaderboard. Near the start of AoC 2019, mcpower
(reddit
discussion) and Kevin
Yap (reddit
discussion) wrote some articles about how to do this, both of which
are worth reading. I also thought about writing such an article and
started a draft, but I didn’t get it anywhere close to publishable
before AoC had concluded, at which point I assumed few people would be
interested. But here it is now.
By a strange quirk of fate, I have started writing C++ for a
living.
Learning C++ was about as complicated as I think I expected it to be.
By line count, I’ve written a lot of C++ for programming competitions,
but I knew that I had only ever used a small cross-section of the
language: basic control flow and variables, STL containers and
algorithms, structs on which you mechanically define
bool operator<(const T& other) const so STL
algorithms can order them, and the very occasional macro or templated
helper function. There were many features I wasn’t even aware
existed.
In the process of learning C++ professionally, one rabbit hole I fell
into quickly was C++11’s defining feature, the rvalue
reference, and how it can be used to implement move
semantics and perfect forwarding. By poring over a copy of
the widely recommended book Effective
Modern C++, by Scott Meyers, and a few dozen StackOverflow
answers and blog posts, I roughly understood it after a few days, but
still had a sort of blind-men-feeling-the-elephant feeling. I was
confused about what lay under some of the abstractions I had been using,
unsure of the full shape of the pitfalls that some of the guides had
pointed out to me, and generally uncomfortable that there were still
many small variations of the code I had seen that I couldn’t predict the
behavior of. It took many more days to work myself out of there, and I
wished I had had a guide that explained rvalue references and their
applications to a bit more depth than what might be necessary for
day-to-day use. So here’s my attempt to explain rvalue references in my
own fundamental I-want-to-know-how-things-work-no-really
style.
(If this vision doesn’t resonate with you, there are many other posts
explaining rvalue references out there that you might prefer. Feel free
to just skim the executive summary and/or check out some of the linked
articles in the Background section.)
Executive Summary
I got… pretty carried away when writing this post, and a lot of it is
just for my own understanding, which may or may not be useful to
readers. Here’s a much more concise rundown (assuming you know basic C++
already):