crates/gunnar-core/src/transparency.rs
//! **The transparency log's arithmetic**: a Merkle tree over records, and a
//! signed tree head over the tree.
//!
//! Push attestation already appends one JSON line per push to an append-only file. Append-only
//! is a *discipline*, not a proof: nothing stops a file being rewritten, and
//! nothing in the file says it has not been. This module is what turns the
//! discipline into evidence.
//!
//! # The shape, and why it is RFC 6962's
//!
//! Certificate Transparency solved this problem, in public, against adversaries,
//! and its hashing rules are three lines:
//!
//! ```text
//! leaf(record) = SHA-256(0x00 ‖ record)
//! node(left,right) = SHA-256(0x01 ‖ left ‖ right)
//! root([]) = SHA-256("")
//! ```
//!
//! The domain-separating prefixes are the load-bearing part. Without them a leaf
//! whose bytes happen to be two concatenated hashes could be presented as an
//! interior node, and an attacker could show a "proof" for a record the log
//! never held (the second-preimage attack every naive Merkle implementation
//! has). Reimplementing this without the prefixes would be a Merkle tree with a
//! hole in it, so the prefixes are here and are tested.
//!
//! An odd node is **promoted, not duplicated**: a level with an odd count
//! carries the last hash up unchanged. Duplicating it instead is the flaw that
//! let two different trees share a root in early Bitcoin.
//!
//! # What signs a tree head, and why it is `sshsig`
//!
//! The same format everything else in this repository signs with: commits
//! (`gunnar-policy`), gRPC challenges (`gunnar-grpc`), and now tree heads. One
//! signature format means one verifier to trust and one that has already been
//! looked at — and it means a client can check a tree head with `ssh-keygen -Y
//! verify` and no gunnar at all.
//!
//! The namespace is [`STH_NAMESPACE`], and it is not the namespace anything else
//! signs under: a signature made for one namespace does not verify in another,
//! so a commit signature can never be replayed as a tree head and vice versa.
use sha2::Digest as _;
/// The `sshsig` namespace a signed tree head is signed under.
///
/// Distinct from `git` (commits) and `gunnar-grpc` (control-plane challenges) on
/// purpose: `sshsig` binds the namespace into what is signed, so a signature
/// made under one cannot be presented as another.
pub const STH_NAMESPACE: &str = "gunnar-transparency";
/// RFC 6962's leaf prefix. Domain separation; see the module docs.
const LEAF_PREFIX: u8 = 0x00;
/// RFC 6962's interior-node prefix.
const NODE_PREFIX: u8 = 0x01;
/// A 32-byte SHA-256 digest.
pub type Hash = [u8; 32];
/// SHA-256 of some bytes, as lowercase hex.
pub fn digest_bytes(bytes: &[u8]) -> String {
let digest: Hash = sha2::Sha256::digest(bytes).into();
hex(&digest)
}
/// Render a hash the way every field in this repository renders one: lowercase
/// hex.
pub fn hex(hash: &Hash) -> String {
let mut out = String::with_capacity(64);
for byte in hash {
out.push_str(&format!("{byte:02x}"));
}
out
}
/// Parse a 64-character lowercase hex digest.
pub fn unhex(text: &str) -> Option<Hash> {
if text.len() != 64 {
return None;
}
let mut out = [0u8; 32];
for (index, slot) in out.iter_mut().enumerate() {
*slot = u8::from_str_radix(text.get(index * 2..index * 2 + 2)?, 16).ok()?;
}
Some(out)
}
/// `SHA-256(0x00 ‖ record)` — one record's leaf hash.
pub fn leaf_hash(record: &[u8]) -> Hash {
let mut hasher = sha2::Sha256::new();
hasher.update([LEAF_PREFIX]);
hasher.update(record);
hasher.finalize().into()
}
/// `SHA-256(0x01 ‖ left ‖ right)` — one interior node.
pub fn node_hash(left: &Hash, right: &Hash) -> Hash {
let mut hasher = sha2::Sha256::new();
hasher.update([NODE_PREFIX]);
hasher.update(left);
hasher.update(right);
hasher.finalize().into()
}
/// The Merkle root over `leaves`, in order.
///
/// An empty log hashes to `SHA-256("")`, which is RFC 6962's rule and is a
/// *value* rather than an absence — an empty log can be signed, and a signed
/// empty head is how a verifier learns the log exists and holds nothing.
pub fn root(leaves: &[Hash]) -> Hash {
if leaves.is_empty() {
return sha2::Sha256::digest([]).into();
}
let mut level: Vec<Hash> = leaves.to_vec();
while level.len() > 1 {
let mut next = Vec::with_capacity(level.len().div_ceil(2));
let mut pairs = level.chunks_exact(2);
for pair in &mut pairs {
next.push(node_hash(&pair[0], &pair[1]));
}
// Promoted, not duplicated. See the module docs.
if let [odd] = pairs.remainder() {
next.push(*odd);
}
level = next;
}
level[0]
}
/// The sibling hashes that carry `index` up to the root of a tree of `leaves`.
///
/// `None` when `index` is out of range — a proof for a record the log does not
/// hold is not an empty proof, and returning one would make "verified" the
/// answer for a leaf that was never there.
pub fn inclusion_proof(leaves: &[Hash], index: usize) -> Option<Vec<Hash>> {
if index >= leaves.len() {
return None;
}
let mut proof = Vec::new();
let mut level: Vec<Hash> = leaves.to_vec();
let mut at = index;
while level.len() > 1 {
// The promoted-odd rule again, and it has to be mirrored exactly: a
// node with no sibling contributes nothing to the path.
let sibling = if at % 2 == 0 { at + 1 } else { at - 1 };
if sibling < level.len() {
proof.push(level[sibling]);
}
let mut next = Vec::with_capacity(level.len().div_ceil(2));
let mut pairs = level.chunks_exact(2);
for pair in &mut pairs {
next.push(node_hash(&pair[0], &pair[1]));
}
if let [odd] = pairs.remainder() {
next.push(*odd);
}
level = next;
at /= 2;
}
Some(proof)
}
/// Recompute a root from one leaf and its proof, and compare.
///
/// This is the whole point of the module: a client with a record, its position,
/// the tree size and a signed root can check membership **without the log**.
pub fn verify_inclusion(
leaf: &Hash,
index: usize,
size: usize,
proof: &[Hash],
expected_root: &Hash,
) -> bool {
if index >= size {
return false;
}
let mut computed = *leaf;
let mut at = index;
let mut width = size;
let mut steps = proof.iter();
while width > 1 {
let sibling = if at % 2 == 0 { at + 1 } else { at - 1 };
if sibling < width {
let Some(step) = steps.next() else {
// The proof ran out before the tree did. A short proof must be
// a refusal and never a pass: padding it with anything at all
// would let a truncated proof verify.
return false;
};
computed = if at % 2 == 0 {
node_hash(&computed, step)
} else {
node_hash(step, &computed)
};
}
at /= 2;
width = width.div_ceil(2);
}
// A proof with steps left over describes a different tree.
steps.next().is_none() && computed == *expected_root
}
/// **What a log signs**: how many records it holds and what they hash to.
///
/// The pair is the claim. A root alone says nothing about *when* — the same
/// root can be reissued for ever — and a size alone is not a commitment to
/// content. Together they say: *at this moment I held exactly these N records,
/// in this order.*
#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
#[serde(deny_unknown_fields)]
pub struct TreeHead {
/// How many records the log held.
pub size: u64,
/// [`root`] over those records, hex.
pub root: String,
/// When the head was issued.
pub at_unix_ms: i64,
}
impl TreeHead {
/// The exact bytes that are signed.
///
/// A fixed, line-oriented rendering rather than the JSON: JSON has no
/// canonical form, so signing the serialisation would make the signature
/// depend on a serialiser's field order. Three lines and a label cannot
/// drift.
pub fn signing_bytes(&self) -> Vec<u8> {
format!(
"gunnar-transparency-v1\nsize {}\nroot {}\nat {}\n",
self.size, self.root, self.at_unix_ms
)
.into_bytes()
}
}
/// A [`TreeHead`] with the signature that makes it evidence.
#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
#[serde(deny_unknown_fields)]
pub struct SignedTreeHead {
/// The head the signature is over.
#[serde(flatten)]
pub head: TreeHead,
/// `SHA256:…` of the key that signed it, so a verifier knows which key to
/// look up before it does any crypto.
pub key_fingerprint: String,
/// The `sshsig`, PEM-armoured, newlines and all.
pub signature: String,
}
/// What went wrong verifying a tree head.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum TreeHeadProblem {
/// The signature is not a well-formed `sshsig`.
Malformed(String),
/// The head names a key that is not the one offered.
WrongKey {
/// The fingerprint the head claims.
signed_by: String,
/// The fingerprint of the key given to check it.
offered: String,
},
/// The signature does not verify against the key.
NotVerified,
}
impl std::fmt::Display for TreeHeadProblem {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
TreeHeadProblem::Malformed(why) => write!(
f,
"the tree head's signature is not a \
well-formed sshsig: {why}"
),
TreeHeadProblem::WrongKey { signed_by, offered } => write!(
f,
"the tree head says it was signed by {signed_by} and was checked against {offered}"
),
TreeHeadProblem::NotVerified => {
write!(f, "the tree head's signature does not verify")
}
}
}
}
/// Sign a tree head with `key`, under [`STH_NAMESPACE`].
pub fn sign_tree_head(
key: &ssh_key::PrivateKey,
head: TreeHead,
) -> Result<SignedTreeHead, ssh_key::Error> {
let signature = key.sign(
STH_NAMESPACE,
ssh_key::HashAlg::Sha512,
&head.signing_bytes(),
)?;
Ok(SignedTreeHead {
key_fingerprint: key
.public_key()
.fingerprint(ssh_key::HashAlg::Sha256)
.to_string(),
signature: signature.to_pem(ssh_key::LineEnding::LF)?,
head,
})
}
/// Verify a signed tree head against a public key.
///
/// The fingerprint in the record is checked against the key **before** the
/// signature, so a head signed by key A can never be reported as verified by
/// key B even if the caller looked up the wrong row.
pub fn verify_tree_head(
sth: &SignedTreeHead,
key: &ssh_key::PublicKey,
) -> Result<(), TreeHeadProblem> {
let offered = key.fingerprint(ssh_key::HashAlg::Sha256).to_string();
if offered != sth.key_fingerprint {
return Err(TreeHeadProblem::WrongKey {
signed_by: sth.key_fingerprint.clone(),
offered,
});
}
let signature = ssh_key::SshSig::from_pem(sth.signature.as_bytes())
.map_err(|err| TreeHeadProblem::Malformed(err.to_string()))?;
if signature.namespace() != STH_NAMESPACE {
return Err(TreeHeadProblem::Malformed(format!(
"namespace is {:?}, not {STH_NAMESPACE:?}",
signature.namespace()
)));
}
key.verify(STH_NAMESPACE, &sth.head.signing_bytes(), &signature)
.map_err(|_| TreeHeadProblem::NotVerified)
}
#[cfg(test)]
mod tests {
use super::*;
fn leaves(n: usize) -> Vec<Hash> {
(0..n)
.map(|i| leaf_hash(format!("record {i}").as_bytes()))
.collect()
}
/// **The prefixes are what stop a second-preimage attack**, so they are
/// asserted rather than assumed: a leaf and a node over the same bytes must
/// not collide.
#[test]
fn a_leaf_and_a_node_over_the_same_bytes_are_different_hashes() {
let a = leaf_hash(b"x");
let b = leaf_hash(b"y");
let mut concatenated = Vec::new();
concatenated.extend_from_slice(&a);
concatenated.extend_from_slice(&b);
assert_ne!(
leaf_hash(&concatenated),
node_hash(&a, &b),
"a leaf whose bytes are two hashes hashes like an interior node, so a proof can be \
forged for a record the log never held"
);
}
/// An odd leaf is **promoted**, not duplicated — and the two rules give
/// different roots, which is why it has to be said.
#[test]
fn an_odd_leaf_is_promoted_and_not_duplicated() {
let three = leaves(3);
let promoted = root(&three);
let duplicated = {
let pair = node_hash(&three[0], &three[1]);
let doubled = node_hash(&three[2], &three[2]);
node_hash(&pair, &doubled)
};
assert_ne!(
promoted, duplicated,
"promotion and duplication produced the same root, so this test cannot tell them \
apart and the rule below is unasserted"
);
}
/// Every leaf in every size up to 33 proves, and every proof is checked
/// against the size it was made for.
#[test]
fn every_leaf_of_every_size_proves_against_its_own_root() {
for size in 1..=33 {
let set = leaves(size);
let expected = root(&set);
for index in 0..size {
let proof = inclusion_proof(&set, index).expect("a leaf that is in the tree");
assert!(
verify_inclusion(&set[index], index, size, &proof, &expected),
"leaf {index} of {size} did not verify"
);
}
}
}
/// The refusals. Each one is a way a verifier could be talked into saying
/// yes, and each must say no.
#[test]
fn a_forged_or_truncated_or_misplaced_proof_is_refused() {
let set = leaves(8);
let expected = root(&set);
let proof = inclusion_proof(&set, 3).expect("in the tree");
assert!(
!verify_inclusion(&set[3], 4, 8, &proof, &expected),
"a proof for leaf 3 verified at position 4"
);
assert!(
!verify_inclusion(&set[4], 3, 8, &proof, &expected),
"a different leaf verified with leaf 3's proof"
);
assert!(
!verify_inclusion(&set[3], 3, 8, &proof[..proof.len() - 1], &expected),
"a TRUNCATED proof verified; a short proof must be a refusal"
);
let mut too_long = proof.clone();
too_long.push([0u8; 32]);
assert!(
!verify_inclusion(&set[3], 3, 8, &too_long, &expected),
"a proof with a step left over verified; it describes a different tree"
);
assert!(
!verify_inclusion(&set[3], 3, 8, &proof, &[0u8; 32]),
"a proof verified against a root nobody signed"
);
assert!(
inclusion_proof(&set, 8).is_none(),
"a proof was produced for a leaf past the end of the log"
);
}
/// **Rewriting one record changes the root**, which is the property the
/// whole log exists for.
#[test]
fn changing_one_record_changes_the_root() {
let mut set = leaves(9);
let before = root(&set);
set[4] = leaf_hash(b"record 4, tampered with");
assert_ne!(
before,
root(&set),
"a record was rewritten and the root did not move, so a signed head over the old \
root still covers the new file"
);
}
#[test]
fn hex_round_trips_and_refuses_what_is_not_a_digest() {
let h = leaf_hash(b"x");
assert_eq!(unhex(&hex(&h)), Some(h));
assert_eq!(unhex("short"), None);
assert_eq!(unhex(&"z".repeat(64)), None);
}
/// A tree head signs and verifies, and every way of getting it wrong is
/// refused: a different key, a moved size, a moved root, another namespace.
#[test]
fn a_tree_head_verifies_and_a_tampered_one_does_not() {
let pem = crate::mint_ed25519().expect("mint a key");
let key = ssh_key::PrivateKey::from_openssh(&pem).expect("parse");
let other = ssh_key::PrivateKey::from_openssh(crate::mint_ed25519().expect("a second key"))
.expect("parse");
let head = TreeHead {
size: 7,
root: hex(&root(&leaves(7))),
at_unix_ms: 1_700_000_000_000,
};
let sth = sign_tree_head(&key, head.clone()).expect("sign");
assert_eq!(verify_tree_head(&sth, key.public_key()), Ok(()));
assert!(matches!(
verify_tree_head(&sth, other.public_key()),
Err(TreeHeadProblem::WrongKey { .. })
));
let mut moved = sth.clone();
moved.head.size = 8;
assert_eq!(
verify_tree_head(&moved, key.public_key()),
Err(TreeHeadProblem::NotVerified),
"a head whose size was changed still verified"
);
let mut rerooted = sth.clone();
rerooted.head.root = hex(&[0u8; 32]);
assert_eq!(
verify_tree_head(&rerooted, key.public_key()),
Err(TreeHeadProblem::NotVerified),
"a head whose root was changed still verified"
);
// A signature made under another namespace must not be accepted here,
// which is what stops a commit signature being presented as a head.
let elsewhere = key
.sign("git", ssh_key::HashAlg::Sha512, &head.signing_bytes())
.expect("sign under another namespace");
let smuggled = SignedTreeHead {
head,
key_fingerprint: sth.key_fingerprint.clone(),
signature: elsewhere.to_pem(ssh_key::LineEnding::LF).expect("armour"),
};
assert!(matches!(
verify_tree_head(&smuggled, key.public_key()),
Err(TreeHeadProblem::Malformed(_))
));
}
}