Merlin: flexible, composable transcripts for zero-knowledge proofs
Zero-knowledge proofs are usually described mathematically as interactive protocols between a prover and a verifier, but implemented noninteractively, so that the final proof can be verified without any input from the prover. This transformation is accomplished by the Fiat-Shamir heuristic, which converts an interactive proof of knowledge to a non-interactive proof of knowledge, by replacing random challenges sent by the verifier with the output of a hash of all previous messages sent by the prover.
Merlin is a small Rust library that performs the Fiat-Shamir transformation in software, maintaining a STROBE-based transcript of the proof protocol and allowing the prover to commit messages to the transcript and compute challenges bound to all previous messages. It also provides a transcript-based RNG for use by the prover, generalizing “deterministic” and “synthetic” nonces to arbitrarily complex zero-knowledge protocols.
In comparison to performing the Fiat-Shamir transformation by hand, this design provides support for:
- natural domain separation with arbitrary label sets;
- multi-round protocols with alternating commit and challenge phases;
- automatic message framing, preventing ambiguous encoding of commitment data;
- automatic composition of proof statements;
- and interactive composition of non-interactive proofs.
Synthetic randomness for zero-knowledge proofs
The prover needs a source of randomness to construct proofs, and bad randomness can be fatal. For instance, in a Schnorr signature, guessing the blinding factor reveals the secret, using the same blinding factor for multiple proofs reveals the secret, and even leaking a few bits of each blinding factor over many proofs can reveal the secret. For more complex zero-knowledge proofs, bad randomness presumably causes worse and more interesting failures.
To address this, Merlin contains a TranscriptRng for use by the prover. This design is intended to generalize from
- the deterministic nonce generation in Ed25519 & RFC 6979;
- Trevor Perrin’s “synthetic” nonce generation for “Generalized EdDSA”;
- and Mike Hamburg’s deterministic nonce construction sketched in the STROBE paper,
towards a design that’s flexible enough for arbitrarily complex proofs.
To generate randomness, the prover clones the public transcript state to obtain a private fork of the transcript, then rekeys the private fork, first with the prover’s secret witness data, and then with the output of an external RNG, before finally generating random bytes. In this way, the prover’s randomness is generated as a PRF of the entire public transcript up to that point, and of the prover’s secrets, and of the output of an external RNG.
In software, the cloning and rekeying is performed by Merlin’s TranscriptRngBuilder, which takes an external RNG to produce a TranscriptRng, making it impossible to forget to rekey and accidentally generate randomness from the public transcript. More information on the design can be found in the TranscriptRng documentation.
A simple example: proving knowledge of discrete log
To see how Merlin works, consider a proof of knowledge of a discrete logarithm in a prime-order group, proving knowledge of some x such that x is the discrete logarithm of P with respect to B.
To implement this using Merlin, the prover commits a proof label to the transcript, then the public parameters B, P.
To generate randomness r, the prover clones the transcript state, then rekeys the cloned transcript with the secret x and randomness from an external RNG. This ensures that the randomness is bound to all of the public data, as well as the prover’s secret, as well as an external RNG, minimizing the risk of weak randomness.
Finally, the prover computes a commitment to the randomness R = r*B, commits R to the transcript, and generates a challenge value c from the transcript, before returning the proof π = (R, s) where s = r + c*x.
To verify the proof, the verifier commits the same messages to its transcript, generates the challenge c, then checks whether R = s*B — c*P. If the prover was honest, s*B — c*P = (r + c*x)*B — c*(x*B) = r*B = R, and the proof verifies correctly.
Although the verifier’s computation is different from the prover’s, both the verifier and the prover perform identical transcript operations, so that (if the proof is well-formed) they will mutate each of their transcripts in exactly the same way.
Automatic, flexible domain separation
Notice that in the diagrams above, the thick black line representing the transcript state extends above and below the grey box representing the proof protocol. Passing a mutable transcript context into the proof implementation as a parameter, rather than creating it internally, means that applications perform domain separation by default (by passing a label when they initialize the transcript).
Because an application can commit its own messages to the transcript before passing it to the proof implementation, applications can bind the proofs they produce to arbitrary data, with no changes to the proof protocol. For instance, the discrete-log proof illustrated above can be used as a Schnorr signature by committing the bytes of a message to the transcript. Alternatively, since Merlin transcripts perform automatic framing (via STROBE), an application could sign structured data by committing it to the transcript as a series of structured messages.
Protocol Composition
Passing a proof transcript as a parameter also means that it’s possible to compose proof statements without making any implementation changes, just by passing the same transcript to multiple proof invocations. This performs sequential composition of protocols.
In addition to providing great flexibility, this also improves the implementations of complex protocols. For instance, Bulletproofs make use of an inner-product argument due to an earlier EUROCRYPT’16 paper.
The inner-product proof allows the prover to convince a verifier that some scalar is the inner-product of two length-n vectors using O(log(n)) steps, and it’s the reason that Bulletproofs are compact. Ignoring the actual computation done by the prover and verifier, the transcript operations for the inner-product proof are illustrated in the diagram.
To create a rangeproof, proving that some value lies in a range, Bulletproofs first perform a protocol that reduces the statement about ranges to a statement about inner-products, then run the inner product proof.
Instead of implementing these logically distinct steps as one combined protocol, Merlin allows implementing them as two separate components, with the rangeproof protocol calling the inner-product protocol internally, composing it into the transcript of the outer proof.
And this is actually how the Bulletproofs implementation by myself, Cathie Yun, and Oleg Andreev works. Although the external API only exposes rangeproof functionality, internally, the inner-product proof is implemented completely separately from the rangeproof code, so it can be reused either for rangeproofs or for circuit proofs.
Interactive composition of noninteractive proofs
Finally, because proving and verification operate identically on the transcript state, it’s possible to perform role-switching between the prover and the verifier.
Why is this useful? One really cool application of zero-knowledge proofs is that they allow protocols to be transformed from having possibly-malicious participants, who might not behave correctly, to honest-but-curious participants, who perform the protocol steps correctly, but might try to learn extra information.
To do this, each participant in the protocol constructs a zero-knowledge proof that they performed their step of the protocol correctly, then sends that proof along with the protocol message to their counterparty. The counterparty can verify the proof to check that the message was correctly computed, then proceed with their step, producing a proof that they performed their step correctly, and so on.
If both parties use Merlin, they can maintain their own transcript states, represented in the diagram by the two thick black lines. When one party proves that they performed their step correctly, they mutate the state of their transcript away from the state of their counterparty’s transcript.
But when the counterparty verifies the proof, the counterparty’s transcript state is mutated in the same way, bringing the two parties’ transcripts back into sync. Now the roles reverse, with the next proving phase mutating the transcript again, and the counterparty’s verification synchronizing the transcripts.
Notice that the proof of each step is a noninteractive proof, but because they’re made on the same transcript, they’re composed with all of the proofs from all prior steps.
In this way, as the parties perform the protocol, they each also interactively compose the noninteractive proofs of correct execution of each step into a “proofchain” of correct execution of the entire protocol.
For this to work, the proof system has to be powerful enough to encode the computation of each protocol step in the language of the proof system. But even for simple proof systems, like Schnorr proofs, this is powerful enough for interesting protocols — for instance, the algebraic-MAC anonymous credentials of Chase, Meiklejohn, and Zaverucha. These credentials allow a client to request blind issuance of a credential without revealing its attributes to the server. The client ElGamal-encrypts the attributes and proves to the server that they were correctly encrypted, and the server uses the encrypted attributes to issue a credential and proves to the client that the credential was correctly computed using the same parameters as all other clients. These proofs can be formed using the approach above, sharing a common transcript for both steps.
More complicated protocols may need more complicated proof systems — but thanks to Cathie Yun’s work, soon it will be possible to programmatically define, prove, and verify arbitrary statements using Merlin-based Bulletproofs, which might make this possible for a wider range of protocols, although I’m not exactly sure how practical it would be.
How Merlin works
Merlin is a simple API built on top of a subset of Mike Hamburg’s STROBE. While STROBE aims to be a framework for transport protocols, Merlin has a narrower scope, so it only supports the AD, PRF, and KEY operations. Merlin contains its own implementation of this subset of STROBE, performs no allocations, and should be no_std compatible.
Merlin requires a user-specified label to initialize the transcript. It then constructs a STROBE-128 object with label Merlin vX.Y and commits the user-specified label as a transcript message with label dom-sep.
To commit a message to the transcript, Merlin performs the STROBE operations
meta-AD( label || LE32(message.len()) );
AD( message );and to obtain a challenge, it performs
meta-AD( label || LE32(dest.len()) );
dest <- PRF();To obtain randomness, the prover clones the transcript state, then rekeys the cloned state with witness data
meta-AD( label || LE32(witness.len()) );
KEY( witness );and then with the output of an external RNG (such as /dev/urandom):
meta-AD( "rng" );
KEY( 32 bytes of rng output );At this point the RNG is initialized and fills bytes with randomness by
meta-AD( label || LE32(dest.len()) );
dest <- PRF();More information on Merlin
The Merlin repository is here on Github, and the documentation can be found here. It includes more detailed descriptions of
- the transcript API and how to use it to implement protocols;
- the transcript RNG construction and its design motivations.
I’m planning to stabilize a 1.0 release soon, but until then there are no stability guarantees.
