Questions about multisig

[BlackHatCoiner]

I'm reading the way multisig works (p2sh), but I haven't totally understood how you end up with this:

Code:

tb1q7zdkfcze59yz4ca9clslznd297xq68yvypkhz33ph34g62g0yxrqxd00gc

Correct me if I'm somewhere wrong:

The scriptPubKey is the hash of my script hash surrounded with HASH160 and EQUAL opcodes. According with an example of learnmeabitcoin, a scriptPubKey looks like that:

_OP_HASH160_ _script hash_ _OP_EQUAL_

or in hexadecimal:

Code:

a914748284390f9e263a4b766a75d0633c50426eb87587

Question #1: Why is the address above longer than a usual native segwit? Since we no longer pay to multisig (using P2MS) and we're locking the funds to a scriptPubKey that has a script hash of the N public keys, shouldn't the address length be the same whether the script hash was hashed requiring 1-of-1 or 15-of-15?

Question #2: How is the script hash come of? I haven't read that anywhere. On a simple address (that requires 1-of-1) it could be a hash of the compressed public key. Once you wanted to spend from that address you could reveal that public key along with a signature, the nodes could hash it to verify that it's the correct public key and validate the signature. What do you hash in this case?

HASH160(M, public keys ^{(ascending order)}, N) ?

Isn't N unnecessary that way?

[ranochigo]

The scriptPubKey is the hash of my script hash surrounded with HASH160 and EQUAL opcodes. According with an example of learnmeabitcoin, a scriptPubKey looks like that:
-snip-

Question #1: Why is the address above longer than a usual native segwit? Since we no longer pay to multisig (using P2MS) and we're locking the funds to a scriptPubKey that has a script hash of the N public keys, shouldn't the address length be the same whether the script hash was hashed requiring 1-of-1 or 15-of-15?
-snip-

P2SH, P2WPKH/P2WSH are all different from each other, as defined in BIP141[1]. The link should answer your queries, scroll up to look at P2WPKH as well. P2WPKH and P2WSH have 20 bytes and 32 bytes of data being pushed onto the stack respectively.

Question #2: How is the script hash come of? I haven't read that anywhere. On a simple address (that requires 1-of-1) it could be a hash of the compressed public key. Once you wanted to spend from that address you could reveal that public key along with a signature, the nodes could hash it to verify that it's the correct public key and validate the signature. What do you hash in this case?

The OP codes are defined in the script hash. Hashing the redeem script allows the nodes to correctly hash the redeem script defined in the spending transaction to your address, together with the conditions and thus verifying that your transaction meets the requirements.

[1] https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki#P2WSH


Multisig is not the only use of P2SH. There are OP_CLTV, anyone can spend and this[2].

[2] https://bitcointalk.org/index.php?topic=293382.0

[BrewMaster]

1) P2WSH addresses are longer compared to P2WPKH (and P2SH) because unlike those scripts that use HASH160 here SHA256 hash is used which is longer.

2) in script hashes we are computing a hash of script as the name suggests. that means the hash found in the P2WSH address is hash of a redeem script that could be anything and only usually is a multisig script.
there is no HASH160 anymore instead it is SHA256(redeemscript). in multisig that is SHA256(m + n*pubkeys + n + OP_CHECKMULTISIG)

[NotATether]

Question #2: How is the script hash come of?

We have the witness, which is just m + n*pubkeys + n + OP_CHECKMULTISIG as BrewMaster said, and the script hash is the 32-byte SHA256 of this byte sequence. Then we have the redeem script which is composed of OP_0 (1 byte), a push byte of 0x20 (1 byte) and then the above 32-byte script hash. And the scriptPubKey is the format in your title post (OP_HASH160 redeemScript OP_EQUAL) and the witness and scriptPubKey are sent together as part of a transaction, where the witness is used in place of the empty scriptSig.

[BlackHatCoiner]

1) P2WSH addresses are longer compared to P2WPKH (and P2SH) because unlike those scripts that use HASH160 here SHA256 hash is used which is longer.

Is there any reason why we use SHA256 instead of HASH160? Why does this change only in multi-sig and not traditionally on 1-of-1 P2WSH addresses? Using 160 bits instead of 256 would make the transaction weight less.

Also, why does that happen only on P2WSH and not on P2SH? My multi-sig nested segwit addresses aren't longer than those that aren't multi-sig:

(Example of nested segwit multi-sig)

(Example of native segwit multi-sig)

We have the witness, which is just m + n*pubkeys + n + OP_CHECKMULTISIG as BrewMaster said

But what is the exact order of the public keys? Since we're hashing a message, then the public keys must be given on the same order. For example, in electrum when it asks me to enter my cosigners' keys, do I have to enter them in the same order when we made the wallet or has it a way to then sort it out in ascending order no matter the way I entered them?

[ranochigo]

Is there any reason why we use SHA256 instead of HASH160? Why does this change only in multi-sig and not traditionally on 1-of-1 P2WSH addresses? Using 160 bits instead of 256 would make the transaction weight less.

You mean P2WPKH?

The rationale behind using SHA256 for P2WSH instead of HASH160 is stated here:

The scriptPubKey occupies 34 bytes, as opposed to 23 bytes of BIP16 P2SH. The increased size improves security against possible collision attacks, as 2^80 work is not infeasible anymore (By the end of 2015, 284 hashes have been calculated in Bitcoin mining since the creation of Bitcoin). The spending script is same as the one for an equivalent BIP16 P2SH output but is moved to witness.

Also, why does that happen only on P2WSH and not on P2SH? My multi-sig nested segwit addresses aren't longer than those that aren't multi-sig:

Nested Segwit (Multisig or not) is P2SH, not P2WSH. The standard is defined before we've decided on this and is different, there is no need to change that. There is no need for us to introduce a longer Segwit address for P2WPKH as well.

But what is the exact order of the public keys? Since we're hashing a message, then the public keys must be given on the same order. For example, in electrum when it asks me to enter my cosigners' keys, do I have to enter them in the same order when we made the wallet or has it a way to then sort it out in ascending order no matter the way I entered them?

You need to do so in the exact order. As you've said, the script is hashed and changing the order also changes the hash. That is why we rely on the redeem script.

[BlackHatCoiner]

You mean P2WPKH?

Wait, P2WPKH stands for “Pay To Witness Public Key Hash” and an example is:

Code:

bc1qs9p7wkudkknd2u7p7rtmtxgpr9ca0z9wk6fl9y

P2WSH stands for “Pay To Witness Script Hash” and an example is:

Code:

bc1qrp33g0q5c5txsp9arysrx4k6zdkfs4nce4xj0gdcccefvpysxf3qccfmv3

Yes, my bad. P2WPKH is what I meant.

The scriptPubKey occupies 34 bytes, as opposed to 23 bytes of BIP16 P2SH. The increased size improves security against possible collision attacks, as 2^80 work is not infeasible anymore (By the end of 2015, 284 hashes have been calculated in Bitcoin mining since the creation of Bitcoin). The spending script is same as the one for an equivalent BIP16 P2SH output but is moved to witness.

So we have the witness script hash (P2WSH) and the witness public key hash (P2WPKH). This Bitcoin improvement proposal says that it will improve the security by increasing the size, from 160 bits to 256, because it'll be harder to find a collision. Isn't this a little ironic for the already existent address types? I'm trying to understand what's going on here, but it seems that I fail to.

If you increase the address size, then the transaction will also weight more, but it'll be more secure against a collision attack. But why did the developers change it to SHA256 since every other address type uses the HASH160? Making such announcement is like contending that HASH160 isn't strong enough, but it is. The fact that they did it exclusively for P2WSH seems weird to me.

Nested Segwit (Multisig or not) is P2SH, not P2WSH. The standard is defined before we've decided on this and is different, there is no need to change that. There is no need for us to introduce a longer Segwit address for P2WPKH as well.

Question: Is there a P2WPKH corresponding to P2SH? Or if I didn't place it properly: An address type that is longer than P2SH, but starts with “3”?

You need to do so in the exact order. As you've said, the script is hashed and changing the order also changes the hash. That is why we rely on the redeem script.

Oh, okay, thanks. So electrum doesn't sort them ascendingly.

[ranochigo]

So we have the witness script hash (P2WSH) and the witness public key hash (P2WPKH). This Bitcoin improvement proposal says that it will improve the security by increasing the size, from 160 bits to 256, because it'll be harder to find a collision. Isn't this a little ironic for the already existent address types? I'm trying to understand what's going on here, but it seems that I fail to.

If you increase the address size, then the transaction will also weight more, but it'll be more secure against a collision attack. But why did the developers change it to SHA256 since every other address type uses the HASH160? Making such announcement is like contending that HASH160 isn't strong enough, but it is. The fact that they did it exclusively for P2WSH seems weird to me.

Hash160 is secure by itself. P2SH is susceptible to collision (with birthday paradox) as the complexity is 2^80. This means that in the far future, it could be feasible for someone to be able to obtain a collision for a given script hash address.

It is not that big of a deal. P2WSH is far more efficient and Taproot is coming out as well. I'm not sure whether there would be any plans to phase out P2SH but that is likely not the case.

Question: Is there a P2WPKH corresponding to P2SH? Or if I didn't place it properly: An address type that is longer than P2SH, but starts with “3”?

Nope.

[BrewMaster]

i don't think we can say 160 bit is not secure, just that 256 bit is more secure. we still can't find a collision for 160 bit and it also won't be enough to find the collision the message that is being hashed (which would be the redeem script for P2SH) has to be a valid spendable script for it to work.

i also don't like this "By the end of 2015, 2^84 hashes have been calculated in Bitcoin mining" since the hashes are SHA256d not RIPEMD160 of SHA256.

[BlackHatCoiner]

Hash160 is secure by itself. P2SH is susceptible to collision (with birthday paradox) as the complexity is 2^80. This means that in the far future, it could be feasible for someone to be able to obtain a collision for a given script hash address.

Just googled what's the birthday paradox, but haven't understood properly how could this be used to increase your probability of finding a collision. It'd be off-topic to analyze it here, so I may create a new thread about it in the future. Anyway, thanks for the clarification.

i don't think we can say 160 bit is not secure, just that 256 bit is more secure. we still can't find a collision for 160 bit and it also won't be enough to find the collision the message that is being hashed (which would be the redeem script for P2SH) has to be a valid spendable script for it to work.

I may have misunderstood this. It wouldn't make sense to brute force invalid scripts, but valid ones. Why would someone brute force scripts that couldn't be redeemed?

[BrewMaster]

I may have misunderstood this. It wouldn't make sense to brute force invalid scripts, but valid ones. Why would someone brute force scripts that couldn't be redeemed?

we are talking about finding hash collision not brute forcing scripts but the bytes you hash to find the collision in a P2SH output is the bytes that are converted to a redeem script so they also have to be a valid script.

[vjudeu]

Just googled what's the birthday paradox, but haven't understood properly how could this be used to increase your probability of finding a collision.

If you want to get any two identical addresses from scratch, then birthday paradox applies here. But if you have some 160-bit address with someone else's coins, then of course birthday paradox does not help at all. So, theoretically you can switch from mining blocks with 80 zero bits to creating addresses and hope that you find a pair of keys after checking 2^80 keys, but it has no use when guessing already used addresses. Also, as nobody took 0.64 BTC reward from the transaction puzzle, I think someone would take them before we would see any collision in addresses.

[HCP]

You need to do so in the exact order. As you've said, the script is hashed and changing the order also changes the hash. That is why we rely on the redeem script.

Oh, okay, thanks. So electrum doesn't sort them ascendingly.

Actually... it does... and it doesn't...

Electrum uses "lexicographical ordering" as per BIP45: https://github.com/bitcoin/bips/blob/master/bip-0045.mediawiki#cosigner-index

But, because it is an HD version of Multisig... the ordering is of the "purpose keys'" of each co-signer (m/45') and is used to determine the co-signer index of each party, which then determines the order of the individual public keys when combining them to create an "address" script... this may result in individual scripts where the public keys are not ordered lexicographically.


As opposed to a "non-HD" multisig, where the combined public keys would (should?) always be lexicographically ordered.