Challenges, Advancements, and Tools for Developing Post-Quantum zk-SNARKs | BTQ | ETHTaipei 2023

okay good morning y'all hear me [Music] hello hello okay there we go yeah good morning Zao uh pleasure to to be here with you all I hope you're all doing well my name is Chris I'm the head of Partnerships at btq uh very excited to be here today to talk a little bit about the future of ZK specifically around challenges advancements and tooling for the development of post Quantum ZK snarks um before we get started there is a QR code here this is the hack MD for this talk I believe this is where you can collaborate over over notes um and yeah we can get into it also want to do a quick survey uh just to get to the audience a little bit so please raise your hand if you are a ZK researcher CK researchers nice a few of you and then uh how about ZK Developers nice okay great great great okay I think I'm in the right place then so the outline for today's talk will be introducing a little bit about our team at btq and the work that we're doing in post Quantum cryptography using pqc as a motivation for why we think we need to start thinking about this transition to post quantum snarks we'll talk I'll introduce kilang which is our team's attempt at initiating this transition to PQ snarks talking a little bit talking a little bit about the language and the ecosystem and then finishing up with a live demo so our team at btq was founded by a group of post-quantum researchers with an interest in addressing the threats that quantum computers pose to blockchains our research or we conduct research in both software and hardware and in order and really what we're looking at is how to make pqc more manageable more digestible in in industry blockchains and and other Technologies and in our effort to do so this has let us down the rabbit hole of post-quantum snarics so let's talk a little bit about that today um so for those of you who aren't familiar with this idea about post Quantum cryptography let's distinguish how this differs from pre-quantum cryptography first so pre-quantium crypto is you know most of the cryptography we use today which relies on mathematical problems uh that are assumed to be difficult only by the computers that we have today so most of the problems that that underpin our crypto systems that we rely on being difficult are things like factorization of large numbers this is what you find in the RSA crypto system also in discrete also the discrete log problem which you find underpinning elliptic curve cryptography now the problem with pre-quantum cryptography is that it as that these problems aren't necessarily hard for quantum computers to solve as well and so if there were and so if there was a Quantum adversary they'd be able to essentially solve these problems which underpin the crypto systems that guarantee their security so what we need to do in post Quantum cryptography is look to to swap out these problems that we assume as being difficult that underpin these crypto systems and so we can look to kind of new variations or new fields of cryptography namely lattice base and and hashbase these are two very popular fields and post Quantum cryptography that introduce new problems that there are no no known efficient Quantum algorithms for it's also worth noting that lattice base and hash based cryptography underpin the latest nist standardized algorithms which is the standardizations body in the US which essentially dictates what all government organizations need to use and so it's really seen as the de facto class of cryptographic algorithms to use so a lot of people are looking at lattice base and hash based cryptography another way that we can look at this transition to post Quantum cryptography is from the view of or point of view of complexity Theory where right now we're relying on problems such as interfac integer factorization and discrete logarithm problem but unfortunately these problems align within the space of bqp which is the set of problems for which there are known efficient Quantum algorithms for and since we are on the horizon of quantum computers it's now the time to move out of bqp we want to move to we want to replace these problems with things like with problems such as learning with errors and the short industry solution both of which are found in in lattice basic cryptography for example and since snarks are really just cryptography under the hood this means that there are also pre and post quantum snarks the good thing is that post Quantum snerdics do exist so this taxonomy of snarks was taken from Justin thaler's book on snarks and he's identified several plausibly post-quantum snark constructions so there is hope and what this talk is going to be about is how do we initiate a transition to using these post Quantum scenarios or like how do we make this transition as painless as possible this transition to Snorks is also on the ethereum roadmap and Quantum stiffness is is very much a uh the end game in ethereum as it should be in in pretty much every cryptographic or any like digital technology that uses cryptography um so I'm not sure if you can see this uh but on the yeah long-term road maps you have Quantum safe aggregation or aggregate friendly signatures um Quantum save uh setup yeah yeah set up free commitments and uh down here we have uh Quantum uh transition to to Quantum snarks or Quantum safe snarks what we should also acknowledge is that this transition to a fully snarked ethereum is underway so this is the item down here where we have a fully snarked ethereum and we're already starting to see this via the emergence of ZK Roll-Ups ZK EVMS zika indexers ZK oracles ZK just about everything and what this means is that with all of these zero knowledge proofs we're also going to need to upgrade those to post quantums UK and a final note here is that just referring back to the other slide um I think a common misconception is that Starks are like the only way out of this Forest of of pre-quantum but there do exists post-quantum snarks as well and so what we'll end up with is as having a variety of of options for post Quantum ZK snarks just as we do today and you'll most likely want or you'll be able to pick the snark that fits your application that affords you the the correct trade-offs based off of your requirements and so starting to think about how we lit how how we live in a in a um in a I guess multiple post Quantum snark world and how we can move between them so in our effort to start initiating this transition this transition to PQ snarks our team has developed kilang which is not uh yeah yeah not a coincidence that it's a Taiwanese Taiwanese um city and kilung is a ZK DSL for uh or for for writings or knowledge proofs what we aimed to do with keelung was to make it as easy as possible for developers to write secure and reliable post Quantum snarks without requiring expert significant expertise in cryptography key lung is also 100 open source which we're very pleased to say there are two components of key loan there's the language which is currently 100 open source there's also a compiler which we'll talk about which will be open sourcing in the next several months we're also very excited to launch key along with some of our launch Partners in sizzic who's working with Hardware acceleration dmtp holonym and VES great so when we went about building Keelan to again initiate this transition to post Quantum snarks we recognize that building another ZK DSL maybe wasn't the hottest thing to do because there are already so many great dsls out there so in addition to supporting post Quantum we also made an effort to support some other things as well such as mobile witness and proof generation which we think is critical in order to onboard the next Millions million of users into into crypto obviously supporting a variety of post Quantum improving systems and also implementing post Quantum cryptographic Primitives in our kilang library for developers to use we also will support a variety of prequent improving systems as this kind of bridge for developers to start with pre-quantum and then move to post Quantum which we'll talk about in a bit we also wanted to make this as developer friendly as possible so we raised the level of obstruction required to build these circuits so that you don't need to be a hardcore zika developer nor cryptographer in order to build safe snarks and then we also are working on Hardware acceleration tighter integration with Hardware acceleration with our partners at sizzic so the idea behind keylong is that you can write one circuit and live with it for the rest of Eternity so in this diagram here you start off with running your circuit description in key lung which then gets compiled down to kind of like an a pre-intermediate representation in eclair which will essentially be able to Route it to various back-end proving systems and we really think that this is one of the ways that we can go about initiating this transition where if you're a developer you can write your your circuit description once and then just recompile it back to it or recompile it down to a post Quantum improving system when you think it's time for your application to upgrade so we'll talk a little bit a little bit about keelung and how we try to make it easy for developers to build these Quantum safe snarks so we made maybe an interesting design decision and in in embedding uh key lung and Haskell uh is anybody here a fan of Haskell any fans about yeah nice the house whoever's a fan about their arms a shoot up when I when I ask this question so I love it it's a loyal community and so essentially by embedding ourselves in Haskell we get to inherit a lot of haskells yeah functions module systems libraries functionality which makes it really really elegant and really easy to express some some some circuit descriptions um in in as little effort as possible and also in a very safe way when we focused so so we embedded ourselves in in Haskell and when we went about building the actual zero knowledge components in Haskell we actually realized that it was actually a relatively small language that we needed to maintain in order to make zkp generation or ck proof writing possible in Haskell so we have a relatively small core language which we'll actually run through today and then also a very simple interface for bridging key lung and high school something that I've noticed when when programming in key long is that it's actually very clear when you're writing Haskell and when you're writing killing because most of the heavy lifting is done by the Haskell language like most of the um most of the like computation or the description of the computation that you want to do is done in Haskell and Keeling really just looks after the management of like your public and private inputs kilong also has a compiler which which I briefly mentioned so every key lung program gets compiled down to a set of constraints which will then be fed to either pre or post Quantum proving systems and this is something that we've put a lot of effort into as well so our in our compiler every program will go through a series of optimization passes and basically in order to reduce the number of constraints as much as possible before it gets translated into its relevant IR okay so touching on the small core language of kilong in order to develop these these peaky snarks um really you only have to keep track of three things or three through data types which are field elements these are just numbers in a finite fields booleans which are really just finite field elements or sorry field elements underneath the hood but allows you to express things like true and false and then unsigned integers which gives you a little bit more of expressivity when you're building these these circuits so before we dive into some more interesting examples using keylong let's just start with a very simple example using the square function which I guess kind of familiar with key lung so this Square function accepts a public input x a private input Y and then asserts that the private input is the square of the public input and when we're thinking about developing Snorks we just want to get into this mode of thinking about public and private inputs because recall that zero knowledge you're typically trying to prove something about some computation about or about some some information without fully disclosing that information so the public input is what you're willing to share with the world and the private input is what you want to hold close to your chest so I think the this example is really nice is a really nice way to see how to see the benefits of embedding a ZK DSL in in Haskell so in this example we're going to walk through how we can think about implementing the rounds of a Poseidon hash function so Poseidon is a hash function that was designed specifically for uh for for zero knowledge proofs which makes it very very fast and so typically if you're going to be hashing something in a snark you're going to be looking at using the Poseidon hash function um the reason it's so fast is because it uses a substitution permutation Network design where where it consists of several instances of these rounds which are the implementation of of the same set of functions um and it just essentially permeates through this this network so if we were to think about implementing one of the rounds in in Poseidon assume that we have you know the relevant functions at each one of the steps that we've already implemented arc S and M and so to define the round function we would just use the Haskell notation and Define round which takes looking at the the top row here the first line here which takes an integer as input a list of field elements as input and then outputs a list of field elements and then for the actual function definition we can say that one instance of this round to R which will be this integer so the integer is is this input here to Arc well it's the input to R and then Arc will take the list of field elements it'll compute that use the output of Arc as input to the s-box function for that round and then use the output of that as input to the next function so if we were to think about let's say that we wanted to implement three of these rounds um if we were to express this mathematically it would simply be to just compute the first round round zero against some initial state of data and then use the output of that as input to the first round and use the output of that into the input as of of the third round which is just these nested functions and we can do all of this really elegantly in Haskell using at the fold L function so this gives you a glimpse of how expressive writing ZK snarks can be in high school and building on this idea we're able to implement fairly sophisticated things in house in in key lung using very few lines of code so this is an example of proving Merkle tree membership and keylong in uh in nine lines of code okay so getting started with key lung is actually very very easy we have a GitHub code spaces which there will be a QR code at the end which you can find that'll navigate you to our keylong examples repo and this allows you to essentially hit code then go to code spaces and then there will be a plus icon here to launch a new code space and it'll come it'll pop up with a vs code environment that looks just like this um our our credit card is just down we're just changing it right now so we don't have the plus icon but it's typically here but once you launch new code space you'll see uh yeah you'll have a vs code environment that allows you to essentially play around with with constructing these snarks which you can start off as being pre-quantum and then later compile back to uh down to a postcard improving system so maybe just to run through some examples just get as familiar with with Keeling we have a very simple Echo function here which takes X as a private input and returns X so let's see if I can run this I'm just going to sit down okay so in order to interact with Kilim we can just navigate to the terminal and open a rebel can you hear me does this work yeah okay thanks great and now we're in the rebel and now we can actually start playing around with some of these functions I remember you can do all of this in in the GitHub code space so we can start with gf181 which is the finite field that we've chosen to construct the circuit and you can change the finite fields and this gives you different security parameters so we'll start with gf181 and then Echo and then which is the name of the function and then in qlung the first set of of bracketed parameters is the public input which will leave empty this doesn't take any public inputs and then we can put in a private input three and it will just Echo the private input we can also do something like Square well where this time we will have both a public and private input so we'll go we'll go gf181 Square we'll go three and nine and this will compile it'll essentially assert that the private input was a square of the public whereas if we did something that didn't that wasn't that it would private input that wasn't the square it just wouldn't compile at all so maybe now we can move on to a more interesting example of proving something that we might actually want to prove in the world which is maybe that we're old enough to drink at least in the US and this should actually be proved that I'm greater than or equal to 21 but that's a minor detail okay so to construct a snark to prove this we'll just need a few pieces of data we'll need my birthday uh the num the minimum age or the minimum yeah minimum age that I need to have lived in order to have a drink and then and then today's date and from those three pieces of data we can construct M and N being how old I am and then n being how old I need to be and we just want to prove very simply that n is greater than or equal to and so in key lung we've written a very very simple function called check minimum age and what this will do is it essentially just pulls on like a very simple script let's say this this birthday script that generates you know basically these the the n and n here so here we need to be at least this many days old so we'll go back to the rebel gf181 check minimum age and here it accepts a minimum age as a as a parameter so we'll go I need to be at least this many days old and then no public input and then and then a private input here and this will compile another generator proof for you that you can then walk around with and go to any bar and say hey cryptographically verify that you can crypto graphically verify that I'm old enough to have a drink here and they have no option but to give you a give you uh your favorite drink of course if we if we change the the minimum age to let's say being like 45 years old so I just used my birthday and I'm I'm not quite 45 yet but it just won't compile and so this is a very very simple snark that you know we can essentially put we can put in the hands of let's say like a trusted verified issuer in order to create these proofs for us on or on behalf of us that we can then walk around to different places and prove our age without you know needing to um be embarrassed sometimes maybe about how old you are yeah and that wraps up my talk so thank you very much all for your time I appreciate it yeah thank you [Applause] anyone has questions uh why kilo not Taipei yeah so that was a that was our our Chief Architect was just I think he was inspired by the river in in kilang and felt that there was some connection with with zero knowledge I think he's operating at a higher level than I am in terms of his inspiration but he was inspired very much by Keelan yeah okay how does the performance compare to the existing Solutions yeah yeah great question yeah so we've been over time and very quiet time yeah yeah so typically those are influenced by the number of constraints so the proof of time is is impacted by the number of constraints that you have uh we're competitive with uh with Socrates and and circum most of pretty much all the major dsls have um have benchmarked like a certain number of constraints for certain like implementations and we meet those those requirements so it's less about being like more performant and then uh We've we've shifted our Focus to being like easier to use and having this flexibility to uh to post quantum mm-hmm yeah thanks any questions yeah so um basically the developer don't need to um write a call in like uh rncs or other constraint system form right because the circum have to write inorences per my answer sending yeah so yeah also it's kind of hard to hear um was the question sorry do you mind repeating the question I'll just come closer oh yeah so my question is um with kilong then the developer don't need to write the code in the R1 CS or other constraint system compatible form right I see okay yeah yeah one sec let's go back up to it okay so the question was whether uh whether developers need to write in the actual intermediate representation which r1cs is one IR there's also a planckish ir and then so the answer would be no they can write in a high level language such as kilang and this is typically the case for for most languages you typically write in some high-level circuit description language such as like Cairo Socrates circum and then it gets compiled down to the IR so all of the work is being done just at the at the high level language level does that answer the question or yeah okay cool thanks uh okay uh I'm curious about how large is the differences between free Quantum uh proving system and post content improving system I mean that uh keylong is amazing that providing some useful Syntax for riding the circuit then circum or other language so I'm curious about uh how is it much worse to a uh creating a another compiler to deal with the IR and then compel the i o into post content cryptography then just creating a new language such as kilo okay yeah I think there's a few ways I could go about answering this um first of all there are trade-offs when you use postcard improvers they typically are more expensive they take more time to uh to generate and they're also typically larger so that's one of the things that you deal with and then I I think there's like a part of your question I think well that at least I understood which is like are there trade-offs in the IR and basically the efficiency of compiling to like different IRS based off of of of of of which prover you want um and at least in the opencl architecture there are there's like an intermediary phase here where where after your circuit description goes through this essentially a routing software to the appropriate adapter it'll go through a series of optimization passes specific for that for that for that prover so for example there would be an r1cs specific Optimizer and then a plonkish Optimizer um and yeah I honestly can't say whether the like optimization or optimizing constraints for for different constraint systems seems to be like kind of where the state of the art research is right now at least in the compiler design so I'm not aware of like how competitive this solution is to um to just like native optimizers but I would imagine that like in this in in this design the idea is just to implement these state-of-the-art Optimizer in this in this stack here so it should be competitive yeah okay let's let's thanks to Chris again cool thank you [Applause]