Struct merlin::TranscriptRng

pub struct TranscriptRng { /* fields omitted */ }

An RNG providing synthetic randomness to the prover.

A TranscriptRng is constructed from a Transcript using a TranscriptRngBuilder; see its documentation for details on how to construct one.

Design

The TranscriptRng provides a STROBE-based PRF for use by the prover to generate random values for use in blinding factors, etc. It's intended to generalize from

1. the deterministic nonce generation in Ed25519 & RFC 6979;
2. Trevor Perrin's "synthetic" nonce generation for Generalised EdDSA;
3. and Mike Hamburg's nonce generation mechanism sketched in the STROBE paper;

towards a design that's flexible enough for arbitrarily complex public-coin arguments.

Deterministic and synthetic nonce generation

In Schnorr signatures (the context for the above designs), the "nonce" is really a blinding factor used for a single sigma-protocol (a proof of knowledge of the secret key, with the message in the context); in a more complex protocol like Bulletproofs, the prover runs a bunch of sigma protocols in sequence and needs a bunch of blinding factors for each of them.

As noted in Trevor's mail, bad randomness in the blinding factor can screw up Schnorr signatures in lots of ways:

• guessing the blinding reveals the secret;
• using the same blinding for two proofs reveals the secret;
• leaking a few bits of each blinding factor over many signatures can allow recovery of the secret.

For more complex ZK arguments there's probably lots of even more horrible ways that everything can go wrong.

In (1), the blinding factor is generated as the hash of both the message data and a secret key unique to each signer, so that the blinding factors are generated in a deterministic but secret way, avoiding problems with bad randomness. However, the choice to make the blinding factors fully deterministic makes fault injection attacks much easier, which has been used with some success on Ed25519.

In (2), the blinding factor is generated as the hash of all of the message data, some secret key, and some randomness from an external RNG. This retains the benefits of (1), but without the disadvantages of being fully deterministic. Trevor terms this "synthetic nonce generation".

The STROBE paper (3) describes a variant of (1) for performing STROBE-based Schnorr signatures, where the blinding factor is generated in the following way: first, the STROBE context is copied; then, the signer uses a private key k to perform the STROBE operations

KEY[sym-key](k);
r <- PRF[sig-determ]()

The STROBE design is nice because forking the transcript exactly when randomness is required ensures that, if the transcripts are different, the blinding factor will be different -- no matter how much extra data was fed into the transcript. This means that even though it's deterministic, it's automatically protected against an issue Trevor mentioned:

Without randomization, the algorithm is fragile to modifications and misuse. In particular, modifying it to add an extra input to h=... without also adding the input to r=... would leak the private scalar if the same message is signed with a different extra input. So would signing a message twice, once passing in an incorrect public key K (though the synthetic-nonce algorithm fixes this separately by hashing K into r).

Transcript-based synthetic randomness

To combine (2) and (3), the TranscriptRng provides a PRF of the Transcript state, prover secrets, and the output of an external RNG, to combine (2) and (3). In Merlin's setting, the only secrets available to the prover are the witness variables for the proof statement, so in the presence of a weak or failing RNG, the "backup" entropy is limited to the entropy of the witness variables.

The TranscriptRng is produced from a TranscriptRngBuilder, which allows the prover to rekey the STROBE state with arbitrary witness data, and then forces the prover to rekey the STROBE state with the output of an external rand_core::RngCore instance. The TranscriptRng then uses STROBE PRF operations to provide randomness.

Binding the output to the Transcript state ensures that two different proof contexts always generate different outputs. This prevents repeating blinding factors between proofs. Binding the output to the prover's witness data ensures that the PRF output has at least as much entropy as the witness does. Finally, binding the output to the output of an external RNG provides a backstop and avoids the downsides of fully deterministic generation.

Trait Implementations

impl CryptoRng for TranscriptRng

impl RngCore for TranscriptRng

fn next_u32(&mut self) -> u32

Return the next random u32.

fn next_u64(&mut self) -> u64

Return the next random u64.

fn fill_bytes(&mut self, dest: &mut [u8])

Fill dest with random data.

fn try_fill_bytes(&mut self, dest: &mut [u8]) -> Result<(), Error>

Fill dest entirely with random data.