Fetching contributors…
Cannot retrieve contributors at this time
104 lines (57 sloc) 16.5 KB

Schnorr Signatures

The Schnorr signature scheme [1] uses a cyclic group `G` of prime order `p`, a generator `g` of `G`, and a hash function `H`. It uses a random number private key `x`, and public key `X`, with `(x, X) ∈ {0, …, p-1} * G` where `X = g^x`. To sign a message `m`, the signer generates a random number integer `r` in `Zp` and computes the nonce `R = g^r_, c = H(X,R,m)` [2], as well as `s = r + cx`. The signature σ is the tuple `(R,s)` and this can be verified by `g^s = RX^c`.

Just like ECDSA, the Schnorr signature scheme is proven secure under the discrete logarithm assumption, defined as followed. Let `(G,p,g)` be group parameters. An algorithm `A` is said to `(t,ԑ)`-solve the DL problem w.r.t. `(G,p,g)` if on input a random group element `X`, it runs in time at most `t` and returns `x ∈ {0, …​, p − 1}` such that `X = g^x` with probability at least ԑ, where the probability is taken over the random draw of `X` and the random coins of `A`. [3]

MuSig

The MuSig paper [4] describes a simple and efficient multi-signature scheme based on Schnorr. Some of the benefits are key aggregation, signature aggregation and batch verification. The paper includes a security prove [5] in the plain public-key model, which is omitted in this paper.

MuSig is parameterized by group parameters `(G,p,g)` where `p` is a `k`-bit integer, `G` is a cyclic group of order `p`, and `g` is a generator of `G`, and by three hash functions. [6] The total signature size is `|G|+|p|`; the public key size `|G|`; and the private key size `|p|`.

Key Generation

Individual private keys `x_i` are generated with a true random number generator and the public keys `X_i` are computed with `X_i = g^x_i`. The `X_1` and `x_1` are individual keys of a specific signer; `X_2, …, X_n` are the public keys of the cosigners; and `L = {pubk_1 = X_1, …, pubk_n = X_n}` is a multiset of all public keys. For `i ∈ {1, …, n}`, the signer computes `a_i = Hagg(L,X_i)` and then aggregates all the individual public keys into the single “aggregated” public key `Ẋ = X_i for 1``X_i = n`, `Ẋ = product of X_i^a_i`.

Each individual signer has sole knowledge of the non-scarce information of the private key. Assuming that this secret is not shared with others and generated with a cryptographically secure random number generator, then only this individual can produce a signature that is valid for the given public key.

Signing

The signer has knowledge of aggregated `Ẋ`; the message `m` (in the context of Bitcoin `m` is the transaction according to the SIGHASH flag); and the multiset `L`. He generates another random integer `r_1` and computes the nonce of 'R_i for 1` ⇐ `R_i``n`, `R = product of all R_i`, and the commitment to that nonce `t_1 = H_com(R_1)`. The commitment `t_1` is shared with all cosigners, then in the next round of communication the nonce `R_1`, and we proceed with the protocol only if all `R` have been correctly committed for all `t_i = H_com(R_i)` with `i ∈ {2, …, n}`.

The signer computes `R for 1``R_i``n`, `R = product of all R_i`, `c = H_sig(Ẋ,R,m)` , and `s_1 = r_1 + ca_1x_1 mod p` , `s_1` is send to all cosigners. After all `s_2, …, sn` have been received, the signer computes let `s for 1``s_i``n`, `s = sum of all (s_i mod p)'. The signature is `σ = (R,s)`.

Only those who have securely generated the individual private key can produce a valid individual signature over a message with very little effort. Without the knowledge of the private key, it is computationally infeasible to produce a correct signature. Once the signing algorithm is calculated, it cannot be undone, as the specific information of the signature is manifested. However, when the signature is not shared with others, nobody can verify it.

Verification

The verifier has a multiset of public keys `L`, a message `m`, and a signature `σ`. With this public information, the verifier computes `a_i`, `Ẋ` and `c`. The signature is valid only if `g^s = R``R = 1``n`, `R (product of X_i^(a_i c)) = R Ẋ^c`. Due to key aggregation, the verification is similar to the standard Schnorr scheme, and secure variants of the MuSig scheme are discussed in the original paper [7].

When given a Bitcoin transaction as a message as well as a signature, then any full node can verify conclusively that the signer had knowledge of the private key. According to Nakamoto Consensus, this means that an existing UTXO can be spend and a new UTXO is created. The transaction will be included in a block of the time chain.

Interactive Key Aggregation

Each cosigner generates their own individual private public key pair `(X,x)`, and only that cosigner has knowledge of this secret key `x_i`. In the first round of communication, all cosigners share their public keys, any verifier can build the multiset `L` and calculates `a_i` by hashing `L` and `X_i`. For `a_1`, the hash pre-image contains all the public keys once, but `X_1` twice. The aggregated public key `Ẋ for 1``Ẋ_i = 1``n`, `Ẋ = product of X_iâ_i` is indistinguishable from any other Schnorr public key. If only `Ẋ` is known, then the individual public keys `X_i` cannot be computed. Thus, the on-chain commitment to this MuSig is the exact same virtual size as any other public key commitment. Therefore, MuSig is both a privacy and scalability improvement. Further, anyone with knowledge of all the public keys `X_i` can compute [and thus send bitcoin to] this aggregated public key `Ẋ`, without collaboration from the peers.

Interactive Signing

Although there is one aggregated public key `Ẋ`, there is no “aggregated private key”. In order to produce a valid signature while defending against the rogue key attack [8] [9], all cosigners have to collaborate in a three step [10] signing ceremony. First, sharing a nonce commitment `t_i`, then the nonce `R_i`, and finally the partial signatures `s_i`. Only when all `i` partial signatures are available can the coordinator produce the valid signature `σ` which contains the aggregated nonce `R` and `s` part of the signature. If one cosigner is unavailable to communicate the signature, then there can not be a valid signature.

Verification

Since the aggregated public key and signature look identical to an individual public key, the verifier knows only that [all of] the signer[s] has [have] agreed and collaborated with that signature and thus the spending of the bitcoin, but he does not know whether this is only one single key pair, or several key pairs in aggregation. Further, this single public key and signature could be a collaborative taproot [11] or graftroot [12] transaction, a collaborative lightning network channel close, or a scriptless script atomic coin swap [13]. This plausible deniablity is a great enhancement to the fungibility of UTXOs and strengthening Bitcoins overall privacy aspects. Although lots of the spending logic is abstracted from the time chain, yet every full node can still verify absolutely if the spending condition, whatever it is, was completely valid. There no false positives or negatives, a UTXO can only be spend with a valid witness script.

Contrarily to the script based multi signature, in Schnorr MuSig only one aggregated public key is committed to the time chain, and a valid signature can only be computed when all 'm' signers collaborate on the shared message. Without any further detail than the aggregated public key and signature, any full node can verify if the spending attempt is valid or not. There are no additional security and node verification assumptions compared to any other single signature transaction.

Non-Simulated Shared Ownership

In a Schnorr 3-of-3 MuSig ceremony, Alice Bob and Charlie each generate an individual non-scarce private key, which only they have the knowledge of. They compute and exchange public keys and concatenate them into one single aggregated public key. Although each individual can produce a valid individual signature with their individual private key, an aggregated signature that is valid to the aggregated public key can only be produced by all three individual signatures over the same message. Thus one aggregated signature is cryptographic proof, that all n-of-n individual private keys have been known and have given active consent to the transaction.

Since, assuming the discrete log problem, there is no computationally feasible way to fake a signature without the knowledge of the private key. When a full node receives a valid transaction with a valid Schnorr signature, it has cryptographic proof that the committed script is computed valid. Thus the transaction is included in the time chain with the most accumulated proof of work, the chain of digital signatures is advanced and a new UTXO with a new spending condition is created. The transfer of the UTXO is thus irrefutable and censorship resistant, it is a true ownership exchange. And since the MuSig transaction is only valid when all n-of-n peers agree, this is non-simulated shared ownership over a scarce bitcoin.

Taproot

Taproot [14] is a proposed variation on the current script language to add a BIP-taproot [15] Merkle spend. Taproot is a clever usage of aggregated Schnorr signatures and Merklized abstract syntax tree [MAST]. This enables a drastic increase in the complexity of potential spending conditions, since only the one script that is actually used to move the coins is revealed to full nodes on the time chain. This allows the writing of very complex scripts while still minimizing their data size for efficient and private usage of block space. A taproot bech32 address contains the public key directly, and not the hash of the public key as in incumbent P2WPKH addresses. Therefore a taproot spend does not require to reveal the public key when the UTXO is consumed. A valid transaction needs to contain a Schnorr signature [64 bytes / 16 vbytes] according to BIP-Schnorr [16]. In total, the cost of creating a taproot UTXO is roughly similar to sending to a P2WSH, yet spending a single-key taproot is 40% cheaper than P2WPKH.

``````[in Vbytes]		P2PKH	P2WPKH	Taproot
scriptPubKey	25		22		35
scriptSig		107		0		0
witness			0		26.75	16.25

total     		132		48.75	51.25``````

[17]

m-of-n Threshold signatures using Taproot

Schnorr MuSig aggregation is very efficient and private for interactive signers, but the taproot concept can be used to add more complexity into the spending condition script, while retaining some privacy and efficiency. For example, a 2-of-3 multi signature security hot wallet, where Alice has two keys, one hot and one cold storage, and Bob as a second factor security expert knows the third hot key. The most common use is [i] the combined signature of the hot keys of both Alice and Bob. In case [ii] Bob is malicious, Alice retrieves her cold storage key and now has two signatures to spend the money. But in case [iii] where Alice’s hot wallet key is compromised, she can use the cold storage wallet, as well as Bob as second factor to spend the coins.

For incumbent script multi signature, each full node would verify in parallel that at least two valid signatures from any of three public keys are provided. Schnorr MuSig will generate a valid signature only if 2-of-3 individual signatures have been made. Yet we can achieve the same result with taproot, by utilizing a different intuition. Instead of a spending condition of 2-of-3, we build three individual scripts of each a 2-of-2 multi signature. Incumbent script multisig would work for these internal spending conditions, but for efficiency, let’s work with three independent aggregated Schnorr public keys, that can only generate a valid signature if 2-of-2 individual private keys sign. The three pairs are [i] Alice hot and Bob hot [the most common case], [ii] Alice hot and Alice cold [Bob is malicious], or [iii] Bob hot and Alice cold [Alice hot key compromised]. The uncommon cases [ii] and [iii] are hashed and put in lexicographic order as the tapleafs of the MAST. These two hashes are then hashed again to calculate the tapbranch, the Merkle root of the tree.

``````	    	TapBranch hash [Merkle root]
/       					\
Tapleaf hash of [ii]			Tapleaf hash of [iii]
|				            |
MuSig aggregated pubkey [ii]	MuSig aggregated pubkey [iii]
Alice hot, Alice cold			Bob hot, Alice cold``````

For the cooperative common case [i], Alice and Bob create another Schnorr MuSig aggregated public key, the taproot internal key. Then, tapbranch and the taproot internal key are hashed together, resulting in a tweaked private key, used to calculate the tweaked public key. The tweaked public key is added to the taproot internal key which generates the taproot output key and used in the bech32 address committed in the time chain. This taproot output key has two spending options, the cooperative key path, or the advanced script path. In the cooperative case all peers can calculate individual and aggregated signatures that validate to this taproot output pubkey. But the output key also commits to a the tapbranch Merkle root, and in the advanced case, it can be verified that the proposed script was part in that MAST, and thus a valid spending condition defined at the time of funding the UTXO.

``````                  Merkle root [hash]	\
\ Tweak Hash => Tweak prkey [32-byte integer] => Tweak pubkey
Alice pubkey =\	Taproot internal key      /
Bob pubkey   =/	Aggregated MuSig pubkey  /

Tweak pubkey		    =\ Taproot output key
Taproot internal key	=/ [pubkey on time chain]``````

For spending this taproot UTXO in the cooperative case [i], Alice and Bob calculate a valid signature aggregated with the tweak private key [including the Merkle root of the unused spending conditions [ii] and [iii]] and taproot internal key. Full nodes will only see the committed taproot output key and the a valid signature for it, they do not know that this was a MuSig, or even a taproot. When using spending condition [ii] or [iii], then the spending transaction includes the script they want to use, the data needed by it [in our case only the aggregated public key and aggregated signature], the taproot internal key and the hash of the tapleaf script not used. In the sub-optimal case, it has to be revealed that the script in fact is a taproot, yet only the spending condition actually used is revealed, not the many other scripts that could have potentially been used to spend the UTXO. The maximum depth of the tree is 32 rows, which would allow for over four billion possible scripts, yet only one has to be revealed and verified. But for any m-of-n there need to be `n!/((m!(n-m)!)` tapleafs specified to express all the possible combinations of m signatures.

1. Claus-Peter Schnorr. Efficient Signature Generation by Smart Cards. J. Cryptology, 4(3):161–174, 1991.
2. The key-prefix method with the hash of _R and m as described by Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, and Bo-Yin Yang. High-Speed High-Security Signatures. In Bart Preneel and Tsuyoshi Takagi, editors, Cryptographic Hardware and Embedded Systems – CHES 2011, volume 6917 of LNCS, pages 124–142. Springer, 2011.
3. See MuSig 2018 Chapter 2.1. Notation and Definitions
4. Gregory Maxwell, Andrew Poelstra, Yannick Seurin, and Pieter Wuille. Simple Schnorr Multi-Signatures with Applications to Bitcoin. 2018
5. See MuSig 2018, Chapter 4. Security of the New Multi-Signature Scheme
6. See MuSig 2018, Chapter 3. Our New Multi-Signature Scheme
7. MuSig 2018, Chapter 4.3 Discussion
8. Thomas Ristenpart and Scott Yilek. The Power of Proofs-of-Possession: Securing Multiparty Signatures against Rogue-Key Attacks. In Moni Naor, editor, Advances in Cryptology - EUROCRYPT 2007, volume 4515 of LNCS, pages 228–245. Springer, 2007.
9. See MuSig 2018 chapter 5.3. Cross-Input Multi-Signatures
10. whilst a two-step round would be possible, it is larger in signature size and computational cost of signing and verification.
11. Maxwell. Taproot: Privacy preserving switchable scripting. Bitcoin-dev mailing list. Jan 23 2018
12. Maxwell. Graftroot: Private and efficient surrogate scripts under the taproot assumption. Bitcoin-dev mailing list. Feb 05 2018
13. Poelstra. Scriptless scripting and deniable swaps. Mimblewimble team mailing list. Feb 03 2017
14. Maxwell, G. (2018) Taproot: Privacy preserving switchable scripting. Bitcoin Mailing List. https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-January/015614.html
15. Wuille, Nick, Petukhow (2019) BIP-Taproot: SeGwit version 1 output spending rules.
16. Wuille, Lundeberg (2019) BIP Schnorr: Schnorr Signatures for secp256k1.
17. Harding, Single-sig spending using Taproot. Bitcoin Optech Newsletter #46. 2019.
You can’t perform that action at this time.