This is a sketch of a design for a STROBE-based RNG for use by the prover to generate blinding factors, etc. It's intended to generalize from

- the deterministic nonce generation in Ed25519 & RFC 6979;
- Trevor Perrin's "synthetic" nonce generation for Generalised EdDSA;
- 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 generation of blinding factors

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 proofs 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, so it would be good to **design a comprehensive fix that applies to Merlin's setting**.

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.

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:

(2) 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).

## Goals

We should provide an API that allows Merlin users to generate randomness which is derived from both the transcript state, prover secrets, and the output of an external RNG, to combine (2) and (3).

In the Merlin setting, the only secrets available to the prover are the witness variables for the proof statement. This means that in the presence of a weak or failing RNG, the "backup" entropy is limited to the entropy of the witness variables. This isn't ideal, since the witnesses may be low-entropy (for instance in the case of a range proof) but I'm not sure what else there is to do.

## API Sketch

This API is intended to allow the following:

```
let mut rng = transcript
.fork_transcript() // -> TranscriptRngConstructor
.commit_witness_bytes(b"witness", witness_data)
.reseed_from_rng(&mut rand::thread_rng()); // -> TranscriptRng
let s = Scalar::random(&mut rng);
```

The method names could be changed, but the workflow is as follows: at any point, the prover can fork the internal STROBE state into a `TranscriptRngConstructor`

.

The prover then runs `TranscriptRngConstructor::commit_witness_bytes()`

, which performs `KEY[label](key)`

. After committing any relevant witness data, the prover runs `TranscriptRngConstructor::reseed_from_rng()`

, which extracts 32 bytes of randomness from the external RNG and performs `KEY["rng"](random_bytes)`

. This consumes the `TranscriptRngConstructor`

to produce a `TranscriptRng`

, which implements the `rand::{Rng, CryptoRng}`

traits.

This design uses the type system to ensure that the prover must commit to witness data before it can request randomness, preventing the prover from accidentally forgetting to rekey the STROBE state.

The API uses method chaining. This is intended to encourage API consumers to fork the transcript and rekey at each stage that they need randomness, by making it easy to get the final RNG without having to create a bunch of intermediate variables. By forcing ownership to pass along the method chain, it also makes the prover-specific code with witness commitments operate differently than the prover-and-verifier-common transcript operations.

Thanks to @isislovecruft for the design discussions.