Network Transaction DOS Attacks

[PhilippGackstatter]

We call notes targeted at network accounts network notes. These notes have some potential for DOS-ing the network transaction builder (NTB), which in the centralized setting is the node operator.

If I understand correctly, the idea is that the node tries to execute any network note against the account it is targeted at a number of times to see if it will succeed. There will be an upper limit to this, but it must be a few times. For example, in a DEX scenario where my note sets the slippage conditions, it might only succeed after a few attempts, which is a valid scenario.

Note execution cycles

A maliciously designed note could take the max number of cycles the NTB is willing to execute. So the NTB will waste max cycles * number of note execution attempts cycles in total, which could be significant.

Lack of fee for failed execution

The problem here is that the note does not pay any fee to the network transaction builder if it does not succeed.

An attacker can exploit this by sending a note to a network account that the attacker knows will never be able to be consumed. For example, this could be a custom P2ID-like note targeted at network account X according to the note tag, but the actual note inputs target account Y. (I say custom note, because the regular P2ID note is well-known and can be statically checked in Rust code, which doesn't prevent the DOS-ing per se, but makes this example generally applicable. Realistically, for the maximum DOS effect, this would be a note which uses the slowest available Miden VM API.)
Now the NTB will see the target of the note in the note tag and try to execute the note against that account a bunch of times.

One idea to prevent this in-protocol is to make network notes pay a penalty if they're consumed by an account whose account ID does not partially match the one from the note tag. This is the case if the attacker tries to reclaim their own note after the NTB has executed it a few times. But reclaiming might not even be necessary for the attack to work for example if the note does not contain a valuable enough asset. That makes the penalty useless. Additionally, since we only put 30 bits of the account ID in the note tag, creating an account with a match in that 30 bit part of the prefix is not too computationally difficult and then the note could be reclaimed by that account and the penalty is bypassed. Only one such partial match of target network account ID and attacker account ID is needed to run this attack against the NTB repeatedly without penalty.

Reducing attack surface

To reduce the attack surface, each network account should expose the set of note script roots it is willing to accept. It may be good enough if this is by convention. For example storage slot 0 of the account is expected to contain a storage map of script roots which represents that set. (See also #1275 (comment)).

This helps with both problems insofar as a maliciously crafted note cannot be sent to every network account. So not every network account will be spammed with useless notes. But, an attacker just wanting to slow down the NTB can create a network account themselves and put the malicious note script root into the allowed note set.

NTB deny strategy

An NTB could apply a "deny strategy" to network accounts. For example, if an NTB executes a few transactions and notes against some network account and most or all of them fail, then it might ignore this account for a while. Figuring out the acceptable failure ratio here might be tricky though without penalizing valid use cases (e.g. notes with slippage conditions in a DEX could fail a lot).

The best metric for the NTB might ultimately be whether the average fees from a network transaction against a certain network account are high enough for the NTB not to make a loss over some period of time. If the NTB makes a loss consistently, the network account is put on the deny list for some time or even indefinitely - these could be individually set strategies if network transaction building becomes decentralized.

This strategy to evaluate the profit of a network account together with the set of notes that a network account is willing to accept might be a reasonably good enough defense.

If anyone can think of other DOS attacks with network notes (or non-DOS attacks too) as well as mitigation strategies, feel free to add those in the discussion.

[igamigo]

So the NTB will waste max cycles * number of note execution attempts cycles in total, which could be significant.

Do we know how this could translate to real world numbers? I think this would depend on the strategy used by the NTB to try to execute and include network transactions as well (which I'm not sure is fully defined yet) but it'd be nice to get a sense of how bad an attack could be.

For example, if an NTB executes a few transactions and notes against some network account and most or all of them fail, then it might ignore this account for a while

Overall it feels like the note sender could cause problems in most scenarios - could you not penalize sender account IDs as well/instead? eg if a note stalls execution, its sender account is put into an LRU cache that provides some info to the NTB about what to prioritize next.

[bobbinth]

Overall it feels like the note sender could cause problems in most scenarios - could you not penalize sender account IDs as well/instead? eg if a note stalls execution, its sender account is put into an LRU cache that provides some info to the NTB about what to prioritize next.

This could be tricky for two reasons:

• The attacker could use many accounts for these attacks.
• In the future, we'll add a way to "anonymize" senders (i.e., where the sender of a note will not be the account that issues the note in the first place).

[PhilippGackstatter]

Do we know how this could translate to real world numbers?

I don't, but to get those, we'd have to run a benchmark for transaction execution with those parameters on the hardware that we'll deploy the NTB on.

[bobbinth]

One idea to prevent this in-protocol is to make network notes pay a penalty if they're consumed by an account whose account ID does not partially match the one from the note tag.

We probably don't want to do this (even if we could). The main reason is that the sender should always have the ability to reclaim a network note. For example, if I created a note for a trade against an AMM, if my trade doesn't go through, I should be able to reclaim the assets.

The problem here is that the note does not pay any fee to the network transaction builder if it does not succeed.

I think imposing fees for failed execution (even if we could impose them), could be problematic. This basically gives an incentive to the NTB to fail some notes. For example, if NTB knows that a note could result in some action in a couple of blocks, and this action is somehow undesirable for NTB, it could fail the note "prematurely". This is a concern only when the network is decentralized, but a concern nevertheless.

So, overall, in my mind are a couple of guidelines:

• An NTB should not have the ability to "fail" a note.
• An NTB should not have the ability to prevent the note from being consumed by someone else.

Now, this doesn't mean that an NTB needs to keep trying to execute some notes forever - but I think this could be a part of a specific block producer's strategy, rather than protocol-wide setting.

Some more general thoughts:

The attack described here is not free. The attacker has the following costs:

• They need to execute and prove a transaction that creates a network note.
• They need to pay a fee for the above transaction.

The first point means that the attacker needs to spend computational resources which are quite high as compared to what the node would spend for a small number of execution attempts. This is because proving a transaction would be 10000x (or maybe even more) expensive than just executing it. So, even if a node tries to execute a note 100 times, the attacker would still need to spend more resources. This doesn't mean that the attack is not profitable: the attacker could be willing to spend these resources (especially for a short duration of time).

The second point should be much bigger of a deterrent, assuming the same transaction cannot be used for something else. Basically, if the attacker creates these notes solely for the purpose of attacking the network, they'd need to pay a pretty significant cost.

The fact that the attacker needs to pay a fee for creating the note in the first place, may be something we can play around with. For example, the cost for creating network notes could be higher than for regular public notes. Or maybe even it could very on per-account basis. That is, the fee for creating a network note for a given note tag could depend on how many unconsumed network notes with the same tag already exist in the system. Though, how to implement this efficiently is not clear to me yet.

To reduce the attack surface, each network account should expose the set of note script roots it is willing to accept.

I think this is a good idea and should drastically increase the cost of the attack because it would eliminate potential alternate uses of a malicious network note.

I wonder, however, if this should be a feature for all accounts (rather than just network accounts). That is, all accounts should be able to specify scripts of notes that they are able to accept. Though, this would be optional for non-network accounts. One question is how this info should be specified.

[bobbinth]

To summarize some of my thinking on this:

• It is a good idea to let accounts specify what notes they are able to accept. For network accounts this should be mandatory. We need to come up with a concrete design of how to do this.
• Strategies of how many times to execute a note, how many cycles a note execution can take, when to stop processing notes against a given network account etc. feel like concern of a node and not the protocol. So, we probably should probably discuss them separately.
• It could be interesting to see if we should do something in the fee design to make network-note attacks more costly. But this is also a separate concern.

One other thing I was thinking about: could there be a way for the users to send "hints" to the node to say "try executing this note now". This could be a way to "rehydrate" notes that the NTB decided to "give up" on. How to do this in an incentive-compatible way is not clear to me though.

[PhilippGackstatter]

That is, all accounts should be able to specify scripts of notes that they are able to accept. Though, this would be optional for non-network accounts.

I definitely see the benefits for network accounts as it allows the NTB to exclude the majority of notes from execution attempts against a given network account. That is a big advantage and definitely worth doing.

For public accounts, it may be useful for a client to check which note types an account is willing to accept. But the problem is that these are only hints and so there could be false positives, e.g. a public account says it is willing to accept a P2ID note but its account interface does not actually expose the necessary receive_asset procedure. So it would just be one more data point to say that a given note is incompatible with an account, but not that it is for sure compatible with an account (without additional checks). Checking against the account interface is actually the more reliable way because it is not a hint.
It would also mean that creating an account is "more verbose" (or putting it bluntly, more annoying), i.e. users now have to specify the roots of all notes they want to accept.

For private accounts I don't see any use case were this would be beneficial.

I'll open an issue to discuss a concrete design for this.

could there be a way for the users to send "hints" to the node to say "try executing this note now". This could be a way to "rehydrate" notes that the NTB decided to "give up" on. How to do this in an incentive-compatible way is not clear to me though.

I was wondering about something similar, but since such a hint could not really be proven, it can also not be charged a fee for. That would then be a free DOS mechanism on the NTB.

If we're willing to introduce edge cases, then one potential way could be for an account to consume a network note that it wants to rehydrate and then create the same note again with the only difference being the serial number (to ensure the nullifier is different). If the batch/block builder sees such transactions, it does not charge the regular fees for consumption/creation but a smaller amount.
But, this does introduce special cases into the fee mechanism (complexity) and could also be used to spam batches/blocks with mostly useless transactions for relatively cheaply compared to other ways. So it's not really incentive-compatible either.

[bobbinth]

For public accounts, it may be useful for a client to check which note types an account is willing to accept. But the problem is that these are only hints and so there could be false positives, e.g. a public account says it is willing to accept a P2ID note but its account interface does not actually expose the necessary receive_asset procedure. So it would just be one more data point to say that a given note is incompatible with an account, but not that it is for sure compatible with an account (without additional checks). Checking against the account interface is actually the more reliable way because it is not a hint. It would also mean that creating an account is "more verbose" (or putting it bluntly, more annoying), i.e. users now have to specify the roots of all notes they want to accept.

For private accounts I don't see any use case were this would be beneficial.

In my mind, the main potential benefit is additional security. For example, we could define a private (or public) account that can only accept P2ID notes. This then would be verified in the kernel and the user would have a guarantee that no other note could be accepted by the account. Whether this additional security is meaningful, is not clear to me though (unless we also can restrict the set of allowed transaction scripts somehow).