Multisignature transactions with notary subsystem

13 min readDec 15, 2021

In real life and economy there are actions that need to be done jointly by a number of entities: signing documents, approving actions, confirming agreements between different parties. Blockchain-enabled smart economy allows for that too, but while it’s rather simple for an individual key owner to sign a transaction and send it to the network, having a number of key owners that want to do something jointly raises a question of how exactly they cooperate to achieve that. In this article we discuss problems related to signature collection and present a solution used by NeoFS.

Multisigning in accounts and transactions

First off, we must notice that ”multisigning” can be referred to in two different contexts: one is about signatures for M-out-of-N keys accounts and another one is about a number of signers in a transaction (see our previous post on signers and scopes). These are quite different cases, we’ll use ”multisignature account” term for accounts corresponding to verification scripts with a number of keys and ”multisigned transactions” for transactions having more than one signer.

While the concept of multiple signers looks pretty obvious — we just add another signer to the array with appropriate witness; multisignature accounts are a bit more involved. In some ways they don’t differ much from ordinary ones (they’re still a 20- byte hash value), but their verification script has a number of keys, M and N parameters and a call to System.Crypto.CheckMultisig syscall (very similar to Legacy scripts once explained in an old article, just using new opcodes/interops). An example of a three-out-of-four verification script looks like this:

INDEX    OPCODE       PARAMETER                                                             
0        PUSH3                                                                              
1        PUSHDATA1    02103a7f7dd016558597f7960d27c516a4394fd968...    
36       PUSHDATA1    02a7bc55fe8684e0119768d104ba30795bdcc86619...    
71       PUSHDATA1    02b3622bf4017bdfe317c58aed5f4c753f206b7db8...    
106      PUSHDATA1    03d90c07df63e690ce77912e10ab51acc944b66860...    
141      PUSH4                                                                              
142      SYSCALL      System.Crypto.CheckMultisig (9ed0dc3a)

What it needs to be executed successfully is a corresponding invocation script that contains three signatures for transaction in question. Like this one:

INDEX    OPCODE       PARAMETER                                                                                                                           
0        PUSHDATA1    199bdd216a4c6c4548fa04c2e75a20cbcbcc85baecd...
66       PUSHDATA1    b17f98a9649938a035caf57dda7eb5d169f80620df2...
132      PUSHDATA1    6d5d1157541c033ce9ede5fe16893ca27b2154dd823...

Any signer account can be a multisignature account, and Neo allows to have a number of them used in a single transaction. In fact, multisignature accounts are used a lot in Neo, every mainnet block is signed by a five-out-of-seven consensus node multisignature account, committee can change network settings using its 11-out-of-21 account and oracle nodes sign oracle responses with three-out-of-four account. NeoFS uses multisignature accounts too for container or deposit management, both in mainnet and in sidechain.

The problem is that different keys used in multisignature account belong to different entities (otherwise it makes little sense using multisignature), and these entities need to cooperate to produce proper invocation script with all signatures needed. Historically, there had been various approaches to this problem for different purposes.

State of multisigning

Consensus and state validation

dBFT consensus is at the core of Neo, this is how Neo blocks get created and signed. Consensus nodes communicate over P2P network with messages packed into ExtensiblePayload. When a node sends a Commit message for proposed block, it includes a signature for this block made using node’s key. Messages are broadcasted through the network and eventually every other node gets enough commits to finish the block. Then, nodes can create an invocation script using these signatures and the block is ready (similar scheme is used by state validation nodes for their job).

What allows nodes to exchange signatures in this case is exactly this ExtensiblePayload which can be seen as a generalization over Neo Legacy’s ConsensusPayload. It’s one of the broadcasted payloads and there are not that many of them:

blocks
transactions
extensible payloads

Every time we deal with a broadcasted message in untrusted environment the question is — what prevents the network from being DDoSed by these messages? Extensible payloads are limited in that they can only be signed by a well-known set of keys which includes consensus and state validation nodes. Joe Random can’t create valid extensible payload to harm the network. Nodes that are allowed to send extensible payloads can be considered semi-trusted, there are protections from any of them becoming rogue, but we’re not likely to see that happening.

We have a scheme here that works fine for a well-known subset of nodes (elected or controlled by committee) that create something special, like a block or a stateroot message. However extending it to a larger set of nodes is dangerous. They will compete for the same (relatively small) payload pool and the more nodes we add the more chances we get for some of them going wild. Allowing anyone to send this type of payload is just impossible.

Committee

We have a committee that from time to time does wonders, like reducing fees on mainnet; and it does them with transactions that use a special committee multisignature account. To collect appropriate number of signatures committee members use out of band communication channels (chats of various sorts), no one can see the transaction on the Neo P2P network until it’s signed. An incomplete (not fully signed) transaction is created by one of the committee members; then, he passes it to the next committee member who signs it and passes this new incomplete context to the next one. It all repeats until enough signatures are collected.

The context needs to be signed by the members one by one, which requires a lot of synchronization effort. For something that is not done frequently, something that is done manually and better yet something that doesn’t require a lot of signatures the process works; a group of unhurried people can use any messaging app of their choice to perform this. But it can’t be used for automated process: it’s not clear who is the first one to create a transaction, who’s the next one in turn to sign (and what if he is offline), synchronization channel itself might be unavailable, the system only works for some task- or application-specific scenario.

Oracle nodes

Oracle responses are created by a group of oracle nodes with (on current mainnet) three-out-of-four multisignature account. The process is completely automated of course, so it uses a quite different technique that at the same time has one thing in common with committee way of signing — it’s out of band, not using P2P network.

All oracle nodes have an RPC server exposed with submitoracleresponse API. And all oracle nodes have addresses of all other nodes in their configuration files, so they can directly connect to each other and exchange responses this way.

Obviously, this scheme doesn’t scale well, nodes always try to submit their data to each other, so it naturally leads to N ∗ (N − 1) connections created and messages exchanged between them for every transaction to be signed. It can also be hard to manage, moving any node to a different address requires updating the configuration of all the others. And the fact that every node directly knows each other node makes the approach only acceptable for app-specific cases.

Centralized collection

Oracle signature exchange scheme can be simplified by using some centralized entity that every node would connect to. But this would mean that either every application creates a service like that for its purposes, or someone has to run this generic service available for anybody. Running a service is not free both in terms of human resources and hardware cost, especially given the fact that this service would be a natural point of interest for attackers, so it’s not likely to happen as something available for everyone to use.

Even if someone to provide this service for general audience, it’d still be a single point of failure. Using it to sign a transaction for distributed decentralized application seems to contradict the essence of such application.

On-chain collection

Another natural approach used by many other blockchains is just managing signatures in a contract. This can also be done in Neo, and in fact NeoFS team has a lot of experience with this because that’s the way NeoFS contracts orignally worked. The idea is rather simple: contract keeps a set of authorized keys in its storage and then some method requiring M-out-of-N signatures is invoked by each signer in a separate transaction. Contract’s code checks if it has enough signatures on invocation. If that’s the case, it does the action required; if not it just increments the counter of signatures received and exits. In a pseudo-code it looks like this:

keys = getTrustedKeys() 
for k in keys { 
    if runtime.CheckWitness(k) { 
        signerKey = k break 
    } 
} 
if signerKey is null { 
    // return error 
}
storage.Put(requestID+signerKey, "") 
if countSigners(requestID) < m { 
    return // Wait for more signatures. 
} 
// Do the action.

Et voilà! Seems rather simple and even usable for trivial and rare occasions, but every method of every contract requiring multisignature approval needs code like this (and we need to be very careful to not mix signatures for different cases then), at least M transactions are needed to perform the task and (the most problematic) it’s impossible to precisely calculate system fee for these transactions.

Imagine four nodes trying to perform some action in a contract, each of them would send a transaction of its own that calls the method required. They can perform a test invocation and it will go ”wait for more signatures” way, spending some small amount of GAS in the process. But when all of these transactions get into the block (in unknown order!) one of them (crossing the ”M” threshold) will go ”do the action” route and if transaction only has system fee attached based on test invocation it’ll just run out of GAS and fail.

So a dApp performing such actions on-chain inevitably has to add some additional GAS to every transaction. The exact amount needed is unknown and it depends on the task performed, but it leads to huge GAS waste when actions are performed regularly. Even more importantly, it leads to potential instability of the dApp. Any update of any dApp contract or contract that it depends on can change the amount of additional GAS required, and it will easily break the dApp (the call will run out of GAS again instead of doing something useful).

That happened so many times to NeoFS that we just had no other choice but create something that works better.

Notary subsystem

Notary subsystem is a proposal for integration into future Neo releases. It’s implemented in NeoGo as an extension since version 0.93.0 (it’s even documented), stabilized and improved in various ways since then. The protocol is described in a GitHub issue and it consists of several key components:

native contract
P2P payload with a separate pool on every node
node module (to be used by designated nodes)
additional transaction attributes: Conflicts, Not Valid Before and Notary Assisted

This system uses P2P network to spread not-yet-fully-signed transactions, so a new broadcasted payload is added to do that. But as was noted above, broadcasting anything via P2P is a dangerous activity that needs to be limited somehow. The way notary payloads are limited is very reminiscent of the way regular transaction spreading is limited. Regular transactions are limited by the amount of GAS transaction sender has — when the sum of the fees for currently pooled transactions reaches account balance, no new transactions from this sender are accepted.

This mechanism couldn’t be used directly for notary payloads because they’re representing not-completely-signed transactions. Since they’re not yet valid, they can’t be accepted into the chain directly, and no one knows if they’ll be completed at all. So, unlike with normal transactions there is no guarantee that the fee will be written off the balance, which is crucial to ensure that eventually the pool will be depleted. Notary subsystem utilizes native contract for this purpose, to use the system user needs to send some GAS to the Notary contract first, which guarantees that there are funds to cover for transaction cost if needed.

Notary request itself then is a combination of two incomplete transactions in one payload: main one (intended to be completed) and fallback (to be sent if the main one doesn’t collect all signatures needed). Fallback transaction always has exactly two signers: Notary contract (which is a sender of this transaction) and request sender (that previously deposited some GAS to the Notary contract). Both transactions have Notary Assisted attribute that counts how many signatures are to be collected for this transaction; main one has whatever number it needs and fallback always has zero. This attribute is not free to use, transaction must attach additional fee for every collected signature plus one.

To make using Notary contract as a signer possible it also implements verify method. This method effectively is a one-out-of-N multisignature checker, so it accepts a parameter, one signature that needs to be made by one of the designated nodes. These nodes are the ones receiving the fee collected for using Notary Assisted attribute, similar to how fees are distributed among Oracle or Consensus nodes.

Fallback and main transactions are tightly coupled in the request: both have the same ”Valid until block” value, but fallback transaction also has ”Conflicts” attribute set to the hash of the main transaction and ”Not valid before” attribute set to some future block. ”Conflicts” attribute is a signal to consensus nodes that only one of the two conflicting transactions can be accepted. ”Not valid before” makes fallback transaction invalid until the chain reaches the specified block number; it’s like the opposite of ”Valid until block” field, very similar to X.509 ”Not valid before”/”Not valid after” pair

P2P notary payloads are being exchanged between nodes and all nodes maintain a pool of them (similar to transaction pool), but designated notary nodes (set by the committee in RoleManagement contract, similar to Oracle or State Validation nodes) additionally track payloads with the same main transaction. Parties that want to multisign their transaction can send payloads containing signatures independently; if and when notary node collects enough signatures to make the transaction valid, it’ll send it to the network. If for whatever reason this never happens, then after the chain reaches ”Not valid before” block from fallback transaction the same nodes will add a signature for the Notary contract signer and send fallback transaction into the network.

Fallback transaction is basically a hostage that guarantees payment for the service. Normally witnesses for the main transaction are assembled correctly and this transaction enters the chain (making fallback transaction forever invalid because of ”Conflicts” attribute). However, if the main transaction is not completed in time (and that time is determined by the ”Not valid before” attribute), then fallback transaction (or transactions coming from multiple sources) does that, ensuring that the main one will never be accepted, again because of the conflict. The GAS deposited to the Notary contract is only written off if fallback transaction is accepted, so for normal use depositing GAS once to the Notary contract should be enough.

While payloads are visible to everyone on the network and technically anyone can assemble a complete main transaction, notary nodes are motivated to do so with fees they get for providing this service. They at the same time can’t cheat by sending fallback transactions right away instead of main ones (because they’re ”Not valid before” some block), and if they have both valid fallbacks and main transaction, sending main transaction is more economically appealing because nodes will get more GAS for doing that.

The system is completetly decentralized and even one Notary node alive is sufficient for it to work. It at the same time is open for any dApp to use, there is no need to reimplement a lot of the same multisignature logic for every dApp, just some adjustments to the backend depending on application specifics. It’s much more reliable and economically appealing than on-chain collection, the number of transactions used is reduced at times.

While it was initially intended for NeoFS nodes that jointly manage a multisignature account and are able to produce the same transaction independently, it can also be used in a bit different fashion for multisigned transactions, adding another useful feature to the Neo stack.

Conclusion

Notary subsystem is still a proposal for the core protocol, but it’s already implemented in NeoGo and you can try it out. We’ve been using it successfully in NeoFS for more than nine months by now, and it greatly simplified both contracts and backend logic, making the system more reliable and performant.