Revisiting Accepted Wisdom in SNARK Design | a16z crypto research

Transcript

so uh I think the way that jolt Works actually uh counters a number of narratives or just general beliefs uh in sort of the community that's building and deploying these snarks so I wanted to describe some of them um so one of them uh and you see this uh Viewpoint expressed uh prominently like on Twitter all the time is that uh simpler instruction sets should lead to faster ZK VMS all right and this is a pretty intuitive statement it's like if each uh step of the VM is simpler it should be faster to prove one step of the VM right and this uh sort of viewpoint is sort of taken to its most extreme in I think the Cairo virtual machine which

was specifically designed to have kind of very small set of very snark friendly instructions okay but uh you know we saw yesterday that uh two things so one is I guess the the commitment cost for the prover and jolt are are less than existing zkvm projects and two like the scalability of the Joe prover like actually oddly it like doesn't really depend on the complexity of the instructions so it's something a little weird there's some kind of threshold Behavior where as long as the instruction leads to a structured lookup table uh whatever structure you know lasso or generalized lasso needs um it doesn't matter how complicated instruction is the approver's costs are actually determined by the size of the

lookup table which only depends on like how big are the inputs to the instruction um okay so another narrative out there is uh there's a heavy focus on supporting what are called high degree constraints um so this is just like you think of this as a generalization of like multiplication Gates where you might be um sort of multiplying more than two numbers or you know doing other other operations that don't correspond to like degree two polynomials um and you know for example there's a recent word called hypernova and protostar which look to uh take a sort of a very different approach very exciting approach to snox uh distinct from anything I'm telling you about today uh which previously were only known to support degree two constraints

and allow them to support higher degree constraints and people are very excited about that now now jolt kind of pushes like all the work the prover does almost all of it into the lookup argument and what's left is very simple and easily captured not just by degree two constraints but actually a very special kind of degree two constraints called r1cs okay so um I just uh you know I I still think High degree constraints are important but if your goal is a ZK VM anyway it's uh it's not actually clear at all that is important so kind of what uh what's more important than high degree constraints is is being able to use a good lookup argument basically okay um there's also a view that snarks over large fields are wasteful um this is actually one of the main

reasons I think people like to use fry uh I mean it's also you know a voice up to curse so it's possibly post Quantum secure so that's nice but um in certain settings uh yeah so so one like field operation over small field is much faster than a field operation over a big field right and um I actually have a blog post coming out soon where I'll discuss why I think you know even if you can work over small fields in some applications it doesn't actually make sense anyway I have to get into that now I want to um discuss the issue about this view that we should work over small Fields because working over large Fields is like wasteful right if you if you um you know the the rough intuition here I think is

um you know if you want the approve her to like commit to a value that's pretty small but you have to represent the value as like a 256-bit field element uh well there's just like a lot of extra bits in there that aren't doing anything and that's just a big waste and you're sort of paying a price in the for the prover um and I don't necessarily think that's the case because of this issue I highlighted that um committing with elliptic curve-based commitment schemes to small field elements even if the element lives in a 256-bit field is really fast right and in fact you can actually do it with essentially one group operation not one exponentiation one operation uh per committed field element if the field elements are small enough

um and then finally uh there's this very popular approach now to snark design which heavily uses recursion where people will take a big circuit break it up into small pieces so to prove each piece separately and then like aggregate the resulting proofs to get kind of approved for the big circuit okay um and with current popular techniques there's really kind of no major loss in performance by doing this um in fact to get good performance is like the only way you can do it because um a lot of snarks people using today have sort of super linear approver time so it's sort of a diseconomy of scale where you deal with a bigger circuit and the cost kind of pergate in the circuit

goes up because of ffts and things like that okay um and a lot of one of the reasons people are doing the breaking up by the way is because something like fry has enormous space costs for the prover like hundreds of gigabytes even for small circuits and so even ignoring proofer time the proverb space just you can't tolerate it at Epic circuits um and there's not much overhead um in breaking it up into small pieces today all you really have to do is make sure that um kind of the the snark verifier when represented as a circuit is like significantly smaller than the original circuit that was proved so that way um when you go to aggregate the proofs by kind of proving you know something the snork verifier would have accepted sort of that's a statement that was smaller than the original one and so the

overhead like isn't a big deal um lasso and joltz uh you actually see economies of scale instead of diseconomies of scale so you actually would lose something by breaking things into smaller pieces and the way to think about these lookup arguments and we discussed this last time in response to one of the questions was you think of them as the prover kind of pays a fixed cost like table size to the one over some constant okay no matter how many lookups are done all right and then that cost gets amortized over all the lookups okay um so the more lookups there are like the better uh that cost gets amortized also if you're using pippinger's algorithm to compute nsms the bigger the pippenger speed up like pipinger saves

like a log Factor over naive multi-exponentiation and you know log of something bigger is a little bit bigger um and intuitively I think we shouldn't expect to see diseconomies of scale right I mean in the real world we see economies of scale all the time um so I think if you kind of use the right techniques uh in snark design uh you know one proof for something really big um you know until you like exhaust the space you know your approver needs or something should actually be better than breaking things into tiny pieces okay so I don't know I hope at least these New Perspectives are interesting even if I don't think everyone's going to agree with me