Network assistance for multisignature transaction forming

[roman-khimov]

(from #1555: #1555 (comment))

Summary or problem description
Generating multisignature transaction requires some interaction between signing parties. Currently this interaction is not handled by the network in any way and requires some jumping through the hoops with partially signed transaction copying like described here: https://github.com/neo-ngd/NEO-Tutorial/blob/8726c5e0df0a0f5e9211fedf0d398bed20f123a6/neo_docs_SmartContract_QuickStart/SmartContract_quickstart_en.md#transfer-neo-to-standard-address

It kinda works for transactions signed by humans (although it still can be quite annoying), but it's a bigger problem for automated transaction generation as it requires signing nodes to use some additional protocol.

At the same time it's exactly the same problem Oracle subsystem has for its response transactions signing and there is already a solution for it in #1555.

Do you have any solution you want to propose?
I think we should extend the mechanism defined by #1555 for generic transactions. Users should be able to push partially signed transactions and the network should be able to collect these signatures to create a correct final multisignature transaction. The Oracle subsystem could then reuse this common infrastructure for its purposes.

Possible problems and solutions
Extending the #1555 mechanism for all transactions adds some complexity because it's designed to be used by a limited number of (somewhat) trusted nodes. Generic solution of course should work for everyone and their dog and be resilient to various misuses of it.

One of the biggest problems here is transaction never completing signature collection, both unintentionally and in some kind of spam attack. The unintentional part of it can be mitigated by short ValidUntilBlock time (I would actually propose using short-lived transactions in general, but that's a topic for another issue). An intentional one probably can be solved by ensuring that the multisignature address has enough GAS to pay for the transaction and at the same time limiting the number of these in-flight transactions from one address.

Neo Version

• Neo 3

Where in the software does this update applies to?

• P2P (TCP)

[Tommo-L]

It is recommended to have an aggregate data on the chain. Or it's better to communicate between these service nodes directly.

[shargon]

I think that this is a good idea, but oracle can't use it because they don't provide the original transaction, only send the signatures in order to avoid the lazy nodes problem.

Users needs to send the TX without sign, but they need to send the original TX, because otherwise you don't know what you are signing, but it's a good idea, because now if you need to sign someting for change CN or Oracle policy, you need to speak with them outside the chain.

[vncoelho]

One can create a Smart Contract with such feature, deploying its address with storage for caching signatures and deleting at the end of the process.
However, there could be a cache for standard multisigs in a Native Contract.

[roman-khimov]

One can create a Smart Contract with such feature, deploying its address with storage for caching signatures and deleting at the end of the process.

That's what we're planning to do at the moment, but obviously it's an app-specific solution. And so is the one used by Oracle subsystem. When there is a number of similar app-specific solutions being used something tells me we need a system-wide solution.

[Tommo-L]

@roman-khimov I think we need this, as we have 21 committees, it'll be a hard work for them to do multisign.

[Tommo-L]

Currently, we have oracle validators, neofs ir validators and committees all need to do multisign.

[roman-khimov]

Another possible use case could be creating transaction with multiple signers, at the moment you also have to collect their signatures via some additional mechanism, the network doesn't help in any way with this.

[roman-khimov]

One can create a Smart Contract with such feature, deploying its address with storage for caching signatures and deleting at the end of the process.

And BTW, this contract-based approach also has a problem if there are multiple invocations of it in a single block. A test invocation for each party involved would just add a signature to the cache, but when executing transactions from a block one of them could see that all signatures are already in place and trigger some additional actions, but it will fail to complete them because it will run out of GAS (because the system fee value would be set based on test invocation). There is an obvious workaround of adding some GAS to each of these invocations ("just in case"), but it leads to GAS waste and is not very reliable.

[Tommo-L]

On the other hand, we can also consider using a native contract, like TaskContract?

[roman-khimov]

I guess it'll have the same problem with multiple invocations in a single block, setting proper system fee for it would be a problem.

[roman-khimov]

Definition of the problem

Several parties want to sign one transaction, it can either be a set of signatures for multisignature signer or multiple signers in one
transaction. It's assumed that all parties can generate the same transaction (with the same hash) without any interaction, which is the case for oracle nodes or NeoFS inner ring nodes.

As some of the services using this mechanism can be quite sensitive to the latency of their requests processing it should be possible to construct complete transaction within the time frame between two consecutive blocks.

Use cases:

• NeoFS inner ring nodes
• Oracle nodes
• Committee-signed transactions

Current solutions

Off-chain non-P2P collection

Either manual or using some additional network connectivity. Has an obvious downside of reliance on something external to the network. If it's manual, it's slow and error-prone, if it's automated, it requires additional protocol for all the parties involved. For the protocol used by oracle nodes that also means explicitly exposing nodes to each other.

On-chain collection

Can be done by a contract, but going through the chain for "M out of N" multsignature means that:

• it can only be app-specific (meaning that for every use case this logic would be duplicated) because we can't create transactions from transactions (thus using proper multisignature account is not possible)
• we need at least M transactions instead of one we really wanted to have, but in reality we'll create and process N of them, so this adds substantial overhead to the chain
• some GAS is inevitably wasted because any invocation could either go the easy path (just adding a signature to the list) or really invoke the function we wanted to (when all signatures are in place), so test invocations don't really help and the user needs to add some GAS to all of these transactions

P2P signature collection (notary) service

The service consists of a native contract and a node module. Native contract is mostly concerned with verification, fees and payment guarantees, while module is doing the actual work. It uses generic "Conflicts" (#1991) and "NotValidBefore" (#1992) transaction attributes for its puproses as well as an additional special one ("Notary assisted").

A new designated role is added, "P2P Notary". It can have arbitrary number of keys associated with it.

Using the service costs some GAS, so below we operate with FEE as a unit of cost for this service. The exact amount of FEE is to be decided, but in general that's the minimum comission notary nodes get for a request, it should be more than the network cost of one fallback transaction (to be explained below), but it should be economically viable to use this service on regular basis. It's suggested to use ECDSA verification price as the basis for it and then apply some multiplier to it if needed.

We'll also use NKEYS definition as the number of keys that participate in the process of signature collection. This is the number of keys that could potentially sign the transaction, for transactions lacking appropriate witnesses that would be the number of witnesses, for "M out of N" multisignature scripts that's N.

"Notary assisted" transaction attribute type

This attribute contains one byte containing the number of transactions collected by the service. It could be 0 for fallback transaction or NKEYS for normal transaction that completed its P2P signature collection. Transactions using this attribute need to pay an additional network fee of (NKEYS+1)×FEE. This attribute could be only be used by transactions signed by the notary native contract.

Native contract

It exposes several methods to the outside world:

• deposit
  Parameters: uint160(from), uint160(to), integer(amount), integer(till)
  Transfers specified amount of GAS from "from" address to native contract address and records deposited amount as belonging to "to" address with a lock till "till" chain's height. Must be witnessed by "from". "to" can be left unspecified (null), with a meaning that "to" is the same address as "from". "amount" can't be less than 2×FEE for the first deposit call for the "to" address. Each successive deposit call must have "till" value equal to or more than the previous successful call (allowing for renewal), if it has additional amount of GAS it adds up to the already deposited value.
  Returns boolean result, "true" for successful calls and "false" for failed ones.
• withdraw
  Parameters: uint160(from), uint160(to)
  Sends all deposited GAS for "from" address to "to" address. Must be witnessed by "from". "to" can be left unspecified (null), with a meaning that "to" is the same address as "from". It can only be successful if the lock has already expired, attempting to withdraw the deposit before that height fails. Partial withdrawal is not supported.
  Returns boolean result, "true" for successful calls and "false" for failed ones.
• balanceOf
  Parameters: uint160(addr)
  Returns deposited GAS amount for specified address (integer).
• expirationOf
  Parameters: uint160(addr)
  Returns deposit lock height for specified address (integer).
• verify
  This is used to verify transactions with notary contract specified as a signer, it needs one signature in the invocation script and it checks for this signature to be made by one of designated keys, effectively implementing "1 out of N" multisignature contract.
• onPersist
  This method is to be run during block processing before transaction processing occurs. For all transactions using "Notary assisted" attribute it mints and distributes to designated addresses transaction fee paid for this attribute ((NKEYS+1)×FEE).

"P2P Notary request" payload type

A new broadcasted payload type is introduced for notary requests (it can be generalized for other services). It's distributed via regular inv-getdata mechanism like transactions, blocks or consensus payloads. An ordinary P2P node verifies it, saves in a structure similar to mempool and relays. This payload has witness (standard single-signature contract) attached signing all
of the payload.

This payload has two incomplete transactions inside:

• fallback tx
  This transaction has P2P Notary contract as a sender and service request sender as an additional signer. It can't have a witness for Notary contract, but it must have proper witness for request sender. It must have "NotValidBefore" attribute that is no more than MAX_NVB_DELTA higher than the current chain height and it must have "Conflicts" attribute with the hash of the main transaction. It at the same time must have "Notary assisted" attribute with a count of zero.
• main tx
  This is the one that actually needs to be completed, it either doesn't have all witnesses attached (in this case none of them can be multisignature), or it only has a partial multisignature, only one of the two is allowed (this can be changed in the future). This transaction must have "Notary assisted" attribute with a count of NKEYS (and Notary contract as one of the signers).

Verification of this service payload:

• each transaction included must satisfy criterias outlined above
• if the sender of this payload has less GAS deposited to the P2P Notary contract than the sum of fees of all not yet processed fallback transactions for this sender, the payload is invalid
• if ValidUntilBlock values of two transactions don't match, the payload is invalid
• if the "Conflicts" hash of the fallback transaction doesn't match main transaction hash, the payload is invalid
• if the sum of "NotValidBefore" height and MAX_NVB_DELTA of the fallback transaction is more than or equal to the sender's deposit expiration height, the payload is invalid

MAX_NVB_DELTA can be policy value set according to network's
MillisecondsPerBlock and ValidatorsCount. It is expected to be around 10-20
blocks for mainnet.

Node module

Node module with the designated key monitors the network for "P2P Notary request" payloads. It maintains a list of current requests grouped by main transaction hash, when it receives enough requests to correctly construct all transaction witnesses it does so, adds a witness of its own (for Notary contract witness) and sends the resulting transaction to the network.

If the main transaction with all witnesses attached still can't be validated because of fee (or other) issues, the node waits for "NotValidBefore" block of the fallback transaction to be persisted.

If "NotValidBefore" block is persisted and there are still some signatures missing (or the resulting transaction is invalid), the module sends all the associated fallback transactions for the main transaction.

After processing service request is deleted from the module.

Regular operation flow

To be able to use the service all parties involved must deposit some amount of GAS to the Notary contract via its deposit method.

Then, when they need to send a transaction using multisignature account they independently prepare that transaction (with one signature attached for that particular participant) and a fallback transaction for it, both transactions are packed into P2P notary request payload, signed by the sender and sent to the P2P network. Participants should then wait for one of their transactions to get accepted into one of subsequent blocks.

Valid payload is distributed via P2P network using standard broadcasting mechanisms until it reaches designated notary nodes that have the respective node module active. They collect all payloads for the same main transaction until enough signatures are collected to create proper witnesses for it. They then attach all witnesses required and send this transaction as usual and monitor subsequent blocks for its inclusion.

All of the operations leading to successful transaction creation are independent from the chain and could easily be done within one block interval, so if the first service request is sent at current height H it's highly likely that the main transaction will be a part of H+1 block.

Economic motivation and payment guarantees

Designated P2P Notary nodes are motivated by fees that they receive for providing the service to the network. If they don't do anything they don't receive anything, if they correctly collect signatures they receive (NKEYS+1)×FEE GAS for each transaction. If something goes wrong and signatures don't get collected before "NotValidBefore" height specified in the fallback transaction, they receive FEE GAS from each unsuccessful attempt to complete the transaction. This motivates nodes to actually do the job they're intended to do.

At the same time if there is any request made by the client, if it ever reaches notary nodes it's guaranteed to produce a transaction that would pay the associated network fee, either main one or fallback.

Malicious behavior

Malicious clients

Each signer deposits some GAS before using the service. They can also withdraw it if need be after it expires, so this GAS is not wasted (and can be deposited only for the time one needs to use the service). At the same time this is what limits bad client behavior, sending lots of requests will result in lots of transactions one way or another and all of them would be paid for. The FEE is expected to be low enough for that to not a problem for regular users, but big enough to prevent spamming the network with service requests.

Malicious notary nodes

Notary node is limited by "NotValidBefore" attribute, it can't immediately use fallback transaction to get the FEE without doing anything. The node might also try to collect all fallback transactions and send them after "NotValidBefore" time, but it's not economically appealing as sending proper main transaction would yield at least one FEE more as a reward. Also, for collection to be successful it's enough to have just one node sending transaction to the network.

If there is a disagreement between nodes (one sends fallback transactions, another main transaction) it's solved by "Conflicts" attribute, higher paying transaction always wins and the main transaction always pays more.

Potential other uses of this service

This service can solve the problem of contract-sponsored (free) transactions, where the problem is that we want to give users an ability to send some free transactions for specific contracts, but at the same time we can't really have completely free transactions. This was disccussed in #1147 and #1468.

Using the mechanism outlined above a user can send a service request for transaction with contract specified as a sender and user specified as a cosigner (with any appropriate witness scope). Contract backend monitoring the network can see the request and based on its logic either complete it by providing contract's signature (thereby sponsoring it) or not.

[roman-khimov]

Update based on one problem noticed an hour after the post. Waiting for feedback otherwise.

Amendment №1
As "1 out of N" verification contract may be dangerous in presence of malicious notaries additional restrictions should be applied (implemented in the verify method):

• Notary contract signer could only have "None" witness scope.
• transactions with this signer must have "notary assisted" attribute
• if Notary address is a sender a check should be made that there exists another signer and that this signer has enough balance on his account

[shargon]

We can create a new message type, incomplete message, type, content and current signatures. Then it's possible to create a plugin in order to collect the specific messages an relay them. But how to prevent the spam? i think that it will be better to do that with a smart contract, they will pay for use the network.

[roman-khimov]

We can create a new message type, incomplete message, type, content and current signatures. Then it's possible to create a plugin in order to collect the specific messages an relay them. But how to prevent the spam?

Yeah, that's one of the key problems here, it's not hard to make a new broadcasted message, but it needs to be limited somehow because otherwise it's trivial to flood the network. At the moment we broadcast transactions, blocks and consensus payloads. Blocks can only be collectively signed by CNs, as long as BFT number of CNs follow the protocol it's not a problem. Consensus payloads are signed by CNs individually, that's a bit more tricky, a rogue CN can at the moment send lots of consensus payloads without any real restriction, but usually CNs don't do that and even if some would try doing so it'd be quickly detected and acted upon. Transactions are limited by sender's GAS, that works fine too, sending lots of transactions has some cost to it.

While we can theoretically accept incomplete transactions into mempool (some special part of it) and use the same GAS locking as for ordinary transactions, we'll get some variation of #1527 problem and the problem of transactions never completing signature collection (it can be mitigated, but still).

So that's where this native contract deposit scheme with fallbacks comes from.

And IMO it also shows how various P2P services can be provided in a safe manner with the result being pushed to the chain (#1584, cough). The very early draft even specifically had generic "service request" and "service attribute" things introduced, but it was decided to not overcomplicate this for now and concentrate on one specific service. We can extend it in the future, of course.

i think that it will be better to do that with a smart contract, they will pay for use the network.

Going through the chain for each signer?

[vncoelho]

We could just have a new attribute that says incomplete transaction and a specific verification script (as always).
Nodes would map in their mempool those TXs and, if possible, broadcast a merged one.
That would save load on consecutive peers.

If not merged, they will be published normally on-chain.
Next block could have a list of pending incomplete tx (which can be limited as well), and even ordered by fees until expired.

[roman-khimov]

I'm not sure I get the idea behind that. Say we want to make a transaction T with "3 out of 4" multisignature contract (MC) for A, B, C and D keys. It should have MC as one of its signers and if MC doesn't have proper invocation script (and it doesn't until we've collected all signatures) T is invalid, it can't be added to mempool or block. We can theoretically allow some transactions with specific attributes to enter mempool without full validation (though that already can cause a lot of troubles to prevent abusing this feature), but adding them to the block doesn't seem right.

[vncoelho]

We are also writing this paper about Smart Account importance on Decentralized Governance: https://www.overleaf.com/read/fvvnhrbtgxpb

This PR is a very important feature we need in NEO, there many good use cases.
We may add something related to P2P for this.

NEM blockchain also has some similar native contracts that are very useful for this kind of use.

I will ask @igormcoelho to take a look here, we have been engaged in this idea for some time as well.

I will soon also reply your last comment,@roman-khimov.

[vncoelho]

It can be added to the block, @roman-khimov, we just need the Native Contract to keep a list o pending incomplete tx's.
As much GAS you pay more blocks you can leave there.

It can also stay on the mempool as an incomplete tx's and as soon as nodes merge Signatures they broadcast the more complete tx. But we need to define a field for ExpiringTime on both mempool and on the state of the native contract.
The GAS for expiring time can be the sum of all merged incomplete txs, even from different callers.

I was just talking to @igormcoelho right now and he again mentioned that concept of Volatile Storage as well, which is another vision that we can use for storage that will be deleted within some couple of blocks.

[igormcoelho]

We have discussed this topic previously, but the way I see now, in order to prevent spam attacks and make it very easy to use (without any deploy or volatile storage), I would adopt the following strategy:

• Create the concept of PendingWitness
• Allow transactions to be relayed even if PendingWitness InvocationScript is not attached (all Verifications should be present)
• Require that Sender witness script is attached and GAS price is being paid (Sender is never PendingWitness)
• Add a DueDate on the transactions (or reuse existing field)
• Adjust the MultiSig strategy to a slightly different format.. instead of performing CheckSignature, perform several CheckWitness (this resolves any possible ordering problem) - SEE PRACTICAL EXAMPLE BELOW
• Validate witnesses in precise order: if some verification fails, tx is discarded; if some verification is incomplete, do not proceed and keep tx until further update (up to DueDate limit) [EDIT]: witnesses can be validated in any order as they are stateless.
• For extra security, limit the number of txs with pending witness in mempool (maybe 10%?)

So, with this strategy in mind, Alice could send a transaction where she pays as Sender, but its interested in some other PendingWitness for MultiSig that requires using CheckWitness inside it, for other pending witnesses. Nodes in P2P will keep relaying this transaction, while other parties may also attach missing witnesses from pending list.
Finally, if consensus node has all witnesses with validated status (as Witnesses should be verified in the exact order of the transaction), it can add the transaction to some block, before DueDate. If it cannot finish the completion of witnesses in time, it can still schedule transaction to block at precisely the DueDate, making Sender pay for necessary fees, and automatically making internal scripts fail, as some witnesses may not be available for execution on block.

A useful feature for consensus is to allow CN to fill an extra binary field after tx header (thus not affecting tx hash but affecting block header hash), that confirms the existence or not of every PendingWitness. In this case, some CN may intentionally inform that it has some tx, but didn't receive some witness... and other CN may have received the witnesses, but will need to decide if they agree or not with proposed block.
To prevent view changes, best strategy is to simply follow the speaker, and let it decide if it puts or not complete tx (some byzantine attack) as Sender will pay the costs anyway. This is something we need to decide: whether we trust the speaker or the tx sender. Anyway, in my opinion, this proposal is fully implementable and resolves any forseen spam situation.

Note that consensus node may also choose not to schedule incomplete tx to block (if P2P load is not high, this is better than punishing eventual incomplete signature failures 100% of the time).

====== PRACTICAL EXAMPLE =======
Transaction:

• Sender: Alice witness (NON-PENDING)
• cosigner 1: Bob (PENDING)
• cosigner 2: Adjusted MultiSig script (NON-PENDING)

Adjusted MultiSig script

• Invocation: empty
• Verification:

      "Count the following"
      Count += Runtime.CheckWitness(Alice)
      Count += Runtime.CheckWitness(Bob)
      Count >= 2 (MultiSig condition)

The extra advantage of AdjustedMultiSig is that each depending witness can also be some MultiSig or any other type of witness (not just signature).

[igormcoelho]

Please take a look on the strategy above @vncoelho @roman-khimov @shargon @Tommo-L ... on short: we just need to add a flag for Pending in some cosigners (except Sender), and a bitstring after txheader to quickly inform which are completed or not. The rest is easy to do: some adjusts on mempool (limit to 10% for pending?) and in selection of tx during consensus (only select tx with pending witness on DueDate, not before).
This resolves not only multisig problem, but any problem regarding interaction of "players" during p2p, to agree or not on the execution of some script.
Possible attacks: (1) spam is nearly impossible and GAS will be consumed anyway.. could be possible if attacker lets pending for a while and completes lastly with some non-pending last failed... this can be controlled by DueDate but attacker may still lose GAS if pending witness is not received in time. (2) byzantine CN may intentionally publish incomplete tx... damage will be reversed to the image of such CN, as it can only be performed intentionally (rather unexpected in my perspective).

[igormcoelho]

Sorry for one more post: I've double checked and in fact it's really impossible to spam the network with above proposal.. the reason is that no one would ever be able to invalidate any pending witness (system would simply discard its InvocationScript), so Sender would just waste its fees in any possible "attack". I also checked that witness could also be assumed for checking in any order (not just sequential), and in proposed AdjustedMultiSig scenario, this witness would pass OK even before other pending witnesses are received (just assume they are also OK). When puting tx on block, CN could finally inform that these don't exist, and tx would be invalidated (and GAS tx still paid).

[roman-khimov]

I see several problems with PendingWitness approach:

• the need to synchronize parties over the transaction signed
  All participating parties have to wait for transaction to appear on P2P network first, before trying to add their signatures. This is a big problem for scenarios like NeoFS inner ring nodes, we can't rely on the fact that one node will create (and sign to be a Sender) a transaction.
• signature propagation over P2P
  Transactions are identified by hashes and this hash doesn't include witnesses, thus when A sends an incomplete transaction T (signed by A only) and it propagates over the network, B can't really send the same transaction with two signatures attached as every node on the network already has T (incomplete, but it's still T identified by its hash)
• the need for CNs to synchronize their view of transaction witness state (pending/complete)
  You can't trust single CN with their view of this status and I think it's the same as missing transaction for consensus process, meaning that either everyone agrees with the status or nodes with different status do a view change
• lack of motivation for anyone to actually collect signatures
  CNs will include the transaction in question in a block anyway, it's even a bit easier for them to include it after DueDate, because the size of the block is going to be smaller then (less witness bytes)

[igormcoelho]

Interesting replies...

• the need to synchronize parties over the transaction signed
  I didn't understand this point, can you ellaborate? I'm not assuming that people should submit their transactions at the same time, so I don't see any synchrony requirement here (besides the maximum expiration time for tx). Maybe a practical example for NeoFS would make me see the point you mention.

• signature propagation over P2P

Transactions are identified by hashes and this hash doesn't include witnesses
That's why we need an extra flag for that.

• the need for CNs to synchronize their view of transaction witness state (pending/complete)
  that's true, in my perspective, CN which are correctly implemented will always try to push complete transactions, as expected

• lack of motivation for anyone to actually collect signatures
  Same as above... correct P2P are necessary for a healthy infrastructure. If P2P cannot efficiently relay messages and follow the protocol, nothing will work as expected.

[ZhangTao1596]

@neo-project/core I think this proposal is more pratical than neo-project/neo-modules#487, and neo-go already has the implementation. @neo-project/ngd-shanghai can implement it in neo-core. @erikzhang

[vncoelho]

I am still in favor of an implementation that deals with a native contract that merges it on-chain, not using the network communication channel itself.

Otherwise, I am in favor of a plugin, as @shargon proposed, which aggregates and replay. That will be enabled just by those that want to provide this service.

@shargon, let's move your plugin forward at least.

[roman-khimov]

This was specifically designed to do things off-chain (but on the P2P network) for reasons mentioned above (reducing the number of transactions, reducing delay). On-chain is too inefficient in many cases (time, GAS, processing overhead).

Nothing has really changed since #1573 (comment) (except https://neospcc.medium.com/multisignature-transactions-with-notary-subsystem-cbbd277b2c39 has some nice pictures in it!), every single day this scheme works in two NeoFS public networks and we really enjoy it: fast, easy and reliable. Every single day IR receives events from the notary pool, checks request (transaction) validity and approves (or not) things. Every single day we also enjoy sponsored transactions via this service (#2577 is not just a wall of text, https://github.com/nspcc-dev/neofs-contract/blob/ca647d67ed3c2b51bf76f74287c2559a2eede13b/proxy/doc.go is a real thing deployed to real networks and it works). We're concentrated on NeoFS-specific things, but this can be leveraged in many many other scenarios (like cool sub-block response time oracles, for example). If it could be used on Neo networks, of course.

[ixje]

Sponsored transactions would have made it much more practical to do what we did as Consensus as well. I was actually looking into this pay-by-contract and found it impractical atm to do safely.

+1 for this/#2577