k-of-n multisignature

The k-of-n multisignature validity predicate authorizes transactions on the basis of k out of n parties approving them. This document targets the encrypted (inner) WASM transactions. Namada does not support multiple signers on wrapper or protocol transactions. The signer of the wrapper transaction is the fee-payer of that transaction.

Protocol

Namada transactions are signed before being delivered to the network. This signature is checked by the invoked validity predicates to determine the validity of the transaction. To support multisignature, Namada's signed transaction data includes the plaintext data of what is being signed, as well as all valid signatures over that data.

There are no special non-multisignature established accounts - all user accounts are just 1-of-1 multisignature accounts.

Rust implementation

A rust implementation of a SignedTxData struct is described below:

pub struct SignedTxData {
    /// The original tx data bytes, if any
    pub data: Option<Vec<u8>>,
    /// The signature is produced on the tx data concatenated with the tx code
    /// and the timestamp.
    pub sig: Vec<(u8, common::Signature)>,
}

The sig field holds a vector of tuples where the first element is an 8-bit integer and the second one is a signature. The integer serves as an index to match a specific signature to one of the public keys in the list of accepted ones for efficiency purposes. This implementation improves the verification algorithm reducing execution complexity to ($\mathcal{O}(n)$), without the need to cycle on all of them which would be $\mathcal{O}(n^2)$.

VPs

All user-owner accounts use the default vp_user validity predicate for verifying state changes. The vp_user validity predicate asserts that at least k out of n valid signatures are present in the signed transaction data for every transaction originating from the user.

To perform the validity checks, the VP requires two pieces of information:

1. The multisignature threshold
2. A list of valid signers' public keys

This data defines the requirements of a valid transaction operating on the multisignature address and is written in storage when the account is created.

A rust storage implementation is shown below:

/$Address/threshold/: u8
/$Address/pubkeys/: LazyVec<PublicKey>

To verify the correctness of the signatures, the VP checks the following conditions:

1. Enough unique signatures for the given threshold are provided
2. Enough valid signatures for the given threshold are provided

If implemented in this fashion, a couple efficiency gains are made: Step 1 allows for short-circuiting the validation process and avoid unnecessary processing and storage access. Each signature is validated only against the public key found in the list at the specified index. Step 2 halts as soon as it retrieves enough valid signatures to match the threshold, meaning that the remaining signatures are not unnecessarily verified.

Addresses

The vp introduced in the previous section is available for all established addresses on Namada. Whenever a user wishes to initialise an established address as a multisignature address, they must provide the multisignature threshold and valid signatures. By default, the threshold is set to 1 if not provided. At least one key must provided as a valid signing key for the VP to check against.

Once this transaction is executed, the following storage writes are made in association, under the storage subspace of that user:

• The vp_user address
• The threshold of the multisignature account
• The list of public keys for the signers of the multisignature account

Multisignature accounts can also be initialized at genesis time - in this case, the requisite parameters are kept in the genesis file and written to storage during initialisation.

Multisig account init validation

Since the VP of an established account does not get triggered at account creation, no checks will be run on the multisignature parameters, meaning that the creator could provide incorrect data.

To perform validation at the time of account creation Namada could:

1. Write in storage the addresses together with the public keys to trigger their VPs
2. Manually trigger the multisig VP even at creation time
3. Create an internal VP managing the creation of every multisig account

All of these solutions would require the init transaction to become a multisigned one.

Solution 1 actually exhibits a problem: in case the members of the account would like to exclude one of them from the account, the target account could refuse to sign the multisig transaction carrying this modification. At validation time, his private VP will be triggered and, since there's no signature matching his own public key in the transaction, it would reject it effectively preventing the multisig account to operate on itself even with enough signatures to match the threshold. This goes against the principle that a multisig account should be self-sufficient and controlled by its own VP and not those of its members.

Solution 2 would perform just a partial check since the logic of the VP will revolve around the threshold.

Finally, solution 3 would require an internal VP dedicated to the management of multisig addresses' parameters both at creation and modification time. This could implement a logic based on the threshold or a logic requiring a signature by all the members to initialize/modify a multisig account's parameters. The former effectively collapses to the VP of the account itself (making the internal VP redundant), while the latter has the same problem as solution 1.

In the end, we don't implement any of these checks and will leave the responsibility to the signer of the transaction creating the address: in case of an error he can simply submit a new transaction to generate the correct account. On the other side, the participants of a multisig account can refuse to sign transactions if they don't agree on the parameters defining the account itself.

Transaction construction

In order to craft a multisignature transaction, the involved parties must coordinate. More precisely, the transaction itself is constructed by one entity which will distribute the constructed transaction to the other signers and collect their signatures.

Finally, these signatures are inserted in the SignedTxData struct to be encrypted, wrapped and submitted to the network.

Namada does not provide a layer to support this process, so the involved parties will need to rely on an external communication mechanism.