ZK14 - Scaling Zcash with Project Tachyon - Tal Derei (Tachyon)

Transcript

Our first speaker for this session is Tal and he'll be telling us about scaling Zcash with Tachon. Take it away T. >> Okay. So, hi. Uh my name my name is Tall. I'm a cryptographic engineer uh working on Tachion and uh I'll talk about scaling Zcash. >> Oh, sorry. Um so uh I'll give a holistic update into Tachion uh what it is what

what how the construction works uh and then a semi-technical overview of REGU um our proving system and PCD toolkit uh and then some applications that RGU enables for Tachion. uh things like uh shielded transaction aggregation uh pruning uh the nullifier set uh via third-party intermediary uh we call an oblivious syncing service um and some other cool applications that I think are unique to Tachion >> next. Okay. Uh so at at a high level uh Tachion um Tachon is many things but it

uh in some sense realizes the uh vision of recursive composition uh outlined all the way back in the 2019 Halo paper. Um Tachion basically enables recursion which enables blockchain scalability. Um the recursive capabilities of Tachion don't currently exist in the Halo 2 library and they don't exist in production in Zcash in any capacity. Um which I think is a like a good data point that that outlines like the sheer complexity of trying to inject scalability into a privacy solution and private payment systems like Zcash. um

because the Halo paper came out in 2019 and only now we're trying to do some kind of recursive composition in Zcash. Um so uh Tachion is the uh fourth shielded pool in in Zcash's history. Um it's it's basically a protocol upgrade in the same lineage as uh Sprout, Sapling, and Orchard. And there have been many upgrades in between. Um, Tachion is uh a scalability upgrade and uh it positions itself purely as a scalability upgrade. Uh all of the these shielded pools have uh something called

ledger indistinguishability. Uh it's a security notion where you can't distinguish between uh different transactions in the shielded pool. They're basically just opaque bite strings. Um and Tachion uh maintains that uh uh that ledger indistinguishability property. Oh my god. Uh in terms of uh scalability challenges, um all well um anonymous payment systems derived from zero cache or zero-like protocols basically have the same scalability

challenges. They have uh uh the shielded sync problem. Um so you can't query a public-f facing remote RPC. Um all client client devices and wallets need to uh download um uh they need to download all of the uh uh cipher texts for every node payload and trial decrypt that node payload to discover a payment. Um there's this idea of transaction bloat. So uh the proofs are quite large. They're a few kilobytes in size which bloat the transaction which then bloat the block. uh you also have this nullifier growth problem. Uh so you have runaway state growth um as the nullifier

state becomes uh becomes large. Um and Tachion solves all of these problems or it will solve all of these problems. But I I'll try to motivate specifically the last one, this nullifier growth problem. So a nullifier is basically just a revocation token. Um it's a byte string um to prevent double spends. In Zcash, we store our nullifiers in a B tree set. Um, and there there's a paper by Sean and Ian called a note on notes towards scalable anonymous payments via evolving nullifiers and oblivious synchronization. Um, they give a they give an example in this paper that at 100 TPS uh the nullifier state grows by about a gigabyte per day. If you then

extend that and you shift the overton window towards commercial payment systems like Visa, then the nullifier state grows by 500 gigabytes per day. And that that's obviously unt untenable growth. You we can't expect a client device to have the bandwidth capabilities or um the compute capabilities even near that scale. Um so nullifier growth is a problem as the as the TPS grows. Um it grows proportional to the number of transactions. Um this is also uh state growth. Oh, thank you.

Um this is also state growth. Um there is a distinction between state versus uh history growth. Um if this was history growth, uh that might be okay. uh if eventually Zcash becomes like a Mina style blockchain and we have a succinct uh blockchain comprising of one proof and you can just do away with all of that history. Uh but again this is state growth which means uh all full nodes need to maintain this set and query this set. Um uh all validating consensus nodes need to maintain this. So it it it's uh it's a bottleneck um as as you increase the TP TPS. Um

so uh I I will as an aside also just highlight uh uh the cost differences between anonymous payment systems and uh non non-private payment systems like Bitcoin. So in Bitcoin um and the paper talks about this as well. Uh you only have to check a UTXO status and uh uh verify an ECDSA signature. In Tachion we have costs that are comparatively a lot more expensive than that. Um like verifying a zero knowledge proof um is much more expensive than checking uh an ECDSA signature. Um and again we also have this nullifier growth problem. So uh our costs are much higher. Uh

so the the solution that the paper outlines is this notion of an of an evolving nullifier. So it's the idea that nullifiers evolve uh over time. And in Zcash now uh nullifiers are uh associated with uh uh a note commitment. They're deterministically derived from a note commitment. But in Tachion, they're not uh deterministic anymore. They're associated with an epoch. Um so uh evolving nullifiers uh effectively split the ledger into a collection of epochs and uh to to prove that that a payment was unspent or uh that a note was

unspent, you you basically prove that all of the versions of that nullifier are also unspent. Um and we can outsource this check to a third-party intermediary uh that we call an oblivious syncing service. So the client device doesn't do this. This third party uh OSS does this. So what is the oblivious syncing service? Uh it's a technique that allows a remote service to prove on behalf of a client that their funds are unspent. Um it does many things but uh at a high level it it generates a succinct proof that uh it generates a succinct proof for uh uh

non-membership uh for nullifiers. uh the client device can uh um okay I I won't go too much into the complexity of of what the OSS does because Sean has a very nice ZCON 6 talk on this but at a high level what what the OSS does is it it syncs syncs notes and it syncs witnesses on behalf of the client and Um uh I guess to build a mental model of of how the wallet interacts with this OSS uh the wallet starts up it generates some nullifiers

and uh set non-inclusion witnesses. It can hand this off to uh the third party oss. the OSS can sync those notes and update update those witnesses. And then the client device can take the uh the um this evolved nullifier and and uh uh the PCD proof that the funds are unspent and and fold that via PCD into their transaction. Um again, it does a lot more than this. This is just a high level uh summary of of what it does. But Sean has a good ZCON uh Zecon 6 talk on this which uh I'll leave just for a few seconds if you want to uh if you want to

watch that talk at some point. Uh find me after I can hand out this QR code. Um so h how do we go towards scalable planetary money? um we want to maintain some bounded state. So uh full nodes uh should not need to maintain this uh perpetually growing nullifier state. Uh ideally you can prune that state via the OSS. So you don't need to maintain all of uh all of the history of nullifiers on chain. Uh you only have to maintain the latest uh state of nullifiers and check that they're uh unique in the latest block. and you can prune all of the um all of the the rest

of the nullifier state. Um we want shielded aggregation uh the the idea that you you can uh uh reduce transaction bloat by recursively combining proofs uh which uh uh increases the block capacity. Um and we we want every uh node to to be a full uh to be a light full node. So uh that enables succinct blockchain constructions. Uh the light clients become full nodes. Uh the idea of a full node in this context is um instead of uh syncing the whole chain, you can just verify a single proof that the

blockchain history is correct. Um so so what makes Tachion different from other pools? Uh this can be a talk in and of itself but I I'll motivate a high level idea of what the distinction between our pool is and previous pools like Orchard are. Um in previous pools you had uh a very tight coupling between uh the shielded protocol and the payment protocol. Uh so the key structures were uh pretty complex because they had to do uh they had they have had to have um a lot of capabilities baked in like spends and incoming uh and outgoing payment detection. Um, Pachion effectively decouples the shielded protocol from the payment protocol. So, so the shielded

protocol is uh for snarks and encryption. Um, and the actual cryptography and the payment protocol is um a different design space for things like addresses, the UX, the key exchange. Um, and and the nice thing about decoupling them is you can work on them at the same time. So we're building uh we're building the recursive proving system and PCD uh toolkit in the shielded pool and we're also working uh with a very talented team uh led by uh Dave Oja um and they're working on many kinds of problems like uh a postquantum UX uh post quantum key exchanges uh things like P to um kill shielded sync

um and and so forth. Um so Ragu um at a high level is our uh proving system and PCD toolkit. Um it it's one of the main components of Tachion. It sits at the heart of Tachion and does all of the heavy lifting. Um so REGU specifically is a recursive snark. Um it uses an accumulation scheme uh similar to the one defined in in the Halo paper. Um and it and it uses that accumulation scheme to instantiate an efficient recursion uh scheme. Um so Halo defined uh this notion of uh nested amortization. Uh nested amortization is a um uh it's a uh

aggregation technique loosely speaking um instantiated over a polomial commitment scheme based on inner product arguments. Um so REGU is Halo plus this uh BCLMS 21 idea of split accumulation. Uh so Ragu uses uh accumulation in the sense that uh instead of uh uh instead of verifying proofs we can fold them together uh using um uh linearly homorphic Person commitments and we can combine them using Fiachamir.

Um and then you can accumulate uh various kinds of arguments based on uh expensive polomial evaluations and many other kinds of arguments. Um and you you can defer expensive checks and then you you do a decision procedure at the end that does the expensive linear time uh verification. So we're just accumulating tons of expensive claims and verifying once at the end. Um, this is also the same underlying cryptography uh that exists in Halo. It's the same primitives from 2020. So, so we didn't invent any new crypto. Uh, we're using battle tested primitives that were uh that we're very familiar

with. Uh, and and Sean has a good blog post on Reagu. Um, in terms of the core architecture, uh, this is an R1C like arithmetization. Uh it's R1CS like in the sense that it's a boodle style arithmetization uh like Sonic and Halo. Uh it we have a cycle fold style uh folding and accumulation scheme. Uh we have a modified IPA uh modified bulletproofs IPA for the commitment scheme. Um it's a custom IOP. So it's uh custom RO1Cs NORC uh using split accumulation and IPA style commitments. um and it's instantiated over the pasta curves, the

palace investa curve cycle. Um in terms of the curve cycle approach that we took um there are two kinds there there are alternating and non-alternating. So alternating are like classic IVC where you bounce between the curve cycles and you maintain a proving system on both but you um only operate on one at the same at any given time per PCD step. Uh then you have lopsided. So you have one curve that that's used to uh just get around the curve cycle. Uh so one of them is a helper. Um but you still bounce between the curve cycles.

Uh then you have nonalternating. Uh that's things like cycle fold. Um so you have one curve that handles all of the scalar moles. Um so it does the folding and then you have the other curve cycle that uh does the main circuit logic. uh Ragu is effectively a hybrid between uh between um cycle fold and lopsided. So we maintain simultaneous state on both curves at the same time. So we're not bouncing between the two curves. Uh we're operating on both curves at the same time and doing work on both. Um so both curves have a full proving system.

um it has lopsided influence in the sense that the two curves are symmetric but they're workload asymmetric. So cycle fold is maximally asymmetric. You have one curve that does just the scaler moles and one curve that does the full uh the full the full circuit logic. So it's maximally asymmetric. Regu is also asymmetric but not as not as asymmetric. Uh so it's it's a combination of of uh different cycling approaches. Uh in terms of the arithmetization um this is an RO1CS like arithmetization.

Uh we don't have any uh complex uh uh uh newer uh machinery that new folding schemes like nova or cycle fold use. Uh we don't have multilinear polomials. We have just univariate polomials. uh we don't have lookup arguments, no custom gates, no highderee gates. Um so it's a very simple arithmetization with univariate polomials. Uh we also don't have any pre-processing. So uh pre-processing in this context means uh something like marlin or plon where you commit to a fixed collection of polomials and you embed those commitments in in a verification key and then you can open like kg commitments um

against those pre-committed polinomials. So so we we don't do that. We actually have a post-processing approach uh which is different than that and I think in our context more efficient. Um we we also don't have any verification keys. Uh so um we we don't need to launder verification keys between the recursion circuits. Uh we don't uh reason about the full R1CS matrix. So we don't materialize the full set of R1CS constraints. Um we we have these light lightweight uh circuit objects and evaluate the polinomials at partial restrictions. But the full R1Cs matrix is never evaluated in memory. Um we

don't evaluate polomials directly during synthesis. So we we we want the uh reduction to polomials to be highly optimized and again not store large polomials in memory. Uh we can uh we can take advantage of of memorization. Um so we have this notion called a a routine. Um so if the same subcircuit appears multiple times like the same endoscaler operations or the same Poseidon hashes uh you can effectively memorize those operations. So um the uh uh those operations can use this the same polomial and uh it's it's effectively a scaling rel relationship. So instead of

recomputing the polomials you can just shift the polomials and memoize them. Um uh we also need highly efficient circuit synthesis code. So um circuit synthesis is a hot path that we need to optimize for. Um if you look at something like arc works uh they bundle witness generation and constraint synthesis. Uh we we don't do that. We we have witness uh witnesses are uh optional depending on the synthesis path that we take. Um so so in arc works uh it's circuit synthesis is consist consistently 25 to 30% of the proof generation time. Um I haven't

fully benchmarked what it is in our system but circuit synthesis does need to be um highly optimized especially in a non uniform PCD setting where you're switching between nodes in the PCD graph uh very often. Um, so the uh the optimization trade-off uh I guess a natural question is like how does Reggu compensate for having such a simple arithmetization? Well, it's it boils down to the things we actually optimize for. Uh we optimize for verifier speed uh which scales with the size of the circuits not the number of circuits. And we also optimize for um uh the uh the option of the number of circuits we can

choose per PCD step and we want that to be large. Um don't know how much time I have so I'll just skip some stuff. Uh so why do we want smaller circuits? Well, uh it means smaller witness commitments uh which leads to smaller IPA proofs which leads to uh smaller verifier multi-exponentiation. So we want the verification to be fast and that's what we optimize for. Um we also want verifier the verification to be fast uh because of things like propagating transactions or um like black block transaction times. So uh like nodes need to verify before

forwarding and if the verification is slow then at some limit that can equal network latency. So we want the verification to be fast and for block times uh verification time uh effectively puts a li a floor on how low the block times can be. Um uh there's also this notion called a recursion threshold. Um it's uh the minimum statement required to perform recursion. So when a proof system is fully succinct um so meaning the proof size and the verification time are sublinear uh the system can verify its own proofs. Uh we have a recursion threshold of 2 to the 11 gates. um it

the verification scales with four n linear constraints. So we're doing a two to the 13 MSMs. Uh we have this concept called a a registry polomial. Um so you can encode all the circuits uh in a single polomial um and then you you can evaluate the polomial at at different roots of unity over a domain and recover um the specific circuit polomials. So we instantiate this uh trivariant polomial mwxy. You can evaluate that at some root of unity and recover the uh bariate sxy.

Um uh we we eval there's a post-processing that we do to this polomial. So we we we evaluate this polomial at a set of points that overdetermines the polomial. um and then we can take a registry digest of the polomial and uh embed that as a constraint in our polomials during polomial evaluation time. Uh so if you tweak the polomial degrees of freedom if a malicious actor tweaks them uh that will change the polomial evaluation which changes the uh the registry uh well it changes the registry key constraint which changes the polomial

evaluation. So you you can't know ahead of time what the polomial will evaluate to uh because any change will again modify that polomial. Uh we have this notion called a staging system. Um so usually you commit to uh uh the full witness uh with staging uh and this is a known technique. Uh we can commit to stages uh uh we can commit to witnesses in partial stages. Um so uh a stage is is a collection of wires uh that's shared by multiple recursion circuits. Um and and uh they they can share uh they can share those stages. uh it's used in two contexts in our proving

system. Uh you you um you can commit to each stage independently and absorb commitments and then you can squeeze challenges uh from those commitments. So you can absorb interstitial commitments and squeeze uh challenges. Um we we also use it to reduce hashing. So if you uh if you need to encode like n things in in a fiat mirror transcript uh you can put those in a stage um and uh uh commit to that stage. Uh uh we we call this a nested commitment. So you're committing to one thing instead of end things. Uh I don't have a lot of time so I'll skip this. Um we or maybe um

uh so the the thing we actually defer are uh wellformedness checks uh verifying that the nested staging polinomials don't overlap that the wire sta the wire stages are non-ontiguous um and we defer all of the scalar multiplications um okay quickly talking about uh applications you you have this uh this um the obvious application is a shielded aggregation. So instead of putting n transactions in a block, you can recursively compose them uh into a single transaction.

Um the oss can use this uh recursive capability to uh um to to generate these nullifiers and and to update them over time. uh in in in the whole construction of Tachion, we're we're probably not going to have uh any Merkel trees. Uh we have um a 2 to PCD. Um that's dynamic depth, but we don't need any like spe special set accumula accumulators. It's just a hash chain. Um the main technique uh that's not highlighted here, it's called polomial oracle access. So it's this idea that the application has access to the underlying univariate polomial

commitment scheme and it can open uh the commitment scheme at any point the application needs and you can build like uh very complex um um IOPS that are generic that don't even have to be snarks. Uh you can build IOPS for things like volatile memory checking uh to uh check um that uh an application accessed memory correctly and the shielded protocol uh can use that to um to check things about nullifiers and commitments. Uh we we're also uh form formally verifying parts of Reggu. Um we're working with ZK security to uh integrate their uh clean framework their lean DSL

against against against Reggu circuit API. Uh as of now as of this morning we do have a blog post um on this uh uh quickly I again postquantum can be a talk in and of itself but I'll just give a quick quick summary. Uh so uh we are postquantum today in most cases uh because we uh uh because we we do use symmetric primitives but to be fully postquantum sound uh we need to uh uh we need to move from a elliptic curve based PCS to a lattice-based PCS and if if you look at the lattice literature they're um uh they're settling on polomial commitments um so when um when Zcash has

uh postquantum prim primitives, we can just swap the PCS. Uh in terms of encryption, uh we we'd need to go from elliptic curve chems to postquantum chems, uh MLEM and postquantum signatures. Um we have a ton of like postquantum resources like a podcast, a road map, a thing called quantum recoverability, so like freezing the shielded pool in the event of a quantum adversary. Uh we have a blog. Um we do plan to have a protocol upgrade and a test net uh sometime later later this year. Uh this is our team uh Sean, myself, Connor O'Hara, Alex Gang, and El Winslow. Um and then uh we do

have a website tachon.zcash. Um and Tachon Zcash uh is the GitHub if you want to learn more. Uh and if you have any questions, email Sean. Uh thank you. Thank you very much, Tal.