Skip to main content

merlin/
transcript.rs

1use zeroize::{Zeroize, Zeroizing};
2
3use crate::strobe::Strobe128;
4
5fn encode_u64(x: u64) -> [u8; 8] {
6    x.to_le_bytes()
7}
8
9fn encode_usize_as_u32(x: usize) -> [u8; 4] {
10    assert!(x <= (u32::MAX as usize));
11    (x as u32).to_le_bytes()
12}
13
14/// A transcript of a public-coin argument.
15///
16/// The prover's messages are added to the transcript using
17/// [`append_message`](Transcript::append_message), and the verifier's
18/// challenges can be computed using
19/// [`challenge_bytes`](Transcript::challenge_bytes).
20///
21/// # Creating and using a Merlin transcript
22///
23/// To create a Merlin transcript, use [`Transcript::new()`].  This
24/// function takes a domain separation label which should be unique to
25/// the application.
26///
27/// To use the transcript with a Merlin-based proof implementation,
28/// the prover's side creates a Merlin transcript with an
29/// application-specific domain separation label, and passes a `&mut`
30/// reference to the transcript to the proving function(s).
31///
32/// To verify the resulting proof, the verifier creates their own
33/// Merlin transcript using the same domain separation label, then
34/// passes a `&mut` reference to the verifier's transcript to the
35/// verification function.
36///
37/// # Implementing proofs using Merlin
38///
39/// For information on the design of Merlin and how to use it to
40/// implement a proof system, see the documentation at
41/// [merlin.cool](https://merlin.cool), particularly the [Using
42/// Merlin](https://merlin.cool/use/index.html) section.
43#[derive(Clone, Zeroize)]
44pub struct Transcript {
45    strobe: Strobe128,
46}
47
48impl Transcript {
49    /// Initialize a new transcript with the supplied `label`, which
50    /// is used as a domain separator.
51    ///
52    /// # Note
53    ///
54    /// This function should be called by a proof library's API
55    /// consumer (i.e., the application using the proof library), and
56    /// **not by the proof implementation**.  See the [Passing
57    /// Transcripts](https://merlin.cool/use/passing.html) section of
58    /// the Merlin website for more details on why.
59    pub fn new(label: &[u8]) -> Transcript {
60        use crate::constants::MERLIN_PROTOCOL_LABEL;
61
62        #[cfg(feature = "debug-transcript")]
63        {
64            use std::str::from_utf8;
65            println!(
66                "Initialize STROBE-128({})\t# b\"{}\"",
67                hex::encode(MERLIN_PROTOCOL_LABEL),
68                from_utf8(MERLIN_PROTOCOL_LABEL).unwrap(),
69            );
70        }
71
72        let mut transcript = Transcript {
73            strobe: Strobe128::new(MERLIN_PROTOCOL_LABEL),
74        };
75        transcript.append_message(b"dom-sep", label);
76
77        transcript
78    }
79
80    /// Append a prover's `message` to the transcript.
81    ///
82    /// The `label` parameter is metadata about the message, and is
83    /// also appended to the transcript.  See the [Transcript
84    /// Protocols](https://merlin.cool/use/protocol.html) section of
85    /// the Merlin website for details on labels.
86    pub fn append_message(&mut self, label: &[u8], message: &[u8]) {
87        let data_len = encode_usize_as_u32(message.len());
88        self.strobe.meta_ad(label, false);
89        self.strobe.meta_ad(&data_len, true);
90        self.strobe.ad(message, false);
91
92        #[cfg(feature = "debug-transcript")]
93        {
94            use std::str::from_utf8;
95
96            match from_utf8(label) {
97                Ok(label_str) => {
98                    println!(
99                        "meta-AD : {} || LE32({})\t# b\"{}\"",
100                        hex::encode(label),
101                        message.len(),
102                        label_str
103                    );
104                }
105                Err(_) => {
106                    println!(
107                        "meta-AD : {} || LE32({})",
108                        hex::encode(label),
109                        message.len()
110                    );
111                }
112            }
113            match from_utf8(message) {
114                Ok(message_str) => {
115                    println!("     AD : {}\t# b\"{}\"", hex::encode(message), message_str);
116                }
117                Err(_) => {
118                    println!("     AD : {}", hex::encode(message));
119                }
120            }
121        }
122    }
123
124    /// Deprecated.  This function was renamed to
125    /// [`append_message`](Transcript::append_message).
126    ///
127    /// This is intended to avoid any possible confusion between the
128    /// transcript-level messages and protocol-level commitments.
129    #[deprecated(since = "1.1.0", note = "renamed to append_message for clarity.")]
130    pub fn commit_bytes(&mut self, label: &[u8], message: &[u8]) {
131        self.append_message(label, message);
132    }
133
134    /// Convenience method for appending a `u64` to the transcript.
135    ///
136    /// The `label` parameter is metadata about the message, and is
137    /// also appended to the transcript.  See the [Transcript
138    /// Protocols](https://merlin.cool/use/protocol.html) section of
139    /// the Merlin website for details on labels.
140    ///
141    /// # Implementation
142    ///
143    /// Calls `append_message` with the 8-byte little-endian encoding
144    /// of `x`.
145    pub fn append_u64(&mut self, label: &[u8], x: u64) {
146        self.append_message(label, &encode_u64(x));
147    }
148
149    /// Deprecated.  This function was renamed to
150    /// [`append_u64`](Transcript::append_u64).
151    ///
152    /// This is intended to avoid any possible confusion between the
153    /// transcript-level messages and protocol-level commitments.
154    #[deprecated(since = "1.1.0", note = "renamed to append_u64 for clarity.")]
155    pub fn commit_u64(&mut self, label: &[u8], x: u64) {
156        self.append_u64(label, x);
157    }
158
159    /// Fill the supplied buffer with the verifier's challenge bytes.
160    ///
161    /// The `label` parameter is metadata about the challenge, and is
162    /// also appended to the transcript.  See the [Transcript
163    /// Protocols](https://merlin.cool/use/protocol.html) section of
164    /// the Merlin website for details on labels.
165    pub fn challenge_bytes(&mut self, label: &[u8], dest: &mut [u8]) {
166        let data_len = encode_usize_as_u32(dest.len());
167        self.strobe.meta_ad(label, false);
168        self.strobe.meta_ad(&data_len, true);
169        self.strobe.prf(dest, false);
170
171        #[cfg(feature = "debug-transcript")]
172        {
173            use std::str::from_utf8;
174
175            match from_utf8(label) {
176                Ok(label_str) => {
177                    println!(
178                        "meta-AD : {} || LE32({})\t# b\"{}\"",
179                        hex::encode(label),
180                        dest.len(),
181                        label_str
182                    );
183                }
184                Err(_) => {
185                    println!("meta-AD : {} || LE32({})", hex::encode(label), dest.len());
186                }
187            }
188            println!("     PRF: {}", hex::encode(dest));
189        }
190    }
191
192    /// Fork the current [`Transcript`] to construct an RNG whose output is bound
193    /// to the current transcript state as well as prover's secrets.
194    ///
195    /// See the [`TranscriptRngBuilder`] documentation for more details.
196    pub fn build_rng(&self) -> TranscriptRngBuilder {
197        TranscriptRngBuilder {
198            strobe: self.strobe.clone(),
199        }
200    }
201}
202
203/// Constructs a [`TranscriptRng`] by rekeying the [`Transcript`] with
204/// prover secrets and an external RNG.
205///
206/// The prover uses a [`TranscriptRngBuilder`] to rekey with its
207/// witness data, before using an external RNG to finalize to a
208/// [`TranscriptRng`].  The resulting [`TranscriptRng`] will be a PRF
209/// of all of the entire public transcript, the prover's secret
210/// witness data, and randomness from the external RNG.
211///
212/// # Usage
213///
214/// To construct a [`TranscriptRng`], a prover calls
215/// [`Transcript::build_rng()`] to clone the transcript state, then
216/// uses [`rekey_with_witness_bytes()`][rekey_with_witness_bytes] to rekey the
217/// transcript with the prover's secrets, before finally calling
218/// [`finalize()`][finalize].  This rekeys the transcript with the
219/// output of an external [`rand_core::RngCore`] instance and returns
220/// a finalized [`TranscriptRng`].
221///
222/// These methods are intended to be chained, passing from a borrowed
223/// [`Transcript`] to an owned [`TranscriptRng`] as follows:
224/// ```
225/// # extern crate merlin;
226/// # extern crate rand_core;
227/// # use merlin::Transcript;
228/// # fn main() {
229/// # let mut transcript = Transcript::new(b"TranscriptRng doctest");
230/// # let public_data = b"public data";
231/// # let witness_data = b"witness data";
232/// # let more_witness_data = b"witness data";
233/// transcript.append_message(b"public", public_data);
234///
235/// let mut rng = transcript
236///     .build_rng()
237///     .rekey_with_witness_bytes(b"witness1", witness_data)
238///     .rekey_with_witness_bytes(b"witness2", more_witness_data)
239///     .finalize(&mut rand_core::OsRng);
240/// # }
241/// ```
242/// In this example, the final `rng` is a PRF of `public_data`
243/// (as well as all previous `transcript` state), and of the prover's
244/// secret `witness_data` and `more_witness_data`, and finally, of the
245/// output of the thread-local RNG.
246/// Note that because the [`TranscriptRng`] is produced from
247/// [`finalize()`][finalize], it's impossible to forget
248/// to rekey the transcript with external randomness.
249///
250/// # Note
251///
252/// Protocols that require randomness in multiple places (e.g., to
253/// choose blinding factors for a multi-round protocol) should create
254/// a fresh [`TranscriptRng`] **each time they need randomness**,
255/// rather than reusing a single instance.  This ensures that the
256/// randomness in each round is bound to the latest transcript state,
257/// rather than just the state of the transcript when randomness was
258/// first required.
259///
260/// # Typed Witness Data
261///
262/// Like the [`Transcript`], the [`TranscriptRngBuilder`] provides a
263/// minimal, byte-oriented API, and like the [`Transcript`], this API
264/// can be extended to allow rekeying with protocol-specific types
265/// using an extension trait.  See the [Transcript
266/// Protocols](https://merlin.cool/use/protocol.html) section of the
267/// Merlin website for more details.
268///
269/// [rekey_with_witness_bytes]: TranscriptRngBuilder::rekey_with_witness_bytes
270/// [finalize]: TranscriptRngBuilder::finalize
271pub struct TranscriptRngBuilder {
272    strobe: Strobe128,
273}
274
275impl TranscriptRngBuilder {
276    /// Rekey the transcript using the provided witness data.
277    ///
278    /// The `label` parameter is metadata about `witness`.
279    pub fn rekey_with_witness_bytes(
280        mut self,
281        label: &[u8],
282        witness: &[u8],
283    ) -> TranscriptRngBuilder {
284        let witness_len = encode_usize_as_u32(witness.len());
285        self.strobe.meta_ad(label, false);
286        self.strobe.meta_ad(&witness_len, true);
287        self.strobe.key(witness, false);
288
289        self
290    }
291
292    /// Deprecated.  This function was renamed to
293    /// [`rekey_with_witness_bytes`](TranscriptRngBuilder::rekey_with_witness_bytes).
294    ///
295    /// This is intended to avoid any possible confusion between the
296    /// transcript-level messages and protocol-level commitments.
297    #[deprecated(
298        since = "1.1.0",
299        note = "renamed to rekey_with_witness_bytes for clarity."
300    )]
301    pub fn commit_witness_bytes(self, label: &[u8], witness: &[u8]) -> TranscriptRngBuilder {
302        self.rekey_with_witness_bytes(label, witness)
303    }
304
305    /// Use the supplied external `rng` to rekey the transcript, so
306    /// that the finalized [`TranscriptRng`] is a PRF bound to
307    /// randomness from the external RNG, as well as all other
308    /// transcript data.
309    pub fn finalize<R>(mut self, rng: &mut R) -> TranscriptRng
310    where
311        R: rand_core::RngCore + rand_core::CryptoRng,
312    {
313        // Wrap before filling so an unwinding RNG also wipes partial output.
314        let mut random_bytes = Zeroizing::new([0u8; 32]);
315        rng.fill_bytes(&mut random_bytes[..]);
316
317        self.strobe.meta_ad(b"rng", false);
318        self.strobe.key(&random_bytes[..], false);
319
320        TranscriptRng {
321            strobe: self.strobe,
322        }
323    }
324}
325
326/// An RNG providing synthetic randomness to the prover.
327///
328/// A [`TranscriptRng`] is constructed from a [`Transcript`] using a
329/// [`TranscriptRngBuilder`]; see its documentation for details on
330/// how to construct one.
331///
332/// The transcript RNG construction is described in the [Generating
333/// Randomness](https://merlin.cool/transcript/rng.html) section of
334/// the Merlin website.
335pub struct TranscriptRng {
336    strobe: Strobe128,
337}
338
339impl rand_core::RngCore for TranscriptRng {
340    fn next_u32(&mut self) -> u32 {
341        rand_core::impls::next_u32_via_fill(self)
342    }
343
344    fn next_u64(&mut self) -> u64 {
345        rand_core::impls::next_u64_via_fill(self)
346    }
347
348    fn fill_bytes(&mut self, dest: &mut [u8]) {
349        let dest_len = encode_usize_as_u32(dest.len());
350        self.strobe.meta_ad(&dest_len, false);
351        self.strobe.prf(dest, false);
352    }
353
354    fn try_fill_bytes(&mut self, dest: &mut [u8]) -> Result<(), rand_core::Error> {
355        self.fill_bytes(dest);
356        Ok(())
357    }
358}
359
360impl rand_core::CryptoRng for TranscriptRng {}
361
362#[cfg(test)]
363mod tests {
364    use strobe_rs::SecParam;
365    use strobe_rs::Strobe;
366
367    use super::*;
368
369    /// Test against a full strobe implementation to ensure we match the few
370    /// operations we're interested in.
371    struct TestTranscript {
372        state: Strobe,
373    }
374
375    impl TestTranscript {
376        /// Strobe init; meta-AD(label)
377        pub fn new(label: &[u8]) -> TestTranscript {
378            use crate::constants::MERLIN_PROTOCOL_LABEL;
379
380            let mut tt = TestTranscript {
381                state: Strobe::new(MERLIN_PROTOCOL_LABEL, SecParam::B128),
382            };
383            tt.append_message(b"dom-sep", label);
384
385            tt
386        }
387
388        /// Strobe op: meta-AD(label || len(message)); AD(message)
389        pub fn append_message(&mut self, label: &[u8], message: &[u8]) {
390            // metadata = label || len(message);
391            let mut metadata: Vec<u8> = Vec::with_capacity(label.len() + 4);
392            metadata.extend_from_slice(label);
393            metadata.extend_from_slice(&encode_usize_as_u32(message.len()));
394
395            self.state.meta_ad(&metadata, false);
396            self.state.ad(message, false);
397        }
398
399        /// Strobe op: meta-AD(label || len(dest)); PRF into challenge_bytes
400        pub fn challenge_bytes(&mut self, label: &[u8], dest: &mut [u8]) {
401            let prf_len = dest.len();
402
403            // metadata = label || len(challenge_bytes);
404            let mut metadata: Vec<u8> = Vec::with_capacity(label.len() + 4);
405            metadata.extend_from_slice(label);
406            metadata.extend_from_slice(&encode_usize_as_u32(prf_len));
407
408            self.state.meta_ad(&metadata, false);
409            self.state.prf(dest, false);
410        }
411    }
412
413    /// Test a simple protocol with one message and one challenge
414    #[test]
415    fn equivalence_simple() {
416        let mut real_transcript = Transcript::new(b"test protocol");
417        let mut test_transcript = TestTranscript::new(b"test protocol");
418
419        real_transcript.append_message(b"some label", b"some data");
420        test_transcript.append_message(b"some label", b"some data");
421
422        let mut real_challenge = [0u8; 32];
423        let mut test_challenge = [0u8; 32];
424
425        real_transcript.challenge_bytes(b"challenge", &mut real_challenge);
426        test_transcript.challenge_bytes(b"challenge", &mut test_challenge);
427
428        assert_eq!(real_challenge, test_challenge);
429    }
430
431    /// Test a complex protocol with multiple messages and challenges,
432    /// with messages long enough to wrap around the sponge state, and
433    /// with multiple rounds of messages and challenges.
434    #[test]
435    fn equivalence_complex() {
436        let mut real_transcript = Transcript::new(b"test protocol");
437        let mut test_transcript = TestTranscript::new(b"test protocol");
438
439        let data = vec![99; 1024];
440
441        real_transcript.append_message(b"step1", b"some data");
442        test_transcript.append_message(b"step1", b"some data");
443
444        let mut real_challenge = [0u8; 32];
445        let mut test_challenge = [0u8; 32];
446
447        for _ in 0..32 {
448            real_transcript.challenge_bytes(b"challenge", &mut real_challenge);
449            test_transcript.challenge_bytes(b"challenge", &mut test_challenge);
450
451            assert_eq!(real_challenge, test_challenge);
452
453            real_transcript.append_message(b"bigdata", &data);
454            test_transcript.append_message(b"bigdata", &data);
455
456            real_transcript.append_message(b"challengedata", &real_challenge);
457            test_transcript.append_message(b"challengedata", &test_challenge);
458        }
459    }
460
461    #[test]
462    fn transcript_rng_is_bound_to_transcript_and_witnesses() {
463        use rand_chacha::ChaChaRng;
464        use rand_core::{RngCore, SeedableRng};
465
466        // Check that the TranscriptRng is bound to the transcript and
467        // the witnesses.  This is done by producing a sequence of
468        // transcripts that diverge at different points and checking
469        // that they produce different challenges.
470
471        let protocol_label = b"test TranscriptRng collisions";
472        let commitment1 = b"commitment data 1";
473        let commitment2 = b"commitment data 2";
474        let witness1 = b"witness data 1";
475        let witness2 = b"witness data 2";
476
477        let mut t1 = Transcript::new(protocol_label);
478        let mut t2 = Transcript::new(protocol_label);
479        let mut t3 = Transcript::new(protocol_label);
480        let mut t4 = Transcript::new(protocol_label);
481
482        t1.append_message(b"com", commitment1);
483        t2.append_message(b"com", commitment2);
484        t3.append_message(b"com", commitment2);
485        t4.append_message(b"com", commitment2);
486
487        let mut r1 = t1
488            .build_rng()
489            .rekey_with_witness_bytes(b"witness", witness1)
490            .finalize(&mut ChaChaRng::from_seed([0; 32]));
491
492        let mut r2 = t2
493            .build_rng()
494            .rekey_with_witness_bytes(b"witness", witness1)
495            .finalize(&mut ChaChaRng::from_seed([0; 32]));
496
497        let mut r3 = t3
498            .build_rng()
499            .rekey_with_witness_bytes(b"witness", witness2)
500            .finalize(&mut ChaChaRng::from_seed([0; 32]));
501
502        let mut r4 = t4
503            .build_rng()
504            .rekey_with_witness_bytes(b"witness", witness2)
505            .finalize(&mut ChaChaRng::from_seed([0; 32]));
506
507        let mut s1 = [0; 32];
508        let mut s2 = [0; 32];
509        let mut s3 = [0; 32];
510        let mut s4 = [0; 32];
511        r1.fill_bytes(&mut s1);
512        r2.fill_bytes(&mut s2);
513        r3.fill_bytes(&mut s3);
514        r4.fill_bytes(&mut s4);
515
516        // Transcript t1 has different commitments than t2, t3, t4, so
517        // it should produce distinct challenges from all of them.
518        assert_ne!(s1, s2);
519        assert_ne!(s1, s3);
520        assert_ne!(s1, s4);
521
522        // Transcript t2 has different witness variables from t3, t4,
523        // so it should produce distinct challenges from all of them.
524        assert_ne!(s2, s3);
525        assert_ne!(s2, s4);
526
527        // Transcripts t3 and t4 have the same commitments and
528        // witnesses, so they should give different challenges only
529        // based on the RNG. Checking that they're equal in the
530        // presence of a bad RNG checks that the different challenges
531        // above aren't because the RNG is accidentally different.
532        assert_eq!(s3, s4);
533    }
534}