Incremental decommit

[ch1bo]

Why

Hydra Heads should not need to be closed to remove funds. This will make Hydra Heads more flexible in enables use cases where long-living Heads are beneficial.

Also, the current protocol may result in "non-finalizable" heads when some UTxO can't be represented on the Cardano mainchain. It would be desirable to recover at least compatible outputs back on L1.

What

Implement the protocol extension for de-committing only part of the Head state (without closing the Head) as already briefly described in the original Hydra Head paper.

"As user, I want to remove my funds from the head to make them available on the Cardano L1"

• When the head is open, a hydra client can request an incremental decommit using the Decommit websocket command or http request POST /decommit
  • The payload / request body is a "decommit transaction" Tx is just a list of transaction output references (aka. transaction inputs), in cardano-api: [TxIn]
  • A decommit tx is spending inputs from the confirmed UTxO in the head, but will produce UTxO which are to be decommitted into the L1
  • All head participants agree on the decommit tx by validating it against the L2 ledger state.
  • With this agreement, the hydra-node does create and submit a decrementTx onto the L1
• Submitting the decrementTx will make the requested outputs available on the Cardano L1
• A client output informs about the requested, approved and completed decommit

Properties

• Closing the head with a same snapshot as a previous decrement must not produce the UTxO again.
• Funds must be returned even if decrementTx was never submitted and the head gets closed instead.
• The head should be live while decommitting, i.e. process transactions of independent UTxOs.

Security

• The specification is updated and checked with researchers whether it is consistent with the properties above (walk-through)
• All validator changes are tested using the mutation testing framework, covering all constraints from the specification and we saw each test "fail for the right reason", i.e. no specification change without a corresponding mutation and (at least) one mutation per constraint

Out of scope

• Multiple decommits should be issuable irrespective whether they are "settled" yet or not. i.e. there can be times when no decommit is possible (yet)
• Incremental decommit when head is closed (= partial fanout)
• Validator changes are audited by the internal audit team at IO

How

Idea: Re-use the ReqSn and snapshots in off-chain consensus to request exclusion of UTxO. With that "granted", on-chain open state is updated in a new decrementTx. We need to make sure off-chain snapshots can only be used to close specific open heads (replay protection).

1. Head is open, $\eta_0$ locked, off-chain busy transacting
2. Client requests decommit by submitting a decommit transaction $\mathsf{tx_{dec}}$ which translates into a $ReqDec(\mathsf{tx_{dec}})$ network request
3. Each participant validates $\mathsf{tx_{dec}}$ against the confirmed ledger state $\bar{U}$ and if valid, stores outputs of $\mathsf{tx_{dec}}$ as $U_\omega$
4. Snapshot leader requests exclusion of UTxO $U_\omega$: $ReqSn(sn, txids, U_\omega)$ (TBD: only submit out-refs?)
5. All participants acknowledge $\bar{U}$ excludes $U_\omega$ by signing the corresponding snapshot's number, $\eta = \mathsf{Digest}(\bar{U})$ and $\eta_\omega = \mathsf{Digest}(U_\omega))$, where $\mathsf{Digest}$ is the same function we use today to create a "combine" of some UTxO set into a "digest" (see specification section 5.3)
6. decrementTx
   • evolves head state $(open, sn_i, \eta_i)$ by spending head output,
   • into head state $(open, sn_{i+1}, \eta_{i+1})$ + outputs equivalent to $U_\omega$
   • given a multi-signed $\xi$ of $\eta_i$, $\eta_{i+1}$, and $\eta_\omega$ as redeemer.
7. closeTx
   • evolves head state $(open, sn_i, \eta_i)$
   • into head state $(closed, sn_c, \eta_c, \eta_\omega^?)$,
   • given a multi-signed certificate "referring" $\eta_i$ of snapshotted $\eta_c$ (corresponding to a confirmed $\bar{U}$) and, if a decommit is in-flight the $\eta_\omega$, which must be present in the output head state
8. fanoutTx
   • ensures outputs correspond to both, $\eta_c$ and $\eta_{omega}$ (if present), in sequence

flowchart LR
  open0([open η0])

  open0 -- "Cert(η0,η1) + ηω" --> decrementTx
  decrementTx --> open1([open η0 η1])
  decrementTx --> decommit1([decommitted o1])
  decrementTx --> decommit2([decommitted o2])

  open1 -- "Cert(η1,ηc)"  --> closeTx
  closeTx --> closed1([closed ηc])

Loading

Possible tasks

• Create the happy path End-to-End scenario #1205
• Add /decommit endpoint #1209
• Incremental decommits off-chain #1223
  • Off-chain protocol changes to ReqDec and extend snapshots to hold optional $U_\omega^?$
  • Decrement transaction construction & observation
• On-chain script changes
  • Verify decrementTx as open -> open transition
  • Changes to verify closeTx with state references (additional data in redeemers?)
  • Changes to verify fanoutTx to handle new $\eta_\omega^?$
• Test combinations of decrement/close/fanout #1390
• Schedule and have a spec walk-through with researchers

Latest task breakdown

• Update the specification with the design #1473
• Decommit and close with same snapshot #1474
• Close incremental decommit spec/impl gaps #1483
• (optional) Ask @abailly whether he can review the specification, implementation or both

To be discussed

• How can any participant request removal if not snapshot leader?
  • Add a new message $ReqDec(U_\omega)$ to request a decrement in the next snapshot (even the snapshot leader, like ReqTx)
• What happens if the incremental decommit is requested and acknowledged on the L2, but the decrementTx is never submitted to L1?
  • The removed UTxO $U_\omega$ must remain part of the off-chain state and is used to fanout the full state, i.e. the closed state $\eta ~ \widehat{=} ~ \bar{U} \cup U_\omega$. For example, assuming the decrementTx above never happens, $\eta_0$ must correspond to $\bar{U} \cup U_\omega$ and fanoutTx produce all corresponding outputs
  • SMT proofs where only some UTxO are realized would make this more flexible.
  • (S)MT could allow verify $\eta \cup \eta_\omega$ in closeTx and lead to a normal closed state with a single $\eta$
  • Any participant can post the decrementTx to avoid stalling.
• What if the agreed to remove state is not "fitting" into a single decrementTx?
  • Only agree "small enough" decrements off-chain (maybe complicated, but should be possible), or
  • Split off decremented state from $\eta$ and allow one or more withdrawTx (= partial fanout)?
  • This can be seen as an orthogonal issue very related to the purpose of Support larger # of UTXO via split-fanout #190
• Do we need a "fancy" state reference as outlined by @mfitzi or are snapshot numbers enough?
  • Not for incremental decrement alone. Because decrements on-chain never impact off-chain availability of UTxOs. Also, rollbacks would only affect semantics if participants agree "too early" (upon seeing a decrementTx) to clean-up the corresponding $U_\omega$ from the off-chain state.
  • The state reference is the same meachanism as explained in Sign snapshots including the initial UTxO set #688, but generalized for multiple open states. A state reference is basically just the $\eta$ of the previous open state and needs to be used to decide on whether an off-chain snapshot is valid against the current state or the previous state. Detailed case separation TBD here (available as draft slides).
• Why are SMT roots and non-inclusion proofs needed on the decrementTx instead of just multi-signing $\bar{U}$ and $U_\omega$?
  • They not needed and we can stick with the hand-rolled concat + hash approach, iff we extend the closed state with the "to-be-decommitted" $\eta_\omega$ derived from $U_\omega$ next to the normal $eta$ and the fanoutTx needs to recreate outputs satisfying both $\eta$ and $\eta_omega$ (related to point 2)
• Is having [TxIn] on the endpoints convenient?
  • If not, change it to UTxO
  • Change it to Tx as we need to authorize a decommit (see comments)
• Shall we add decrements (partial fanout) from a closed head?
  • Out of scope (see What)

[ch1bo]

Drawn a transaction trace with the current design using our old-school notation:

[ch1bo]

Discussed the approach with researchers and here are today's notes also reflected in the TBD section above, while the main body of the issues requires some updating now:

Notes on decrements <2023-11-16 Thu>

• We need the state reference also in decrement (rollback protection similar to η0)
  • state-ref = pid + η
  • consequence: to validate a close (that is allowed on the "previous open state") we need to carry the previous η in every open state (simliar like the η0 idea)
• Can there be many decommits?
  • Sequential processing easier
  • Each participant can post the decrement transaction!
  • Δη could be also a collected MT root of all decrements requested / pending -> that would complicate on-chain proofs
• What to fanout when closed with a Δη
  • Careful: depends which state was referenced -> close decides
  • Be able to check on chain that η u Δη !!
  • Or track two etas in close and fanout needs to realize both
• Increment commits specified as TxIn
  • simple on-chain check, but enough!
  • could make off-chain complicated (need to lookup before signing)

[ch1bo]

We had a discussion today which led to the question:

How are decommits authenticated? How can we prevent "someone" to decommit funds of "someone" else?

Many use cases will mean a denial of service if any participant (or users "in proxy") can request decommitting arbitrary UTxO.

A simple example would be two actors Alice and Bob have both have a single UTxO in a head to do fast & cheap transactions to each other. Then Alice could request to decommit Bobs UTxO which will make him not able to send anything anymore.

Maybe this is a bit constructed, but certainly most use cases would be impacted by such an "attack" vector.

How is this different than close of a head?

Closing a head does "level the playing field" more as everyone is impacted the same.

---

For this feature to be useful, this needs to be handled and we should update the What requirements of this feature item!

Ideas we had to avoid/solve this:

• Require witnesses for spending the UTxO and validate them in a ledger
• Instead of requesting a UTxO to be decommitted, model that as a "special" Tx which needs to be applicable, but does not update the layer 2 ledger state

[GeorgeFlerovsky]

The person attempting to decommit must own the utxos in the hydra ledger.

In the hydrozoa paper, my approach was to include in the decommit request a transaction with no outputs and inputs consisting of the utxos to be decommitted. This transaction is invalid on L1 (which prevents it from being submitted there — an added benefit) but can be interpreted by a special ledger rule that disables the tx balancing check when handling decommit requests. Since the other ledger rules are still active, this means that:

• Pubkey utxos can be decommitted only via tx signature from the pubkey.
• Script utxos can be decommitted only by satisfying the scripts' validators' decommit redeemer.

Indeed, the above transaction precisely describes what should happen to the L2 ledger when the utxos are decommitted. On L1, such transactions are illegal because it must conserve tokens (modulo mint/burn); on L2, such transactions are necessary because utxos can enter/leave the system exogenously.

https://github.com/GeorgeFlerovsky/cardano-hydrozoa#decommit-on-l2

[ch1bo]

Latest update of example transaction traces using signatures including $\eta_\omega$ (see #199 (comment) for more details)

Nominal decrement

Alternative: Close with U3 instead of decrement

Alternative: Close with U3 after decrement