How many characters of an address do I actually need to verify?

Question

Let's assume I want to verify the receive address on the phone. The recipient confirms the first M and last N characters of the address. How big is the computational effort for an attacker to create a valid address that has the same M characters at the beginning and the same N characters at the end?

What would be a safe M/N?

Is it okay if the recipient doesn't mention if a character is upper or lower case?

Answer 1

How big is the computational effort for an attacker to create a valid address that has the same M characters at the beginning and the same N characters at the end?

It depends on what your attack model is.

If you're worried about an attacker replacing your address with another valid address that matches in a number of places, but is not spendable by the attacker (so they'd just be burned funds), this is easy, regardless of how many characters you check. If this is your concern, you should check all of them, except possibly the last 6, as those are only checksum characters. If everything but the checksum matches, the checksum itself will also match.

If you're only concerned about attackers who replace addresses with others they themselves can spend, it is harder.

• In base58 addresses: Every character except the first one makes it 58 times harder for the attacker. Checking any 11 characters would require a nontrivial amount of computation time (2^64.4 work). At 22 characters, it would be assumed computationally infeasible for anyone (2^128.9 work, similar to what cracking a public key itself would need).
  • If you ignore lower/uppercase, every characters only makes it up to 29 times harder for an attacker. Then 14 characters would require 2^68.0 work, and 27 characters needs 2^131.2.
• In bech32(m) addresses: every character except the first 4 requires 32 times more work from the attacker. Around 13 characters here means 2⁶⁵ work, and 26 for 2¹³⁰. Bech32 addresses are case insensitive.

Note that these computations assume the attacker knows which characters you'll be looking at, which is perhaps the case if you're always going to pick the N first and M last to compare. If you compare random ones, it is significantly harder for attackers, but the computation would depend on the exact strategy used.

For reference, base58 addresses for Bitcoin mainnet start with 1... (P2PKH) or 3... (P2SH). bech32 addresses start with bc1q... (P2WPKH or P2WSH) or bc1p... (P2TR).

Answer 2

How big is the computational effort for an attacker to create a valid address that has the same M characters at the beginning and the same N characters at the end?

It's pretty easy to make addresses with are visually similar to one another, here only targeting the start of the address but there's no particular reason why it couldn't target the end as well.

18eXmgR5Svoqqa6PaYVrKvbH6hvrp5xe3A  
18eXmgR5Svoqqa6JXSMmbNaD4Cs5ThcV1P

These examples for P2PKH are both valid, and used bitcoin keys that share 20 characters. They would have taken a number of hours to produce on today's CPUs, which isn't particularly an issue in any attack scenario.

Is it okay if the recipient doesn't mention if a character is upper or lower case?

Lowercase and uppercase are different addresses in p2pkh addresses, so it weakens any partial cross validation. For newer bech32 addresses capitalization is irrelevant and simply doesn't matter.