Support for parallel nonces to allow for safe submission of concurrent transactions

[soareschen]

Summary

Having parallel nonces will allow accounts such as from IBC relayers to safely submit concurrent transactions to the same block with future versions of Tendermint.

Problem Definition

With the imminent introduction of priority mempool, ABCI++, and MEV proposers, it is becoming increasingly unsafe to submit multiple transactions from the same account to the mempool due to transaction reordering. This is because the current nonce design uses a single account sequence that is required to be monotonically increasing. If two transactions with the nonce N and N+1 are reordered, the transaction with N+1 nonce will fail with account sequence mismatch error.

This was not an issue in the original behavior for Tendermint v0.34.19 and earlier versions. The transactions would be committed in the same order as they were submitted, and thus there were no issue with the account sequence being invalidated by transaction reordering.

IBC relayers such as Hermes currently rely on this behavior to submit concurrent transactions to the chain under various circumstances. A notable example of this is during congestion events such as the Osmosis epoch block which takes a very long time to compute the LP rewards. This would result in subsequent blocks such as 5655412 to contain 15 or more transactions to be committed by the same relayer, such as osmo1ks0qeq9vyt9l7vgasaajd49ff0k8klur3p2jrp.

It is challenging to find alternative workaround for transaction activities such as above. In such case, the relayer cannot reduce the number of transactions, because it cannot forsee that Osmosis is taking extra long time to produce the epoch block. At the same time, IBC packets are continuously arriving from other chains, requiring new IBC transactions to be submitted.

It would also be inefficient for the relayer to delay submitting new transactions until the previous transaction is cleared. With the real world example above, the relayer would have needed to wait for 15 or more blocks in order to clear the transactions after the epoch block, during which more IBC transactions may arrive.

While having multiple wallets with fee grant may alleviate the problem up to a certain degree, it would require significant maintenance burden for the IBC relayer to sustain the current performance. For the above case, the relayer would need to create 15 or more wallets in order to submit the same number of concurrent transactions during the Osmosis epoch block.

It is also worth noting that the IBC relayer needs to sustain good performance even with 10x to 100x increase in IBC traffic. So in the future, it may need to submit as many if not more concurrent transactions to the same block during normal times.

Proposal

A more sustainable solution is for Cosmos SDK to introduce parallel nonces that are non-overlapping, so that the IBC relayer can use different nonce series to submit concurrent transactions to the same block.

The current data tells us that the relayer would need at least 15 parallel nonces to handle heavy IBC traffic such as during the Osmosis epoch. To scale for increase in IBC traffic in the future, it would be ideal if account holders can dynamically create up to hundreds of parallel nonces.

References

• Support for priority mempool chains informalsystems/hermes#2350

[alexanderbez]

Having parallel nonces will allow accounts such as from IBC relayers to safely submit concurrent transactions to the same block with future versions of Tendermint.

You mean being able to submit txs from the same account with multiple nonces? Or do you mean executing txs in parallel?

With the imminent introduction of priority mempool, ABCI++, and MEV proposers, it is becoming increasingly unsafe to submit multiple transactions from the same account to the mempool due to transaction reordering.

You can totally submit txs with varying nonces from the same account with ABCI++ and app-side mempool. What makes you say it's unsafe? You mean it interferes with MEV execution order? Note, the app-side mempool can and will handle multi-dimensional ordering, i.e. nonces will take precedence over priority when there are conflicts.

In any case, I do agree with you in the the current system of nonce management is weak and not flexible. In fact, I like @ValarDragon idea on nonce refactor. I'll allow him to fully describe it in a followup comment, but it's similar to your proposal.

The gist of it is, that accounts have nonce "lanes" or "buckets", and they can submit txs using a nonce from any one of these nonce buckets, e.g. [<0-1000>, <1001-2000>, ...], where each nonce must be monotonically increasing in it's respective bucket. The fixed number of buckets is essentially equivalent to how many txs an account can submit at once without having to worry about re-ordering. This is similar to how one would scale using Zookeeper. Anyway, I'll let @ValarDragon further explain and/or correct me. But I do agree that we should revise this part of accounts 👍

[soareschen]

You mean being able to submit txs from the same account with multiple nonces? Or do you mean executing txs in parallel?

I meant submitting txs with multiple nonces. I didn't meant having the transactions executed in parallel, sorry for the confusion. I guess we need better terminology here, as the parallel and concurrent transactions I meant here are for multiple transactions from the same sender being present at the same time in the mempool, and can be potentially be committed into the same block with different sequential ordering.

You can totally submit txs with varying nonces from the same account with ABCI++ and app-side mempool. What makes you say it's unsafe? You mean it interferes with MEV execution order? Note, the app-side mempool can and will handle multi-dimensional ordering, i.e. nonces will take precedence over priority when there are conflicts.

What I meant is that it would be dependent on the application logic to determine whether concurrent transactions are safe. With the current implementation of Cosmos SDK, it may be unsafe due to nonce reordering. For MEV, it will have to depend on whether the specific ABCI++ application would reject proposed blocks containing nonces in reverse ordering. However in general, an ABCI++ application do not make any guarantee like multi-dimensional ordering, so we cannot make assumption that it is guaranteed by all ABCI++ applications.

The gist of it is, that accounts have nonce "lanes" or "buckets", and they can submit txs using a nonce from any one of these nonce buckets, e.g. [<0-1000>, <1001-2000>, ...], where each nonce must be monotonically increasing in it's respective bucket.

Yes, this is pretty close to what I meant in the original post. The additional consideration for this case is that the IBC relayer would need at least dozens of lanes or buckets to maintain the current throughput.

[alexanderbez]

I just want to clarify, with ABCI++ via TM v0.37 and SDK v0.47, the app-side mempool will respect nonces and clients/relayers CAN submit multiple txs from the same account.

In the future, we will explore and evaluate more sophisticated nonce management and proposed above :)

[yihuang]

I just want to clarify, with ABCI++ via TM v0.37 and SDK v0.47, the app-side mempool will respect nonces and clients/relayers CAN submit multiple txs from the same account.

In the future, we will explore and evaluate more sophisticated nonce management and proposed above :)

I guess we can support sth similar to ethereum:

• hold the tx with nonce in the future in a pending list for a while.
• support tx replacement with the same nonce?

[robert-zaremba]

The gist of it is, that accounts have nonce "lanes" or "buckets", and they can submit txs using a nonce from any one of these nonce buckets, e.g. [<0-1000>, <1001-2000>, ...], where each nonce must be monotonically increasing in it's respective bucket.

@ValarDragon , @alexanderbez , based on the example, if I understand correctly, you want to break nonce sequence into ranges.
I think a better idea is to model it with a sequence id:

type Nonce struct {
  SeqID  varint   // or uin32 or uint64?
  Nonce uint64  // could be varint as well
}

This way, we don't have weird rules on how a relayer should claim next range, or a situation when we have millions of ranges with only one claimed nonce (thus making big gaps).

It's obviously a breaking change, however, we can make a compatibility rule:

1. try to deserialize as a single number x
   1. if it succeeds -> nonce = Nonce{0, x} (current behavior)
   2. otherwise deserialize as Nonce
2. SeqID = 0 can be used only by direct signer.

[alexanderbez]

Not sure I understand your proposal. Also, there aren't any rules on lane usage. A relayer could simply perform round-robin on its accounts for example.

[robert-zaremba]

The idea is to change the type of nonce from uint64 to the struct described above.

[tac0turtle]

closed with the acceptance of #18553. Implementation will start today or tomorrow