Hydrozoa: Lightweight and scalable Hydra Heads

[GeorgeFlerovsky]

Why

This is an adaptation of the Coordinated Hydra Head protocol with more lightweight and scalable Hydra Heads. It introduces cheap and deterministic state update transactions as the default way to commit utxos to and decommit utxos from the Hydra Head. A similarly cheap finalization procedure can be used to stop operating the head if consensus can be maintained throughout its life. The halt and dissolve procedures (analogous to close and fanout in the Coordinated Hydra Head) are more expensive and should only be used if L2 consensus breaks down.

What

The main design ideas of Hydrozoa are:

1. Eliminate the initialization phase — open the Hydra Head immediately with an empty L2 active utxo set.
2. Commit utxos on L1 to the head simply by sending them to a native script address controlled by the participants' keys.
3. Transact on L2 in the same way as before, using Cardano ledger rules to apply transactions to the L2 active utxo set.
4. Decommit utxos via a new L2 request to remove certain utxos from the L2 active utxo set, validated like an input-only transaction via modified Cardano ledger rules.
5. While the head is open, periodically collect commits and release decommits on L1, updating the major version in the L1 head state. Semantic versioning is used because these updates are backwards incompatible with previous snapshots — updates change the balance of funds at the head state utxo.
6. If participants can maintain L2 consensus, finalize the head and release its L2 active utxo set on L1 just as cheaply and efficiently as if all utxos decommitted.
7. If L2 consensus breaks down, halt the head and dissolve its remaining funds to produce outputs corresponding to the L2 active utxo set of the snapshot with which it was halted. Dissolution is specified and authorized via multi-signed certificates instead of multi-signed transactions.
8. Spin off the contestation mechanism so that it can only affect the head state when the contestation deadline elapses or all participants have exercised their right to contest.
9. Updates should be used during normal operation to commit and decommit utxos, finalization should be used if the participants want to stop operating the head, and the contestation mechanism should only be used to halt the head if consensus breaks down.

The L1 component of the Hydra Head protocol becomes simpler, cheaper, and more scalable. In exchange, the L2 component is somewhat more complicated.

How

More details are described in the article:
https://github.com/GeorgeFlerovsky/cardano-ideas/blob/main/001/README.md

(Open in a browser, not the Github app — it sucks at rendering)

Lower-level details are currently TODO, but most of them should be straightforward to complete.

[ghost]

Interesting! I did not go through the detailed article but will definitely have a look later on next week. Foregoing the (costly) Init and CollectCom transactions is something we have been discussing a bit in the past but never acted upon. Just thinking out loud but perhaps this is something to consider as an alternative protocol to the standard head that could be hosted within the same "node", eg. the hydra-node provides the infrastructure to talk to L1, interconnect L2 parties, and offers an API to clients, but the same "shell" could run different protocols, represented by different HeadLogic components.

[GeorgeFlerovsky]

The proposal modifies the L1 head log, too — simplifying it. However, I suppose that the L2 stuff could run on top of a different L1 stack, as long as it can interpret the stuff from L2.

Conversely, the new L1 logic can support a completely different L2 consensus protocol — not necessarily using the Cardano ledger rules. I think that's one of the strengths of the proposal: its simpler L1 makes fewer assumptions about what happens in L2, making it easier to support a variety of L2's.

[GeorgeFlerovsky]

Having said that, I think that a lot of the existing codebase for Hydra can be re-used.

The main things to change would be:

• Head logic
• L1 transaction builders and watchers (simpler)
• L2 messaging and consensus (more complicated)

You guys made a lot of quality supporting libs for monitoring/interacting with L1, communicating between nodes, etc. that can be significantly re-used.

[uhbif19]

Very cool. My initial thoughts on first read.

Questions:

• "contestation deadline t_deadline is T_C seconds after the upper bound of this validity interval" - why participant cannot manipulate this by using big upper bound? So tx will be accepted and contestation resolving will be locked for that time. Upper bound is limited by horizon but still.
• "Each participant caches the received L2 transaction requests, without validating them, until they are needed to create or verify a snapshot." - what happens if tx request is cannot be performed in some way? What happens if requests have different ordering on different nodes?

Questions:

• aggregate trees have different logic for dissolving and de-commit, right?
• Is "assurance transaction" can be invalidated somehow? Like if L2 spends this commited Utxo, then it should be invalidated, right?

Minor issues:

• Figure 2 - no "open" input. Is that right?
• "The participants can unanimously agree to finalize the head." - link does not work.
• article.md file seems to be duplicate of README.md.
• It seems that Rationale should to be on top in TOC, cuz it is high-level description.

[GeorgeFlerovsky]

It seems that Rationale should to be on top in TOC, cuz it is high-level description.

I'm following roughly the same structure as they use in CIPs:

• Motivation (currently missing) — what is the problem and why is it a problem?
• Design – at a medium-high level how does the solution work?
• Spec – lower level details
• Rationale – why does the solution work in this way, rather than some alternative ways?

[GeorgeFlerovsky]

aggregate trees have different logic for dissolving and de-commit, right?

Yes. For decommits, we know exactly what the transactions look like, because we know which specific utxo they branch out of.

For dissolution, we don't know which utxo the dissolution trees with branch out of, because we don't know exactly how the head state will be halted (i.e. the sequence of transactions leading to the halted state). That's why we have to use certificates for the dissolution txs and plutus validators for the aggregate outputs.

[GeorgeFlerovsky]

Is "assurance transaction" can be invalidated somehow? Like if L2 spends this commited Utxo, then it should be invalidated, right?

Yes. The assurance transaction is only needed if the participants ignore the committed utxo. If they spend it, then the assurance transaction should be discarded.

[GeorgeFlerovsky]

"The participants can unanimously agree to finalize the head." Link doesn't work

Not sure why it doesn't work for you. Works for me...

[GeorgeFlerovsky]

The validity and ordering is determined by the snapshot leader who assembles the list of requests to include in the snapshot.

Oh right. So participants only validate tx set?

"The participant waits until he has observed all of the L2 transaction and decommit requests" - is that why participants cache tx requests?

Yup 👍

[uhbif19]

Take 2.

Questions:

• How script (like our hydra-auction script) would check that it gonna be commited in Head with given Id? If it is just sent to native script address.
• "A snapshot must contain: Hashes of the L2 transaction and decommit requests"
  Why only hashes? If leader dictates "true" ordering of requests, when other delegates could not know it to validate snapshot.
  • "assurance transactions" - why are they needed to be saved in snapshots?
• "The root dissolution transaction must: Verify that the granular and aggregate outputs hash to "
  Verify off-chain? I am not sure how this could be validated on-chain.
  • "Each aggregate output is at the unparametrized validator with datum (s,r,j)" - what about real de-commited tx datums, how they would be restored? Like there is no info about correct datum/value for tx on-chain this way.
    I do not understand how encapsulated datums should be encoded at all.
  • Are you sure that multiple-party pre-signing of tx trees would work?
• "The participant waits until he has observed all of the L2 transaction and decommit requests"
  Could not network layer ensure that leader knows that every node acknoweleded requests used in snapshot? Maybe this does not improve anything though.
• "A snapshot becomes confirmed when all participants unanimously sign all of the assurance transactions" - seems wrong. They sign assurance tx before commit happens.
• The participant waits until he has observed all of the L2 transaction and decommit requests
• "each update transaction depends on the head state output of its predecessor update transaction"
  what means that next update (and Head as whole) should be blocked
  by previous update confirmation. Could not one make Head slow when, attacing by multiple garbage commits? Seems expensive though.
• Also not sure what happening if update invalidates. I think major shoud be same and leader re-create signing requests. Maybe other peers should also check that update tx is actually invalidated.
• "If the snapshot is minor, then the participant checks that: The L2 requests contain no decommit requests."
  Seems like this should be checked in on-chain case as well.
• "This ensures that no one can execute any of the snapshot's settlement or dissolution transactions until all of the participants have provided all of the signatures necessary for the snapshot's complete confirmation."
  But settlement tx depend on update tx, so cannot be performed before anyway.
  As for dissolution - could it not be performed anyway, by sending
  halting tx concurrently with leader update tx?

Ideas:

• Instead of assurance tx pre-siging, one can use native script checking all signatures or deadline. Script address would be dynamic then, but it can be discovered by other means.

[GeorgeFlerovsky]

I meant that if leader will only use requests acknowledged by all peers, then they could not wait for requests to come,
but just invalidate snapshot on spot if requests are not known to them. Not sure that this is better though.

It's an alternative way to do things, but I think I agree with the Hydra team's reasoning for not confirming L2 requests individually.

[GeorgeFlerovsky]

Yes, but your diagram seems to confirm that major updates are blocked by previous update.

Yes, each update transaction is dependent on its precursors. That's the only way that we can guarantee that update transactions will not be ignored/skipped.

[GeorgeFlerovsky]

I thought your spec requires to consume all eligible commits. Seems I was wrong.

In an earlier iteration of Hydrozoa, I had considered having aggregate commits that would be created by helper transactions to collect eligible commits for the update transaction. Something like this:

flowchart LR
  head\_state\_1([Open s])
  commit\_1([Commit 1])
  commit\_2([Commit 2])
  commit\_3([Commit 3])
  commit\_4([Commit 4])
  head\_state\_2([Open s'])
  agg\_commit\_1([Aggregate commit 1])
  agg\_commit\_2([Aggregate commit 2])
  agg\_decommit\_1([Aggregate decommit 1])
  agg\_decommit\_2([Aggregate decommit 2])
  decommit\_1([Decommit 1])
  decommit\_2([Decommit 2])
  decommit\_3([Decommit 3])
  decommit\_4([Decommit 4])
  decommit\_5([Decommit 5])

  update[Update]
  update\_2[Next update]
  collect\_1[Collect]
  collect\_2[Collect]
  split\_1[Split]
  split\_2[Split]
  
  commit\_1 --> collect\_1
  commit\_2 --> collect\_1
  commit\_3 --> collect\_2
  commit\_4 --> collect\_2
  collect\_1 --> agg\_commit\_1
  collect\_2 --> agg\_commit\_2

  head\_state\_1 ----> update
  agg\_commit\_1 --> update
  agg\_commit\_2 --> update
  update --> agg\_decommit\_1
  update --> agg\_decommit\_2
  update ----> decommit\_5
  update ----> head\_state\_2

  head\_state\_2 --> update\_2

  agg\_decommit\_1 --> split\_1
  split\_1 --> decommit\_1
  split\_1 --> decommit\_2

  agg\_decommit\_2 --> split\_2
  split\_2 --> decommit\_3
  split\_2 --> decommit\_4

  style update\_2 stroke-dasharray: 5 5

Loading

However, I didn't like that approach because it was more complicated and because I couldn't figure out how to make the update transaction be the root of everything (needed for snapshot atomicity) when the helper transactions are its precursors.

[GeorgeFlerovsky]

But given that you say that leaders are free to select commits, could not they just ignore commits until some of it would be expired, and Head L1 state gonna be invalidated?

If a major snapshot is confirmed, then any one of the participants can submit the update transaction on L1 to collect the commits. Furthermore, if the update transaction is constructed prudently (i.e. the commits that it collects have sufficient block depth and enough time before their assurance txs become valid), then there's plenty of time to submit the update transaction. I don't see why any one of the participants wouldn't submit it; conversely, if all participants choose not to submit it, then you could argue that they unanimously chose to invalidate the confirmed snapshot post hoc.

[uhbif19]

I don't see why any one of the participants wouldn't submit it; conversely, if all participants choose not to submit it, then you could argue that they unanimously chose to invalidate the confirmed snapshot post hoc.

I mean that if they must submit all known commits, that may lead to locking by having too much commits. If not, commits could be not handled in time, which leads to halting. So I think there should be some reasoning, why protocol is resilient to having too many commits.

[ghost]

@GeorgeFlerovsky I am trying to pandoc the README.md to get something I can print and annotate (sorry, I am a bit old-school and need paper and pencil ;) ) but running into issues with amsmath and align* environment. Did you try to do that already?

[GeorgeFlerovsky]

I made a PR to fix it. Does it help?

https://github.com/GeorgeFlerovsky/cardano-ideas/pull/1

With this PR, you should be able to run this from the root of the repo:

cd 001/ && pandoc article.md --pdf-engine=xelatex -o article.pdf

[GeorgeFlerovsky]

I also sent you a rendered PDF (with mermaid diagrams rendered) on slack

[ghost]

Thanks a lot @GeorgeFlerovsky ! I managed to get it but the mermaid diagram were not rendered of course.

[ch1bo]

Did you succeed in generating a markdown converted latex including mermaid?

[ghost]

I finally found the time to go through the paper, lots of interesting things @GeorgeFlerovsky! I don't have very detailed questions or concerns at this stage, I would need to re-read it and perhaps draw a bit more how I view the txs flow to really understand it, but here are a few feedback points:

• As said, I like the overall idea that opening a channel is a one transaction process and does not involve multiple steps like Hydra head
• Using native multisig scripts allowing the use of a single pair of keys both for off-chain and on-chain consensus is clever. The initial intent of Hydra Head paper was to use a more advanced multisignature scheme like musig2 that allows more efficient signature schemes, but this is far from being integrated in Plutus,
• Using major/minor version for snapshots to delimitate changes that impact the head balance from changes that keep it constant makes sense, something we could possibly reuse when implementing commits/decommits in the Head
• Rather than having specialised ledger rules, couldn't we make decommit L2 transactions balanced using fees for example, so that the variations of the L2 treasury would represent variations in the overall balance of the head? I guess I am concerned with departing from using standard ledger :)
• In the Verify snapshot part there is the whole discussion about how "participant simulates an L1 ledger state", I am not sure how this would be done as managing L1 state might imply maintaining a lot of state,
• The "assurance" txs sound a lot like Lightning and is definitely a cool idea which the native multisig script enables, perhaps also something to think about for a Head,
• Of course, the protocol is more involved than the Head which raises the question of how much work is needed to implement it correctly.

[GeorgeFlerovsky]

You're right: the determinism of the settlement transaction relies in a somewhat fragile way on having an accurate view of the L1 subset when the transactions are created and multi-signed, and there isn't really a good recovery mechanism other than halting the head with the last snapshot that was not invalidated by the new dominant fork on L1.

That's why I tried to be comprehensive about the sources of invalidation for settlement transactions and recommended fairly conservative mitigation measures to minimize the probability of settlement transactions' invalidation. Also, the hope is that L1 forks wouldn't invalidate too many L2 snapshots, so that not that many L2 transactions would be affected.

[GeorgeFlerovsky]

Another thing to consider: you can perhaps borrow parts of hydrozoa for smaller incremental improvements to hydra.

Definitely. There are quite a lot of interesting ideas to explore and steal :) FYI, we have asked researchers from IOG to have look at it. They won't have the time to do a deep dive but I think even a high level feedback would be useful

@abailly Did the IOG researchers have any feedback on hydrozoa?

[abailly]

My apologies @GeorgeFlerovsky , I was OOO the whole week hence why I did not reply earlier. No, we haven't heard back from researchers, AFAIK

[GeorgeFlerovsky]

Thanks for letting me know @abailly. Would be curious to hear their feedback, if they ever get around to it

[ch1bo]

This thread is maybe already a bit off topic, but I saw:

If there's a better way to do that while ensuring that decommit transactions can't be abused on L1, I am open to suggestions.

Putting an output (that is owned by a key/script) is complete safe thing to ask. The L1 would check for authorization anyways. So I do not think that we need to prove "ability to spend" on the L2 in the first place?

[uhbif19]

@ch1bo @abailly @pgrange

cc @GeorgeFlerovsky

Related feature sub-proposal:

For our (hydra-auction) usecase it is important to prevent Head stopping before bidding end time. Any bidder has incentive to stop Head, to make all following competing bets harder to make. So if node is on same side as some bidder, it has such incentive too.

In theory protocol could forbid closing before some time. But there is no way to ensure that peers will continue to participate in protocol. Slashing for preventing Head work seems very hard to implement.

But there is other option. Protocol could use m-of-peers consensus, instead of all-peers consensus. In model of this proposal it should be very simple to implement and make it configurable, by just changing native script. That way it would be harder to stop Head before it is planned if nodes are independent.

In that case halting by single node should change too. Otherwise single peer could stop it. I guess halting should have (n-m)-of-peers consensus, where n is number of all peers.

[uhbif19]

Halting may have n-m consensus (where n is number of nodes, and m is nodes for "normal progress" consensus). Or maybe it should be n-m+1? That way halting may happen exactly then number of nodes opposing to consensus is such that it may not happen anymore.

Closing should have same "normal progress" consensus as snapshots.

Contestation do not have any separate consensus mechanism, cuz one just uses snapshots which was signed before, I think.

[uhbif19]

I probably did not think of the case then some nodes are pro-snapshot, some are opposing it, and some just want to prevent any protocol progress.

Also nodes may be different incentives for having money decommited and for closing/halting.

[abailly]

Byzantine fault tolerant systems are hard :) It seems to me that for the cases that matter, having a way to penalise uncooperative parties through pre-signed transactions might be much easier.

[uhbif19]

Do you mean signing transaction before knowing its content? This does not cover our case. Bidder has incentive to prevent all next bids on L2, regardless of their content.

[ch1bo]

Do you want to open another discussion dedicated to this topic? I think it does apply to any of the current Hydra Head designs (including Hydrozoa)

[ch1bo]

I had the chance to go through @GeorgeFlerovsky's proposal in detail today and while I thought I would chime in in other threads, it was quite hard to do that as it contained many clarification questions & responses. This thread will be no different, so let's keep it a thread-per-reviewer discussion :)

Overall: Thank you, George, for researching this and I hope this gets funded through catalyst as I'm curious if the different approach of dealing with snapshots can be done and brings the benefits you foresee. In any case, I will personally draw inspiration from your ideas in this, do understand now some aspects better also in other designs, and finally see many similarities - confirming we are on to something here altogether.

Summary of what I liked/disliked:

• Pro: Form of the write-up (MD + mermaid)
• Pro: The lack for an opening phase
• Pro: The idea with the pre-agreed assurance tx (in case commit was not picked up)
• Con: Interaction needed to commit
• Con: Ledger modifications / special treatment transactions for decommit
• Pro: Symmetry of collecting commits/producing decommits via tx_update
• Con: Snapshot leader needs to worry "how much" can collected
• Con: Complexity of decommit transaction trees (is this split fanout?)
• Pro: Finalize the head seems to be "optimistic finalization" from the Head paper.
• Con: Overall complicated with many different L1 transactions types (11)

General comment:

• The reason for separate keys in Hydra Head is not because of the initialization phase, but because we anticipate to use aggregatable multi-signature schemes for smaller signatures on-chain. With secp256k1 signatures added recently to plutus, we will be able to use Schnorr multi-signatures (or even better/later BLS). One could argue that this was pre-mature optimization / YAGNI though.

Questions:

1. How is it verified on L1 that the right UTxO were added/removed? I could not find where a proof of UTxO available on L2 is recorded on the L1.
2. Why not also limit how much to decommit, such that no aggregate decommits are needed?
3. The section about update transactions becoming invalid is scary and I didn't really understand. It seems to relate to potential rollbacks? Finding that "sufficient block depth" is super hard and it would be highly preferrable if each head participant can decide for themselves how much assurance they want before they "see" a commit as valid (blocking L2 consensus if needed). Maybe this is already the case and I didn't understand?
4. Do you think we could just use Merkle Patricia Trees (MPT) as described in the paper (or sparse merkle trees) instead of the "tree of dissolution certificates"? After all these dissolution transactions seem to form a merkle tree already!
5. The "verify a snapshot" section seems to be very different to the Head protocol paper and spec. It's also very verbose and seems to have branching (not all variables are need in all cases). Do you think we could write this in some pseudocode?
6. I did not understand the rationale for the separate contestation thread. Isn't this resulting in poential race between the threads? Or at least it introduces additional complexity by needing the reset transaction?
7. Do you have an estimate in how expensive the commit via a plutus validator would be? The fact that committers must interact with the Head to get a multi-signed tx up-front (neat trick though) is quite some additional complexity and would be great if we can avoid it.

[GeorgeFlerovsky]

Thanks for your feedback. I'll consider it and respond in the coming days