Support larger # of UTXO via split-fanout

[ch1bo]

What & Why

The first naiive, but correct implementation (see #145) of the Hydra Head plutus script validators is limiting to the number of UTXOs supported in a Hydra Head.

This is because we need to make sure all the UTXOs can be distributed back in the single, complete fanout transaction and we are bound by Plutus script execution budgets.

In order to close a head containing a large number of UTXO which do not fit in a single transaction, the fanout step needs to be done in two steps where the UTXO is first split into smaller subsets which will be independently fanned out.

Functional Requirements

• It is possible to organize the UTXO in a hierarchical manner allowing for deterministic splits of known sizes.
• It is possible to verify independently, on-chain, that each subset is indeed included in the original set.
• The proof of inclusion must be small in front of the UTXO subset.

Technical details

The functional requirements can be met by organizing the UTXO into a modified merkle-tree where each leaf is a transaction output and each node also contains the total size (in bytes) of the children.

And recent experiments #161 showed that this is feasible to be used.

[ch1bo]

Changed to 🟡 because we this is quite complex in terms of plutus contracts. We are quite sure we have everything we need, but it's not clear whether it "fits" and the changes are likely also quite involved.

[ch1bo]

Having #370 makes this not pressing as we will not have unclosable Heads. Also, we have ideas in how to improve fanout performance (not decoding TxOut in the script context). Let's revisit this if it is brought up by users.

[ch1bo]

Unfortunately we have identified a theoretical case which could require this. #370 would only come into effect after opening the head. But it's possible that a collect transaction can open a head which would not fit into a fanout.

[ch1bo]

Instead of "only" organizing UTxO in a "hierarchical manner allowing for deterministic splits of known sizes", we aim of full flexibility of what to realize on the L1 with #1468.

In case that approach is too expensive or otherwise unrealistic, we might want to revisit this item.