Post-Quantum Accounts Today: Benchmarking Falcon-512 Verification Inside Starknet's `__validate__`

Transcript

[music] [music] >> I think you you gave the talk already, you know, in in few lines. Okay. So, I'm going to uh uh I digress a little bit on that. So, uh what I'm going to do here is uh we're going to talk about uh the Falcon 512 implementation we have on StarkNet. Uh um mostly the verification part. All right, so on chain. So, uh All right, so let's go. Um So, uh this is the outline of my talk.

I'm going to discuss why uh you know, the post-quantum account works today. It's just a contract swap. Then we'll quickly talk about Falcon 512, what it computes, and what are the five verifiers we built. Uh and then, you know, the numbers, the gas, how many how much computation we can do, and so on and so forth. Then we'll talk about the uh the engineering which makes it fit, again, quote unquote. And then, accounts today migration, and what next, and then we'll stop with the with the um uh with the questions. Uh okay. All right, so as as people have been already talking about uh uh the current quantum algorithm uh

in the current paradigm, Shor's algorithm breaks the uh the elliptic curve or any discrete log problem. So, the the the signature schemes based on discrete log problems are uh vulnerable once the quantum computer comes in. Whereas um the hash-based uh and the lattice-based uh systems are are are supposedly safe for now. Okay. We don't know. I mean, something might happen tomorrow. Anyway. So, uh the idea is uh following Stark Proofs uh essentially uh uses hashes. So, and hashes are considered to be safe. Of Of course, it depends on what kind of hash we're using here.

And uh the the the the signature scheme is not right? So, what we want to do is simply replace the signature scheme, right? Uh with something which is post-quantum, and then check uh uh whatever signature scheme we have got and does it fits in or not. How much does it fit in? What are the cost and so on and so forth. So, this is roughly the idea behind the whole thing. All right. So, uh So, uh as I said earlier, migration is a contract swap, uh not a protocol upgrade, because well, all all the accounts on on StarkNet are essentially uh uh they have a account abstraction, so you can just uh you know, uh swap out the uh signature with the uh

the the elliptic curve signature with the uh Here here we are using Falcon 512, okay? So, that's all fine. So, there's only the the central part which has to be replaced. I mean, kind of, of course, when you're building the signature also, you have to replace that, but on chain, you are basically changing that validate part um and then uh then the whole thing works out, right? So, uh however, the only constraint is when you go on chain, you you basically have some limitations. Uh the limitation is namely that the validation runs before the fee is charged, and then so it's capped at some number of steps, uh which is uh 1 million uh Cairo steps, and uh which uh

roughly corresponds to 100 million L2 gas, okay? So, the verifier has to fit in between both, all right? All right. So, uh we ran this with Falcon 512, uh uh the number of bytes per signature is uh up there. Uh number of bytes per per public key is over there, and then we have the modulus Q, uh which is this number here, okay? Not very big, pretty pretty reasonable, around 2 to the power uh 9-ish something.

So uh not 2 to the power Sorry, that was a blunder, really. Okay, so uh start. Uh so, let's So, basically, why did we choose this? Because it it was selected by NIST in 2022. Uh the standardization is still pending. Uh Yep. So, um Of course, as I said earlier, signing chain stays off chain and the the reference signers use floating point arithmetic, but recently there have been proposals about using fixed integer arithmetic. Okay.

So, so at the end of the day, what is the verification uh which we are talking about? So, verification involves the following. It involves integer only multiplication steps. So, it includes a hash. Uh it includes an NTT, number theoretic transform for multiplying some polynomials. And then a norm check for the security of the Falcon, right? Okay. So, let's move further. So, this is what the signer sends, basically. So, what they do is they have a They have a transaction hash.

Uh Uh they have 40 bytes of salt. Uh Then they hash to point and then essentially um They compute them trapdoors. They send S1 and they drop S0. And well, what you have to do is now you have to pack it inside the uh the the felt, which is the field element of uh of of Stark, which is around 252 bits. So, you pack them nicely and then you send it off to validate, okay? So, now again, there are two ways we can go about it and that's why we have these five verifiers, essentially. So, what you can do is if you send S1,

uh you can also send S1 * X, which we'll call hint. You'll see that in a minute why is that hint important. So, um and then yep, so this is a setup. All right, so uh So, here's the following setup. So, we have C, which is a hash to point, which hashes salt and the message. Then we get S0, which is C minus S1 H. H is a public key. And if we are computing all over that uh that ring there.

And we accept if the the norm essentially is is bounded, okay? So that's the the whole setup. And then there are some some some interesting, you know, uh uh what do you say? Um some representations uh uh here. You can have a look. All right. So where does the entity comes into the picture? So well, uh so when you decode uh the key in the signature, you have to do hash to the point. But if you if you see we have to compute this S1 of uh this S1 of H there. And what what what signer can do actually is they can send S1 plus H, right?

All right. So All right. So what are these five verifiers we are talking about? So essentially it is the the only thing which is going to change is the hash function, all right? So we basically computed things with two hash functions SHA 256, Blake, and Poseidon. And how does it becomes five? Because there are two of them we use hints as well. And for the other for the Poseidon we just went about directly because Poseidon is cheap, right?

Okay. So uh Yeah, so uh What is shared with all of them? Essentially everything else in some sense, right? So you you have you know, one entity domain key, you have 29 cells field elements packed nicely and uh So this is the standard construction used uh And as you can see, ECDSA today is just for 1.6%. So what are these percentages? These are the percentage of the gas allowed the 100 million part, right?

So uh Poseidon with hint is 13.6 uh Blake with hint is 14.4 and so on so forth, okay? So uh the the the the two which are the standards essentially is the Shake 256 because uh uh the Falcon uh the standards the NIST standards uh talks about using the the the Shake uh uh hash function. So uh those are the numbers we should be careful about, all right? So we have some benchmark uh which we ran on the the the the StarkNet foundry. Yeah, so these are our real uh benchmarks.

So as you can see uh for for for the uh for the Shake uh we are having the validate is uh somewhere around 50 million, yeah? Uh whereas the for the gas and the bound the maximum 100 million, All right, so that's that. Sorry. Oh, sorry. Okay.

All right, so yeah um Yeah, so this also gives you the the number of steps we have a description uh breakdown. Uh so you know, Shake uses the the Keccak F uh uh permutation and uh uh these are the what do you say? Uh among that 50,000 or sorry, 50 million roughly uh this is a breakdown for the first one and for the Poseidon that's the breakdown. So as you can see uh Yeah, so mostly um for the first one for the Shake you can see it's really the the hash function which is expensive, right?

All right, so And then we have uh essentially NTT which is slightly expensive as well as you can go back and see uh there is 10% of entity for that one. And, uh, yeah, so essentially Yeah, so we have some numbers for entity as well here. Cool so So, you can basically, uh, look at the, you know, you can you can download the code yourself and and have a look at it. Um, and yeah, I think the Yeah, so that's that's about it. So, in

nutshell, essentially, we have the validate and we we have some benchmarks, on how much time it takes and that's about it. Yeah. Thanks. >> All right, thank you, Vijay. I see we have a question or two here. Feel free to add more questions on Meerkats. Okay, first off here, we have, um, first question, how does replacing SHA-256 with Poseidon affect Falcon security guarantees?

>> So, um, Poseidon is not studied as well, right? While a SHA is, so uh, I I think, uh, changing with Poseidon does not conforms to the to the to the NIST standards. Um, I mean, we haven't found any any bug or anything, but, uh, but but that's that's where the things are. Yeah, so there are some implementations uh uh uh where where people have, um, like people are only talking about Poseidon for that matter. >> Great. Okay, and next question we have here is are we moving towards a world of AI-native cryptanalyst cryptanalyst analyst analyst versus AI-native

cryptography, i.e., humans not in the loop? >> I'm actually too naive to even talk about this. Yeah, I I think AI is changing every day, you know, so so I I would not I would not, uh, you know, make any statement formally, but informally speaking, yes. You know, they are getting better and better. Like the AI is getting better and better and then with some little bit of input from humans, it's actually I mean, we all know what's happening, you know. Well, I mean, even hard problems like you know, Navier-Stokes is actually very close to, you know, So, I don't know. I mean, >> It is a tough question to answer.

How can we protect Falcon 512 private keys against implementation attacks? >> So, right now, whatever I've implemented is is a toy problem, really, right? I mean, I mean, something needs to change definitely, right? Like we have 100 million gas and there is barely two or maybe, you know, two two signatures which can fit in. So, right now, even talking about you know um the hardcore attacks is is kind of slightly naive, you know, um but Yeah, but this is something we can study.

Yeah. So, I don't have answer for this because this is like right we are right at the at the, you know, I would dare to say at the at the at the border of cutting edge. Yeah. >> Got it. I mean, Def Con audience here asking the tough questions. That's all I can say. Okay, I think we got another one here. Can Falcon 512 and ML-DSA DSA coexist in a hybrid authentication architecture? >> Sure, but I mean, definitely they can because as you can see, the StarkNet is is essentially a you know, the the accounts are smart contracts, right? So, you can actually say whatever logic you want to use for, you know,

for for for for for authentication. Although people are like people like Dan Bernstein are they are talking about hybrid with ECDSA and and some lattice-based stuff. Not just two different lattice-based stuff. But anything can be done. Yeah, yeah. So, >> Great. Okay, that looks like that was the last question. So, we'll be back in a couple of minutes and please give another round of >> [music]