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 (264.4 work). At 22 characters, it would be assumed computationally infeasible for anyone (2128.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 268.0 work, and 27 characters needs 2131.2.
- In bech32(m) addresses: every character except the first 4 requires 32 times more work from the attacker. Around 13 characters here means 265 work, and 26 for 2130. 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).