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}