Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
357 lines (209 sloc) 47 KB

PART II: SHARED OWNERSHIP OF SCARCE BITCOIN

Basics of Bitcoin Script

A bitcoin UTXO is the tip of the chain of digital signatures which originates in the coinbase issuance transaction. A transaction dedicates inputs, which are previously unspent transaction outputs with a valid witness to the ScriptPubkey; and outputs, which "lock up" the bitcoin with a new ScriptPubKey. The Bitcoin script is the property rights definition of how a UTXO can be spend. At any time, there is only one script for one UTXO, the spending conditions are defined at the point where the UTXO is created.

Pay to Public Key Hash

A ScriptPubKey is a short script that details the conditions which must be met in order to claim control of the bitcoin. In a P2PKH transaction, this script contains OP_DUP OP_HASH160 <PubKey> OP_EQUALVERIFY OP_CHECKSIG, the UTXO can only be spend by the proof of knowledge of the private key corresponding to the committed public key hash. The signature script is a prefixed to the ScriptPubKey and contains an secp256k1 signature and the full public key: <Sig> <PubKey> OP_DUP OP_HASH160 <PubkeyHash> OP_EQUALVERIFY OP_CHECKSIG. To verify the correctness of the transaction, all operators from both the Alice’s signature and Bob’s pubkey script are executed. The message to sign is the hash of certain parts of the transaction it self. So not only is the signature proof of knowledge of the private key, it also gives the explicit consent which input is consumed, and which outputs are created.

Multi Signature in P2PKH

ScriptPubKey: M <Public Key 1> <Public Key 2> …​ <Public Key N> N CHECKMULTISIG

SignatureScript: <Signature 1> <Signature 2> …​ <Signature M>

Validation Script: <Signature 1> <Signature M> M <Public Key 1> <Public Key 2> <Public Key N> N CHECKMULTISIG

Pay to Script Hash

The ScriptPubKey of a P2SH transaction contains a hash of a redeem script, which can be any script whatsoever. [1] At the time of UTXO creation there is only the hash of the script on the time chain, but not the script itself. It is thus unclear what the spending condition of that particular coin is. These conditions to redeem the bitcoin are with the receiver, not the sender of the transaction. To spend the UTXO, Bob needs to provide both the full redeem script and a valid signature script. It is only valid, when the redeem script hashes to the same value as the script hash Alice committed to in the output. The redeem script has the same attributes as a pubkey hash, thus the follow up process is identical to a P2PKH script. This gives the benefit of removing complex scripts from block space and shifting the burden of key storage to the future spending time. The majority of fees are paid not when receiving to a complex P2SH, but when spending the P2SH UTXO where the redeem script and signatures are revealed.

Multi Signature in P2SH

Redeem Script: M <Public Key 1> <Public Key 2> …​ <Public Key N> N CHECKMULTISIG

ScriptPubKey: HASH160 <20-byte hash of redeem script> EQUAL

SignatureScript: <Signature 1> …​ <Signature M> <redeem script>

Address: Base58Check(HASH160(<ScriptPubKey>))

Pay to Witness Public Key Hash

Segregated witness [2] is a protocol upgrade [3] intended to fix transaction malleability and to increase the block size through different weight calculations. [4] P2WPKH transactions remove the signature in the input field, and relocate it in the witness structure of the scriptSig. The script PubKey thus contains only 0 <PubKeyHash> and the signature is verified as <signature> <pubkey> CHECKSIG.

Single Signature in P2WPKH

Redeem Script: <Public Key> CHECKSIG

Witness Script: 0 <Public Key Hash>

ScriptPubKey: 0 SHA256(<witness Script>)

Address: RIPEMD160(SHA256(<witnessScript>))

Pay to Witness Script Hash

Similar to P2WPKH, P2WSH removes the witness part from the transaction merke tree of the redeem script. The main difference to P2PKH is thus the location of the signature part. SegWit also increases the security for multisig compared to P2SH, which uses 160-bit HASH160 algorithm, a double hash with RIPEMD of SHA256. In the case where one signer of the multisig is malicious and wants to spend the money without the consent of other signers, he can brute force a collision between a valid P2SH multisig address and a script that pays him all the money. This requires only 80-bits, that is 2^80 worth of work, which is already possible for a well funded attacker. SegWit fixes this issue by using HASH160 only for P2WPKH, but 256-bit SHA256 for P2WSH.

Multi Signature in P2WSH

Redeem Script: M <Public Key 1> <Public Key 2> …​ <Public Key N> N CHECKMULTISIG

Witness Script 0 <signature 1> …​ <signature M> M <Public Key 1> …​ <Public Key M> N CHECKMULTISIG

ScriptPubKey: 0 SHA256(<witnessScript>)

Address: checksum base32 [5] encoded

Script Multi Signatures

In the incumbent implementation of multi signatures, the redeem script contains a list of n public keys, as well as the threshold of m necessary signatures to validate a transaction. This redeem script is hashed to the script public key and committed to the time chain at the creation of the UTXO. The hash commitment decreases the P2WSH UTXO data size at the time of funding, yet the clear text script needs to be revealed for verification at the time of spending.

In order to spend this coin, the committed redeem script and a valid witness script has to be provided, containing any m signatures corresponding to the committed public keys. If the proposed signatures are not valid for the public keys, or if less then m signatures are provided, then the transaction and block are rejected by every full node. This enforces the shared ownership of bitcoin on the level of full nodes. This verification is done both at the time the transaction is initially broadcasted, or during the initial block download of a new full node.

However, this system is fundamentally based on the trust in the thorough verification of the consensus rules as they have been defined at the point of funding. Full nodes could adopt a hard fork that changes the validity rules so that the coins can be spend in another way as originally defined. This is in contrast to aggregated Schnorr MuSig [See chapter on Schnorr MuSig.] where nodes verify only one signature, not knowing that this is actually a aggregated signature of several individual private keys. Since the verifier of a script multi signature has more information available, there is a higher possibility to censor this particular transaction. An adversary could define an additional rule that all script based multi signature scripts are to be dropped, yet he cannot do this for aggregated multi signatures. Script multi signatures have a smaller anonymity set.

However, if this concept of full node verification is working properly and reliably, as is the case in Bitcoin [6], then the redeem script can be considered a non-simulated property right definition, there is a very slim and unprecedented plausibility of breaking the spending conditions. This is one of the many reasons why the adherence to Nakamoto consensus is so vitally important, and why any change to the set of rules, including soft forks but especially hard forks, carry a tremendous risk.

Schnorr Signatures

The Schnorr signature scheme [7] is a conceptually simple, data size and computationally efficient and secure under the discrete logarithm assumption [ECDSA]. This protocol is currently proposed as s soft fork replacement of Bitcoin’s incumbent elliptical curve digital signature algorithm.

Schnorr is in nearly all regards superior to ECDSA, other than the fact that it’s use requires a change to Nakamoto consensus as well as the lacking documentation and implementation.

[i] The signature is constant-size, regardless the number of participants in the multi signature, only one aggregated public key and signature needs to be verified. This allows for a large group of peers to define and enforce secure, private and efficient shared ownership of scarce bitcoin. The nuances of aggregated MuSig is explained in detail below.

[ii] Since the data size of redeem and witness script are overall smaller, this also means that the bandwidth usage of the peer to peer gossiping protocol is reduced. Every transaction is shared with a default of 8 peers, thus the bandwidth constrains are more pressing than the computation or storage of the data.

[iii] Due to the linearity of Schnorr, there can be entire spending conditions and policies included in the public key and signature itself, obscured and indistinguishable from regular single public key and signature. This means that a single signature spend, a MuSig spend, a taproot cooperative spend, a lightning network payment channel closing, or an adapter signature coin swap, all of them require the same form of information to validate - only one single public key and signature. The signature can be valid if and only if all the spending conditions are met, the details of the property rights definition don’t necessarily matter, rather it’s validity is essential.

[iv] A verifier can leverage the linearity of public keys and signatures in order to batch validate them, it is computationally easier to batch and verify many signatures at once, rather than to verify them individually one after another. For example all Schnorr signatures in a Bitcoin block can be batched together and if the batched single check is valid, than all the individual signatures must be valid as well. Yet in the case that one signature is wrong, the batch verification will also be invalid, and the block will be discarded.

[v] In an advanced implementation of Schnorr signatures to the Bitcoin protocol, interactive cross-input signature aggregation can drastically reduce the size of transactions with many inputs. This transaction doesn’t need to have one signature for each input, but one single signature for all inputs. This aggregated signature is only valid if all the signatures of each individual input are valid. This would allow for example for a large coin join transaction with only one signature, which would be much more efficient than a one input - one output transaction.

The Schnorr signature scheme 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) [8], 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. [9]

MuSig

The MuSig paper [10] 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 in the plain public-key model [11], 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. [12] The total signature size is |G|+|p|; the public key size |G|; and the private key size |p|.

Interactive Key Generation and Aggregation

Individual private keys x_i are generated by each cosigner 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. In the first round of communication, all cosigners share their public keys, any verifier can build the multiset L and for all 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́ = X_i for 1X_i = n, X́ = product of X_i^a_i. The the hash pre-image of a_1 contains all the public keys once, but X_1 twice.

The aggregated public key X́ for 1X́_i = 1n, X́ = 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.

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.

Interactive 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 1R_in, 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 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 1R_in, R = product of all R_i, c = H_sig(X́,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 1s_in, s = sum of all (s_i mod p). The signature is σ = (R,s).

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 [13] [14], all cosigners have to collaborate in a three step [15] 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.

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 = RR = 1n, R (product of X_i^(a_i c)) = R X́^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 [16].

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.

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 [17] or graftroot [18] transaction, a collaborative lightning network channel close, or a scriptless script atomic coin swap [19]. 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 might be, is 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, a valid aggregated signature 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.

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 [20] is a proposed variation on the current script language to add a BIP-taproot [21] Merkel spend. Taproot is a clever usage of aggregated Schnorr signatures and Merkelized abstract syntax tree [MAST] [22]. 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 [23]. 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

Tabel 1: Data size of different scripts, by David Harding for the Bitcoin OpTech Group [24]

m-of-n Threshold signatures using Taproot

Schnorr MuSig aggregation is very efficient and private for n-of-n 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 and 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 3-of-3 individual signatures have been made. Schnorr Threshold signatures can actually be used to create a 2-of-3 condition. 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 Merkel root of the tree.

	    	TapBranch hash [Merkel 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 Merkel 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.

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

Shamir’s Secret Sharing Scheme

Shamir’s Secret Sharing [SSSS] [25] is an algorithm used to divide a given master secret MS into n parts, such that m parts are required in order to compute the original master secret. If only m-1 parts are available, no information about the master secret is revealed. If the m-of-n threshold scheme is n = 2m-1 then we can still recover MS even if n/2 = m-1 of the n pieces are destroyed. However, an adversary cannot reconstruct MS even when he has compromised n/2 = m-1 parts.

SSSS is based on polynomial interpolation: given m points in the 2-dimensional plane (x_1, y_1) … (x_m, y_m) there is only one function q(x) of degree m-1 such that q(x_i) = y_i for all i. In order to protect against the attacker acquiring information about MS with every additional D_i, we use finite field arithmetic with a field of size p ∊ P: p > MS, p > n. Prime number p must be close enough to the desired security level, because a too large p leads to long cypher text, but a too small p leads to compromised security.

Preparation

After specifying MS, m and n, we generate m-1 random numbers a_1, … a_[m-1] and build a polynomial with the secret as a_0. The polynomial is thus q(x) = a_0 + a_1*x + a_2*x^2 + … + a_[m-1]*x^[m-1].

Then we construct n points D_[x-1] = (x, q(x) mod p) from the polynomial and each party gets a different point [both x and q(x)], the MS is q(0). Each sub-secret is a point n on the constructed polynomial curve.

Reconstruction

To reconstruct MS, any m of n will be enough to compute the entire polynomial q(x) with the Lagrange interpolation formula [26].

Simulated shared ownership

SSSS can distribute the knowledge of a secret across several different sub-secret, where each of the holders has full knowledge of his individual part, yet alone he has no knowledge of the master secret. However, the dealer first generates a master secret, which he has full knowledge off. Thus the dealer has full access and property rights in the funds locked up by the master secret. The sub-secret holders have a simulated shared ownership, however, they rely on the good will of the dealer to not spend the funds on his own accord. The use case for SSSS is thus more to backup a private key among semi-trusted peers, but where the dealer and owner of the bitcoin has always full control himself. [27] This is a vitally important differentiation compared to some secure key and signature aggregation [28], which generates non-simulated shared ownership.

Verifiable Secret Sharing Scheme

Verifiable Secret Sharing Scheme [VSS] is used to prevent the dealer from cheating, every peer can verify his own share and will detect when the dealer has distributed inconsistent shares. [29] This removes some, but not all of the trust in the central dealer.

The dealer specifies MS ∈ Z and a random number MS' ∈ Z and commits to them by publicly releasing C_0 = MS*G + MS'*H. Then he chooses at random the polynomials f(u) = MS + f_1 u + …​ + f_t+1 u^t-1 and f'(u) = MS' + f'_1 u + …​ + f'_t+1 u^t-1 to compute (s_i, s'_i) = (f(i), f'(i)) for i ∈ {1, …​, n}. The tuple (s_i, s'_i) is send secretly to player P_i for 1 < i < n. Now the master dealer publicly commits the values C_j = f_j*G + f'_j*H for 1 =< j =< t-1.

Then each player P_i verifies that s_i*G + s'_i*H = for t-1 ⇐ j = 0 ⇐ sum of i^j*C_j, if this is false, the dealer is publicly accused and he can defend himself by revealing the value (f(i), f'(i). The dealer is rejected if there are more than m complaints, or if his defense does not validate the equation.

Schnorr Threshold Signatures

A threshold signature scheme [30] is setup by n individual public keys, and it computes valid only with proof of knowledge of m private keys. This protocol uses in part MuSig and Shamir’s Secret Sharing Scheme.

Key Generation

All n signers compute their individual private public key pairs, and they use a m-of-n verifiable secret sharing scheme [31] to generate n shares of their individual private key, so that given m shares the individual private key can be calculated. Each of the n participants then give each peer one specific share, so that all peers have one share each of all the private keys of all participants. Due to the linearity of the Schnorr signature scheme, these shares can be added, that is tweaked, to the individual private key. All participants broadcast their individual public keys, so that an n-of-n aggregated public key can be calculated and used as the locking script of a UTXO. [32]

Signing

In order to produce a valid signature, at least m participants need to collaborate. Each of them signs a spending transaction with the individual tweaked private key, which is the sum of their individual private key and all n-1 shares of the other individual private keys. All m individual signatures are then aggregated to the final signature. This includes the m "full" signatures of each active signer, and m shares of the signature of the n-m non-signing private keys. Because m shares are enough to produce the full signature for the non-signing keys, this final signature is a fully n-of-n, and thus valid according to regular MuSig.

Lightning Network

The lightning network consists of individual peers communicating information and trustlessly exchanging bitcoin between each other without requesting the verification of all Bitcoin full nodes. An additional piece of software, a lightning network node, has to be installed and run by the user. Each node can communicate with different peers to gain necessary information about the state of the network. In order to send bitcoin between lightning peers, two nodes collaboratively open, update and close a payment channel off-chain. This limits full node verification of on-chain transactions to two transactions in the life cycle of a payment channel, which can conduct potentially unlimited amounts of updated commitment transactions. These are based on the Bitcoin scripts multi signatures and hashed time locked contracts, as well as per-signed revocation transactions. A payment can be routed through many independent channels, so even peers without a direct channel can send and receive bitcoin. The following chapters focus on the shared ownership of payment channel, and not on the routing between the channels since this is independent from the channel update mechanism.

2-of-2 Lightning Network Payment Channel

The basic implementation of the current payment channels is based on a 2-of-2 script multisig. Two peers collaborate long term to send payments in between each other, and to route payments through the lightning network. The life cycle of a channel consists of the on-chain opening transaction, off-chain commitment transaction, different cases for collaborative or forced closing transactions, and the defense against theft with revocation transactions. Each of them will be analyzed in this chapter.

Funding Transaction

Two parties create a transaction funded by individual inputs, for example Alice provides a 10 bitcoin UTXO as input. This funding transaction creates a 2-of-2 multi signature with the redeem script 2 <PubKeyAlice> <PubKeyBob> 2 CHECKMULTISIG. [33] Alice and Bob can only spend this UTXO with both signatures. If one of them is malicious, the funds are locked and irredeemable. Alice wants to protect herself against the case that malicious Bob goes off-line, so she requests Bob’s signature over a commitment transaction, as described below, that send all 10 bitcoin to a new script of Alice. Alice stores this transaction, yet she doesn’t yet broadcast it. Now Alice will sign the funding transaction, knowing that at any time she could broadcast the initial commitment transaction with Bob’s signature. The funding transaction is verified by every full node and confirmed in the time chain. Now the payment channel is open, it has a unique identifier of the transaction and channel ID. Alice and Bob can choose to announce this channel publicly to the lightning network and offer to route payments up to the capacity of the multisig.

Commitment Transaction

Subsequently, Alice and Bob can exchange signed commitment transactions [34] which change the value of the outputs dedicated to Alice and Bob. This transaction consumes the output of the funding transaction, and creates four new outputs, one back to Alice’s single signature private key, the other back to Bob’s, and one for each offered and received HTLC. [35] Initially, only Alice partially signs [36] the transaction and sends it to Bob, who completes the 2-of-2 multi signature and sends the fully signed transaction back to Alice. The next commitment transaction consumes the same founding transaction output, but changes the amount dedicated to the newly created outputs of Alice and Bob. These valid transactions could be broadcasted to the network and added to the time chain, but for now they are kept occulted by Alice and Bob.

Offered HTLC output P2WSH: DUP HASH160 <RIPEMD160(SHA256(revocationpubkey))> EQUAL IF CHECKSIG ELSE <remote_htlcpubkey> SWAO SIZE 32 EQUAL NOTIF DROP 2 SWAP <local_htlcpubkey> 2 CHECKMULTISIG ELSE HASH160 <RIPEMD160(payment_hash)> EQUALVERIFY CHECKSIG ENDIF ENDIF

Witness Script: <remotehtlcsig> <payment_preimage>

If a revoked commitment transaction is published, the Witness Script <revocation_sig> <payment_preimage> can spend the output immediately. For every commitment transaction, the receiver requests the revocation private key before accepting the money. Thus for any received payment there is proof of payment, and that can be used to punish a malicious trying to settle an old state. It has to be ensured, that a old state of the channel is invalidated with the most current commitment transaction. There needs to exist enforceable proof in the case that a old state is closed on chain. There are several different update and revocation mechanisms with according thread models and security assumptions:

Transaction held by Alice

[i 0] 2-of-2 funding output, signed by Bob	|	[o] <nValueAlice>: <PubKeyAlice>
											|	[o] <nValueBob>: IF <Revocation Public Key> ELSE <delay in blockst> CHECKSEQUENCEVERIFY DROP <PubKeyBob> CHECKSIG

Transaction held by Bob

[i] 2-of-2 funding output, signed by Alice	|	[o] <nValueBob>: <PubKeyBob>
											|	[o] <nValueAlice>: IF <Revocation Public Key> ELSE <delay in blocks> CHECKSEQUENCEVERIFY DROP <PubKeyAlice> ENDIF CHECKSIG

The revocable key is split in two secrets, similar to 2-of-2 multi signature based on elliptical curve arithmetics. When Bob sends funds to Alice, Bob has to revoke the old commitment transaction by revealing her secret to Alice, before Alice agrees to sign the commitment transaction of the new state. If Bob would try to cheat and broadcast an old state, Alice can become active and use both paths of the revocation key to redeem Bob’s delayed output. Alice only has one half of the revocation key and can only redeem her output after the block delay timeout. With each state update, both exchange the new commitment transactions, and the revocation secret of the previous one.

Closing Transaction

After Alice and Bob have done several off-chain payments, they can cooperatively close this payment channel, by broadcasting the final multisig settlement transaction to the network. This cooperative closing transaction has a witness script 0 <signature1> <signature2> 2 <PubKey1> <PubKey2> 2 CHECKMULTISIG and can specify any new ScriptPubKey in the output. In this case where both signatures are available, the transaction does not include any timelocks and thus can be spend again without any timeouts.

In the case where one peer is uncooperative the other party can do a one-sided closing transaction. This is the script with the revocation key and HTLC in order to protect against the closing with an old state. In this time-out window the uncooperative party has the opportunity to come back online and to check if this closing attempt is actually valid. If not, then the revocation key is used as proof that this is an old state.

n-of-n Multi Party Channel Factories

Channel factories are payment channels where every commitment transaction opens more payment channels. The off-chain update transaction closes the previous payment channel and opens the new one atomically. This script enables the secure opening and closing of a new payment channel without committing any extra transaction to the time chain. A 10 peer channel factory has 90% transaction size savings compared to individual channel opening. [37]

Hook Transaction

Two, or preferably more peers create a channel factory deposit transaction that is verified by all nodes and committed to the time chain. All peers provide their individual UTXOs with witness proofs in the input of the hook transaction, and they create several individual change outputs, as well as the channel factory script UTXO. This is the transaction to collect all the bitcoin from the peers and fund the channel factory. This script has the regular payment channel conditions, the n-of-n cooperative case, as well as partially signed yet unbroadcasted backup transactions with time locks with single signatures for uncooperative spending. The hook transaction is signed only when all transactions of the initial state are signed to ensure the funds always return to their initial owner in case of the uncooperative case.

[i]	Alice	| [o]	10-of-10 channel factory
	Bob		|		Alice Change
	...		|		Bob Change
	Justin	|		...
			|		Justin Change

Replaceable Allocation Transaction

After the funding transaction has sufficient accumulated proof of work, the peers can collaboratively update the channel factory by creating an unbroadcasted commitment transaction. The input is the n-of-n cooperative multi signature of the allocation transaction, the outputs are the funding UTXO with a 2-of-2 direct payment channels between the individuals within the factory.

Every allocation transaction thus spends the hook UTXO to create individual payment channel funding transactions. Only peers of the same factory can connect, since only they verify and enforce the scarcity and double spending protection of these bitcoin. Because only the factory peers need to verify the unbroadcasted commitment transactions, the speed of opening and closing an individual payment channel is near instant, and without any on-chain transaction cost.

The goal of a channel factory is to have many off-chain allocation transactions that open many individual 2-of-2 payment channels. Because only the latest state of these allocation transactions must successfully be committed on the time chain, it is thus essential that old states are replaced by the new one. This can be done by building an invalidation tree with either decrementing timelocks started by a kickoff root transaction [38], exchanging revocation secrets [39] or utilizing the eltoo [40] updating mechanism. The leaves of the invalidation tree are the individual 2-of-2 multi signatures that open an individual 2 peer payment channel.

Commitment Transaction

After the hook transaction has sufficient accumulated proof of work, and the allocation transaction is successfully signed and communicated, then the individual sub-channels are open. The commitment transaction spends the 2-of-2 multi signature of the allocation transaction, and creates UTXOs with the single public key of the individual owners of the bitcoin. The scripts and signing ceremony is identical to the ones of regular 2-of-2 payment channels.

Closing Transaction

In the case where all peers collaborate, they will close all the individual payment channels within the factory, this is done all off-chain and should be coordinated within seconds. Then they build and sign a factory closing transaction with the n-of-n multisig as the input, and individual UTXOs with the correct number of bitcoin according to the latest state of the factory. In this case there are no timelocks, and thus every individual can spend their own UTXO as soon as they desire. The individual script might even be the funding of a new channel or factory according to the splicing in and out process.

In the uncooperative case, the on-line peers can construct a one sided closing transaction, which is however limited by an additional time lock. During this period the off-line peers have the opportunity to come back on-line to check if this is the most recent state of the channel factory, and if not, to proof it and punish the thieves.

M-of-n HTLC

An early proposal for instant escrows was to use complex scripts with several HTLCs to enable threshold transactions inside a payment channel. [41] m-of-n hash preimages are required for the HTLC to be fulfilled. Timeouts are at the minimum the escrow timeouts and they increase with every additional n in the multisig scheme. Sender, escrow and receiver [or others] have the n preimages, yet only m of them are required in order to validate the redeem script. In most cases, sender and receiver will disclose preimage themselves without the need for escrow action. Although this does work theoretically, it commits a lot of information to the time chain and is thus rather inefficient.

Assume the order in the stack is Sender, Escrow, Recipient.

For PAID 2-of-3 Escrow+Recipient, the HTLC stack is:
        <BobSig> <0> <EscrowPreimageR> <RecipientPreimageR> (0)

If it's REFUND because 2-of-3 has not been redeemed in time:
        <AliceSig> (0) (1)

Bitcoin Script (Alice's, we use OP_1/OP_0 to distinctly show computed
true/false. 0/1 is for supplied data as part of the
sigScript/redeemScript stack):
------------------------------------------------------------------------

//Paid
OP_IF
        <CSVDelay> OP_DROP OP_CSV //under rusty's CSV style

        //Stack: <BobSig> <0> <EscrowPreimageR> <RecipientPreimageR>
        //Recipient must agree to receive funds.
        OP_HASH160 <RecipientHash> OP_EQUALVERIFY

        //Stack: <BobSig> <0> <EscrowPreimageR>
        //Either the Sender or Escrow must consent for payment
        OP_HASH160 <EscrowHash> OP_EQUAL
        //Stack: <BobSig> <0> <OP_1>
        OP_SWAP
        //Stack: <BobSig> <OP_1> (0)
        OP_HASH160 <SenderHash> OP_EQUAL
        //Stack: <BobSig> <OP_1> <OP_0>
        OP_BOOLOR
        //Stack: <BobSig> <OP_1>
        OP_VERIFY

        <BobPubKey>
        //Stack: <BobSig> <BobPubKey>
//Refund
OP_ELSE
        //Stack: <AliceSig> (0)
        OP_HASH160 OP_DUP
        <R-HASH> OP_EQUAL
        OP_NOTIF
                <CSVDelay> OP_DROP OP_CSV
        OP_ENDIF

        <HTLCTimeout> OP_DROP OP_CLTV

        //Stack: <AliceSig>
        <AlicePubKey>
        //Stack: <AliceSig> <AlicePubKey>
OP_ENDIF
OP_CHECKSIG
------------------------------------------------------------------------

[42]


1. BIP16
2. Lombrozo, Lau, Wuille. BIP 141: Segregated Witness. 2017.
3. Fry. BIP 148: Mandatory Activation of SegWit Deployment 2017.
4. See Bitcoin Wiki. Weight units.
5. BIP173
6. See Chapter on Full Nodes Define, Verify and Enforce Scarcity.
7. Claus-Peter Schnorr. Efficient Signature Generation by Smart Cards. J. Cryptology, 4(3):161–174, 1991.
8. 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.
9. See MuSig 2018 Chapter 2.1. Notation and Definitions
10. Maxwell, Poelstra, Seurin, Wuille. Simple Schnorr Multi-Signatures with Applications to Bitcoin. 2018.
11. See MuSig 2018, Chapter 4. Security of the New Multi-Signature Scheme
12. See MuSig 2018, Chapter 3. Our New Multi-Signature Scheme
13. Ristenpart, 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.
14. See MuSig. Chapter 5.3. Cross-Input Multi-Signatures. 2018.
15. whilst a two-step round would be possible, it is larger in signature size and computational cost of signing and verification.
16. MuSig 2018, Chapter 4.3 Discussion
17. Maxwell. Taproot: Privacy preserving switchable scripting. Bitcoin-dev mailing list. Jan 23 2018
18. Maxwell. Graftroot: Private and efficient surrogate scripts under the taproot assumption. Bitcoin-dev mailing list. Feb 05 2018
19. Poelstra. Scriptless scripting and deniable swaps. Mimblewimble team mailing list. Feb 03 2017
20. Maxwell, G. (2018) Taproot: Privacy preserving switchable scripting. Bitcoin Mailing List. https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-January/015614.html
21. Wuille, Nick, Petukhow (2019) BIP-Taproot: SeGwit version 1 output spending rules.
22. Rubin, Naik, Subramanian. Merkelized Abstract Syntax Trees 2016
23. Wuille, Lundeberg (2019) BIP Schnorr: Schnorr Signatures for secp256k1.
24. Harding, Single-sig spending using Taproot. Bitcoin Optech Newsletter #46. 2019.
25. Adi Shamir. How to Share a Secret. Communications of the ACM, Volume 22, November 1979.
26. Hazewinkel, Michiel. Lagrange interpolation formula. Encyclopedia of Mathematics, Springer Science+Business Media B.V. 1994
27. See Rusnak, Kozlik, Vejpustek, Susanka, Palatinus, Hoenicke. SLIP 0039: Shamir’s Secret-Sharing for Mnemonic Codes. 2017.
28. Refer to chapter on Schnorr MuSig
29. Pedersen. Non-interactive and information-theoretic secure verifiable secret sharing. Lecture Notes in Computer Science (Crypto '90), 473:331-238, 1991.
30. Stinson, Strobl. Provably Secure Distributed Schnorr Signatures and a (t,n) Threshold Scheme for Implicit Certificates. Certicom Corporation, 2001.
31. See Chapter on Shamir’s Secret Sharing Scheme
32. Refer to chapter II.4. on MuSig.
33. BOLT 3, Funding Transaction Output
34. BOLT 3, Commitment Transaction
35. BOLT 3, Commitment Transaction outputs
36. Chow. BIP 174: Partially Signed Bitcoin Transactions. 2017.
37. Harding, What are Channel Factories and how do they work? 2018
38. Decker, Wattenhofer. A Fast and Scalable Payment Network with Bitcoin Duplex Micropayment Channels. 2016.
39. Poon, Dryja. The Bitcoin Lightning Network: Scalable Off-Chain Instant Payments. 2016.
40. Decker, Russell, Osuntokun. eltoo: A Simple Layer 2 Protocol for Bitcoin. 2018.
41. [2-of-3 Instant Escrow, or How to Do "2-of-3 Multisig Contract" Equivalent on Lightning, Joseph Poon: https://lists.linuxfoundation.org/pipermail/lightning-dev/2016-January/000403.html
42. Original proposed script by Poon.
You can’t perform that action at this time.