[bitcoin-dev] Multi party Schnorr Rust implementation

Anthony Towns aj at erisian.com.au
Wed Nov 28 10:49:46 UTC 2018

On Tue, Nov 27, 2018 at 10:33:30PM -0800, Devrandom via bitcoin-dev wrote:
> Are there any candidates for non-interactive threshold signatures?  Interactive
> signatures are not very suitable for air-gapped use cases.

I think you can work around this to some extent by "batching" signing


For interactive multisignatures (threshold or not), the protocol is:

   produce secret nonce r, calculate public nonce R=r*G
   everyone shares H(R)
   everyone shares R, checks received values match received hashes
   everyone calculates s=r+H(R',P',m)*p, shares s

For deterministic nonces, you generate r=H(p,m) based on the message
being signed and your private key, so can only start this process when
you start signing, and the sharing rounds mean interactivity.


But you don't strictly need deterministic nonces, you just have to never
use the same nonce with a different message. If you arrange to do that
by keeping some state instead, you can calculate nonces in advance:

phase 1:
    produce secret nonces r1..r1024, calculate R1..R1024
    share H(R1)..H(R1024)

phase 2:
    store other parties hashes, eg as H1..H1024
    share R1..R1024

phase 3:
    check received nonces match, ie H(R1)=H1, etc

phase 4:
    request to sign msg m, with nonce n
    if nonce n has already been used, abort
    mark nonce n as having being used
    lookup other signer's nonces n and sum them to get R'
    calculate s = rn + H(R',P',m)*p
    share s

That way you could do phases 1-3 once, and then do 1024 signatures during
the month on whatever your current timetable is.

You could also combine these phases, so when you get a signing request you:

   * receive msg to sign m, n=4; everyone else's R4, H(R5)

   * check  H(R4) = previously received "H(R4)"
   * calculate R4' by summing up your and everyone's R4s
   * bump state to n=5
   * do the signature...

   * send sig=(s,R4), R5, H(R6)

which would let you have an untrusted app that does the coordination and
shares the nonces and nonce-hashes, and getting all the needed air-gapped
communication in a single round. (This is effectively doing phase 3 and
4 for the current signature, phase 2 for the next signature, and phase
1 for the signature after that all in one round of communication)

That seems almost as good as true non-interactivity to me, if your signing
hardware is capable of securely storing (and updating) a few kB of state
(which is probably not quite as easy as it sounds).


More information about the bitcoin-dev mailing list