* [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173)
@ 2020-10-08 0:21 Rusty Russell
2020-10-08 14:59 ` David A. Harding
2020-10-28 0:20 ` Pieter Wuille
0 siblings, 2 replies; 24+ messages in thread
From: Rusty Russell @ 2020-10-08 0:21 UTC (permalink / raw)
To: Bitcoin Protocol Discussion
Hi all,
I propose an alternative to length restrictions suggested by
Russell in https://github.com/bitcoin/bips/pull/945: use the
https://gist.github.com/sipa/a9845b37c1b298a7301c33a04090b2eb variant,
unless the first byte is 0.
Here's a summary of each proposal:
Length restrictions (future segwits must be 10, 13, 16, 20, 23, 26, 29,
32, 36, or 40 bytes)
1. Backwards compatible for v1 etc; old code it still works.
2. Restricts future segwit versions, may require new encoding if we
want a diff length (or waste chainspace if we need to have a padded
version for compat).
Checksum change based on first byte:
1. Backwards incompatible for v1 etc; only succeeds 1 in a billion.
2. Weakens guarantees against typos in first two data-part letters to
1 in a billion.[1]
I prefer the second because it forces upgrades, since it breaks so
clearly. And unfortunately we do need to upgrade, because the length
extension bug means it's unwise to accept non-v0 addresses.
(Note non-v0 segwit didn't relay before v0.19.0 anyway, so many places
may already be restricting to v0 segwit).
The sooner a decision is reached on this, the sooner we can begin
upgrading software for a taproot world.
Thanks,
Rusty.
PS. Lightning uses bech32 over longer lengths, but the checksum is less critical; we'd prefer to follow whatever
bitcoin chooses.
[1] Technically less for non-v0: you have a 1 in 8 chance of a typo in the second letter changing the checksum
algorithm, so it's 1 in 8 billion.
^ permalink raw reply [flat|nested] 24+ messages in thread* Re: [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173) 2020-10-08 0:21 [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173) Rusty Russell @ 2020-10-08 14:59 ` David A. Harding 2020-10-08 15:21 ` Russell O'Connor 2020-10-15 1:40 ` Rusty Russell 2020-10-28 0:20 ` Pieter Wuille 1 sibling, 2 replies; 24+ messages in thread From: David A. Harding @ 2020-10-08 14:59 UTC (permalink / raw) To: Rusty Russell, Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 2148 bytes --] On Thu, Oct 08, 2020 at 10:51:10AM +1030, Rusty Russell via bitcoin-dev wrote: > Hi all, > > I propose an alternative to length restrictions suggested by > Russell in https://github.com/bitcoin/bips/pull/945 : use the > https://gist.github.com/sipa/a9845b37c1b298a7301c33a04090b2eb variant, > unless the first byte is 0. > > Here's a summary of each proposal: > > Length restrictions (future segwits must be 10, 13, 16, 20, 23, 26, 29, > 32, 36, or 40 bytes) > 1. Backwards compatible for v1 etc; old code it still works. > 2. Restricts future segwit versions, may require new encoding if we > want a diff length (or waste chainspace if we need to have a padded > version for compat). > > Checksum change based on first byte: > 1. Backwards incompatible for v1 etc; only succeeds 1 in a billion. > 2. Weakens guarantees against typos in first two data-part letters to > 1 in a billion.[1] Excellent summary! > I prefer the second because it forces upgrades, since it breaks so > clearly. And unfortunately we do need to upgrade, because the length > extension bug means it's unwise to accept non-v0 addresses. I don't think the second option forces upgrades. It just creates another opt-in address format that means we'll spend another several years with every wallet having two address buttons, one for a "segwit address" (v0) and one for a "taproot address" (v1). Or maybe three buttons, with the third being a "taproot-in-a-segwit-address" (v1 witness program using the original bech32 encoding). It took a lot of community effort to get widespread support for bech32 addresses. Rather than go through that again, I'd prefer we use the backwards compatible proposal from BIPs PR#945 and, if we want to maximize safety, consensus restrict v1 witness program size, e.g. reject transactions with scriptPubKeys paying v1 witness programs that aren't exactly 32 bytes. Hopefully by the time we want to use segwit v2, most software will have implemented length limits and so we won't need any additional consensus restrictions from then on forward. -Dave [-- Attachment #2: signature.asc --] [-- Type: application/pgp-signature, Size: 833 bytes --] ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173) 2020-10-08 14:59 ` David A. Harding @ 2020-10-08 15:21 ` Russell O'Connor 2020-10-15 1:40 ` Rusty Russell 1 sibling, 0 replies; 24+ messages in thread From: Russell O'Connor @ 2020-10-08 15:21 UTC (permalink / raw) To: David A. Harding, Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 780 bytes --] On Thu, Oct 8, 2020 at 11:00 AM David A. Harding via bitcoin-dev < bitcoin-dev@lists•linuxfoundation.org> wrote: > Rather than go through that again, I'd prefer we use the > backwards compatible proposal from BIPs PR#945 and, if we want to > maximize safety, consensus restrict v1 witness program size, e.g. reject > transactions with scriptPubKeys paying v1 witness programs that aren't > exactly 32 bytes. > Adding some kind of relay policy rule would be easier than a consensus rule, and maybe effective enough. (This comment is not intended to endorse any one proposal over another.) > Hopefully by the time we want to use segwit v2, most software will have > implemented length limits and so we won't need any additional consensus > restrictions from then on forward. > [-- Attachment #2: Type: text/html, Size: 1284 bytes --] ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173) 2020-10-08 14:59 ` David A. Harding 2020-10-08 15:21 ` Russell O'Connor @ 2020-10-15 1:40 ` Rusty Russell 2020-10-16 21:09 ` Pieter Wuille 1 sibling, 1 reply; 24+ messages in thread From: Rusty Russell @ 2020-10-15 1:40 UTC (permalink / raw) To: David A. Harding, Bitcoin Protocol Discussion "David A. Harding" <dave@dtrt•org> writes: > On Thu, Oct 08, 2020 at 10:51:10AM +1030, Rusty Russell via bitcoin-dev wrote: >> Hi all, >> >> I propose an alternative to length restrictions suggested by >> Russell in https://github.com/bitcoin/bips/pull/945 : use the >> https://gist.github.com/sipa/a9845b37c1b298a7301c33a04090b2eb variant, >> unless the first byte is 0. >> >> Here's a summary of each proposal: >> >> Length restrictions (future segwits must be 10, 13, 16, 20, 23, 26, 29, >> 32, 36, or 40 bytes) >> 1. Backwards compatible for v1 etc; old code it still works. >> 2. Restricts future segwit versions, may require new encoding if we >> want a diff length (or waste chainspace if we need to have a padded >> version for compat). >> >> Checksum change based on first byte: >> 1. Backwards incompatible for v1 etc; only succeeds 1 in a billion. >> 2. Weakens guarantees against typos in first two data-part letters to >> 1 in a billion.[1] > > Excellent summary! > >> I prefer the second because it forces upgrades, since it breaks so >> clearly. And unfortunately we do need to upgrade, because the length >> extension bug means it's unwise to accept non-v0 addresses. > > I don't think the second option forces upgrades. It just creates > another opt-in address format that means we'll spend another several > years with every wallet having two address buttons, one for a "segwit > address" (v0) and one for a "taproot address" (v1). Or maybe three > buttons, with the third being a "taproot-in-a-segwit-address" (v1 > witness program using the original bech32 encoding). If we go for option 2, v1 (generated from bitcoin core) will simply fail the first time you try test it. So it will force an upgrade. There are fewer places generating addresses than accepting them, so this seems the most likely scenario. OTOH, with option 1, anyone accepting v1 addresses today is going to become a liability once v1 addresses start being generated. > It took a lot of community effort to get widespread support for bech32 > addresses. Rather than go through that again, I'd prefer we use the > backwards compatible proposal from BIPs PR#945 and, if we want to > maximize safety, consensus restrict v1 witness program size, e.g. reject > transactions with scriptPubKeys paying v1 witness programs that aren't > exactly 32 bytes. Yes, I too wish we weren't here. :( Deferring a hard decision is not useful unless we expect things to be easier in future, and I only see it getting harder as time passes and userbases grow. The good news it that the change is fairly simple and the reference implementations are widely used so change is not actually that hard once the decision is made. > Hopefully by the time we want to use segwit v2, most software will have > implemented length limits and so we won't need any additional consensus > restrictions from then on forward. If we are prepared to commit to restrictions on future addresses. We don't know enough to do that, however, so I'm reluctant; I worry that a future scheme where we could save (e.g.) 2 bytes will impractical due to our encoding restrictions, resulting in unnecessary onchain bloat. Cheers, Rusty. ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173) 2020-10-15 1:40 ` Rusty Russell @ 2020-10-16 21:09 ` Pieter Wuille 2020-10-19 0:49 ` Rusty Russell 0 siblings, 1 reply; 24+ messages in thread From: Pieter Wuille @ 2020-10-16 21:09 UTC (permalink / raw) To: Rusty Russell, Bitcoin Protocol Discussion Hi Rusty, thanks for starting this thread. We definitely should make a decision around this soon. On Wednesday, October 14, 2020 6:40 PM, Rusty Russell via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote: > > > Here's a summary of each proposal: > > > Length restrictions (future segwits must be 10, 13, 16, 20, 23, 26, 29, > > > 32, 36, or 40 bytes) > > > > > > 1. Backwards compatible for v1 etc; old code it still works. > > > 2. Restricts future segwit versions, may require new encoding if we > > > want a diff length (or waste chainspace if we need to have a padded > > > version for compat). > > > > > > Checksum change based on first byte: > > > > > > 1. Backwards incompatible for v1 etc; only succeeds 1 in a billion. > > > 2. Weakens guarantees against typos in first two data-part letters to > > > 1 in a billion.[1] > > > > If we go for option 2, v1 (generated from bitcoin core) will simply fail > the first time you try test it. So it will force an upgrade. There > are fewer places generating addresses than accepting them, so this > seems the most likely scenario. > > OTOH, with option 1, anyone accepting v1 addresses today is going to > become a liability once v1 addresses start being generated. Today, no witness v1 receivers exist. So it seems to me the only question is what software/infrastructure exist that supports sending to witness v1, and whether they (and their userbase) are more or less likely to upgrade before receivers appear than those that don't. Clearly if only actively developed software currently supports sending to v1 right now, then the question of forward compatibility is moot, and I'd agree the cleanliness of option 2 is preferable. Does anyone have an up-to-date overview of where to-future-witness sending is supported? I know Bitcoin Core does. > > It took a lot of community effort to get widespread support for bech32 > > addresses. Rather than go through that again, I'd prefer we use the > > backwards compatible proposal from BIPs PR#945 and, if we want to > > maximize safety, consensus restrict v1 witness program size, e.g. reject > > transactions with scriptPubKeys paying v1 witness programs that aren't > > exactly 32 bytes. > > Yes, I too wish we weren't here. :( > > Deferring a hard decision is not useful unless we expect things to be > easier in future, and I only see it getting harder as time passes and > userbases grow. Possibly, but in the past I think there has existed a pattern where adoption of new technology is at least partially based on certain infrastructure and codebases going out of business and/or being replaced with newer ones, rather than improvements to existing ones. If that effect is significant, option 1 may be preferable: it means less compatibility issues in the short term, and longer term all that may be required is fixing the spec, and waiting long enough for old/unmaintained code to be replaced. As for how long: new witness version/length combinations are only rarely needed, and there are 14 length=32 ones left to pick. We'll likely want to use those first anyway, as it's the cheapest option with 128-bit collision resistance. Assuming future constructions have something like BIP341's leaf versioning, new witness version/length combinations are only required for: * Changes to the commitment structure of script execution (e.g. Graftroot, different hash function for Merkle trees, ...) * Upgrades to new signing cryptography (EC curve change, PQC, ...). * Changes to signatures outside of a commitment structure (e.g. new sighash modes for the keypath in BIP341, or cross-input aggregation for them). and in general, not for things like new script opcodes, or even for fairly invasive redesigns of the script language itself. > The good news it that the change is fairly simple and the reference > implementations are widely used so change is not actually that hard > once the decision is made. Indeed. Whatever observations we had about adoption of base58 -> bech32 may not apply because the change to a different checksum is fairly trivial compared to that. Still, presence of production codebases that just don't update at all may complicate this. > > Hopefully by the time we want to use segwit v2, most software will have > > implemented length limits and so we won't need any additional consensus > > restrictions from then on forward. > > If we are prepared to commit to restrictions on future addresses. > > We don't know enough to do that, however, so I'm reluctant; I worry that > a future scheme where we could save (e.g.) 2 bytes will impractical due > to our encoding restrictions, resulting in unnecessary onchain bloat. I'm opposed to consensus-invalidating certain length/version combinations, if that's what you're suggesting, and I don't think there is a need for it. TL;DR: what codebases/services/infrastructure exists today that supports sending to witness v1 BIP173 addresses? Cheers, -- Pieter ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173) 2020-10-16 21:09 ` Pieter Wuille @ 2020-10-19 0:49 ` Rusty Russell 2020-10-19 22:55 ` Pieter Wuille 2020-10-21 3:05 ` ZmnSCPxj 0 siblings, 2 replies; 24+ messages in thread From: Rusty Russell @ 2020-10-19 0:49 UTC (permalink / raw) To: Pieter Wuille, Bitcoin Protocol Discussion; +Cc: John Barboza Pieter Wuille <bitcoin-dev@wuille•net> writes: > Today, no witness v1 receivers exist. So it seems to me the only question > is what software/infrastructure exist that supports sending to witness v1, > and whether they (and their userbase) are more or less likely to upgrade > before receivers appear than those that don't. > > Clearly if only actively developed software currently supports sending to > v1 right now, then the question of forward compatibility is moot, and I'd > agree the cleanliness of option 2 is preferable. If software supports v1 today and doesn't get upgraded, and we persue option 1 then a trailing typo can make trouble. Not directly lose money (since the tx won't get propagated), but for most systems (e.g. hosted wallets) someone has to go in and figure out the error and fix it up. Option 2 means they're likely to fix their systems the first time someone tries a v1 send, not the first time someone makes a trailing typo (which might be years). > Does anyone have an up-to-date overview of where to-future-witness sending > is supported? I know Bitcoin Core does. Anecdata: c-lightning doesn't allow withdraw to segwit > 0. It seems that the contributor John Barboza (CC'd) assumed that future versions should be invalid: if (bip173) { bool witness_ok = false; if (witness_version == 0 && (witness_program_len == 20 || witness_program_len == 32)) { witness_ok = true; } /* Insert other witness versions here. */ >> Deferring a hard decision is not useful unless we expect things to be >> easier in future, and I only see it getting harder as time passes and >> userbases grow. > > Possibly, but in the past I think there has existed a pattern where adoption > of new technology is at least partially based on certain infrastructure > and codebases going out of business and/or being replaced with newer ones, > rather than improvements to existing ones. > > If that effect is significant, option 1 may be preferable: it means less > compatibility issues in the short term, and longer term all that may be > required is fixing the spec, and waiting long enough for old/unmaintained code > to be replaced. Hmm, I'd rather cleanly break zombie infra, since they're exactly the kind that won't/cant fix the case where someone trailing-typos? > As for how long: new witness version/length combinations are only rarely needed, > and there are 14 length=32 ones left to pick. We'll likely want to use those > first anyway, as it's the cheapest option with 128-bit collision resistance. > Assuming future constructions have something like BIP341's leaf versioning, new > witness version/length combinations are only required for: > > * Changes to the commitment structure of script execution (e.g. Graftroot, > different hash function for Merkle trees, ...) > * Upgrades to new signing cryptography (EC curve change, PQC, ...). > * Changes to signatures outside of a commitment structure (e.g. new sighash > modes for the keypath in BIP341, or cross-input aggregation for them). > > and in general, not for things like new script opcodes, or even for fairly > invasive redesigns of the script language itself. Hmm, good point. These can all be done with version bumps. The only use for extra bytes I can see is per-UTXO flags, but even then I can't see why you'd need to know them until their spent (in which case you stash the flag in the input, not the output). And fewer bytes seems bad for fungibility, since multisig would be dangerous. But the future keeps surprising me, so I'm still hesitant. >> The good news it that the change is fairly simple and the reference >> implementations are widely used so change is not actually that hard >> once the decision is made. > > Indeed. Whatever observations we had about adoption of base58 -> bech32 may not > apply because the change to a different checksum is fairly trivial compared to > that. Still, presence of production codebases that just don't update at all > may complicate this. > >> > Hopefully by the time we want to use segwit v2, most software will have >> > implemented length limits and so we won't need any additional consensus >> > restrictions from then on forward. >> >> If we are prepared to commit to restrictions on future addresses. >> >> We don't know enough to do that, however, so I'm reluctant; I worry that >> a future scheme where we could save (e.g.) 2 bytes will impractical due >> to our encoding restrictions, resulting in unnecessary onchain bloat. > > I'm opposed to consensus-invalidating certain length/version combinations, if > that's what you're suggesting, and I don't think there is a need for it. This *seems* to leave the option of later removing size restrictions, but I think this is an illusion. Upgrading will only get harder over time: we would instead opt for some kind of backward compatiblity hack (i.e. 33 byte address, but you can optionally add 3 zero pad bytes) which *will* have consensus effect. > TL;DR: what codebases/services/infrastructure exists today that supports > sending to witness v1 BIP173 addresses? OK, time to waste some money! Can you provide a mainnet v1 address, and I'll try to spam it from as many things as I can find. If we're really lucky, you can collect it post-fork and donate it to charity. Or a miner can steal it pre-fork :) Thanks! Rusty. ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173) 2020-10-19 0:49 ` Rusty Russell @ 2020-10-19 22:55 ` Pieter Wuille 2020-10-20 0:42 ` Rusty Russell 2020-10-21 3:05 ` ZmnSCPxj 1 sibling, 1 reply; 24+ messages in thread From: Pieter Wuille @ 2020-10-19 22:55 UTC (permalink / raw) To: Rusty Russell; +Cc: Bitcoin Protocol Discussion, John Barboza On Sunday, October 18, 2020 5:49 PM, Rusty Russell <rusty@rustcorp•com.au> wrote: > Pieter Wuille bitcoin-dev@wuille•net writes: > > > Today, no witness v1 receivers exist. So it seems to me the only question > > is what software/infrastructure exist that supports sending to witness v1, > > and whether they (and their userbase) are more or less likely to upgrade > > before receivers appear than those that don't. > > Clearly if only actively developed software currently supports sending to > > v1 right now, then the question of forward compatibility is moot, and I'd > > agree the cleanliness of option 2 is preferable. > > If software supports v1 today and doesn't get upgraded, and we persue > option 1 then a trailing typo can make trouble. Not directly lose money > (since the tx won't get propagated), but for most systems (e.g. hosted > wallets) someone has to go in and figure out the error and fix it up. It depends. As is, they'd be relayed even as sending to future witness versions or lengths is standard. If option 1 is chosen there may be reasons to add safeguards using relay policy, though. > Option 2 means they're likely to fix their systems the first time > someone tries a v1 send, not the first time someone makes a trailing > typo (which might be years). Possibly, but it's also possible that it won't get fixed at all, and instead receiver software just has to wait a few years longer before being able to start giving out v1 addresses and have a reasonable chance the sender supports it. You're right though that protecting old sender software from being protected against the insertion bug is a good argument in favor of Option 2. Strictly speaking it also has an issue, as the error detection properties aren't guaranteed for new-scheme-address + intended-detected-error interpreted as old-scheme-address (in particular, you can make 4 substitution errors in a new-scheme address and have it be a valid old-scheme address). This is much less of an issue than the insertion bug that remains present with Option 1 in old senders. > > As for how long: new witness version/length combinations are only rarely needed, > > and there are 14 length=32 ones left to pick. We'll likely want to use those > > first anyway, as it's the cheapest option with 128-bit collision resistance. > > Assuming future constructions have something like BIP341's leaf versioning, new > > witness version/length combinations are only required for: > > > > - Changes to the commitment structure of script execution (e.g. Graftroot, > > different hash function for Merkle trees, ...) > > > > - Upgrades to new signing cryptography (EC curve change, PQC, ...). > > - Changes to signatures outside of a commitment structure (e.g. new sighash > > modes for the keypath in BIP341, or cross-input aggregation for them). > > > > > > and in general, not for things like new script opcodes, or even for fairly > > invasive redesigns of the script language itself. > > Hmm, good point. These can all be done with version bumps. > > The only use for extra bytes I can see is per-UTXO flags, but even then > I can't see why you'd need to know them until their spent (in which case > you stash the flag in the input, not the output). > > And fewer bytes seems bad for fungibility, since multisig would be > dangerous. > > But the future keeps surprising me, so I'm still hesitant. Of course, our thinking here may change significantly over time - still, I expect it'll be years before something other than 32-byte addresses is desired. > > TL;DR: what codebases/services/infrastructure exists today that supports > > sending to witness v1 BIP173 addresses? > > OK, time to waste some money! > > Can you provide a mainnet v1 address, and I'll try to spam it from as > many things as I can find. If we're really lucky, you can collect it > post-fork and donate it to charity. Or a miner can steal it pre-fork :) Here is a BIP341 witness v1 address, corresponding to just the generator as inner public key (using TapTweak(pubkey) as tweak, as suggested by the BIP): bc1pmfr3p9 YOU j00pfxjh WILL 0zmgp99y8zf LOSE tmd3s5pmedqhy MONEY ptwy6lm87hf5ss52r5n8 Cheers, -- Pieter ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173) 2020-10-19 22:55 ` Pieter Wuille @ 2020-10-20 0:42 ` Rusty Russell 2020-10-20 3:31 ` Rusty Russell 2020-10-20 10:29 ` David A. Harding 0 siblings, 2 replies; 24+ messages in thread From: Rusty Russell @ 2020-10-20 0:42 UTC (permalink / raw) To: Pieter Wuille; +Cc: Bitcoin Protocol Discussion, John Barboza Pieter Wuille <bitcoin-dev@wuille•net> writes: > Here is a BIP341 witness v1 address, corresponding to just the generator as > inner public key (using TapTweak(pubkey) as tweak, as suggested by the BIP): > > bc1pmfr3p9 YOU j00pfxjh WILL 0zmgp99y8zf LOSE tmd3s5pmedqhy MONEY ptwy6lm87hf5ss52r5n8 Here are my initial results: Rejects ------- c-lightning: "Could not parse destination address, destination should be a valid address" Phoenix: "Invalid data. Please try again." Accepts ------- Green: ef1662fd2eb736612afb1b60e3efabfdf700b1c4822733d9dbe1bfee607a5b9b blockchain.info: 64b0fcb22d57b3c920fee1a97b9facec5b128d9c895a49c7d321292fb4156c21 Will keep exploring (and others are welcome to try too!) Cheers, Rusty. ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173) 2020-10-20 0:42 ` Rusty Russell @ 2020-10-20 3:31 ` Rusty Russell 2020-10-20 9:21 ` Riccardo Casatta 2020-10-20 10:29 ` David A. Harding 1 sibling, 1 reply; 24+ messages in thread From: Rusty Russell @ 2020-10-20 3:31 UTC (permalink / raw) To: Pieter Wuille; +Cc: Bitcoin Protocol Discussion, John Barboza Rusty Russell <rusty@rustcorp•com.au> writes: > Accepts > ------- > Green: ef1662fd2eb736612afb1b60e3efabfdf700b1c4822733d9dbe1bfee607a5b9b > blockchain.info: 64b0fcb22d57b3c920fee1a97b9facec5b128d9c895a49c7d321292fb4156c21 PEBKAC. Pasted wrong address. Here are correct results: Rejects ------- c-lightning: "Could not parse destination address, destination should be a valid address" Phoenix: "Invalid data. Please try again." blockchain.info: "Your Bitcoin transaction failed to send. Please try again." Accepts ------- Green: 9e4ab6617a2983439181a304f0b4647b63f51af08fdd84b0676221beb71a8f21 Cheers, Rusty. ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173) 2020-10-20 3:31 ` Rusty Russell @ 2020-10-20 9:21 ` Riccardo Casatta 0 siblings, 0 replies; 24+ messages in thread From: Riccardo Casatta @ 2020-10-20 9:21 UTC (permalink / raw) To: Rusty Russell, Bitcoin Protocol Discussion; +Cc: John Barboza [-- Attachment #1: Type: text/plain, Size: 1299 bytes --] Here is a mainnet tx done with aqua wallet, which is based on rust-bitcoin https://blockstream.info/tx/b48a59fa9e036e997ba733904f631b1a64f5274be646698e49fd542141ca9404?expand I am not sure about the scriptpubkey starting with 51 so I opened this https://github.com/rust-bitcoin/rust-bitcoin/pull/504 Il giorno mar 20 ott 2020 alle ore 05:32 Rusty Russell via bitcoin-dev < bitcoin-dev@lists•linuxfoundation.org> ha scritto: > > Rusty Russell <rusty@rustcorp•com.au> writes: > > Accepts > > ------- > > Green: ef1662fd2eb736612afb1b60e3efabfdf700b1c4822733d9dbe1bfee607a5b9b > > blockchain.info: 64b0fcb22d57b3c920fee1a97b9facec5b128d9c895a49c7d321292fb4156c21 > > PEBKAC. Pasted wrong address. Here are correct results: > > Rejects > ------- > c-lightning: "Could not parse destination address, destination should be a valid address" > Phoenix: "Invalid data. Please try again." > blockchain.info: "Your Bitcoin transaction failed to send. Please try again." > > Accepts > ------- > Green: 9e4ab6617a2983439181a304f0b4647b63f51af08fdd84b0676221beb71a8f21 > > Cheers, > Rusty. > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev -- Riccardo Casatta - @RCasatta [-- Attachment #2: Type: text/html, Size: 2054 bytes --] ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173) 2020-10-20 0:42 ` Rusty Russell 2020-10-20 3:31 ` Rusty Russell @ 2020-10-20 10:29 ` David A. Harding 2020-10-20 20:12 ` Pieter Wuille 1 sibling, 1 reply; 24+ messages in thread From: David A. Harding @ 2020-10-20 10:29 UTC (permalink / raw) To: Rusty Russell; +Cc: Bitcoin Protocol Discussion, John Barboza [-- Attachment #1: Type: text/plain, Size: 2520 bytes --] On Tue, Oct 20, 2020 at 11:12:06AM +1030, Rusty Russell wrote: > Here are my initial results: A while ago, around the Bitcoin Core 0.19.0 release that enabled relaying v1+ segwit addresses, Mike Schmidt was working on the Optech Compatibility Matrix[1] and tested a variety of software and services with a v1 address using the original BIP341 specification (33 byte pubkeys; we now use 32 byte keys). Here's a summary of his results, posted with his permission: - abra: Bech32 not supported. - binance: Does not pass front end javascript validation - bitgo: Error occurs during sending process, after validation. - bitmex: Bech32 not supported. - bitrefill: Address does not pass validation. - bitstamp: Address text input doesn’t allow bech32 addresses due to character limits. - blockchain.info: Error occurs during sending process, after validation. - brd: Allows sending workflow to complete in the UI. Transaction stays as pending in the transaction list. - casa: Fails on signing attempt. - coinbase: Fails address validation client side in the UI. - conio: Server error 500 while attemping to send. - copay: Allows v1 address to be entered in the UI. Fails during broadcast. - edge: Allows sending workflow to complete. Transaction stays in pending state. Appears to causes issues with the balance calculation as well as ability to send subsequent transactions. - electrum: Error message during broadcasting of transaction. - green: Fails on validation of the address. - jaxx: Fails on validation of the address. - ledger live: Fails when transaction is sent to the hardwave device for signing. - mycelium: Fails during address validation. - purse: Transaction can be created and broadcast, relayed by peers compatible with Bitcoin Core v0.19.0.1 or above. - river: Transaction can be created and broadcast, relayed by peers compatible with Bitcoin Core v0.19.0.1 or above. - samourai: Fails on broadcast of transaction to the network. - trezor: Fails on validation of the address. - wasabi: Fails on validation of the address. - xapo: Xapo allows users to create segwit v1 transactions in the UI. However, the transaction gets stuck as pending for an indeterminate period of time I would guess that some of the failures / stuck transactions might now be successes if the backend infrastructure has upgraded to Bitcoin Core >= 0.19. -Dave [1] https://bitcoinops.org/en/compatibility/ [-- Attachment #2: signature.asc --] [-- Type: application/pgp-signature, Size: 833 bytes --] ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173) 2020-10-20 10:29 ` David A. Harding @ 2020-10-20 20:12 ` Pieter Wuille 2020-10-20 23:52 ` Mike Schmidt 0 siblings, 1 reply; 24+ messages in thread From: Pieter Wuille @ 2020-10-20 20:12 UTC (permalink / raw) To: David A. Harding; +Cc: Bitcoin Protocol Discussion, John Barboza On Tuesday, October 20, 2020 3:29 AM, David A. Harding <dave@dtrt•org> wrote: > I would guess that some of the failures / stuck transactions might now be successes if the backend infrastructure has upgraded to Bitcoin Core > = 0.19. Yeah, it would be good to re-test them since a ~year has passed since the 0.19.0 release. Cheers, -- Pieter ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173) 2020-10-20 20:12 ` Pieter Wuille @ 2020-10-20 23:52 ` Mike Schmidt 2020-10-21 4:51 ` Rusty Russell 2020-11-06 19:49 ` Mike Schmidt 0 siblings, 2 replies; 24+ messages in thread From: Mike Schmidt @ 2020-10-20 23:52 UTC (permalink / raw) To: Bitcoin Protocol Discussion, Pieter Wuille; +Cc: John Barboza [-- Attachment #1: Type: text/plain, Size: 860 bytes --] I am happy to re-test the services Harding listed previously for v1 send support next week. Suggestions of additional services that would be valuable to test are welcome as well. Mike On Tue, Oct 20, 2020 at 3:38 PM Pieter Wuille via bitcoin-dev < bitcoin-dev@lists•linuxfoundation.org> wrote: > On Tuesday, October 20, 2020 3:29 AM, David A. Harding <dave@dtrt•org> > wrote: > > > > I would guess that some of the failures / stuck transactions might now > be successes if the backend infrastructure has upgraded to Bitcoin Core > = > 0.19. > > Yeah, it would be good to re-test them since a ~year has passed since the > 0.19.0 release. > > Cheers, > > -- > Pieter > > > > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > [-- Attachment #2: Type: text/html, Size: 1671 bytes --] ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173) 2020-10-20 23:52 ` Mike Schmidt @ 2020-10-21 4:51 ` Rusty Russell 2020-11-06 19:49 ` Mike Schmidt 1 sibling, 0 replies; 24+ messages in thread From: Rusty Russell @ 2020-10-21 4:51 UTC (permalink / raw) To: Mike Schmidt, Bitcoin Protocol Discussion, Bitcoin Protocol Discussion, Pieter Wuille Cc: John Barboza Mike Schmidt via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> writes: > I am happy to re-test the services Harding listed previously for v1 send > support next week. > > Suggestions of additional services that would be valuable to test are > welcome as well. Thanks! I am a little disappointed that I won't get to ask Bitcoin Twitter to send tips to Pieter[1] though... I would like to hear from the services who currently support v1+ (who thus *would* have to change their software) whether they have a technical preference for option 1 or 2. Cheers, Rusty. [1] Or just maybe, tips to some random miner... ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173) 2020-10-20 23:52 ` Mike Schmidt 2020-10-21 4:51 ` Rusty Russell @ 2020-11-06 19:49 ` Mike Schmidt 2020-12-05 23:10 ` Pieter Wuille 1 sibling, 1 reply; 24+ messages in thread From: Mike Schmidt @ 2020-11-06 19:49 UTC (permalink / raw) To: Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 1755 bytes --] 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. [-- Attachment #2: Type: text/html, Size: 2115 bytes --] ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173) 2020-11-06 19:49 ` Mike Schmidt @ 2020-12-05 23:10 ` Pieter Wuille 2020-12-06 13:04 ` David A. Harding 0 siblings, 1 reply; 24+ messages in thread From: Pieter Wuille @ 2020-12-05 23:10 UTC (permalink / raw) To: Mike Schmidt, Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 1112 bytes --] On Friday, November 6, 2020 11:49 AM, Mike Schmidt via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote: > 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: 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. Thus, I agree with Rusty that we should change the checksum for v1+ unconditionally. That also means that old senders are protected from the insertion issue (by failing, as we can guarantee that new-checksum addresses, even after a few errors, are invalid to old software). I've sent another mail in this thread with details, but the TL;DR is that we should use the constant M=0x2bc830a3 rather than 0x3fffffff as previous suggested. More information on https://gist.github.com/sipa/14c248c288c3880a3b191f978a34508e. Absent objections, I'll write up a BIP soon. Cheers, -- Pieter [-- Attachment #2: Type: text/html, Size: 1605 bytes --] ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173) 2020-12-05 23:10 ` Pieter Wuille @ 2020-12-06 13:04 ` David A. Harding 2020-12-06 20:43 ` Pieter Wuille 2020-12-08 17:39 ` Ryan Grant 0 siblings, 2 replies; 24+ messages in thread From: David A. Harding @ 2020-12-06 13:04 UTC (permalink / raw) To: Pieter Wuille, Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 1427 bytes --] On Sat, Dec 05, 2020 at 11:10:51PM +0000, Pieter Wuille via bitcoin-dev wrote: > 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. I don't think this is a good criteria to use for making a decision. We shouldn't deny users of working implementations the benefit of a feature because some other developers didn't implement it correctly. > Thus, I agree with Rusty that we should change the checksum for v1+ > unconditionally. 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+. Thanks, -Dave [-- Attachment #2: signature.asc --] [-- Type: application/pgp-signature, Size: 833 bytes --] ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173) 2020-12-06 13:04 ` David A. Harding @ 2020-12-06 20:43 ` Pieter Wuille 2020-12-08 17:39 ` Ryan Grant 1 sibling, 0 replies; 24+ messages in thread From: Pieter Wuille @ 2020-12-06 20:43 UTC (permalink / raw) To: David A. Harding; +Cc: Bitcoin Protocol Discussion ‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐ On Sunday, December 6, 2020 5:04 AM, David A. Harding <dave@dtrt•org> wrote: > On Sat, Dec 05, 2020 at 11:10:51PM +0000, Pieter Wuille via bitcoin-dev wrote: > > > 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. > > I don't think this is a good criteria to use for making a decision. We > shouldn't deny users of working implementations the benefit of a feature > because some other developers didn't implement it correctly. > > > Thus, I agree with Rusty that we should change the checksum for v1+ > > unconditionally. > > 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). Hi Dave, You're right to point out there is nuance I skipped over. 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 So the question is how the support for sending to v1+ in (a) software weighs up against protecting both (a) from the insertion issue, and (c) from lost funds. I do think (c) matters in this equation - people may choose to avoid adopting v1+ witnesses if it were to be known that some senders out there would misdirect funds. But the fact that (a) is small also means there is very little to gain from the old proposal. So perhaps I should have formulated it as: the small number of v1+ compatible senders today (regardless of the reasons for that) shows how futile the attempt to have one address type for all witness versions was, and the fact that there are even some who misdirect(ed) funds is the final nail in the coffin. Changing the checksum unconditionally gives us a new attempt at that. > Given that, I also now agree with changing the checksum for v1+. Great. Cheers, -- Pieter ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173) 2020-12-06 13:04 ` David A. Harding 2020-12-06 20:43 ` Pieter Wuille @ 2020-12-08 17:39 ` Ryan Grant 2020-12-18 2:02 ` Pieter Wuille 1 sibling, 1 reply; 24+ messages in thread From: Ryan Grant @ 2020-12-08 17:39 UTC (permalink / raw) To: Bitcoin Protocol Discussion It looks like a good strategy for a bech32 library that is external to Bitcoin Core would be: - Default to the new M, under the same bech32 brand. - Provide an interface to explicitly use both M=1 and M=0x2bc830a3. - If decoding fails, throw an error; but in constructing that error inform whether the other M would have succeeded. - Provide an interface for a BIP173 implementation to peek at the witness version byte of the data part, which may also involve sanity-checking that byte for errors using a BIP173-specific understanding of the appropriate checksum. Return values for this special interface might currently be: "it's version zero, based on a clean decoding", "it's version one, based on a clean decoding", "it's version zero, based on an auto-corrected byte", "it's version one, based on an auto-corrected byte", "no result, due to a decoding error on this byte", and "too many errors to say anything more about decoding". Although the reasoning is clear for doing so, looking into the data that is supposed to be checksummed to determine which checksum to use is not very elegant. There are two trips into a bech32 library for a BIP173 decoding, and an indeterminate result on the version byte would require heuristics for deciding what to do with the rest of the data part to even advise the user on the error. Because of this, as a library writer I would be tempted to auto-correct the witness version byte (against the "SHOULD NOT" advice of BIP173's current version), if it were the only one corrupted, as per the example return values above. Please advise. Some of the libraries that will be contemplating these steps include: https://github.com/topics/bech32?o=desc&s=stars Here are three existing uses of bech32 that are external to Bitcoin Core: https://github.com/lightningnetwork/lightning-rfc/blob/master/11-payment-encoding.md https://github.com/btcontract/lnurl-rfc https://github.com/bitcoin/bips/blob/master/bip-0136.mediawiki Of the above, I think BIP136 can be unconditionally moved to M=0x2bc830a3 due to having little legacy burden. ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173) 2020-12-08 17:39 ` Ryan Grant @ 2020-12-18 2:02 ` Pieter Wuille 0 siblings, 0 replies; 24+ messages in thread From: Pieter Wuille @ 2020-12-18 2:02 UTC (permalink / raw) To: Ryan Grant; +Cc: Bitcoin Protocol Discussion On Tuesday, December 8, 2020 9:39 AM, Ryan Grant <bitcoin-dev@rgrant•org> wrote: > It looks like a good strategy for a bech32 library that is external to > Bitcoin Core would be: > > - Default to the new M, under the same bech32 brand. > - Provide an interface to explicitly use both M=1 and M=0x2bc830a3. > - If decoding fails, throw an error; but in constructing that error > inform whether the other M would have succeeded. > > - Provide an interface for a BIP173 implementation to peek at the > witness version byte of the data part, which may also involve > sanity-checking that byte for errors using a BIP173-specific > understanding of the appropriate checksum. I think there are two possible interfaces that make sense: - Have the caller explicitly specify whether they want bech32 or bech32m (which someone - I think Rusty? - started using in reference to this new code and I'm going to adopt now). - Have the bech32 decoding function return a tristate (failed, valid as bech32, valid as bech32m). No string is ever valid as both, so there is no loss of information here. The former is a bit cleaner, and also the only real choice if error location hinting is desired. The second is more efficient if decoding twice is a performance concern. Cheers, -- Pieter ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173) 2020-10-19 0:49 ` Rusty Russell 2020-10-19 22:55 ` Pieter Wuille @ 2020-10-21 3:05 ` ZmnSCPxj 2020-10-21 4:39 ` Rusty Russell 1 sibling, 1 reply; 24+ messages in thread From: ZmnSCPxj @ 2020-10-21 3:05 UTC (permalink / raw) To: Rusty Russell, Bitcoin Protocol Discussion; +Cc: John Barboza > Anecdata: c-lightning doesn't allow withdraw to segwit > 0. It seems > that the contributor John Barboza (CC'd) assumed that future versions > should be invalid: > > if (bip173) { > bool witness_ok = false; > if (witness_version == 0 && (witness_program_len == 20 || > witness_program_len == 32)) { > witness_ok = true; > } > /* Insert other witness versions here. */ I believe this is actually my code, which was later refactored by John Barboza when we were standardizing the `param` system. This was intended only as a simple precaution against creating non-standard transaction, and not an assumption that future versions should be invalid. The intent is that further `else if` branches would be added for newer witness versions and whatever length restrictions they may have, as the `/* Insert other witness versions here. */` comment implies. Regards, ZmnSCPxj ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173) 2020-10-21 3:05 ` ZmnSCPxj @ 2020-10-21 4:39 ` Rusty Russell 0 siblings, 0 replies; 24+ messages in thread From: Rusty Russell @ 2020-10-21 4:39 UTC (permalink / raw) To: ZmnSCPxj, Bitcoin Protocol Discussion; +Cc: John Barboza ZmnSCPxj <ZmnSCPxj@protonmail•com> writes: > I believe this is actually my code, which was later refactored by John Barboza when we were standardizing the `param` system. Ah, sorry! > This was intended only as a simple precaution against creating non-standard transaction, and not an assumption that future versions should be invalid. > The intent is that further `else if` branches would be added for newer witness versions and whatever length restrictions they may have, as the `/* Insert other witness versions here. */` comment implies. Yes, I mentioned it here because I've found this to be a common misconception; the *idea* was that application's segwit code would not have to be reworked for future upgrades, but that information propagated poorly. (Just as well, because of overly strict standardness rules, the overflow bug, and now the proposed validation changes, turns out this lack of forward compat is a feature!) Thanks! Rusty. ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173) 2020-10-08 0:21 [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173) Rusty Russell 2020-10-08 14:59 ` David A. Harding @ 2020-10-28 0:20 ` Pieter Wuille 2020-12-05 22:59 ` Pieter Wuille 1 sibling, 1 reply; 24+ messages in thread From: Pieter Wuille @ 2020-10-28 0:20 UTC (permalink / raw) To: Rusty Russell, Bitcoin Protocol Discussion On Wednesday, October 7, 2020 5:21 PM, Rusty Russell via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote: > I propose an alternative to length restrictions suggested by > Russell in https://github.com/bitcoin/bips/pull/945: use the > https://gist.github.com/sipa/a9845b37c1b298a7301c33a04090b2eb variant, > unless the first byte is 0. Hi all, starting a slight side-thread here. The discussion here made me realize that as we're introducing (at some point) a new checksum scheme, we don't just care about the new scheme's own error detection capabilities, but also about the probability that a new style address + errors is incorrectly accepted as an old style address. Clearly these properties are less of a priority than just the new-style + error being misinterpreted as a new-style address, as problems will only occur when entering a new address with errors in old software that supports the old scheme (which this thread shows, is not very common). Still, all other things being equal, it can't hurt to see if some choices are better than others. https://gist.github.com/sipa/a9845b37c1b298a7301c33a04090b2eb suggested the use of constant M = 0x3FFFFFFF. It turns out this is slightly suboptimal in two ways: * It's possible to take a new-style address with that constant, make 3 substitution errors, and obtain an old-style address. * If a new-style address ends with '7', inserting 'g78u' just before it will result in a valid old-style address (ignoring length constraints). I don't think either of these is serious, but it's possible to improve upon them: * Guaranteeing that 4 substitution errors are always detected while switching schemes seems impossible, but a constant can be picked that guarantees 3 errors always are. * Insertion/deletion errors can be restricted to patterns that require 6 fixed characters (which, assuming uniformly random characters, implies a probability of 2^-30). It seems M=0x3ffeffff has both these properties. I'm going to do some more analysis (swapping, and insertion/erasure near the start), and then update my gist, but so far it seems this is a strictly (albeit only slightly) better choice. Cheers, -- Pieter ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173) 2020-10-28 0:20 ` Pieter Wuille @ 2020-12-05 22:59 ` Pieter Wuille 0 siblings, 0 replies; 24+ messages in thread From: Pieter Wuille @ 2020-12-05 22:59 UTC (permalink / raw) To: Rusty Russell, Bitcoin Protocol Discussion > On Wednesday, October 7, 2020 5:21 PM, Rusty Russell via bitcoin-dev bitcoin-dev@lists•linuxfoundation.org wrote: > > > I propose an alternative to length restrictions suggested by > > Russell in https://github.com/bitcoin/bips/pull/945: use the > > https://gist.github.com/sipa/a9845b37c1b298a7301c33a04090b2eb variant, > > unless the first byte is 0. > > Hi all, > > starting a slight side-thread here. Another update, and a longer write-up. Introduction ------------ 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. Properties ---------- If we define an error as a deletion of one position, a swap of adjacent positions, a substitution in a specific position with a random character, an insertion of one random character in a specific position, or a duplication of the character in a specific position, then this M constant above gives us the following properties: * For generic HRPs and errors that don't affect the first 6 data characters, or alternatively averaged over all HRPs (see details futher): * Always detected: * (P) Up to 4 substitution errors (true for any constant). * (Q) Any valid code with the new constant, fed without modification to software that uses the old constant 1 (true for any constant). * Any error pattern has failure to detect probability <= 2^-30: * (L) Any number of errors restricted to a single window of up to 4 characters. * (B) Up to two errors restricted to a window of up to 68 characters. * (D) Any one error made to a valid code with the new constant, and fed to software that uses the old constant 1 * Most error patterns have probability <= 2^-30: * (C) Up to two errors in general: out of 23926796 such error patterns, 0.0040% have probability 2^-25. * (N) Up to three errors restricted to a window of up to 69 characters: out of 284708444 such patterns, 0.033% have probability 2^-25. * (O) Up to three errors in general: out of 295744442 such error patterns, 0.034% have probability 2^-25; 0.000065% have probability 2^-20. * (G) Up to two errors made to a valid code with the new constant, and fed to software that uses the old constant 1: out of 2831622 such error patterns, 0.048% have probability 2^-25. * Specifically for the bc1 HRP, with the BIP173 length restrictions: * Always detected: * (R) Up to 4 substitution errors (true for any constant). * (A) Up to 3 substitution errors made to a valid code with the new constant, and fed to software that uses the old constant 1. * Any error pattern has failure to detect probability <= 2^-30: * (E) Any one error. * (F) Any one error made to a valid code with the new constant, and fed to software that uses the old constant 1. * (H) Up to two errors restricted to a window of 28 characters. * Most error patterns have probability <= 2^-30: * (J) Up to two errors in general: out of 455916 such error patterns, 0.039% have probability 2^-25; 0.0053% have 2^-20. * (K) Any number of errors restricted to a window of 4 characters: out of 5813139 such error patterns, 0.0016% have probability 2^-25. * (M) Up to three errors: out of 50713466 such error patterns, 0.078% have probability 2^-25; 0.00063% have 2^-20. * (I) Up to two errors made to a valid code with the new constant, and fed to software that uses the old constant 1: out of 610683 such error patterns, 0.092% have probability 2^-25; 0.00049% have probability 2^-20. To give an idea of what these probabilities mean, consider the known BIP173 insertion issue. It admits an error pattern of 1 error (insertion in penultimate position) that has a failure to detect probability of 2^-10: it requires the final character to be 'p', and the inserted character to be 'q'. Assuming those are both random, we have a chance of 1 in 32*32 to hit it. Note that the choice of *what* the error pattern is (whether it's insertion, and where) isn't part of our probabilities: we try to make sure that *every* pattern behaves well, not just randomly chosen ones, because presumably humans make some kinds of errors more than others, and we don't know which ones. All the analyzed patterns above are guaranteed to be detected with probability 2^-20 or better (and most are 2^-30). Of course, if we'd search for even larger classes of errors, say any 4 independent errors of any type, we would probably discover patterns with worse probabilities, but at that point the probability of the pattern itself being hit should be taken into account. The selection was made based on these same properties: * Start with the set of all 2^30 constants. * The generic properties (L), (B), (D), (C), (N), (O), and (G) were selected for by rejecting all constants that left any worse error patterns (e.g. all codes for which patterns matching (N) existed with failure probability above 2^-25 were removed). All these restrictions are as strong as they can be: making them over longer strings, wider windows, or more errors with the same restrictions removes all remaining constants. This leaves us with just 12054 acceptable constants. * The same was then done for the bc1/BIP173 specific properties (A), (E), (J), (F), (H), (K), (M), and (I). This reduces the set further to 79 acceptable constants. The full analysis output for all of these can be found in output.txt. * Finally, the constant with the minimal number of worst-probability patterns was chosen for the generic property (N). The single constant 0x2bc830a3 remains. * This solution and a few of its expected properties were then validated using a simple program that makes random errors (see the monte_carlo.py file). Technical details ----------------- For the purpose of this analysis, define an "error pattern" as a starting length (of a valid string consisting of otherwise randomly chosen characters) combined with a sequence of the following (in this order): * 0 or more deletions of characters at specific positions (without constraining what those characters are) * 0 or more swaps of characters at specific positions with the character following it * 0 or more substitutions of characters at specific positions with a uniformly randomly selected character * 0 or more insertions of uniformly randomly selected characters at specific positions * 0 or more duplications of characters at specific positions (including duplications of characters inserted/substituted in the previous steps) Examples: * "Start with a random valid 58 character string, remove the 17th character, swap the 11th character with the 12th character, and insert a random character in the 24th position" is an error pattern. * "Replace the 17th through 24th characters in a 78 character string with 'aardvark'" is not an error pattern, because substituted characters have to be random, and can't be specific values. Given such a pattern, assign variable names to every input character, and to every inserted/substituted character. For example, the pattern "Start with a 6 character string, delete the 1st character, swap the 2nd and 3rd character, and insert a random character between those" would be represented as [v0 v1 v2 v3 v4 v5] and [v1 v3 v6 v2 v4 v5]. Treat these variables as elements of GF(32), and write out the equations that both the first and second list have a valid checksum. Due to the fact that BCH codes are linear, this is just a linear set of equations over GF(32), and we can use Gaussian elimination to find the size of the solution space. If the input and output are the same length, we need to subtract the number of solutions for which the input and output are exactly the same, which is easy to find with another set of equations. Now compute the ratio of this number divided by (32^numvars / 32^6), where the 32^6 is due to the precondition that the input string is valid. This gives us the probability of failure, assuming input and output are random, apart from the known relation between the two, and the fact that both are valid. This technique has an important limitation: it can only reason about randomly- chosen input strings, and the presence of the HRP and version numbers at the start violates that assumption. These are not random, and we're forced to make one of these concessions: 1) Ignore the problem, and treat the HRP as random. This lets us derive properties that hold over all potential HRPs on average, but will thus fail to account for the possibility that for a small numbers of potential HRPs some error patterns may exist that behave worse. For technical reasons, this averaging makes all constants behave identically for error patterns that don't change the length of the string. Given that substitution/swap only errors are already dealt with well due to the BCH design this is perhaps not too important. One exception is frame-shifting errors (a deletion in one place compensated with an insertion in another place). 2) Restrict analysis to error patterns that don't affect the first 6 actual characters. Doing so "masks" the effect of the HRP completely. 3) Do analysis for specific HRPs only, allowing much more accurate statements, but HRP-specific ones that may not hold for every HRP. Our final selection primarily optimizes for 1) and 2) as those benefit all potential uses of the encoding, but do optimize for 3) the "bc1" prefix specifically (and the BIP173 length restriction) as a tiebreaker. The code for this can be found under the link above, in const_analysis.cpp. Cheers, -- Pieter ^ permalink raw reply [flat|nested] 24+ messages in thread
end of thread, other threads:[~2020-12-18 2:02 UTC | newest] Thread overview: 24+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2020-10-08 0:21 [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173) Rusty Russell 2020-10-08 14:59 ` David A. Harding 2020-10-08 15:21 ` Russell O'Connor 2020-10-15 1:40 ` Rusty Russell 2020-10-16 21:09 ` Pieter Wuille 2020-10-19 0:49 ` Rusty Russell 2020-10-19 22:55 ` Pieter Wuille 2020-10-20 0:42 ` Rusty Russell 2020-10-20 3:31 ` Rusty Russell 2020-10-20 9:21 ` Riccardo Casatta 2020-10-20 10:29 ` David A. Harding 2020-10-20 20:12 ` Pieter Wuille 2020-10-20 23:52 ` Mike Schmidt 2020-10-21 4:51 ` Rusty Russell 2020-11-06 19:49 ` Mike Schmidt 2020-12-05 23:10 ` Pieter Wuille 2020-12-06 13:04 ` David A. Harding 2020-12-06 20:43 ` Pieter Wuille 2020-12-08 17:39 ` Ryan Grant 2020-12-18 2:02 ` Pieter Wuille 2020-10-21 3:05 ` ZmnSCPxj 2020-10-21 4:39 ` Rusty Russell 2020-10-28 0:20 ` Pieter Wuille 2020-12-05 22:59 ` Pieter Wuille
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox