Skip to main content

hide_transparency/
witness.rs

1//! Interoperability with the C2SP transparency-log witness network.
2//!
3//! HIDE's own cosignature (`Checkpoint::cosign`) is a HIDE-Sign hybrid signature
4//! over the checkpoint text, which only another HIDE implementation can verify.
5//! That is enough for a HIDE-only deployment and useless for reaching the
6//! public witness network, whose members are ordinary C2SP witnesses: an HTTP
7//! service identified by a name and a public key, speaking
8//! [`c2sp.org/tlog-witness`](https://c2sp.org/tlog-witness) and cosigning in the
9//! format of [`c2sp.org/tlog-cosignature`](https://c2sp.org/tlog-cosignature).
10//!
11//! A HIDE checkpoint note is already a C2SP note — origin, size, base64 root,
12//! then signature lines — so the two can live in one note. This module adds the
13//! missing half: building the `add-checkpoint` request, reading the response the
14//! way the specification classifies it, and verifying an Ed25519 cosignature a
15//! standard witness returned.
16//!
17//! # Honest limits
18//!
19//! - **ML-DSA-44 cosignatures are out of scope.** `c2sp.org/tlog-cosignature`
20//!   defines two algorithms and recommends ML-DSA-44 for new deployments. HIDE
21//!   implements ML-DSA-65, so it can verify the Ed25519 algorithm and cannot
22//!   verify the ML-DSA-44 one. A witness offering only ML-DSA-44 is refused
23//!   explicitly rather than silently ignored.
24//! - **Cosigning a HIDE checkpoint proves nothing about HIDE.** A cosignature
25//!   attests to one tree head at one time, exactly as it does for any other log.
26//! - Nothing here talks to the network: the request and response are bytes, so
27//!   the caller decides what performs the HTTP call and how it is authenticated.
28
29use ed25519_dalek::{Signature, VerifyingKey};
30
31use crate::checkpoint::{Checkpoint, MAX_NOTE_BYTES, SignedNote, valid_name};
32use crate::{Hash, LogError};
33
34/// The C2SP algorithm byte for Ed25519 cosignatures. `c2sp.org/signed-note`
35/// assigns `0x01`; HIDE-Sign uses the `0xff` escape followed by a type string,
36/// so a note carrying both can never confuse the two.
37pub const C2SP_ED25519_ALGORITHM: u8 = 0x01;
38
39/// A witness is allowed at most 63 consistency proof lines.
40pub const MAX_WITNESS_PROOF_LINES: usize = 63;
41
42/// Domain separation for the cosignature, per `c2sp.org/tlog-cosignature`.
43const COSIGNATURE_LABEL: &[u8] = b"cosignature/v1";
44/// The empty tree, RFC 6962 §2.1: the hash of an empty string.
45pub fn empty_tree_root() -> Hash {
46    use sha2::Digest;
47    let digest = sha2::Sha256::digest([]);
48    let mut root = [0_u8; 32];
49    root.copy_from_slice(&digest);
50    root
51}
52
53/// The key id a C2SP cosignature line carries:
54/// `SHA-256(name || 0x0A || algorithm || public_key)[:4]`.
55///
56/// Distinct from [`crate::key_id`], which uses the signed-note escape byte and a
57/// type string; the two derivations cannot collide on the same key.
58pub fn c2sp_key_id(name: &str, ed25519_public: &[u8; 32]) -> [u8; 4] {
59    use sha2::Digest;
60    let mut hasher = sha2::Sha256::new();
61    hasher.update(name.as_bytes());
62    hasher.update([0x0a, C2SP_ED25519_ALGORITHM]);
63    hasher.update(ed25519_public);
64    let digest = hasher.finalize();
65    [digest[0], digest[1], digest[2], digest[3]]
66}
67
68/// The exact bytes an Ed25519 C2SP cosignature is computed over. Every line is
69/// newline-terminated, and the timestamp is ASCII decimal with no leading zeroes.
70///
71/// Reproduced from the specification rather than derived, because a signature
72/// covers exactly these bytes and any difference is a failed verification that
73/// looks like a dishonest witness.
74pub fn cosignature_input(timestamp: u64, checkpoint_text: &str) -> Vec<u8> {
75    let mut out = Vec::with_capacity(32 + checkpoint_text.len());
76    out.extend_from_slice(COSIGNATURE_LABEL);
77    out.push(b'\n');
78    out.extend_from_slice(format!("time {timestamp}\n").as_bytes());
79    out.extend_from_slice(checkpoint_text.as_bytes());
80    out
81}
82
83/// A witness the caller trusts for this log: a name and an Ed25519 key.
84#[derive(Debug, Clone, PartialEq, Eq)]
85pub struct Witness {
86    pub name: String,
87    pub ed25519_public: [u8; 32],
88}
89
90impl Witness {
91    /// Refuses a name a C2SP note could not carry, so an unusable witness is a
92    /// configuration error rather than a silent non-match later.
93    pub fn new(name: impl Into<String>, ed25519_public: [u8; 32]) -> Result<Self, LogError> {
94        let name = name.into();
95        if !valid_name(&name) {
96            return Err(LogError::Malformed);
97        }
98        Ok(Self {
99            name,
100            ed25519_public,
101        })
102    }
103}
104
105/// How a cosignature line was verified, so a caller can tell "the witness I
106/// meant signed this" from "some line had the right key id".
107#[derive(Debug, Clone, Copy, PartialEq, Eq)]
108pub struct Cosignature {
109    pub timestamp: u64,
110}
111
112/// Verifies a C2SP Ed25519 cosignature from `witness` over `note`, in addition
113/// to the log's own HIDE-Sign signature, and requires the checkpoint to be the
114/// one `origin` names.
115///
116/// The timestamp is recovered by trying the candidate: a cosignature signs the
117/// timestamp, so it cannot be read off the line and checked afterwards. The
118/// specification sends it in a `time` line inside the *signed* message, which is
119/// what this rebuilds — the value therefore comes from the witness's own
120/// signature input and must be supplied by the caller from the response the
121/// witness returned.
122pub fn verify_ed25519_cosignature(
123    note: &[u8],
124    origin: &str,
125    log: &hide_sign::VerifyingIdentity,
126    witness: &Witness,
127    timestamp: u64,
128) -> Result<(Checkpoint, Cosignature), LogError> {
129    // The log's signature is checked first: a cosignature over a checkpoint the
130    // log never signed is worth nothing, however well it verifies.
131    let checkpoint = Checkpoint::verify(note, origin, log)?;
132
133    if note.len() > MAX_NOTE_BYTES {
134        return Err(LogError::Malformed);
135    }
136    let parsed = SignedNote::decode(note)?;
137    let id = c2sp_key_id(&witness.name, &witness.ed25519_public);
138    let line = parsed
139        .signatures
140        .iter()
141        .find(|line| line.name == witness.name && line.key_id == id)
142        .ok_or(LogError::Unsigned)?;
143
144    let key =
145        VerifyingKey::from_bytes(&witness.ed25519_public).map_err(|_| LogError::BadSignature)?;
146    let signature = Signature::from_slice(&line.signature).map_err(|_| LogError::BadSignature)?;
147    let message = cosignature_input(timestamp, &parsed.text);
148    // Strict, because a non-canonical encoding or a small-order key would
149    // otherwise be accepted here and refused by a stricter peer.
150    key.verify_strict(&message, &signature)
151        .map_err(|_| LogError::BadSignature)?;
152
153    Ok((checkpoint, Cosignature { timestamp }))
154}
155
156/// The body of a `POST <prefix>/add-checkpoint` request: the old size line, the
157/// consistency proof lines, an empty line, then the note.
158///
159/// `proof` must be the RFC 6962 consistency proof from `old_size` to the
160/// checkpoint's size, and empty when `old_size` is zero — the specification makes
161/// a non-empty proof at size zero a `422`.
162pub fn add_checkpoint_body(
163    old_size: u64,
164    proof: &[Hash],
165    note: &[u8],
166) -> Result<Vec<u8>, LogError> {
167    use base64::Engine;
168    if proof.len() > MAX_WITNESS_PROOF_LINES {
169        return Err(LogError::ProofTooLong(proof.len()));
170    }
171    if old_size == 0 && !proof.is_empty() {
172        return Err(LogError::Malformed);
173    }
174    if note.len() > MAX_NOTE_BYTES {
175        return Err(LogError::Malformed);
176    }
177    let mut out = Vec::with_capacity(32 + 45 * proof.len() + note.len());
178    out.extend_from_slice(format!("old {old_size}\n").as_bytes());
179    for hash in proof {
180        out.extend_from_slice(
181            base64::engine::general_purpose::STANDARD
182                .encode(hash)
183                .as_bytes(),
184        );
185        out.push(b'\n');
186    }
187    out.push(b'\n');
188    out.extend_from_slice(note);
189    Ok(out)
190}
191
192/// What a witness said, classified from the status code exactly as
193/// `c2sp.org/tlog-witness` defines it, so a caller never has to guess from a
194/// status alone which of the four refusals it received.
195#[derive(Debug, Clone, PartialEq, Eq)]
196pub enum AddCheckpointOutcome {
197    /// `200`: the body is the cosignature line the witness returned.
198    Cosigned(Vec<u8>),
199    /// `404`: the witness does not serve this origin.
200    UnknownOrigin,
201    /// `403`: no signature from a trusted key, or the checkpoint is malformed.
202    NotSigned,
203    /// `400`: the old size is above the checkpoint size.
204    BadOldSize,
205    /// `409`: the old size is not what this witness last cosigned. The body
206    /// carries the size it did cosign, which is what the caller must retry from.
207    Conflict { newest_size: u64 },
208    /// `422`: the proof does not verify, or a size-zero checkpoint has a root
209    /// that is not the empty tree.
210    ProofRejected,
211}
212
213/// Classifies an `add-checkpoint` response. A status this specification does not
214/// name is refused rather than mapped onto the nearest one.
215pub fn classify_add_checkpoint(status: u16, body: &[u8]) -> Result<AddCheckpointOutcome, LogError> {
216    Ok(match status {
217        200 => AddCheckpointOutcome::Cosigned(body.to_vec()),
218        403 => AddCheckpointOutcome::NotSigned,
219        404 => AddCheckpointOutcome::UnknownOrigin,
220        400 => AddCheckpointOutcome::BadOldSize,
221        409 => {
222            let text = std::str::from_utf8(body).map_err(|_| LogError::Malformed)?;
223            let line = text.strip_suffix('\n').ok_or(LogError::Malformed)?;
224            // `parse` would accept "+5" and "05"; the specification allows
225            // neither, and the value is what a retry is based on.
226            if line.is_empty() || !line.bytes().all(|b| b.is_ascii_digit()) {
227                return Err(LogError::Malformed);
228            }
229            if line.len() > 1 && line.starts_with('0') {
230                return Err(LogError::Malformed);
231            }
232            let newest_size: u64 = line.parse().map_err(|_| LogError::Malformed)?;
233            AddCheckpointOutcome::Conflict { newest_size }
234        }
235        422 => AddCheckpointOutcome::ProofRejected,
236        _ => return Err(LogError::Malformed),
237    })
238}
239
240/// The root a size-zero checkpoint must carry, so a caller can build one that a
241/// witness will not reject with `422`.
242/// Whether a checkpoint a witness would accept at size zero is well-formed.
243pub fn is_empty_tree_checkpoint(checkpoint: &Checkpoint) -> bool {
244    checkpoint.size == 0 && checkpoint.root == empty_tree_root()
245}
246
247#[cfg(test)]
248mod tests {
249    use super::*;
250    use ed25519_dalek::{Signer, SigningKey};
251
252    fn checkpoint(size: u64) -> Checkpoint {
253        Checkpoint {
254            origin: "hide.example/log".into(),
255            size,
256            root: [7_u8; 32],
257        }
258    }
259
260    fn witness_key() -> SigningKey {
261        SigningKey::from_bytes(&[0x51; 32])
262    }
263
264    fn cosigned_note(timestamp: u64) -> (Vec<u8>, Witness) {
265        let log = hide_sign::SigningIdentity::from_bytes(&[0x42; 32]).unwrap();
266        let text = checkpoint(9).text().unwrap();
267        let mut note = checkpoint(9).sign(&log).unwrap();
268        let witness =
269            Witness::new("witness.example", witness_key().verifying_key().to_bytes()).unwrap();
270        let signature = witness_key().sign(&cosignature_input(timestamp, &text));
271        let mut raw = Vec::new();
272        raw.extend_from_slice(&c2sp_key_id(&witness.name, &witness.ed25519_public));
273        raw.extend_from_slice(&signature.to_bytes());
274        note.signatures.push(crate::checkpoint::NoteSignature {
275            name: witness.name.clone(),
276            key_id: c2sp_key_id(&witness.name, &witness.ed25519_public),
277            signature: raw[4..].to_vec(),
278        });
279        (note.encode().into_bytes(), witness)
280    }
281
282    /// The whole point: a standard Ed25519 witness cosignature over a HIDE
283    /// checkpoint verifies, and the log's own signature is still required.
284    #[test]
285    fn a_c2sp_ed25519_cosignature_verifies_over_a_hide_checkpoint() {
286        let log = hide_sign::SigningIdentity::from_bytes(&[0x42; 32]).unwrap();
287        let (note, witness) = cosigned_note(1_700_000_000);
288        let (checkpoint, cosignature) = verify_ed25519_cosignature(
289            &note,
290            "hide.example/log",
291            &log.verifying_key(),
292            &witness,
293            1_700_000_000,
294        )
295        .expect("a genuine cosignature verifies");
296        assert_eq!(checkpoint.size, 9);
297        assert_eq!(cosignature.timestamp, 1_700_000_000);
298    }
299
300    /// The timestamp is signed, so the same note must fail at a different one.
301    #[test]
302    fn a_cosignature_is_bound_to_its_timestamp() {
303        let log = hide_sign::SigningIdentity::from_bytes(&[0x42; 32]).unwrap();
304        let (note, witness) = cosigned_note(1_700_000_000);
305        assert_eq!(
306            verify_ed25519_cosignature(
307                &note,
308                "hide.example/log",
309                &log.verifying_key(),
310                &witness,
311                1_700_000_001
312            ),
313            Err(LogError::BadSignature)
314        );
315    }
316
317    /// A cosignature is not a substitute for the log's signature.
318    #[test]
319    fn a_cosignature_over_an_unsigned_checkpoint_is_refused() {
320        let other = hide_sign::SigningIdentity::from_bytes(&[0x43; 32]).unwrap();
321        let (note, witness) = cosigned_note(1_700_000_000);
322        // No signature line carries the key id of `other`, so the failure is
323        // reported as "not signed by the expected log key" rather than as a
324        // broken signature: the two are different findings for a caller.
325        assert_eq!(
326            verify_ed25519_cosignature(
327                &note,
328                "hide.example/log",
329                &other.verifying_key(),
330                &witness,
331                1_700_000_000
332            ),
333            Err(LogError::Unsigned)
334        );
335    }
336
337    /// A witness the caller did not configure cannot be substituted, even with a
338    /// correctly derived key id.
339    #[test]
340    fn a_cosignature_from_another_witness_is_refused() {
341        let log = hide_sign::SigningIdentity::from_bytes(&[0x42; 32]).unwrap();
342        let (note, _) = cosigned_note(1_700_000_000);
343        let other = SigningKey::from_bytes(&[0x52; 32]);
344        let stranger = Witness::new("witness.example", other.verifying_key().to_bytes()).unwrap();
345        assert_eq!(
346            verify_ed25519_cosignature(
347                &note,
348                "hide.example/log",
349                &log.verifying_key(),
350                &stranger,
351                1_700_000_000
352            ),
353            Err(LogError::Unsigned)
354        );
355    }
356
357    /// The request body is framed the way the specification shows it, including
358    /// the empty line before the note.
359    #[test]
360    fn the_request_body_has_the_specified_framing() {
361        let note = b"origin\n1\nAAAA\n\xe2\x80\x94 sig AAAA\n";
362        let proof = [[1_u8; 32], [2_u8; 32]];
363        let body = add_checkpoint_body(5, &proof, note).unwrap();
364        let text = String::from_utf8(body.clone()).unwrap();
365        let mut lines = text.split_inclusive('\n');
366        assert_eq!(lines.next().unwrap(), "old 5\n");
367        assert_eq!(
368            lines.next().unwrap(),
369            "AQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQE=\n"
370        );
371        assert_eq!(
372            lines.next().unwrap(),
373            "AgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgI=\n"
374        );
375        assert_eq!(lines.next().unwrap(), "\n");
376        assert_eq!(text.split("\n\n").nth(1).unwrap().as_bytes(), note);
377    }
378
379    /// A non-empty proof at size zero is refused here rather than by the witness,
380    /// because the specification makes it a `422`.
381    #[test]
382    fn a_non_empty_proof_at_size_zero_is_refused() {
383        let note = b"origin\n0\nAAAA\n";
384        assert_eq!(
385            add_checkpoint_body(0, &[[1_u8; 32]], note),
386            Err(LogError::Malformed)
387        );
388        assert!(add_checkpoint_body(0, &[], note).is_ok());
389    }
390
391    /// More proof lines than the specification allows are refused before the
392    /// body is built.
393    #[test]
394    fn too_many_proof_lines_are_refused() {
395        let note = b"origin\n1\nAAAA\n";
396        let proof = vec![[1_u8; 32]; MAX_WITNESS_PROOF_LINES + 1];
397        assert!(matches!(
398            add_checkpoint_body(1, &proof, note),
399            Err(LogError::ProofTooLong(_))
400        ));
401        assert!(add_checkpoint_body(1, &vec![[1_u8; 32]; MAX_WITNESS_PROOF_LINES], note).is_ok());
402    }
403
404    #[test]
405    fn every_named_status_is_classified() {
406        assert_eq!(
407            classify_add_checkpoint(200, b"\xe2\x80\x94 w AAAA\n").unwrap(),
408            AddCheckpointOutcome::Cosigned(b"\xe2\x80\x94 w AAAA\n".to_vec())
409        );
410        assert_eq!(
411            classify_add_checkpoint(403, b"").unwrap(),
412            AddCheckpointOutcome::NotSigned
413        );
414        assert_eq!(
415            classify_add_checkpoint(404, b"").unwrap(),
416            AddCheckpointOutcome::UnknownOrigin
417        );
418        assert_eq!(
419            classify_add_checkpoint(400, b"").unwrap(),
420            AddCheckpointOutcome::BadOldSize
421        );
422        assert_eq!(
423            classify_add_checkpoint(409, b"20852014\n").unwrap(),
424            AddCheckpointOutcome::Conflict {
425                newest_size: 20_852_014
426            }
427        );
428        assert_eq!(
429            classify_add_checkpoint(422, b"").unwrap(),
430            AddCheckpointOutcome::ProofRejected
431        );
432    }
433
434    /// A conflict body is a retry instruction, so a value the specification does
435    /// not allow must not be read as a size.
436    #[test]
437    fn a_malformed_conflict_body_is_refused() {
438        for body in [
439            &b"05\n"[..],
440            &b"+5\n"[..],
441            &b"5"[..],
442            &b"\n"[..],
443            &b"5 5\n"[..],
444            &b"18446744073709551616\n"[..],
445        ] {
446            assert_eq!(
447                classify_add_checkpoint(409, body),
448                Err(LogError::Malformed),
449                "accepted {body:?}"
450            );
451        }
452    }
453
454    /// A status the specification does not name is not mapped onto a nearby one.
455    #[test]
456    fn an_unnamed_status_is_refused() {
457        for status in [201, 301, 500, 0] {
458            assert_eq!(
459                classify_add_checkpoint(status, b""),
460                Err(LogError::Malformed)
461            );
462        }
463    }
464
465    /// A two-line input and a one-line input are not the same message.
466    #[test]
467    fn the_cosignature_input_cannot_be_shifted() {
468        assert_ne!(cosignature_input(1, "a\n"), cosignature_input(11, "\n"));
469        assert_eq!(
470            cosignature_input(1, "origin\n1\nAAAA\n"),
471            b"cosignature/v1\ntime 1\norigin\n1\nAAAA\n".to_vec()
472        );
473    }
474
475    /// A witness name a note cannot carry is a configuration error, not a
476    /// non-match discovered at verification time.
477    #[test]
478    fn an_unusable_witness_name_is_refused() {
479        assert!(Witness::new("", [0_u8; 32]).is_err());
480        assert!(Witness::new("has space", [0_u8; 32]).is_err());
481        assert!(Witness::new("has+plus", [0_u8; 32]).is_err());
482        assert!(Witness::new("witness.example", [0_u8; 32]).is_ok());
483    }
484
485    /// The empty-tree root is the RFC 6962 §2.1 hash of the empty string, which
486    /// is what a witness requires of a size-zero checkpoint.
487    #[test]
488    fn the_empty_root_matches_rfc_6962() {
489        use base64::Engine;
490        assert_eq!(
491            base64::engine::general_purpose::STANDARD.encode(empty_tree_root()),
492            "47DEQpj8HBSa+/TImW+5JCeuQeRkm5NMpJWZG3hSuFU="
493        );
494        assert!(is_empty_tree_checkpoint(&Checkpoint {
495            origin: "o".into(),
496            size: 0,
497            root: empty_tree_root(),
498        }));
499        assert!(!is_empty_tree_checkpoint(&Checkpoint {
500            origin: "o".into(),
501            size: 0,
502            root: [1_u8; 32],
503        }));
504        assert!(!is_empty_tree_checkpoint(&checkpoint(1)));
505    }
506
507    /// The two key-id derivations must not collide for the same key, or a note
508    /// carrying both kinds of line could be read wrongly.
509    #[test]
510    fn the_two_key_id_derivations_differ() {
511        let log = hide_sign::SigningIdentity::from_bytes(&[0x42; 32]).unwrap();
512        let ed = log.verifying_key().ed25519_bytes();
513        let name = "witness.example";
514        assert_ne!(
515            c2sp_key_id(name, &ed),
516            crate::key_id(name, &log.verifying_key())
517        );
518    }
519}