cardano-scaling / hydra

Implementation of the Hydra Head protocol
https://hydra.family/head-protocol/
Apache License 2.0
284 stars 86 forks source link

Incremental commit #199

Open ch1bo opened 2 years ago

ch1bo commented 2 years ago

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"

Scenarios

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

Security

Out of scope

How

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])

Protocol transitions:

To be discussed

ch1bo commented 2 years ago

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 commented 2 years ago

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

Yasuke commented 2 years ago

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 commented 2 years ago

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

ch1bo commented 1 year ago

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

pgrange commented 1 year ago

Some use cases that we believe could benefit from this:

ch1bo commented 1 year ago

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

Configuration change transactions

Adding and removing participants

Committing and decommitting UTxOs

Synchronisation

Multisigs

ch1bo commented 1 year ago

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 commented 1 year ago

Grooming discussion:

Next steps:

ch1bo commented 8 months ago

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

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 commented 8 months ago

We should also revise the API for requesting a commit. Having a mere UTxOWithWitnesses is not enough as indicated by this feature request: https://github.com/input-output-hk/hydra/discussions/1337

ch1bo commented 8 months ago

Notes from a discussion yesterday:

ch1bo commented 8 months ago

Introduction

I have revisited the incremental commit (and also decommit) over the weekend from a "transaction trace" stand point, where I wrote out the individual paths taken on the on-chain state machine and identify what information is required in which transition (= transaction / validator). First, let me include the two hand-written graphs created, describe what is shown and followed by a discussion:

hydra.pdf

Description

All arrows are transition between states, which also corresponds to transactions. Nodes in between are states represented by a sum-type datum (Upper case name, e.g. Open or Closed), while labels of transitions are individual constructors of a sum-type redeemer (lower case, e.g. close).

Both diagrams start in the $(Open, 0, \eta_0, \bot)$ state. The scenarios A and B match the basic protocol for closing with the initial snapshot $\eta_0$ or a multi-signed snapshot $\xi_2$ about some UTxO $U_2$. Scenario C is when we get off-chain approval for increment/decrement, but we instead choose to close the head instead using that same snapshot $\xi3$. The alternative is nominally a increment/decrement transaction where UTxO is added $U\alpha$ or removed $U_\omega$ yielding a new Open state, before it is closed with either the same snapshot as it was incremented/decremented (scenario D) or later closed with any other multi-signed snapshot $\xi_5$ (nominal case E). Not shown is that $\xi5$ could still be a snapshot which has $U\alpha$ or $U_\omega$ pending.

Due to space issues, the individual components of the state variables are not labeled, but it turns out that the $Open$ state holds: a snapshot number, a current head state digest and a previous head state digest ($\bot$ in the first open state - could also be $\eta0$ in the beginning). The $Closed$ state is depicted with the same, plus an optional additional digest of to be committed UTxO to fan out ($\bot$ or $\eta\alpha$) and an optional additional digest of to be decommitted UTxO to fanout ($\bot$ or $\eta_\omega$). TBD: Can we merge them?

Discussion

The approach seems to work out in a very similar fashion as these slides shared by researchers:

In summary, this seems workable, but we would better verify by also testing this state-space; ideally in a model-based fashion.

v0d1ch commented 8 months ago

I am slightly confused by how would the on-chain checks look like with these new snapshot digests in place? How would we prove that new snapshot is a direct successor to the previous one (if we ignore snapshot numbers)?

ch1bo commented 8 months ago

I am slightly confused by how would the on-chain checks look like with these new snapshot digests in place? How would we prove that new snapshot is a direct successor to the previous one (if we ignore snapshot numbers)?

Both, Open and Closed states will contain the $\eta$ digests of the current and previous off-chain state. Hence we can check equality with a snapshots reference $\eta{\mathsf{ref}}$ with either the current $\eta$ or the previous $\eta\mathsf{prev}$, which will allow us to distinguish also the individual scenarios (i.e. handling already committed or not yet decommitted UTxOs on close)

MicroProofs commented 7 months ago

Here is a sparse merkle tree implementation in Aiken with a offchain component that needs just a bit more work in rust https://github.com/aiken-lang/sparse-merkle-tree Here is an example of using it in on chain code. https://github.com/MicroProofs/inverse-whirlpool

The idea behind the implementation is to have an ordered list of hashes of members and then new insertions simply need a proof of the left and right hashes to verify both the old and new root.

ch1bo commented 7 months ago

Latest update of example transaction traces using the above mechanism of signatures including $\eta_\alpha$:

Nominal increment

Transaction traces - Incremental commits 2024-04-04

Alternative: Close with U3 instead of increment

Transaction traces - Close with U3 instead of increment(1)

Alternative: Close with U3 after increment

Transaction traces - Close with U3 after increment(1)

v0d1ch commented 4 months ago

Open question: How to detect that commit was never observed and have mechanics to remove it from the state so that the following commits are enabled again? If we don't have this then anybody could prevent other parties from committing more funds just by asking for a commit inclusion and just never follow through with posting the commit transaction on-chain. Maybe not relevant for the current iteration?

GeorgeFlerovsky commented 4 months ago

Open question: How to detect that commit was never observed and have mechanics to remove it from the state so that the following commits are enabled again? If we don't have this then anybody could prevent other parties from committing more funds just by asking for a commit inclusion and just never follow through with posting the commit transaction on-chain. Maybe not relevant for the current iteration?

IMO the root of the problem is that if the user's utxo is spent directly into a single increment tx, then you have no choice but to wait until after L2 snapshot confirmation to draft the increment tx, obtain the user's signature, and submit to L1. Thus, you are completely at the user's mercy to sign and submit the increment tx: if the user reneges, then you have to figure out a way to revoke the L2 peers' confirmation of the L2 snapshot, which is impossible if the user is an L2 peer.

The increment tx comes after the L2 snapshot confirmation because you want to support commits from a pubkey address, which can only sign a complete tx and whose signature is invalidated if the tx is modified/evolved. The only options that I see around this are:

  1. Disallow commits from pubkey addresses
  2. Deposit the user's utxo into an escrow that allows spending by signed user intent
  3. Deposit the user's utxo into an escrow that allows spending either by L2 multi-consent (before a timeout) or by user consent (after the timeout)

Hydrozoa uses option 3.

ch1bo commented 4 months ago

Open question: How to detect that commit was never observed and have mechanics to remove it from the state so that the following commits are enabled again? If we don't have this then anybody could prevent other parties from committing more funds just by asking for a commit inclusion and just never follow through with posting the commit transaction on-chain. Maybe not relevant for the current iteration?

Indeed, this would speak for a deposit-then-L2 workflow (we had considered that at some point, but wanted to avoid spending two transactions on L1).

However, is this a realistic case? If a participant requests to add something to the head, but then does not follow-through with it. How is that lack of cooperation different than not signing a snapshot? IMO both are a similar loss of consensus and warrant head closing.

GeorgeFlerovsky commented 4 months ago

Open question: How to detect that commit was never observed and have mechanics to remove it from the state so that the following commits are enabled again? If we don't have this then anybody could prevent other parties from committing more funds just by asking for a commit inclusion and just never follow through with posting the commit transaction on-chain. Maybe not relevant for the current iteration?

Indeed, this would speak for a deposit-then-L2 workflow (we had considered that at some point, but wanted to avoid spending two transactions on L1).

However, is this a realistic case? If a participant requests to add something to the head, but then does not follow-through with it. How is that lack of cooperation different than not signing a snapshot? IMO both are a similar loss of consensus and warrant head closing.

Right, but now you have an invalid multi-signed L2 snapshot and an invalid L2 ledger state. Arguably, that's worse than just a non-responsive L2 peer, because you have to clean it up.

How does the invalid multi-signed L2 snapshot interact with the contestation mechanism if the head is closed? Is there a clear way for the contestation validator to ignore the invalid snapshot and all its descendants?

Furthermore, what if this is an external commit from a user who is not an L2 peer (e.g. under delegated head architecture)? You wouldn't want to close the head just because the external user didn't submit an incrementTx...

GeorgeFlerovsky commented 4 months ago

@ch1bo If you do decide to use a deposit workflow, I think option 2 from my post above would be the simplest to implement:

  1. Deposit the user's utxo into an escrow that allows spending by signed user intent

This is something that the user can do on her own, in advance, without any involvement from the hydra parties. You can think of it as a "Hydra-ready" smart wallet utxo.

Smart wallet utxos are going to be widely promoted by other Cardano dapps, which also greatly benefit from intent-based user entrypoints. For example, an AMM DEX batcher can collect user intents offchain and then post just a single batch transaction to fulfill them on L1.

(See for example @MicroProofs's thread: https://x.com/MicroProofs/status/1808586118537097724)

Hydra's API could have a utility endpoint to help a user set up a smart wallet utxo. However, the /POST Commit would assume that the utxo to be absorbed is already in a smart wallet utxo with sufficient finality, which would be verified by HeadLogic before sending ReqInc to L2 peers.

This would allow ReqInc to include the user's signed intent for her utxo to be absorbed. This means that, as soon as the L2 snapshot is confirmed, every L2 peer will have everything needed to draft+submit the incrementTx if needed.


However, the disadvantage of this approach is that it relies on users holding funds in smart wallet addresses, which have only been proposed so far and are not well supported in wallet UIs. Then again, Hydra isn't, either. 😂

ch1bo commented 4 months ago

Got triggered by the thought that if we want to be safe properly secure Hydra Heads against rollbacks of incrementally committed funds, having full sequencing requirements + potentially long lockup times is going to be really bad. Also the UX workflow is an odd (see https://github.com/cardano-scaling/hydra/issues/199#issuecomment-1980456949 and https://github.com/cardano-scaling/hydra/blob/f24022532cb169eb3d404e8a70362bde37a21712/docs/docs/dev/protocol.md) mix between synchronous API and asynchronous interactive rounds on the Head.

In presence of rollbacks/pessimistic settings, this is creating a Head that is not "very live" as it would need to be forced to close in case a requested to commit UTxO is spent otherwise before the incrementTx hits the chain.

A deposit based scheme (as @GeorgeFlerovsky and others have been exploring too) using a synchrony assumption where funds are locked "to get picked up" for longer than typical rollbacks occur, is much preferable in these points. While it will require two on-chain transactions to add funds to a head, we can be sure after the first deposit that any spend into the head (before a reclaim deadline) is going to still apply if rolled back. So we can employ varying strategy on timeouts between deposit (wait long) and increment (no need to wait).

Here is a drawing of this scenario:

Transaction traces - Increment_ Deposit + versioned sequential commits 2024-08-01

noonio commented 3 months ago

We discussed the above in grooming and realised that another validator will be needed for the deposit workflow; a minting policy, because we need to ensure that things are correctly recorded into the deposit; we will need a token on the deposit, and these can be used to discover deposits.

GeorgeFlerovsky commented 3 months ago

We discussed the above in grooming and realised that another validator will be needed for the deposit workflow; a minting policy, because we need to ensure that things are correctly recorded into the deposit; we will need a token on the deposit, and these can be used to discover deposits.

(1) Why do you need to enforce correct deposit datum via an on-chain minting policy?

If the datum is incorrect, then the deposit can't be collected, but the user can reclaim it after deposit timeout.

(2) Doesn't that duplicate computation that occurs when collecting the commit later?

The datum needs to be inspected when checking that the head state merkel root is evolved properly, during collection.

ch1bo commented 3 months ago

(1) Why do you need to enforce correct deposit datum via an on-chain minting policy?

If the datum is incorrect, then the deposit can't be collected, but the user can reclaim it after deposit timeout.

@GeorgeFlerovsky How would you know whether the datum is correct? The transaction collecting from the deposit can't inspect the output that was deposited and needs to rely that it was recorded correctly into the datum (e.g. that the right address is recorded)

Ultimately, deposit is a two step protocol and the second step needs to rely that the first step was executed correctly. Using a minting policy and a minted token for contract continuity between the two steps is the standard technique for this.

Are there other ways to ensure this?

(2) Doesn't that duplicate computation that occurs when collecting the commit later?

The datum needs to be inspected when checking that the head state merkel root is evolved properly, during collection.

In a way, yes. It requires processing the output twice, but no duplicate computation. We are not necessarily using merkle tree structures for this feature (we might switch to that for #1468), but the processing would always be two steps: serialize and digest. The plan is that the deposit transaction does only do the serialization, which would allow for easy observation and detecting of what was committed (no input resolution needed), while the increment transaction would need to create a digest that matches the multi-signed snapshot (this depends again how the L2 state is represented on L1 and how snapshots are structured)

GeorgeFlerovsky commented 3 months ago

I guess my question is whether your onchain code should:

(A) merely check that the serialization parses into the correct type (i.e. something like { l2Addr :: Address, l2Datum :: PlutusData, l1DepositTimeout :: Slot, l1RefundAddr :: Address }); or

(B) also check that the serialization corresponds to the depositor's input utxo that provided the funds to create the deposit utxo.


Computation (A) is mandatory if your onchain code is responsible for the correct evolution of the head state hash during collection.

Computation (B) is a nice guardrail to prevent the depositor from shooting himself in the foot with a correct type but incorrect value in the deposit datum, but it incurs more fees and is not strictly necessary from the perspective of the hydra head.

ch1bo commented 3 months ago

@GeorgeFlerovsky I disagree that (B) is optional, it is crucial for the correctness of any layer 2. Otherwise anyone could claim anything on the L2. While the damage is somewhat limited on value as the L1 ledger would ensure that there is enough spent into the L2, it's important that any datum is retained correctly to not break scripts when they are moved into L2.

GeorgeFlerovsky commented 3 months ago

@GeorgeFlerovsky I disagree that (B) is optional, it is crucial for the correctness of any layer 2. Otherwise anyone could claim anything on the L2. While the damage is somewhat limited on value as the L1 ledger would ensure that there is enough spent into the L2, it's important that any datum is retained correctly to not break scripts when they are moved into L2.

Fair enough 👍

GeorgeFlerovsky commented 3 months ago

Although, I'm not quite sure what you mean by "anyone could claim anything on L2" and "any datum is retained correctly to not break scripts when moving to L2".

If the deposit utxo is being created from pubkey-held funds, then the deposit's L2 address and datum can be anything that the pubkey owner wants, as authorized by his signature in the tx.

If the deposit utxo is being created from script-held funds, then the deposit's L2 address and datum can be anything that the script allows in its "SendToL2" redeemer logic.

I think the difference between our views is:

ch1bo commented 3 months ago

@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 commented 3 months ago

@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.