use sha2::{Digest, Sha256};
use thiserror::Error;
mod checkpoint;
pub use checkpoint::{
CHECKPOINT_CONTEXT, Checkpoint, MAX_NOTE_BYTES, MAX_ORIGIN_BYTES, NoteSignature, SignedNote,
key_id,
};
mod witness;
pub use witness::{
AddCheckpointOutcome, C2SP_ED25519_ALGORITHM, Cosignature, MAX_WITNESS_PROOF_LINES, Witness,
add_checkpoint_body, c2sp_key_id, classify_add_checkpoint, cosignature_input, empty_tree_root,
is_empty_tree_checkpoint, verify_ed25519_cosignature,
};
const LEAF_PREFIX: u8 = 0x00;
const NODE_PREFIX: u8 = 0x01;
const MAX_PROOF_LEN: usize = 64;
pub type Hash = [u8; 32];
#[derive(Debug, Error, PartialEq, Eq)]
pub enum LogError {
#[error("the log is empty")]
Empty,
#[error("entry {index} is not in a log of size {size}")]
OutOfRange { index: u64, size: u64 },
#[error("a log of size {old} cannot be a prefix of one of size {new}")]
NotAPrefix { old: u64, new: u64 },
#[error("the proof does not verify")]
BadProof,
#[error("a proof of {0} hashes exceeds the limit")]
ProofTooLong(usize),
#[error("the encoding is malformed")]
Malformed,
#[error("the checkpoint is not signed by the expected log key")]
Unsigned,
#[error("a signature from the expected log key does not verify")]
BadSignature,
#[error("the checkpoint names origin {found:?}, not the expected one")]
WrongOrigin { found: String },
}
const IDENTITY_LEAF_LABEL: &[u8] = b"HIDE/1.0 identity leaf";
const EPOCH_LEAF_LABEL: &[u8] = b"HIDE/1.0 epoch leaf";
pub fn identity_leaf(root: &Hash, recovery_id: &Hash, head: &Hash, entries: u64) -> Vec<u8> {
let mut out = Vec::with_capacity(IDENTITY_LEAF_LABEL.len() + 104);
out.extend_from_slice(IDENTITY_LEAF_LABEL);
out.extend_from_slice(root);
out.extend_from_slice(recovery_id);
out.extend_from_slice(head);
out.extend_from_slice(&entries.to_be_bytes());
out
}
pub fn epoch_leaf(identity_root: &Hash, chain_head: &Hash, epochs: u64) -> Vec<u8> {
let mut out = Vec::with_capacity(EPOCH_LEAF_LABEL.len() + 72);
out.extend_from_slice(EPOCH_LEAF_LABEL);
out.extend_from_slice(identity_root);
out.extend_from_slice(chain_head);
out.extend_from_slice(&epochs.to_be_bytes());
out
}
const INCLUSION_TAG: u8 = 0x01;
const CONSISTENCY_TAG: u8 = 0x02;
const PROOF_HEADER: usize = 18;
fn encode_proof(tag: u8, first: u64, second: u64, path: &[Hash]) -> Result<Vec<u8>, LogError> {
if path.len() > MAX_PROOF_LEN {
return Err(LogError::ProofTooLong(path.len()));
}
let mut out = Vec::with_capacity(PROOF_HEADER + 32 * path.len());
out.push(tag);
out.extend_from_slice(&first.to_be_bytes());
out.extend_from_slice(&second.to_be_bytes());
out.push(path.len() as u8);
for hash in path {
out.extend_from_slice(hash);
}
Ok(out)
}
fn decode_proof(tag: u8, bytes: &[u8]) -> Result<(u64, u64, Vec<Hash>), LogError> {
if bytes.len() < PROOF_HEADER || bytes[0] != tag {
return Err(LogError::Malformed);
}
let first = u64::from_be_bytes(bytes[1..9].try_into().map_err(|_| LogError::Malformed)?);
let second = u64::from_be_bytes(bytes[9..17].try_into().map_err(|_| LogError::Malformed)?);
let count = usize::from(bytes[17]);
if count > MAX_PROOF_LEN {
return Err(LogError::ProofTooLong(count));
}
if bytes.len() != PROOF_HEADER + 32 * count {
return Err(LogError::Malformed);
}
let path = bytes[PROOF_HEADER..]
.chunks_exact(32)
.map(|chunk| chunk.try_into().map_err(|_| LogError::Malformed))
.collect::<Result<Vec<Hash>, _>>()?;
Ok((first, second, path))
}
impl InclusionProof {
pub fn encode(&self) -> Result<Vec<u8>, LogError> {
encode_proof(INCLUSION_TAG, self.index, self.size, &self.path)
}
pub fn decode(bytes: &[u8]) -> Result<Self, LogError> {
let (index, size, path) = decode_proof(INCLUSION_TAG, bytes)?;
Ok(Self { index, size, path })
}
}
impl ConsistencyProof {
pub fn encode(&self) -> Result<Vec<u8>, LogError> {
encode_proof(CONSISTENCY_TAG, self.old_size, self.new_size, &self.path)
}
pub fn decode(bytes: &[u8]) -> Result<Self, LogError> {
let (old_size, new_size, path) = decode_proof(CONSISTENCY_TAG, bytes)?;
Ok(Self {
old_size,
new_size,
path,
})
}
}
pub fn leaf_hash(data: &[u8]) -> Hash {
let mut hasher = Sha256::new();
hasher.update([LEAF_PREFIX]);
hasher.update(data);
hasher.finalize().into()
}
fn node_hash(left: &Hash, right: &Hash) -> Hash {
let mut hasher = Sha256::new();
hasher.update([NODE_PREFIX]);
hasher.update(left);
hasher.update(right);
hasher.finalize().into()
}
fn root_of(leaves: &[Hash]) -> Hash {
match leaves.len() {
0 => Sha256::digest(b"").into(),
1 => leaves[0],
n => {
let split = largest_power_of_two_below(n as u64) as usize;
node_hash(&root_of(&leaves[..split]), &root_of(&leaves[split..]))
}
}
}
fn largest_power_of_two_below(n: u64) -> u64 {
debug_assert!(n > 1);
1 << (n - 1).ilog2()
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct InclusionProof {
pub index: u64,
pub size: u64,
pub path: Vec<Hash>,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ConsistencyProof {
pub old_size: u64,
pub new_size: u64,
pub path: Vec<Hash>,
}
#[derive(Debug, Default, Clone)]
pub struct TransparencyLog {
leaves: Vec<Hash>,
}
impl TransparencyLog {
pub fn new() -> Self {
Self::default()
}
pub fn append(&mut self, data: &[u8]) -> u64 {
let index = self.leaves.len() as u64;
self.leaves.push(leaf_hash(data));
index
}
pub fn len(&self) -> u64 {
self.leaves.len() as u64
}
pub fn is_empty(&self) -> bool {
self.leaves.is_empty()
}
pub fn root(&self) -> Hash {
root_of(&self.leaves)
}
pub fn root_at(&self, size: u64) -> Result<Hash, LogError> {
if size > self.len() {
return Err(LogError::OutOfRange {
index: size,
size: self.len(),
});
}
Ok(root_of(&self.leaves[..size as usize]))
}
pub fn prove_inclusion(&self, index: u64, size: u64) -> Result<InclusionProof, LogError> {
if size > self.len() || index >= size {
return Err(LogError::OutOfRange { index, size });
}
let mut path = Vec::new();
collect_inclusion(&self.leaves[..size as usize], index as usize, &mut path);
Ok(InclusionProof { index, size, path })
}
pub fn prove_consistency(
&self,
old_size: u64,
new_size: u64,
) -> Result<ConsistencyProof, LogError> {
if new_size > self.len() {
return Err(LogError::OutOfRange {
index: new_size,
size: self.len(),
});
}
if old_size > new_size || old_size == 0 {
return Err(LogError::NotAPrefix {
old: old_size,
new: new_size,
});
}
let mut path = Vec::new();
collect_consistency(
&self.leaves[..new_size as usize],
old_size as usize,
true,
&mut path,
);
Ok(ConsistencyProof {
old_size,
new_size,
path,
})
}
}
fn collect_inclusion(leaves: &[Hash], index: usize, path: &mut Vec<Hash>) {
if leaves.len() <= 1 {
return;
}
let split = largest_power_of_two_below(leaves.len() as u64) as usize;
if index < split {
collect_inclusion(&leaves[..split], index, path);
path.push(root_of(&leaves[split..]));
} else {
collect_inclusion(&leaves[split..], index - split, path);
path.push(root_of(&leaves[..split]));
}
}
fn collect_consistency(leaves: &[Hash], old: usize, complete: bool, path: &mut Vec<Hash>) {
if old == leaves.len() {
if !complete {
path.push(root_of(leaves));
}
return;
}
let split = largest_power_of_two_below(leaves.len() as u64) as usize;
if old <= split {
collect_consistency(&leaves[..split], old, complete, path);
path.push(root_of(&leaves[split..]));
} else {
collect_consistency(&leaves[split..], old - split, false, path);
path.push(root_of(&leaves[..split]));
}
}
pub fn verify_inclusion(proof: &InclusionProof, leaf: &Hash, root: &Hash) -> Result<(), LogError> {
if proof.path.len() > MAX_PROOF_LEN {
return Err(LogError::ProofTooLong(proof.path.len()));
}
if proof.index >= proof.size {
return Err(LogError::OutOfRange {
index: proof.index,
size: proof.size,
});
}
let mut turns = Vec::new();
let mut index = proof.index;
let mut size = proof.size;
while size > 1 {
let split = largest_power_of_two_below(size);
if index < split {
turns.push(true);
size = split;
} else {
turns.push(false);
index -= split;
size -= split;
}
}
if turns.len() != proof.path.len() {
return Err(LogError::BadProof);
}
let mut hash = *leaf;
for (sibling, went_left) in proof.path.iter().zip(turns.iter().rev()) {
hash = if *went_left {
node_hash(&hash, sibling)
} else {
node_hash(sibling, &hash)
};
}
if hash != *root {
return Err(LogError::BadProof);
}
Ok(())
}
pub fn verify_consistency(
proof: &ConsistencyProof,
old_root: &Hash,
new_root: &Hash,
) -> Result<(), LogError> {
if proof.path.len() > MAX_PROOF_LEN {
return Err(LogError::ProofTooLong(proof.path.len()));
}
if proof.old_size == 0 || proof.old_size > proof.new_size {
return Err(LogError::NotAPrefix {
old: proof.old_size,
new: proof.new_size,
});
}
if proof.old_size == proof.new_size {
return if proof.path.is_empty() && old_root == new_root {
Ok(())
} else {
Err(LogError::BadProof)
};
}
let mut turns = Vec::new();
let mut old_size = proof.old_size;
let mut new_size = proof.new_size;
let mut complete = true;
while old_size != new_size {
let split = largest_power_of_two_below(new_size);
if old_size <= split {
turns.push(true);
new_size = split;
} else {
turns.push(false);
old_size -= split;
new_size -= split;
complete = false;
}
}
let expected = turns.len() + usize::from(!complete);
if proof.path.len() != expected {
return Err(LogError::BadProof);
}
let mut path = proof.path.iter();
let seed = if complete {
*old_root
} else {
*path.next().ok_or(LogError::BadProof)?
};
let mut old_hash = seed;
let mut new_hash = seed;
for (sibling, went_left) in path.zip(turns.iter().rev()) {
if *went_left {
new_hash = node_hash(&new_hash, sibling);
} else {
old_hash = node_hash(sibling, &old_hash);
new_hash = node_hash(sibling, &new_hash);
}
}
if old_hash != *old_root || new_hash != *new_root {
return Err(LogError::BadProof);
}
Ok(())
}
pub fn encode_checkpoint(size: u64, root: &Hash) -> Vec<u8> {
let mut out = Vec::with_capacity(40);
out.extend_from_slice(&size.to_be_bytes());
out.extend_from_slice(root);
out
}
pub fn decode_checkpoint(bytes: &[u8]) -> Result<(u64, Hash), LogError> {
if bytes.len() != 40 {
return Err(LogError::Malformed);
}
let size = u64::from_be_bytes(bytes[..8].try_into().map_err(|_| LogError::Malformed)?);
let root: Hash = bytes[8..].try_into().map_err(|_| LogError::Malformed)?;
Ok((size, root))
}