Replacing the FiatShamirRng with Merlin?

[hdevalence]

Currently Marlin includes its own FiatShamirRng which uses chacha20 and a generic Digest function (instantiated with I think blake2s).

Would you be interested in a PR that replaces it with Merlin?

In contrast to the existing implementation, this provides more secure prover randomness generation, allows binding Marlin proofs to arbitrary structured application data rather than just a single domain separator string, or to transcripts of other proof protocols, and potentially makes the implementation slightly cleaner (although the FiatShamirRng API is already pretty reasonable). It also simplifies the (cryptographic) dependencies, as rather than relying on the security of both chacha20 and blake2s (or some other hash function), the security relies only on keccak-f/1600.

I would be happy to create a PR for this change but only if it's one that you'd actually want.

[burdges]

At minimum some Rng and rand could become RngCore and rand_core in both marlin and poly_commit, which simplifies reading the code.

I think merlin has stayed rand_core 0.4 (rand 0.6) so doing this doubles the rand dependencies, although merlin's own rand dependencies could be upgraded.

I do not understand all the code of course, but it appears marlin only uses FiatShamirRng for actual Fiat-Shamir transforms, aka challenges, never on anything using system randomness. Right now, merlin's challenge methods have no RngCore implementation. Also, merlin's TranscriptRng incorporates system randomness, which makes it unsuitable.

I do think merlin's challenge methods could replace your own RngCore, but this would become some larger change across at least both marlin and poly-commit. It's possible you've some direct Rng usages around that'd benefit from being instantiated with merlin's .build_rng().finalize(rng) etc., but maybe more in poly-commit, not sure.

I believe strobe-rs removed all the Vec usage and now works without std, so you could use STROBE directly. Also, one could define some STROBERng that maybe works to merlin's TranscriptRng, but starts from an arbitrary STROBE state without the system randomness. At first blush such a STROBERng looks like the minimal change.

[Pratyush]

@hdevalence Thanks for bringing up this issue. Yes, currently I'm not too happy with our custom hand-written framework for generating FS randomness, but the reason we haven't switched away is that we want to write a R1CS gadget for the marlin verifier, and it's not clear to me how to me how to write a constraint system with custom SNARK-friendky hashes for Merlin.

Maybe if one could abstract away the changes behind a trait or something, it would be easier?

[Pratyush]

@burdges yes, I should minimize the dependency down to rand_core. Do you want to open a separate issue for that? If not, I can do that. Thanks!

[burdges]

Sure: #6 arkworks-rs/poly-commit#2

Afaik, anyone using merlin or strobe-rs uses an extension trait anyways, even when only doing trivial stuff: https://github.com/w3f/schnorrkel/blob/master/src/context.rs#L46

If you abstract enough for SNARK-friendky hashes then would you still use RngCore (Rng) the same way between marlin and poly-commit? Or would you need some interface that constrains the amount or type of output? You cannot constrain the amount of output needed in poly-commit maybe, but maybe you'd have special more efficient types?

[hdevalence]

@Pratyush Wanting to be able to write an R1CS gadget for the Marlin verifier is a good reason not to use Merlin, because Merlin is designed only for the "machine model" and isn't intended to be used in R1CS. It would be nice to have an R1CS-friendly Merlin-ish construction for exactly this kind of case but it doesn't exist as a drop-in right now, so it's not useful for this issue.