Data availability

[L-as]

Motivation

We want to verify that the ledger (really account db) in our outer account is "available", that is, people who have a vested interest in what's on the rollup are able to see what's on it even after an update by a third party.

Assume for simplicity that everyone must know everything. This isn't a hard constraint and can be relaxed, but it makes it more complex to think about.

Assume that our DA layer is an unpermissioned "ledger", i.e., public bulletin board, anyone can post a batch of data to. Our circuit must somehow verify that the Zeko ledger has been posted to the DA layer, in such a way that given only the hash of the Zeko ledger and the full(-ish) DA layer content, you should be able to recover the Zeko ledger itself, possibly along with the commands/actions/events used to build it.

We want the behaviour of the nodes operating the network for the DA layer to be as simple as possible.

The dumbest approach is to make the basic batch unit of the DA layer the commands. Then you post the command to the DA layer, and prove that the commands that make up your ledger are on the DA layer. However, you can't recover the state from this efficiently, unless you don't allow skipping commands. The issue is that a user might post an invalid command (we can try to prevent this), and then we either need a way to prove that the command is invalid, or we don't, and skip it, but then we can't know what commands have been skipped and thus can't rebuild the state efficiently. For N commands in the DA layer you would have to try 2^N combinations naively.

We want a simple protocol for the DA network, i.e. the network of nodes that make up the DA layer. We can require that the DA layer only accepts valid commands, but this makes it much more complicated, and isn't a possibly on e.g. Celestia now AFAIK.

We want to use an unpermissioned extremely simple DA layer in such a way that Zeko can run on top of it.

However, we can try another approach: The basic batch unit could be made a list of account states that have changed, along with a link to the predecessor ledger state (which should also be in the DA layer).

In our circuit we then check that there is a batch on the DA layer such that the batch's output ledger matches the ledger hash we are committing to.

Then as an end-user, to recover the state we start from the beginning of the DA layer, and build up a tree of ledger hashes and corresponding ledgers, until we find the ledger hash we're looking for, at which point we terminate, returning the ledger we recovered for it. Any invalid batch is discarded and ignored.

The crux of the trick is that we denote what comes after what explicitly, heavily reducing the combinatorial explosion of possible paths when parsing the DA layer.

Expansion

You can expand upon this model in multiple ways.

The L1 (outer) account could point to not just a ledger hash, but also the location of the ledger, i.e. where on the DA it is. Thus, rather than scanning forward, you could scan backwards, starting from the most recent update to the ledger. You would also have to make the predecessors location-addressed rather than content-addressed, i.e. the location on the DA layer rather than hash of predecessor.

You could allow for multiple predecessors such that multiple people can cooperate. This, however, requires that the predecessors do not conflict.

We might also want more than just the content of the ledger, we might want the history. Perhaps we want the actions associated with an account. We can trivially extend the above model and include along with the ledger changes the actions posted to each account. The circuit must then take care to verify that the action state hash matches the posted actions. We can go a step further and include the whole command history for all accounts too, by posting the full command(s) for the ledger update, and have the circuit verify the receipt chain hash. Given an L1 (outer) account with some ledger hash, since we know the ledger hash is valid, we can deduce that all commands included on the DA layer in its history are also necessarily valid, since with each ledger there is a unique history of commands. The receipt chain hash enforces this.

However, what if we want to support changes that do not have an associated command? For example, we might update (or fork) the ledger, and force some change (e.g. change vk, balance). This still works perfectly in this model. The receipt chain hash is still valid and enforces that all commands in the history are both valid and the canonical ones that were used to create the ledger, but you do not know what order forced changes happened in if you had multiple in a row.

Implementation

How do we implement this in practice then? There are roughly three options for this approach:

• Multisig
• Celestia-style DA
• Espresso-style DA
• Mina events

Multisig

Public bulletin board

Consider a protocol where the multisig participants operate a very simple protocol. They hold a shared ledger, and sign the hash of data appended to it. This is enough for the above protocol, since all it needs is a public bulletin board.

In practice, our circuit would verify that the transactions to commit are included in the DA, along with all their predecessors. We have some inherent recursion then. We need the "DA proofs" for the previous commits to be efficient. In a single-sequencer case, this is trivial. In a multi-sequencer case, the sequencers might be non-cooperative.

We can accept as DA proof the proof for the previous commit (i.e. proof for the account update), or perhaps even the blockchain/transaction snark for it if it is available.

Pushing circuit logic into DA network

Rather than proving facts about what the DA has signed, we can instead make the DA sign the ledger hashes directly.

Regardless of what the DA layer signs, we can not commit to an invalid ledger. The DA layer can lie about the structure of what they're signing, but it doesn't give them any extra power. At the end of the day, the only thing they can do is withhold the data in the DA or prevent the rollup from progressing, neither of which are affected by proving the internal structure of what the DAC signs. Hence we can make the DAC simply sign the ledger hash.

Is there any point to the above protocol then? Yes, it is still quite simple as the DAC would only need the ability to apply commands. It does not need to verify any proofs, or know the state of the L1.

You can imagine other protocols where they need to know the state of the L1 that reduce the amount of data the DAC stores, and there is a trade-off between efficiency and simplicity.

Celestia (non-sharded shared unpermissioned ledger)

This is very similar to the public bulleting board multisig case, since that is essentially what Celestia is, but with a very big and dynamic multisig.

Instead of a simple multisig verification, the circuit would verify a Groth16 proof of Celestia consensus however. But care must be taken wrt. accidentally "rolling back" to invalid dishonest forks in case of leakage of old private keys.

Instead of having a signature for each batch of data posted to the DA, we instead have a Merkle tree of all of it. This increases the complexity by a minor amount. We can optimize and share the Merkle tree opening in case we need to prove existence of multiple batches too.

Espresso-style (sharded possibly unshared unpermissioned ledger)

Operating a public bulletin board in a sharded manner is possible and there is much literature on this matter. Consider e.g. Danksharding, this is fundamentally very similar to what we want. In some sense the only difference between this and Celestia is that, while both are "blockchains", unpermissioned public ledgers, this approach has a much bigger multisig than Celestia, made possible by reducing the amount of data that needs to be sent to each party via error checking codes (e.g. polynomial sharding).

In the end this is what we want, but it might be the case that Celestia implements it. Celestia has the benefit that it's shared with other networks, meaning that it's "more secure", but also possibly slower since there are more participants.

However, the security argument isn't perfect. Consider the case where the value (in terms of e.g. Ether) stored on all the rollups on Celestia is considerably more than the value of the Celestia market cap. Rational Celestia nodes would be inclined to disrupt the protocol on purpose and hold the rollups ransom.

To cover this case, we probably want the ability to roll back in case a commit with a valid DA proof is posted but later found to be malicious. This doesn't work if the DA layer is Zeko specific and is controlled by the same token though obviously.

Mina events/actions (native L1 DA)

This option is attractive since if consensus is tied to DA, you can possibly cause rollbacks if DA fails, protecting the rollup from DA failures. OTOH, you're now restricted by what the L1 offers.

We would again use events like a public bulletin-board the same way we would with Celestia, in a black box manner. Preconditions give us a "merkle tree" of everything posted. That's it.

Unfortunately, currently the throughput for events/actions on Mina is quite low AFAIU, meaning that it isn't a realistic option for now.

In the future you could imagine a change to Mina such that events are shared à la how blobs on Ethereum will (?) be.

[L-as]

I updated issue contents

[MartinOndejka]

Instead of having a signature for each batch of data posted to the DA, we instead have a Merkle tree of all of it. This increases the complexity by a minor amount.

Complexity might not be an issue, but checking merkle proof of sha256 for each transaction will be a major bottleneck.

[MartinOndejka]

We should not forget about the native DA solution of Mina with events. I'm convinced that this should be the way to go. Not only for us, but for everyone using Mina.

[L-as]

indeed, completely agree with DA part. I have communicated this to O1/MF as much as possible, but it isn't realistic in the short term. I should have included it above though.

Wrt. merkle proof checking, I confirmed that if you post a single blob of all the transactions you want to commit, they will be split up and put into a merkle tree (leaf size = 512 bytes) such that all the "shares" are adjacent, ergo you can reuse most of the merkle path. It's 2N sha256 hashes for N shares apparently. I don't know how many hashes we can do per circuit but this doesn't seem too bad.

[L-as]

Added some short (given that it's trivial) comments about native DA.

[MartinOndejka]

In the future you could imagine a change to Mina such that events are shared à la how blobs on Ethereum will (?) be.

AFAIU they are currently shared the same way, why can't we have the same throughput?

I think that just being able to pay for more than 100 events should be already usable DA layer. Later we can think of adding DA sampling for light clients and whatnot, but it should be done in iterative way, same as on ethereum.

I think being able to pay for more events/actions is more than realistic to get included in next hardfork.

[L-as]

will not is. Indeed, we should at the very least try it.

FWIW now that I think about it alternative designs might be better in this case since you could accept only sequenced commands as events, the dumbest way you can think of, like all zkapps do by default.

I’ll try to implement it if it’s easy enough and we can see how it goes.

[L-as]

149 we already have this issue btw

[L-as]

You can do paying for more by splitting it across more commands.

[MartinOndejka]

You can do paying for more by splitting it across more commands.

I think you would run into txn block limit as throughput isn't high enough. But if not, maybe it's worth trying.

[L-as]

You could use the whole command as DA now that I think about it…

[L-as]

One thing to consider wrt. content-addressing vs location-addressing is that the former is trivially compatible with using multiple DA layers at the same time. In the latter setting the location might be different depending on the DA layer, which is an issue if you do a product instead of a sum of DA layers. (For a sum, it would be, the batch is accepted if it is in either layer, for a product, it is accepted if it is in both layers. Of course you could make the location a pair of the locations for each DA layer, but this is more complicated vs simple content-addressing)

[MartinOndejka]

We can accept as DA proof the proof for the previous commit (i.e. proof for the account update), or perhaps even the blockchain/transaction snark for it if it is available.

I don't understand this part, can you elaborate more on what the DA proof is in this case?

[MartinOndejka]

Regarding Multisig, do we actually need the shared ledger and consensus at all? Can the DA validator be just a service that stores and signs the batches and sequencer asks each to do so? It would tremendously simplify the architecture.

[L-as]

We don't, each "node" can be its own "DA layer", and we can compose them as I write in https://github.com/zeko-labs/zeko/issues/12#issuecomment-2209604020