ZK14 - Origin Tags: Dynamic Detection of Fiat-Shamir bugs in complex systems - Innokentii Sennovskii

Transcript

Uh hi. Yeah. So my name is Inente. I'm head of security at Labs and I'm going to talk about a mechanism that we've created to detect some of the uh vulnerabilities that often arise when we create uh fatimir U based systems. So let's dive in right away into most basic interactive protocol. Let's say we are trying to prove uh the knowledge of uh the discrete logarithm in some uh secure group. Uh the way this usually happens is the prover generates some sort of uh secret uh random scaler car then commits to it, send it to the verifier, receives

a challenge from the verifier in return that the verify is supposed uh to generate uh randomly and then utes a function of that challenge, the original uh private key, the original secret uh and uh the original scala that it created in the first round. Then uh it sends back uh this the result of this function and the verifier checks that the arithmetic for the scalers and the exponentiated uh elements holds. So in this case the verify generates the random challenge sends it uh to the prover to convert this to an non-interactive

uh uh to a non-interactive proof which is needed for most of the blockchain use cases because we can't have a verifier who is completely online all the time. Uh we perform the fiat transformation. I'm not going to go into the whole random oracle model. In practice, what we usually do is we use a secure hash function with which uh into which uh we put uh various parameters of the system and usually in addition to uh the commitment to the random uh scala k to uh to which we commit in the first round some additional message for example so

that uh we can instantiate that this proof happens under certain conditions for example I am proving something on this day in Rome uh on the 7th of May and somebody else shouldn't be able to use it or under different circumstances. So the prover uh computes this hash uh and generates the challenge uh in this way from the hash. Then it uh finishes the protocol as if it was talking to the interactive uh verifier and sends all the necessary information to the ver verifier. Once the verifier can then simply recomputee the hash, recomputee the challenge and use it to check the correctness. So in practice there are uh many things that can go wrong. Uh so the

first most basic thing is you can forget the message. Uh if you forget the message then it means that you have created a proof which when sent on the network or when published can be easily re uh reused by anybody else. So I proved the my knowledge of the discrete logarithm once. Somebody else used the same proof because it's non-interactive. It's not bound to any conditions and they can prove that they know the discrete logarithm uh without actually doing any work. Uh an even worse case is if we forget to commit to the if we forget to uh add the commitment uh to the nons uh scaler into the hash. That means that the challenge

is now completely deterministic. Um and the malicious prover can basically uh ignore it. uh use the information from this deterministic u from this deterministic challenge and create such parameters that would completely break the scheme without uh actually u having any knowledge of uh the public key. So you basically so the malicious uh proofer can basically go and set such parameters that uh this signature this non-attractive protocol holds without any knowledge and uh there were a lot of examples of fiat mirror attacks in the previous

years. So for example for the last four years every year there have been published attacks. In 2023 there were uh several attacks on various proof systems such as bulletproofs uh long specifically on uh various implementations. Then in 2024 I think at uh the ziki summit actually there was uh there was a presentation on the last challenge attack where uh fiat was implemented incorrectly within uh a particular plon instantiation and the batching challenge was computed incorrectly in 2025 there was a funky free uh vulnerability and uh the day before I submitted this presentation uh I think published uh several attacks on

uh six zkms with various vulnerabilities uh in famil implementations. There are a few reasons why this keeps happening especially in the modern systems. So the first is modularity. Right now to develop something you have to quickly be able to exchange components. For example, there is a new commitment system that is more efficient like where comes out. You want to uh take out your pre-existing uh polomial commitment system and put in a new one. Sometimes when you're doing that you end up with mistakes. Um the second is rapid development because we are uh instead of uh trying to create one uh secure specification and then implement it

correctly I don't know like for ECDSA uh let's say we have uh proven systems that are evolving constantly uh there's rapid development uh there's no specification it's very hard to basically write out uh the whole uh layout of the full protocol uh which means that it is hard to catch these in a paper. Uh and last thing is that there are no uh well there are very few uh potential detection mechanisms. So for example there are uh special frameworks such as Merlin and decree which help but they basically rely on uh either def the developer completely defining the protocol uh beforehand

which makes it harder uh to which makes it uh much harder to use modularity or uh and uh they also rely on the developer not leaving out any data because like every uh submitted value has to be submitted directly into the transcript with them. Uh which means uh that if somebody just decided to compute something on top of uh uh the values that they didn't put in the transcript or they just forgot to put something in the transcript, there's no way uh that this can be caught. Uh obviously this kind of complexity also affects uh the adject network because we have a very

complex we have a very complex system uh with lots of recursion. So for example we have several layers of application circuits and kernel circuits being recursively folded um with uh special speed up mechanisms for recursive folding. So all of the elliptic curve operations for example go into a special uh elliptic curve operation Q. Uh then at the end of all of these recursion we have a special hiding kernel that now uses zero knowledge. Before that zero knowledge is not being used all the uh elliptic curve uh operations then go into a special VM. uh that is done not on the main curve that we're using uh

BN254 but on a special cycle curve that proves the operations and then we go into a special circuit that proves the correspondence between what is happening in ECCVM uh all of those operations and the original uh OPQ that is in BM254 which is the translator and all then from all of this we get one single proof from multiple components and even at uh recursive uh recursion step. We also have several components. So we have the basic hyperplon uh version with uh lookups which is called oink uh internally that goes through the sum check and then we use hypernova to

accumulate the claims uh and uh to to accumulate the claims and eject them into the next uh step of recussion. So tons of components and this basically creates a recipe for disaster for our system because well one we're using recursive verification on the client. There is no training wheel. There's no way for us to check uh that somebody hasn't injected something malicious there. There's huge modularity with different components some check uh hypernova. Then we have deferred uh elliptic curve operations that go into the ECCVM and the translator. There are many flavors. We have the ZK sum check.

We have the non-ZK sum check. Uh then we have two different curves that we use and there are special protocols like ACCVM translator and merge protocol to actually bind individual ECU operations and pull them into this whole queue that is getting improved in the end. So uh we decided that we need to do something to catch these kind of issues uh within and the first thing that we decided to do is to make a single recursive transcript. Uh the basic idea is that we are not injecting values one by one into it. So instead of sending uh for example by one a commitment to uh witness uh wire uh you just take the whole proof as field

elements and you send it to the recursive transcript and then when you want to receive on the verify side an element you actually call receive and it automatically adds that to the buffer for the hashing uh for the future for creating challenges and gives you the uh element that you want to use in an appropriate format. That means that every time that we ask for the challenges, all of the previous data uh is being used for the hashes. It means that there can't be a situation where we are rehashing and we forgot uh some previous element. Uh unfortunately this obviously doesn't protect against all the attacks. This is a very simple uh architectural

uh choice. uh and especially because we are using recursion there can be such simple things as okay the developer forgot to use uh the transcript let's say and decided to recomputee the a particular batching challenge uh natively and then reinserted as a witness into the circuit. So for example, we have two commitments uh that go into the transcript and then the challenge is recmputed separately just using their native versions uh instead of and then reing injected instead of uh using the challenges from the transcript. And obviously we'd like to catch this kind of attack because it's one of the most basic ones. So the thing that we decided to do is to add additional information into each of the

elements that we use when we're describing the algorithm of uh the recursive verifier. So let's say we have a special element field that represents field operations. We're adding the tag there uh for all the operations on various for the group operations like for example the cycle group that uh represents grumpkin or for non-native operations uh like big field uh we have this field called tag which represents some information about uh the element every time we do any arithmetic on these elements we merge the tag so the new tag is the result of the previous ones any arithmetic automatically does is the developer doesn't have to think about

it. So what we can do is then create a set of rules that will simply detect uh the most basic problem. So uh the at stage one of uh the origin tag mechanism we add the information whether this particular element is supposed to be a constant. So this is either uh an element that is not even injected as a witness uh into the circuit. it is automatically put into the selectors. Uh let's say uh whether it is a free witness, it didn't originate from the transcript at all or whether this uh element was ejected was uh taken from the transcript. It means that uh it is either a challenge or a value that was

uh taken from the transcript and takes part in the hash and takes part in the whole regressive verification. And then we have several rules. Whenever a constant operates with a different element, it preserves the tag of that element. If we have two free witnesses operating, we get a free witness. And if a free witness operates on an element received from the transcript, then we immediately generate an exception because this shouldn't be happening. So this immediately protects us from this most uh basic problem. When uh two elements from the transcript uh interact, that is completely okay. Uh so as a result we have a mechanism which immediately solves the issue uh in uh the uh first attack. So we have a

commitment that is derived from the transcript. We have a challenge that is uh completely independently created as a free witness. Yep. Uh we try to combine the tag from the two and as a result we get an exception which prevents us from making this mistake. So uh obviously there are some other attacks. uh for example uh a lot of the problems in fiat shamir happen uh if uh we have two separate subprotocols let's say uh one of the issues that can arise is that the challenge that is used for batching some of the information is derived just from one of the subprotocols like in this

case we are talking about uh plon as a result of the recursive plon verification you usually end up with two group elements which should be used for pairing. Um you can go and batch uh two different recursive plunk proofs. So you have four elements you can batch them so that you end up with uh two pairs. Once again uh one of the vulnerabilities uh that I have seen in the past is that the batching challenge is generated just from the last one of them. This means that the uh malicious prover can simply change uh the values that are derived from the first uh element uh from the first proof in such a way that the whole proof uh

holds and the result of batching uh is considered correct by the recursive verify. uh to detect this issue we add additional information into the origin tags which basically tracks which transcript uh these uh values are descended from. So if you are instantiating a different recursive transcript that uses completely different data uh then it will have the ID of that transcript and whenever values from two different transcripts from two different fiat mirrors meet we immediately throw because why is this happening? Why are you using for example the challenge that belongs to one on the other? This is ripe for a vulnerability.

And as a result, when we're trying to merge uh the tags from two different uh plon uh uh recursive plunk verifications, this is going to throw and this is going to protect us. Um the last thing that the origin tax uh can protect against is uh the uh the attack that uh is also quite widespread. I think um in the case of the last challenge attack and in the case of the plunky pre vulnerability, one of the issues was that the uh batching challenge uh was derived not from uh the end uh not at

the end of the protocol but uh right after the commitments uh to the wires. So after that you get the evaluation of the wires and you apply the batching challenge to the evaluations uh even though the batching challenge was derived before those which means that you can provide such evaluations that will always pass your further checks. So to pro protect against this uh we've extended the protocol with round provenence. Basically we have a special field uh which is 256 bits where the lowest 128 bits represent that this value uh is derived from some value in

the round uh that in the round with this number uh that was submitted by the prover. The higher uh 128 bits show that this value has uh in its history uh of uh derivation a challenge from the same round. Then we can uh add uh a mechanism that checks that whenever we apply a challenge the maximum challenge round in this uh particular uh value is more equal than the maximum uh submitted round. That means that we are basically not applying a challenge to a value that is uh that was uh submitted in the later round. As a result, when we're trying to

combine uh a challenge from the uh from the pre previous rounds, we immediately get a throw and this protects us from this batched uh challenge attacks. There are a few problems even with uh these mechanism. One is that all of the detections still have to be uh manually handled. There are some uh false positives such as for example the last uh step of the KCG is when you create the quotient. So this is the last submitted value. There are no challenges after that which means that we're when you're computing the recursive verification of KCG this round provenence is going to fire off and the developer has to go in and say okay this

is a false positive this is uh something we can ignore across our code base uh across the Aztec uh packages uh codebase uh there are 10 highlevel and 25 lowlevel uh false positives that we had uh to get rid of But uh so there is some work but it basically has to be done once and then you are uh just continuing using it. It also doesn't protect against fundamental logic parts obviously. So if your protocol is uh incorrect it can't really uh help you and uh a reviewer can uh treat a positive as a false positive unfortunately. So you can't really protect against that only but maybe uh

pushing it into an LM. So yeah u to summarize uh fiat is hard to implement correctly. Uh it is possible to create automated detection that is uh going to help you find these issues. It doesn't defend from all the bugs. There still it still needs some oversight and developers can still uh make mistakes. Uh but it does help. Uh, I'd also like to thank Luke, Sergey, and Lucas for their help with the mechanism. That's it. Great. So, thank you very much. Have we got any questions for the moment?

No. Okay. Yep. One over here. I think I'm closest race. Um, Fat Shmeir has been around for so long. Um, do you have any insights into um what makes it so like what makes it so hard to implement correctly? Um, and and is there any hope of meaningfully uh moving past that?

Well, I think right now we are creating protocols which are huge and just created from many scraps basically, right? We are pushing a lot of stuff together. We are not usually formalizing how it interacts. There's no single proof usually for the whole protocol. So as a result it is hard uh to check and then people simply make mistakes anyway. Uh so some value can be just forgotten. you're not really checking that the code 100% fits the specification. So it's just a huge complex thing. So it's easy to make a mistake. So I don't know how you can fix it completely unfortunately.

>> Make no mistakes. Cheers. >> Thank you. >> I didn't quite understand how is difference between this how is this difference from Maryland like um incre you're adding tag at every step right >> yes all the interactions so you are adding to values it will immediately show you uh the issues yeah and this is this doesn't have a formalization of the protocol so it for any transcript that you use you take out the values for example out of there you start using it with a different value that is not connected to this at all uh it will trigger uh an exception

>> so each operation you do attack. >> Yes. All it's not just the uh original elements that just exit the transcript. All the verification or the arithmetic every time uh computes the uh the conjugation like of those tags >> and then tag has all the input to that operation. >> Uh yes. So it basically every time it computes from the previous ones a new tag and and it sees oh is there a violation on this one or not >> and and uh so you don't really like this is automatic like you write and then somebody like there's a compiler that take the current

code and add the tags step to it right >> uh it's just part of the type system our recursive verification is written out as uh uh insircuit types in C++ and so you just do a plus b and automatically under the hood those >> yeah the compiler you understand thank you very much >> okay any more questions no okay thank you very much in Kenti