Are the set of all Bitcoin addresses a context-sensitive language?

Question

This started with me trying to make a regex to accept Bitcoin addresses. However, I couldn't do it. That led me to think: "is the set of all possible Bitcoin addresses even a regular language"?

For simplicity, consider only "legacy" P2PKH Bitcoin addresses: a valid address consists of the character "1" followed by 25 to 33 Base58 (123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz) symbols. There is an additional constraint that the last 32 bits of the address are a checksum which equals the first 32 bits of the result of the double SHA-256 hash of the rest of the address.

Obviously, the set of Bitcoin addresses under this definition is a regular language because it is finite, although this is probably no solace to anyone who wants to write a regex to validate it! But it's more interesting to think about Bitcoin addresses of unbounded length. I believe this is not a regular language, and the pumping lemma for regular languages can be used to prove that, nor is it a context-free language, once again because of the pumping lemma (for context-free languages), although I'm not as certain because I didn't take the actual time to think of a proof of this. It's also obvious that this new language of Bitcoin addresses of up to any length is recursively-enumerable and recursive, as it's trivial to write some C code to validate strings in it and also generate strings for it.

Now, the question that I am unable to answer is this: is the set of Bitcoin addresses with up to any length a context-sensitive language?

Forgive me if this is a question with an obvious answer; I only learned this stuff last term :)

Answer 1

Any answer I give you is likely to be unsatisfying and a little silly, both because we're squarely in theory-land here (and not the useful kind of theory, but theory that is irrelevant in practice), but also because of an oddity of the SHA256 hash: the SHA256 hash was not designed to hash messages that are longer than $2^{64}$ bits long. The SHA256 spec is not 100% clear (and I can't blame the authors, as it's ridiculous to imagine hashing such long messages), but it appears that the hash is not defined for longer messages, so Bitcoin addresses longer than that are not well-defined.

As a result of this oddity, arguably this language is finite: because it seems to suggest that Bitcoin addresses have an upper limit on their length, there are only finitely many valid addresses, so it is regular by definition. This is silly and useless in practice because the number, while finite, is so ridiculously large that you'd never want to recognize it using a DFA or regular expression.

But what if we let that bit of silliness go, and assume that SHA256 is well-defined for longer messages? Well, then we have to decide how to hash messages longer than $2^{64}$ bits, which is not something the SHA256 spec describes. The spec says that we append the length of the message, expressed in a 64-bit word. So what should we do if the length is longer than $2^{64}$? Perhaps we use the length modulo $2^{64}$ (even though there is nothing in the spec saying to do that)? In that case, the language is regular, since SHA256 can be computed in a streaming way with a finite amount of space, so you can check membership in this language with a finite-state automaton. In general, if you can check membership using $O(1)$ space, the language is regular, and that would apply here. But that would be purely theoretical, because the finite-state automaton would have a humongous number of states, so you'd never want to compute it using a regular expression.

What if we invent a different variant of SHA256 that appends the length, but not limiting it to a 64-bit word? In that scenario the language would be almost certainly not regular, as counting the length is something you can't do with a finite-state automaton. Yes, it would be certainly context-sensitive: you can check membership using $O(n)$ space, where $n$ is the length of the address (in fact $O(\log n)$ space suffices, as all we need is to keep track of the length), which means it can be recognized by a linear bounded automaton (LBA), hence it is context-sensitive.

At risk of stating the obvious: In practice, all of this is irrelevant (as I suspect you are already aware). Language theory is not the right tool to recognize Bitcoin addresses. Instead, parse them, and then check whether the SHA256 hash is correct.