Schnorr signature and multi-sig overview & guideline

[AndrejMitrovic]

Overview

In the BOA blockchain we want to be able to support several types of signatures:

1. Schnorr single-party signature. This is the simplest form of signature using Schnorr, where one person owns their key and uses it to sign a message.
2. Schnorr multi-signatures. This supports signatures of the form: 1 of 1, 2 of 2, 3 of 3, and so on. This is called an n-of-n scheme, because the n is the same on both sides. This means if 3 people want to collaborate on signing a message, they must combine their public keys into a single public key, and all 3 of their signatures must be combined.
3. Threshold multi-signatures. This is called a k-of-n scheme, because the number of signers can be smaller than the number of total participants. For example, 1 of 2, 2 of 3, 2 of 4, 3 of 4, 4 of 4, or any combination where k <= n.

Curve and signature

We use Curve25519 and not Secp256k1. There is an open issue about changing our curve to Secp256k1, but as of this time it has not been scheduled for development: #207

Our signature signing consists of the following steps:

• Retrieve the Seed. For example "SCT4KKJNYLTQO4TVDPVJQZEONTVVW66YLRWAINWI3FZDY7U4JS4JJEI4".
• The seed will then contain the secret.
• Convert the seed's Secret into a Scalar so it can be used with Schnorr. You can use libsodium. You can call this Scalar x.
• Extract the Point out of the Scalar. You can use libsodium for this. You can call this Point X.
• Generate a new random nonce Scalar. You can use libsodium for this. Call this Scalar r.
• You will need to extract the Point out the scalar as well. As mentioned before you can use libsodium for this. Call this Point R.
• To sign a transaction you need to sign the Challenge. The Challenge is defined as Challenge = H(X ~ R ~ Transaction). This is described below:
• To calculate the Challenge use libsodium to hash the X (this is the Point of the Scalar of the Secret of the Seed used in signing), and hash the R (the Point of the Scalar of the random nonce), and hash the Transaction itself.
• Use libsodium to hash the three values together to create the Challenge. An example of using libsodium for hashing is here.
• To create the signature calculate the following: Scalar signature = r + (Challenge * x). Where as mentioned before r is the Scalar of the random nonce, and x is the Scalar of the private key.
• An example of a Schnorr signing routine in Agora is here: https://github.com/bpfkorea/agora/blob/b6c7b12b9c8dc3fbc88f6e3f8c8dbefd29af5a08/source/agora/common/crypto/Schnorr.d#L247
• You can also use the SendTxProcess tool to send a schnorr-signed transaction to an agora node. Please make sure to use the latest commit, this one. For example:

$ dub build -c client
$ ./build/agora-client sendtx -i "0.0.0.0" -p 2826 -t "0xb3aaf405f53560a6f6d5dd9dd83d7b031da480c0640a2897f2e2562c4670dfe84552d84daf5b1b7c63ce249d06bf54747cc5fdc98178a932fff99ab1372e873b"  -a 2000 -d "GDDGBCGFG7R6XH6F7IVDZ6WXO5SZRUN5PLTEZPVQEZH33FFNQECYMQ2E" -k "SCT4KKJNYLTQO4TVDPVJQZEONTVVW66YLRWAINWI3FZDY7U4JS4JJEI4" -n 0

Note: Please be aware that the random nonce is changed for every new signing, therefore the signature will appear different when signing the same transaction multiple times. This will not change the transaction's hash however.

Schnorr single-party signature

The support code has been implemented in the ECC.D and Schnorr.d modules.

As of today (2020-12-18), the v0.x.x branch does not use Schnorr for validating Transaction signatures yet!
The v0.x.x branch currently uses EdDSA for validating the signatures, as seen in the Key.d module.

The flash-layer branch does use Schnorr. It replaced EdDSA Transaction signature validation with Schnorr signature validation, as can be seen in the Engine.d module.

Schnorr multi-signatures

This is the n-of-n signature scheme where the number of participants is always the same as the number of signers.
For example, 1 of 1, 2 of 2, 3 of 3, 4 of 4, and so on.

Validating these signatures is the same as validating single-party signatures.
That means the execution engine already supports these signatures.

However, creating these signatures is complex and has security and safety implications.
Please read the Creating Schnorr multi-signatures section below for more information.

Note: A 2 of 4 signature is not a multi-signature, it is a threshold multi-signature described in the next section.

Threshold multi-signatures

This is the k-of-n signature scheme. In this case the number of signers can be less than the number of total participants.
For example, if Alice, Bob, and Charlie want to create a 2 of 3 spending condition, it will require the signatures of: Alice and Bob or Bob and Charlie or Alice and Charlie.

There are two ways of supporting threshold signatures:

1. With a special opcode such as CHECK_MULTI_SIG. It is implemented in Bitcoin. It is also implemented in Agora PR #1429. This is a non-interactive scheme. It is highly secure, but a little bit innefficient.
2. Using a dedicated threshold signature creating scheme which produces a single signature. This signature would then be validated in the sam way as a regular Schnorr single-party signature.

CHECK_MULTI_SIG for simple threshold signatures

In Agora PR #1429, we've implemented the CHECK_MULTI_SIG opcode. This allows highly-secure but slightly inneficient threshold signatures. This adds support for k of n signatures.

The way they work is simple. The lock script of an Output contains the list of public keys and the required count of signatures.

For example:

2 Key(0xAA) Key(0xBB) Key(0xCC) 3

Here 3 is the total number of participants, followed by the list of public keys on the left.
To the left of that is 2 which is the required number of signatures.

Assume that each user has their own signature, for example:

• Alice: 0x1234
• Bob: 0x2345
• Charlie: 0x4567

Then, the Input unlock script in the Transaction can be any of these:

# Alice and Bob provided the signature
Sig(0x1234) Sig(0x2345)

# or: Bob and Charlie
Sig(0x2345) Sig(0x4567)

# or: Alice and Charlie
Sig(0x1234) Sig(0x4567)

This scheme is non-interactive, which means that the users do not have to interactively pick a single nonce for their signatures.
Instead, each user can use their own nonce. Nonces are important because they must be random in order to be secure.

Benefit:

• Highly secure

Drawback:

• It is innefficient on the blockchain. Instead of having a single 64-byte signature there may be several 64-byte signatures as well as the list of 32-byte keys. This is why in the Engine we have temporarily limited these signatures to a maximum of 5 keys and 5 signatures.
• Validation is slower. Each key must try to be validated against a signature. The example validation is pasted below:

// if there are no sigs left, validation succeeded.
// if there are more sigs left than keys left it means we cannot reach
// the minimum required signatures as there's not enough keys to
// compare with.
while (sigs.length > 0 && sigs.length <= keys.length)
{
    if (Schnorr.verify(keys.front, sigs.front, tx))
        sigs.popFront();

    keys.popFront();
}

Dedicated threshold signature creating scheme

A more efficient way of adding support for threshold signatures is to use a dedicated scheme which produces a single Schnorr signature.
However, most implementations which currently exist are experimental and may not be proven secure yet.

This is why we've decided to implement CHECK_MULTI_SIG.

MuSig

MuSig is a scheme of interactively creating a multi-signature, and creating a single resulting Schnorr signature
which can be validated in the same way as a normal single-party schnorr signature.

Therefore Agora already supports validating such signatures.

This scheme supports n-of-n signatures, and not k-of-n.

What is MuSig for? Why do we need it? Can't we just use CHECK_MULTI_SIG?

MuSig is a way of creating an n-of-n multi-sig which generates a single schnorr signature.
Since this is a single signature, it's very efficient to store on the blockchain.
And it's also very efficient to validate.

Briefly, the scheme works as follows:

• Each user generates their own random nonce number R.
• Each user shares the hash of their nonce to the other users. This is called a commitment. They do not reveal R. They reveal hash(R).
• The users collaborate on creating the message. In our example this is a Transaction.
• If everybody agrees on this Transaction then they proceed to share their actual R nonces. The R is the preimage of hash(R). This is why hash(R) is called a commitment, and R is called the preimage.
• Each user signs the Transaction using their own R, and shares their partial signature to each other.
• The signatures are then combined into a single Schnorr signature.

Why do they not reveal their R, but instead they initially reveal only the hash of it?
Because, if an attacker knows all of the R's in advance they could generate a transaction with a very specific hash,
which can end up revealing the private key of a user if they use that R during signing.

See the Pre-sharing nonce commitments section in this article for more information.

Benefits:

• It generates a single Schnorr signature. The transaction output lock does not need to use CHECK_MULTI_SIG. The signature is small, it only contains the combined public key (32 bytes) and the combined signature (64 bytes).

Drawbacks:

• It is very interactive. The users must interact over the network to share their commitment and then later their R nonces.
• It must be implemented properly. If the nonces are reveald prematurely, it can lead to an attack where the attacker could steal the user's private key.

Conclusion

• Single-signer schnorr validation is supported in Agora. Multi-sig n-of-n validation is also supported, because it is the same
  as validating a single-signer schnorr signature.
• Threshold-sig k-of-n schnorr validation is supported by the CHECK_MULTI_SIG opcode.

If we want efficient multi-sig N-of-N which produces a single signature we would require the wallet to use MuSig.

For threshold k-of-n signatures the wallet would either have to use CHECK_MULTI_SIG,
OR they would need to find an alternative scheme which supports k-of-n.