TX mass constraint optimization

[danwt]

Come up with a scheme to avoid tx mass constraints while still achieving good throughput

[keruch]

Context

Based on the last research, we can fit no more than 9 multisig inputs with 8 signatures – multisig inputs are heavy.

We need to make sure big deposit flow doesn't stop the system. We might have many UTXOs in the escrow address as every deposit creates a new entry.

Therefore, we need to sweep the escrow UTXO set from time to time.

Solution

In theory, we need a separate sweeping tx creation and validation flows. In practice, sweeping is an edge case of the withdrawal but with no HL messages.

1. Get a batch of HL messages
2. Get all UTXOs from the escrow account
3. Create a sweeping PSKTs if necessary
4. Append withdrawal PSKT after sweeping TXs

Alternative

Alternative include using some subset of UTXO set that covers the desired withdrawal amount. However, we need to make sure that there is a subset that doesn't exceed the mass limit and does cover the withdrawal amount.

Threshold value

We don’t need to know the exact input number threshold since the can use the Generator feature from Kaspa.

TLDR, if the UTXO set exceeds the mass limit, the “relay” transaction is created to sweep the subset of the initial UTXO set. After, the process is repeated until all UTXOs are consumed.

Sweeping process

//! A1  Tx2 Tx3 Tx4 Tx5 Tx6     | stage 0 (relays to stage 1)
//!  |   |   |   |   |   |      |
//!  +---+   +---+   +---+      |
//!    |       |       |        |
//!   A2      Tx8     Tx9       | stage 1 (relays to stage 2)
//!    |       |       |        |
//!    +-------+-------+        |
//!            |                |
//!            A3               | stage 2 (final outbound transaction)

1. Provide the initial UTXO set
2. Take UTXOs until the tx reaches the mass limit
3. Once the limit is reached, create a sweeping transaction with one change output that accumulates all the chosen UTXOs
4. Repeat until there is one singe UTXO -> new anchor

The process could be done in parallel. However, we need to keep track of the anchor chain, so we can backtrace it in the future. We don't care about the other (non-anchor) UTXOs, they are swept in parallel.

The process above is implemented in the Generator, we just need to carefully wire it.

Note that we don't care about the maturity since the sweeping process creates the tree with one parent which will be used in the further withdrawal. Therefore, we only care about withdrawal maturity.

Affected components

Withdrawal validation

This check should be omitted. TODO: think about consequences!

No other changes required.

Confirmation validation

In the confirmation flow, we have an anchor cache, so we know exactly how to backtrack the transaction.

See what happens here if the payload is empty (in case of the sweeping tx)

hyperlane-monorepo/dymension/libs/kaspa/lib/validator/src/confirmation.rs

Lines 113 to 116 in fb6e511

	let message_ids =
	MessageIDs::from_tx_payload(&p).map_err(|e| ValidationError::PayloadParseError {
	reason: format!("Failed to parse message IDs: {}", e),
	})?;

No other changes required.

Relayer withdrawal

1. Wire the Generator
2. Create PSKT from sweeping TXs. See if PSKTGenerator or bundle_from_pskt_generator is useful.
3. While using the Generator, keep track of the anchor chain
4. Prepend sweeping PSTKs to the withdrawal Bundle
5. Prepend intermediate anchors in the cache

Anchor backtracking

TODO: think about consequences!

This might be tricky since the change makes the backtracking non-linear. Only one branch leads to the old anchor while others are just deposits.

In theory, we can distinguish sweeping TXs (all inputs and outputs have escrow script pub key).If the TX doesn't have any escrow UTXO in inputs, then it's a user-created TX, and we can give up this branch.

The other solution is to avoid parallel sweeping, but in this case we can't use the Generator.

//! A1  Tx2 Tx3 Tx4     | stage 0 (relays to stage 1)
//!  |   |   |   |      |
//!  +---+   |   |      |
//!    |     |   |      |
//!   A2     |   |      | stage 1 (relays to stage 2)
//!    |     |   |      |
//!    +-----+   |      |
//!       |      |      |
//!       A3     |      | stage 2 (relays to stage 3)
//!       |      |      |
//!       +------+      |
//!          |          |
//!          A4         | stage 3 (final outbound transaction)

DoS vectors

TODO!

Questions

1. How to pay the fee?

[danwt]

Nice!

---

Regarding

This check should be omitted. TODO: think about consequences!

I think its fine to remove, not sure why its there tbh

---

Regarding backtracking and fee paying

In theory, we can distinguish sweeping TXs (all inputs and outputs have escrow script pub key)

I think we still want relayer to pay

If the TX doesn't have any escrow UTXO in inputs, then it's a user-created TX, and we can give up this branch

Seems correct

---

[keruch]

Closed by #220