Witnesses for the transparency log: cosignatures and the witness rule b0621c2f8cc4

// ------------------------------------------------------------- witnesses

/// C2SP tlog-cosignature: a witness's Ed25519 cosignature.

const SIG_COSIGNATURE: u8 = 0x04;

/// Oxygen's composite cosignature beside it (spec §14.8).

const SIG_COSIG_COMPOSITE: u8 = 0x4e;

/// What a cosignature signs: `cosignature/v1`, the witness's time in

/// seconds, then the checkpoint's text.

fn cosigned_message(text: &str, time: u64) -> String {

    format!("cosignature/v1\ntime {time}\n{text}")

}

fn cosig_target(message: &str) -> ObjectRef {

    let mut h = blake3::Hasher::new();

    h.update(b"oxygen-tlog-cosig\0");

    h.update(message.as_bytes());

    ObjectRef(*h.finalize().as_bytes())

}

/// A witness's cosignature of a checkpoint's text at `time` (seconds):

/// the C2SP cosignature/v1 line, and a composite line that keeps it

/// post-quantum. Each carries the time before the signature.

pub fn cosign(

    text: &str,

    name: &str,

    witness: &Identity,

    sk: &SecretKey,

    time: u64,

) -> Result<Vec<NoteSignature>> {

    if !valid_name(name) {

        return Err(TlogError::BadNote(format!(

            "{name:?} cannot name a witness"

        )));

    }

    let message = cosigned_message(text, time);

    let mut ed = time.to_be_bytes().to_vec();

    ed.extend_from_slice(&sk.sign_ed25519(message.as_bytes()));

    let mut composite = time.to_be_bytes().to_vec();

    composite.extend_from_slice(&cbor::encode(

        &sk.sign(Domain::Checkpoint, &witness.hash(), &cosig_target(&message))

            .to_value(),

    ));

    Ok(vec![

        NoteSignature {

            name: name.to_string(),

            key_hash: key_hash(name, SIG_COSIGNATURE, &witness.ed25519_pk),

            sig: ed,

        },

        NoteSignature {

            name: name.to_string(),

            key_hash: key_hash(name, SIG_COSIG_COMPOSITE, &witness.encode()),

            sig: composite,

        },

    ])

}

impl Note {

    /// The time `witness` (named `name`) cosigned this note, once both its

    /// lines verify and agree on the time.

    pub fn cosigned_by(&self, name: &str, witness: &Identity) -> Result<u64> {

        let find = |t: u8, key: &[u8]| {

            let h = key_hash(name, t, key);

            self.sigs.iter().find(|s| s.name == name && s.key_hash == h)

        };

        let time_of = |sig: &[u8]| -> Result<(u64, Vec<u8>)> {

            if sig.len() < 9 {

                return Err(TlogError::BadSignature(format!(

                    "{name}'s cosignature is short"

                )));

            }

            let mut t = [0u8; 8];

            t.copy_from_slice(&sig[..8]);

            Ok((u64::from_be_bytes(t), sig[8..].to_vec()))

        };

        let ed = find(SIG_COSIGNATURE, &witness.ed25519_pk)

            .ok_or_else(|| TlogError::BadSignature(format!("no cosignature by {name}")))?;

        let (time, sig) = time_of(&ed.sig)?;

        let message = cosigned_message(&self.text, time);

        witness

            .verify_ed25519(message.as_bytes(), &sig)

            .map_err(|_| {

                TlogError::BadSignature(format!("{name}'s cosignature does not verify"))

            })?;

        let c = find(SIG_COSIG_COMPOSITE, &witness.encode()).ok_or_else(|| {

            TlogError::BadSignature(format!("no composite cosignature by {name}"))

        })?;

        let (ctime, csig) = time_of(&c.sig)?;

        if ctime != time {

            return Err(TlogError::BadSignature(format!(

                "{name}'s two cosignatures disagree on the time"

            )));

        }

        let sig = cbor::decode(&csig)

            .map_err(|e| e.to_string())

            .and_then(|v| Signature::from_value(&v).map_err(|e| e.to_string()))

            .map_err(|e| TlogError::BadSignature(format!("{name}'s composite cosignature: {e}")))?;

        verify(witness, &sig, Domain::Checkpoint, &cosig_target(&message)).map_err(|e| {

            TlogError::BadSignature(format!(

                "{name}'s composite cosignature does not verify: {e}"

            ))

        })?;

        Ok(time)

    }

}

/// A C2SP tlog-witness `add-checkpoint` request: the size of the last

/// checkpoint the witness cosigned for this log, the consistency proof

/// from it, and the new checkpoint note.

#[derive(Clone, Debug, PartialEq, Eq)]

pub struct AddCheckpoint {

    pub old_size: u64,

    pub proof: Vec<Hash>,

    pub note: String,

}

impl AddCheckpoint {

    pub fn encode(&self) -> String {

        let mut out = format!("old {}\n", self.old_size);

        for h in &self.proof {

            out.push_str(&crate::dsse::base64(h));

            out.push('\n');

        }

        out.push('\n');

        out.push_str(&self.note);

        out

    }

    pub fn parse(body: &str) -> Result<AddCheckpoint> {

        let bad = |w: &str| TlogError::BadNote(format!("add-checkpoint: {w}"));

        let (head, note) = body

            .split_once("\n\n")

            .ok_or_else(|| bad("no blank line before the checkpoint"))?;

        let mut lines = head.split('\n');

        let old_size = lines

            .next()

            .and_then(|l| l.strip_prefix("old "))

            .and_then(|n| n.parse().ok())

            .ok_or_else(|| bad("no old size"))?;

        let mut proof = Vec::new();

        for l in lines {

            let h = crate::dsse::base64_decode(l)

                .and_then(|b| <Hash>::try_from(b).ok())

                .ok_or_else(|| bad("a proof line is not a hash"))?;

            proof.push(h);

        }

        Ok(AddCheckpoint {

            old_size,

            proof,

            note: note.to_string(),

        })

    }

}

/// What a witness answers.

#[derive(Clone, Debug, PartialEq, Eq)]

pub enum Witnessed {

    /// Cosigned: the checkpoint, and the cosignature lines to return.

    Cosigned {

        checkpoint: Checkpoint,

        lines: Vec<NoteSignature>,

    },

    /// The request's old size is not the witness's: it answers with its own

    /// (409, so the log retries with a proof from there).

    Conflict(u64),

}

/// Why a witness refused.

#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]

pub enum WitnessError {

    /// Not signed by the log's key (403).

    #[error("{0}")]

    Unsigned(String),

    /// The checkpoint does not extend what the witness cosigned (422).

    #[error("{0}")]

    Inconsistent(String),

    /// Malformed (400).

    #[error("{0}")]

    Bad(String),

}

/// A witness: its name in cosignatures, and its key.

pub struct WitnessKey<'a> {

    pub name: &'a str,

    pub identity: &'a Identity,

    pub sk: &'a SecretKey,

}

/// A witness's decision (C2SP tlog-witness) on `req` for the log named

/// `origin` with key `log_key`, whose last cosigned checkpoint was

/// `latest` (size and root): cosign when the new checkpoint verifies and

/// extends it, as `me` at `now` (seconds).

pub fn witness(

    req: &AddCheckpoint,

    origin: &str,

    log_key: &Identity,

    latest: Option<(u64, Hash)>,

    me: &WitnessKey,

    now: u64,

) -> std::result::Result<Witnessed, WitnessError> {

    let note = Note::parse(&req.note).map_err(|e| WitnessError::Bad(e.to_string()))?;

    let cp = Checkpoint::verify(&note, origin, log_key)

        .map_err(|e| WitnessError::Unsigned(e.to_string()))?;

    let (old, old_root) = latest.unwrap_or((0, empty_root()));

    if req.old_size != old {

        return Ok(Witnessed::Conflict(old));

    }

    if cp.size < old {

        return Err(WitnessError::Bad(format!(

            "a checkpoint of {} entries is older than the {old} cosigned",

            cp.size

        )));

    }

    let consistent = match (old, cp.size == old) {

        (0, _) => req.proof.is_empty(),

        (_, true) => req.proof.is_empty() && cp.root == old_root,

        _ => check_consistency(&req.proof, cp.size, &cp.root, old, &old_root).is_ok(),

    };

    if !consistent {

        return Err(WitnessError::Inconsistent(format!(

            "the checkpoint of {} entries does not extend the one of {old} cosigned",

            cp.size

        )));

    }

    let lines = cosign(&note.text, me.name, me.identity, me.sk, now)

        .map_err(|e| WitnessError::Bad(e.to_string()))?;

    Ok(Witnessed::Cosigned {

        checkpoint: cp,

        lines,

    })

}

    }

    #[test]

    fn a_witness_cosigns_what_extends_what_it_saw_and_nothing_else() {

        let log_sk = SecretKey::generate();

        let log = log_sk.identity("log", "[email protected]", 1);

        let w_sk = SecretKey::generate();

        let w = w_sk.identity("witness", "[email protected]", 1);

        let origin = "hub.example/log";

        let (stored, _) = grow(40);

        let note_of = |n: u64| {

            Checkpoint {

                origin: origin.into(),

                size: n,

                root: tree_hash(n, &stored).unwrap(),

                extensions: vec![],

            }

            .sign(&log, &log_sk)

            .unwrap()

            .encode()

        };

        let ask = |old: u64, n: u64, latest: Option<(u64, Hash)>| {

            let proof = if old == 0 || old == n {

                vec![]

            } else {

                prove_consistency(n, old, &stored).unwrap()

            };

            let req = AddCheckpoint {

                old_size: old,

                proof,

                note: note_of(n),

            };

            let req = AddCheckpoint::parse(&req.encode()).unwrap();

            let me = WitnessKey {

                name: "w.example",

                identity: &w,

                sk: &w_sk,

            };

            witness(&req, origin, &log, latest, &me, 1_792_300_000)

        };

        // First sight, then a later checkpoint with its proof.

        let Ok(Witnessed::Cosigned { checkpoint, lines }) = ask(0, 10, None) else {

            panic!()

        };

        let mut note = Note::parse(&note_of(10)).unwrap();

        note.sigs.extend(lines);

        let back = Note::parse(&note.encode()).unwrap();

        assert_eq!(back.cosigned_by("w.example", &w).unwrap(), 1_792_300_000);

        assert!(

            back.cosigned_by("w.example", &log).is_err(),

            "another witness's key"

        );

        let latest = Some((10, checkpoint.root));

        assert!(matches!(

            ask(10, 40, latest),

            Ok(Witnessed::Cosigned { .. })

        ));

        // The log's idea of what the witness saw is wrong: told the size.

        assert_eq!(ask(5, 40, latest), Ok(Witnessed::Conflict(10)));

        // A fork: what the witness saw is not a prefix.

        let forked = Some((10, [9; 32]));

        assert!(matches!(

            ask(10, 40, forked),

            Err(WitnessError::Inconsistent(_))

        ));

        // Signed by someone else.

        let req = AddCheckpoint {

            old_size: 0,

            proof: vec![],

            note: note_of(10),

        };

        assert!(matches!(

            witness(

                &req,

                origin,

                &w,

                None,

                &WitnessKey {

                    name: "w.example",

                    identity: &w,

                    sk: &w_sk

                },

                1

            ),

            Err(WitnessError::Unsigned(_))

        ));

**Witnesses** (C2SP tlog-witness) cosign a log's checkpoints with their own keys and clocks, so a log cannot show two histories without someone seeing both. A log sends a witness `POST add-checkpoint`: `old <size>` (of the last checkpoint that witness cosigned), the consistency proof's hashes in base64 one per line, a blank line, then the checkpoint note. The witness:

- answers 409 with its own size when `old` is not it;

- answers 403 when the note does not verify with the log's key;

- answers 422 when the checkpoint does not extend the one it cosigned;

- otherwise remembers the new size and root, and returns its cosignature lines, which the log adds to the checkpoint it serves.

A cosignature is two lines under the witness's name:

- C2SP cosignature/v1 (type 0x04): the witness's time in seconds as 8 big-endian bytes, then an Ed25519 signature over `cosignature/v1\ntime <seconds>\n` followed by the checkpoint's text;

- a composite line (type 0x4e): the same time, then the CBOR of a composite Signature in domain `checkpoint` over `BLAKE3("oxygen-tlog-cosig\0" || that message)`.

A reader counts a cosignature only when both lines verify and agree on the time.