To limit maximum number of native token IDs in the output

[lunfardo314]

Introduction

Currently Stardust protocol puts cap on maximum different token IDs in the transaction. The number is quite big, something like 256.
Number of different native token ID in one output is unlimited, it can be all 256 in one output.
This limit is not enough to prevent certain attacks and complexities for development.

The problem

It is probably fine to keep many token IDs in an one time transaction. However keeping all of them in the wallet UTXOs is unreasonable. If wallet would keep it all in one UTXO, it will have to spend the whole output when moving even one token. This can result in much bigger transaction.
Therefore, reasonable strategy for the wallet developer is to split tokens into many UTXOs, for example one UTXO for 1 native token ID.

That is the strategy of the Stardust VM (a distributed wallet). It uses one output for native token ID to keep the total on the chain. Any other options are significantly more complicated to implement and costs more dust deposit.
This leads to the following problem:

If sender sends >125 tokens in the output, the Stardust VM won't be able to process it because if split, it will exceed maximum number of UTXOs in the transaction. The only option is to ignore the output. This funds will essentially be lost.
The same will happen with any wallet which splits multi-token outputs to separate UTXOs.

Ignoring the big multi-token output also creates and attack vector, because the output will remain in the backlog forever and It will keep coming again and again.

Solution

To introduce limit or maximum number of token IDs in the output. This will prevent this kind of attack.
The reasonable limit is maximum 4 different native token IDs in one output.

Pros

• prevents limit exceeding attacks on L2 apps
• simple to implement
• no overhead
• maximum can be increased later as a non-breaking change with 100% backward compatibility
• alternatively, introducing limit later would be a breaking change

Cons

• would prevent theoretical and exotic use-cases which needs 5 and more token IDs in one output. This always can be mitigated by splitting the whole batch into several UTXOs in the same transaction

[Wollac]

Definitions

• Max Output Count: Maximum number of outputs in a transaction
• Max Input Count: Maximum number of inputs in a transaction
• Max Output Token Count: Maximum number of (distinct) native tokens in each output (and thus input)
• Max Tx Distinct Native Token Count: Maximum number of distinct native tokens in each transaction

Rational behind current parameter values

• Max Input Count is a critical parameter as it limits the number of signatures to verify per transaction and must not be too large
• The balance computations are much more lightweight than signature checks, but still we have:
  • Computational complexity of O( (Max Output Count + Max Input Count) * Max Output Token Count )
  • Memory complexity of O( Max Tx Distinct Native Token Count )
• By setting Max Tx Distinct Native Token Count = 256 and Max Input Count = Max Output Count = 128, we bound the computation complexity by 65536 operations and the memory complexity to 256 stored values

Considerations:

• I agree with the OP, that It seems reasonable to assure that:
  Max Output Token Count <= Max Output Count
  This assures that it is always possible to split an output into single-token outputs
• The current limit of 65536 uint256 operations still seems expensive?
• Limiting Max Tx Distinct Native Token Count is an elegant way to also bound the computation and memory complexity with one parameter. This property should be kept in order to keep the number of parameters low.
• Allowing a single output with many different native tokens, helps to compress the ledger, i.e. less dust deposit fees need to be paid in order to store multiple tokens.
• Having at most one native token per output simplifies the L1 specification and implementation.

Proposal

I see mainly two viable options here:

1. Set Max Output Token Count= 1 and remove Max Tx Distinct Native Token Count (will be implicitly Max Output Count)
2. Set Max Output Count = Max Tx Distinct Native Token Count = 128. This limits the balance computations to 32768.

Any other option “in between” these two seems too arbitrary to me.

[WernerderChamp]

I think that the option to compress the ledger is probably one of the most important here, that's why option 1 is pretty much out of the game. A lot of wallets will have >5 tokens and this just adds dust deposit. A dry extended output has a size of 716 v_byte in muxxers initial dust protection RFC (With the unlock condition changes this is probably slightly off by now). Adding a native tokens adds just 70 bytes.

At 127 native tokens (we only allow 127 inputs not 128) we would be at 10876 v_byte, which is a little over the size of 15 dry outputs. 127 therefore seems viable in my eyes, unless there aren't any further constraints.

[lunfardo314]

Max Output Token Count = 1 still seems quite arbitrary to me :)
I don't think there are "natural" bounds. The key point is to to make live easier for the L2 apps. What is very easy on L1 (e.g. not allowing more than 4 token IDs in the output), it becomes very complicated on L2 due to edge conditions. Requirement to mind outputs with many IDs (close to transaction output maximum) leads to uresolvable/attackable edge conditions which do not rule out lose of user's funds