Partial fanout

[ch1bo]

Why

The current naiive, but correct implementation (see #145) of representing L2 UTxO in the Head validators is limiting the number of UTXOs supported in a Hydra Head (currently about 80 ada-only outputs, see benchmarks)

This is an all-or-nothing approach and the fanout can only succeed if all UTxOs are produced in a single transaction. This means, there is no way to finalize a head which exceeds these limits!

Within this feature, we want to overcome this limitation by enabling individual (subsets of) outputs to be realized onto the main chain after the contestation deadline passed.

This is similar to #190, but allows for individual UTxOs to be realized and hence can even work around situations where some parts of the state are not compatible with the L1 (e.g. min UTxO value not met)

What

• The hydra-node when asked to Fanout a head can fanout any size of UTxO set with one or more (partial) fanout transactions

• Out of scope: asking hydra-node deliberatly picking a subset of UTxO to fanout.

• Head protocol fanout transactions allow arbitrary subset of closed UTxO to be realized onto the main chain.

  • As before is only possible after the contestation deadline passed.
  • There is a maximum of outputs producible by a single fanout transaction.
  • Any number of fanout transactions can be sequenced in the protocol (as long as there are outputs left to fanout).

• Maintain offchain performance in the same order of magnitude

How

Idea: We update the digest mechanism used in collect, (increment/decrement) and close transactions in such a way to allow for exclusion proofs in fanout transactions.

Using BLS accumulators as researched and experimented by @perturbing in https://github.com/perturbing/plutus-accumulator and https://hackmd.io/@CjIlIbTxRqWOCpWzxuWmkQ/BybaUlSN0

Possible tasks:

• Benchmark off-chain proving time for BLS accumulators on an UTxO set #1666
• Change existing validators (same txs) and digests for snapshots and check impact on performance (collect, abort and fanout) #1667
• Update the specification with BLS accumulator introduction + use it in on-/off-chain sections

• Write a (pending) test that covers finalizing "big heads"
  • Ideally from "very outside", e.g. ModelSpec where the test just says Close and Fanout

• Change fanout off-chain code to be partially

TBD: Off-chain performance is still to be benchmarked and might impact snapshot signing performance on the L2

[ch1bo]

@colll78 is this related to how you aim to do things in Midgard?

[colll78]

@colll78 is this related to how you aim to do things in Midgard?

I reached out to Thomas a few weeks ago to discuss the potential of using the BLS accumulator for the Midgard inbox / outbox contracts.

To have an optimistic rollup truly inherit L1 security, you need to have a mechanism through which users can transact on the L2 directly via L1 transactions (as opposed to submitting the tx to the L2 validator network). To achieve this, you have an inbox contract that users can send transactions to on the L1, and any state commitments (containing batches of incoming blocks from the L2) must include the transactions in the inbox in their commitment (emptying the inbox in the process). The state commitment is invalidated if it does not contain all the pending transactions from the inbox. Currently, the inbox stores these pending txs in a sparse merkle tree and the process of guaranteeing inclusion involves providing a one-by-one proof of inclusion of each inbox transaction in the incoming state commitment (which updates each inbox entry to prevent re-use of the same membership proof). The BLS accumulator can likely be used here to vastly speed up this process with the batched membership proofs. Current focus is on implementing fraud proof validators so this is on the backburner for now.

[ch1bo]

@perturbing created the optimized rust accumulator and already demonstrated using it from haskell here

[perturbing]

A small update, for prover times (on my beefy machine), for sets of the following sizes, proof creation over G2 takes roughly

set size      1_000: 11.04 ms +- 202.9 μs
set size     10_000: 77.61 ms +- 1.463 ms
set size    100_000: 683.5 ms +- 6.646 ms
set size  1_000_000: 7.288 s  +- 56.36 ms
set size 10_000_000: 94.38 s  +- 1.420 s

To run such a test yourself for different sizes, change the 1_000 to the set size you want here and use nix run .#bindings-test to compile :)

PS: there is a known issue in linking the rust -> C -> haskell code on mac (I do not own a mac, so could not reproduce it yet).

[noonio]

Note: hydra-doom requires around 2-3 ms creation time for snapshots; (below 10 UTxOs); what do the benchmarks looks like in that domain?

[perturbing]

@noonio

It depends on the machine ofc, but on my beefy laptop

benchmarking proof calculations/snapshot time
time                 457.0 μs   (454.3 μs .. 460.0 μs)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 457.0 μs   (455.5 μs .. 458.6 μs)
std dev              5.233 μs   (4.304 μs .. 6.610 μs)

So, that sounds doable, though this an isolated measurment of only the core functionality.