ZK14 - eDAS: Extending Data Availability Sampling with Privacy and Compliance - Isobel Watkins (UCL)

Transcript

Thank you. So, hi everyone. I'm Izzy Watkins. I'm a postgraduate from UCL and today I will be talking about EDAS, which is short for encrypted data availability sampling. So, this is our work on extending data availability sampling to also support privacy and compliance. This is joint work with my master's thesis supervisors Nicholas Mombla and Philip Javanovich. So to start with I'll give an overview of data availability sampling.

So data availability sampling or DAS for short is a blockchain protocol that facilitates nodes with few computational resources to independently determine whether data is available without having to download it in full. In typical blockchain architectures like clients have to rely on full nodes to inform them if block data is unavailable. Therefore, DAS enables more nodes to participate meaningfully in the network and reduces the bottleneck on full nodes, which improves both scalability and decentralization of the blockchain.

So, at a high level, a DAS scheme works as follows. The data is stored as an encoding spread across the network. A light client can check the availability of this data by sampling a few shares of the encoding and verifying them against a commitment. If enough samples pass verification, then the client is convinced that the data is available. In addition, any node in the network is able to extract the block data if they have collected a sufficient number of shares of the encoded data.

So more specifically, DAS works as follows. The first step, the data is encoded via an encode algorithm to produce an encoding pi and a commitment denoted as COM. Clients first run the V1 algorithm to query positions of the encoding when they want to check for the for the availability of the data. V1 records the positions and the corresponding shares of the encoding in a transcript denoted as TR.

This transcript is then verified against the commitment checking that the sampled shares of the encoding are consistent with what was committed to. If successful, the client will accept the data as available. Finally, if a node collects enough transcripts from other nodes, an extraction algorithm can reconstruct the data from the commitment and the transcripts. So, a DAS scheme must satisfy three key properties. The first being completeness, which says if everything is run honestly, then data can be reconstructed correctly.

The second being soundness which says if verifiers are convinced that the data is available then it genuinely is and data can be reconstructed. And the final is consistency which says that when run on the same input reconstruction algorithm always gives the same unique output. Notice that in DAS the data being input is public and any node who collects enough transcripts is able to reconstruct the data in full. For many blockchain use cases, that's completely fine. However, what about the scenarios in which data is want to be kept

privately? Cryptographic privacy is almost entirely unexplored in the context of DAS and that's what this work sets out to address. So let's look at the properties that we want to explore incorporating into DAS. We firstly consider compliance as a guarantee that the data satisfies some public policy. For example, it could be that the data only contains characters within a specific alphabet.

Secondly, we consider privacy as that the data the privacy of the data sorry is maintained throughout. More specifically, we can consider the privacy in terms of being zero knowledge meaning that verifiers should be able to determine whether data is available without learning anything about the data. So, do existing DAS schemes give us either of these? Well, the answer is no. And the reasons are as follows. Compliance isn't satisfied in DAS schemes as there's simply no property in the DAS definition that gives any rules the data must abide by.

Privacy also clearly isn't satisfied as any node can reconstruct the data from collecting enough samples. Completeness ensures that this reconstructed data is the same as the original input data. Thus, a complete DS scheme cannot be zero knowledge as verifiers are able to reconstruct the original data, therefore learning exactly what the data is by running the extract algorithm. This tells us that we cannot simply simp simply tweak existing DAS schemes to achieve privacy and that privacy in DAS requires a fundamentally different schema. We look at building this schema in the following straw man.

So before discussing our entire solution to this, let's look at the most trivial attempt to achieve privacy in DAS. This naive approach would be to first encrypt the data and then run all the DAS algorithms as a blackbox on the cipher text. In this scenario, the DAS extract algorithm would reconstruct the cipher text instead of the underlying data. So this scheme would be successful in maintaining privacy of the plain text data. The data would be as private as the encryption method is secure.

However, the issue of this straw man is that the availability of the cipher text does not imply the availability of the plain text data. DAS properties guarantee the availability of the cipher text. But what if the cipher text were a load of rubbish and not actually decryptible to anything? There would be no way that the verifier could know whether this was the case. Hence, verifies could incorrectly accept data as available in this scheme. This illustrates why we therefore want to add a cryptographic link between the cipher text and the plain text data to enforce that the cipher text is in fact a valid encryption of some data.

And this motivates our following main construction EDAS. So, EDAS, short for encrypted data availability sampling, prefer um sorry, preserves the general structure of DAS, but also includes two new algorithms being encrypt and decrypt as well as tweaking the encode algorithm such that it also takes a state denoted as ST as input. As we will illustrate in our following two EDS constructions, these modifications enable verification of whether the cipher text is wellformed, which was the flaw of our straw man.

Moreover, the fundamental issue of DAS that meant that data couldn't maintain its privacy does not hold in EDAS as only the individuals with knowledge of the decryption key are able to recover the data. Now as EDAS is a form of data availability sampling scheme, the properties of completeness, soundness and consistency must be satisfied by any EDAS scheme. Moreover, we define EDAS such that it also provides privacy and compliance which we ensure through the two properties of EDAS being zero knowledge and policy enforcing.

We define zero knowledge to be such that EDOS can be simulated to produce a verified transcript that is indistinguishable from one by running EDAS honestly on some input data. Zero knowledge is achievable in EDAS unlike in regular DAS as the addition of an encryption layer means that is no longer true that any node can reconstruct the data. An EDA scheme being policy enforcing means that if some verifiers accept, then not only is some data available, but that the decrypted data also satisfies a public policy.

Next, we'll we'll present two constructions of EDAS. Both of the following constructions rely on two key tools being public key encryption and ZK Knox. ZK knocks are instrumental in enabling both privacy and compliance simultaneously. In both constructions, we implement a zk kn that proves the following statement s. The input data encrypts to the cipher tech and satisfies policy fi and the commitment com is a commitment to the cipher text.

This convinces the verifier that the data is correctly encrypted and policy compliant without ever learning what the data actually is. So our first construction is produced modularly from a public key encryption scheme, a DAS scheme and a ZK. The first step of our modular EDS construction is that data is encrypted via public key encryption to produce a cipher text and a corresponding state. This cipher text is then encoded as in DAS returning a commitment and an encoding as output. Our EDAS encode algorithm here also produces a zk proof

of statement s which is stored in the EDAS uh commitment alongside the DAS commitment. DAS algorithms V1 and V2 are then run as black boxes to obtain verified transcripts for a few positions of the encoding. Our EDAS V2 algorithm here also verifies the ZK proof. If both the DAS v2 algorithm and the ZKP verification algorithm succeed, then a client can accept the data as available.

Given V2 has accepted the data as available, our extract our extract algorithm runs the DAS extract algorithm to reconstruct the cipher text. And this cipher text can then be decrypted by individuals who possess the private key via the decryption method of the public key encryption scheme. Now, it's important to note that some DAS schemes already use snark proof systems internally. Thus, as our modular approach uses an existing DS scheme as well as a ZK NRC, this could result with running two separate proof systems with within this construction.

This would cause a large efficiency overhead and we look to counter this in our following direct construction. So the first step of our direct EDAS construction is identical to that of our modular construction with data being encrypted via the PKE scheme producing a cipher text and a corresponding state. This cipher text is then encoded using an arasia code. The code word produced is then committed to via a vector commitment scheme with the openings being computed for each position of the code word.

Lastly, a zero knowledge proof of statement s is also produced which is stored in the ed commitment alongside the vectic commitment. The code word as well as the openings are stored in the encoding pi. V1 then uses index samplers to determine a set of positions to query the encoding app. V2 uses both vector commitment and ZKR verification algorithms to verify the commitment against the encoded shares.

Given a sufficient number of transcripts that have been accepted by V2, our extract algorithm compiles a list of unique indices where the encoding has been queried. The extract algorithm then verifies that this list is not smaller than the reception efficiency of the erasia code. If this checks out, then the ERA codes reconstruction algorithm is run to reconstruct the cipher text. And finally, this cipher text can be decrypted by the individuals who possess the private key by running the decryption algorithm of the PKE scheme.

As mentioned earlier, whilst our modular construction is simple as it uses existing systems as black boxes, this can come with the cost of running two separate snark proof systems. Our direct construction is more efficient with everything combined into one snark proof. However, it does require being built from cryptographic components rather than reusing an existing DAS scheme. Therefore, it cannot be deployed on top of existing systems as easily as our modular construction can be.

So to wrap up um we have discussed why privacy is impossible in the standard DAS model. Therefore we have introduced EDAS as a framework for encrypted data availability sampling providing both privacy and compliance. And finally, we had given two constructions of EDAS. One being modular and easy to deploy and the other being more efficient, which we've both proven to be secure.

If you're interested in any of our formal proofs, the QR code can take you to our paper, but otherwise, thank you. >> Thank you very much, Isabelle. We do have time for questions. So if you have one question, raise your hands and wait for the mic. Go there. >> I'm worried about the concrete efficiency. So one component is a snark proving that the encryption of the cipher text uh so cipher text is the encryption of the plain text and the plain text has a given commitment. And to me this seems like an extremely

expensive thing. uh and the DS only makes sense for large data. So like what's the concrete efficiency of this thing? >> Yeah, definitely I don't disagree with that. Um we haven't measured efficiency practically in terms of metrics. Um obviously I think our direct construction is more efficient than our uh modular as it's one system versus two. But definitely I think there's room for improvement in terms of efficiency of this. This is the first as as far as we know uh DAS scheme that um introduces privacy. So the first isn't always the most efficient. Um but yeah, thank you.

>> Okay, another one here. >> Yeah, sorry it might be a bit of a repeat, but I was wondering about how you define efficiency because here it seems that one is more simple than the others, but vector commitments are quite expensive. >> Mhm. So >> yeah, no sure. Um, so if I take us back to there, this kind of gives a summary of the direct elus construction. If you can read the gray bits, that is. Um, so with our modular construction, it uses existing DS systems as a black box. Um, and this uses instead vector commitments, erasia codes. An example of a DAS scheme is one um produced from

erasia codes, vector commitments, all of that. So vector commitments are certainly very expensive. Um but the b the thing that makes this construction more efficient is the there being one proof system instead of two. Um because the modular construction theoretically that DAS scheme as a blackbox could also include vector commitments. Um hope that answers your question. >> Yeah, thank you. >> Are there any more questions for Well, you were very clear. Well, please round of applause for Isabelle.

>> Thank you.