(from #1555: https://github.com/neo-project/neo/pull/1555#discussion_r408706349)
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
Where in the software does this update applies to?
It is recommended to have an aggregate data on the chain. Or it's better to communicate between these service nodes directly.
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.
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.
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.
@roman-khimov I think we need this, as we have 21 committees, it'll be a hard work for them to do multisign.
Currently, we have oracle validators, neofs ir validators and committees all need to do multisign.
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.
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.
On the other hand, we can also consider using a native contract, like TaskContract?
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.
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:
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.
Can be done by a contract, but going through the chain for "M out of N" multsignature means that:
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.
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.
It exposes several methods to the outside world:
(NKEYS+1)×FEE).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:
Verification of this service payload:
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 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.
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.
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.
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.
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.
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.
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):
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.
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?
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.
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.
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.
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.
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:
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:
Adjusted MultiSig script
"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).
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).
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).
I see several problems with PendingWitness approach:
DueDate, because the size of the block is going to be smaller then (less witness bytes)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.
the need to synchronize parties over the transaction signed
I didn't understand this point, can you ellaborate?
PendingWitness scheme requires sender to be non-pending which practically means that someone has to send transaction first and only after that any other cosigners can join the party and send their signatures. Which obviously raises a question of who sends this transaction and how long for other parties to wait for this transaction to come.
Consider NeoFS inner ring nodes, they use standard "M out of N" contract, say 5 out of 7. It means that there are seven nodes on the network and they need to invoke some contract that will do CheckWitness for this "5 out of 7" contract. With PendingWitness only one node can actually "propose" a transaction to sign and all the other nodes need to get it first, then sign. Notary scheme from https://github.com/neo-project/neo/issues/1573#issuecomment-704874472 doesn't have this requirement, if they can all independently produce the same transaction (and they can) then they can shoot their messages right away and let notaries collect them.
As the preview4 is coming pretty soon, this issue becoming more important for committees, oracle and FS nodes. We need to have a better and easy to use multi-signature mechanism for those essential roles. What do you think about the discussion and proposal here? @erikzhang
I think that we can use https://github.com/neo-project/neo/pull/2101
It's certainly not for preview4, for preview4 we should just use the simplest possible (temporary) solution. But we're working on it and the only things left at the moment are P2P payloads (but they're like 90% complete) and the service itself. I think we'll have a complete solution in neo-go next week, but we'll need to test it/try it for NeoFS nodes, see how it all works in action. In January it should be stable enough to port to C# node.
@neo-project/core I think this proposal is more pratical than https://github.com/neo-project/neo-modules/pull/487, and neo-go already has the implementation. @neo-project/ngd-shanghai can implement it in neo-core. @erikzhang
Most helpful comment
@roman-khimov I think we need this, as we have 21 committees, it'll be a hard work for them to do multisign.