Month: February 2022

Who still uses cash?

PNRJ current events, macroeconomics, public policy , , , , , , , , , , ,

Feb 27 JDN 2459638

If you had to guess, what is the most common denomination of US dollar bills? You might check your wallet: $1? $20?

No, it’s actually $100. There are 13.1 billion $1 bills, 11.7 billion $20 bills, and 16.4 billion $100 bills. And since $100 bills are worth more, the vast majority of US dollar value in circulation is in those $100 bills—indeed, $1.64 trillion of the total $2.05 trillion cash supply.

This is… odd, to say the least. When’s the last time you spent a $100 bill? Then again, when’s the last time you spent… cash? In a typical week, 30% of Americans use no cash at all.

In the United States, cash is used for 26% of transactions, compared to 28% for debit card and 23% for credit cards. The US is actually a relatively cash-heavy country by First World standards. In the Netherlands and Scandinavia, cash is almost unheard of. When I last visited Amsterdam a couple of months ago, businesses were more likely to take US credit cards than they were to take cash euros.

A list of countries most reliant on cash shows mostly very poor countries, like Chad, Angola, and Burkina Faso. But even in Sub-Saharan Africa, mobile money is dominant in Botswana, Kenya and Uganda.

And yet the cash money supply is still quite large: $2.05 trillion is only a third of the US monetary base, but it’s still a huge amount of money. If most people aren’t using it, who is? And why is so much of it in the form of $100 bills?

It turns out that the answer to the second question can provide an answer to the first. $100 bills are not widely used for consumer purchases—indeed, most businesses won’t even accept them. (Honestly that has always bothered me: What exactly does “legal tender” mean, if you’re allowed to categorically refuse $100 bills? It’d be one thing to say “we can’t accept payment when we can’t make change”, and obviously nobody seriously expects you to accept $10,000 bills; but what if you have a $97 purchase?) When people spend cash, it’s mainly ones, fives, and twenties.

Who uses $100 bills? People who want to store money in a way that is anonymous, easily transportable—including across borders—and stable against market fluctuations. Drug dealers leap to mind (and indeed the money-laundering that HSBC did for drug cartels was largely in the form of thick stacks of $100 bills). Of course it isn’t just drug dealers, or even just illegal transactions, but it is mostly people who want to cross borders. 80% of US $100 bills are in circulation outside the United States. Since 80% of US cash is in the form of $100 bills, this means that nearly two-thirds of all US dollars are outside the US.

Knowing this, I have to wonder: Why does the Federal Reserve continue printing so many $100 bills? Okay, once they’re out there, it may be hard to get them back. But they do wear out eventually. (In fact, US dollars wear out faster than most currencies, because they are made of linen instead of plastic. Surprisingly, this actually makes them less eco-friendly despite being more biodegradable. Of course, the most eco-friendly method of payment is mobile payments, since their marginal environmental impact is basically zero.) So they could simply stop printing them, and eventually the global supply would dwindle.

They clearly haven’t done this—indeed, there were more $100 bills printed last year than any previous year, increasing the global supply by 2 billion bills, or $200 billion. Why not? Are they trying to keep money flowing for drug dealers? Even if the goal is to substitute for failing currencies in other countries (a somewhat odd, if altruistic, objective), wouldn’t that be more effective with $1 and $5 bills? $100 is a lot of money for people in Chad or Angola! Chad’s per-capita GDP is a staggeringly low $600 per year; that means that a $100 bill to a typical person in Chad would be like me holding onto a $10,000 bill (those exist, technically). Surely they’d prefer $1 bills—which would still feel to them like $100 bills feel to me. Even in middle-income countries, $100 is quite a bit; Ecuador actually uses the US dollar as its main currency, but their per-capita GDP is only $5,600, so $100 to them feels like $1000 to us.

If you want to usefully increase the money supply to stimulate consumer spending, print $20 bills—or just increase some numbers in bank reserve accounts. Printing $100 bills is honestly baffling to me. It seems at best inept, and at worst possibly corrupt—maybe they do want to support drug cartels?

Basic income reconsidered

PNRJ development economics, inequality, politics, public policy , , ,

Feb 20 JDN 2459631

In several previous posts I have sung the praises of universal basic income (though I have also tried to acknowledge the challenges involved).

In this post I’d like to take a step back and reconsider the question of whether basic income is really the best approach after all. One nagging thought keeps coming back to me, and it is the fact that basic income is extremely expensive.

About 11% of the US population lives below the standard poverty line. There are many criticisms of the standard poverty line: Some say it’s too high, because you can compare it favorably with middle-class incomes in much poorer countries. Others say it’s too low, because income at that level doesn’t allow people to really live in financial security. There are many difficult judgment calls that go into devising a poverty threshold, and we can reasonably debate whether the right ones were made here.

However, I think this threshold is at least approximately correct; maybe the true poverty threshold for a household of 1 should be not $12,880 but $11,000 or $15,000, but I don’t think it should be $5,000 or $25,000. Maybe for a household of 4 it should be not $26,500 but $19,000 or $32,000; but I don’t think it should be $12,000 or $40,000.

So let’s suppose that we wanted to implement a universal basic income in the United States that would lift everyone out of poverty. We could essentially do that by taking the 2-person-household threshold of $17,420 and dividing it by 2, yielding $8,710 per person per year. (Why not use the 1-person-household threshold? There aren’t very many 1-person households in poverty, and that threshold would be considerably higher and thus considerably more expensive. A typical poor household is a single parent and one or more children; as long as kids get the basic income, that household would be above the threshold in this system.)

The US population is currently about 331 million people. If every single one of them were to receive a basic income of $8,710, that would cost nearly $2.9 trillion per year. This is a feasible amount—it’s less than half the current total federal budget—but it is still a very large amount. The tax increases required to support it would be massive, and that’s probably why, despite ostensibly bipartisan support for the idea of a basic income, no serious proposal has ever gotten off of the ground.

If on the other hand we were to only give the basic income to people below the poverty line, that would cost only 11% of that amount: A far more manageable $320 billion per year.

We don’t want to do exactly that, however, because it would create all kinds of harmful distortions in the economy. Consider someone who is just below the threshold, considering whether to take on more work or get a higher-paying job. If their household pre-tax income is currently $15,000 and they could raise it to $18,000, a basic income given only to people below the threshold would mean that they are choosing between $15,000+$17,000=$32,000 if they keep their current work and $18,000 if they increase it. Clearly, they would not want to take on more work. That’s a terrible system—it amounts to a marginal tax rate above 100%.

Another possible method would be to simply top off people’s income, give them whatever they need to get to the poverty line but no more. (This would actually be even cheaper; it would probably cost something more like $160 billion per year.) That removes the distortion for people near the threshold, at the cost of making it much worse for those far below the threshold. Someone considering whether to work for $7,000 or work for $11,000 is, in such a system, choosing whether to work less for $17,000 or work more for… $17,000. They will surely choose to work less.

In order to solve these problems, what we would most likely need to do is gradually phase out the basic income, so that say increasing your pre-tax income by $1.00 would decrease your basic income payment by $0.50. The cost of this system would be somewhere in between that of a truly universal basic income and a threshold-based system, so let’s ballpark that as around $600 billion per year. It would effectively implement a marginal tax rate of 50% for anyone who is receiving basic income payments.

In theory, this is probably worse than a universal basic income, because in the latter case you can target the taxes however you like—and thus (probably) make them less cause less distortion than the phased-out basic income system would. But in practice, a truly universal basic income might simply not be politically viable, and some kind of phased-out system seems much more likely to actually get passed.


Even then, I confess I am not extremely optimistic. For some reason, everyone seems to want to end poverty, but very few seem willing to use the obvious solution: Give poor people money.

The fragility of encryption

PNRJ computer science, mathematical models , , , , , , ,

Feb 13 JDN 2459620

I said in last week’s post that most of the world’s online security rests upon public-key encryption. It’s how we do our shopping, our banking, and paying our taxes.

Yet public-key encryption has an Achilles’ Heel. It relies entirely on the assumption that, even knowing someone’s public key, you can’t possibly figure out what their private key is. Yet obviously the two must be deeply connected: In order for my private key to decrypt all messages that are encrypted using my public key, they must, in a deep sense, contain the same information. There must be a mathematical operation that will translate from one to the other—and that mathematical operation must be invertible.

What we have been relying on to keep public-key encryption secure is the notion of a one-way function: A function that is easy to compute, but hard to invert. A typical example is multiplying two numbers: Multiplication is a basic computing operation that is extremely fast, even for numbers with thousands of digits; but factoring a number into its prime factors is far more difficult, and currently cannot be done in any reasonable amount of time for numbers that are more than a hundred digits long.


“Easy” and “hard” in what sense? The usual criterion is in polynomial time.

Say you have an input that is n bits long—i.e. n digits, when expressed as a binary number, all 0s and 1s. A function that can be computed in time proportional to n is linear time; if it can only be done in time proportional to n2, that is quadratic time; n3 would be cubic time. All of these are examples of polynomial time.

But if instead the time required were 2n, that would be exponential time. 3n and 1.5n would also be exponential time.

This is significant because of how much faster exponential functions grow relative to polynomial functions, for large values of n. For example, let’s compare n3 with2n. When n=3, the polynomial is actually larger: n3=27 but 2n=8. At n=10 they are nearly equal: n3=1000 but 2n=1024. But by n=20, n3 is only 8000 while 2n is over 1 million. At n=100, n3is a manageable (for a modern computer) 1 million, while 2nis a staggering 1030; that’s a million trillion trillion.

You may see that there is already something a bit fishy about this: There are lots of different ways to be polynomial and lots of different ways to be exponential. Linear time n is clearly fast, and for many types of problems it seems unlikely one could do any better. But is n100 time really all that fast? It’s still polynomial. It doesn’t take a large exponential base to make for very fast growth—2 doesn’t seem that big, after all, and when dealing with binary digits it shows up quite naturally. But while 2n grows very fast even for reasonably-sized n, 1.0000001n grows slower than most polynomials—even linear!—for quite a long range before eventually becoming very fast growth when n is in the hundreds of millions. Yet it is still exponential.


So, why do we use these categories? Well, computer scientists and mathematicians have discovered that many types of problems that seem different can in fact be translated into one another, so that solving one would solve the other. For instance, you can easily convert between the Boolean satisfiability problem and the subset-sum problem or the travelling salesman problem. These conversions always take time that is a polynomial in n(usually somewhere between linear and quadratic, as it turns out). This has allowed to build complexity classes, classes of problem such that any problem can be converted to any other in polynomial time or better.

Problems that can be solved in polynomial timeare in class P, for polynomial.

Problems that can be checked—but not necessarily solved—in polynomial time are in class NP, which actually stands for “non-deterministic polynomial” (not a great name, to be honest). Given a problem in NP, you may not be able to come up with a valid answer in polynomial time. But if someone gave you an answer, you could tell in polynomial time whether or not that answer was valid.

Boolean satisfiability (often abbreviated SAT) is the paradigmatic NP problem: Given a Boolean formula like (A OR B OR C) AND (¬A OR D OR E) AND (¬D OR ¬C OR B) and so on, it isn’t a simple task to determine if there’s some assignment of the variables A, B, C, D, E that makes it all true. But if someone handed you such an assignment, say (¬A, B, ¬C, D, E), you could easily check that it does in fact satisfy the expression. It turns out that in fact SAT is what’s called NP-complete: Any NP problem can be converted into SAT in polynomial time.

This is important because in order to be useful as an encryption system, we need our one-way function to be in class P (otherwise, we couldn’t compute it quickly). Yet, by definition, this means its inverse must be in class NP.


Thus, simply because it is easy to multiply two numbers, I know for sure that factoring numbers must be in NP: All I have to do to verify that a factorization is correct is multiply the numbers. Since the way to get a public key from a private key is (essentially) to multiply two numbers, this means that getting a private key from a public key is equivalent to factorization—which means it must be in NP.

This would be fine if we knew some problems in NP that could never, ever be solved in polynomial time. We could just pick one of those and make it the basis of our encryption system. Yet in fact, we do not know any such problems—indeed, we are not even certain they exist.

One of the biggest unsolved problems in mathematics is P versus NP, which asks the seemingly-simple question: “Are P and NP really different classes?” It certainly seems like they are—there are problems like multiplying numbers, or even finding out whether a number is prime, that are clearly in P, and there are other problems, like SAT, that are definitely in NP but seem to not be in P. But in fact no one has ever been able to prove that P ≠ NP. Despite decades of attempts, no one has managed it.

To be clear, no one has managed to prove that P = NP, either. (Doing either one would win you a Clay Millennium Prize.) But since the conventional wisdom among most mathematicians is that P ≠ NP (99% of experts polled in 2019 agreed), I actually think this possibility has not been as thoroughly considered.

Vague heuristic arguments are often advanced for why P ≠ NP, such as this one by Scott Aaronson: “If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found.”

That really doesn’t follow at all. Doing something in polynomial time is not the same thing as doing it instantly.

Say for instance someone finds an algorithm to solve SAT in n6 time. Such an algorithm would conclusively prove P = NP. n6; that’s a polynomial, all right. But it’s a big polynomial. The time required to check a SAT solution is linear in the number of terms in the Boolean formula—just check each one, see if it works. But if it turns out we could generate such a solution in time proportional to the sixth power of the number of terms, that would still mean it’s a lot easier to check than it is to solve. A lot easier.

I guess if your notion of a “fundamental gap” rests upon the polynomial/exponential distinction, you could say that’s not “fundamental”. But this is a weird notion to say the least. If n = 1 million can be checked in 1 million processor cycles (that is, milliseconds, or with some overhead, seconds), but only solved in 1036 processor cycles (that is, over a million trillion years), that sounds like a pretty big difference to me.

Even an n2 algorithm wouldn’t show there’s no difference. The difference between n and n2, is, well, a factor of n. So finding the answer could still take far longer than verifying it. This would be worrisome for encryption, however: Even a million times as long isn’t really that great actually. It means that if something would work in a few seconds for an ordinary computer (the timescale we want for our online shopping and banking), then, say, the Russian government with a supercomputer a thousand times better could spend half an hour on it. That’s… a problem. I guess if breaking our encryption was only feasible for superpower national intelligence agencies, it wouldn’t be a complete disaster. (Indeed, many people suspect that the NSA and FSB have already broken most of our encryption, and I wouldn’t be surprised to learn that’s true.)

But what I really want to say here is that since it may be true that P=NP—we don’t know it isn’t, even if most people strongly suspect as much—we should be trying to find methods of encryption that would remain secure even if that turns out to be the case. (There’s another reason as well: Quantum computers are known to be able to factor numbers in polynomial time—though it may be awhile before they get good enough to do so usefully.)

We do know two such methods, as a matter of fact. There is quantum encryption, which, like most things quantum, is very esoteric and hard to explain. (Maybe I’ll get to that in another post.) It also requires sophisticated, expensive hardware that most people are unlikely to be able to get.

And then there is onetime pad encryption, which is shockingly easy to explain and can be implemented on any home computer.

The problem with substitution ciphers is that you can look for patterns. You can do this because the key ultimately contains only so much information, based on how long it is. If the key contains 100 bits and the message contains 10,000 bits, at some point you’re going to have to repeat some kind of pattern—even if it’s a very complex, sophisticated one like the Enigma machine.

Well, what if the key were as long as the message? What if a 10,000 bit message used a 10,000 bit key? Then you could substitute every single letter for a different symbol each time. What if, on its first occurrence, E is D, but then it’s Q, and then it’s T—and each of these was generated randomly and independently each time? Then it can’t be broken by searching for patterns—because there are no patterns to be found.

Mathematically, it would look like this: Take each bit of the plaintext, and randomly generate another bit for the key. Add the key bit to the plaintext bit (technically you want to use bitwise XOR, but that’s basically adding), and you’ve got the ciphertext bit. At the other end, subtracting out each key bit will give back each plaintext bit. Provided you can generate random numbers efficiently, this will be fast to encrypt and decrypt—but literally impossible to break without the key.

Indeed, onetime-pad encryption is so secure that it is a proven mathematical theorem that there is no way to break it. Even if you had such staggering computing power that you could try every possible key, you wouldn’t even know when you got the right one—because every possible message can be generated from a given ciphertext, using some key. Even if you knew some parts of the message already, you would have no way to figure out any of the rest—because there are no patterns linking the two.

The downside is that you need to somehow send the keys. As I said in last week’s post, if you have a safe way to send the key, why can’t you send the message that way? Well, there is still an advantage, actually, and that’s speed.

If there is a slow, secure way to send information (e.g. deliver it physically by armed courier), and a fast, insecure way (e.g. send it over the Internet), then you can send the keys in advance by the slow, safe way and then send ciphertexts later the fast, risky way. Indeed, this kind of courier-based onetime-pad encryption is how the “red phone” (really a fax line) linking the White House to the Kremlin works.

Now, for online banking, we’re not going to be able to use couriers. But here’s something we could do. When you open a bank account, the bank could give you a, say, 128 GB flash drive of onetime-pad keys for you to use in your online banking. You plug that into your computer every time you want to log in, and it grabs the next part of key each time (there are some tricky technical details with synchronizing this that could, in practice, create some risk—but, done right, the risk would be small). If you are sending 10 megabytes of encrypted data each time (and that’s surely enough to encode a bank statement, though they might want to use a format other than PDF), you’ll get over 10,000 uses out of that flash drive. If you’ve been sending a lot of data and your key starts to run low, you can physically show up at the bank branch and get a new one.

Similarly, you could have onetime-pad keys on flash drives (more literal flash keys)given to you by the US government for tax filing, and another from each of your credit card issuers. For online purchases, the sellers would probably need to have their own onetime-pad keys set up with the banks and credit card companies, so that you send the info to VISA encrypted one way and they send it to the seller encrypted another way. Businesses with large sales volume would go through keys very quickly—but then, they can afford to keep buying new flash drives. Since each transaction should only take a few kilobytes, the cost of additional onetime-pad should be small compared to the cost of packing, shipping, and the items themselves. For larger purchases, business could even get in the habit of sending you a free flash key with each purchase so that future purchases are easier.

This would render paywalls very difficult to implement, but good riddance. Cryptocurrency would die, but even better riddance.It would be most inconvenient to deal with things like, well, writing a blog like this; needing to get a physical key from WordPress sounds like quite a hassle. People might actually just tolerate having their blogs hacked on occasion, because… who is going to hack your blog, and who really cares if your blog gets hacked?

Yes, this system is awkward and inconvenient compared to our current system. But unlike our current system, it is provably secure. Right now, it may seem like a remote possibility that someone would find an algorithm to prove P=NP and break encryption. But it could definitely happen, and if it did happen, it could happen quite suddenly. It would be far better to prepare for the worst than be unprepared when it’s too late.

The importance of encryption

PNRJ computer science , , , , , ,

Feb 6 JDN 2459617

In last week’s post I told you of the compounding failures of cryptocurrency, which largely follow from the fact that it is very bad at being, well, currency. It doesn’t have a steady, predictable value, it isn’t easy to make payments with, and it isn’t accepted for most purchases.

But I realized that I haven’t ever gotten around to explaining anything about the crypto side of things—just what is encryption, and why does it matter?

At its core, encryption is any technique designed to disguise information so that it can be seen only by its intended viewers. Humans have been using some form of encryption since shortly after we invented writing—though, like any technology, our encryption has greatly improved over time.

Encryption involves converting a plaintext, the information you want to keep secret, into a ciphertext, a disguised form, using a key that is kept secret and can be used to convert the ciphertext back into plaintext. Decryption is the opposite process, extracting the plaintext from the ciphertext.

Some of the first forms of encryption were simple substitution ciphers: Have a set of rules that substitutes different letters for the original letters, such as “A becomes D, B becomes Q” and so on. This works pretty well, actually; but if each letter in the ciphertext always corresponds to the same letter in the plaintext, then you can look for patterns that would show up in text. For instance, E is usually the most common letter, so if you see a lot of three-letter sequences like BFP and P is a really common letter, odds are good that BFP is really THE and so you can guess that B=T, F=H, P=E.

More sophisticated ciphers tried to solve this problem by changing the substitution pattern as they go. The Enigma used by Nazi Germany was essentially this: It had a complex electrical and mechanical apparatus dedicated to changing the substitution rules with each key-press, in a manner that would be unpredictable to an outside observer but could be readily reproduced by using another Enigma machine. (Of course, it wasn’t actually as secure as they thought.)

For most of history, people have used what’s called private-key encryption, where there is a single key using for both encryption and decryption. In that case, you need to keep the key secret: If someone were to get their hands on it, they could easily decrypt all of your messages.

This is a problem, because with private-key encryption, you need to give the key to the person you want to read the message. And if there is a safe way to send the key, well… why couldn’t you send the message that way?

In the late 20th century mathematicians figured out an alternative, public-key encryption, which uses two keys: A private key, used to decrypt, and a new, public key, which can be used to encrypt. The public key is called “public” because you don’t need to keep it secret. You can hand it out to anyone, and they can encrypt messages with it. Those messages will be readable by you and you alone—for only you have the private key.

With most methods of public-key encryption, senders can even use their private key to prove to you that they are the person who sent the message, known as authentication. They encrypt it using their private key and your public key, and then you decrypt it using their public key and your private key.

This is great! It means that anyone can send messages to anyone else, and everyone will know not only that their information is safe, but also who it came from. You never have to transmit the private keys at all. Problem solved.


We now use public-key encryption for all sorts of things, particularly online: Online shopping, online banking, online tax filing. It’s not hard to imagine how catastrophic it could be if all of these forms of encryption were to suddenly fail.

In next week’s post, I’m going to talk about why I’m worried that something like that could one day happen, and what we might do in order to make sure it doesn’t. Stay tuned.