data availaiblity guarrentees outside EVM

[barryWhiteHat]

So roll_up POC has data availbiltiy guarrentees inside the snark. But this kind of sucks and the best we can optimize this to is ~ 5000 gas per tx. Which limits our scaling. So now we want to provide data availability guarrenetees outside the EVM so that there is no gas cost per tx.

[barryWhiteHat]

Comment from https://github.com/barryWhiteHat/roll_up/issues/6#issuecomment-421697548 Ideally we can construct a system in which users can go offline for prolonged periods of time and still reasonably expect their funds to be safe. Let's call it long exit guarantee. Zk-SNARKs cover the most difficult part of it: no incorrect transactions can be posted. Now, hopefully we find a solution the remaining challenge, data availability.

If I understand correctly, stale state exit approach would not have long exit guarantee, because users must act immediately when they face data unavailability for their branch. Right?

[yondonfu]

I think the above comment's point about zk-snarks solving one of the core requirements for the long exit guarantee is right. Plasma constructions require users to exit when they face unavailable data because once data becomes unavailable, the user wouldn't know if the operator included an invalid state transition with a new Merkle root submitted to the main chain. So, the safest course of action would be for the user to exit.

Since zk-snarks prevent invalid state transitions, if users face unavailable data, as long as they still have their most recently received data, they should still be able to use that for some type of exit at a later point in time - in the interim the operator wouldn't be able to modify ownership of the user's leaves?

[gluk64]

if users face unavailable data, as long as they still have their most recently received data, they should still be able to use that for some type of exit at a later point in time

Really interesting direction. The problem is that a malicious user can initiate exit with funds that have been meanwhile transferred to another user, in collusion with the operator who will not challenge this exit. They can thus drain the funds from the sidechain.

One solution we discussed on gitter is to have an exit queue on the mainchain, which operator is obliged to serve. This won't prevent operator from being able to stop a particular user from exiting, but freezing one user will halt all exits. An "everybody or nobody" game. With enough at stake it can motivate the operator to actually spread input data as wide as possible, to ensure it can not go lost.

[gluk64]

And, if such a halt event happens, then a recovery mechanism is triggered, where users are allowed to exit with their balances at some point of time in the past (e.g. N hours prior to the last unserved request). A precise point of time is required to prevent double-spends.

Let's assume we require operator to provide data with erasure coding, and all clients request and store random pieces of the state for every block. Now we can now rely on the honest minority to detect data availability and trigger recovery. This means, that in the worst case data damage will comprise transactions of the last N hours, but not all funds. Which, combined with operator's security deposit, looks like pretty decent security guarantee to me! It is comparable with finality guarantees of a PoS chain, and can be further optimized.

[barryWhiteHat]

Really interesting direction. The problem is that a malicious user can initiate exit with funds that have been meanwhile transferred to another user, in collusion with the operator who will not challenge this exit. They can thus drain the funds from the sidechain.

If you use one leaf per input and just change the owner of the leaf during transfers you can prevent this attack by storing the leaf address at exit time and then then compareing with it.

[gluk64]

If you use one leaf per input and just change the owner of the leaf during transfers you can prevent this attack by storing the leaf address at exit time and then then compareing with it.

I can't follow. Storing the leaf address at exit time and then then compareing where? Who does this at what point?

[HarryR]

More discussion from gitter, under the assumption that it's a centralised service which offers both data availability guarantees and does the proving:

• There are N 'data availability guarantors' - whos public keys are embedded in the on-chain contract
• A threshold signature, of at least 3 of those 'data availability nodes', for the merkle root being submitted, confirms that the centralised provider has ensured the data is available in a fault-tolerant manner.
• The prover provides this threshold signature along with the proof

This means, in the context of a centralised provider, the data availability nodes operate separately and largely independently from the prover. The two processes operate in lock-step: data availability is confirmed, prover publishes the proof for that data on-chain.

This also means that anybody could publish the proof as long as it's confirmed by the 'data availability nodes'.

But, on-chain management of the public keys of the 'data availability nodes' would be needed, to add and remove them.

[barryWhiteHat]

I can't follow. Storing the leaf address at exit time and then then compareing where? Who does this at what point?

So at each exit you confirm that leaf with address X has not been withdrawn before. Because leaves are never destroyed you just pass them around this should work fine. So a balance is deposited into a leaf. it is passed around throught transfers but its denomination is never changed. Then that leaf is withdrawn.

So there are two problems

1. This leaf can still be transfered in the snark. So we say that each user should only check leaves that have not been withdrawn.
2. There is no way to change the denomitation of a leaf in this system. I am thinking about this problem now.

[gluk64]

1. This leaf can still be transfered in the snark.

Yeah, that's the exactly the problem discussed: as operator, I transfer the leaf in snark and then initiate exit on the mainchain using the older hash. Nobody objects (because they don't have data), so I take the money, transfer the leaf further and continue, until the mainchain contract is empty.

[barryWhiteHat]

Yeah, that's the exactly the problem discussed: as operator, I transfer the leaf in snark and then initiate exit on the mainchain using the older hash. Nobody objects (because they don't have data), so I take the money, transfer the leaf further and continue, until the mainchain contract is empty.

You don't store the hash you store the address in the tree. You check against teh address in the tree not the hash. You can update the hash. But not the address.

[gluk64]

How about this:

1. Assume centralized operator model.
2. We have 'priority request queue' on chain. Operator is obliged to serve it.
3. If operator fails to serve a request for N blocks, then we have a proovable data unavailability event as operator's fault.
4. When and only when this event is triggered: 4.1. Everyone is allowed to exit under the improved plasma rules described by @barryWhiteHat 4.2. Anybody can object to stale claim, not only the owner. 4.3. Opearator's security deposit is used to compensate gas and processing costs to everyone (it must be sufficient).
5. If the failure was purely technical, operator can resume service anytime.

In this scenario there is no need for anybody to watch the chain 24/7 until unhappy event happens. If it happens, it will become news soon, and a lot of people will run watching software for a while, allowing everyone to exit safely. Emergency expenses are kept to a minimum. Operator can in no way profit from failure.

[gluk64]

To summarize the offline discussions, current approach is to implement the following mechanisms to solve data unavailability:

• First, a user attempts a cheap exit via priority queue on the root chain
• If the priority queue halts, the operator is slashed, and chain rollback is attempted
• If the chain rollback fails, we default to the normal plasma exit

[MihailoBjelic]

'data availability nodes'

After a lot of thinking about the problem, I think this would be the only realistic solution (at least in the short to medium term), but in a way that these nodes are the ones guaranteeing availability (instead of the centralized service) by storing copies of the data. They would probably provide some sort of Filecoin-like Proof-of-Replication, which would have to be submitted to the main chain alongside the root. They would be incentivized by either rent or inflation.

I've just started playing with this idea, so I would appreciate any feedback/input. Thanks! :)

[HarryR]

The currently proposed mechanism is:

• Operator guarantees to provide data availability
• Users can challenge the operator on-chain, with a 'data availability request'
• Operator must respond within N blocks, otherwise they incur a penalty

However, there is a problem - a stubborn operator may not upload all the data to 'the place' (e.g. IPFS, bittorrent), or could only upload a subset of it, and then still respond to data availability requests on-chain - but unless every user submits a data availability request to recover their data the whole dataset may not be available to everybody.

The idea with the 'data availability nodes' was that they would have to verify that all of the data is available, in 'the place', and the operator requires proof of that consensus before they can upload the zkSNARK proof.

Another problem is that the zkSNARK proof doesn't guarantee that the data it says it's working on is the same data set that the 'availability nodes / validators' signed off on.

I propose the following mechanism:

1. Operator publishes the sequence of transactions
2. Validators retrieve this information, verify it's correct etc.
3. Validators, as a consensus, sign a hash of all of the transactions
4. Operator runs the zkSNARK proof
5. zkSNARK has the 'hash of all transactions' as an input

This ensures that the data the validators came to consensus on is the same as what the operator is working on. However, we could go one step further:

With a content addressable distribution network, like IPFS or BitTorrent, lets take BitTorrent because I'm more familiar with that.

The zkSNARK circuit computes the info_hash of the input data, which means the block of transactions can be distributed as a trackerless torrent, the validators download it using the info_hash and also start seeding it.

For IPFS it'd work differently, and I prefer BitTorrent because it's more widely supported and easier to implement the info_hash part.

Using this mechanism means that, as long as the validators are >50% honest, then any info_hash they sign (which must be provided by the operator to publish the zkSNARK proof) can be used by users to download the block of transactions.

[gluk64]

A few game-theoretical questions:

• What incentives can be offered to validators? Fees?
• How to govern the set of validators?
• What incentives do ordinary users have to download the data from bitTorrent / IPFS? Since the priority queue and fallback to Plasma exit provide guarantees of eventual recoverability of the funds, it will likely encourage the majority of users to prefer low-ressource consuming light clients, especially on mobile devices.