Post-Quantum Cryptography: Recursive Aggregation

Transcript

Okay. Hello everyone. Um I'm going to give a talk about um postum. Hello everyone. I'm going to give you a talk about postontum recursive signature aggregation for the be chain. So first of all part of it is uh partially opinionated so only reflects my current personal opinion. uh as Dimmitri explained poson based XMSS signatures is a good candidate to replace BLS which had very nice aggregation properties but uh which unfortunately does not resist a quantum computer.

Um the question is then how to aggregate those XMSS so hash based signatures because we need this aggregation property for Ethereum consensus layer and there are multiple way multiple ways to do it and in this talk we are going to focus on the snark particularly hashbased snark to make it plausibly postquantum. What algorithms do we want to snarkify? Two of them actually. First aggregate which basically proves that you have knowledge of some signatures corresponding to ones in a bit field and

that you have um sequentially verified all the signatures. And when you um create a snap proof of this algorithm, you end up with a small um aggregation proof. And second algorithm merge which which basically consists in aggregating the aggregates. So you can reagregate already aggregated signatures. But doing this we'll have to verify um a snark inside a snark because you need to verify the first snap proof of the aggregate algorithm which is regression.

The question is then how to design an efficient yet simple snark. Uh first possibility would be to have a handwritten circuit but doing this for in particular the merge algorithm is nightmare and possible. So probably more something like a minimal CKVM. You can think of something like KO but optimized for our use case which is allocating signature and which actually could consist in verifying a lot of hashes.

Which PCS to use? Probably we uh first because we has shorter proofs than Fry and we want to target short proofs around 128 kilobytes. And additional advantage of we is that it's a multi-linear primal commitment scheme which is useful because you can um in a f based stack you have to commit to each um column as an as a separate univariate polomial using a multilinear PCS you can commit to the whole air table as a single polomial multilinear and This will additionally help to reduce the proof

size. Uh which arithmetization to use probably air. So algebraic intermediate representation because uh these transition constraints constraints sorry are very natural to represent the execution of an op code. Which field to use? probably again a small field because this will lead to fewer robons in proaton and uh because we would use we a multilinear PCS we would not use the classical univariate questioning in stocks and we can replace this with

sunshe based pop uh and with the help of the univariate skip from angles dream We can totally remove the embedding that you previously had using small fields in the sun check that you have like another that appears after the first one and you can totally remove this this overhead using the uni skip and which field in particular probably collab because the cube map is an automorphism of the multiplicative group and this means that posedon is more efficient and particularly easier to prove. Uh the only drawback of collab is that it has a low to addicity meaning

that you can only commit to you can commit to less data. So you have you cannot prove a snack on a big statement. But if you use an extension degree which is a power of two, you can increase this to addicity. And for instance, if we use a degree 8 extension field, we gain toicity up to two to the^ 27, which is enough to prove a validity of 2 million procedum permutations. An additional advantage of degree 8 for co extension field would be the security level because with a degree four it's impossible even though you have a field

of the size of the order of 128 bits. It's impossible to get this level of security 128 bits. You only get approximately 100 bits of security even with the capacity the conjecture to capacity for the paper um proximity caps in the teleon codes. Actually you you could use the star conjecture but some not something you want to enraine in Ethereum probably uh in terms of ISA probably not risk five. We don't need all this op code to only prove posyons something much simpler probably closer to kro so being able to add multiply and to manipulate memory

uh very few registers for instance k only has three registers PC AP and FP and there is a debate around the memory there are two types of memory read only and readwrite memory readr makes it easier to write a program but is more expensive to prove. So personally I would argue it not 100% sure but I think read only would offers would offer better performance.

Uh we would also need um pre-ompiles uh for our computationally intensive tasks. Of course they don't pre-ompile but we could also we would al potentially also need um a pre-ompile to do the operations in the extension field because in the merge algorithm we need to verify a snark inside the snark and verifying a snark a snark happens in the extension field for soundness reason and so that's why we would have in this part a lot of extension field operation and that's why it's potentially useful to have

pre-ompiles for the extension field ad here is a sketch of a potential architecture nothing fancy main table for the execution tables for pre-ompiles and memory with memory buses aka lookups to communicate information and to conclude to conclude I wanted to highlight a paper by Lev which is an indexed lookup argument. What is an index lookup argument? Basically you have a column containing data and you have another column containing indexes and you want to prove that this third column correspond to the correct indexes. So for instance one here it

corresponds uh but in previous lookups for instance log up GK you have to commit to these three columns uh and then you prove that the lookup is correct but with this recent paper you can avoid to commit to this column and only commit to a column of this size T which is particularly useful when the column T is less is much smaller than the column on the of the indexes which is the case for the bite code because each op code will be read accessed multiple times because of the loops. So for instance if this

column represent the bite code the columns of the program counter and the upper code will be much longer than the by code itself. So avoiding to commit to this one may be interesting for us. Additionally, in Kro you have to commit to numerous boolean columns that represent the logical bits of the op code. And so you would avoid to commit to lots of columns using this index lookup argument. That's it for me and uh here is a link to some implementations related to this topic. Happy to take questions. Okay.

Thank you. [Applause] You said you're like exploring like a custom ISA like do you think it would be something like is doing or I think something something much simpler probably I think we need to take in Spanish inspiration sorry from ko ko is very very simple to understand and to prove follow question like you're doing something custom like what are your projected like timelines of like production? We all we already have this part. We already have um a PCS

implemented with the pron fields. We have PCS is in this room. Um we are petra we sorry and we already have um multilinear p that's able to prove validity of proyons. We can currently do more than 100 actually we could do I know how we could almost reach 200 posaton on the CPU and above a million with a GPU. Uh the thing that is that remains to be done is this part with the execution table and the memory and the lookup. So we have this extra I have a very new question about when

you talk about does it mean that is over? Yes. So does it mean that in some sense it would mean in training a specific because if someone uses baby bear or less prime they would need to emulate cola bear and then they slow down all the others. Yeah, you would in the system we would have over and the pro the proof system over everything. Yeah. Okay. So it's it's in some sense it's which makes sense. It's okay gives advantage to one specific.

Exactly. We would have to choose. Okay. For instance, in in the the um this map which is a a an automorphism baby is to the power seven. So it's much more expensive than yeah I don't know. I think I don't know for but I think if we could avoid the conceptual the conceptual complexity of circle stocks would be

great I guess if we can get enough performance with classical and how about you I think some people left so this is shared confidentially but um the irreducible people have pivoted just a few days ago And they are no longer going to be pushing business as hard. Okay. [Applause]