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. I’ll assume that readers are familiar with the standard notions of soundness and knowledge soundness.

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 knowledge soundness and special-soundness both imply WEE.

Motivation: proofs from knowledge soundness are 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.