# Beyond recursive proving for Starknet by Gideon Kaempfer | Devcon SEA

- Speakers: [Gideon Kaempfer](https://streameth.org/speakers/gideon-kaempfer)
- Channel: [Devcon](https://streameth.org/devcon)
- Date: 2025-10-07
- Duration: 23:56
- Watch: https://streameth.org/watch/yt-SdWkt9B5W8E
- YouTube: https://www.youtube.com/watch?v=SdWkt9B5W8E

## Description

Recursive proving is very cool tech enabling very large proofs or combining many different statements into a single proof. Beyond recursive proving, statements can be combined in interesting ways to further reduce system overheads such as data availability compression and layer1 state updates as well as various privacy concepts. In this session we'll discuss some of these technologies and how they are being applied in Starknet to achieve various user and system benefits.

Speaker(s): Gideon Kaempfer
Skill level: Intermediate
Track: Layer 2
Keywords: Zk Rollups, starknet, recursion

Follow us: https://twitter.com/efdevcon, https://twitter.com/ethereum, https://warpcast.com/devcon
Learn more about devcon: https://www.devcon.org/
Learn more about ethereum: https://ethereum.org/ 

Visit the https://archive.devcon.org/ to gain access to the entire library of Devcon talks with the ease of filtering, playlists, personalized suggestions, decentralized access on Swarm, IPFS and more.

Devcon is the Ethereum conference for developers, researchers, thinkers, and makers. 
Devcon SEA was held in Bangkok, Thailand on Nov 12 - Nov 15, 2024.
Devcon is organized and presented by the Ethereum Foundation. To find out more, please visit https://ethereum.foundation/

## Transcript

our next speaker will talk about Beyond recours of approving for starnet please welcome gon CER hi everyone let's see if you can hear me okay so uh the goal of this presentation is to talk about everything Beyond recursive proving but I'm not going to assume you know everything about proving or recursive proving uh so I'll just begin with the basics and uh you'll uh follow me I assume so uh let's talk about the basics of a validity rollup what uh composes a validity rollup you have transactions uh sequencers select these transactions Define their order and I'll use the term sequencer also for execution of these transactions so if you're confused by base rollups where they separate the sequencing from execution here I'm going to combine them um and they build the blocks uh once we have a block uh the way a validity rollup works is that it proves the validity of the execution of these blocks using a prover instance and send this sends this proof per block to verify our contract on ethereum on the layer underlying layer one and once that proof has been accepted uh a state contract tracking the state of the rollup is updated with a new state uh together with the state update we also uh add what we call State diff and uh we may include also messaging between the layer two and the validity rollup and the underlying Network State diff just to make sure you understand what I mean when I talk about State diff is basically the update to the state of the rollup uh resulting from the executed block uh validity rollups do not need to transmit the actual transaction that they sequenced to the underlying layer there's no context no uh uh such thing as fraud proofs or anything of that kind we positively prove everything happening on a validity rollup and as a result we can send much less much less data to the underlying Network in order to be able to reconstruct the full state of the layer two so a state diff is basically just the locations in the state that have changed and their values so in this simple example the has been changed into X so the state diff of the transition from State one to state two is just a single element change location 3 to Value x what does it mean to prove a block so basically what we're doing is we're using the context of uh of uh proof in order to uh um to prove the statement that we have seen a valid execution from a given State a resulting in a new state B and the resulting stative between State a and state B is such and such so the statement is the transactions were correctly sequenced and the input State results in the output State what are we doing on layer one for the validity rollup in this simple uh basic validity rollup uh we need to verify a proof of a block which can be costly in some cases we need to publish the state diff typically using blobs on ethereum and we need to update the state which is typically some contract call of the state contract tracking the state of the rooll up on L one um as long as the blocks are significantly large this is all this is fine but if we want just to have a few transactions per block on Layer Two or quick finality this can become quite costly so the basic validity rollup is good if you have either a very large block or you have a lot of traffic and then you can still have a short finality on Layer Two or you have long finality then it becomes less costly but it's less effective because you have long finality enter recursive proving recursive proving intends to reduce the overhead of verifying the proofs per block so let's begin with what recursive proving really is so on the left hand side you can see the generic uh concept of proving so basically you have some statement and you want to prove that given a a current uh given an input or a witness if you like uh there is a correct execution of the statement resulting in a given output and what the prover does it basically proves that the statement was run correctly on the input and that the actual output is the given output uh the proof does not necessarily need to divulge the input as we call it zero knowledge proofs but if you like to include some of the input in the output you can just copy that within the statement so how do we use this context uh this concept to create recursive proving basically we replace the statement with a new statement that just says I verified two proofs and found them to be correct uh so proof one with output one and proof two with output two you use a statement that performs verification which is just an algorithm right so there's no reason that you can't uh build such a statement and the result is the two outputs the original outputs you just copy them from the input to the output so when we prove this statement exactly like on the left hand side the result is a proof and the outputs that we want to generate which in this case are output one and output two what does this mean we've basically combined two proofs with two outputs into one proof with two out outputs now we can use this construct in order to combine various statements possibly totally different statements from different sources if you like we can prove uh statements from multiple rollups even uh into a single proof and a series of outputs uh coming from the original inputs or from the original statements I I should say so in this diagram you can see four different statements there's no relationship between them each of them has their own input creates the own their own output and uh using recursive proving twice in this example we result with one proof and four outputs so what does a validity rollup with recursive proving look like very very similar to what we had before so you have the transactions the sequencers Define the sequence uh execute the transactions and create blocks just like before in this case let's say the accumulate four blocks then we can use recursive proving in order to prove these four blocks with one proof as opposed to four proofs in the previous example in the basic validity roll up and this proof is sent to the same verifier contract on layer one then for every block a state update takes place on layer one on the smart contract that tracks the state of the rollup and the statives per block are sent to layer one so using recursive proving we've basically reduced the cost of verifying proofs on layer one but we still keep uh the concept of publishing State diffs per block and State updates per transition so from State I to State I + one that takes place per block it's less costly than before because sometimes a significant cost is on the verification of the proof uh State updates are less costly but the smaller the blocks get the more significant the cost of these State updates become so this allows us to improve uh to reduce uh block times on Layer Two on the rollup or if you like uh reduces the need to perform large B batching on the blocks on layer to but still I would like to optimize this further which brings me to Beyond recursive proving which is the topic of my discussion uh we want to build something which we call applicative recursion so let's define applicative recursion roughly in the following way here you see again the same recursive proving tree that we had before uh we have four input statements uh we combine them together into a single proof with four outputs with applicative recursion uh the difference uh from regular uh recursive proving is that here we're going to assume that all the statements come from a single application so they have some kind of common semantics uh for instance these are four proofs of blocks coming from the same rollup then what we do is we use the same context the concept of proving but now for basically squashing the outputs together into a single output uh so in this case we'll have a new statement which basically says this is in the red rectangle on the bottom basically we verify the last proof so we make sure that the outputs are valid by using verification of this proof and we perform a statement that is a valid combination of the four outputs into a single output so the result is a single proof with a single output this time so let's see what this output could contain okay so for example if we're interested in aggregating state diff uh here is an example of three state transitions so we're moving from State one to state two to state three and eventually to State four in each transition we generate State diff so in the first transition you can see that position number three has changed from D into X in the second transition we're touching positions five and six and in the last transition the fourth transition from the third transition from state three to State four uh we're changing position three again and position six again so the result is the state called S4 on the bottom of the slide but if you look at the resulting stative between S1 and S4 there are only three changes so there's no reason to transmit three statives with six changes as in this example so one of the things that we can do in the squashing proof this final step of applicative recursion is joining the outputs together into a single more concise output now in reality for validity rollups it happens quite a lot that the same positions in the state are changed multiple times even within a block and certainly between blocks especially if there are many many blocks or large blocks so this kind of uh aggregation is very very is very important to improve efficiency of State div transmitted to the blockchain but also other things can be done and I'll go into examples in a moment so now uh validity rollup looks like this you have the transactions as you know they're sequenced and executed put into blocks for every set of blocks we create a recursive proof then we do the applicative recursion because all these proofs relate to the same application the same rollup in this case so we can do that and this single proof with the aggregated output a single output is sent to the verifier on layer one so we pay for verification just like we paid for ver verification in the previous example using simple recursive proving but now instead of doing a state update per block we can do a state update per recursive cycle if you like for multiple blocks together simultaneously so what does uh this look like so we have the recursive uh uh appc applicative recursion recursion per recursion we verify appr proof and per recursion we publish the aggregate State diff in one or more blobs and update the state on the on the contract that tracks the state of the rollup with a single state update that updates the state to the final State we've reached after multiple blocks and of course we can include messaging as before so the more blocks we have Pro recursion the lower layer one cost will be and this basically skills infinitely uh depending on the latency you require uh to layer one um and uh this is actually what we are doing currently on our rollup uh called Stark net what else can be done in this uh applicative squashing or if you like an applicative recursion so the basic uh aggregation of State diffs as I mentioned is just uh a straightforward aggregation but you can also do more sophisticated things for instance if you want to represent your state in a more efficient way so utilize your blobs more efficiently you can Implement for instance a compression algorithm on this data uh just deflating the data into much smaller form which allows you to uh include more blocks on your applicative recursion of course eventually when all the blobs fill up uh you may reach a state where blob prices could go up or you have more blobs than could fit in a single transaction and things like that that is something you want to avoid so that's a point where you want to cut off the applicative recursion so it's not really infinite as I mentioned before in addition as I mentioned you can uh remove the need to do update States per block and if you like you can generalize this into a con into a concept of segmenting a very large computer ation into multiple segments so if you prove that you've executed a program from some State a to some State B and then you've executed the same program or continuation of the program from State B to State C Etc an applicative recursion or the squashing mechanism can ensure that you've actually proven the complete execution of this program from State a all the way through State C or Zed or whatever uh so this is the generalization of the concept of applicative recursion and you may have more ideas here and uh the more creative you get the more interesting it gets so basically if you think about it uh the whole concept of recursive proving applicative proving is are a few examples of offchain proving so these are proofs that are never submitted to a verifier on layer one so basically they're only submitted to a new statement that verifies them off chain completely and there are other examples that are useful in in this context and I'll talk about a few of these so one example could be for instance for a privacy preserving uh uh exchange for example so let's say you have an exchange on your rollup on the blockchain itself typically exchanges that are on chain they expose the positions of their users uh some users are very sensitive to this information because it divulges a trading Str strategies so what you can do is basically have a user who knows uh their own position uh execute uh some order on their position while keeping the position encrypted on the on the rollup itself or on the blockchain if you like so in this example if I go over the diagram you keep you store encrypted positions on the blockchain every user uh is involved in the encryption of this of this position by using their own key they can read the encrypted position decrypt it and then execute an order on their own position and encrypt the resulting or the resulting position now if they prove to a contract that executes um trades that this would be the result of their encrypted position if for instance they get a little more e selling a little bit of Bitcoin uh then a trading contract or if you like an exchange can accept that proof without actually knowing the contents of the current position so of course this does divulge some information because uh we are telling the exchange uh by how much how much we are selling and how much we are buying but anyone looking at the position of a given uh user wouldn't be able to decipher the current strategy of this Trader so this is one example where proofs can be combined into a blockchain in order to create a more private environment uh by using client side proving in this example there are variants of this concept uh where we trust the exchange with our private information and then all the positions can be encrypted and decrypted by the exchange as part of uh proving uh but this is one interesting example U that can also be implemented on uh rollups or blockchains as long as you have a contract that can verify uh proofs uh on Stark net we have contracts verifying Stark proofs uh we also have a contract verifying gross extin proofs so you have a choice of building your application on top of that and Stark net today another example is for scaling blockchains and this will be my final slide so for everyone uh uh pressed for time um this is a little bit more sophisticated but the idea is let's say I have a bottleneck in terms of the capacity of sequencing and execution of what's going on in the in the rollup I want to Outsource sequencing to someone else if you like or I want to Shard my layer my uh validity rollup so that different sequencers can run together in parallel sequencing different parts of the rollup or different contracts if you like some segregation of transactions so in this context you basically what you see here is something that looks like two rollups but they are actually the same rollup so you have multiple sequencers each executing part of the sequencing for the rollup and proving this sequencing is correct using the validity concept where the output of this proof is the state diff or the changes to the state in the areas that they're responsible for an underlying sequencer that which is the validity rollup sequencer can verify these proofs completely remaining on the rollup doesn't have these proofs don't need to be sent to ethereum and by verifying these proofs uh this centralized or this rollup sequencer can accept the state diffs coming from these various shards or what we call ZK threads and when we combine the state of all the threads we result in a single state of a single rollup that can be as in the previous story transmitted to ethereum with various kinds of proving uh resulting in a unified uh rollup that has all the state computed by multiple sequencers so here we utilize uh validity proofs uh in order to scale a rollup that's it I think I have 3 seconds left thank you we have now a few questions could you question so I think the first question is how is aggregating State differ from multiple blocks and is it better than increasing the block time itself um aggregating state is better than multiple blocks uh no uh multiple blocks is better than having a single aggregate block I'll put it that way why because what use users really want is finality on Layer Two on the validity roll up itself so response times go down the smaller the block is uh of course if we would wait for an hour to aggregate lots of transactions in a block then we would had you we would have huge blocks and the basic validity roll up would work but finality on Layer Two would be very slow I also want to answer of about about proving cost um it's a good question because uh in the past people thought uh that proving I remember back in 2017 or 2018 uh the number thrown at people was that proving a statement was something like four orders of magnitude uh less uh performant than actually executing that statement at starkware I think our initial prover reached about two orders of magnitude H which is called the stoneover and today we're talking about a Stover where execution of the statement is almost the same as proving the statement so the cost of proving has gone down very very significantly well it's not the same of course you still have an overhead but to prove statements today costs very very little uh so all this recursive proving for instance is done within seconds every recursive step so you get a very quick finality even of the recursive proof and of course that doesn't cost much okay um we have still time so um what's the current transaction finality on Stark net if you uh can yes currently on starnet you get finality on Layer Two within two seconds two seconds and this two seconds will be preserved in a decentralized environment where actually block times will go down to 2 seconds and we will continue to prove every block so that's where we can go with this technology and maybe could this be used for Crossroad lab Communications through a shared approver absolutely uh in fact in Stark net to in starkware I should say today we already have a shared prover it's called sharp sharp for shared proving and we use it for many systems together so we use it for public Stark net we use it for private Stark X instances we are layer 2 platforms for exchanges we use it for app chains of Stark net and all of the com all of these proofs are combined into single recursive proofs some of them are applicative recursion some of them are regular recursion and all of this is submitted in a single proof attesting to a huge number of execution steps across multiple systems so of course this could also be used for messaging between different rollups uh do we have any questions from the audience no okay uh