Incremental commit

[ch1bo]

Why

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

Furthermore, it could pave the way for getting rid of the initialization phase altogether, which would result in a much simpler protocol.

What

Implement the protocol extension for more committing additional UTXOs into a Head as already briefly described in the original Hydra Head paper.

"As user, I want to add more funds to the head, such that I can spend them later in the head"

• When the head is open, a hydra client can request an incremental commit:

  • Requesting can be done via HTTP using the POST /commit. Just like with the "normal" commit, the user needs to send either a UTxO or a "blueprint transaction".
  • The api call is synchronous and returns a depositTx corresponding to the requested commit. (This works just the same way as the commit endpoint works so far during initialization phase)
  • Alternatively, or in addition, we provide a library to build such depositTx

• Submitting the depositTx transaction should have the requested UTxO eventually added to the head

  • A CommitRequested (TBD: or DepositDetected?) server output is sent to signal observation of the deposit
  • The hydra-node will request inclusion of the deposited UTxO and wait for a SnapshotConfirmed with inclusion approval.
  • Using the snapshot, the creates an incrementTx, signs and submits that.
  • A CommitFinalized server output is sent to the clients when the incrementTx is observed.

• The node provides a list of pending commits via the API using GET /commits

• Each pending commit (deposit) has an id (i.e. the deposit outputs' TxIn) and a deadline attached, after which a user can request refund of the commit

  • Requesting can be done via HTTP using DELETE /commits/<id>, which has the node construct and submit a recoverTx for the user. TBD: okay that node pay fees here?
  • Alternatively, or in addition, we provide a library to build such a recoverTx

• Any UTxO which can be committed, can also be incrementally committed

Scenarios

All of the positive scenarios also ensure correct balance after fanout:

• Can commit to an open Head
  • not matter what is currently available on L2 (also empty head)
• Can commit and immediately close with the same snapshot
• Can do multiple increments one after another
• Can do multiple commits and decommits in sequence as long as decommitted UTxO are consistent
• Can commit and decommit the same UTxO should result in the same open Head UTxO
• Cannot commit while another decommit is pending
• Cannot decommit funds you don't own
• Cannot commit funds you don't own
• Can decommit everything from the Head
• Can process L2 transactions of independent UTxO while commit is happening.
• Cannot commit same UTxO in two Heads
  • specially in presence of rollbacks (due to network partition)
• Can close and fanout while commit is pending
  • i.e. when someone did not submit incrementTx
  • either funds did not get committed at all or reimbursed by fanout

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

• Changes to the initialization of the head, see Directly open heads #1329
• Multiple concurrent commits, i.e. there can be times when no commit is possible (yet)
• Validator changes are audited by the internal audit team
• Committed UTXO's are only made available in L2 if the probability of rollback is reasonably low (TODO: create orthogonal issue about rollbacks)
  • This will be a known limitation

How

• Incremental commit specification & scenarios #1484
• Specify deposit workflow in ticket and technical specification #1571
• Implement deposit validators and off-chain code #1574
• Implement off-chain user journey of incremental commits #1522
• On-chain verification of increment and tests to cover all scenarios #1664
• Add incremental commits to the TUI #1737
• Open a head between Hydra core members and test out the new functionality #1738
• Add hydra-node option to specify a deposit deadline #1797
• Revisit the spec and unmark red changes Incremental commits spec changes hydra-formal-specification#12
• Make sure to update hydra-node master with new spec input hash #1802

Protocol design

Important

Idea: Deposit anything to commit into a deposit output. Head participants then re-use the ReqSn off-chain consensus to request inclusion of UTxO (like incremental decommit). Deposits have an asymmetric deadline, such that users need to wait longer before they can reclaim than the head participants have time to ensure the deposit is not rolled back (double spent). Deposits are recording outputs like in the commitTx and claiming a deposit into the head via an incrementTx ensures the recorded UTxO matches (completely) with what was agreed off-chain. Participants only agree off-chain if they saw a matching deposit.

Outline of one deposit being claimed in an increment and one deposit being recovered:

flowchart LR
  seed([seed])--> initTx
  initTx --> open0([open v0 η0])

  u1([u1]) --> depositTx1 --> deposit1(["deposit DL [u1]"])
  u2([u2]) --> depositTx2 --> deposit2(["deposit DL [u2]"])

  open0 -- Increment ξ3 --> incrementTx
  deposit1 -- Claim --> incrementTx
  incrementTx --> open1([open v1 η3])

  open1 -- Close ξ1 --> closeTx

  deposit2 -- Recover --> recoverTx --> u3([u2])

Loading

Protocol transitions:

• Situation: Head is open, $U_0$ locked, off-chain busy transacting

• Deposit:

  1. Anyone can create a deposit by posting a depositTx
     • we can enable this through hydra-node or through a library/tool.
  2. The depositTx ensures through minting of a deposit token (DT) that anything to be committed $\phi$ is recorded correctly into the datum (isomorphic to $U_\alpha$)
     • this also ensures contract continuity for next steps
     • TBD: Needed? pub key outputs need signature anyways and script outputs could inspect depositTx to ensure the transition to L2 is "correct"? Could mean more coupling, but simpler protocol here.
  3. All deposit outputs have the same address and the datum also contains target headid $\mathsf{cid}$ and a deadline $T_{DL}$
     • TBD: on commits users asked to identify heads not only by id but by participant keys, we could put them into the datum here and ensure only heads with those PTs can claim a deposit?

• Recover:

  1. In case deposit was not picked up by a head, anyone can "undo" a commit using a recoverTx after the deadline has passed
     • most of the time, this is going to be the original user who wanted to deposit
  2. Deadline should be long enough such that the head has enough time to wait for the deposit "to settle" and still absorb it into the head (synchrony assumption on Cardano).

• Increment:

  1. One or more Head participants (i.e. their hydra-node) observe pending deposits using the common deposit address
     • this should only happen after gaining enough confidence that the accompanying depositTx is not rolled back
     • need to check head id and deadline (should be configurable)
  2. A node requests inclusion of a pending decommit by sending a ReqSn message with $U_\alpha$
     • Not needed as every participant would observe it on-chain and its up to the snapshot leader to include it anyways
  3. The snapshot leader will request inclusion: $ReqSn(v, sn, txids, U_\alpha)$
     • Note that this submits a utxo set, not a transaction
  4. All participants acknowledge by signing this snapshot $\eta = \mathsf{combine}(\bar{U})$ and $\eta_\alpha = \mathsf{combine}(U_\alpha))$
  5. This yields a multi-signed certificate $\xi$ which can be used to post the incrementTx, which:
     • spends a deposit output, where the deposit validator ensures
       • recorded commits match $\eta_\alpha$
       • head id from datum matches (using the head state thread token)
       • deadline has not passed
     • evolves on-chain head state $(open, v, \eta)$ into updated head state $(open, v+1, \eta')$,
       • given a multi-signed certificate $\xi$ and snapshot number,
       • by verifying the signature using snapshot number, version and $\eta'$ from the head output, as well as $\eta_\alpha$ from the deposit output
  6. Head participants observe incrementTx on L1 with added $U_\alpha$ and make it available in their L2 state
     • no delay because rollbacks are impossible here -> deposit can only be spent into the head before the deadline

To be discussed

• What happens if incrementTx is not posted after being signed on L2?

  • Any node can submit this transaction; similar situation as fanout for example

• Do we really need to change η to be a merkle-tree-like structure with inclusion proofs?

  • Checking the value on L1 + signature on L2 would be enough, but this requires interaction with L1 when signing on L2
  • By using deposit, we can observe correct locking before requesting inclusion and our basic digest is good enough to check all-or-nothing on any individual deposit UTxO.

• Shall we drop the initialization phase?

  • Maybe as a follow-up; Not in scope

• How to deal with rollbacks/forward which result in a different $\eta$? When is it safe to integrate $U_\alpha$ into confirmed $U$?

  • Deadline after which a user can submit recoverTx should be >> than a safe margin on observing depositTx (e.g. deadline = 7 days, delay on deposit observe ~ 1 day); As deposits can only be spent into the head before the deadline passed, we don't need to wait when observing incrementTx
    • IMPORTANT should require a safe margin before the deadline in incrementTx (re-use contestation period?)

[ch1bo]

In a discussion I had with @mchakravarty we touched on the fact that it would also be possible to directly open a head in a single transaction and do all commits incrementally after. That might lead to congestion on the state output (it's like sequential commits), but simplifies some other use cases?

[ch1bo]

Incremental decommits may be very interesting to oracle use cases, where the resulting data is getting decomitted upon consumption.

[Yasuke]

The use case of Incremental De/Commit really adds so much added value to many of the Use Cases that Hydra seeks solve for end-users.

From an end-users perspective, with all of the potential Heads that will be running, they will be locking funds in various places. A stake pool is well understood way of locking in funds, but with Heads, and the varied use cases, they may be more hesitant or unable (because they have commit to previous heads), to participate.

By having Incremental De/Commit users are free to allocate their funds as necessary with their goals, and feel more confident with the developers integrating features utilizing Hydra Heads.

So I see this as a very important feature for optics to the greater cardano community, and Hydra Pay would definitely be able to make good use of it.

[v0d1ch]

@Sbcdn mentioned they would love to have this feature as well for their use case so +1

[ch1bo]

We discussed incremental commits/decommits (aka increments/decrements) today with the original authors of the Hydra Head paper:

• Basically this is about adding two more transactions increment and decrement to the L1 protocol

• Decrement requires certificate and all participants need to agree on taking
  something out of the head state

• Sandro: This is a rough sketch/doesn't include anything related to L2
  code

• We can start from the paper and build intuition further using knowledge from
  research team (pick their brain not do any additional work)

• Multiple ideas to go about the increment step (original paper was not clear how $\eta$ turns into $\eta'$)

  1. we assumed we would use and require Merkle-Patricia-Trees (MPTs) for that
  2. could also use the L2 to gather a certificate for incrementing $\eta$ by some UTxO, similar to decrement step

• Discussion pros and cons of these two approaches

  • What does this mean - request saying some participant is adding utxos?

  • Matthias: We would extend snapshots to include new information.

  • Currently, utxos are combined and hashed together for the on-chain code

  • Why MPT's? We need it in order for validator to be able to check that new state includes new utxos. We don't want to store utxo's on-chain. Could utilize inclusion proofs for the on-chain code.

  • Why would we want to use the L2 for incrementing the UTxO as well? Wouldn't everyone always agree?

    • It is likely cheaper / less work on L1
    • Requires more off-chain coordination (usual trade-off)

  • For L2 signing: we would need to sign the $\eta$, the $\eta'$ (of the latest snapshot which we expand) as well as the UTxO added/removed

    • to avoid commits you want to include may not exist anymore
    • to ensure sequencing of multiple increments

  • Isn't this interleaving state updates on the L2 with adding/removing funds from the L1?

    • Can't we do better than this combine everything approach?
    • After all, UTxO guarantee that only present outputs can be spent

• Conclusion:

  • MPT may not strictly be required for this
  • Sandro: We should think more and not try to implement this initial brainstorm
  • Need to analyze interactions between L1/L2 to design a solution here

[pgrange]

Some use cases that we believe could benefit from this:

• open public auctions: people should be able to join and leave the auction fluently
• DEX: similar to auction
• payment channels: add/retrieve funds dynamically