Hail 0x2bc830a3! The new Bech32, forward compatibility, and idiotic implementers

[nullius]

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/14c248c288c3880a3b191f978a34508e

See 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?

<blink><size=2²⁵⁶pt>
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.
</size></blink>

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).

[1715700564]

1715700564

[1715700564]

1715700564

[1715700564]

1715700564

[1715700564]

1715700564

[Carlton Banks]

in light of these new developments, I'm looking for clarification about sig-agg using (future) witness v1 inputs:

The following mailing list thread suggests that any future witness versions would use a new address format: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-December/018298.html

Can we assume from this that signature-aggregation (which includes cross-input aggregation the way I read it...) will not be possible using witness v1 inputs (i.e. 1st gen schnorr inputs), assuming that the changes discussed on the bitcoin-dev mailing list come to be? It seems to me that not just the signing/verifying code needs changing to make aggregation work.

it would be a shame if witness v2 (or possibly higher?) addresses were necessary for sig-agg, but I also get gmaxwell's point from the linked thread about trying to be expedient with packages of soft-fork upgrades. It's possible that v1 will mostly get used for opening and closing channels, which would certainly still be a big win of course. Other uses are possible, but I would argue unlikely to take off in the medium term (I'd love to be proved wrong, naturally)

[achow101]

Using multiple wallet to verify SegWit signed message address already annoying, i'd rather not backup and remember password for multiple wallets.

You probably would've had to do that anyways for segwit v1 because it's Schnorr signatures and the data available for verification will be fundamentally different. Someone will either come up with yet another hack to make it look like the old signed message format, but it will be fundamentally different. Or we can all push for BIP 322 and actually get a proper signed message format that supports everything.

The reason it is fundamentally different is because segwit v1 addresses will encode the pubkey directly. It is not an address hash. This removes the need to do pubkey recovery (which is actually impossible with BIP 340 Schnorr signatures), but that will also change how the signatures are encoded because there's no need to include the recovery id in the signature. Additionally, the encoding should be changed to avoid users attempting to use a Schnorr signature in an ECDSA verifier.

On a side note, it's mentioned that there are 2 wallet which implement forward compatibility correctly. One of them is Bitcoin Core, but what's the other one?
I tried digging https://bitcoinops.org/ for a bit, but couldn't find relevant information.

https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-October/018258.html has a list. Looks like Purse and River are fully forwards compatible. Brd and Xapo are probably compatible and just need node upgrades in the backend. And edge is mostly compatible but has some issues, also needs node upgrades in the backend.

in light of these new developments, I'm looking for clarification about sig-agg using (future) witness v1 inputs:

The following mailing list thread suggests that any future witness versions would use a new address format: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-December/018298.html

Can we assume from this that signature-aggregation (which includes cross-input aggregation the way I read it...) will not be possible using witness v1 inputs (i.e. 1st gen schnorr inputs), assuming that the changes discussed on the bitcoin-dev mailing list come to be? It seems to me that not just the signing/verifying code needs changing to make aggregation work.

it would be a shame if witness v2 (or possibly higher?) addresses were necessary for sig-agg, but I also get gmaxwell's point from the linked thread about trying to be expedient with packages of soft-fork upgrades. It's possible that v1 will mostly get used for opening and closing channels, which would certainly still be a big win of course. Other uses are possible, but I would argue unlikely to take off in the medium term (I'd love to be proved wrong, naturally)

Signature aggregation has never been part of the segwit v1 proposal and won't ever be. It will require another version of segwit. The changes to support it as a soft fork are far too large and require changes to how transactions are constructed.

[Carlton Banks]

Signature aggregation has never been part of the segwit v1 proposal and won't ever be. It will require another version of segwit. The changes to support it as a soft fork are far too large and require changes to how transactions are constructed.

at least we may set a slightly more convivial precedent with activating BIPs 340-342 in repect of the timeframe, it rather seems as if there's no substantial objections (not that there ever was for the previous soft-fork, depending on one's definition of "substantial"), and a healthy majority of (expected) miner signalling. I'm looking forward to an expedited BIP Sig-Agg

[nullius]

I am also interested in knowing which wallets destroyed funds in tests, instead of just doing nothing.  My educated guess about the cause is that the authors of those wallets did not read this:

Implementations should take special care when converting the address to a scriptPubkey, where witness version n is stored as OP_n. OP_0 is encoded as 0x00, but OP_1 through OP_16 are encoded as 0x51 though 0x60 (81 to 96 in decimal). If a bech32 address is converted to an incorrect scriptPubKey the result will likely be either unspendable or insecure.

Every time an implementer writes code without reading the clearly stated warning in the standard, kittens cry.  😿😿😿  Please do not make kittens cry.  Thank you.

Using multiple wallet to verify SegWit signed message address already annoying, i'd rather not backup and remember password for multiple wallets.

Even for handling transactions, I myself was not able to switch (almost) fully to a Segwit-native, Bech32-addressed wallet for a long time after Segwit activated.  Too many senders told me that I had an “invalid address”.

Wherefore I thank Segwit’s architects for forward-compatible addressing—no thanks to implementers who didn’t implement it.

I'm looking forward to an expedited BIP Sig-Agg

We will need it, to survive in the era of a serious push for transaction-blacklisting, “KYC”-enforcing miner pools which now ride in on greed.  In my opinion, Payjoin-style protocols and massive sig-agg CoinJoins indistinguishable from ordinary transactions will be critical to prevent, or at least reduce the co-option of Bitcoin.

Too bad that every upgrade also partitions anonymity sets, encourages the type of mixed-script transactions that make change identification trivial, creates design problems for privacy services (as I am currently contemplating), and necessitates special-casing to avoid mixed-script transactions in protocols such as BIP 78 (Payjoin).

Once we get some critical upgrades such as Taproot and future sig agg, I would prefer to see fewer, less-frequent changes on L1.  Let’s not use up those Witness versions too fast...

On a side note, it's mentioned that there are 2 wallet which implement forward compatibility correctly. One of them is Bitcoin Core, but what's the other one?
I tried digging https://bitcoinops.org/ for a bit, but couldn't find relevant information.

https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-October/018258.html has a list. Looks like Purse and River are fully forwards compatible. Brd and Xapo are probably compatible and just need node upgrades in the backend. And edge is mostly compatible but has some issues, also needs node upgrades in the backend.

Have these any of these tests examined the functionality of developer-level implementations, such as libwally?  As to libwally specifically, I have a high regard for its authors, and I expect for it to DTRT; but if it were forward-compatible, then several different wallets should have been forward-compatible.  I see that in the October tests, Blockstream Green (libwally’s flagship consumer) is listed as not forward-compatible (“Fails on validation of the address.”).  Time to dig into the code...

A better question:  Are the test vectors (or better, a full test suite) used for these wallet tests publicly available?  I may talk big about reading the standard; but if I were to develop something (probably just using libwally under the hood), then I should test its functionality before foisting it on others.

Thanks.

[pooya87]

I am also interested in knowing which wallets destroyed funds in tests, instead of just doing nothing.  My educated guess about the cause is that the authors of those wallets did not read this:

Considering the fact that is no defined witness version apart from version zero in the protocol yet any coins send to random version 1+ witness scripts are most probably already unspendable regardless of the correct usage of OP codes in the pubkey scripts.
Not to mention that all the existing bitcoin core versions <=0.20.1 are rejecting witness versions >= 1 as "non-standard" there is no way to burn actual funds for developers. Not to mention that tests are performed on testnet not on mainnet.

[nullius]

I was wrong (and pooya87’s post was completely wrong).  Updating this.

This mainnet transaction apparently burnt 0.00009815 BTC with Green—which may answer my question about libwally (though I do not see an issue for this? which I would have noticed anyway...):
http://explorerzydxu5ecjrkwceayqybizmpjjznk5izmitf2modhcusuqlid.onion/tx/ef1662fd2eb736612afb1b60e3efabfdf700b1c4822733d9dbe1bfee607a5b9b

This mainnet transaction apparently burnt 0.00000546 BTC (dust limit) with Blockchain.com:
http://explorerzydxu5ecjrkwceayqybizmpjjznk5izmitf2modhcusuqlid.onion/tx/64b0fcb22d57b3c920fee1a97b9facec5b128d9c895a49c7d321292fb4156c21

This mainnet transaction successfully sent 0.00003656 BTC to bc1pmfr3p9j00pfxjh0zmgp99y8zftmd3s5pmedqhyptwy6lm87hf5ss52r5n8:
http://explorerzydxu5ecjrkwceayqybizmpjjznk5izmitf2modhcusuqlid.onion/tx/b48a59fa9e036e997ba733904f631b1a64f5274be646698e49fd542141ca9404

Reference:  I somehow missed this message last month, and should probably update OP with it after some more poking around here:

Well I sure picked a bad couple weeks to volunteer to send a bunch of Bitcoin test transactions...

While I tested less than I would have liked, there are some notable results:

- Green wallet segwit v1 send resulted in funds being sent to the wrong address (bc1qmfr3p9j00pfxjh0zmgp99y8zftmd3s5pmedqhyptwy6lm87hf5sstpn3we instead of my intended destination, Pieter's r5n8 address. You can see this with Rusty's test transaction as well:
ef1662fd2eb736612afb1b60e3efabfdf700b1c4822733d9dbe1bfee607a5b9b Blockstream is aware of the issue and has fixes.
- Blockchain.com's wallet behaved similarly, sending to the same, incorrect address. Rusty's blockchain.com transaction for reference: 64b0fcb22d57b3c920fee1a97b9facec5b128d9c895a49c7d321292fb4156c21 I will be reaching out to Blockchain's team to let them know about this.
- Blockchain.info's explorer suffers similarly, "Unable to decode output address" when viewing a tx with v1 output, and inability to display address details for a v1 address
- Bitgo accepts a v1 send address, but then a “Server error” during send occurs
- Coinbase (web) reported on final step of sending: Your send failed Please enter a valid email or Bitcoin address
- brd sends successfully to v1
- bitrefill, casa, xapo, wasabi, all previously failed address validation, and still fail address validation
- binance, bitmex, kraken, all previously failed address validation, but now accept v1 addresses. I did not attempt full send with these services, simply passing initial validations.
- While Riccardo noted that Aqua successfully sent to Pieter's address (b48a59fa9e036e997ba733904f631b1a64f5274be646698e49fd542141ca9404) Ive been informed Aqua has disabled send to v1 addresses for now.

And that answers my question about which wallets failed.

Unedited post follows.  I will keep updating this as I dig for more information, until somebody replies or I get bored.

I am also interested in knowing which wallets destroyed funds in tests, instead of just doing nothing.  My educated guess about the cause is that the authors of those wallets did not read this:

Considering the fact that is no defined witness version apart from version zero in the protocol yet any coins send to random version 1+ witness scripts are most probably already unspendable regardless of the correct usage of OP codes in the pubkey scripts.
Not to mention that all the existing bitcoin core versions <=0.20.1 are rejecting witness versions >= 1 as "non-standard" there is no way to burn actual funds for developers. Not to mention that tests are performed on testnet not on mainnet.

I think it’s bloody obvious that I was talking about the destruction of testnet coins—and how those unidentified wallets would burn real money, if Witness v1 were deployed on mainnet with BIP 173 addresses.  As I read the discussion on bitcoin-dev, that was the decisive factor for both sipa and harding in their respective agreements to break forward-compatibility.

Did you seriously read my post as a complaint about the destruction of real money, with live v1 transactions?  (Rhetorical question; don’t answer.)

[NotATether]

How are we going to stop this from fragmenting the network, particularly among the nodes and clients that have already implemented segwit v0? We don't want a situation where only three or four clients support v1 after several months and the rest still only recognize v0. We'll probably never be able to get most of the legacy clients (re. exchanges and corporate merchants) to adopt v0 or v1 so let's forget about those.

Using multiple wallet to verify SegWit signed message address already annoying, i'd rather not backup and remember password for multiple wallets.

You probably would've had to do that anyways for segwit v1 because it's Schnorr signatures and the data available for verification will be fundamentally different. Someone will either come up with yet another hack to make it look like the old signed message format, but it will be fundamentally different. Or we can all push for BIP 322 and actually get a proper signed message format that supports everything.

I don't think many people will catch on with using a P2PKH-converted segwit v1 address for message signing, and I haven't seen many people use that for segwit v0 anyway. What can we as developers do to accelerate BIP 322 to be added in Core? I see that the spec is missing reference implementations and test vectors, is there anything else that need to be revised?

It's the only viable way to get all the v0 clients to share a common message signature functionality.