Re: [bitcoin-dev] Code Review: The Consensus Critical Parts of Segwit by Peter Todd

Re: [bitcoin-dev] Code Review: The Consensus Critical Parts of Segwit by Peter Todd

[Johnson Lau]

[-- Attachment #1: Type: text/plain, Size: 2406 bytes --]

Thanks for Peter Todd’s detailed report:
https://petertodd.org/2016/segwit-consensus-critical-code-review

I have the following response.

>Since the reserve value is only a single, 32-byte value, we’re setting ourselves up for the same problem again7.

Please note that unlimited space has been reserved after the witness commitment:

  block.vtx[0].vout[o].scriptPubKey.size() >= 38

 Which means anything after 38 bytes has no consensus meaning. Any new consensus critical commitments/metadata could be put there. Anyway, there is no efficient way to add a new commitment with softfork.


> the fact that we do this has a rather odd result: a transaction spending a witness output with an unknown version is valid even if the transaction doesn’t have any witnesses!

I don’t see any reason to have such check. We simply leave unknown witness program as any-one-can-spend without looking at the witness, as described in BIP141.


> Bizzarely segwit has an additonal pay-to-witness-pubkey-hashP2WPKH that lets you use a 160-bit (20 byte) commitment……

Since ~90% of current transactions are P2PKH, we expect many people will keep using this type of transaction in the future. P2WPKH gives the same level of security as P2PKH, and smaller scriptPubKey.

>give users the option instead to choose to accept the less secure 160-bit commitment if their use-case doesn’t need the full 256-bit security level

This is actually discussed on the mailing list. P2WSH with multi-sig is subject to birthday attack, and therefore 256-bit is used to provide 128-bit security. P2WPKH is used as single sig and therefore 160-bit is enough.


>Secondly, if you are going to give a 160-bit commitment option, you don’t need the extra level of indirection in the P2SH case: just make the segwit redeemScript be: <version> <serialized witness script>

Something wrong here? In P2WPKH, the witness is <sig> <pubkey>


>The only downside is the serialized witness script is constrained to 520 bytes max

520 is the original limit. BIP141 tries to mimic the existing behaviour as much as possible. Anyway, normally nothing in the current scripts should use a push with more than 75 bytes


>we haven’t explicitly ensured that signatures for the new signature hash can’t be reused for the old signature hash

How could that be? That’d be a hash collision.






[-- Attachment #2: Message signed with OpenPGP using GPGMail --]
[-- Type: application/pgp-signature, Size: 671 bytes --]

Re: [bitcoin-dev] Code Review: The Consensus Critical Parts of Segwit by Peter Todd

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 5204 bytes --]

On Wed, Jun 29, 2016 at 12:22:45AM +0800, Johnson Lau via bitcoin-dev wrote:
> Thanks for Peter Todd’s detailed report:
> https://petertodd.org/2016/segwit-consensus-critical-code-review
> 
> I have the following response.
> 
> >Since the reserve value is only a single, 32-byte value, we’re setting ourselves up for the same problem again7.
> 
> Please note that unlimited space has been reserved after the witness commitment:
> 
>   block.vtx[0].vout[o].scriptPubKey.size() >= 38
> 
>  Which means anything after 38 bytes has no consensus meaning. Any new consensus critical commitments/metadata could be put there. Anyway, there is no efficient way to add a new commitment with softfork.

Sure - equally you could say you could add additional commitments as other
coinbase txouts.

My point is that the extensible commitment - specifically the thing described
in the BIP - can't be easily used for the purpose of extending segwit due to a
design flaw.

> > the fact that we do this has a rather odd result: a transaction spending a witness output with an unknown version is valid even if the transaction doesn’t have any witnesses!
> 
> I don’t see any reason to have such check. We simply leave unknown witness program as any-one-can-spend without looking at the witness, as described in BIP141.

It will lead to a special case in code that does things with witness
transactions, as we can spend a witness output without a witness.

> > Bizzarely segwit has an additonal pay-to-witness-pubkey-hashP2WPKH that lets you use a 160-bit (20 byte) commitment……
> 
> Since ~90% of current transactions are P2PKH, we expect many people will keep using this type of transaction in the future. P2WPKH gives the same level of security as P2PKH, and smaller scriptPubKey.
> 
> >give users the option instead to choose to accept the less secure 160-bit commitment if their use-case doesn’t need the full 256-bit security level
> 
> This is actually discussed on the mailing list. P2WSH with multi-sig is subject to birthday attack, and therefore 256-bit is used to provide 128-bit security. P2WPKH is used as single sig and therefore 160-bit is enough.

I'm aware of that - there are many P2SH scripts where birthday attacks are not
an issue. In fact, _most_ usage of P2SH right now - multifactor wallets -
doesn't have a birthday attack problem.

> >Secondly, if you are going to give a 160-bit commitment option, you don’t need the extra level of indirection in the P2SH case: just make the segwit redeemScript be: <version> <serialized witness script>
> 
> Something wrong here? In P2WPKH, the witness is <sig> <pubkey>

Huh? That still another level of indirection.

Anyway, the right argument against my proposal for pay-to-pubkey-hash
functionality, is that taking into account the witness discount, my proposal is
slightly less efficient. In P2WPKH in P2SH the witness program in the
redeemScript is 22 bytes:

    <1-byte version> <1-byte length> <20 byte pubkey hash>

And the witness len(sig) + 34 bytes:

    <sig> <1 byte length> <33 bytes pubkey>

Taking into account the discount, that results in 22*4 + 34 + len(sig) = 122 bytes + len(sig)

My proposal would have a 37 byte redeemScript:

    <1-byte version> <1-byte witness script length> {<1-byte pubkey length> <33 byte pubkey> OP_CHECKSIG}

and a len(sig) length witness:

    <sig>

Taking into account the discount, that results in 37*4 + len(sig) = 148 bytes + len(sig)
Meanwhile for any more complex script, you'd certainly want to use the 256-bit
hash instead, due to the witness discount.

This suggests an obvious alternative: let users choose to use 160-bit security,
and make 256-bit and 160-bit witness programm commitments just be different
hash functions. P2PKH functionality implemented this way would be a single
extra byte vs. special-casing it.

Thus you could summarize the argument for the P2PKH special case as "We don't
want to make it possible to use 160-bit commitments for multisig, which _might_
need 256-bit security. But we do want to special-case pubkeys to save a few
bytes."

> >The only downside is the serialized witness script is constrained to 520 bytes max
> 
> 520 is the original limit. BIP141 tries to mimic the existing behaviour as much as possible. Anyway, normally nothing in the current scripts should use a push with more than 75 bytes

No, you're quite confused at my point: the witness script is otherwise
constrained to 10,000 bytes, as the first item in the witness is special-cased
for version 0 to be not be subject to the 520 byte rule.

> >we haven’t explicitly ensured that signatures for the new signature hash can’t be reused for the old signature hash
> 
> How could that be? That’d be a hash collision.

Nope. The problem is it might not be a hash collission, if the actual bytes
signed can be interpreted in two different ways, by different types of
signature hashes.

This is the same reason the signmessage functionality prepends the message
being signed with the "Bitcoin Signed Message:\n" magic string.

-- 
https://petertodd.org 'peter'[:-1]@petertodd.org

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 455 bytes --]

Re: [bitcoin-dev] Code Review: The Consensus Critical Parts of Segwit by Peter Todd

[Johnson Lau]

[-- Attachment #1: Type: text/plain, Size: 2237 bytes --]


> 
>>> the fact that we do this has a rather odd result: a transaction spending a witness output with an unknown version is valid even if the transaction doesn’t have any witnesses!
>> 
>> I don’t see any reason to have such check. We simply leave unknown witness program as any-one-can-spend without looking at the witness, as described in BIP141.
> 
> It will lead to a special case in code that does things with witness
> transactions, as we can spend a witness output without a witness.

It is trivial to softfork a new rule to require the witness must not be empty for a witness output. However, does it really make the code simpler?
> 
> Thus you could summarize the argument for the P2PKH special case as "We don't
> want to make it possible to use 160-bit commitments for multisig, which _might_
> need 256-bit security. But we do want to special-case pubkeys to save a few
> bytes.”

Actually I would like to see even shorter hash and pubkey to be used. Storing 1 BTC for a few months does not really require the security level of P2PKH.

> 
>>> we haven’t explicitly ensured that signatures for the new signature hash can’t be reused for the old signature hash
>> 
>> How could that be? That’d be a hash collision.
> 
> Nope. The problem is it might not be a hash collission, if the actual bytes
> signed can be interpreted in two different ways, by different types of
> signature hashes.
> 
> This is the same reason the signmessage functionality prepends the message
> being signed with the "Bitcoin Signed Message:\n" magic string.
> 

In BIP143 sig, first 4 bytes is nVersion, and the next 32 bytes (hashPrevouts) is a hash of all prevouts. (in the case of ANYONECANPAY, the bytes following would be zero, as you proposed)

In the original sig, first 4 bytes in nVersion, next 4 bytes is number of inputs, and the next 32 bytes is a txid.

For a signature to be valid for both schemes, the last 28 bytes of the hashPrevouts must also be the first 28 bytes of a valid txid. This is already impossible. And this is just one of the many collisions required. In such case SHA256 would be insecure and adding a zero after the nVersion as you suggest would not be helpful at all.

[-- Attachment #2: Message signed with OpenPGP using GPGMail --]
[-- Type: application/pgp-signature, Size: 671 bytes --]

Re: [bitcoin-dev] Code Review: The Consensus Critical Parts of Segwit by Peter Todd

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 4124 bytes --]

On Sun, Jul 03, 2016 at 03:20:42AM +0800, Johnson Lau wrote:
> >>> the fact that we do this has a rather odd result: a transaction spending a witness output with an unknown version is valid even if the transaction doesn’t have any witnesses!
> >> 
> >> I don’t see any reason to have such check. We simply leave unknown witness program as any-one-can-spend without looking at the witness, as described in BIP141.
> > 
> > It will lead to a special case in code that does things with witness
> > transactions, as we can spend a witness output without a witness.
> 
> It is trivial to softfork a new rule to require the witness must not be empty for a witness output. However, does it really make the code simpler?

The Bitcoin Core codebase, no, but it does reduce the number of special cases
other codebases have to contend with.

Probably not worth changing now, but it was I think a weird design choice to
make.

> > Thus you could summarize the argument for the P2PKH special case as "We don't
> > want to make it possible to use 160-bit commitments for multisig, which _might_
> > need 256-bit security. But we do want to special-case pubkeys to save a few
> > bytes.”
> 
> Actually I would like to see even shorter hash and pubkey to be used. Storing 1 BTC for a few months does not really require the security level of P2PKH.

How short? 128 bits? 80 bits? 64 bits?

It's hard to know what's the point where you're going to risk massive losses
due to theft... and as we've seen with the DAO, those kinds of losses can lead
to very undesirable pressure for devs to act as a central authority and
intervene.

> >>> we haven’t explicitly ensured that signatures for the new signature hash can’t be reused for the old signature hash
> >> 
> >> How could that be? That’d be a hash collision.
> > 
> > Nope. The problem is it might not be a hash collission, if the actual bytes
> > signed can be interpreted in two different ways, by different types of
> > signature hashes.
> > 
> > This is the same reason the signmessage functionality prepends the message
> > being signed with the "Bitcoin Signed Message:\n" magic string.
> > 
> 
> In BIP143 sig, first 4 bytes is nVersion, and the next 32 bytes (hashPrevouts) is a hash of all prevouts. (in the case of ANYONECANPAY, the bytes following would be zero, as you proposed)
> 
> In the original sig, first 4 bytes in nVersion, next 4 bytes is number of inputs, and the next 32 bytes is a txid.
> 
> For a signature to be valid for both schemes, the last 28 bytes of the hashPrevouts must also be the first 28 bytes of a valid txid. This is already impossible. And this is just one of the many collisions required. In such case SHA256 would be insecure and adding a zero after the nVersion as you suggest would not be helpful at all.

Why isn't this carefully documented in the BIPs then?

Again, as I said in my summary:

    In a number of places we either have a belt, or suspenders, when given the
    importance of this code we’d rather have both a belt and suspenders.

Tagged hashing is an excellent way to absolutely sure that signatures can't be
reused in different contexts; if it happens to be overkill in a specific
context, the overhead of hashing another few bytes is trivial; the gain of
being absolutely sure you haven't missed a vulnerability can't be easily
dismissed.

Equally, I think in most cases simply XORing the digest obtained by hashing
with a magic tag prior to using it (e.g. by signing it) should be sufficient
for signature applications, and the overhead of doing that is ~zero.
Essentially you can think of the magic tag that's XORed with the raw digest as
making clear the intent of the signature: "this is why I think I'm signing this
digest"

However, the XOR option does have one potentially big downside in other
contexts, like general use in committed data structures: it's incompatible with
timestamping schemes like OpenTimestamps that rely on all operations being
cryptographically secure.

-- 
https://petertodd.org 'peter'[:-1]@petertodd.org

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 455 bytes --]