Topic: Non-interactive schnorr signatures? (Read 203 times)
awesome. thanks!
This might be relevant to your interests: https://blockstream.com/2015/08/24/en-treesignatures/
It's written pre-taproot so that specific scripts/leafs you'd use wouldn't be the same, but it gives counts on enumerations of combinations. The linked implementation also constructs huge trees without needing to use a lot of memory and the same approach could be adopted for an implementation for taproot construction.
Also this: https://medium.com/@murchandamus/2-of-3-multisig-inputs-using-pay-to-taproot-d5faf2312ba3
It's written pre-taproot so that specific scripts/leafs you'd use wouldn't be the same, but it gives counts on enumerations of combinations. The linked implementation also constructs huge trees without needing to use a lot of memory and the same approach could be adopted for an implementation for taproot construction.
Also this: https://medium.com/@murchandamus/2-of-3-multisig-inputs-using-pay-to-taproot-d5faf2312ba3
Many thanks for the detailed reply.
You just made me realise something - actually the use case I had in mind does require accountability - in fact the N keys must be known and provable at time of locking and the M signers must be somehow deducible from the spend at time of spending (through hashing). So I guess the super-efficient threshold signatures are out of the question.
The tree of all possible signatures seems like it *could* work for what I want to do, although the tree could get very big too.
Would you be able to point me to any resources (code, medium, etc) which explains these trees in more detail?
You just made me realise something - actually the use case I had in mind does require accountability - in fact the N keys must be known and provable at time of locking and the M signers must be somehow deducible from the spend at time of spending (through hashing). So I guess the super-efficient threshold signatures are out of the question.
The tree of all possible signatures seems like it *could* work for what I want to do, although the tree could get very big too.
Would you be able to point me to any resources (code, medium, etc) which explains these trees in more detail?
Your question isn't quite clear enough for me.
For N of N no interaction for key creation is needed. The keys have to be delinearized to prevent rogue key attacks-- but musig just multiplies each key with a value computed from the hash of all the keys.
For N of M interaction and storage are fundamentally required, not just for schnorr but for other efficient threshold signatures too-- efficient being a key word.
But taproot has other ways of doing N of M: You can do a checkmultisig-like checksig-add, or you can make a tree of all the N-of-N subsets and get a script that scales linearly with the participant count. Like for a 2 of 3 with keys A, B, C... the valid possibilities are A&&B, B&&C, and C&&A.
You can even make the taproot root key one of these N of Ns, e.g. if one is most likely to get used. So essentially the size of the signature scales with the log of the probability that a given choice will be made. It's not quite as efficient but it avoids interaction and storage.
In many applications there is some sufficient N of N that is much more likely to be used than others, so in practice the efficiency gap may not be large. For example, if you have 2 of 3 with you, an offline key of yours, and some 2FA service then you normally expect the 2-of-2 involving you and the 2fa will be signing 99.99% of the time.
Unrelated to efficiency/storage-durability there is another big reason that many applications may not want to use efficient threshold signatures: They're unaccountable. If an unauthorized payment is made there is no way to prove which keys were involved.
The above alternatives to native thresholds are all inherently accountable.
A couple years back I proposed an alternative construction that I called polysig which is not supported in taproot today but could be added in a leaf version later which had size that was linear in the number of non-participating signers, relatively private (observers only learn the number of missing keys not the total number of keys) and completely accountable. But given that taproot can efficiently do the "A specific N of N" or "something else"-- there wasn't a lot of interest in going forward with completing the polysig work (e.g. formally proving its security).
For N of N no interaction for key creation is needed. The keys have to be delinearized to prevent rogue key attacks-- but musig just multiplies each key with a value computed from the hash of all the keys.
For N of M interaction and storage are fundamentally required, not just for schnorr but for other efficient threshold signatures too-- efficient being a key word.
But taproot has other ways of doing N of M: You can do a checkmultisig-like checksig-add, or you can make a tree of all the N-of-N subsets and get a script that scales linearly with the participant count. Like for a 2 of 3 with keys A, B, C... the valid possibilities are A&&B, B&&C, and C&&A.
You can even make the taproot root key one of these N of Ns, e.g. if one is most likely to get used. So essentially the size of the signature scales with the log of the probability that a given choice will be made. It's not quite as efficient but it avoids interaction and storage.
In many applications there is some sufficient N of N that is much more likely to be used than others, so in practice the efficiency gap may not be large. For example, if you have 2 of 3 with you, an offline key of yours, and some 2FA service then you normally expect the 2-of-2 involving you and the 2fa will be signing 99.99% of the time.
Unrelated to efficiency/storage-durability there is another big reason that many applications may not want to use efficient threshold signatures: They're unaccountable. If an unauthorized payment is made there is no way to prove which keys were involved.
The above alternatives to native thresholds are all inherently accountable.
A couple years back I proposed an alternative construction that I called polysig which is not supported in taproot today but could be added in a leaf version later which had size that was linear in the number of non-participating signers, relatively private (observers only learn the number of missing keys not the total number of keys) and completely accountable. But given that taproot can efficiently do the "A specific N of N" or "something else"-- there wasn't a lot of interest in going forward with completing the polysig work (e.g. formally proving its security).
I'm hoping somebody who has a better understanding of Schnorr signatures than me could answer this question. I have a basic understanding of EC math but have not studied Schnorr in great detail.
As I understand, Schnorr signatures as implemented in Taproot allow a script to be created which requires a m-of-n threshold signature in order to be spent.
My question is: is it possible for a completely non-interactive locking of funds? i.e. scriptPubKey. Of course this is is possible with traditional scripted threshold signatures, but as I understand Schnorr signatures requires the signatories to choose random numbers to multiply with their public keys in order to create a master public key. This master public key looks just like any other public key. Without these random numbers there is an attack that can be performed by adding the public keys together. Several questions arise from this:
1. Is it possible to choose the random numbers in a pseudo-random, deterministic way, yet still be safe?
2. Do the signatories need to remember the random numbers in order to create the Schnorr signatures at time of unlocking?
Apologies for my poor understanding of Schnorr. I'm in the process of learning about it.
I appreciate if anybody could help me with this question.
As I understand, Schnorr signatures as implemented in Taproot allow a script to be created which requires a m-of-n threshold signature in order to be spent.
My question is: is it possible for a completely non-interactive locking of funds? i.e. scriptPubKey. Of course this is is possible with traditional scripted threshold signatures, but as I understand Schnorr signatures requires the signatories to choose random numbers to multiply with their public keys in order to create a master public key. This master public key looks just like any other public key. Without these random numbers there is an attack that can be performed by adding the public keys together. Several questions arise from this:
1. Is it possible to choose the random numbers in a pseudo-random, deterministic way, yet still be safe?
2. Do the signatories need to remember the random numbers in order to create the Schnorr signatures at time of unlocking?
Apologies for my poor understanding of Schnorr. I'm in the process of learning about it.
I appreciate if anybody could help me with this question.
Jump to: