Multisignature transactions with notary subsystem

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

Multisigned transaction

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

Block signature collection over P2P

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

Committee out of band signing

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

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.

Oracle signature exchange

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

Centralized signature collection

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

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

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

Example notary payload

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.

Notary signature collection over P2P

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.

Sponsored transactions

Because all signers are equal, sender’s signature can be added the same way. So a user can send a notary payload with multisigned transaction that consumes as much GAS as it needs to, but some other account (single- or multisignature or contract) pays for it. The backend of the application can then decide if this transaction should be sponsored or not. Unlike contract’s verify method, the backend doesn’t have any limitations in doing so, it can parse the script, it can test-execute it, it can check all the fields, whatever is needed (see GitHub issue also).

If there is something wrong with the transaction, the backend might just ignore this event, main transaction won’t be completed and fallback one will be sent. The number of these outstanding requests is also directly controlled by the amount of GAS deposited in the Notary contract. While accepting such requests directly poses a risk of DoS attack, Notary scheme ensures that sending a big number of unsatisfied requests will be paid for. So, applications can safely offer this service to their users (and it’d be much easier for them to do so by reusing this infrastructure).

Conclusion

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store