So imagine you have a message that’s been signed with 100 different private/public key pairs. These signatures get combined into one aggregated signature. Now, let’s say the only things you’ve got are the aggregated signature, the original message, and one private/public key pair from those 100 used to create that aggregation.
Can you figure out if that specific private/public key pair actually played a role in the aggregated signature, or is that just not possible?
Yes, it is possible. If you can join signatures, then you can split them as well.
https://en.bitcoin.it/wiki/Schnorr
https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki
For example, let's assume, that you have some message:
And then, you have this signature:
Then, you have some public key, and you want to prove, that it contributed to the joined signature:
Now, you know, that the key "P1" also signed the message "e" with some "(R1,s1)" signature. And you also know, that there are other signers, if you subtract signatures:
And you can verify, that the subtracted part is also valid, if you try to check it in the same way:
But of course, you don't know, if "P1" or "P2" belongs to a single person. It can be a part of some larger group, which could be splitted further.
Your model is too simple. Let's prove, that Satoshi participated in your message:
Joined parts should not be used directly as a proof, by checking just your public key. You should instead hash all public keys, and put it into R-value, and then prove it, by revealing a commitment. In other case, you can prove, that anyone was a part of your multisig.
Well, it's not necessarily proof that you signed one of the signatures in the aggregated Schnorr, but just proof that you can sign it. But maybe someone has your key and then signed it.
To deterministically prove that it was indeed you who signed that particular signature, you'd need to use something like BIP 322 and paste some PGP signed message output inside it along with date, block hash etc.
This "nested signature" allows people with your PGP key or any other alternative form of cryptographic identification to know that in fact, you created the associated transaction.
Of course, it can be placed inside an aggregated Schnorr signature if the BIP is implemented, and all other parties create their own as well.
I appreciate the responses so far. I realize my initial question wasnt detailed enough, so Id like to expand and clarify. Im working with Schnorr signatures, specifically in the context of multisignatures.
Assume the following setup:
A publicly known message (it could be any message, or even empty).The message is signed by 100 private/public key pairs, each using a deterministic nonce value.The signatures are aggregated into a single aggregated signature.The public keys are aggregated into a single aggregated public key.All information is public except for the complete set of private/public key pairs that contributed to the aggregated signature and aggregated public key.
The question is: Given the available public information, is it possible to verify whether a specific private/public key pair contributed to the aggregated signature or whether a private/public key pair contributed to the aggregated public key?
If this verification is possible, how can I achieve it using the secp256k1 library?
From an earlier suggestion, it seems I might need to extract the s value from the 64-byte aggregated signature (which includes both R and s) and modify it appropriately. Additionally, I would need to remove the contribution of the specific public key (noting that the corresponding private key and nonce are known) from the aggregated public key, and then verify against the modified aggregated signature and the modified aggregated public key. Or is there a better method using the secp256k1 library? Any guidance would be greatly appreciated.
Can you derive it? If you can, then it is half of the job done, because if people cannot pick any R-values they want, then you can split the signature, by using derived R-value.
Aggregated public key has to be public, because you have to verify, that the whole multisig is correct. So, you may not know P1, P2, P3, ..., P100, but you have to know "P=P1+P2+P3+...+P100", because this P-value is used to generate a Taproot address for the whole group.
A signature is just a multiplication and addition between the aggregated public key of all participants (P-value), and aggregated signature nonce (R-value). If you can split the joined signature into "P=AliceP+TailP" and "R=AliceR+TailR", then, there is only one matching s-value, meeting the equation "s=sAlice+sTail".
I guess you need both R and s, because "R=AliceR+TailR", and "s=sAlice+sTail". And then, if "AliceR" is deterministic, and you can derive it, then you can avoid the attack, described by Garlo Nicon.
You only have to verify two signatures: the full 100-of-100 multisig, and Alice's signature. The tail signature of 99-of-99 multisig will be correct, if those two will also be, and if joining those two parts will lead you to identical signature, as in 100-of-100 multisig.
It depends on the exact multisig implementation (because there is more than one way to do that, and I don't know, which one you will want to observe). It is technically possible to make proofs, that "Alice took part in this 100-of-100 multisig". But: if your model does not reveal any kind of proofs, and you can only see some Taproot address, spent by key, and you see only things, which are seen by all on-chain observers, then you cannot do that.
Because in general, it works in this way: you have a regular signature, where you don't know, if it is 100-of-100 multisig, or 2-of-2 multisig. And then, someone can give you some data, to reveal, that it is "at least 2-of-2 multisig" (or "exactly 100-of-100 multisig" in some models), and that Alice was there. But: if you don't have this additional data, then you don't know that.
It's heavily dependent on the code you use to make such aggregated signatures.
Static programs where you can literally type out all 100 private keys can be modified to make the 100-aggregated signature and a single signature for a given key.
But in a practical setting where the private keys are distributed across multiple users, then it's possible you will not have access to all of the private keys. Sure, maybe the software would make everyone send their public keys to a central server and each user can fetch all the keys from that, but it's also possible to send each user their own public key in a decentralized and interactive manner, and then incrementally construct an aggregated signature like this:
U1 => U2 => U3=> .... U100 => U1
So that no person knows more than three public keys at any time.
In that case, a third party wouldn't be able to verify outside participation by another party.
It really depends on your privacy requirements.
Thank you for the detailed insights and suggestions.
To make the discussion more concrete, I believe it would be best to present a practical example. This will outline all the data that is publicly available.
For clarity and practical implementation, I will use the data structures provided by the secp256k1 library.
Below is a general idea of how the data was generated. Note that this code is illustrative and not the exact implementation:
Here is the data generated for the example:
So, given the above data, what specific operations need to be performed to confirm that the public key: 024CBBD03BC9B079BC360A26A034A298EB4520333F87DA4A3D195F390B50B7BD27 contributed to the aggregated signature or the aggregated public key? Or that the secp256k1MusigPartialSignature EBFB1A3284DDE05BA570956916623030D11F266A8260A8C4F074190793F088E12EABB41F contributed to the aggregated signature?
In this case, the masterPrivateKey used is:
It is important to note that everything is known except the full set of private/public key pairs that contributed to the aggregated signature or public key.
Let's see how keys are aggregated:
Then, the aggregated hash is 9309c24c2bc0162de694d5f3a80e35cd17e7db4afd1994b86a1470dc4ea5bf57, if those three keys are sorted. Because SHA-256 is executed in 512-bit chunks, it is aligned in this way:
So, I guess by providing some in-between hashes, it could be possible to prove, that the aggregated hash contained a specific public key. For example, for the last key:
Of course, public keys are not-so-well-aligned, because they take 33 bytes, instead of 32, but still, picking any other keys will change the initialization vector from e4408850f10bfbab723cc28807ec49e0491d6a6750fff49c2b6358ec0ac4bc1a to something else. And picking any other data, would very likely not hash into 9309c24c2bc0162de694d5f3a80e35cd17e7db4afd1994b86a1470dc4ea5bf57. But: I still have to dig deeper into the code, to produce more detailed logs.
I assume at least some of my assumptions about SHA-256 are correct, because I found the same constants in the code:
https://github.com/bitcoin-core/secp256k1/blob/master/src/modules/musig/keyagg_impl.h#L64