Notes on Witness-extended Emulation

I recently came across some papers that were using the notion of witness-extended emulation (WEE). This is a term that I first encountered a while ago when first learning about Bulletproofs but that I had ignored as it was “too technical for me” at the time. This article is a summary of my recent notes on witness-extended emulation and why you should not prove it directly.

The main conclusion is that witness-extended emulation is helpful to analyze protocol composition but is more complicated than knowledge soundness. It should never be proven directly since conceptually simpler properties like Damgård’s knowledge soundness and special-soundness both imply WEE.

Background: Damgård’s knowledge soundness

The literature that introduces witness-extended emulation uses a definition of knowledge soundness that was popularized by Ivan Damgård. This definition is slightly different to our usual definition of knowledge soundness and is likely not equivalent. I’ll give a quick explainer of what the property is and how it differs from our usual definition. Readers familiar with both notions can skip ahead to the next section, knowing that we always refer to Damgård’s definition.

At a high level, Damgård’s definition states that we can always extract a valid witness (in acceptable time) from any prover that has a high chance of convincing the verifier. Formally, this property can be expressed as in the following excerpt of Damgård’s lecture notes on Sigma protocols:

This is not the same as our usual definition of knowledge soundness which state that “the probability that the verifier accepts and the extractor fails to output a valid witness is negligible”. For example, an extractor that has a fixed failure probability against all provers can satisfy the usual definition but not Damgård’s.

We know that Damgård’s knowledge soundness implies the knowledge soundness we usually work with, however the opposite direction is unclear. Therefore, the rest of this article will exclusively refer to Damgård’s defintion of knowledge soundness in order to remain compatible with the witness-extended emulation literature.

Motivation: composing proofs of knowledge is hard

Witness-extended emulation is a notion that was defined to avoid a “technical difficulty” that arises when composing arguments of knowledge. As noted by Lindell [Lin03], we may find ourselves unable to prove the security of a wider, composed system if we just naively use the guarantees given by knowledge soundness. The excerpt of [Lin03] below explains why this is the case:

In short, the difficulty is the following. To prove security of the overall protocol, we need to describe an expected polynomial time “simulator” that correctly reproduces the views of all parties in the protocol without knowing any secret information. To do so, the simulator will internally make use of the “extractor” defined by the knowledge soundness property. However, if we are not careful, the simulator’s running time will depend on both the malicious prover’s success probability (to obtain the necessary executions of the argument) and the extractor’s run-time (to obtain the witness). This double dependence might lead to simulators that do not run in expected polynomial time.

After this passage, Lindell also makes it clear that we are not doomed — the technical difficulty above is not an inherent problem:

This technical difficulty was solved by Goldreich and Kahan in [20] and therefore there is no inherent problem here. However, their techniques are complex and thus applying them every time we wish to use a proof of knowledge as a subprotocol is cumbersome. Our goal here is therefore to present a general lemma that will enable the use of proofs of knowledge as subprotocols without requiring any complicated analysis. Rather, the analysis (indeed using the techniques of [20]) is needed only once in proving the lemma.

Introducing witness-extended emulation

Witness-extended emulation is almost a tailor-made property for proving the security of such wider systems. It essentially requires that there exists an expected polynomial time emulator that “outputs the information required by the simulator to continue the simulation of the larger protocol” [Lin03].

What is more important than the definition itself, is lemma 3.1 in [Lin03]: knowledge soundness implies witness-extended emulation. The proof uses the techniques of Goldreich and Kahan but in a generalized context. By doing this, Lindell applies those techniques once and for all, allowing us to never have to worry about WEE if we can prove knowledge soundness.

WEE from simpler properties

So why, you might ask, do we have papers proving witness-extended emulation directly? This is a result of the tools that were available at the time.

Proving knowledge soundness is not always easy. The go-to method was to prove that a protocol has special-soundness and then, using a technical tool known as the forking lemma, we could show that the protocol has knowledge soundness. However, for a long time special-soundness was only defined for $1$-round protocols and required to produce a witness from exactly $2$ branching transcripts. Protocols like Bulletproofs and its predecessor Bootle-proofs did not meet those requirements and therefore resorted to proving witness-extended emulation.

The notion of special-soundness was extended in [ACK21] to multi-round protocols with arbitrary numbers of branching transcripts for each round. They also show that multi-round special-soundness implies knowledge soundness, and therefore implies WEE.

Conclusion

Witness-extended emulation is a useful notion to show that our arguments of knowledge can “play nice” when composed in wider protocols. However, we never need to prove it by hand: the heavy lifting has been done for us, we only need to prove knowledge soundness or special-soundness.

A more concise version of this whole discussion is given in [ACK21]:

What about non-interactive proofs? It is important to note that everything discussed so far only applies to interactive protocols. Studying non-interactive protocols obtained from the Fiat-Shamir transform requires further security notions.

Acknowledgements

Thank you to Michele Orrù for pointing out that the original version of the article missed the difference between knowledge soundness (“the probability that the verifier accepts and the extractor fails is negligible”) and Damgård’s knowledge soundness (“there exists an extractor that always succeeds against provers that have high acceptance probability”). All the results mentioned about WEE only apply to the latter definition of knowledge soundness.