At Clovr Labs, we developed NodeGuard, a treasury management system that allows people to have money secured behind multi-signature wallets (among other features). One of the benefits of multi-signature wallets is that because of how they are constructed, a “contract” prevents a single person from owning the funds. For money to change hands, multiple people must sign the operation to approve the ownership change.

To make signing more straightforward, we’re developing a browser extension allowing people to import their seeds and sign an operation. This extension will be open-sourced in the future. It will be open for everyone to use, not only in the NodeGuard application but with their own applications.

Now, let’s talk about multi-signature wallets, AKA multi-sig wallets. As stated before, multi-sig wallets are wallets in which the ownership of funds belongs to more than one person at a time. In addition, multi-sig wallets are referred to by the “M-of-N” description, where “N” denotes the number of total signers “agreeing” to construct the wallet. In contrast, “M” represents the number of signers required to do an operation or “transaction” with these funds.

Let’s set an example. Imagine I belong to a group of 3 friends, and we constructed a 2-of-3 multi-sig wallet together. That means that the 3 of us “agreed” to create a wallet together, and we would only need the signature of 2 friends to change ownership of funds. Since we want to send funds to a different wallet, another friend and I must sign off on a transaction. Even though my other friend “agreed” to be part of the wallet, they are not needed to sign.

Let’s do another example. I have a friend who has a business in which he has one other partner. My friend comes from a construction background, and his partner comes from an architecture background; they don’t trust each other but decided to go into a business together because they complement each other well. They decided to create a Bitcoin 2-of-2 multi-sig wallet. In this scenario, they both agreed to make the wallet. The contract specifies that both signatures are needed to transact with their funds.

As you see, the flexibility of M-of-N wallets allows for a world of possibilities in which funds are secured via many different configurations: 3-of-6, 2-of-2, etc.

In this article, we will learn how to sign off on a transaction by multiple people using the Rust language. But first, we need to learn a few concepts that will allow us to understand the code better.

🔹 Wallet

We talked about multi-sig wallets, but how are they constructed? We mentioned in the last part that we need to sign something (we’ll talk about what later) to perform a transaction. The way signatures work in Bitcoin is pretty much how a safe work in real life. To access the content of a safe, you need to prove that you know the safe combination. In comparison, to see that you have ownership of funds in Bitcoin, you need to prove that you own a “private key”, which is a 256-bit number. This private key can be encoded as 64 hexadecimal characters so humans can easily read it. In the case of a 2-of-3 multi-sig wallet, you can imagine a safe with 3 keypads, but only two out of the 3 combinations are needed to be input to open it. So in the case of a Bitcoin wallet, you (or your friends) need to prove that they know 2 of the private keys to sign off on a transaction.

🔹 Public Keys

A public key is an essential part of how wallets work. It is the face of a wallet and how wallets are constructed. The public key is derived from the private key and generates an address for receiving Bitcoin. The derivation of a public key is one way; even if someone knows your public key, they cannot retrieve the private key from it. Public keys are combined to generate an address to receive funds in a multi-sig wallet. Once funds are transferred to that address, private keys can be used to prove the ownership of that public key and “unlock” the funds for further expending. This is one of the main reasons you see that whenever someone loses their wallet keys, the funds are lost forever since it’s impossible to reconstruct the private key from a public key. And the possibilities of guessing a private key, even with powerful computers, are astronomically small.

🔹 Derivation Path

A Bitcoin wallet uses a derivation path to derive multiple public keys and, in turn, create infinitely different Bitcoin addresses for the same wallet. You can think of derivation paths as other safes belonging to the same person that lives in different buildings, cities and countries. To unlock money from a safe, we first need to know the country, city, building, room and safe number. With that information, we know which safe to input the password, and the password we’ll use will depend on the safe number. In Bitcoin, in contrast, the passwords from the different safes in a room can be derived from the password that unlocks the door of the room. Which also is safe if you think of a room as a big safe with a password-protected door. We’ll not talk about some other complexities regarding derivation paths here. But to sign off on a transaction, we first need to know in which “safe” the money is and if we can prove ownership of the secret to use that money.

🔹 Fingerprint

A fingerprint is a more compact version of a private key. As the name suggests, it identifies a private key without using the long private key itself. In our case, we’ll use it to quickly verify that our private key can be used to sign a transaction and prove that the money is ours before signing off on the transaction.

🔹 Inputs

Inputs consist of information saying where the money comes from, a reference to previous transaction outputs, and information proving that the funds we want to use are authorized to be spent. Every time you do a transaction, e.g., spend money in Bitcoin, a transaction id is generated as the output of that transaction. The input contains the id of the previous transaction being made, so you can trace the money back until it was created. Because an earlier transaction can be done with more than one input, an index is necessary to identify which transaction inputs are being spent. This is somewhat difficult to follow, so let’s see the anatomy of a transaction:

    
    Transaction: TXID: f4184fc596403b9d638783cf57adfe4c75c605f6356fbc91338530e9831e9e16
    Input 1: a1075db55d416d3ca199f55b6084e2115b9345e16c5cf302fc80e9d5fbf5d48d (vout 0)
    Input 2: 4ce18f49ba153a51bcda9bb80d7f978e3de6e81b5fc326f00465464530c052f4 (vout 2)
    Output 1: 1 BTC to mvhMvZi4m17c8YR44YB64LisKYA3NbqBvS
    Output 2: 1 BTC to mgYJwtk2SWLcBbuNGnUV4dza1MERoHA9SR

As you can see, a transaction id (TXID) was generated for this transaction. In this case, my transaction has two outputs to two different wallets, and we’re transferring 1 BTC to each wallet. We also have inputs 1 and 2; they have the transaction id of the previous one and an index called “vout” that references which of the previous transaction outputs is being spent. In this example, the transaction is spending the Output number 1 (vout 0) of the previous transaction a1075db55d416d3ca199f55b6084e2115b9345e16c5cf302fc80e9d5fbf5d48d, and the Output number 3 (vout 2) of the last transaction 4ce18f49ba153a51bcda9bb80d7f978e3de6e81b5fc326f00465464530c052f of the previous transaction 4. And all that money spent is going into the addresses mvhMvZi4m17c8YR44YB64LisKYA3NbqBvS and mgYJwtk2SWLcBbuNGnUV4dza1MERoHA9SR.

As stated before, another vital piece of information that input contains is a script that proves that the funds someone is about to spend are authorized to be spent by that person. This proof is done by providing a signature that matches this script. As you can see, signatures are not like the ones you do on a piece of paper, but they are a way to prove that you are the owner of funds, and you need to have a private key to prove that ownership. This script that the input contains is called an “Unlocking Script” because it provides the information you need to verify to unlock the funds. And to “sign off” on a transaction, you need to give this signature and add them to the input data structure.

We saw that inputs reference previous transaction outputs, which contain information on how the money can be spent. The name of this unspent transaction output is called UTXO. Let’s talk about them.

🔹 UTXO

An Unspent Transaction Output, UTXO for short, is the output of a previous transaction that remains to be spent. If you received the money in your Bitcoin wallet and never spent it, then you are the proud owner of UTXOs. If you spend those UTXOs, they will be used as inputs for a new transaction.

And most important for what we need to do, a UTXO contains information about the conditions to spend the money. There are a lot of “contracts” in Bitcoin for spending money. You can have sequence-based contracts defining that the money can be spent after several blocks have been mined. You can have time-based contracts where you can only spend the money after a specific time. You can have “custom” contracts that let the owner of the money specify how to satisfy the contract to unlock the funds. These “contracts” are called “Unlocking Scripts”. For our purposes, and because we need to ensure we are gathering the required number of signatures, we’re interested in multi-signature “Pay to Script Hash” unlocking scripts, one of the “custom” contracts we mentioned earlier. In our case, the enforcer of spending conditions is a script containing the public keys of the people that can sign and the number of signatures required to fulfil the spending condition. A pay-to-script hash can look like this:

    
    2 PubKey1 PubKey2 PubKey3 3 CHECKMULTISIG

Let’s look at this and see what we can interpret from it. At first sight, we can see CHECKMULTISIG written on the script. This is the “type” of the script, and it tells the code how to interpret the rest of the numbers and characters appearing in the rest of the script. Bitcoin scripts are read from right to left, so CHECKMULTISIG is the first thing read by the code. Thanks to CHECKMULTISIG, the code can interpret the numbers 2 and 3, which are the descriptors of the wallet allowed to spend the money. In this case, we’re looking at a 2-of-3 multi-sig wallet. We need to prove that 2 out of the 3 public keys also appearing in this script can be derived from our private keys.

So you see, between inputs and outputs, we have all the information needed to prove who is the current owner of the funds (the locking script), that the current owner of the funds allowed the transfer of funds to a different wallet (e.g. they spent the money), how to prove that we are the new owner of the money after the transaction is being done (the unlocking script), where the money comes from and where the money is going to.

One thing I skipped about the script we are using is that there are two types of those: those that have “Segregated Witness” and those that don’t. Since we’ll need to know the difference to sign off on this transaction, we’ll explain these two types as our next concept.

🔹 Segregated Witness

Segregated Witness, or SegWit, is the name assigned to an improved version of the Bitcoin protocol in 2017. Before that moment, and as we saw in the previous concept, the transaction data contained the ids of the last transaction’s outputs being spent, along with the signatures that prove who the money about to be spent belongs to. As signature data can be quite large and substantially increase the size of a Bitcoin transaction, a decision to change how a transaction is constructed was made to separate the signature information into a different data structure. With this change, when the size of the transaction is calculated, the signature information is not counted as part of that size (but still very much included in the block), and since a Bitcoin block size limit is 4MB, the reduction in the size of the transaction data allows for more transactions to be included in a single block (neat trick huh?). Since the blockchain has the recorded information of all transactions being made from the beginning, and because some people might still be using the older version, there is no way to “deprecate” or enforce this change for everyone. So the two versions of the blockchain (SegWit and not Segwit) coexist and can be used. However, SegWit is recommended and also incurs fewer transaction fees.

🔹 Sighash

A Sighash is a hash of the transaction data that we’ll “ combine” with the signature to sign the inputs. This is useful for verification because the hash wouldn’t match the signature if the data inside a transaction is modified. There are different types of sighashes: SIGHASH_ALL, SIGHASH_NONE, SIGHASH_SINGLE and SIGHASH_ANYONECANPAY. They all describe what information about the inputs and outputs will be included when creating the transaction hash.

🔹 PSBT

Finally, we reached the part of the article where we’ll explain where all the concepts we mentioned earlier live. One of the ways an operation could be signed in a multi-sig wallet is via a Partially Signed Bitcoin Transaction (PSBT). A PSBT is a paper containing all the relevant transaction information. This includes the amount of Bitcoin to be spent, the total number of members of a wallet (N), and the required members of a wallet (M) that need to sign to do a transaction; The inputs and outputs, the witnesses and the UTXOs. PSBTs are only sometimes necessary to do multi-sig transactions and can also be used to sign single transactions. A PSBT is helpful because it provides another layer of security and privacy since it can be constructed and signed offline, minimizing the risk of exposing private keys.

The reason it’s called “Partially Signed” is because it works like an actual contract. Each party has to individually sign the contract and then pass it along to the next signer. So if you encounter a PSBT in the wild, it can be in 3 states: Not signed, partially signed or fully signed. The fully signed state is reached once all required signers have added their unlocking script into the PSBT. So to “sign” a PSBT, you need to read the inputs from the PSBT and create the Unlocking Scripts for each. Let’s see how this looks in the Rust code. For this article, we’ll only sign inputs with segregated witnesses.

The crates we’ll use for this article are the “bitcoin” crate for manipulating our PSBT and the “anyhow” crate for handling the errors.

First, we’ll create the signature of our function. It will receive a psbt, a private key and a derivation path that we’ll use to derive the private key for that specific location (remember the “safe” concept)

    
    fn sign_psbt(
        mut psbt: PartiallySignedTransaction,
        xprv: ExtendedPrivKey,
        derivation: &DerivationPath,
    ) -> Result<PartiallySignedTransaction> {
        ...
    }

Next, we’ll iterate over all the inputs we need to sign. We’ll also need an index of the input to be later able to construct the signature. Everything we’ll do from now on will be inside this for a loop.

    
    for (index, input) in psbt.inputs.iter_mut().enumerate() {
        ...
    }

We get the witness script, which contains the signatures from the current owners of the outputs being spent in this transaction. This will be used to verify the transaction inputs. Since we’re only coding for segregated witnesses, we’ll throw an error if this information is not available and let the parent of this function handle it.

    
    let witness_script = input
        .witness_script
        .as_ref()
        .context("Missing witness script")?;

We get the amount from the UTXO, and as before, we’ll let the parent function handle the missing witness.

    
    let amount = input
        .witness_utxo
        .as_ref()
        .context("Witness utxo not found")?
        .value;

We talked briefly about the sighash before; in these couple of lines, we’ll create the sighash, but we will wait to combine it with our signature. We’ll include all the relevant information, and then we’ll get the sighash to tell the segwit_signature_hash what information to add to the hash.

    
    let mut sighash_cache = SighashCache::new(&psbt.unsigned_tx);
    let sighash = sighash_cache.segwit_signature_hash(
        index,
        witness_script,
        amount,
        get_sighash_type(input),
    )?;

In the last part of the code, we invoke a function called get_sighash_type; this function gets the sighash type information from the input created when the PSBT was created. If that information was not included in the input, we default to SIGHASH_ALL.

    
    fn get_sighash_type(input: &Input) -> EcdsaSighashType {
        input
            .sighash_type
            .and_then(|t| t.ecdsa_hash_ty().ok())
            .unwrap_or(EcdsaSighashType::All)
    }

Continuing our path, we’ll see where the fingerprint we mentioned before becomes useful. We’re using it to compare it against our private key’s fingerprint for any matches. A matching fingerprint would mean we can later prove we have the necessary private key to sign the transaction and own the funds. After verifying that the fingerprint matches, we collect a KeyPair, a tuple of a Public and a Private Key. If there are no matching fingerprints, then we cannot sign the transaction, and that means that the funds we want to spend don’t belong to us. You might be wondering why we are using an array, and that is because there is a possibility that the input has multiple required signatures that can be derived from the same private key. In case we find a matching fingerprint, and before continuing with our signature, we have to derive the private key to get the right combination to our “safe” Let’s see that next.

    
    let mut input_keypairs = Vec::new();
    for (_, (fingerprint, sub_derivation)) in input.bip32_derivation.iter() {
        if fingerprint != &xprv.fingerprint(&secp) {
            continue;
        }
        let parent_xprv = derive_relative_xpriv(&xprv, &secp, derivation, sub_derivation)?;
        input_keypairs.push(parent_xprv.to_keypair(&secp));
    }
    if input_keypairs.is_empty() {
        return Err(anyhow!("No private keys to sign this psbt"));
    }

We saw earlier that to have access to a safe, we needed to know the building, the room and the safe number. And we saw that when having the password to a room, we can derive the passwords to the safes inside it. There is a possibility that a Bitcoin wallet owner knows the master password (e.g. to the building) or just a room’s password. For that reason, to know the password we need to use to open a safe, we need to combine the derivation paths of the password we own with the absolute path we want to reach. And that is what the get_partial_derivation function does. You can think of derivation paths as an array with the coordinates of our safe. For example, [44, 1, 3] could be noted as the country we’re in (44), the city (1), and the building (3). If I only know the password for the city, then I know the coordinates are [44, 1]. Since the input gives us the final combination to the safe, e.g. [44, 1, 3, 2, 2], we need to derive the password from the city to the safe. Then our get_partial_derivation function will give us exactly this partial derivation path: [3, 2, 2]. Our second function, ‘derive_relative_xpriv’, will be responsible for deriving the private key into the one we’ll need to sign.

    
    fn get_partial_derivation(
        derivation: &DerivationPath,
        sub_derivation: &DerivationPath,
    ) -> Result<DerivationPath> {
        if derivation.len() > sub_derivation.len() {
            return Err(anyhow!(
                "Can't get a partial derivation from a derivation greater than the sub derivation"
            ));
        }
        let partial = &sub_derivation[derivation.len()..];
        DerivationPath::try_from(partial).map_err(|e| anyhow!("{e}"))
    }

    
    fn derive_relative_xpriv(
        xprv: &ExtendedPrivKey,
        secp: &Secp256k1<All>,
        derivation: &DerivationPath,
        sub_derivation: &DerivationPath,
    ) -> Result<ExtendedPrivKey> {
        xprv.derive_priv(secp, &get_partial_derivation(derivation, sub_derivation)?)
            .map_err(|e| anyhow!("{e}"))
    }

The final part of our code is just the “signing”. We get the key pairs we collected in the previous steps. We create a Message, a container for all the necessary information to create and sign a valid transaction. Once we construct our message, we can finally sign it and add the partial signature to the input as another tuple, a Public Key – Signature tuple. But first, we’ll need to add to the input the information about which sighash type we used to sign the data. This will be used to verify the signature later on.

    
    for keypair in input_keypairs {
        let message = &Message::from_slice(&sighash)?;
        let signature = secp.sign_ecdsa(message, &keypair.secret_key());
        input.partial_sigs.insert(
            PublicKey::new(keypair.public_key()),
            set_sighash_type(signature, input),
        );
        secp.verify_ecdsa(message, &signature, &keypair.public_key())?;
    }

The sighash type is set by using the get_sighash_type function we used before and combining it with the signature.

    
    fn set_sighash_type(signature: Signature, input: &Input) -> EcdsaSig {
        let sighash_type = get_sighash_type(input);
        EcdsaSig {
            sig: signature,
            hash_ty: sighash_type,
        }
    }

Lastly, out of our inputs for loop, we return the PSBT to the caller of the sign_psbt function so that PSBT can be signed by the next signer.

    
            }
        Ok(psbt)
    }

You can see the full code below:

    
    use anyhow::{anyhow, Context, Result};
    use bitcoin::psbt::Input;
    use bitcoin::secp256k1::ecdsa::Signature;
    use bitcoin::secp256k1::{All, Message, Secp256k1};
    use bitcoin::util::bip32::{DerivationPath, ExtendedPrivKey};
    use bitcoin::util::psbt::PartiallySignedTransaction;
    use bitcoin::util::sighash::SighashCache;
    use bitcoin::{EcdsaSig, EcdsaSighashType, PublicKey};
    
    fn set_sighash_type(signature: Signature, input: &Input) -> EcdsaSig {
        let sighash_type = get_sighash_type(input);
        EcdsaSig {
            sig: signature,
            hash_ty: sighash_type,
        }
    }
    
    fn get_sighash_type(input: &Input) -> EcdsaSighashType {
        input
            .sighash_type
            .and_then(|t| t.ecdsa_hash_ty().ok())
            .unwrap_or(EcdsaSighashType::All)
    }
    
    fn get_partial_derivation(
        derivation: &DerivationPath,
        sub_derivation: &DerivationPath,
    ) -> Result<DerivationPath> {
        if derivation.len() > sub_derivation.len() {
            return Err(anyhow!(
                "Can't get a partial derivation from a derivation greater than the sub derivation"
            ));
        }
        let partial = &sub_derivation[derivation.len()..];
        dbg!(&partial);
        DerivationPath::try_from(partial).map_err(|e| anyhow!("{e}"))
    }
    
    fn derive_relative_xpriv(
        xprv: &ExtendedPrivKey,
        secp: &Secp256k1<All>,
        derivation: &DerivationPath,
        sub_derivation: &DerivationPath,
    ) -> Result<ExtendedPrivKey> {
        xprv.derive_priv(secp, &get_partial_derivation(derivation, sub_derivation)?)
            .map_err(|e| anyhow!("{e}"))
    }
    
    fn sign_psbt(
        mut psbt: PartiallySignedTransaction,
        xprv: ExtendedPrivKey,
        derivation: &DerivationPath,
    ) -> Result<PartiallySignedTransaction> {
        let secp = Secp256k1::new();
        // <https://github.com/bitcoin/bips/blob/master/bip-0174.mediawiki#user-content-Signer>
        for (index, input) in psbt.inputs.iter_mut().enumerate() {
            let witness_script = input
                .witness_script
                .as_ref()
                .context("Missing witness script")?;
            let amount = input
                .witness_utxo
                .as_ref()
                .context("Witness utxo not found")?
                .value;
            let mut sighash_cache = SighashCache::new(&psbt.unsigned_tx);
            let sighash = sighash_cache.segwit_signature_hash(
                index,
                witness_script,
                amount,
                get_sighash_type(input),
            )?;
            let mut input_keypairs = Vec::new();
            for (_, (fingerprint, sub_derivation)) in input.bip32_derivation.iter() {
                if fingerprint != &xprv.fingerprint(&secp) {
                    continue;
                }
                let parent_xprv = derive_relative_xpriv(&xprv, &secp, derivation, sub_derivation)?;
                input_keypairs.push(parent_xprv.to_keypair(&secp));
            }
            if input_keypairs.is_empty() {
                return Err(anyhow!("No private keys to sign this psbt"));
            }
            for keypair in input_keypairs {
                let message = &Message::from_slice(&sighash)?;
                let signature = secp.sign_ecdsa(message, &keypair.secret_key());
                input.partial_sigs.insert(
                    PublicKey::new(keypair.public_key()),
                    set_sighash_type(signature, input),
                );
                secp.verify_ecdsa(message, &signature, &keypair.public_key())?;
            }
        }
        Ok(psbt)
    }

I hope this made sense to you and that you enjoy this content. See you in the next article!

NodeGuard Signer Extension: How to sign a PSBT in Rust