Composable proof transcripts for public-coin arguments of knowledge

Merlin requires 'static protocol labels, which normally originate in Rust code for various reasons, ala session type. Yet, the label passwd to Transcript::new could reasonably originate outside Rust code when protocols are designed to be composed.

https://github.com/paritytech/schnorrkel-js/issues/12#issuecomment-507547778

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

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 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.

This PR is to fix the compilation errors on nightly because #[zeroize(drop)] is no longer supported with newer versions of zeroize. It is now replaced by another trait ZeroizeOnDrop.

One question: what is the MSVC plan for merlin?

version 3 of the merlin crate is merlin-ng effectively. I think this crate should be called merlin-og? or we could ask him nicely to yank and republish under merlin-ng... this is the joys of gits decentralisation meeting crates.io's centralisation...

Fixes #58. The transcript bytes appear to always be written in little endian, even on big endian systems, due to the byteorder encoding wrapper functions, but we should probably update the github action from #59 that tests on powerPC to use the debug-transcript feature to check that.

External RNG

We are working on porting w3f/schnorrkel to embedded device. Merlin is one of its dependency. Embedded device always has hardware random source which is from physical noise, very secure. Meanwhile, some functions like thread_rng in rand or rand_core could not be compiled in no_std environment on thzumbv7m-none-eabi or similar. So we added a function with extra para to make it is possible to use external RNG in transcript.rs

pub fn finalize_trng(mut self,trng: &[u8]) -> TranscriptRng
    {
        let mut random_bytes = [0u8; 32];
        random_bytes.copy_from_slice(&trng[..]);

        self.strobe.meta_ad(b"rng", false);
        self.strobe.key(&random_bytes, false);

        TranscriptRng {
            strobe: self.strobe,
        }
    }

To see how the embedded porting works, you could ref wookong-dot-schnorrkel

In the current doc on Transcript Protocol:

"A sufficient condition for the transcript to be parseable is that the labels should be distinct and none should be a prefix of any other."

"parseable" is only relevant with debug feature on, right?

I don't quite follow why those labels needs to be prefix-free of each other.

Appreciate the clarification in advance!

I was confused when I encountered

/// Strobe R value; security level 128 is hardcoded
const STROBE_R: u8 = 166;

R=166 means that 166 bytes=1328 bits can be extracted (the rate) from the Keccak state. That leaves 34 bytes=272 bits of sponge capacity. These numbers seem weird to me; especially since intuition would tell me that 128 bits security would mean 32 bytes of capacity and thus a rate of 168 bytes (or even c=16 bytes and r=184 bytes).

Am I forgetting something? I'm not a Keccak expert!

I think 0.3 is basically a 1.0 prerelease.

Stabilization checklist:

• [x] have some people look at the design
• [x] use it for some stuff to make sure there's not a bad API
• [x] bikeshed the function naming a little bit
• [x] fix #22

In retrospect, the transcript functions could have been better-named. For 1.1, I'm planning to rename them and leave the old ones in place as #[deprecated] functions.

Renaming:

• commit_bytes -> append_message (avoids concept collision between the transcript layer and some protocol's commitments)
• commit_witness_bytes -> rekey_with_witness_bytes (makes rekeying explicit)

These traits permit using a Transcript as a key in a HashMap or BTreeMap, which permits handy optimizations, such as in conjunction with pairings. These do leak state to the caller of course, but if that's a concern then they could operate on only the first 32-64 bytes of the state.. or Hash could include its own siphasher invocation, and the others could be ignored. It's a nice feature of strobe that the state contains almost only the 200 byte keccak state, so siphash can usually process it faster than ant relevant from which the Transcript was created.

Recall that tests currently fail on bigendian machines, as per https://github.com/dalek-cryptography/merlin/pull/60#issuecomment-697043828. I already have a STROBE implementation that works on big-endian machines, and has an extremely similar API. This PR simply uses that as a drop-in replacement.

Hey!

We're currently running into the following (as expected) on big-endian machines:

   |
10 | / compile_error!(
11 | |     r#"
12 | | This crate doesn't support big-endian targets, since I didn't
13 | | have one to test correctness on.  If you're seeing this message,
14 | | please file an issue!
15 | | "#
16 | | );
   | |__^

error: aborting due to previous error

error: could not compile `merlin`.