A novel approach to proof-of-replication via polynomial evaluation with Foteini Baldimtsi

Transcript

happy to introduce fantini who's an associate professor G also a research adviser to M Labs um she does a lot of really cool black cryptography and work on blockchains in general her talk is uh not about snarks um might be very snark week but the techniques are related and I'm excited to hear about it thank you so much Justin and thank you for having me here um so I'm very excited to talk about a very recent work uh that is going to appear in crypto in a couple of months this is a work on decentralized um storage increasing scalability of proof of replication and uh it is joined work with colleagues at George M University and uh also um mat Labs well M used to be at filecoin when we started

this work but now has moved let me start with a brief introduction uh on some of the uh fundamentals in the space and let me first introduce what we mean by the notion proof of space so in a very abstract way you can think a proof of space as an interactive protocol between aover and a verifier so you might have a prover that has committed to dedicate a certain amount of storage so let's say 1 Gigabyte and um it wants to convince the verifier that indeed it is using this space proofs of space have been uh proposed as an eco-friendly alternative to proof of work and uh they have found applications on Cil resistant blockchain

consensus but also spam protection Doos attack resistance and so on an important note to make about proofs of space is that the statement that the prover is proving is literally just the fact that they are committing a certain amount of space but the in the typical proof of space setting you don't the the Prov does not prove anything about what are the data that they are storing okay so the data it's not particularly helpful or specific it doesn't really matter what the data is proof of replication uh is uh related to grof of space but tries to um solve this exact point that I made before the pro receives a particular piece of data and they commit that they dedicate certain

memory to store that exact data D okay so um I like to separate the phases the process of a proof of replication by um two stages the setup uh phase and the audit phase so in the audit phase the verifier again is going to challenge the prover and um the goal of the approver is to convince the verifier that indeed they are using they have committed that much space but also that they are storing this particular piece of data the reason that we care about proof of replication as opposed to just proof of space is that you don't weit waste the space of the prover you can actually use the space to prove something

useful and um in a very abstract uh level the uh the security guarantee that you want here is that um the Prov is going to dedicate unique storage um resources for every replica of the data so uh proof of replication can be very useful to build decentralized and verifiable uh file storage an important uh also point that I want to make about both proof of space and proof of replication I mean you know these are proof systems um you would typically think that their basic security requirements would be uh correctness and soundness uh but there is one more property that is um relevant and very important in both settings here and this is the uh the notion of space Gap and

again in a very high level and we're going to um formalize this a little bit more later in the talk um when we refer to a space gap or sometimes also called the tightness of um of a proof uh we refer to the difference between the amount of space that the prover claims to have dedicated here and the actual space that they're using in order to compute their proofs okay so obviously um the tighter the proof here is the more secure the system is another way to think about proof of replication is as a combination of various other types of proofs that have been proposed in the literature so you can think of it as proof of storage again the pro is proving that is dedicating a certain amount of space proof of data possession

that the pro is really holding that particular data that um uh you asking to prove and also proof of retrievability in the sense that the prover should be able to return uh back this data if um it is asked proof of replication uh has found um applications as I said before in various settings but the most prominent one and the one that we uh This Crowd here I would guess cares most about is a file coin um I I assume most of you are familiar with the basic idea of filecoin it is an open source uh cryptocurrency that at the same time also serves as a decentralized storage system users are willing uh to pay um uh some um some amount in order for files

for their files to be stored and of course we want to do that in a way that uh users can be sure that their files are retrievable and they can uh get them back so if we try to think a little bit about how file coin works as a I said before we have users uh they are willing to pay a fee in order to have some providers that are participants in the file coin consensus protocol to store their data um the store providers will uh guarantee through the blockchain that they are indeed storing the data and there are also these retrieval providers that help users to retrieve their data back but the important phase here is the fa the phase of file coin verification because as I said it is very very

important to make sure that indeed whoever is the pro here indeed whoever is storing the data they actually have the data at any time so proof of replication comes exactly at this point um and it has to guarantee that data is stored and readily available uh to be retrieved okay and our focus in this talk is in this part of um file coin uh verification in systems like file coin where you would imagine that you would have um a very large number of participants there are certain um uh properties there are certain efficiency um requirements uh that um one uh one needs in order for the system to to work practically the first one is what we

call laconic challenges so remember that I said before that there is this sort of auditing phase that we want to make sure that the server is storing the data and as I was showing you before in this interactive protocol there is some sort of challenge that comes from a user to the approver so ideally we want this challenges to be very very short and ideally of constant size the second property that we aim for is to have both the prover and the verifier to run in time sublinear to the number of files that are being stored and finally we also want to have a robust space Gap and remember this the space Gap is the tightness of the proof that I mentioned before and ideally we want to have like an as secure protocol as possible so these are the the three parameters the three requirements that uh we are trying

to optimize when we're building large scale proofs of retrievability so there has been a lot of work uh in all all these types of um of different proofs proof of space and so on I'm not listing all these works you can refer to our paper there are like dozens of them uh but I want to refer a little bit to um this work on proof replication uh by Ben fit from 2018 which is the one that is the most relevant to our work and it is the one that we are kind of comparing um directly the idea here is this setup phase uh the verifier the user they're going to send um data to the prover and uh the Prov is going to perform some pre-processing on this data and uh

commit to them in this particular work of um of 18 and of many other uh previous works on proof of replication what happens is that the prover is going to build some sort of graph structure over the data that they are uh building that they are storing um and they're going to we call this the encoding phase where they're going to encode the the files the data um through a graph C and the goal would be to do it in a way so that they can later convince the verifier that they are holding the data and uh they uh they have they have also like dedicated a certain amount of mem so in the audit phase of such protocols the important part to notice is that the

verifier is going to challenge the prover on a subset of the nodes of the graph so the challenge here is not a single challenge but it is a challenge that consists of many little pieces and the approval will uh return back proofs the tightness of the proof here it will really depend on how large the challenge is okay so the more challenges uh you give to the approver the higher are the chances that theover is not sitting here so the auditing phase as I just said it is probabilistic and a large set of challenges is going to be needed for a good level of security so what we're trying to to do in this work is uh to come up with a proof of um replication protocol that we have this audit phase

that will allow the uh verifier to support to send a single Challenge and with a single challenge we want to make sure in a deterministic way that the Prov is holding all the data okay so we're trying to get from like multiple challenges to a single Challenge and at the same time get like uh a very high level of of security so as opposed to using these special types of graphs our technique is going to be based on uh polinomial EV evaluation all right so let's um let's see how we do it and um I'm going to start with um getting a little bit more formal and uh defining first um how we uh describe uh proof of replication we define proof of

replication as a set of five algorithms so first we have a setup algorithm it takes as input different parameters that they're going to become apparent a little bit later they have to do with the they have to do with uh uh the time of the uh of the prover and and the memory that the pro uses this setup algorithm is going to Output three public Keys an encoding key a public key and a verification key and notice here that there are no secret keys so the scheme is uh completely trapless then there is this algorithm that we call the encode algorithm that will take as input the message or the data uh it will take the encoding key and uh some identifier ID you can think of it as being some

sort of ass salt okay and the reason that you want that is to be able to have different encodings even if you uh encode the same piece of data so this encoding algorithm will output an encoding and some digest AIDS and this digest AIDS is going to be published so this is the pre-processing phase and then we have the audit phase and in the audit phase we essentially need uh a prove algorithm that uh using the encoding and um The Proving public key and um a challenge it will output a proof together with a proof algorithm we also a verification algorithm which having as input the verification key the public digest AIDS and the proof will output accept or

reject finally we also have a decode algorithm that using the encoding and the um encoding key then coding C and then coding key it can uh return back the original message okay you can think of this as some sort of like decryption algorithm so the security properties that we want here are going to be en coding correctness uh proof complet Fitness and also replication and extraction and I'm going to focus on replication and extraction because these are the kind of more you know non-standard properties here remember that the goal of our work is going to be to reduce the complexity of this phase right so remember what I said before about how we compare with um the work by Ben Fe we are trying to make sure that when you're proving when you're being

audited you can just do it with a single challenge for the full set of um of data so let me start by defining replication which is I think the most interesting property informally uh the replication property should guarantee that the amount of memory that the prover is using has to be specific in order to be able to produce uh proofs that verify so let me explain that more formally so we're going to Define this by a security game and assume that we have a challenger that first runs the setup algorithm and then um we give all the public keys to an adversary and the adversary is going to select a set of messages okay so this is the messages

the data that you want to uh to encode then we're going to run the encode algorithm and notice here that the encode algorithm is run honestly and I'll keep that in your mind and I'll get back to it uh soon in order to run then code algorithm we are going to pick this random identifiers and again recall that these are these identifiers they can just be viewed as some sort of salt here and um we're going to encode the ch is going to encode all the messages that the adversary selected and output the encodings and the digest for each one of them then all these encodings and encodings and digest along the IDS are going to be given uh to the adversary and the adversary is going to Output

some value Alpha that is basically the adversarial memory that the adversary is trying to to create here we're going to sble a challenge from The Challenge space recall again that we have a single challenge here and uh we're going to give now the challenge to the adversary and the goal for this adversary by only having access now at this special value Alpha that created in the previous step would be to Output a bunch of proofs that are going to be accepted all of them are going to be verified verifying and we are going to say that this adversary breaks replication of the system wins this game if it manages to produce such accepting proofs while using some piece of information this

Alpha the size of Which is less than n where again remember that n is the amount of memory that you would need in order to store all these files um M M1 to Mu something to also mention here is that in certain settings the messages that you're trying to to encode in these systems might be messages that are naturally very easy to compress think for example that you might have to store a sequence of messages that are basically evaluations of a prf on some counter or something like this right in that case you could have a prover that basically avoids to store the data and just uh generates the data

on the fly when they're asked to create a proof that's the reason that uh for this kind of protocols we are going to need an encode algorithm that is going to be slow okay that has to be forced to be slow and uh at the same time it has to be the case that the running time of the adversary that creates the proofs is less than the time that this encode algorithm runs okay because again otherwise you could have the adversary running then coding all over again okay and we're going to see how we we got this so question so what why is it bad if you had someone storing a compressed version if it was highly compressible data like as long as you a user can

retrieve it so um exactly because this proofs of replication they want to combine the property of proof of space as well you want to maintain the property that you are dedicating a certain amount of space right but I guess my question is why right if I can if I can get the data why why do I I mean I I definitely get the fact you don't want to just like pass through the query to someone else so I get the idea that you want decentralization you want replicated storage like if I had like 10,000 people all storing at locally compressed I think Joe you have a good answer to that so Tim I think compressibility can vary from person to person so there's an attack on these schemes where you upload some giant file that you know the prf key that generated it so you can you can store it very

succinctly but everybody else can't and then well then you're sort of like possibly making other people store more data than you are so I'm just trying to so like you just thinking about some malicious user who that was like the original concern I think when we were looking at this like years ago it's just that like you would have some secret compression key that would sort of like let you compress the data but not anybody else and then you could sort of get credit for what seems like you're storing a lot of data so the the way that I think about it is that because they're using this in this like proof of space based consensus

algorithms they do want to make sure that validators are dedicating a certain amount of storage and between different validators maybe some of them are getting files that are compressible and some others are getting files that they're not compressible but they want to make sure that all the validators are um saving the same amount of space so they really want to enforce that this is what is being stored so it's really important I mean so this is really optimized for like civil resistance and consensus as opposed to just like data availability of corre rollup dator like that yeah so so we should be thinking of this as really you know like how to improve file coing potentially yeah okay another Point here and uh this is something that it's um U different uh

from the work of uh of Fe is that if you notice our security game you're going to see that the we don't let the adversary run the end code algorithm we actually run the en code algorith honestly this is U different from from pH 18 because there they actually assume a malicious and code um however just to make Justin happy as well this could be uh resolved by adding a snark um along with the output of the code to make sure that the en code was run correctly but nevertheless the focus on of our work is not to improve the encoding phase but to improve the audit phase okay so even if this requires a snark at the time of encoding we don't consider this a problem we are fine with having a more costly pre-processing phase because

we're really trying to optimize the audit phase but definitionally this is a difference from uh prior definitions so remember that before I also said that memory uh the memory Gap is important in this in these proofs and again we Define the memory Gap as the distance between the space that you would need to store all the files all the messages and the replication parameter n so this memory that you would have to hold here the smaller the Gap the better is the robustness of the uh of the proof of replication system okay so uh basically if an adversary wants to pass the verification with non- negligible probability then it will have to be it will it will be be forced to spend memory to dedicate memory that is very

very close to the actual memory that it would take to store all this files actually yeah so the second property um that I'm going to Define is that of extraction it's not a very fancy Pro uh property it's you know the typical extraction property that you would see in such proofs and it basically says that all messages are going to be retrievable when aover who holds the encodings produces um valid uh proofs so again we Define this through a security game we have a setup algorithm outputs all the keys we have an adversary that is going to um select the files we are going to run the encode algorithm exactly as before we're going to give the digest and the encodings of all the files uh to the adversary the

adversary is going to try to compress them or like put them in some sort of um data structure Alpha and now we Define the existence of an extractor that will have Oracle access to this A3 that is producing the proofs and uh what we want to make sure is that such an extractor exists and if it manages to get valid proofs from this um adversary A3 by only providing challenges to this adversary then the extractor will be able to extract the messages that were encoded in the encodings okay so these messages should uh should be the same as the original ones so the extractability properties is you know more of a uh

needed property for like the the proofs of these systems so let's talk a little bit about our construction and let me start by um quickly going over some of the basic building blocks uh that we use here and um the first building block uh that we utilize is that of memory hard functions again in a very high level uh you can think of a memory hard function as a deterministic function that takes an input and evaluates it an input X and evaluates it into an output y uh and the special thing about these functions is that these functions take a long time to run even if you try to um parallelize the process they do require a certain amount of memory to be dedicated in order to um to evaluate the

there have been multiple uh proposals of constructions of memory hard functions and um again the security property here is what we call input dependent and potentially multi- instance as well pre-processing so multiple input evaluations are completely independent and uh pre-processing does not really help okay so uh it doesn't matter if you have done any sort of like pre-processing here whenever you have to evaluate a new input uh that should be completely independent from anything else that you did in the past the second building block that we're going to use here is that of polinomial evaluation and um the observation here for our construction is that basically what we're going to do is to encode the files

the messages that we want to uh to store uh in the form of a polinomial okay so I'm going to uh Define a polinomial f um of degree D that is going to be sampled randomly from a field z uh of order P the idea is going to be like in when we're talking about polinomial evaluation the idea is that uh the verifier is going to be sending some um inputs to the prover and the prover is going to be evaluating the polinomial in this image remember though that uh an important property here is that we want to make sure that the server is really storing is really dedicating a certain amount of memory here so it is um important to understand how much memory

if we assume that there is a way and I haven't shown you how yet if we assume that there is a way to represent the data as a polinomial we have to make sure that the server is really dedicating the right amount of space here the round amount of memory story The observation here is that there is this result about incompressibility of Random pols so again assuming that we have a polinomial that is randomly sbled the the property that we want here is that in order to evaluate this polinomial you should require memory close to the size of the polinomial if you have an adversary that tries to pre-process the polinomial and compute A Memory Alpha this data structure Alpha that is smaller to the size of the polinomial it shouldn't be able for this

adversary to evaluate this polinomial on random points okay just by using this uh this Alpha data structure unless again this data structure is of size similar to the polinomial so also I'm going to denote the size of the polinomial as the degree of the polinomial time P where P again was the order of the of the field so luckily we have a result an existing result on this by at all from pkc 23 which basically says that for random polinomial it shows that the amount of memory that you would need in order to be able to evaluate the polinomial in random points is is actually pretty close to F ofx it is actually D * P minus D * the size of Q where Q is the

subset from which the valuation points are being sbled how how do you prove this result it's a completely different work and I'm happy to talk to you about it offline but it's like an existing result it's not something that we did in this work uhhuh and is this prior work also in the same context or different context um it's not about proofs of retrievability uh it's literally about uh incompressibility of uh of Random pooms so um just to give you one more hint about how this works basically they reduce uh this result to incompressibility of random strings um using some color of uh analysis but again it's we're using this as a fact we have to do the only

difference in our work is that we had to do like a small tweak uh just for the parameters but uh it's not a new result so again the observation here is that what I want you to uh to keep is that as long as these pols that we're going to use to represent our files are random they're not going to be compressible so let's get now a little bit more U specific on how the encoding phase is going to work for our system and again remember that this encoding algorithm is going to take as input the messages the files that you want to encode a key and this random identifier and is going to produce an encoding uh and the dig for now let's just assume that we're trying to encode a single file a single message and let me take this message M and break

it into smaller blocks and um I'm breaking my message into uh D blocks okay and every the size of every message is of size P where again remember p is the order uh of the field from which you assemble um the the polinomial what we're going to do is that we're going to combine this random identifier along with the message in order to derive the polinomial that will appear like it was randomly sbled from zp so first we're going to use the memory hard function and we're going to run it over the random IDs which as I said before we can use them we can sble them from a random beon okay so this is going to give us this first value V and

then we are going to compute the polinomial by Hing this value V with the ID where a you can assume that is a random Oracle and you're going to exort this with every block of the message so in a sense you can think that every block of the message is going to be roughly a coefficient of the polinomial okay so a note here about um age about the the random Oracle um the reason that we model this as a random Oracle is because it allows our construction to be a little bit more modular it doesn't um require any specifics from the underlying memory hard hard function but if open up the box here uh a little bit you might be

able to avoid the use for a random Oracle as long as the memory hard function has certain properties okay but it's much easier to think about it in a more modular way assuming that this is a a random here what's the point of the memory hard function if you can lost on that so the the point of the memory hard function here is to ensure that the encoding is slow but I mean memory hard is not slow right it's memory hard like it might be fast if you well uh by slow here I guess dedicating certain memory I see but why would you want that in your encoding process so um this is going to become a little bit more apparent as we look into more uh into more details um trying to

see what's the easy answer I can give sorry I'm getting you you you get like your memory usage is at least you know depth robustness of the memory hard thing plus like degree right something like that I'm sorry I didn't sorry like you're like you know you have the gap between the amount of memory you need and the amount of memory you want to store them with depth robustness of the memory hard functional whatever right underlying or whatever you have like right that's like some minimum guarantee plus like the degree because you have this result like you need at least D minus this and so you want it to be at least some threshold and you yeah okay if you want it to be slow why isn't it a vdf instead of a memory heart function it seems like that's the

specific thing for slow um would the vdf also have uh specific requirements on the um memory side no but I guess like like I I maybe I'm confused like does the memory requirement here come from the memory hard function or from storing all these kind of like random from like the proof of space part yeah so I I don't know we have to think about that repl in this with a vdf seems like you need memory to store the polom right right so and you cannot compress that yeah and then if you want slow like a BDF that's its whole job is to be slow whereas memory

hard is like is sort of slow but that's just like a byproduct like what it's really trying to do yeah that's a fair point I I can I can think about it yeah back to the encoding this is basically how we represent the messages as a polinomial and that's that's the output of of thing coding we're not done yet but let's try to see how uh how things are standing right now so we have the server that received all this uh data I'm not showing that in the picture and in this pre-processing phase the server is going to uh prepare one polinomial per message so here in the previous slide I was just showing the process for a single message but now assume that you're doing that for multiple messages okay so you have a different polinomial

for each methods and now our goal will be to design an audit pH case where the verifier will send a single challenge a single random point and the prover will evaluate all these different polinomial on the same random Point okay so this is what is going to give us a single challenge as opposed to having multiple challenges here so what have you done so far so we can get a single Challenge from the verifier and still getting all these evaluations on all these different polinomial be sure that the prover is storing all the data and we have also enforced the use of space uh by um

making sure that the polinomial are not compressible what we haven't done yet is we haven't achieved sublinear proving time we haven't explained how proof is going to work and also we haven't talked at all about how the the verifier is going to verify that indeed the evaluations that he receives are correct okay so let's try to uh answer those two questions as well so let's get first into the sublinear proving time there have been multiple works that focus on how to uh speed up um the evaluation of polinomial but um the one that we're actually going to uh to use here is a very cute result that it's um like more than 10 10 years old by klia and Uma uh on Fast po nomial factorization and

modular composition so the nice thing about this work is that it uses a ram structure in order to experti polinomial evaluations and uh by doing that it will achieve it does achieve the uh evaluation of the polinomial to happen in po logarithmic time in the degree of the polinomial B uh so the way again I'm not going to get into too many details because this is like uh not work that we have done here but uh it has two algorithms it has this algorithm that generates data structure that gets us input the polinomial and creates data structure D and then evaluates the polinomial in random points random point x by just using this data

structure so again a very very high level it is going to leverage Ram access to this data structure D in order to only access the blocks from D that are going to be relevant to evaluate the polinomial it does come with a caveat though and I want to convince you that this caveat is not a big problem for us okay so the caveat in this work is that the size of this data structur that it requires in order to then speed up the valuation of the polinomial basically expands the size that um the polinomial has okay so it has this like memory expansion problem uh it uh actually expands enlarges the memory by a factor gamma on top of the size of the

polinomial okay so the trade of here is that we're going to get faster evaluation with a single challenge but our provs will have to dedicate more memory so this gamma um can be um defined in terms of the degree of the polinomial and um the order p and some constant Factor Delta so the smaller this constant Factor Delta is here the smaller is going to be this data structure the smaller is going to the slower is going to be the valuation and what it was shown in this prior work is that any Delta that is greater than one is actually going to suff to be sufficient uh to achieve poly log evaluation I should also highlight at this point

that um trying to come up with concretes for this work it's you know it's going to look pretty ugly so the the main contribution of this work is mostly of theoretical interest so the uh the advantages are going to be on an asymptotic level okay so playing with constants here it's not it's not easy all right so having that result so intuitively is that just saying it's like a way to store the polinomial redundantly to speed up exactly exactly and then access on only certain parts of the memory in order to evaluate it and that's why you can get evaluation in po logarithm and are they coming more from like a complexity Theory motivation or yeah it's it's not easy to explain

actually okay yeah I um and not umans it really feels like a Chris um's result you know what I mean but yeah okay so it's it's a result that I I didn't know about uh I I don't know how I I have a feeling that it's a result that it's not being heavily used in because it's it's very it's a it's very complicated it's very complicated too it's it's a lot of ch remaindering right but also like it's not clear to me if you ask me about you know we had this uh discussion on the rebattle of the paper if you ask me about the the concretes of this work it would be very hard to answer but is the kind of thing where it's not even clear that in principle you should be able to do that right so yeah that's right it seems kind of cool even just to right

but again like in this setting where you don't really try to optimize this processing phase and how much memory you really actually want the users to be storing lots of memory it's not a big deal you could also just store the whole table of field evaluations right but uh it's too big but it's too big but but we're going to yeah but then um as I'm going to say in a couple of slides uh this will also help the to get a poog verification time and if you store the whole table this might be a little bit utilizing this result can also give us some linear proving time so the the last thing to resolve here is how can we also run verification in sublinear time and we also want to do

that in po logarithm time so the observation here the first you know attempt that again would make Justin happy would be uh to Let's uh assume that we we're just going to use snarks so whenever the prover evaluates the polinomial using this special data structure it can also attach a proof and say hey that's why the evaluation is correct but again the problem here is that the pro time will become linear to D okay to the size of D and that's something that we don't want here again we want to uh to uh have sublinear uh verification uh sorry we we we're trying so hard to have sublinear proving time so now we're going to uh increase that again our trick here was to basically have the verifier also compute evaluate

the polinomial locally in the same way that the prover is going to do it okay so how do we do that of course the verifier does not have access to this whole data to D and we don't want it to have access but remember that we said that in order for the prover to evaluate the polinomial it will only need to perform Ram access to a to particular blocks of this data structure okay so how about we just provide this blocks which are going to be a PO logarithmic um number to the verifier so the way that we're going to do that is by building a Merle Tree on top of these uh blocks of the data structure and then when the prover evaluates the uh the polinomial is going to uh give the valuation again I'm doing this for a

single point but for a single file you could be doing that for multiple files you're also going to send the digest um the the root of the tree the blocks the subset of the blocks that you use for the valuation and the meral tree proves that they belong to the to the digest of the tree okay and this part you can actually think of it as happening during the pre-processing phase okay so now the ifier would just have to check proofs the mer three proofs and then it would have to reevaluate the polinomial and check if the values that it got from the from the pro are the same ones that it locally computes and this way you can also achieve Pol logarithmic verification here how much

memory was it to compute the pols CU the verifier will have to have that much memory right it's Pol logarithmic to the size of the or even the memory was small which which memory oh like you said that like the algorithm which runs in poly log time yes the memory that it uses was larger right yes D is the so the memory that the Prov needs is d uh and D is slightly well it has an expansion Factor over the size of the polinomial so it's larger than the polinomial so to recap how the scheme Works uh we do have this um encoding or pre-processing phase first uh we are going to prepare one polinomial per

methods per file this is going to be our encoding um then using this special data we're going to generate the special data structure for each one of the polinomial we're going to build a Merle Tree on top of each one of them and this is going to be our digest potentially we're going to also give snarks here that things were well formed if we actually care about um honest encoding um uh if if we care about malicious encoding execution we're going to publish the digest potentially the proofs if we need them so and then the nice thing about the audit phase is that we can do it with a single challenge it's going to take po logarithmic time on both the prover and the verifier side uh quick question is GI is it evaluation of some related pols is it kind of which di di yeah di is

this special uh RAM based data structure that you're going to compute um on top of the polinomial in order to be able to do the uh quick evaluation and if you use like something like polinomial commitments instead of Merle trees here do you think we can go around generic snarks and use something like targeted yeah you could potentially the focus here was not so much and try to optimize anything on the pre-processing phase basically the tradeoff that we're trying to solve is you know we're willing to increase the amount of memory that theover is um devoting we are willing to have a more expensive and a slower pre-processing time at the cost of having a verification like an auditing phase that

is more challenging because if you think about it this whole pre-processing happens once yeah but this like auditing phase happens all the time so I think in file coin uh if I'm not mistaken it happens about like 10 times a day so you audit this valid datas about 10 times a day um and um you want to be able to audit in a way that the auditing is not really probabilistic here right so you with a single challenge you're just auditing the whole structure the whole data structure of the the whole memory of the of the appr one thing you can say about the polinomial commitment suggestion is the committer here is honest um it's the pre-processing so this is like a really nice Pol normal

commitment scheme if the committer is on probably right can't do better than this would be my gue right right but but if if the poomer was not honest then you know you can start thinking about better ways to resolve this this problem and again as a comparison the work by Ben fees it does not it assumes a malicious committer and you know that's that's an important difference um all right so um let me conclude by giving you a comparison and ASM totic comparison with um the work by Ben Fe so this is the work by Ben Fe and this is our main construction the main things that I want you to notice is that we we're fixing this to be the same so in a sense you can think of those two columns as being the level of security offered

by both schemes and under the same level of security uh the advantage of our scheme is that the number of challenges that you need is constant as opposed to having challenges that depend you here is the total number of files that are being stored so you have a single challenge as oppos something that depends on the number of files being stored the run time for The prover and the verifier is um Pol logarithmic on the degree of the polinomial or else the blocks the number of blocks that every file contains as opposed to U Square log D and uh the caveat here what we're paying here is the fact that the memory expansion of the prover the amount of

data that the prover needs to store is going to be quite larger in our case so again it is a tradeoff um and uh it it you know it really depends on how fast auditing you want to get here and um how whether you want auditing to be like um on the full set or you're happy to just be auditing certain parts of the of the St to do you ever think about or did you compare to like a sort of a wrapped version of Ben protocol where you still have like end challenges but then you compress them all with some generic snark scheme uh we haven't compared we haven't tried to do a comparison this way um it's not clear to me whether this

asymptotically would be any better well I mean you could keep the like the simple the simpler setup an expansion of the the fish steam um but then you wouldn't have to actually post all the challenges and responses on chain you could just sort of commit to them which you could do quickly and then even if it takes you a while you could come up with a proof within some time that says that they're all correct so you could get I guess I'm just thinking like time it's not clear to me that the the proving and verification time would actually be polog here if you do something like that would be better I I I think it wouldn't be better if you try to do something like this I mean it could be pretty fast

if you did like 16 you know you could you could prove that all the challenges are correct potentially like very for like the the full set yeah yeah it's it's it's not it's it's not clear to me I'm again happy to discuss this more I guess the reason I thought of it is at the time then was designing that protocol I think like I mean this idea of only having like one challenge or constant number of challenges wasn't really wasn't something we thought about um but pretty interesting but I wonder if there's yeah like a another way to get there yeah I'm happy to to talk about it if you know you think there are better ways well just a different way I don't know yeah yeah I mean I should also probably say that uh file con uses

something much simpler than than all these it just uses like Merle trees and I think snarks now as well um but it's interesting because we started this project in collaboration with their team and um they seem to be very interested uh about how you could possibly do something like this just with like a single Challenge and have this kind of of deterministic uh audit phase but again like trying to actually make like the parameters practical here it's it's a nightmare so it's mostly of like theoretical interest as a result yeah does things change if you do multivariate pols we are actually using multivariate pols so I mean I'm putting multiple things under the carpet but we

yeah yeah um and are the security proofs are they straightforwards or straight um because exactly because we build the scheme as like a completely modular system so we don't need like any extra assumptions we just need like you know security of all the underlying Primitives that we're using but in a completely blackbox way so if I gave you a practical polinomial valuation with small overhead yeah then maybe maybe this would become uh yeah so that's the main source of why you say it's theoretical yeah okay yeah but I I I I don't think that's an easy thing to do I think this algorithm played a role in some important P results recently too so it seems to

be useful in cryptography maybe broadly but seems totally impractical or at least not not good off distur The Gauntlet we know it's possible in principle can you have a practical version of that interesting yeah I mean when again I didn't know about this result by and um um forgetting the first author now so when I saw it was actually pretty pretty impressed that you can do that so efficiently have you thought about the the model where the there's like a private encoding um um so there's like the model where I encode the file and upload it and then I want to audit that it's being stored

later which is usually much simpler mhm um I guess I haven't seen this idea of like constant size number of challenges I don't know how that so if you have a private and cod would that like compose well with this like block consensus kind of thing uh usually not use for other applications right but I was just wondering cuz it's it's kind of like the two modes for proofs of replication is like public encoding and private encoding yeah I mean we had the setting of like you know consensus here uh but yeah this this might be interesting as well I mean yeah it should be strictly easier cuz you can always use repic coding steem

right but sometimes you can do much better all right thank guys