Bech32 is still awesome.Unfortunately, the great dream of a forward-compatible address format
hit a snag with Segwit v1; nonetheless, it has been taken as an opportunity to make Bech32’s error detection even better.
Bech32's checksum algorithm was designed to be strong against substitution errors, but it also provides some protection against more general classes of errors. The final constant M that is XOR'ed into the checksum influences that protection. BIP173 today uses M=1, but it is now known that this has a weakness: if the final character is a "p", any number of "q" characters can be inserted or erased right before it, without invalidating the checksum.
As it was recognized that other constants do not have this issue, the obvious question is whether this is the only possible type of weakness, and if not, if there is an optimal constant to use that minimizes the largest number of weaknesses.
Since my last mail I've realized that it is actually possible to analyse the behavior of these final constants under a wide variety of error classes (substitutions, deletions, insertions, swaps, duplications) programatically. Greg Maxwell and I have used this to perform an exhaustive analysis of certain error patterns for all 2^30 possible M values, selected a number of criteria to optimize for, and conclude that we should use as constant:
M = 0x2bc830a3
The code used to do this analysis, as well as the code used to verify some expected properties of the final result, and more, can be found on
https://gist.github.com/sipa/14c248c288c3880a3b191f978a34508eSee results_final.txt to see how this constant compares with the previously suggested constants 1, 0x3fffffff, and 0x3fefffff.
See the above-linked gist for more technical information.
A new BIP is forthcoming.Note: This has no practical effect whatsoever on the bc1q... Bech32 addresses that you are using today. Those addresses are fine. It is only a potential problem for the forthcoming Taproot upgrade, or for use of Bech32 with other protocols.This has little effect on the security of P2WPKH/P2WSH addresses, as those are only valid (per BIP173) for specific lengths (42 and 62 characters respectively). Inserting 20 consecutive "p"s in a typo seems highly improbable.
Understatement.
The problem is little enough that it seems the balance against forward compatibility was tipped by a cold, cruel fact:
Implementers are idiots! :-/I disagreed with Rusty previously and he proposed we check to see how disruptive an address format change would be by seeing how many wallets already provide forward compatibility and how many would need to be updated for taproot no matter what address format is used. I think that instead is a good criteria for making a decision.
I understand the results of that survey to be that only two wallets correctly handled v1+ BIP173 addresses. One of those wallets is Bitcoin Core, which I personally believe will unhesitatingly update to a new address format that's technically sound and which has widespread support (doubly so if it's just a tweak to an already-implemented checksum algorithm).
Given that, I also now agree with changing the checksum for v1+.
For thoughtful, forward-compatible design to be
useful, implementers need to
implement the standard correctly.
It is not merely an
implementation problem: It is an
implementer problem. Too many implementers are simpletons who monkey-paste and cargo-cult
bad code, just to push out the door some semi-functional bugware that they can spam naïve users into using. Why should the architects of a system make the effort to provide an elegant design, if almost
nobody implements it correctly?
Developers, please get it right with Segwit v1: Implement address handling correctly, so that the users of your software will have forward-compatible, correct-to-spec handling of future Segwit v2, v3, v14... addresses without upgrading. This will allow early adopters to start using the new version immediately, without the chicken-and-egg network-effect problem. Thank you.This makes nullius cry:
I think these results really show there is no reason to try to maintain the old-software-can-send-to-future-segwit-versions property, given that more than one not just didn't support it, but actually sent coins into a black hole.
😿 🤬Let's look at the behavior of different classes of software/services that exist today when trying to send to v1+ addresses:
(A) Supports sending to v1+ today
* Old proposal: works, but subject to bech32 insertion issue
* New proposal: fails
(B) Fails to send to v1+ today
* Old proposal: fails
* New proposal: fails
(C) Incorrectly sends to v1+ today
* Old proposal: lost funds
* New proposal: fails
Please, I want someday to enjoy the pleasure of a major Bitcoin upgrade
without needing to keep multiple wallets so that I can receive money from users of old software.
I think that I am not the only one who would enjoy that.
With Segwit v0, we needed a huge push to educate users. Now, we need
another push to educate users—and a push to educate developers, such that we should not need to repeat the same push every time the witness version gets a bump.
References for those who want to know what happened here:
- Jonathan Knowles, 2019-05-28, sipa/bech32#51: bug report
- Pieter Wuille, 2019-11-07, [bitcoin-dev] Bech32 weakness and impact on bip-taproot addresses
- Pieter Wuille, 2019-11-22, Bech32 insertion analysis
- Russell O'Connor, 2020-07-15, [bitcoin-dev] Bech32 weakness and impact on bip-taproot addresses
- Rusty Russell, 2020-10-08, [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173)
- Pieter Wuille (as quoted above), 2020-12-05, [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173) (gist with analysis source code and data)
Local rules (recently updated).