[pre-MIP] Remove two-pass logic

[L-as]

See

• DoS Vulnerability Mitigations in mip-zkapps.md
• Updated Transaction Snark Statement mina#12000

for background.

The whole reason for the existence of this is the (literally) dumb mempool, however, the mempool can be not dumb and yet still be fantastically simple.
Mina, while superficially similar to Ethereum and other account-model style protocols, is in fact much more similar to Bitcoin and derivatives.
zkApp commands are (mostly) deterministic, and very limited in what they can do.
The reason you pay fees on Ethereum is because regardless of whether your transaction is correct,
a lot of work has to be expended to verify that it didn't work.
This isn't true on Bitcoin. On Bitcoin, you do a simple check to see if the input UTXOs are available.
On Mina, you do a simple check to see if the preconditions hold.

The motive, then, for Mina having a two-pass system (as described in ), is that you could theoretically destroy throughput, described as such:

Such processes can be repeated to completely fill the mempool with "broken" transactions such that honest transactions cannot be processed; the economic incentives for filling the mempool are bypassed.

This however is only true in the naive mempool model.
Bitcoin and many other blockchains have the exact same problem, but it's easier to see in their case,
the transactions form a DAG trivially.
But so is it in Mina's case, there is almost an isomorphism because Mina's model and the UTXO-model, such that
you can view preconditions as input UTXOs and the resulting changes as output UTXOs.
You can thus form a DAG of zkApp commands such that dependents point to dependencies.

Let's revisit the original attack, but elaborated (as was done in private discussions):
We have in the mempool some huge number of commands that have some state as precondition. They in total pay a huge fee.
The adversary then submits a command that has a higher fee than any individual command in the mempool until now.
In the naive model, it gets prioritised, but now the other commands can no longer pass, meaning the total fees taken is much less without the two-pass system, where fees are always taken.
But let's modify our mempool such that it maintains the DAG explained above.
We can now view our entire mempool as a single DAG (with perhaps completely disjoint portions),
the task then is to consider whether the new command can be inserted into the DAG, such that the resulting
DAG has a higher total fee than before.
If yes, insert, if no, ignore.
In the example case, the total fee payout would be considerably less than before, meaning that the attack is avoided.

In the case of indeterministic transactions, for example, add 100 Mina to an account without any preconditions,
this can in the mempool be assigned "fake" preconditions, and also be used as a dependency for other commands
that might require that amount of Mina.

Or, it might conflict with some precondition on the exact amount of balance in an account, meaning it could be rejected.

Other blockchains

In Cardano, there is/was no fee-prioritisation system. Everything was FIFO.
The above attack was thus impossible from the start, and Cardano transactions would not be
dropped from the mempool.

In Bitcoin's reference implementation, the following explains how it works:

• https://github.com/bitcoin/bitcoin/blob/717a4d89449f607c5203138b128e1e30b4493f2c/src/txmempool.h#L243
• https://github.com/bitcoin/bitcoin/blob/717a4d89449f607c5203138b128e1e30b4493f2c/doc/policy/mempool-replacements.md
• https://github.com/bitcoin/bitcoin/blob/717a4d89449f607c5203138b128e1e30b4493f2c/doc/policy/mempool-limits.md

The mitigation of the above attack is explained as such:

3. The replacement transaction pays an absolute fee of at least the sum paid by the original transactions.

Rationale: Only requiring the replacement transaction to have a higher feerate could allow an attacker to bypass node minimum relay feerate requirements and cause the network to repeatedly relay slightly smaller replacement transactions without adding any more fees. Additionally, if any of the original transactions would be included in the next block assembled by an economically rational miner, a replacement policy allowing the replacement transaction to decrease the absolute fees in the next block would be incentive-incompatible.

Motivation

• Consider an account that rapidly has actions added to it.
  We wish to "reduce" the actions, as such we have the action state as a precondition,
  however, this precondition is likely to fail. Paying fees on the failed transaction is prohibitive.
• The resulting system is much simpler, removing the need for the complex ad-hoc mitigations.

[bkase]

Hey @L-as thanks for the feedback.

@nholland94 and @mrmr1993 and I happen to be in the same room, so we dug into this a bit together.

You're argument is that we're more similar to Bitcoin than Ethereum. In reality, Mina is different to both. The ordering of the transaction dependency graph is not acyclic (unlike Bitcoin, like Ethereum). Ethereum's solution is to segregate accounts into those that can create fees and those that can execute from -- in Mina we allow a mixed model; but this means there is a coupling between fee-paying and smart contract execution. These interdependencies cause cycles in the transaction dependency graph.

Fee payments need to be deterministic in order to avoid DoS attacks. Our non-deterministic operation outcome can affect fee-payments. The two-pass ledger system allows us to exist in this model while ensuring that trivial DoS attacks against are mitigated. This two-pass system allows us to keep the more powerful transaction system (since we can mix fee-payments and smart contract logic) as well as enabling smart contracts paying fees in the future (currently disabled).

It's messy as a consequence of complexities in the scan state (which we can fix!), but conceptually it's the sequential process of collecting fees first, and then applying transactions which is pretty simple!

[L-as]

@bkase

I don't see how removing the two-pass system and simplifying it means you can't have mixing. The above wouldn't restrict how Mina's transaction logic works. Elaborate?

FWIW, the dependency graph can't be "cyclic", obviously. I think what you mean to say is that there are multiple valid orderings. The important part is that checking whether a transaction is valid doesn't involve executing arbitrary logic, it's merely a check that a proof is correct.

[mrmr1993]

The two-pass system was designed to meet the following constraints:

• any account may participate in an atomic zkApp update via one or more 'account updates';
• an account update may change any field in the account, and is not necessarily guarded by a nonce;
• a zkApp command may fail to meet its preconditions and be rejected, causing its account updates not to be applied;
• the validity of a fee-payment depends on some fields of the account; in particular the 'send' permission must be compatible with signatures, and the balance must be sufficiently high.

With these properties, any single transaction can affect the (in)validity of any -- or potentially every -- transaction in the pool. As such, a cleverly constructed series of transactions could fill the pool with txns that will be invalidated after choosing any one of them, starving the block producers and the network of transactions.

As @bkase mentioned above, we decided from here that the best way to protect the block producers from such DOS attacks is by collecting the fees for the transactions in a block first (stage-1) before applying the account updates (stage-2).