FRIVail: A Data Availability Scheme based on FRI Binius

Transcript

So hello everyone. I'm Rajat. I work as a senior research and development at a project. And today I will be introducing Fryville, one of the data availability scheme we have been working on for a while. So I will first go over what was the purpose of it, why we needed it and then uh dig into a bit deeper on why uh we went with the designs we chose. So let's first discuss the problems right. So in the data availability space we have um two different type of uh dominant structures today. One is similar to what Ethereum is doing in the PRA uh implementation where they are using KCJ based polomial commitments and

coding the data committing it using KZJ uh based PCS and then just you relying on validity proofs by opening the polomials at a given position. Uh other alternates is competitors like uh Celestia where uh Merkel proofs are basically used alongside fraud proofs. Now merkeler proofs in nature do not create relationships between the points. So as a result you have to rely on fraud proofs uh in order to get the guarantee on chain that the data was available and the data was encoded correctly. And then there are other overrates for example all of these schemes and designs are not postquantum. uh like Merkel Merkel variant is in a sense is postquantum but

relies on fraud proof which is a uh problem if you want to rely on validity proofs and KZJ relies on a thing called bilinear pairings and bilinear pairings in turn relies on discrete log problems. So this again becomes a problem in a postquantum run because discrete log is considered broken and other than that ZK and PCS are still expensive today. So yeah so just to give a overview of what are today's designs do most of the KCJ based production implementation as I mentioned relies on balin peeling and fraud proofs rely on Merkel trees uh that's why the correctness guarantees comes from validity proof in case of uh

KZJ but in case of fraud proofs it comes from uh the constant size of uh like constant size of the Merkel commitment itself and these are all hashes of the data that you um want to actually encode and put on the blockchain. The postquantum guarantees are not there in KZJ but in case of fraud proofs they are available and similarly from practicality wise if you want to compare the cost KZJ is still relatively harder to prove because it's an expensive operation and u these are mostly based on prime fields and not binary fields compared to fraud proofs which are actually quite efficient we have very efficient algorithm for hashes but since there is a um challenge window involved when it comes to finalization it becomes

a really slow process for us. And then there is a overhead problem where in case of KZJ if you really want to recover some particular cell or data or a row you need to download all of the commitments corresponding to all of the other rows and in case of fraud proofs you also have to rebuild the entire grid in order to reach the part to in order to recover the data. And now uh since in last few years there have been few uh impressive breakthroughs. One of them is includes uh Zoda and the other one is Freda. So Zoda introduced the idea of a zero overhead idea. So as I mentioned on my previous slide uh in the last section, the overhead is a problem in KZJ and

both fraud proofs in a certain sense because you have to download data that are not relevant for the data you want to be concerned with. Zoda handles it by introducing uh uh vendor monte mantrix in their encoding system where basically the linear code allows you to uh download a particular row and the row in itself becomes a proof of correctness that the so basically when you download a row in case of zoda it says that the row itself says that I was encoded correctly and you don't have to download anything extra. Freda is a different design and Freda relies on the idea of fry polomial commitment scheme in uh in its whole. So Freda uh uses the Fry commitment schemes and uh the problem

with Freda that it addressed was that Fry schemes rely upon um the Fry when you do a Fry commitment you are actually not committing to the exact data but you are com claiming that you are committing to a polomial which is close to the original polomial and that is a problem which Freda addressed because we cannot have data close to the original we need the exact data and that's where uh the Freda paper introduced a new uh row plus one query system which fel inherits.

So to just summarize in today's world one of the most uh uh pro reliable design will be something that will have zero overhead. Uh zero overhead is a very important factor if you want to download and scale 10 GB and plus blocks. It should be postquantum because we are really coming close in a lot of benchmarks and estimations on breaking the discrete lock problems. Ideally we want a sharded design because network cost should not become a limitation and economic security uh should covers the gap if the current technology doesn't allow you to do it and of course you need to maintain the core DA properties which were originally the idea which is you should be eraser

coding the data and adding redundancy you should be adding some sort of a reconstruction mechanism and you should be a be able to open it at a particular point so now I'm going to dig a bit into how Fwell itself works and how we plan to implement it and what is the current status of the rollout. So first of all we use a thing called binary fields contrary to prime fields. So most of the original systems that I talked about say especially in the pol PCS era they rely on a prime fields and prime fields are not really CPU native.

You always end up having a to compromise on your computation cost when you're dealing with prime fields. binary fields as a result if you can build on top of it results in highly efficient computation and you get really good benchmarks. Uh fry inherently does erasure coding during the commitment process and the fry proof that you get in the commitment scheme in itself is a certain guarantee that the erasure coding was done and eraser coding becomes inherited part. you can actually specify how much uh redundancy you want during the um aid coding step and then of course we want some of a sharded architecture because if let's say you have 10 GB 20 GB of data you cannot

practically just propagate it through uh hundreds of nodes in a small amount of time which is the block time of your particular blockchain and then you also want to just do uh rowle operations ideally and you want to define your shards in terms of row. Ideally, let's say you are a big roll up and you have a lot of data to post. You what you do is you assign yourself a particular row and you create a subset of validators that deal with your row and keep track of your data. Ideally, the verification of your correctness should be done through validity proofs and not really re-executing of data. And then of course, we need some sort of an infinite horizontal scaling ideally if we can afford to since we are moving to shard architecture.

So how frival works right? So we start with a thing called encoding. So you take a raw set of data you convert it into a multilinear polomial and then from that polomial you derive a univaried polomial which is actually erasure coded using solomment code word commitment is actually the merkel commitments but if you have ever heard of how fry works in fry you have the bottommost row you commit a do a merkel commitment to this data and then you fold it to the next level and after the next level you do another degree of commitment ment which is again a ML commitment and so on so forth until you have a single element at the top and then the fry proof is basically the

final value at the top that you can verify against uh the u original uh code word that you had then you do the verification which is again in case of binary fields are really fast operations now and then sampling so sampling is a bit tricky in a sense that you can open things against the Muckle commitment but As I mentioned earlier, fry uh gives you the guarantee that the committed world is close to the original polomial and not the exact one. And that's where the R plus1 query select mechanism comes into play. This design was slightly inspired from Freda. And then I'm going to cover sampling again a bit later. Uh recovery is basically standard resolment

encoding recovery where if you have more than 50% of the data of a given row, you should be able to derive it. So I want to go a bit into the gap when you want to try and use something like fry in case of data availability sampling. So the problem with fry is that as I previously mentioned the the commitment the commitment and the fry proofs gives you the guarantee that the code word is close to the original polomial not exact. And when you do a thing called a query + one, basically you ask the prover to give you an opening for a particular cell in the data and then you basically do the check at every level and make sure that the

final output matches exactly what the claim proof is. Then you get the guarantee with the R+1 randomness cell opening that the code was was not u uh the code was not uh tampered with. Why does it work? Because in case of fry when you move upward you do a thing called fry folding and fryolding let's say you have a issue at the you try to change a world at the lowest level the error gets amplified at each layer. So it becomes really really uh probabilistically negligible to hide a tampered cell as you move upward especially if you're doing an entire query from bottom to top and that is

where the idea comes from. So there is a uh graphical demonstration of it. Let's say you are you want to open index I and you want to verify it uh against the against the Merkel commitment of the code word. You can open it. But now the question becomes what if the cell right next to I maybe was tempered or maybe I was slightly tempered. If you go to the level one which is the folded one if I was tempered if you reach to fold one stage what will end up happening is the error margin in the uh code word level gets amplified at fold one and this amplified error again gets amplified in the fold two stage. So the final

terminal uh result that you get almost will probabistically never match and you will have a guaranteed that the cold world was tampered with. So you can reject the sample. So here are some performance benchmarks. uh most of the production DAS either uh hover somewhere around in case of aware was hovering around four MB of data and the commitment size came down to up to 40 mconds and the proof size was 221 KB. One of the key thing is since you are using Fry the proof size does not linearly increases. We also tested it against 1 GB of data which is again around 11 seconds and 32 MB is again sub 300 millconds now. And this is happening

and this kind of performance is possible because now the underlying scheme relies on binary fields and no longer on um any sort of prime fields. Now I just want to talk a bit about the rollout stage. Uh so there is definite which is already live uh since July 2024. The test net went live in October and the mainet uh progress is in um the mainet deployment is in progress. Now just to mention one more thing uh I mentioned binary fields here and one of the key factor here is that there are going to be several loads in the entire sharded architecture. We need some sort

of a global representation for this. Today we uh have several options. One of them is relying on the consensus economic guarantees and the other one is you can either aggregate these fry proofs and fortunately today we have technology uh like if you have heard about flock which was recently introduced as a zk variant. Flock also uses binary fields and these kind of aggregations become quite native to those kind of new zkms that can that are popping up. So transitioning the fry proof in and verifying them recursively in a ZK circuit is now becoming a reality. This this system can be uh can be safeguarded using consensus and later

on can be easily be migrated to a uh binary based ZK proofer. So that's all from my side. Uh here is a QR code for all the papers related to this talk. all of the resources that you will need and if you have any questions you can also connect with me on my Twitter. Thank you. >> Awesome. Uh Rajit that that was amazing. Um yeah so I have some questions. Um main question here is how much faster is commitment generation with binas on binary fields compared to standard KZG commitments?

>> Significantly around we easily got around 5 to 6x increment on small data around 4 MB. So, and that this does not scale linearly. Uh, if you have 1 GB of data, KZG takes almost forever. >> And so, another question, when scaling blocks up to 10 GB, how much RAM and bandwidth does a light client actually need to perform sampling? >> Um, so not really much. So, if you have noticed in the design, what the light is actually doing is it is actually just u opening it against the fry proof. And if you looked at my slides, the fry pro is hovering around 300 KB. So 300 KB of network bandwidth is needed.

Computationally wise, you're just verifying mostly h kash hashes. So that again is not really a hard cell. So you can easily verify it even on your watch in today's era. >> Okay. Wow. So another question, why use fry and why use read solomment codes? Have you tried more optimal protocols like stir and wor? Have you explored the use of other eraser codes like error correcting codes? >> So fry was one of the key stuff we went with because first of all the uh frapp pcs are quite reliable and we know they are postquantum. So the post argument postquantum argument hold it for us. The second one was read solomon code. So

read Solomon code is essential when it comes to data uh uh data availability because if you do not read you do not encode your data and you lose a cell there is no way for you to recover the data and uh we have explored uh stere and we actually but if you actually go with the binius the performances that we got when we uh went with the fry binas and the binary field structures uh the ver protocols were actually getting beaten when it comes to extremely large sizes of data. So 1GB there is no uh the will performance was quite inferior when it come compared to uh binius based designs which is binary fields.

>> Another question that I had just like listening to your talk. So how much larger does the block have to get? So you overencode the data in the block right using read solomment code. How much larger like what is the the rate of the read solomment code that you're using? >> Yeah. So ideally we we more made all of our benchmarks as in as was in the slide with a 2x expansion. We can go further but the question remains is an engineering problem that if you have let's say 20 GB of data do you really want to add a redundancy of 4x and make it 80 GB or you want to if or if 20 GB is going to be sufficient for your uh particular use case. Another question uh does combining fry proofs improve data

availability without increasing prover complexity? Uh I don't get >> I also sort of don't fully understand that question but yeah >> um okay so >> um yeah I I asked this question essentially this uh by over encoding the data of a block using read codes how much larger does the block get >> uh over encoding the data of a block by using root how much does the block size become so if you are doing a 2x expansion right It depends. The system is completely sharded at this point.

There can be 10 shards with 10 GB of data and each shard in itself will basically move if you go with 2x that's almost the 2x of the size inside the block. The aggregation that the block hash itself will use and keep in the state that will be basically the aggregation of the systems. So it all depends upon the particular row. If you just combine all of the data and if you look at what of what is the u redundancy that you're adding the RS encoding that it will just multiply according to it. So if you have 10 GB 20 GB 20GB with 2x uh 2x 2x then it's 40 + 80 plus uh I think it was 40. So 40 plus uh 40 plus 80 plus 80.

>> Okay, makes sense. >> That's what the network can support easily. Um, next question is, is 10 GB block throughput realistic on a live network soon or is peer-to-peer gossip the real bottleneck holding it back? >> That's a very good question and one of the things that I covered was that we need sharded architecture because we do not want network bandwidth to become a bottleneck. When you can horizontally scale into subsets of validators that hold the data and rest of the validators just verify by downloading a few KBs of data, you actually get the scaling you want. In even other uh state-of-the-art blockchains, they are exploring systems in which you just verify the uh small proof and you basically get the guarantees. So it's aligns with the same

idea. You don't have to download the entire data. You don't have to re-execute everything to come to the conclusion that things are correct. Amazing Rashid. This was some really interesting stuff. I'm going to definitely read that paper on errint.