* [bitcoin-dev] Bech32 weakness and impact on bip-taproot addresses
@ 2019-11-07 22:35 Pieter Wuille
2019-11-07 22:45 ` Greg Sanders
` (2 more replies)
0 siblings, 3 replies; 16+ messages in thread
From: Pieter Wuille @ 2019-11-07 22:35 UTC (permalink / raw)
To: Bitcoin Dev
Hello all,
A while ago it was discovered that bech32 has a mutation weakness (see
https://github.com/sipa/bech32/issues/51 for details). Specifically,
when a bech32 string ends with a "p", inserting or erasing "q"s right
before that "p" does not invalidate it. While insertion/erasure
robustness was not an explicit goal (BCH codes in general only have
guarantees about substitution errors), this is very much not by
design, and this specific issue could have been made much less
impactful with a slightly different approach. I'm sorry it wasn't
caught earlier.
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.
I'm making this post because this property may unfortunately influence
design decisions around bip-taproot, as was brought up in the review
session (https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-October/017427.html)
past tuesday. In the current draft, witness v1 outputs of length other
than 32 remain unencumbered, which means that for now such an
insertion or erasure would result in an output that can be spent by
anyone. If that is considered unacceptable, it could be prevented by
for example outlawing v1 witness outputs of length 31 and 33.
Thoughts?
Cheers,
--
Pieter
^ permalink raw reply [flat|nested] 16+ messages in thread* Re: [bitcoin-dev] Bech32 weakness and impact on bip-taproot addresses 2019-11-07 22:35 [bitcoin-dev] Bech32 weakness and impact on bip-taproot addresses Pieter Wuille @ 2019-11-07 22:45 ` Greg Sanders 2019-11-08 0:41 ` Matt Corallo 2019-11-08 2:15 ` David A. Harding 2019-11-08 5:11 ` ZmnSCPxj 2 siblings, 1 reply; 16+ messages in thread From: Greg Sanders @ 2019-11-07 22:45 UTC (permalink / raw) To: Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 1905 bytes --] Could the softer touch of just making them non-standard apply as a future preparation for an accepted softfork? Relaxations could easily be done later if desired. On Thu, Nov 7, 2019, 5:37 PM Pieter Wuille via bitcoin-dev < bitcoin-dev@lists•linuxfoundation.org> wrote: > Hello all, > > A while ago it was discovered that bech32 has a mutation weakness (see > https://github.com/sipa/bech32/issues/51 for details). Specifically, > when a bech32 string ends with a "p", inserting or erasing "q"s right > before that "p" does not invalidate it. While insertion/erasure > robustness was not an explicit goal (BCH codes in general only have > guarantees about substitution errors), this is very much not by > design, and this specific issue could have been made much less > impactful with a slightly different approach. I'm sorry it wasn't > caught earlier. > > 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. > > I'm making this post because this property may unfortunately influence > design decisions around bip-taproot, as was brought up in the review > session ( > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-October/017427.html > ) > past tuesday. In the current draft, witness v1 outputs of length other > than 32 remain unencumbered, which means that for now such an > insertion or erasure would result in an output that can be spent by > anyone. If that is considered unacceptable, it could be prevented by > for example outlawing v1 witness outputs of length 31 and 33. > > Thoughts? > > 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: 2793 bytes --] ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [bitcoin-dev] Bech32 weakness and impact on bip-taproot addresses 2019-11-07 22:45 ` Greg Sanders @ 2019-11-08 0:41 ` Matt Corallo 0 siblings, 0 replies; 16+ messages in thread From: Matt Corallo @ 2019-11-08 0:41 UTC (permalink / raw) To: Greg Sanders, Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 2600 bytes --] Given the issue is in the address format, not the consensus/standardness layer, it does seem somewhat strange to jump to addressing it with a consensus/standardness fix. Maybe the ship has sailed, but for the sake of considering all our options, we could also redefine bech32 to not allow such addresses. Matt >> On Nov 7, 2019, at 17:47, Greg Sanders via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote: > > Could the softer touch of just making them non-standard apply as a future preparation for an accepted softfork? Relaxations could easily be done later if desired. > >>> On Thu, Nov 7, 2019, 5:37 PM Pieter Wuille via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote: >> Hello all, >> >> A while ago it was discovered that bech32 has a mutation weakness (see >> https://github.com/sipa/bech32/issues/51 for details). Specifically, >> when a bech32 string ends with a "p", inserting or erasing "q"s right >> before that "p" does not invalidate it. While insertion/erasure >> robustness was not an explicit goal (BCH codes in general only have >> guarantees about substitution errors), this is very much not by >> design, and this specific issue could have been made much less >> impactful with a slightly different approach. I'm sorry it wasn't >> caught earlier. >> >> 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. >> >> I'm making this post because this property may unfortunately influence >> design decisions around bip-taproot, as was brought up in the review >> session (https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-October/017427.html) >> past tuesday. In the current draft, witness v1 outputs of length other >> than 32 remain unencumbered, which means that for now such an >> insertion or erasure would result in an output that can be spent by >> anyone. If that is considered unacceptable, it could be prevented by >> for example outlawing v1 witness outputs of length 31 and 33. >> >> Thoughts? >> >> Cheers, >> >> -- >> Pieter >> _______________________________________________ >> bitcoin-dev mailing list >> bitcoin-dev@lists•linuxfoundation.org >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev [-- Attachment #2: Type: text/html, Size: 3730 bytes --] ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [bitcoin-dev] Bech32 weakness and impact on bip-taproot addresses 2019-11-07 22:35 [bitcoin-dev] Bech32 weakness and impact on bip-taproot addresses Pieter Wuille 2019-11-07 22:45 ` Greg Sanders @ 2019-11-08 2:15 ` David A. Harding 2019-11-08 3:15 ` Eric Voskuil 2019-11-10 21:51 ` Pieter Wuille 2019-11-08 5:11 ` ZmnSCPxj 2 siblings, 2 replies; 16+ messages in thread From: David A. Harding @ 2019-11-08 2:15 UTC (permalink / raw) To: Pieter Wuille, Bitcoin Protocol Discussion On Thu, Nov 07, 2019 at 02:35:42PM -0800, Pieter Wuille via bitcoin-dev wrote: > In the current draft, witness v1 outputs of length other > than 32 remain unencumbered, which means that for now such an > insertion or erasure would result in an output that can be spent by > anyone. If that is considered unacceptable, it could be prevented by > for example outlawing v1 witness outputs of length 31 and 33. Either a consensus rule or a standardness rule[1] would require anyone using a bech32 library supporting v1+ segwit to upgrade their library. Otherwise, users of old libraries will still attempt to pay v1 witness outputs of length 31 or 33, causing their transactions to get rejected by newer nodes or get stuck on older nodes. This is basically the problem #15846[2] was meant to prevent. If we're going to need everyone to upgrade their bech32 libraries anyway, I think it's probably best that the problem is fixed in the bech32 algorithm rather than at the consensus/standardness layer. -Dave [1] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-November/017444.html [2] https://github.com/bitcoin/bitcoin/pull/15846 P.S. My thanks as well to the people who asked the question during review that lead to this discussion: http://www.erisian.com.au/meetbot/taproot-bip-review/2019/taproot-bip-review.2019-11-05-19.00.log.html#l-88 ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [bitcoin-dev] Bech32 weakness and impact on bip-taproot addresses 2019-11-08 2:15 ` David A. Harding @ 2019-11-08 3:15 ` Eric Voskuil 2019-11-10 21:51 ` Pieter Wuille 1 sibling, 0 replies; 16+ messages in thread From: Eric Voskuil @ 2019-11-08 3:15 UTC (permalink / raw) To: David A. Harding, Bitcoin Protocol Discussion > On Nov 8, 2019, at 11:16, David A. Harding via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote: > > On Thu, Nov 07, 2019 at 02:35:42PM -0800, Pieter Wuille via bitcoin-dev wrote: >> In the current draft, witness v1 outputs of length other >> than 32 remain unencumbered, which means that for now such an >> insertion or erasure would result in an output that can be spent by >> anyone. If that is considered unacceptable, it could be prevented by >> for example outlawing v1 witness outputs of length 31 and 33. > > Either a consensus rule or a standardness rule[1] would require anyone > using a bech32 library supporting v1+ segwit to upgrade their library. > Otherwise, users of old libraries will still attempt to pay v1 witness > outputs of length 31 or 33, causing their transactions to get rejected > by newer nodes or get stuck on older nodes. This is basically the > problem #15846[2] was meant to prevent. > > If we're going to need everyone to upgrade their bech32 libraries > anyway, I think it's probably best that the problem is fixed in the > bech32 algorithm rather than at the consensus/standardness layer. As an implementer of both the address encoding and script validation, I agree. e > -Dave > > [1] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-November/017444.html > [2] https://github.com/bitcoin/bitcoin/pull/15846 > > P.S. My thanks as well to the people who asked the question during > review that lead to this discussion: > > http://www.erisian.com.au/meetbot/taproot-bip-review/2019/taproot-bip-review.2019-11-05-19.00.log.html#l-88 > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [bitcoin-dev] Bech32 weakness and impact on bip-taproot addresses 2019-11-08 2:15 ` David A. Harding 2019-11-08 3:15 ` Eric Voskuil @ 2019-11-10 21:51 ` Pieter Wuille 2019-11-11 1:02 ` Matt Corallo 1 sibling, 1 reply; 16+ messages in thread From: Pieter Wuille @ 2019-11-10 21:51 UTC (permalink / raw) To: David A. Harding, Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 3972 bytes --] On Thu, Nov 7, 2019, 18:16 David A. Harding <dave@dtrt•org> wrote: > On Thu, Nov 07, 2019 at 02:35:42PM -0800, Pieter Wuille via bitcoin-dev > wrote: > > In the current draft, witness v1 outputs of length other > > than 32 remain unencumbered, which means that for now such an > > insertion or erasure would result in an output that can be spent by > > anyone. If that is considered unacceptable, it could be prevented by > > for example outlawing v1 witness outputs of length 31 and 33. > > Either a consensus rule or a standardness rule[1] would require anyone > using a bech32 library supporting v1+ segwit to upgrade their library. > Otherwise, users of old libraries will still attempt to pay v1 witness > outputs of length 31 or 33, causing their transactions to get rejected > by newer nodes or get stuck on older nodes. This is basically the > problem #15846[2] was meant to prevent. > > If we're going to need everyone to upgrade their bech32 libraries > anyway, I think it's probably best that the problem is fixed in the > bech32 algorithm rather than at the consensus/standardness layer. > Admittedly, this affecting development of consensus or standardness rules would feel unnatural. In addition, it also has the potential downside of breaking batched transactions in some settings (ask an exchange for a withdrawal to a invalid/nonstandard version, which they batch with other outputs that then get stuck because the transaction does not go through). So, Ideally this is indeed solved entirely on the bech32/address encoding side of things. I did not initially expect the discussion here to go in that direction, as that could come with all problems that rolling out a new address scheme in the first place has. However, there may be a way to mostly avoid those problems for the time being, while also not having any impact on consensus or standardness rules. I believe that most new witness programs we'd want to introduce anyway will be 32 bytes in the future, if the option exists. It's enough for a 256-bit hash (which has up to 128-bit collision security, and more than 128 bits is hard to achieve in Bitcoin anyway), or for X coordinates directly. Either of those, plus a small version number to indicate the commitment structure should be enough to encode any spendability condition we'd want with any achievable security level. With that observation, I propose the following. We amend BIP173 to be restricted to witness programs of length 20 or 32 (but still support versions other than 0). This seems like it may be sufficient for several years, until version numbers run out. I believe that some wallet implementations already restrict sending to known versions only, which means effectively no change for them in addition to normal deployment. In the mean time we develop a variant of bech32 with better insertion/erasure detecting properties, which will be used for witness programs of length different from 20 or 32. If we make sure that there are never two distinct valid checksum algorithms for the same output, I don't believe there is any need for a new address scheme or a different HRP. The latter is something I'd strongly try to avoid anyway, as it would mean additional cognitive load on users because of another visually distinct address style, plus more logistical overhead (coordination and keeping track of 2 HRPs per chain). I believe improving bech32 itself is preferable over changing the way segwit addresses use bech32, as that can be done without making addresses even longer. Furthermore, the root of the issue is in bech32, and it is simplest to fix things there. The easiest solution is to simply change the constant 1 that is xor'ed into the checksum before encoding it to a 30-bit number. This has the advantage that a single checksum is never valid for both algoritgms simultaneously. Another approach is to implicitly including the length into the checksummed data. What do people think? Cheers, -- Pieter [-- Attachment #2: Type: text/html, Size: 5119 bytes --] ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [bitcoin-dev] Bech32 weakness and impact on bip-taproot addresses 2019-11-10 21:51 ` Pieter Wuille @ 2019-11-11 1:02 ` Matt Corallo 2019-11-13 2:56 ` Clark Moody 0 siblings, 1 reply; 16+ messages in thread From: Matt Corallo @ 2019-11-11 1:02 UTC (permalink / raw) To: Pieter Wuille, Bitcoin Protocol Discussion, David A. Harding Seems good to me, though I'm curious if we have any (even vaguely) immediate need for non-32/20-byte Segwit outputs? It seems to me this can be resolved by just limiting the size of bech32 outputs and calling it a day - adding yet another address format has very significant ecosystem costs, and if we don't anticipate needing it for 5 years (if at all)...lets not jump to pay that cost. Matt On 11/10/19 9:51 PM, Pieter Wuille via bitcoin-dev wrote: > On Thu, Nov 7, 2019, 18:16 David A. Harding <dave@dtrt•org > <mailto:dave@dtrt•org>> wrote: > > On Thu, Nov 07, 2019 at 02:35:42PM -0800, Pieter Wuille via > bitcoin-dev wrote: > > In the current draft, witness v1 outputs of length other > > than 32 remain unencumbered, which means that for now such an > > insertion or erasure would result in an output that can be spent by > > anyone. If that is considered unacceptable, it could be prevented by > > for example outlawing v1 witness outputs of length 31 and 33. > > Either a consensus rule or a standardness rule[1] would require anyone > using a bech32 library supporting v1+ segwit to upgrade their library. > Otherwise, users of old libraries will still attempt to pay v1 witness > outputs of length 31 or 33, causing their transactions to get rejected > by newer nodes or get stuck on older nodes. This is basically the > problem #15846[2] was meant to prevent. > > If we're going to need everyone to upgrade their bech32 libraries > anyway, I think it's probably best that the problem is fixed in the > bech32 algorithm rather than at the consensus/standardness layer. > > > Admittedly, this affecting development of consensus or standardness > rules would feel unnatural. In addition, it also has the potential > downside of breaking batched transactions in some settings (ask an > exchange for a withdrawal to a invalid/nonstandard version, which they > batch with other outputs that then get stuck because the transaction > does not go through). > > So, Ideally this is indeed solved entirely on the bech32/address > encoding side of things. I did not initially expect the discussion here > to go in that direction, as that could come with all problems that > rolling out a new address scheme in the first place has. However, there > may be a way to mostly avoid those problems for the time being, while > also not having any impact on consensus or standardness rules. > > I believe that most new witness programs we'd want to introduce anyway > will be 32 bytes in the future, if the option exists. It's enough for a > 256-bit hash (which has up to 128-bit collision security, and more than > 128 bits is hard to achieve in Bitcoin anyway), or for X coordinates > directly. Either of those, plus a small version number to indicate the > commitment structure should be enough to encode any spendability > condition we'd want with any achievable security level. > > With that observation, I propose the following. We amend BIP173 to be > restricted to witness programs of length 20 or 32 (but still support > versions other than 0). This seems like it may be sufficient for several > years, until version numbers run out. I believe that some wallet > implementations already restrict sending to known versions only, which > means effectively no change for them in addition to normal deployment. > > In the mean time we develop a variant of bech32 with better > insertion/erasure detecting properties, which will be used for witness > programs of length different from 20 or 32. If we make sure that there > are never two distinct valid checksum algorithms for the same output, I > don't believe there is any need for a new address scheme or a different > HRP. The latter is something I'd strongly try to avoid anyway, as it > would mean additional cognitive load on users because of another > visually distinct address style, plus more logistical overhead > (coordination and keeping track of 2 HRPs per chain). > > I believe improving bech32 itself is preferable over changing the way > segwit addresses use bech32, as that can be done without making > addresses even longer. Furthermore, the root of the issue is in bech32, > and it is simplest to fix things there. The easiest solution is to > simply change the constant 1 that is xor'ed into the checksum before > encoding it to a 30-bit number. This has the advantage that a single > checksum is never valid for both algoritgms simultaneously. Another > approach is to implicitly including the length into the checksummed data. > > What do people think? > > Cheers, > > -- > Pieter > > > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [bitcoin-dev] Bech32 weakness and impact on bip-taproot addresses 2019-11-11 1:02 ` Matt Corallo @ 2019-11-13 2:56 ` Clark Moody 2019-11-13 5:32 ` ZmnSCPxj 0 siblings, 1 reply; 16+ messages in thread From: Clark Moody @ 2019-11-13 2:56 UTC (permalink / raw) To: Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 5635 bytes --] I agree on all points. The address space already brings enough confusion to users out there. As it stands, we can use script version and program length for address validity. Sneaking an alternate checksum into the mix for different length programs lets us lean on our parsing libraries and not increase cognitive load for users. -Clark On Sun, Nov 10, 2019 at 7:02 PM Matt Corallo via bitcoin-dev < bitcoin-dev@lists•linuxfoundation.org> wrote: > Seems good to me, though I'm curious if we have any (even vaguely) > immediate need for non-32/20-byte Segwit outputs? It seems to me this > can be resolved by just limiting the size of bech32 outputs and calling > it a day - adding yet another address format has very significant > ecosystem costs, and if we don't anticipate needing it for 5 years (if > at all)...lets not jump to pay that cost. > > Matt > > On 11/10/19 9:51 PM, Pieter Wuille via bitcoin-dev wrote: > > On Thu, Nov 7, 2019, 18:16 David A. Harding <dave@dtrt•org > > <mailto:dave@dtrt•org>> wrote: > > > > On Thu, Nov 07, 2019 at 02:35:42PM -0800, Pieter Wuille via > > bitcoin-dev wrote: > > > In the current draft, witness v1 outputs of length other > > > than 32 remain unencumbered, which means that for now such an > > > insertion or erasure would result in an output that can be spent by > > > anyone. If that is considered unacceptable, it could be prevented > by > > > for example outlawing v1 witness outputs of length 31 and 33. > > > > Either a consensus rule or a standardness rule[1] would require > anyone > > using a bech32 library supporting v1+ segwit to upgrade their > library. > > Otherwise, users of old libraries will still attempt to pay v1 > witness > > outputs of length 31 or 33, causing their transactions to get > rejected > > by newer nodes or get stuck on older nodes. This is basically the > > problem #15846[2] was meant to prevent. > > > > If we're going to need everyone to upgrade their bech32 libraries > > anyway, I think it's probably best that the problem is fixed in the > > bech32 algorithm rather than at the consensus/standardness layer. > > > > > > Admittedly, this affecting development of consensus or standardness > > rules would feel unnatural. In addition, it also has the potential > > downside of breaking batched transactions in some settings (ask an > > exchange for a withdrawal to a invalid/nonstandard version, which they > > batch with other outputs that then get stuck because the transaction > > does not go through). > > > > So, Ideally this is indeed solved entirely on the bech32/address > > encoding side of things. I did not initially expect the discussion here > > to go in that direction, as that could come with all problems that > > rolling out a new address scheme in the first place has. However, there > > may be a way to mostly avoid those problems for the time being, while > > also not having any impact on consensus or standardness rules. > > > > I believe that most new witness programs we'd want to introduce anyway > > will be 32 bytes in the future, if the option exists. It's enough for a > > 256-bit hash (which has up to 128-bit collision security, and more than > > 128 bits is hard to achieve in Bitcoin anyway), or for X coordinates > > directly. Either of those, plus a small version number to indicate the > > commitment structure should be enough to encode any spendability > > condition we'd want with any achievable security level. > > > > With that observation, I propose the following. We amend BIP173 to be > > restricted to witness programs of length 20 or 32 (but still support > > versions other than 0). This seems like it may be sufficient for several > > years, until version numbers run out. I believe that some wallet > > implementations already restrict sending to known versions only, which > > means effectively no change for them in addition to normal deployment. > > > > In the mean time we develop a variant of bech32 with better > > insertion/erasure detecting properties, which will be used for witness > > programs of length different from 20 or 32. If we make sure that there > > are never two distinct valid checksum algorithms for the same output, I > > don't believe there is any need for a new address scheme or a different > > HRP. The latter is something I'd strongly try to avoid anyway, as it > > would mean additional cognitive load on users because of another > > visually distinct address style, plus more logistical overhead > > (coordination and keeping track of 2 HRPs per chain). > > > > I believe improving bech32 itself is preferable over changing the way > > segwit addresses use bech32, as that can be done without making > > addresses even longer. Furthermore, the root of the issue is in bech32, > > and it is simplest to fix things there. The easiest solution is to > > simply change the constant 1 that is xor'ed into the checksum before > > encoding it to a 30-bit number. This has the advantage that a single > > checksum is never valid for both algoritgms simultaneously. Another > > approach is to implicitly including the length into the checksummed data. > > > > What do people think? > > > > Cheers, > > > > -- > > Pieter > > > > > > _______________________________________________ > > bitcoin-dev mailing list > > bitcoin-dev@lists•linuxfoundation.org > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > > > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > [-- Attachment #2: Type: text/html, Size: 7327 bytes --] ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [bitcoin-dev] Bech32 weakness and impact on bip-taproot addresses 2019-11-13 2:56 ` Clark Moody @ 2019-11-13 5:32 ` ZmnSCPxj 2019-11-13 6:30 ` Pieter Wuille 0 siblings, 1 reply; 16+ messages in thread From: ZmnSCPxj @ 2019-11-13 5:32 UTC (permalink / raw) To: Clark Moody, Bitcoin Protocol Discussion Good morning all, It seems to me that adding the length for checksumming purposes need not require the length to be *actually* added in the address format. So, currently, below is my understanding of bech32 validation: * Run BCH checksum on witness program. * Compare checksum to checksum in address. * If the checksum matches: * If version is 0, validate that the witness program is length 20 or 32. * Else accept. * If the checksum does not match: * Reject Let me propose then: * Run BCH checksum on witness program. * Compare checksum to checksum in address. * If the checksum matches: * If version is 0, validate that the witness program is length 20 or 32. * Else validate that the witness program is length 32. * If the checksum does not match: * Get the length of the witness program. * Prepend the length to the witness program. * Run BCH checksum on concatenated length | witness program. * Compare checksum to checksum in address. * If the checksum matches: * Accept. * Else reject. A writer of bech32 addresses would then: * If the witness program is length 32, or witness version is 0 and witness program length is 20, use a non-length-prefixed checksum. * Otherwise, use a length-prefixed checksum (but not include the length in the address, just change the BCH checksum). This has the following properties: * The bech32 address format is retained, and no explicit length is added. * There are now two checksum formats: one with just the witness program, the other which validates with the witness program length. * Readers that do not understand the new checksum format will simply reject them without mis-sending to the wrong witness program. Is the above acceptable? Regards, ZmnSCPxj ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [bitcoin-dev] Bech32 weakness and impact on bip-taproot addresses 2019-11-13 5:32 ` ZmnSCPxj @ 2019-11-13 6:30 ` Pieter Wuille 2020-07-15 20:56 ` Russell O'Connor 0 siblings, 1 reply; 16+ messages in thread From: Pieter Wuille @ 2019-11-13 6:30 UTC (permalink / raw) To: Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 2506 bytes --] On Tue, Nov 12, 2019, 21:33 ZmnSCPxj via bitcoin-dev < bitcoin-dev@lists•linuxfoundation.org> wrote: > Good morning all, > > It seems to me that adding the length for checksumming purposes need not > require the length to be *actually* added in the address format. > Indeed! This has the following properties: > > * The bech32 address format is retained, and no explicit length is added. > * There are now two checksum formats: one with just the witness program, > the other which validates with the witness program length. > * Readers that do not understand the new checksum format will simply > reject them without mis-sending to the wrong witness program. > That's very close to what I was suggesting: create an improved bech32 algorithm and use that for future addresses, rather than working around the problem in the address encoding while keeping the existing bech32 checksum. Sorry if that wasn't clear from my previous email. In this case, there is no need to even implicitly include the length in the checksum algorithm. Replacing the "xor 1" at the end of the algorithm to "xor (2^30 - 1)" would reduce the occurrence of this weakness from 1/32 to 1/2^30, and have no downsides otherwise. I'd like to do some analysis to ascertain it actually will catch any other kind of insertion/deletion errors with high probability as well before actually proposing it, though. There are other solutions which do include the length in some fashion directly in the checksum calculation, which may be preferable (I need to analyse things...). It's also possible to do this in such a way that for 33-symbol and 53-symbol data parts (corresponding to P2WPKH and P2WSH lengths) the new algorithm is defined as identical to the old one. That would simplify upstream users of a bech32 library (which would then effectively need no changes at all, apart from updating the checksum/decoder code). That brings me to Matt's point: there is no need to do this right now. We can simply amend BIP173 to only permit length 20 and length 32 (and only length 20 for v0, if you like; but they're so far apart that permitting both shouldn't hurt), for now. Introducing the "new" address format (the one using an improved checksum algorithm) only needs to be there in time for when a non-32-byte-witness-program would come in sight. Of course, I should update BIP173 to indicate the issue, and have a suggested improvement for other users of bech32, if they feel this issue is significant enough. Cheers, -- Pieter [-- Attachment #2: Type: text/html, Size: 3684 bytes --] ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [bitcoin-dev] Bech32 weakness and impact on bip-taproot addresses 2019-11-13 6:30 ` Pieter Wuille @ 2020-07-15 20:56 ` Russell O'Connor 2020-07-15 21:05 ` Greg Sanders 0 siblings, 1 reply; 16+ messages in thread From: Russell O'Connor @ 2020-07-15 20:56 UTC (permalink / raw) To: Pieter Wuille, Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 2165 bytes --] On Wed, Nov 13, 2019 at 1:31 AM Pieter Wuille via bitcoin-dev < bitcoin-dev@lists•linuxfoundation.org> wrote: > > That brings me to Matt's point: there is no need to do this right now. We > can simply amend BIP173 to only permit length 20 and length 32 (and only > length 20 for v0, if you like; but they're so far apart that permitting > both shouldn't hurt), for now. Introducing the "new" address format (the > one using an improved checksum algorithm) only needs to be there in time > for when a non-32-byte-witness-program would come in sight. > As a prerequisite to taproot activation, I was looking into amending BIP173 as stated above. However after reviewing https://gist.github.com/sipa/a9845b37c1b298a7301c33a04090b2eb#detection-of-insertion-errors it seems that insertions of 5 characters or more is "safe" in the sense that there is low probability of creating a valid checksum by doing so randomly. This means we could safely allow witness programs of lengths *20*, 23, 26, 29, *32*, 36, and 40 (or 39). These correspond to Bech32 addresses of length *42*, 47, 52, 57, *62*, 68, and 74 (or 73). We could also support a set of shorter addresses, but given the lack of entropy in such short addresses, it is hard to believe that such witness programs could be used to secure anything. I'm not sure what the motivation for allowing such short witness programs was, but I'm somewhat inclined to exclude them from the segwit address format. Given that we would only be able to support one of 39 or 40 byte witness programs, it is sensible to choose to allow 40 byte witness programs to be addressable. This is the maximum witness program size allowed by BIP 141. So my proposal would be to amend BIP173 in such a way to restrict "bc" and "tb" segwit address formats to require witness programs be of size *20*, 23, 26, 29, *32*, 36, or 40. Witness programs of other sizes (between 2 and 40) would, of course, still be legal in accordance with BIP 141; however they would be unaddressable by using this "bc" and "tb" prefix. Another address format would be needed to support other witness sizes, should the need ever arise. -- Russell O'Connor [-- Attachment #2: Type: text/html, Size: 2896 bytes --] ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [bitcoin-dev] Bech32 weakness and impact on bip-taproot addresses 2020-07-15 20:56 ` Russell O'Connor @ 2020-07-15 21:05 ` Greg Sanders 2020-07-15 21:11 ` Russell O'Connor 0 siblings, 1 reply; 16+ messages in thread From: Greg Sanders @ 2020-07-15 21:05 UTC (permalink / raw) To: Russell O'Connor, Bitcoin Protocol Discussion; +Cc: Pieter Wuille [-- Attachment #1: Type: text/plain, Size: 2595 bytes --] Can you make it clear what the bold vs not-bold numbers mean? On Wed, Jul 15, 2020 at 4:56 PM Russell O'Connor via bitcoin-dev < bitcoin-dev@lists•linuxfoundation.org> wrote: > On Wed, Nov 13, 2019 at 1:31 AM Pieter Wuille via bitcoin-dev < > bitcoin-dev@lists•linuxfoundation.org> wrote: > >> >> That brings me to Matt's point: there is no need to do this right now. We >> can simply amend BIP173 to only permit length 20 and length 32 (and only >> length 20 for v0, if you like; but they're so far apart that permitting >> both shouldn't hurt), for now. Introducing the "new" address format (the >> one using an improved checksum algorithm) only needs to be there in time >> for when a non-32-byte-witness-program would come in sight. >> > > As a prerequisite to taproot activation, I was looking into amending > BIP173 as stated above. However after reviewing > https://gist.github.com/sipa/a9845b37c1b298a7301c33a04090b2eb#detection-of-insertion-errors > it seems that insertions of 5 characters or more is "safe" in the sense > that there is low probability of creating a valid checksum by doing so > randomly. > > This means we could safely allow witness programs of lengths *20*, 23, > 26, 29, *32*, 36, and 40 (or 39). These correspond to Bech32 addresses > of length *42*, 47, 52, 57, *62*, 68, and 74 (or 73). We could also > support a set of shorter addresses, but given the lack of entropy in such > short addresses, it is hard to believe that such witness programs could be > used to secure anything. I'm not sure what the motivation for allowing > such short witness programs was, but I'm somewhat inclined to exclude them > from the segwit address format. > > Given that we would only be able to support one of 39 or 40 byte witness > programs, it is sensible to choose to allow 40 byte witness programs to be > addressable. This is the maximum witness program size allowed by BIP 141. > > So my proposal would be to amend BIP173 in such a way to restrict "bc" and > "tb" segwit address formats to require witness programs be of size *20*, > 23, 26, 29, *32*, 36, or 40. Witness programs of other sizes (between 2 > and 40) would, of course, still be legal in accordance with BIP 141; > however they would be unaddressable by using this "bc" and "tb" prefix. > Another address format would be needed to support other witness sizes, > should the need ever arise. > > -- > Russell O'Connor > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > [-- Attachment #2: Type: text/html, Size: 3752 bytes --] ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [bitcoin-dev] Bech32 weakness and impact on bip-taproot addresses 2020-07-15 21:05 ` Greg Sanders @ 2020-07-15 21:11 ` Russell O'Connor 0 siblings, 0 replies; 16+ messages in thread From: Russell O'Connor @ 2020-07-15 21:11 UTC (permalink / raw) To: Greg Sanders; +Cc: Bitcoin Protocol Discussion, Pieter Wuille [-- Attachment #1: Type: text/plain, Size: 3016 bytes --] The bold values are the witness program lengths and address lengths of the segwit v0 programs (BIP-141), which clearly need to be covered in my proposed amendment. 32 bytes is also the proposed witness program length for segwit v1 that would correspond to a taproot (BIP-341) program. On Wed, Jul 15, 2020 at 5:05 PM Greg Sanders <gsanders87@gmail•com> wrote: > Can you make it clear what the bold vs not-bold numbers mean? > > On Wed, Jul 15, 2020 at 4:56 PM Russell O'Connor via bitcoin-dev < > bitcoin-dev@lists•linuxfoundation.org> wrote: > >> On Wed, Nov 13, 2019 at 1:31 AM Pieter Wuille via bitcoin-dev < >> bitcoin-dev@lists•linuxfoundation.org> wrote: >> >>> >>> That brings me to Matt's point: there is no need to do this right now. >>> We can simply amend BIP173 to only permit length 20 and length 32 (and only >>> length 20 for v0, if you like; but they're so far apart that permitting >>> both shouldn't hurt), for now. Introducing the "new" address format (the >>> one using an improved checksum algorithm) only needs to be there in time >>> for when a non-32-byte-witness-program would come in sight. >>> >> >> As a prerequisite to taproot activation, I was looking into amending >> BIP173 as stated above. However after reviewing >> https://gist.github.com/sipa/a9845b37c1b298a7301c33a04090b2eb#detection-of-insertion-errors >> it seems that insertions of 5 characters or more is "safe" in the sense >> that there is low probability of creating a valid checksum by doing so >> randomly. >> >> This means we could safely allow witness programs of lengths *20*, 23, >> 26, 29, *32*, 36, and 40 (or 39). These correspond to Bech32 addresses >> of length *42*, 47, 52, 57, *62*, 68, and 74 (or 73). We could also >> support a set of shorter addresses, but given the lack of entropy in such >> short addresses, it is hard to believe that such witness programs could be >> used to secure anything. I'm not sure what the motivation for allowing >> such short witness programs was, but I'm somewhat inclined to exclude them >> from the segwit address format. >> >> Given that we would only be able to support one of 39 or 40 byte witness >> programs, it is sensible to choose to allow 40 byte witness programs to be >> addressable. This is the maximum witness program size allowed by BIP 141. >> >> So my proposal would be to amend BIP173 in such a way to restrict "bc" >> and "tb" segwit address formats to require witness programs be of size >> *20*, 23, 26, 29, *32*, 36, or 40. Witness programs of other sizes >> (between 2 and 40) would, of course, still be legal in accordance with BIP >> 141; however they would be unaddressable by using this "bc" and "tb" >> prefix. Another address format would be needed to support other witness >> sizes, should the need ever arise. >> >> -- >> Russell O'Connor >> _______________________________________________ >> bitcoin-dev mailing list >> bitcoin-dev@lists•linuxfoundation.org >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >> > [-- Attachment #2: Type: text/html, Size: 4416 bytes --] ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [bitcoin-dev] Bech32 weakness and impact on bip-taproot addresses 2019-11-07 22:35 [bitcoin-dev] Bech32 weakness and impact on bip-taproot addresses Pieter Wuille 2019-11-07 22:45 ` Greg Sanders 2019-11-08 2:15 ` David A. Harding @ 2019-11-08 5:11 ` ZmnSCPxj 2019-11-08 13:03 ` Russell O'Connor 2 siblings, 1 reply; 16+ messages in thread From: ZmnSCPxj @ 2019-11-08 5:11 UTC (permalink / raw) To: Pieter Wuille, Bitcoin Protocol Discussion Good morning Pieter, and all, Can we modify Bech32 SegWit address format for version 1 and above as below? * The data-part values: ** 1 byte: the witness version + ** If the witness version is non-zero, 1 byte: the length of the witness program. ** A conversion of the 2-to-40-byte witness program (as defined by [https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki BIP141]) to base32: *** Start with the bits of the witness program, most significant bit per byte first. *** Re-arrange those bits into groups of 5, and pad with zeroes at the end if needed. *** Translate those bits to characters using the table above. This retains the ability of a bech32 address to specify any valid witness length and allows future version 1 addresses with lengths other than 32, while closing this malleation. Older software being given the modified v1 address format would mis-send it to the wrong witness program, however. Alternately we could just keep using version 0 in the address format forever. The requirement would be to ensure that SegWit vN (N >= 1) output witness programs would have a data-part value encoded as below: * The data-part values: ** 1 byte: legacy witness version, which must always be 0. ** 1 byte: actual witness version, which must be non-zero. ** 1 byte: padding length: 0 or 1. ** If padding length is 1, 1 byte: padding, which must be 0. ** 1 byte: witness program length. ** variable: witness program. A writer for a v1 or later address would initially set an empty padding, then compute: 1 // actual witness version + 1 // padding length + 1 // witness length + witness_length If the above sum is 20 or 32, then the writer selects a non-zero padding and inserts the padding byte so that the above sum is now 21 or 33. To a reader that understands only bech32 v0, such an encoding would look like a SegWit v0 invalid-program-length, and be rejected. A reader which understands the above protocol would, instead of rejecting a SegWit v0 invalid-program-length, instead attempt to parse it as above first, and consider it as SegWit v1 or higher if it was parsed correctly as above. The above proposal is of course ridiculous and I am now currently running diagnostics on my processing units to see if further glitches occur in test reasoning skills. Regards, ZmnSCPxj ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [bitcoin-dev] Bech32 weakness and impact on bip-taproot addresses 2019-11-08 5:11 ` ZmnSCPxj @ 2019-11-08 13:03 ` Russell O'Connor 2019-11-08 13:42 ` Damian Mee 0 siblings, 1 reply; 16+ messages in thread From: Russell O'Connor @ 2019-11-08 13:03 UTC (permalink / raw) To: ZmnSCPxj via bitcoin-dev; +Cc: Pieter Wuille [-- Attachment #1: Type: text/plain, Size: 3271 bytes --] I do like the idea of length prefixing the witness program. I will note that the 1 byte witness version is really more like a 1 character witness version. There are 17 different segwit versions and there are 32 characters in the bech32 alphabet. That leaves 15 unused characters that we can use for assigning new meanings too. That said, it is probably most sensible to define a new human-readable-prefix for length prefixed bitcoin witness programs. "btc1" anyone? On Fri, Nov 8, 2019 at 12:12 AM ZmnSCPxj via bitcoin-dev < bitcoin-dev@lists•linuxfoundation.org> wrote: > Good morning Pieter, and all, > > Can we modify Bech32 SegWit address format for version 1 and above as > below? > > * The data-part values: > ** 1 byte: the witness version > + ** If the witness version is non-zero, 1 byte: the length of the > witness program. > ** A conversion of the 2-to-40-byte witness program (as defined by [ > https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki BIP141]) > to base32: > *** Start with the bits of the witness program, most significant bit > per byte first. > *** Re-arrange those bits into groups of 5, and pad with zeroes at > the end if needed. > *** Translate those bits to characters using the table above. > > This retains the ability of a bech32 address to specify any valid witness > length and allows future version 1 addresses with lengths other than 32, > while closing this malleation. > > Older software being given the modified v1 address format would mis-send > it to the wrong witness program, however. > > Alternately we could just keep using version 0 in the address format > forever. > The requirement would be to ensure that SegWit vN (N >= 1) output witness > programs would have a data-part value encoded as below: > > * The data-part values: > ** 1 byte: legacy witness version, which must always be 0. > ** 1 byte: actual witness version, which must be non-zero. > ** 1 byte: padding length: 0 or 1. > ** If padding length is 1, 1 byte: padding, which must be 0. > ** 1 byte: witness program length. > ** variable: witness program. > > A writer for a v1 or later address would initially set an empty padding, > then compute: > > 1 // actual witness version > + 1 // padding length > + 1 // witness length > + witness_length > > If the above sum is 20 or 32, then the writer selects a non-zero padding > and inserts the padding byte so that the above sum is now 21 or 33. > > To a reader that understands only bech32 v0, such an encoding would look > like a SegWit v0 invalid-program-length, and be rejected. > A reader which understands the above protocol would, instead of rejecting > a SegWit v0 invalid-program-length, instead attempt to parse it as above > first, and consider it as SegWit v1 or higher if it was parsed correctly as > above. > > The above proposal is of course ridiculous and I am now currently running > diagnostics on my processing units to see if further glitches occur in test > reasoning skills. > > Regards, > ZmnSCPxj > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > [-- Attachment #2: Type: text/html, Size: 4073 bytes --] ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [bitcoin-dev] Bech32 weakness and impact on bip-taproot addresses 2019-11-08 13:03 ` Russell O'Connor @ 2019-11-08 13:42 ` Damian Mee 0 siblings, 0 replies; 16+ messages in thread From: Damian Mee @ 2019-11-08 13:42 UTC (permalink / raw) To: Russell O'Connor, Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 3765 bytes --] > a new human-readable-prefix for length prefixed bitcoin witness programs. "btc1" anyone? Yes, please! On Fri, Nov 8, 2019 at 2:04 PM Russell O'Connor via bitcoin-dev < bitcoin-dev@lists•linuxfoundation.org> wrote: > I do like the idea of length prefixing the witness program. I will note > that the 1 byte witness version is really more like a 1 character witness > version. There are 17 different segwit versions and there are 32 > characters in the bech32 alphabet. That leaves 15 unused characters that > we can use for assigning new meanings too. > > That said, it is probably most sensible to define a new > human-readable-prefix for length prefixed bitcoin witness programs. "btc1" > anyone? > > On Fri, Nov 8, 2019 at 12:12 AM ZmnSCPxj via bitcoin-dev < > bitcoin-dev@lists•linuxfoundation.org> wrote: > >> Good morning Pieter, and all, >> >> Can we modify Bech32 SegWit address format for version 1 and above as >> below? >> >> * The data-part values: >> ** 1 byte: the witness version >> + ** If the witness version is non-zero, 1 byte: the length of the >> witness program. >> ** A conversion of the 2-to-40-byte witness program (as defined by [ >> https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki BIP141]) >> to base32: >> *** Start with the bits of the witness program, most significant >> bit per byte first. >> *** Re-arrange those bits into groups of 5, and pad with zeroes at >> the end if needed. >> *** Translate those bits to characters using the table above. >> >> This retains the ability of a bech32 address to specify any valid witness >> length and allows future version 1 addresses with lengths other than 32, >> while closing this malleation. >> >> Older software being given the modified v1 address format would mis-send >> it to the wrong witness program, however. >> >> Alternately we could just keep using version 0 in the address format >> forever. >> The requirement would be to ensure that SegWit vN (N >= 1) output witness >> programs would have a data-part value encoded as below: >> >> * The data-part values: >> ** 1 byte: legacy witness version, which must always be 0. >> ** 1 byte: actual witness version, which must be non-zero. >> ** 1 byte: padding length: 0 or 1. >> ** If padding length is 1, 1 byte: padding, which must be 0. >> ** 1 byte: witness program length. >> ** variable: witness program. >> >> A writer for a v1 or later address would initially set an empty padding, >> then compute: >> >> 1 // actual witness version >> + 1 // padding length >> + 1 // witness length >> + witness_length >> >> If the above sum is 20 or 32, then the writer selects a non-zero padding >> and inserts the padding byte so that the above sum is now 21 or 33. >> >> To a reader that understands only bech32 v0, such an encoding would look >> like a SegWit v0 invalid-program-length, and be rejected. >> A reader which understands the above protocol would, instead of rejecting >> a SegWit v0 invalid-program-length, instead attempt to parse it as above >> first, and consider it as SegWit v1 or higher if it was parsed correctly as >> above. >> >> The above proposal is of course ridiculous and I am now currently running >> diagnostics on my processing units to see if further glitches occur in test >> reasoning skills. >> >> Regards, >> ZmnSCPxj >> _______________________________________________ >> bitcoin-dev mailing list >> bitcoin-dev@lists•linuxfoundation.org >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >> > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > [-- Attachment #2: Type: text/html, Size: 5026 bytes --] ^ permalink raw reply [flat|nested] 16+ messages in thread
end of thread, other threads:[~2020-07-15 21:11 UTC | newest] Thread overview: 16+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2019-11-07 22:35 [bitcoin-dev] Bech32 weakness and impact on bip-taproot addresses Pieter Wuille 2019-11-07 22:45 ` Greg Sanders 2019-11-08 0:41 ` Matt Corallo 2019-11-08 2:15 ` David A. Harding 2019-11-08 3:15 ` Eric Voskuil 2019-11-10 21:51 ` Pieter Wuille 2019-11-11 1:02 ` Matt Corallo 2019-11-13 2:56 ` Clark Moody 2019-11-13 5:32 ` ZmnSCPxj 2019-11-13 6:30 ` Pieter Wuille 2020-07-15 20:56 ` Russell O'Connor 2020-07-15 21:05 ` Greg Sanders 2020-07-15 21:11 ` Russell O'Connor 2019-11-08 5:11 ` ZmnSCPxj 2019-11-08 13:03 ` Russell O'Connor 2019-11-08 13:42 ` Damian Mee
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox