Composable proof transcripts for public-coin arguments of knowledge

Related tags

Cryptography merlin
Overview

Merlin: composable proof transcripts for public-coin arguments of knowledge

Merlin is a STROBE-based transcript construction for zero-knowledge proofs. It automates the Fiat-Shamir transform, so that by using Merlin, non-interactive protocols can be implemented as if they were interactive.

This is significantly easier and less error-prone than performing the transformation by hand, and in addition, it also provides natural support for:

  • multi-round protocols with alternating commit and challenge phases;

  • natural domain separation, ensuring challenges are bound to the statements to be proved;

  • automatic message framing, preventing ambiguous encoding of commitment data;

  • and protocol composition, by using a common transcript for multiple protocols.

Finally, Merlin also provides a transcript-based random number generator as defense-in-depth against bad-entropy attacks (such as nonce reuse, or bias over many proofs). This RNG provides synthetic randomness derived from the entire public transcript, as well as the prover's witness data, and an auxiliary input from an external RNG.

More details on the design of Merlin and how to use it for proof systems can be found on the Merlin website.

Features

The nightly feature is passed to clear_on_drop; it may be replaced with a no-op in the future (since clear_on_drop is an implementation detail).

The debug-transcript feature prints an annotated proof transcript to stdout; it is only suitable for development and testing purposes, should not be used in released crates, and should not be considered stable.

An example of an annotated transcript for a Bulletproof rangeproof can be found here.

About

Merlin is authored by Henry de Valence, with design input from Isis Lovecruft and Oleg Andreev. The construction grew out of work with Oleg Andreev and Cathie Yun on a Bulletproofs implementation. Thanks also to Trevor Perrin and Mike Hamburg for helpful discussions. Merlin is named in reference to Arthur-Merlin protocols which introduced the notion of public coin arguments.

The header image was created by Oleg Andreev as a composite of Arthur Pyle's The Enchanter Merlin and the Keccak Team's θ-step diagram.

This project is licensed under the MIT license.

Comments
  • Allow Transcript::new labels to come from non-rust code without leakage, UB, etc.

    Allow Transcript::new labels to come from non-rust code without leakage, UB, etc.

    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

    opened by burdges 14
  • Provide a Transcript RNG which generalizes synthetic nonce creation

    Provide a Transcript RNG which generalizes synthetic nonce creation

    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.

    opened by hdevalence 8
  • `#[zeroize(drop)]` is deprecated in `zeroize`

    `#[zeroize(drop)]` is deprecated in `zeroize`

    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?

    opened by weikengchen 5
  • the package name seems to need to change?

    the package name seems to need to change?

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

    opened by gilescope 5
  • Remove big endian compile error

    Remove big endian compile error

    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.

    opened by isislovecruft 5
  • Add external RNG input

    Add external RNG input

    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

    opened by chesterliliang 5
  • [Question] prefix-free requirement on labels

    [Question] prefix-free requirement on labels

    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!

    opened by alxiong 4
  • STROBE_R = 166

    STROBE_R = 166

    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!

    opened by rubdos 3
  • Stabilize a `1.0` version

    Stabilize a `1.0` version

    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
    opened by hdevalence 3
  • Rename transcript functions

    Rename transcript functions

    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)
    opened by hdevalence 2
  • Derive PartialEq, Eq, PartialOrd, Ord, and Hash

    Derive PartialEq, Eq, PartialOrd, Ord, and Hash

    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.

    opened by burdges 2
  • Switch to strobe-rs for STROBE dep

    Switch to strobe-rs for STROBE dep

    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.

    opened by rozbb 0
  • Build fails on big-endian

    Build fails on big-endian

    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`.
    
    opened by n4ss 4
Owner
dalek cryptography
Fast, safe, pure-rust elliptic curve cryptography
dalek cryptography
OpenZKP - pure Rust implementations of Zero-Knowledge Proof systems.

OpenZKP OpenZKP - pure Rust implementations of Zero-Knowledge Proof systems. Overview Project current implements ?? the Stark protocol (see its readme

0x 529 Jan 5, 2023
A mdbook preprocessor that allows the re-usability of template files with dynamic arguments

mdbook-template A mdbook preprocessor that allows the re-usability of template files with dynamic arguments Table of Contents Author Notes Installatio

Hamothy 7 Dec 22, 2022
A Software Development Kit (SDK) for Zero-Knowledge Transactions

Aleo SDK The Aleo SDK is a developer framework to make it simple to create a new account, craft a transaction, and broadcast it to the network. Table

Aleo 270 Jan 5, 2023
Zerocaf: A library built for EC operations in Zero Knowledge.

Dusk-Zerocaf WARNING: WIP Repo. Fast, efficient and bulletproof-friendly cryptographic operations. This repository contains an implementation of the S

Dusk Network 50 Oct 31, 2022
Zero-Knowledge Assembly language and compiler

zkAsm A Zero-Knowledge circuit assembly language, designed to represent Zero-Knowledge circuits in a compressed format, to be stored on blockchains. I

null 1 Dec 30, 2021
Noir is a domain specific language for zero knowledge proofs

The Noir Programming Language Noir is a Domain Specific Language for SNARK proving systems. It has been designed to use any ACIR compatible proving sy

null 404 Jan 1, 2023
RISC Zero is a zero-knowledge verifiable general computing platform based on zk-STARKs and the RISC-V microarchitecture.

RISC Zero WARNING: This software is still experimental, we do not recommend it for production use (see Security section). RISC Zero is a zero-knowledg

RISC Zero 653 Jan 3, 2023
Vector OLE and zero-knowledge for Z2k.

Mozzarella Benchmarking Code This repository contains the code developed for the benchmarking experiments in our paper: "Moz $\mathbb{Z}_{2^k}$ arella

null 7 Dec 20, 2022
Safeguard your financial privacy with zero-knowledge proofs.

Spinner The Spinner project (https://spinner.cash) takes a privacy first approach to protect users crypto assets. It is a layer-2 protocol built on th

Spinner 21 Dec 28, 2022
STARK - SNARK recursive zero knowledge proofs, combinaison of the Winterfell library and the Circom language

STARK - SNARK recursive proofs The point of this library is to combine the SNARK and STARK computation arguments of knowledge, namely the Winterfell l

Victor Colomb 68 Dec 5, 2022
The Nervos CKB is a public permissionless blockchain, and the layer 1 of Nervos network.

Nervos CKB - The Common Knowledge Base master develop About CKB CKB is the layer 1 of Nervos Network, a public/permissionless blockchain. CKB uses Pro

Nervos Network 1k Dec 30, 2022
The public source and documentation for Xenon iOS tweak.

THE GUIDE HAS BEEN MOVED TO THE WIKI This is the public source for the Xenon iOS tweak. The full version is available for $1.99 on Chariz. Differences

aspen 1 Dec 28, 2022
Manage secret values in-repo via public key cryptography

amber Manage secret values in-repo via public key cryptography. See the announcement blog post for more motivation. Amber provides the ability to secu

FP Complete 82 Nov 10, 2022
Zei is a library that provide tools to create and verify public transaction with confidential data.

#Zei: Findora's Cryptographic Library Zei is a library that provide tools to create and verify public transaction with confidential data. Support: Bas

Findora Foundation 0 Oct 23, 2022
The Hybrid Public Key Encryption (HPKE) standard in Python

Hybrid PKE The Hybrid Public Key Encryption (HPKE) standard in Python. hybrid_pke = hpke-rs ➕ PyO3 This library provides Python bindings to the hpke-r

Cape Privacy 4 Nov 7, 2022
Simple automated proof assistant.

Esther is a work-in-progress, proof-of-concept automated theorem proof assistant based on Homotopy Type Theory. Acknowledgements Arend, Lean, Coq and

Aodhnait Étaín 5 Sep 14, 2021
Implementation of Proof of Existence consensus using Substrate Framework, Frame, Pallets, RUST

Substrate Node Template A fresh FRAME-based Substrate node, ready for hacking ?? Getting Started Follow the steps below to get started with the Node T

Vijayendra Gaur 1 Jun 8, 2022
OGC API & STAC - Proof of Concept

OAPI - POC Proof of concept (POC) to ingest geospatial datasets from MeteoSuisse into a SpatioTemporal Asset Catalog (STAC), expose as OGC API Feature

Camptocamp 32 Dec 1, 2022
Rust implementation of Namada, a sovereign proof-of-stake blockchain that enables asset-agnostic private transfers

Namada Overview Namada is a sovereign proof-of-stake blockchain, using Tendermint BFT consensus, that enables multi-asset private transfers for any na

anoma 144 Jan 2, 2023