ZK10: Applications of Zero -Knowledge Proofs for Data-Parallel Computation -Ismael Hishon-Rezaizadeh

Transcript

foreign [Music] okay so next up we have Ismail from Lagrange labs speaking on applications of zero knowledge proofs and for data parallel computation simple topic there should be a mic up there yeah thank you very much okay so good to meet you everyone my name is Ismail I'm the founder of LaGrange labs So today we're going to discuss a new Vector commitment scheme that our team brought forward at Stanford blockchain conference this year Rec proofs what makes Rec proof special well it's a vector commitment designed for

concurrently proving batched set inclusion and dynamic mapreduce style computation over the subset that is proven that is updatable in logarithmic time so to understand why this is relevant let's take a step back to First principles a Merkle tree a simple commitment to an ordered sequence of values created through concatenation and recursive hashing of adjacent values likely a review here for everyone a membership proof in a Merkle tree has a path size proportional to the logarithm of the set size and it can be updated as such in logarithmic time when an element in the set changes

now what about a batch proof we can think of a batch proof as a single proof that opens K arbitrary elements in a set simultaneously the naive approach is through a concatenation and hashing of adjacent values um and the batch proof has a smaller proof size and can be but can't be updated in logarithmic time it requires a recomputation from scratch which means you save on aggregation time at the cost of updates and this is where Rec proofs come in and we're going to be making this very concrete with applications in the

blockchain context very soon but what a wreck proof is is a batch proof that can support both set inclusion and dynamic data parallel computation that is updatable in contrast to the naive approaches the batch proofs so how do we do this well the technique that our team has brought forward is something called canonical hashing and so with canonical hashing which can be supported in any snark that supports recursion or embodiment of the abstraction of recursion such as folding every Branch proves the sub tree rooted at that position and it proves the inclusion of that subtree and in a general context computation in the

mapreduce style over that subtree and so as such when an element and a subset that is proven changes or an element in the set changes all you have to do is to update each of the proofs that has had the subtree change and what this enables is a very extensible primitive that can be supported in any snark construction that has recursion or an embodiment abstraction recursion such as folding that can be updated when you change some component of the data set that a computation is run on as long as that data set in that computation is done

data parallel and so why this is applicable in the blockchain context is because blockchains are fundamentally append only data structures and they have naturally very low entropy of storage state so between Block B and B plus one the only mutation to the storage state is from the execution and transactions contained in B plus one so any computation over a subset of storage state that you want to update for the incremental block doesn't necessitate a full update of the computation from scratch and so to take a step back let's define state of a blockchain simply and broadly

as the result of the execution of all transactions from Genesis to a given point [Music] and as such we can define a storage proof for a membership proof or whatever you want to call it as a simple inclusion proof for a given block of some Leaf element through hashing the adjacent elements and asserting the path [Music] and so this is supported in almost every snark framework or DSL but what about a batch proof what if I want to do something very expressive with the underlying data of a chain I for example want to compute volatility from let's say Block B minus K to Block

B over a ring buffer of size K I need to do two inclusion proofs per block and I need to do that K times and then I want to aggregate the path and compute over it great I constructed a large proof but in 12 seconds this is ethereum state the the blockchain changes a new block is added and as such the naive batch proof that I constructed with the computation is no longer valid with respect to Block B plus one so what I would have to do is to put an amount of work into computation in this case in the naive approach that is proportional to the batch size okay and that obviously is untenable

because this structure can be updated in log n then why can't my computation be updated in log n and this is where Rec proofs are highly applicable for large computation spanning multiple blocks you're able to have that computation updatable in logarithmic time so in this case we would take the proof of the computation validity from Block B minus K to B and I would update it to now be valid with respect to the data contained in B minus K plus 1 all the way up to B plus one and this amount of work is only proportional to the update not proportional to the overall size of K and so in short update your proofs don't recompute them from scratch if the majority of data within that proof does

not change [Music] and so looking at Rec proofs versus the field and making it very concrete why these are more performant so Rec proofs compared to Merkel snarks and naive approaches has an update speed of 135 times faster from our early benchmarks compared to recomputation though I expect this to be much higher in the next presentation Rec proofs are embarrassingly parallel which means that we can distribute these as as efficiently as we want to and we're able to massively improve the efficiency of the computation and secondly the verification thirdly the verification time compared to naive approaches is far lower and so to look at a few examples of why this type of computation is very well

suited for blockchain data let's look at the simple example to start with of a full storage Quarry I want to run some query over the contract state for a given contract from another contract I want to say I'm going to query an nft contract to determine nfts matching a certain property for my other GameFly contract right now you would have to iterate through the entirety of storage either on the VM or in a snark for the current the current instantiation of that storage value the storage values with this approach you can build a batch proof over that structure and then continually compute over that while updating the underlying inclusion proofs on a block by block basis and this is extensible as well to other

core Primitives that are foundational to the infrastructure of DK applications so if you need to compute frequently over a certain subset of memory what you can do with Rec proofs is basically do an ETL job on it you can extract the subset of memory that you want in a rep proof you can transform it into a new data structure and then you can load it into a new VM so what this basically creates is a is a configurable mechanism for ZK based ETL and we can think of other extensions of this for example as something like verifiable reward issuance over a large longitudinal computation of on-chain transaction storage or receipt tree

state or you can think about this in the context of wanting to aggregate BLS Keys a historically linear time operation with respect to subset signer size that can now be done with a one-time setup and then incremental updates and so in summary if anyone here wants to learn more about Rec proofs or some of the work that our team at LaGrange Labs is doing I have a QR code up here which will take you to our paper and so thank you everyone [Music] yes thank you