Iterations on Multisig

Multisig is among the most common smart contracts used on blockchains, prompting us to improve on it. Here are some thoughts that we had when implementing multisig, points that we believe will benefit other smart contracts writers on Tezos (regardless of their choice to use LIGO or not).

What is a Multisig?

Let us start by explaining what a multisig contract is.

Operations on Tezos are either signed by a TZx (a public key) or relayed by a KT1 (a smart contract). However, sometimes we would like some operations to be mediated by multiple parties instead of a single one. Examples where we want this can be found here. In that case, we need a smart contract as an intermediary that will check that the different required parties have authorized a given operation.

A simple multisig on Tezos would work this way:

  • Its storage would contain the list of participants and the required threshold for agreement.
  • An entry point would take as parameters an address, an amount and the set of participants with their associated signatures. It would pack the address and the amount, check that the signatures are valid and coming from participants. If the signatures are valid and the threshold is met, then the contract makes a transfer to the address of the amount it received.

For technical reasons, it would also need

  • to implement a do-nothing entry point to allow receiving tez from regular transfers;
  • to store the public key of the participants in a list (and thus implementing LIST_MEM ) instead of a set, or to pass empty signatures for the participants that do not sign it.

That is the basic flow of a multisig contract on Tezos.

V0. Avoiding Replay Attacks

This basic flow is not safe, though! Nothing forbids someone from again calling the multisig with the exact same parameters. What it means is that if a multisig sends you 1tz, you could simply replay the same operation with the same signatures until it is emptied.

To avoid this, along with the address and the amount of the transfer, we sign a counter. The idea is that a signed operation is only valid when the counter it was signed with matches the one the smart contract holds. For every operation that is done by the multisig, the smart contract counter is incremented by 1. This means that a signature for an operation can at most be used once.

We also have to sign a chain_id , which represents the network where the smart contract is executed. We might not want an operation signed on a testnet to be valid on the mainnet.

V1. lambda(unit , list(operation))

So far, we have a safe multisig that controls sending money to a given smart contract. However, we might want to extend this into a multisig that can call any entry point of any smart contract.

To do so, instead of signing the byte representation of an address and an amount, we will sign the byte representation of a value of type lambda(unit, list(operation)) . Such a value is a Michelson function that takes an argument devoid of information (that is, of type unit ) and returns a list of operations. Those operations are typically a single call to a given entry point of a given smart contract.

( Remark: The user should never try to build a Michelson lambda to sign a multisig. This means that a generic multisig needs custom tooling support. )

V2. Enabling Participations of KT1

With the current scheme, we check that a current message is signed by the different participants. There are two problems with this:

  1. Additional custom tooling is needed to support to sign the multisig messages because they have a format specified by the contract code rather than the contract signature .
  2. It is not possible to have smart contracts participate in the multisig. Indeed, a smart contract can not sign messages, as there is no SIGN instruction in Michelson (which makes sense because there is no private key stored on chain corresponding to the contract).

The latter is of course the biggest problem, given we might want to compose the multisig with other contracts. To enable participation of other contracts, it is better to view a k-of-n multisig as a k-of-n voting contract, where only white-listed addresses can vote for a proposition.

With this in mind, the contract design becomes much simpler: we aggregate votes for a proposition from the given KT1s in a map, once one of them crosses the multisig threshold, we clear its entry from the map and execute it. There is no need to check signatures, counters or chain_id , given those are already taken care of by the protocol.

V2 bis. Spam Avoidance

Given our latest design, we can aggregate propositions from the participants, but one participant might try to make the contract unavailable to the other participants (Denial of Service) by spamming it with dummy propositions. This would happen because the storage of a smart contract has usually to be serialized every time a contract is invoked.

There are two ways to avoid this.

  1. By using a Michelson big_map , that is, a lazy Michelson data structure that was made so that each users of a smart contract operates on their own region of the memory. Big maps are not serialized when a contract is invoked. However, they have a higher runtime gas cost because all queried keys within the contracts have to be retrieved from the context.
  2. By limiting the number of propositions per participant. The downside of that solution is that the contract now has to manage the number of propositions per participant, which makes it more complicated and more likely to be faulty. (But less so if a higher-level smart contract language is used instead of Michelson , for example LIGO .)

V3. Smart Messages

(Remark: This part is more complicated, feel free to ask questions and I’ll clarify!)

When we had a counter, there was a problem we did not mention: what if the current counter of the smart contract is 4 , and we want to sign two messages, where the second should pass only if the first one did? We can either

  1. sign the first one with the counter value 4 and wait for it to be included and executed, then sign the other one;
  2. or sign the first one with the counter value 4 and the second one with 5 .

The first approach requires always being online (waiting for the signature to be pooled with others and for the transaction to be included on the chain).

The second one is actually faulty! It is indeed possible that some totally unrelated message gets signed with counter 4 , and then our message with counter 5 gets included without my message with counter 4 .

Ideally, we would like a solution that does not require always being online, and that is, of course, correct. A possible approach is to change the signature of the messages from the type lambda(unit, list(operation)) to lambda(bytes, list(operation)) . The difference is bytes being passed to the second lambda and those bytes would be the hash of a representation of the whole history of messages. It would be initialized in the storage with the empty byte sequence, and then, every time a message is evaluated, its byte representation would be concatenated to the hash and then re-hashed.

With this in mind, it is now possible for the lambda to return its operations (encoding the calls) and check that the given hash matches what it expected. This does solve our problem because

  • instead of being signed with counter 4 , the first message is actually signed with a lambda that checks that the hash being passed is the current contract hash;
  • also, instead of being signed with counter 5 , the second message is signed with a lambda that checks that the hash being passed is the one that would result from the previous message being evaluated.

We can go deeper and have lambdas that perform checks based on the given timestamp, or a set of valid hashes, etc. Those would be smart messages , messages that are only valid given some conditions verified on the blockchain.