ZK13: GIGA Protocol: Unlocking Trustless Parallel Computation in Blockchains through SNARKs

Transcript

[Music] Okay. Hello everybody and today I'm going to present uh the Giga protocol and how to break the blockchain sequential barrier uh with trustless parallel execution. So let's start from a first consideration. Today the words operates in a completely distributed and parallel way. There are tens of million of servers that are processing the today's uh work computation completely in parallel. And what about blockchain? On blockchain, every single

actor needs to process the whole chain workload. And most of the chains cannot even process the transactions on separate threads. they have to process them sequentially one after the other one and the block propagation also even requires re-execution. So now let's imagine if a single server has to process all web two computation. One minute of web two computation would take 100 years to be processed on chain and every minute will increase a 100 year

queue. So definitely we are quite far for supporting web two computation. Okay, you can say okay what about L2s? L2s has the same issue. You can you can think about for example u L2s on on Ethereum. You have to process transactions sequentially also there and also there a single actor must have the computational power to process the whole L2 throughput and the cross uh communication uh between L2s has to be a synchronous and this is very detrimental to user experience.

So with all these constraints uh the overall system ends up in a very fragmented scenario of centralized uh subsystems. Okay. So what is needed to unlock the throughput but at the same time keep the centralization. Okay. First of all, we need to avoid requiring a single entity having to process the whole chain workload and also you have to limit the transaction sequential execution uh only in the case it is needed and when it is needed that two transaction are executed sequentially when they are going to touch the same part of the state. For

example, two transaction that are spending the same balance. And so in order to be sure that there is enough balance, you have to to uh let me say process them sequentially. And this is valid also for smart contracts and other kind of executions. And also we need to remove the need of re-execution uh by validators and all the other nodes. Okay. How we solve this? So for what regards the um the need of requiring a single entity to process the whole chain workload uh instead of having this entity processing the chain workload, we delegate the execution to the centralized doctors and we can

trustlessly reuse the computation results because we are using snarks. So how can you really delegate the computation to someone else and trustlessly accept the result by proving it? So we delegate the execution and then they do the execution and they prove it the results. And for what regards the limit of uh transaction sequential execution by being aware of possible state conflicts uh in advance we can and we can let's say organize uh the transaction execution in parallel. So if you know in

advance what are the part of the state the transaction are touching you're able to understand uh what is conflicting and then organizing the par uh the execution in parallel and for what regards the the removal of the need of re-execution you can uh reuse u the aggregation computation proofs um the the proof sorry um for validating the state changes and then aggregate them into a single proof. So what are the main principles? So first transactions declares the part of the state they read and

write. Then block producers no longer execute any transaction. The comput the block producer do not execute the computation of of the transaction and the smart contracts. They just coordinate their execution and the non-conlicting transaction has to be executed in parallel and the execution is done by decentralized actors and the execution results are proving proven using a ZKVM and this ensures uh a trustless correctness and then the proofs are

recursively aggregated into a single block proof that validates all the state changes. Okay. Now let's see how we model the ledger uh in order to enable an efficient parallel execution because also the the ledger model uh has an impact on how much you can parallelize. Okay. First here we can see uh we have three different entities the smart contract the and two users. Okay. The state is structured in a non-monolytic way uh in order to maximize transaction isolation

and we will see later uh what does it mean? And so the state is composed by accounts and each account contains substates that are other portion of the state and the substates are specific data that is owned by an application but it's related to another account. So we can see the user array that have two substates and one of these substates has an owner that is the the smart contract application and the substate can be modified only by the owning application.

So for example the user array with substate two that is owned by s uh uh by the smart contract this part this substate can be modified only by that smart contract. And now let's take as an example the tator smart contract. So for example on Ethereum you will see the smart contract state um of of a t smart contract having uh a whole list of of pairs of um public keys and balances. So like a monolithic state of the smart contract.

Instead with this approach we are splitting let me say these these uh these pairs or the public key and balance um between the the users. So the the pair public key and balance is stored within the user account and in a substate that is owned by the tater account. Why we are doing this? because we can identify let me say uh more specifically which accounts which part of the state are touched. If we are not doing this, we will be able just to identify let me say all operation that are uh related to

the tet smart contract by using just the tater uh account. Instead now we are able to if two users are interact inter interacting with the tetas smart contract um the part of the state that they are touching are different because they are moving let me say different part of the state and so now the transaction uh we can see that transactions specify which accounts they read and write uh to identify the possible state conflicts and so uh in this case who users uh will specify their that are interacting with the tether smart contract. They will

specify their own account and not the tater account. In such a way the system can know in advance if these two transactions are in conflict or not. And so by uh knowing which accounts are read and written um the execution can be organized in parallel and um um and the the kind of of transactions that are not uh let me say uh that are in conflict will be grouped for sequential [Music] execution. Okay. Now that we saw how the ledger model is is um structured, now we

can see how the block generation scheme uh is structured in order to enable trustless parallel execution. So here we can see a block producer with his own mele of full of transaction and each transaction is declaring which part of the state is touching or better what what is the list of accounts that is writing and reading but the block producer as we were saying before doesn't execute any transaction. What it does, the block producer organize these transactions into non-conlicting batches and assigns them to the

centralized batch provers. So for example the batch prover one will have a set of transactions that let me say are writing accounts and such accounts cannot be written by the other batches and in parallel each batch prover executes natively it's assigned transactions and this execution needs to be sequential because there could there can the potential conflicts because I mean the idea is to uh assign to a specific package prover transaction that are in that that are potentially in conflict and so but now the sequential

execution is only within the batch and now you can have several batches and several batch provers that are even doing the execution in parallel and you're not anymore bound to a single actor to execute all the thing all everything in in sequentially and limiting the throughput. You can see a batch prover like let me say a single chain somehow and so in such a way you are unlocking the the parallel execution and okay one detail here the native execution or better the transa

the onchain logic here when is executed is interacting not with the with a whole state but with a state view that is a sort of a subset of the whole state and um when the native execution happen uh these state views are transitioned. So what do I mean by applying a transaction of transaction one the transaction one when uh affects the state in reality it affects the state view and after the execution of transaction one you have let me say a modified state view and this modified state view is the start

state view of the next transaction. So for example, let's imagine that transaction one is spending some balance is decreasing some balance. The state view of the uh start state view of the next transaction will have the modified balance and these ensure that the modifications are uh let me say coherent and uh there is no double spend for example. And so now that we have a start state view for each transaction and an end state view for each transaction, we are able to even parallelize within the batch the proving because every um let me say every transaction has a starting point

that is well known and is compatible with the end state of the previous one. So we can prove in parallel within the batch. And so for example here in the batch prover one we we have the three transaction with the uh the start state view the end state view for each transaction and and then the uh relative proof and how we are proving it uh the execution uh with a zkmn. Okay, now that we have for each transaction within the batch uh a proof, we can aggregate this proof and we can forget about the intermediate

state views because they are let me say adent. And so we can end up with a unique proof that proves the state transition of the state view from the first one to the last one. And so in the last state view of a batch we have all the modified values uh that let me say were caused or all the modifications that were caused by the execution of all the transaction in that batch. So we have all the modifications proven now and but and all of these is happening in parallel uh between all the batch provers and now that we have the proof about the state changes. Now we can

apply these state changes to the global state. So you can imagine having a global state of the chain and we are applying all the state changes all these state changes to the global state. And so uh we can uh derive a final proof that proves this the transition of uh from the global from the start global state to an end global state. And so um yeah and we can reuse this proof or better we can uh create a block finally uh that is containing the aggregated proof of all the state changes and the state changes itself and

this and the block then can be broadcasted to the network and there is no need of re-execution because all the state modifications are proven and were proven in parallel and were proven written by several different actors in a completely decentralized way. And so uh we previously previously we spoke about uh how to prove it and by using a a ZKVM and which ZKVM okay and or better which VM uh risk five uh why for having a a larger developer base uh having for sure a mature tool chain a more ZK friendly architecture

but also uh another important aspect is that you can have a a multilanguage uh contract. So you can have multiple languages that can compile to risk 5. So you can have uh several uh development languages uh available for uh the developers. So let's uh have a summary about the proposed solution. So in this way the throughput is not anymore constrained by the computational power of a single actor. You can distribute the computation to several decentralized actor in a trustless way and

transactions are executed and proven in parallel and we are not affecting the centralization at all. The re-execution is avoided because once you aggregate you have a unique proof for for all the state changes and the nodes can just verify this state this proof and another benefit that you can have now that you have a a proof for the state. The chain is saxently proven and so you can enable trustless bridges between chains because the state is proven. So um you can just presenting a a proof to another chain you can prove some fact about the originating chain and also you can enable fully trustless

light clients and last but not least you can enable different development languages for writing the smart contracts. Okay, we made some estimates uh about the performances and how we made the comparison. We made the comparison to existing models. Okay, first of all, we are not using TPS. TPS is a wrong way for comparing uh let me say uh the throughput of the chain is completely misleading. You have to compare the computational throughput. So like cycles

per millisecond that the chain can process and uh the models that we compare are the fully sequential one like Ethereum uh and uh a multi-thread one like Solana for example and um we in order to have a appletole comparison um we assumed to have the same kind of VM on in all the three uh scenarios and also the same execution frequency and uh and the same network parameters. So um the execution and proving frequency uh were taken from the risk zero data sheet and um assuming uh

an Nvidia RTX uh 319 GPU and the proof aggregation was estimated using the timings of risk clunky 2 and plunky to gold implementation uh with an additional 4x coming from GPU acceleration and what are risky 2 and plur risk clunky 2 because we use risk zero for as a ZKVM M this clunky 2 allows to um wrap a risk zero received and plon to goldbear is a plonky2 version able to perform aggregation of the baby bear field without simulating arithmetic and several scenario have been estimated assuming different computation per each

transaction and different number of transaction different number of batches. So very quickly let's look at the at the last line for example where we have um cycles per transactions that let me say it's the complexity of the of the transaction execution. So let's assume um it's 8 800k cycles per transaction and that we have 64 transactions per batch and we estimated for example in this case a huge load in to the network.

This is what we want to achieve. And so 6,000 batch 16,000 batches and the cycles that Giga can process uh per second is uh 61 billion and the fully sequential is 5 million and the multi-thread is 100 million. So we can see a performance let me say um speed up ratio the of the giga protocol over the sequential one of 11 being 11 times 11 11,000 times

faster and over the multi-thread one over 500 times faster and so where where is giga chain now. So the we wrote a paper that is is now available publicly on print that describes in details how the protocol works and um all there is also an incentive schemes uh that let me say assure the centralization of the of the protocol. We developed a prototype that is able to parallelize both the execution and the proving over multiple machines. And also we designed uh smart

contracts uh that can be uh that are written in Rust and that can be uh proven using risk zero. And um last but not least, we implemented also the proof aggregation uh and dropping using risk lon was saying before and plunky to goldbear currently on CPU. So uh that's all and if you want to know more this is the white paper you can scan uh the QR code or there is the link and um that's all. Thank you.

Any questions? Yeah, I wonder about um how the dependencies induced by user transmit transaction translate into the gas model. So you know single transaction might cause different levels on congestion and level of parallelism. Is this something you have thought about or have an idea? It's a good question. So, uh let's say and this is mostly related to the incentive scheme. So, if you think okay the the block producer now think about the block producer the block

producer earn more the more transaction he can include in his in the block. Okay. So, the more is able to create a parallelizable uh solution the more he gain. So implicitly the gas will be uh affected but by how much the uh the transaction that is created by the user is affecting parallelization.

So we can see it in another way. Um let's say that um transaction that are locking many uh many accounts and potentially uh affecting the level of paralization will need to cover the costs that let me say will uh will be uh um created for not being able to uh include all the transactions because you have to provide a block within a certain amount of time. And so um let's say these affect the gas that the user has to pay. I hope this uh answer your question.

Um what is the bottleneck of your system that you imagine like if if you were to right implement um the actual decentralized part of right the the different part parts of the parts of the system and assume that the workload is somewhat paralyzable. What do you think the bottleneck is? Sorry what what do you think the bottleneck is of your system? The bottleneck oh okay um one element that needs to be uh fast is the aggregation part. So for this reason so the the recursive proof aggregation uh even if it is let me say it's let's say it scales uh logarithmically so the cost of aggregating all the all the batches okay

because it's a u it's in a tree form and so this is one of the um the bottleneck um but we already saw with um for example aggregating over Baby bear we already obtain with CPU very good uh let me say timings and by uh leveraging GPU we can even um let me see I have better numbers so I think that I mean and these estimates are already let me say taking into consideration all the phases uh for um for for creating a whole blog I

I I don't see call that's bottling but I I think that's probably like reduce latency right but maybe I think it's more like if you increase number of transactions will be the bing on the system which part to place first so if you increase what bandwidth uh so like number of transactions let's say of number instructions yeah I mean but if you increase the number of transactions I mean you can uh let's say augment the the number of parallel uh batch provers that are working and Then um let me say yeah at some point you will hit the limit of the of the block time but uh let's say this limit uh can be quite

bigger and let's say in addition to this we are also working on a consensus that allows to let's say not affect too much uh let me say that the latency and at the same time uh allow allowing a very uh let me say allowing having big trees of transactions and so uh including many more transactions. So because one tradeoff is the latency. So if you're thinking to create a huge tree of transactions uh then implicitly you're considering having a longer block time but we are

thinking about uh let me say I'm working on a consensus that would allow to let me say uh not affect the latency um while keeping the possibility to have huge trees that could aggregate many more transactions. Any other questions? All right. Thank you very much. Thank you.