DOS attack vectors

[bobbinth]

Motivated by #7 (reply in thread) I'd like to list out potential DOS attack vectors so that we could start thinking about potential mitigating strategies. This will be an initial list, and we'll probably add to it as time goes on.

Locally proven transactions

I think attack surface for locally proven transactions is relatively small. A malicious user could do a few things though:

• Submit an invalid proof. This may force the operator to expend resources on proof verification. This is not a huge problem as proof verification is relatively quick (i.e., a couple of milliseconds and we can probable improve it further) - but we should still make detection of invalid proofs as easy as possible.
  *. Submit an invalid transaction with a valid proof. For example, a transaction which consumed an already consumed note, or is executed against an old account state. Unlike the previous case, this type of an issue cannot be validated in isolation and will require some lookups in the DB (or some in-memory structure).

I think there are two broad strategies of mitigating the above attacks:

1. Coming up with a sequence of low-costs steps which would detect that something is invalid as quickly as possible.
2. Forcing the attacker to expend asymmetric amount resources even for invalid transactions (i.e., the attacker would need to spend more resources on generating an invalid transaction than the operator would need to spend on checking it).

Network transactions

These are the transactions which are executed by the operator. These break down further based on the type of notes consumed. Specifically, transactions which consume notes with type 11 are intended to be executed by the operator without any additional user inputs. Transactions which consume notes with type 00 or 10 are intended to be executed by users locally, but users can ask the operator to execute such transactions (i.e., if a user is on a low-power device and cannot generate a local proof). Attack vectors for these transaction categories are different.

Transactions consuming notes with type 11

The attack vectors I see here are:

1. A note is crafted in a way which makes identifying an account against which it is supposed to be executed difficult. I'm actually not super happy with the 13-bit prefix solution I described here - so, we should try to come up with something better.
2. A note does not have a known use case tag (this is for notes with prefix 110). I actually don't think that this is an attack vector as operators can probably just ignore such notes.
3. A note has a script which when the operator tries to execute it, fails at the last moment. This could force the operator to execute most of the transaction thereby expensing resources (though these resources would be relatively small as we won't get to the step of proof generation - which is the really expensive part).

I actually don't think that the last attack is concerning. The reason is that the attacker would need to pay for this attack quite a bit. Specifically:

1. They would need to pay transaction fee for creating such a note.
2. Assuming they don't want to leave the note unconsumed, they would need to pay a fee for consuming.

Thus, forcing the operator to execute code for malicious transaction requires paying fees for two transactions - which probably makes this attack impractical at a large scale.

Transactions consuming notes with type 00 or 10

As mentioned above, these notes are indented for local execution, but users may ask operators to execute transactions consuming such notes for a variety of reasons.

The main attack vector here is similar to point 3 from the previous section: users may craft transactions in a way which fails at the very last step. However, in this case, crafting such transactions is nearly free to the user. What's worse, is that we can't force the user to do any kind of significant work as one of the main use cases for asking operator to execute such transaction is for users on low-power devices.

This is a general problem for account abstractions (e.g., see here) - but I think in our case it may be a bit simpler because execution is only a small part of the proving process (i.e., like less than 100th). This should enable strategies which are not available in other settings.

Two broad strategies for addressing these attacks are:

1. Detecting that a transaction will fail as quickly as possible (i.e., without having to execute the code).
2. Forcing the user to pay fees even for failed transactions. Not clear how we can do this yet.

[hackaugusto]

Notes with invalid code

It is possible to hit some code paths that panic in the assembler, here is a simple example:

begin adv.keyval end

Sending such a note causes a panic. Depending on how the system is integrated this can result into a crash. (I have not looked up on the binary representation codepath, so I'm not sure if that is an issue there).

[bobbinth]

This should actually be a bug - no program should result in a panic in the assembler (we should return an error). However, this specific case probably wouldn't be DoS attack vector as on-chain representation of code is serialize AST. But if there is a similar situation in deserializing AST and converting it to MAST, then that would be a DoS attack vector.

[hackaugusto]

This should actually be a bug

Agreed, but my assumption is there will be bugs, and in the client design the thread that handles external data should be isolated to allow for undetected panics. Another example of this was the empty blocks begin end that we recently fixed 0xPolygonMiden/miden-vm#628

[bobbinth]

Agreed! In fact, we will probably end up running a separate machine for proving each transaction - so, even if the entire machine crashes during proof computation, it will not bring down the node (which would be running on a different machine).