I am interested in generating a Bitcoin address by hand for security's sake. After I choose/generate a private key, how do I generate the public key?
From there, how would I double check my work?
Essentially, I am interested in not exposing my private key to any hardware, including my own.
Please feel free to give technical answers, if necessary. Thank you for reading thus far!
I've spent a fair bit of time thinking about this and can provide a fairly comprehensive answer about the state of the art. But unfortunately the TL;DR is that we don't know how to do this (yet) in fewer than many months of full-time tedious computation, where checking your work is a similar amount of time. Near the bottom of this post there is a bold paragraph with specific numbers, which have a lot of hand-waving in them but I think represent the right order of magnitude.
"Not exposing your private key to any hardware" is a fairly common and understandable goal. And there are some operations that (it turns out) are totally reasonable to do by hand. In particular, you can do Shamir Secret Sharing and compute certain checksums by hand. (See codex32 and BIP 93 for more information on these. See seedxor for a simpler approach that does not include checksumming. For random number generation there are a variety of "diceware" schemes for extracting data from dice rolls.)
Working with an 128-bit seed, in my experience it takes 5-10 minutes to do very simple operations (adding seeds together character-by-character, or multiplying them by fixed Lagrange multipliers during secret sharing) and 30-60 minutes to do more complex ones (computing or verifying BCH checksums).
However, what the above schemes all have in common is that they are able to break seed data down into a sequence of characters, and then do computations on them character-by-character. This means that the operations involve tediously repeating steps which are easy to describe and master, and easy to assist via lookup tables and paper computers.
codex32/bip93, by having a checksum, allows you to check all your by-hand work by filling in a "checksum worksheet" on your results. You can even zero in on the exact location of your mistakes doing this. (To check your work on the checksum worksheets themselves, you have to redo them.)
Okay. So if you are merely trying to store your seed and verify its integrity, this is "easy" and you can follow the links I provided to see how to do it. But there are two harder things that you want to do:
For step 1, in 2014 Ken Shirrif famously started to compute a sha256 by hand and estimated that it would take him 1.5 days of continuous work to do the full double-sha256 needed for mining. It would be a comparable amount of work to do a BIP32 derivation. Fortunately, if all you want are HD keys, I think a chacha20-based approach could be devised which is would probably take around 4 hours. Though if you follow that link, you'll see there are lots of missing details here; this is just an extrapolation from some simpler computations, and since even 4 hours per key is pretty brutal, people want to find a better scheme before they put too much time into playing with this.
Unlike with secret sharing and related schemes, there isn't any checksum that will be preserved when doing sha2 or chacha20. So to check your work on this, you'll have to redo the entire computation.
For step 2, secret to public key derivation things get interesting. As you may or may not know, this single operation is sufficient to derive addresses (prior to Taproot, you would also need to compute at least one hash, but with Taproot you can pretty-much just use a key as an address) (plus a checksum, but it's a BCH code so you can use the bip93 process to compute that by hand). It's also sufficient to compute signatures (the hard part of producing a Taproot/Schnorr signature is an EC multiplication; there is also a field multiplication and field addition, but as we'll see, if you can do an EC mult, you've necessarily figured out how to do this).
So to answer your "how do I check my work when doing an EC mult" question, the answer is: you compute a signature with your derived public key. Signatures are public so you can use a computer to check it. You will also want to use a computer to compute the message hash[*]. In fact, Bitcoin Core does this when it derives addresses: it signs a dummy message with every key and verifies it, to make sure that nothing glitched in its key derivation logic.
Okay, so, what's involved in a secret key to public key derivation? Essentially, what you do is interpret your secret key as an integer $n$, take a special elliptic curve (EC) point called G, and compute n × G which is defined as G added to itself n times. And "added to" means the elliptic curve group operation which is a ratio of polynomials. These polynomials are in a field of order 2^256 - 2^32 - 977, so every addition and multiplication involves manipulating 256-bit numbers modulo a large prime.
Maaaaybe you could express an EC multiplication in a way that didn't look like a series of polynomials over this field. But if you discovered such a thing I suspect you'd have solved the discrete log problem, in which case this entire discussion is moot. So I'll assume for the rest of this answer that we're stuck in the "polynomials in a finite field" paradigm. I'll further assume that division in a finite field will be very slow, at least ten times as slow as multiplication, in which case you want to represent your points in "Jacobian coordinates", which is a special coordinate system in which your points are represented by 3 numbers rather than 2, and where you can always replace divisions by (a couple of) multiplications. I don't have a good citation for Jacobian coordinates; they are not the same as "Jacobi coordinates" that Google will find for you. As far as I'm aware, they're used heavily in the field of computing elliptic curve math, and pretty-much unused everywhere else.
This is the same paradigm as electronic computers have to work in, so we actually know how to do the minimum number of field operations for each EC group operation. The answer is 6-16 field multiplications, depending on how "compatible" the points you're combining are (whether their third coordinates match (good), or are one (better)).
Putting this all together, there are three main strategies for efficiently doing EC mults:
For step 1, again assuming no discrete-log-breaking levels of novel math, the only way to reduce the number of group operations is to introduce lookup tables. When computing $G$ plus itself $n$ times, obviously we're not going to actually do $n$-many additions. That would be ~2^255 additions. Instead, we would represent $n$ is base-16, say, so that we have a simpler equation that looks like
n_0 + n_1×(2^4)G + n_2×(2^8)G + n_3×(2^12)G + ... + n_63×(2^252)G
For each term there are only 16 possibilties; these don't overlap so you'll be adding from a set of size 16×64 = 1024. So if you had a lookup table with 1024 entries, you could do this in 64 multiplications. Rather than using base 16, you might use base 1024; then you'd have to do 26 additions from a lookup table of size 26×1024 = 26624.
I was able to fit 18 per page in my "table of discrete logarithms", which I put together in 2018 or so, then thinking it was a joke; I wasted a lot of space, but you can tell that it'd be hard to readably get more than 64 on a page, as a simple estimate. So let's say 64 per page. Then 26624 entries is a 416-page tome. There are diminishing returns to trying to go further and I think this line of analysis is pretty much complete.
For step 2, reducing the number of field operations, we observe from the EFD page I linked above that we can reduce the number of operations we have to do by choosing the points that we're adding carefully. Since even addition will have one point from the lookup table, we can make sure that all the points in the lookup table have z=1; if we need to work in Fourier space or in Montgomery form, we can also do those conversions in the lookup table rather than making the user do them by hand[**]. Just with z=1 we can reduce every EC operation to 11 multiplications.
Peter Dettman has a scheme called "effective affine" which could be used to treat other points as having z=1 even if they don't, but it's not obviously applicable to this.
Step 3 has the most room for exploration in my view, because here is where the hand-computation story really diverges from the electronic-computation story, and we can no longer depend on existing research to get turnkey best-in-class algorithms.
Let's start working things out in detail. We'll assume that we're working in base-32 and that our field elements consist of 52 bech32 "digits" in this base. The benefit of working in this base is that we can do digit multiplication and addition using 1024-element volvelles which are a particularly error-resistant form of lookup table. If we used a lower base, we'd be doing extra work, and with a higher base, the volvelles would be too big. Though maybe there is room to fudge this.
Addition modulo a 256-bit prime will involve 52 digit additions, then another 52 to reduce. Because additions for computers are basically free, I don't have easy-at-hand estimates for the number of additions we have to do per point, but let's say 10 as a swag. So 1040 operations.
We then have to do 11 field multiplications. Naively multiplying two 52-digit numbers involves 2704 digit operations. But with Karatsuba multiplication we can reduce this to around 1500 (if I'm remembering right). With Fourier transform techniques we could reduce this to more-like 52 operations, but every few multiplications we'd need to move out of Fourier space, an operation which costs 10000s of digit operations. I don't have a good estimate of how often you have to do this; it could be anywhere from "you have to do it so frequently this is useless" to "so infrequently that this is a massive win".
Unfortunately these algorithms are for integer multiplication, and we want to do modular multiplication. Naively this would be horrible and involve Euclid's algorithm and dozens of digit divisions and stuff. But non-naively we can use Montgomery multiplication to do this, which roughly adds the overhead of multiplying each digit by a fixed precomputed factor. The digits in the precomp table we could pre-multiply so this is free. For the other digits, we'll also assume this is free, because multiplication by a fixed constant can be done very cheaply using lookup tables, and I haven't yet thought through the details.
A few people have explored combining Montgomery multiplication with Karatsuba-like techniques or even Fourier techniques. Unfortunately the Karatsuba stuff turns out not to be worth the overhead until you get to numbers a fair bit bigger than 256 bits, and the Fourier stuff not til you're way bigger. So the literature on this is few and far between and is written in weird jargon for weird specific applications like digital signal processing chips, or 1950s-era computers, or whatever. I can feel in my bones that there's some really big result ("big" for people trying to do bitcoin wallets by hand) in here but the limiting agent here is deep study time. I would encourage anyone reading this to get their hands dirty and to open a discussion on the codex32 github repo if they're making progress. There are other more speculative ideas (e.g. using residue number systems and then representing entries in the lookup table as their residue modulo various small primes .... if we could then do multiplication/division modulo small primes, then suddenly digit division becomes just as cheap as digit multiplication, which opens up new avenues) that I haven't seen in the literature but may lead somewhere useful.
Putting this all together, here is where we stand: with a 400-page lookup table, assuming no overhead (keeping track of carries, copying data from line to line, etc) and assuming volvelles for every operation, we can do 26 group operations, totalling 286 field multiplications and 260 field additions, which break down into ~786k digit operations (naively) or ~440k (assuming some Karatsuba-like stuff works). Let's say we can do 5 digit operations per minute. Then even after all this hand-waving we are still looking at 2622 hours of work naively or 1475 hours. At a 40 hour/week this is 65 weeks naively or 36 weeks with the tricks that we're fairly confident about.
In my view, if we could reduce this to one month (160 hours of work) (plus another 160 to verify a signature, if you're doing this to derive addresses), I think this would be a reasonable thing to do for a certain kind of super-paranoid Bitcoin user who only transacted every several years. Perhaps you could operate a cold wallet this way, and teach your children and grandchildren to do it, and over the centuries it wouldn't add up to too much trouble. I'm also skeptical that we could do better than this, given that it's already ~16x faster than what we currently know how to do. Though given the magnitude of the unknowns here, I wouldn't be shocked if we could.
However, in my view, no matter how crazy paranoid you are, this is not realistic with current techniques, even for a very-long-term cold wallet.
[*] If you're super serious about avoiding trust in electronic computers, you may be upset about signing hashes that a computer makes for you. After all, the computer could lie about what the hash is, thereby tricking you into signing a transaction you don't intend to. To deal with this, I would advise asking multiple computers to make the same hash, and maybe even do it on a TI-84 or a Gameboy or something which long predates Bitcoin. You could compute the hashes by hand but this is many tens of hours of work.
[**] Maybe you are worried that the computations done in the lookup table may be wrong or compromised. Well, unless you are willing to make your own lookup table tome, which will take you many decades doing monk-like work in a secret location, you will need to live with this. There's more I could say about this but I am trying to keep this answer focused.
I’m one of the folks that’s interested in the Residue Number System angle of attack here. RNS already has a long history of helping making cryptographic functions more efficient for computers, just search “RNS CRYPTOGRAPHY” on google scholar. The reason why they are so attractive both for computers and for humans to handle large arithmetic operations is that they completely dispense with carrying operations.
What this means in practice is that each “digit column” of your operation may be done entirely in parallel. RNS works based of something called the Chinese Remainder Theorem, which proves that if you take any set of coprime integers (integers that share no common factors other than the 1), which we’ll call our “Moduli Set”, then every integer between 1 and the product of our Moduli Set has a unique representation by its set of remainders after being divided by each of our Moduli Set.
Example:
Moduli Set = 2,3,5 product = 30
1 = 1,1,1
2 = 0,2,2
3 = 1,0,3
4 = 0,1,4
5 = 1,2,0
…
30 = 0,0,0
31 = 1,1,1
…
You can see here in that example that we can only get up to 30 (2x3x5) before we start to “overflow” our RNS, however for a lot of cryptographic operations we don’t care about these overflows, as they actually serve as a natural method of obfuscating information. If you’re familiar with modular / finite field arithmetic, which is essentially universal in modern cryptographic systems, this is just an example of that.
The difference is that by representing our numbers in an RNS we don’t actually need to bother with doing arithmetic mod 30, we only need to bother with doing it mod 2,3 and 5. (Generally with RNS you want to use “Primorial Numbers”, ie the product of the first n primes, just because that will end up giving you the smallest coprime integers).
As previously stated what makes RNS so cool is that there is no carrying, you only need to do your arithmetic per digit column:
17 = 1,2,2
x 9 = 1,0,4
———————————
153 = 1,0,3
2s column: 1x1=1
3s column: 2x0=0
5s column: 2x4=8=3
For a computer this means they can do these operations in a highly parallel fashion which makes computers happy and for humans it means that we have to deal with MUCH smaller finite fields within which we need to do maths which makes us happy. Going from having to work mod 30 vs mod 5 might not seem like that big a difference. But how about 193 vs 2^256? If we were to build a 2^256 sized RNS then 193 would be the biggest number we’d have to work with.
This is just a high level overview of RNS and why I’m stoked on it potentially leading to hand crypto, but as Andrew mentioned it’s highly speculative whether or not a bridge can be built into the specific applications we are looking for here. If you’re interested there’s a couple papers in particular that initially got me to think that this might be feasible:
http://journals.theired.org/journals/paper/details/5008.html
https://arxiv.org/abs/1801.07561
In the end with this stuff I think you’d still want some kind of slide rule-y type gadget to help you, and if we really want to do this stuff right it probably means we need to invent entirely new cryptography under these human constraints, which is also something I spend a fair amount of time thinking about.
I love the answer by Andrew
It isn’t by hand on a piece of paper, but a spreadsheet with all the calculations visible (no macros or array formulas) that can perform the ECDSA secp256k1 formula for bitcoin’s public key and another set of spreadsheets for other steps (e.g. RIPEMD160 and SHA256, again no array or macros) can deliver a functional public address, and cuts the time down to under an hour to manually convert from a private key to a public key. I built some in excel and you can find the spreadsheets at modulo.network
I suppose could follow the spreadsheet(s) tabs by hand and arrive at the public address but there are over 180 tabs with long division (and I mean long!) that would become tedious. Hence why I like Andrew’s answer.
