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

[ch1bo]

Notes from @mchakravarty on incremental commits and more general configuration changes (from back in the days):

Hydra Head with Incremental Commits

Requirements
Head state snapshot

• UTxO set
• Hash of multisig verification key (serves as a commitment to the current set of participants)
• Sequence number (0 at initial head state; incremented with every configuration change)

Configuration change transactions

• Configuration changes are the addition and removal of new participants as well as the committing and decommitting of funds.
• Configuration changes are always cooperative, involving all existing participants
  • A configuration change transaction for the mainchain state machine needs to be signed by all existing participants.
  • That is, there are now two types of transactions that get multi-signed in the off-chain substrate: (1) state channel transactions and (2) configuration transactions. The former transition the off-chain UTxO set and the latter are submitted to the mainchain.
  • Like state change transactions, configuration transactions are sent by one participant p to all other participants for signing. Once fully signed, the configuration change is included into the head state snapshot and p submits the transaction to the mainchain, advancing the mainchain contract.
• There are four types of configuration changes
  • Adding a participant
  • Removing a participant
  • Committing UTxOs to layer 2
  • Decommitting UTxOs from layer 2
• A configuration change affects the off-chain protocol as soon as it is included in the current head state snapshot
• Each configuration change transaction includes the head state snapshot after application of the configuration change
• The collectCom transaction turns into configuration change 0. (But do we want it signed by everybody?)

Adding and removing participants

• The change transaction contains the new multisig verification key.

Committing and decommitting UTxOs

• The change transaction contains (a commitment to) the new off-chain UTxO set.

Synchronisation

• Which configuration to use for a transaction in the off-chain is determined by the snapshot that this transaction is supposed to build on.
• When a configuration change transaction has just been submitted or is not final on the blockchain, it may still be rolled back. In can, however, also be rolled forward again, unless all participants have also signed a competing transaction extending the mainchain or somebody decommits.
• This raises the question of whether we need a means to contest a decommit with a configuration change. After all, the configuration change has been signed by all current participants, so it ought to be binding.

Multisigs

• The signer set changes with adding and removing participants. What are the implications for the multisig scheme out of that?
• Whenever the set of participants changes, the joint verification needs to be recomputed (for the new set) and needs to be committed to the mainchain contract (as part of the corresponding configuration change transaction).

[ch1bo]

Besides the basic mermaid diagram above, here is another drawing of the potential life-cycle with incremental commits/decommits from our Miro board:

Transaction traces - Incremental commits_decommits-1.pdf

[ch1bo]

Grooming discussion:

• Separate increment and decrement parts (it's two user stories)
• Same dependencies / impacts, but tackling one of the them will provide insights to the other
• We worked on the increment part and realized we need a two-step process to avoid the problem of a commit not "being picked up". This follows the design of @mchakravarty (above) and @GeorgeFlerovsky (Hydrozoa).

Next steps:

• separate it into two items: Incremental decommit #1057
• continue work on the details

[ch1bo]

We continued work on this after also starting #1057. We had implemented the off-chain workflow to the point of this diagram shows:

sequenceDiagram
    Alice->>+API: POST /commit (UTxO)
    API->>HeadLogic: Commit UTxO

    par broadcast
        HeadLogic->>HeadLogic: ReqInc incUTxO
    and
        HeadLogic->>Node B: ReqInc incUTxO
    end

    HeadLogic -->> Alice: WS CommitRequested

    par Alice isLeader
        HeadLogic->>HeadLogic: ReqSn incUTxO
    and
        HeadLogic->>Node B: ReqSn incUTxO
    end
    
    Note over HeadLogic,Chain: PROBLEM: Need to verify incUTxO on L1 as we authorize the TxIns to use (because of on-chain scripts).

    HeadLogic->>HeadLogic: sig = sign snapshot incl. inputs(incUTxO)

    par broadcast
        HeadLogic->>HeadLogic: AckSn sig
    and
        HeadLogic->>Node B: AckSn sig
    end

    Node B->>HeadLogic: AckSn sig

    HeadLogic -->> Alice: WS SnapshotConfirmed
    HeadLogic -->> Alice: WS CommitApproved

    HeadLogic -->> API: SnapshotConfirmed
    API->>API: draftIncrementTx vk snapshot sig >>= finalizeTx >>= signTx sk

    API-->>-Alice: IncrementTx
    Alice->>Alice: sign IncrementTx
    Alice->>Chain: submit IncrementTx
    
    Chain->>HeadLogic: OnIncrementTx
    HeadLogic-->>Alice: CommitFinalized

Loading

However, when working on the specification and trying to realize the recommendation of researchers, we hit the problem as indicated in the picture. Namely, that in one of the designs the assumption was made that Hydra participants would sign off on the transaction output references (TxOutRef) of the to-be-committed UTxO. While this would make the on-chain part fairly simply - we only need to show the out refs in the redeemer and on-chain reproduce the signed data by serializing a list of [TxOutRef], it makes the overall protocol very interactive and would require a new interaction between the protocol logic in the hydra-node and the L1 chain (query the output references before signing).

We need to discuss this and the alternative of using a Merkle-Tree based $\eta$-construction with researchers.
We now switch focus on the off-chain part on this item (as to the user, any variant would be identical) and the on-chain part of #1057 (which works on the "naiive"-$\eta$ the same as for the MT-based one) for the short term.

[ch1bo]

@GeorgeFlerovsky When typing out the specification for the on-chain checks to be done on deposit (here) I see now more clearly what you meant:

There is no actual need for on-chain checks of what a valid deposit is (what I would have encoded in the minting policy). Anyone paying to the deposit validator (off-chain code) should ensure that what they put is a valid datum having a deadline and if a script wants to ensure continuity of its datum, it would need to green light any deposit transaction anyways.

While the interface between downstream scripts and the deposit protocol would become slightly more involved, it comes at the benefit of greatly simplifying the protocol transactions. But..

How would you describe this interface?

I was thinking something similar to the commit transaction's description: https://hydra.family/head-protocol/unstable/assets/files/hydra-spec-09c867d2d94685906cbc7a74873f9de5.pdf#subsection.5.2 but we would need to describe decoding of the recorded outputs in $C$ and check consistency with locked value off-chain?

[GeorgeFlerovsky]

@ch1bo TBH, I haven't thought too much about that interface yet.

In a hand-wavy sense, we can adapt components from what you've previously been doing for users — serializing utxos, deserializing their datum representation, comparing redeemers to hashes, etc.

We're just pushing some of those onchain/offchain mechanisms outside the hydra protocol. The onchain parts become opt-in for scripts, while pubkey users rely on the offchain checks.