Bitcoin Forum
October 29, 2020, 11:20:29 PM *
News: Latest Bitcoin Core release: 0.20.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Non-interactive schnorr signatures?  (Read 110 times)
unsigned_long_long
Jr. Member
*
Offline Offline

Activity: 38
Merit: 1


View Profile
August 21, 2020, 05:11:42 PM
 #1

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.
1604013629
Hero Member
*
Offline Offline

Posts: 1604013629

View Profile Personal Message (Offline)

Ignore
1604013629
Reply with quote  #2

1604013629
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1604013629
Hero Member
*
Offline Offline

Posts: 1604013629

View Profile Personal Message (Offline)

Ignore
1604013629
Reply with quote  #2

1604013629
Report to moderator
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 3220
Merit: 4416



View Profile
August 22, 2020, 05:00:30 AM
Merited by Welsh (8)
 #2

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).


unsigned_long_long
Jr. Member
*
Offline Offline

Activity: 38
Merit: 1


View Profile
August 22, 2020, 02:07:43 PM
 #3

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?
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 3220
Merit: 4416



View Profile
August 22, 2020, 05:39:20 PM
Last edit: August 22, 2020, 06:16:14 PM by gmaxwell
 #4

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
unsigned_long_long
Jr. Member
*
Offline Offline

Activity: 38
Merit: 1


View Profile
August 22, 2020, 08:10:29 PM
 #5

awesome. thanks!
Pages: [1]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!