schnorr signature weakness, why did they do it this way?

[larry_vw_1955]

 i think the legacy bitcoin multisig actually require m of n signatures because it checks each signature. schnorr doesn't.  it just checks the aggregated public key. seem like a fake multisig.

[pooya87]

It still requires multiple signatures to be spent.
The single public key that is revealed and used for verification doesn't have a known private key and it can not be guessed or computed which means there is no weakness here.

[achow101]

First of all, Schnorr signatures do not require that multisigs must use key aggregation. You can still have a traditional multisig where keys are listed explicitly and each key has a signature. There's nothing that prevents that. Specifically with Taproot, OP_CHECKMULTISIG was replaced with OP_CHECKSIGADD because it is much more efficient. Taproot also allows for more keys to be in the multisig and OP_CHECKSIGADD allows very large multisigs to be efficiently verified.

Furthermore, Schnorr signature merely allow key and signature aggregation schemes to work. This is just a property of the algorithm. There is no required method for key aggregated multisigs. There are many different ways you could do key aggregation; some are unsafe and some are safe (with rigorous mathematical proofs to back them up).

[ranochigo]

Legacy Bitcoin multisig is more vulnerable to collisions being able to defraud the other parties. Not practical currently but might be in the future, which is why P2WSH came with a larger collision resistance. So, not really as secure as you think it is.

For the security proofs, I've linked it in the post in your other thread a few hours ago.

[gmaxwell]

checks the aggregated public key. seem like a fake multisig.

That is extremely vague. Do you expect a useful reply?  Your non-question post seems like a fake question.

In reality the old checkmultisig is the fake multisignature:  It's not a true multisignature but one faked by just having a bunch of regular signatures and applying some logic after the fact.

You can still use that kind of explicit fake multisig if you want to, but but it's inefficient.  M*32 bytes + N*64 bytes ... instead of just 32+64 bytes. You can also do other variants with different tradeoffs.  Like a tree of N choose M leaves (size 32*ceil(log2(n choose m))) plus a M of M signature (size 32+64).


Any M of N multisig is only as secure as the N-Mth most secure key in it.  Same is true for a fake-multisig as it is for a true threshold signature.

[larry_vw_1955]

That is extremely vague. Do you expect a useful reply?  Your non-question post seems like a fake question.

In reality the old checkmultisig is the fake multisignature:  It's not a true multisignature but one faked by just having a bunch of regular signatures and applying some logic after the fact.

Well congratulations you just summed up what true multisignature is. But you call it "fake". Not sure why. Multisignature needs as you said "a bunch of regular signatures", in fact it needs M of them. And then it also needs to apply "logic after the fact" as you also pointed out, to figure out that out of the N public keys that M of the signatures belong to N of those public keys. I think that's really the only way you could really ensure that M of the N private keys were used. There's no other way.

You can still use that kind of explicit fake multisig if you want to, but but it's inefficient.  M*32 bytes + N*64 bytes ... instead of just 32+64 bytes. You can also do other variants with different tradeoffs.  Like a tree of N choose M leaves (size 32*ceil(log2(n choose m))) plus a M of M signature (size 32+64).

It's not always about transaction sizes. Some people use multisignature for the increase in security it is supposed to provide them. But if there's a way to shortcut that then it's all for naught.

Any M of N multisig is only as secure as the N-Mth most secure key in it.  Same is true for a fake-multisig as it is for a true threshold signature.

What do you mean by "fake multisig" again? Love to hear you define it and explain more. Because you really know your stuff.

Legacy Bitcoin multisig is more vulnerable to collisions being able to defraud the other parties. Not practical currently but might be in the future, which is why P2WSH came with a larger collision resistance. So, not really as secure as you think it is.

For the security proofs, I've linked it in the post in your other thread a few hours ago.

I'm assuming when you say collisions you mean hash collissions? never thought of that. so i guess even the legacy multisig is no more secure than a single public key. that's the problem with multisig in general is it works but u can't be sure there's not another way to spend the funds other than YOUR way which is the m of n private keys. until they get something like that, i guess it's not true multisig ever. kind of disappointing that bitcoin has this limitation of such a small address space what is it 2^160?

well actually i guess here's another question though, just because you have a multisig address that starts with 3 I'm not sure how someone would go about finding a script that would hash to that. wouldn't it be harder than just finding a private key for a bitcoin address that starts with a 1? how would you even know something exists that hashes to the thing that starts with 3 other than the script you created it with? and then even if you could do that would it be recognized as a valid script by the network? it seems like it would be really hard not sure how hard though. but probably alot harder than brute forcing a single btc 1 address.

[moderator's note: consecutive posts merged]

[ranochigo]

I'm assuming when you say collisions you mean hash collissions? never thought of that. so i guess even the legacy multisig is no more secure than a single public key. that's the problem with multisig in general is it works but u can't be sure there's not another way to spend the funds other than YOUR way which is the m of n private keys. until they get something like that, i guess it's not true multisig ever. kind of disappointing that bitcoin has this limitation of such a small address space what is it 2^160?

It affects multisig, where multiple entities are involved. By birthday paradox, the attacker can run through 2^80 combinations of their public keys with the other party's public key and produce a collision. The victim would be left in the dark, which is why we've pre-emptively introduced SHA256 with P2WSH.

Multisignature needs as you said "a bunch of regular signatures", in fact it needs M of them. And then it also needs to apply "logic after the fact" as you also pointed out, to figure out that out of the N public keys that M of the signatures belong to N of those public keys. I think that's really the only way you could really ensure that M of the N private keys were used. There's no other way.

Not really. The conditions are only required provided that the redeem script that you're providing in the transaction states so. If I were to somehow give a redeem script which hashes out to the corresponding hash in the UTXO, then the conditions in that redeem script is considered for unlocking those outputs. For example, if I were to somehow have a redeem script which is a 2-of-3 Multisig and its hash somehow is the same as another completely different P2SH with differing requirements, then by fulfilling the former redeem script requirements, I can spend the outputs tied to the latter P2SH script.

It is a totally hypothetical and incredibly unlikely scenario, but it proves that for a specific P2SH, we can define an alternative script to bypass the requirements in the first place completely.

[larry_vw_1955]

It is a totally hypothetical and incredibly unlikely scenario, but it proves that for a specific P2SH, we can define an alternative script to bypass the requirements in the first place completely.

I agree it does sound very unlikely to do, no one would probably waste resources trying to do that but is there anyway that security issue could be fixed? I seem to have an issue with bitcoin using such short addresses where collissions can be an issue but no matter what the size of the address space, those could always happen. Seems something more fundamental would have to be done to fix that.

It still requires multiple signatures to be spent.

The single public key that is revealed and used for verification doesn't have a known private key and it can not be guessed or computed which means there is no weakness here.

I was looking at this cowboy's video and he had some nice slides showing schnorr multisignature and from looking over that, it seemed like the aggregated public key had a corresponding aggregated private key although in the algorithm it is never computed since no one is supposed to know all the individual private keys. But if you have all N private keys then you can compute the "master private key" which it seemed like you could use to do transactions and bypass the need for multisig all together. Again, that's just what it looked like. But someone confirmed that is true in the other thread. But they said it's of no consequence since it would be infeasible to find it.

The thing is though, if that's the way it is then an attacker benefits anyway since they are looking for something they know exists.

Maybe the NSA is going to use that master private key as a backdoor? what do you guys think?

[moderator's note: consecutive posts merged]

[kaggie]

By birthday paradox, the attacker can run through 2^80 combinations of their public keys with the other party's public key and produce a collision. The victim would be left in the dark, which is why we've pre-emptively introduced SHA256 with P2WSH.

Wouldn't birthday paradox only apply if all people involved are searching, and the rewards of the finds are equal?
But, as you say, the search space is smaller than the key space (2^80?). The public address space is smaller than the key space (2^160?), so you don't really need to search through the entire private key space for collisions. Maybe this is why the key space was made to be so large.

Maybe public addresses should be longer if the birthday paradox applies? But as you've said, there is SHA256 and P2WSH.

Maybe the NSA is going to use that master private key as a backdoor? what do you guys think?

There have been flaws with parts of bitcoin's software, such as poor random generation in early versions. But no, I don't think there is a backdoor in the main methods (for addresses that have never sent a transaction, were generated purely randomly, etc; I don't know enough about multisig), otherwise I can think of a number of public addresses that would have been drained by now.

[ranochigo]

I agree it does sound very unlikely to do, no one would probably waste resources trying to do that but is there anyway that security issue could be fixed? I seem to have an issue with bitcoin using such short addresses where collissions can be an issue but no matter what the size of the address space, those could always happen. Seems something more fundamental would have to be done to fix that.

No. It is not a security issue. You'll probably have to see the post referenced below to understand what I'm talking about in relation to the Multisig and normal P2SH.

Wouldn't birthday paradox only apply if all people involved are searching, and the rewards of the finds are equal?
But, as you say, the search space is smaller than the key space (2^80?). The public address space is smaller than the key space (2^160?), so you don't really need to search through the entire private key space for collisions. Maybe this is why the key space was made to be so large.

Maybe public addresses should be longer if the birthday paradox applies? But as you've said, there is SHA256 and P2WSH.

Collision attack is very different from pre-image attack. In trying to find a collision, we would be finding two of the same hashes when we're searching for the keys. The hash that will be found is completely arbitrary, and the theoretical attack scenario is better described here: https://bitcointalk.org/index.php?topic=5348160.msg57410551#msg57410551.

If you are looking for any specific addresses, you will need to do a second pre-image attack (2^160), so we're finding the inputs that would result in a specific set of addresses. Birthday probability doesn't apply here because we're not looking for random collisions, but inputs that would result in specific addresses.

[gmaxwell]

Attacks against ECDLP allows you to solve multiple ECDLPs for only very slightly more work.

The security increase from bitcoin multisig comes because some of the participants may be untrustworthy or because they're unable to keep control of their private keys (hacks, etc.).  This same benefit is also provided by true multisignatures.

Multisig is an pre-existing term in cryptography that predates bitcoin, E.g.:

Multi-signatures allow multiple signers to jointly authenticate a message using a single compact signature.

The bitcoin checkmultisig fakes a traditional mutisignature with a collection of single signatures because defects in ECDSA (which exist because ECDSA was created to avoid schnorr's patent) make it extraordinarily complicated to implement a true multisignature with it.  With Schnorr, you don't have to fake it.

However, in taproot you still can use a collection of single signatures if you want. Why would you? Not for security but because a schnorr multisignature requires two passes while a fake multisignature can be done in a single pass, or simply because you have software for one and not the other.

If you were using multisig with all the private keys just on a single device-- that's snake oil. It isn't practically increasing your security.

Some people use multisignature for the increase in security it is supposed to provide them. But if there's a way to shortcut that then it's all for naught.

Some people? You mean ... all people, right?  There isn't a way to shortcut it: You can't sign without getting access to the requisite private keys. (assuming the hardness of the hash functions and discrete log problem, of course).

[larry_vw_1955]

Attacks against ECDLP allows you to solve multiple ECDLPs for only very slightly more work.

The security increase from bitcoin multisig comes because some of the participants may be untrustworthy or because they're unable to keep control of their private keys (hacks, etc.).  This same benefit is also provided by true multisignatures.

Well yeah, I mean, what you said is true. But the real security increase is supposed to come from there being no other way to spend the money unless M of N private keys sign. There can't be any shortcuts or hacks.

As long as hashes are going to be used to represent spending conditions, well, I couldn't consider that to be real multisignature. Real multisignature would be getting rid of P2SH and using the actual redeem script as the payment address. yes it might be big but then I don't think there would be any other way to spend the money unless M of the N private keys belonging to the public keys were used to sign. Not even a theoretical way to get around that. That's real multisig.

I guess there's a difference between "practical/real world" security which deals with things like how people store their private keys and such vs the mathematical underpinnings of how the setup works on the blockchain and what risks there are with that. I'm talking about the latter. Don't care about the former.

[gmaxwell]

If you can compute a second preimage of a arbitrary hash you can already steal any coin, e.g. by replacing the transaction someone signed by another transaction, or even by replacing transactions in the ledger. Bitcoin has an absolute and total dependency of the second preimage security of SHA256.  Nor would it be particularly feasible to construct an alternative system which didn't have similar security requirements.

Fortunately the security history of well studied hash functions against second preimage attacks is extremely good.  Even old and busted hash functions like MD5 and SHA1 still stand up pretty well to second preimage attacks.

[larry_vw_1955]

If you can compute a second preimage of a arbitrary hash you can already steal any coin, e.g. by replacing the transaction someone signed by another transaction, or even by replacing transactions in the ledger. Bitcoin has an absolute and total dependency of the second preimage security of SHA256.  Nor would it be particularly feasible to construct an alternative system which didn't have similar security requirements.

I think the chances of that would unimaginably small.  Just because someone finds a second preimage doesn't mean it would be in the format of a valid transaction or any meaningful format at all. How many matches would you have to find before one of them did the thing you needed? And the other thing is, there's no guarantee that a 2nd preimage of some hash even exists. I'm pretty sure about that but I could be wrong but I dont think so...

  Nor would it be particularly feasible to construct an alternative system which didn't have similar security requirements.

But it would be fun, no? Not having to rely on hashes for sending and receiving money. Seem like a pipe dream in crypto. Hashes are like entropy destroyers. they make you lose information and you can never get it back.

[moderator's note: consecutive posts merged]

[garlonicon]

I think the chances of that would unimaginably small.  Just because someone finds a second preimage doesn't mean it would be in the format of a valid transaction or any meaningful format at all.

Not that small as you may think. Many formats have some dummy fields like comments, Script has OP_RETURN and then you can put any 80 bytes after that, there are ways to construct your transaction in a way where you will have a lot of space for putting any bytes you want. Take http://shattered.io/ for example, they created two PDF's that are different, valid files in this format, and both have the same hash for SHA-1. If you reduce SHA-256 to the first 16 rounds, you can clearly see, how theoretically that attack could be mounted. Of course in case of SHA-1 it was just a collision, not a second preimage, but still, in most formats you can mount that attack by putting random (but correct from consensus point) data in the right place and attack it in this way.

Not having to rely on hashes for sending and receiving money.

In such system you would have to replace hash-based mining with something else, for example ECDSA-public-key-based mining. So, mining could be replaced (if you reject G/2 from valid points, start from some other point or change it to find leading ones instead of leading zeroes, etc.), but what about merkle tree construction? With no hashes, you will have just point addition or point multiplication, how do you want to construct that tree in a secure way and make it impossible to replace transactions? Even things like Pedersen Commitments use hashing. More than that: even signatures use hashing! So, if you have just ECDSA and you want to make a signature, how do you want to do that without hashing?

[gmaxwell]

Because the hashes are much shorter than the input data there an infinite number of second preimages for almost any hash. If that weren't true it would result in statistical discrepancies in the hash function that would distinguish it from random.

[Shymaa-Arafat]

I'm just replying about whether it's similar or not to the Birthday Paradox

In general, no matter what the scheme u r using afterwards, if u have N keys/signatures, X of which r compromised (malicious/hacked/...), Then when choosing M out of N:
Prob(all M is correct)=
[(N-X)/N]*[(N-X-1)/(N-1)]*...*[(N-X-M+1)/(N-M+1)]
=[(N-X)(N-X-1)...(N-X-M+1)]
/[N(N-1)...(N-M+1)]


That's little similar how the Birthday Paradox is calculated, the prob of no collision is:
For no 2 people in a group of size "M" have same Birthday (N
Prob(all different)= 1* 364/365*363/365*...*(365-X+1)/365]
(The 1st person can have any birthday, the 2nd only 364 for this to be wrong, the 3rd only 363,..)
Then it was found out that X as small as 25 can make this probability < 0.5

Only difference here is the number of total possible days (the population we withdraw from) don't change it is always 365, but in signatures the population is like balls decreases by 1 with each withdraw

[NotATether]

But if you have all N private keys then you can compute the "master private key" which it seemed like you could use to do transactions and bypass the need for multisig all together.

Maybe the NSA is going to use that master private key as a backdoor? what do you guys think?

The aggregated private key is never computed by the signing algorithm of Schnorr multisignatures, because it's not necessary. Only the aggregated public key and the aggregated r,s pair. Specifically:

(assume Xi are the public keys and xi are the private keys)

Call X the sum of the Xi points
Each signer chooses a random nonce ri, and shares Ri = riG with the other signers
Call R the sum of the Ri points
Each signer computes si = ri + H(X,R,m)xi
The final signature is (R,s) where s is the sum of the si values
Verification requires sG = R + H(X,R,m)X, where X is the sum of the individual public keys

So as you can see, there is only a need to compute "X = sum(Xi), R = sum(Ri), S = sum(Si)"

but never "x = sum(xi)".

When something is not computed then there's no state leaked into the program memory that can be inspected by adversaries.

I'm just replying about whether it's similar or not to the Birthday Paradox

In general, no matter what the scheme u r using afterwards, if u have N keys/signatures, X of which r compromised (malicious/hacked/...), Then when choosing M out of N:
Prob(all M is correct)=
[(N-X)/N]*[(N-X-1)/(N-1)]*...*[(N-X-M+1)/(N-M+1)]
=[(N-X)(N-X-1)...(N-X-M+1)]
/[N(N-1)...(N-M+1)]

...

The process of plugging random private keys to aggregate them into a multisignature is not similar to the birthday problem at all though, but your assumption does hold for calculating the probability of "rogue" keys in theory.

[gmaxwell]

The aggregated private key is never computed

And if you ever could compute it, then you have the contributing keys and could just spend the coin.

[Shymaa-Arafat]

The security increase from bitcoin multisig comes because some of the participants may be untrustworthy or because they're unable to keep control of their private keys (hacks, etc.).  This same benefit is also provided by true multisignatures.

My reply meant however the aggregated key is calculated, u have to calculate the probability of its input including a compromised key as described ( a way little Similar to calculating the probability of Birthday Paradox)
=[(N-X)(N-X-1)...(N-X-M+1)]
/[N(N-1)...(N-M+1)]

not just assume it would be (1-p) to the power M, for p=X/N the probability/ratio of compromised keys