use crate::derivation::{Derivations, Registered};
use crate::store::CheckpointedLog;
pub use crate::store::{Record, RecordSource};
use crate::substrate::{StatedCheckpoint, SubstrateError};
use evidence_request::cll_material::{
encode_consistency_proof, encode_inclusion_proof, KIND_CHECKPOINT, KIND_CONSISTENCY,
KIND_INCLUSION,
};
use evidence_request::envelope::{
sign_with_profile, Anchor, AnchorFreshness, Envelope, EnvelopeParts, Signer,
};
use evidence_request::request::{Coverage, Derivation, Freshness, Request, Subject};
use evidence_request::resolve::{self, ResolvedAnchor};
use serde_json::{json, Map, Value};
use sha2::{Digest, Sha256};
pub const DERIVATION_HISTORY_CARD: &str = "history_card/1";
pub use evidence_request::history_card::DERIVATION_HISTORY_CARD_2;
pub const DEFAULT_HISTORY_WINDOW: usize = 16;
pub const MIN_HISTORY_WINDOW: usize = 1;
pub const MAX_HISTORY_WINDOW: usize = evidence_request::history_card::MAX_WINDOW as usize;
pub const DERIVATION_STANDARD_HISTORY: &str = crate::standard_history::DERIVATION;
pub const MAX_RECORDS: u64 = 10_000;
#[derive(Debug, thiserror::Error)]
pub enum AnswerError {
#[error("the resolved anchor is not one of the stream's stated checkpoints")]
AnchorNotFound,
#[error("no stated checkpoint covers a record citing the half yet")]
CitingNotAnchored,
#[error("a record the subject names is not in the log under the anchor")]
RecordNotFound,
#[error("the subject resolves to no records under the anchor")]
NoRecords,
#[error("a record's octets do not recompute its committed entry")]
RecordDigest,
#[error("the derivation has no answer path")]
DerivationUnsupported,
#[error("the store holds no header for a record the derivation projects")]
RecordHeader,
#[error("the derivation is prepared for another recipient")]
NotAuthorized,
#[error("the answer would carry more than the limit of records or checkpoints")]
OverLimit,
#[error("the history window is {0}, not 1 to 64")]
HistoryWindow(usize),
#[error("the artifact cannot be canonicalized: {0}")]
Artifact(String),
#[error("the envelope could not be signed: {0}")]
Sign(#[from] evidence_request::envelope::SignError),
#[error(transparent)]
Substrate(#[from] SubstrateError),
}
pub type Derive<'a> = &'a dyn Fn(&str, &Subject, &StatedCheckpoint) -> Option<(String, Value)>;
#[derive(Clone, Copy, Default)]
pub struct Options<'a> {
pub prove_beyond_profile: bool,
pub derive: Option<Derive<'a>>,
pub derivations: Option<&'a Derivations>,
pub requester: Option<&'a str>,
pub standard_card: Option<&'a [u8]>,
pub history_window: usize,
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Selection {
pub at: usize,
pub records: Vec<u64>,
}
fn sha256_hex(bytes: &[u8]) -> String {
hex::encode(Sha256::digest(bytes))
}
pub fn anchor_digest(checkpoint: &StatedCheckpoint) -> String {
sha256_hex(&checkpoint.statement)
}
pub fn anchors(log: &dyn CheckpointedLog) -> Result<Vec<resolve::Anchor>, SubstrateError> {
log.stated_checkpoints()?
.iter()
.map(|cp| {
Ok(resolve::Anchor {
digest: anchor_digest(cp),
size: cp.checkpoint.leaf_count()?,
issued_at: cp.checkpoint.timestamp.clone(),
})
})
.collect()
}
#[allow(clippy::too_many_arguments)]
pub fn answer(
log: &dyn CheckpointedLog,
records: &dyn RecordSource,
request: &Request,
request_bytes: &[u8],
anchor: &ResolvedAnchor,
limit: u64,
signer: &dyn Signer,
issued_at: &str,
) -> Result<Envelope, AnswerError> {
let selection = select(log, records, request, anchor, limit)?;
build(
log,
records,
request,
request_bytes,
anchor,
&selection,
Options::default(),
signer,
issued_at,
)
}
pub fn serving_checkpoint(
records: &dyn RecordSource,
checkpoints: &[StatedCheckpoint],
anchor: &ResolvedAnchor,
) -> Result<usize, AnswerError> {
match anchor {
ResolvedAnchor::Anchor(a) => checkpoints
.iter()
.position(|cp| anchor_digest(cp) == a.digest)
.ok_or(AnswerError::AnchorNotFound),
ResolvedAnchor::ExchangeHalf(half) => {
citing_anchor(records, checkpoints, half)?.ok_or(AnswerError::CitingNotAnchored)
}
}
}
pub fn select(
log: &dyn CheckpointedLog,
records: &dyn RecordSource,
request: &Request,
anchor: &ResolvedAnchor,
limit: u64,
) -> Result<Selection, AnswerError> {
let checkpoints = log.stated_checkpoints()?;
let at = serving_checkpoint(records, &checkpoints, anchor)?;
let covered = checkpoints[at].checkpoint.leaf_count()?;
let limit = limit.min(MAX_RECORDS);
let listed = at as u64 + 1;
let leaves = match (&request.derivation, &request.subject) {
(Some(Derivation::Token(t)), _) if t == DERIVATION_HISTORY_CARD => {
if listed > limit {
return Err(AnswerError::OverLimit);
}
Vec::new()
}
(Some(Derivation::Token(_)), _) => Vec::new(),
(Some(Derivation::Digest(_)), Subject::Checkpoints) => Vec::new(),
(_, Subject::Checkpoints) => {
if listed > limit {
return Err(AnswerError::OverLimit);
}
Vec::new()
}
(_, Subject::CheckpointRange(a, b)) => {
if b - a + 1 > limit {
return Err(AnswerError::OverLimit);
}
Vec::new()
}
(_, Subject::Record(_)) if limit == 0 => return Err(AnswerError::OverLimit),
(_, Subject::Record(d)) => {
let leaf = records
.leaf_index_of(d)
.filter(|&i| i < covered)
.ok_or(AnswerError::RecordNotFound)?;
vec![leaf]
}
(_, Subject::Range(a, b)) => range_leaves(*a, *b, covered, limit)?,
(_, Subject::FullHistory) => {
if covered == 0 {
return Err(AnswerError::NoRecords);
}
range_leaves(0, covered - 1, covered, limit)?
}
(_, Subject::Correlation(id)) => leaves_under(records.correlation(id), covered, limit)?,
(_, _) => {
let half = citing_half(&request.subject).expect("every other form is matched above");
leaves_under(records.citing(half), covered, limit)?
}
};
Ok(Selection {
at,
records: leaves,
})
}
#[allow(clippy::too_many_arguments)]
pub fn build(
log: &dyn CheckpointedLog,
records: &dyn RecordSource,
request: &Request,
request_bytes: &[u8],
anchor: &ResolvedAnchor,
selection: &Selection,
options: Options<'_>,
signer: &dyn Signer,
issued_at: &str,
) -> Result<Envelope, AnswerError> {
let checkpoints = log.stated_checkpoints()?;
let at = checkpoints
.get(selection.at)
.ok_or(AnswerError::AnchorNotFound)?;
let chain = &checkpoints[..=selection.at];
let mut head = Map::new();
head.insert("anchor".into(), json!(anchor_digest(at)));
head.insert("evidence_stream".into(), json!(at.checkpoint.log_id));
head.insert(
"subject".into(),
evidence_request::envelope::subject_value(&request.subject),
);
let mut material: Vec<(String, Vec<u8>)> = Vec::new();
let registered = |id: &str| options.derivations.and_then(|d| d.get(id)).is_some();
let derived = match (&request.derivation, options.derive) {
(Some(Derivation::Token(t)), Some(derive))
if t != DERIVATION_HISTORY_CARD
&& t != DERIVATION_HISTORY_CARD_2
&& t != DERIVATION_STANDARD_HISTORY =>
{
derive(t, &request.subject, at).map(|d| (t.clone(), d))
}
(Some(Derivation::Digest(id)), Some(derive)) if !registered(id) => {
derive(id, &request.subject, at).map(|d| (id.clone(), d))
}
_ => None,
};
let artifact = match (&request.derivation, &request.subject) {
(Some(Derivation::Token(t)), _) if t == DERIVATION_HISTORY_CARD => {
let mut history = Vec::with_capacity(chain.len());
for (i, cp) in chain.iter().enumerate() {
let consistency = match i.checked_sub(1).map(|p| &chain[p]) {
Some(prev) if prev.checkpoint.mmr_size < cp.checkpoint.mmr_size => {
json!(hex::encode(consistency(
log,
prev.checkpoint.mmr_size,
cp.checkpoint.mmr_size
)?))
}
_ => Value::Null,
};
history.push(json!({
"checkpoint": hex::encode(&cp.statement),
"consistency_from_previous": consistency,
}));
}
head.insert("derivation".into(), json!(DERIVATION_HISTORY_CARD));
head.insert("history".into(), Value::Array(history));
jcs(head)?
}
(Some(Derivation::Token(t)), _) if t == DERIVATION_HISTORY_CARD_2 => {
let window = match options.history_window {
0 => DEFAULT_HISTORY_WINDOW,
w => w,
};
if !(MIN_HISTORY_WINDOW..=MAX_HISTORY_WINDOW).contains(&window) {
return Err(AnswerError::HistoryWindow(window));
}
let positions =
evidence_request::history_card::positions(selection.at as u64, window as u64);
head.insert("derivation".into(), json!(DERIVATION_HISTORY_CARD_2));
head.insert(
"history".into(),
Value::Array(sampled(log, chain, &positions)?),
);
head.insert("window".into(), json!(window));
jcs(head)?
}
(Some(Derivation::Token(t)), _) if t == DERIVATION_STANDARD_HISTORY => options
.standard_card
.ok_or(AnswerError::DerivationUnsupported)?
.to_vec(),
(Some(Derivation::Digest(id)), subject) if derived.is_none() => {
let registered = options
.derivations
.and_then(|d| d.get(id))
.filter(|r| r.declares(subject.form()))
.ok_or(AnswerError::DerivationUnsupported)?;
if registered.authorizes(options.requester) == Some(false) {
return Err(AnswerError::NotAuthorized);
}
let set = record_set(log, records, selection, at, options, &mut material)?;
head.insert("derivation".into(), json!(registered.id()));
head.insert("records".into(), projection(records, &set, registered)?);
jcs(head)?
}
(Some(_), _) => {
let (token, (member, value)) = derived.ok_or(AnswerError::DerivationUnsupported)?;
head.insert("derivation".into(), json!(token));
head.insert(member, value);
if options.prove_beyond_profile {
material.push((KIND_CHECKPOINT.into(), at.statement.clone()));
}
jcs(head)?
}
(None, Subject::Checkpoints) => {
let list = chain
.iter()
.map(|cp| json!(hex::encode(&cp.statement)))
.collect();
head.insert("checkpoints".into(), Value::Array(list));
jcs(head)?
}
(None, Subject::CheckpointRange(a, b)) => {
let positions: Vec<u64> = (*a..=*b).collect();
let history = sampled(log, chain, &positions)?;
let end = usize::try_from(*b)
.ok()
.and_then(|i| chain.get(i))
.ok_or(AnswerError::AnchorNotFound)?;
let to_anchor = if end.checkpoint.mmr_size < at.checkpoint.mmr_size {
json!(hex::encode(consistency(
log,
end.checkpoint.mmr_size,
at.checkpoint.mmr_size
)?))
} else {
Value::Null
};
material.push((KIND_CHECKPOINT.into(), at.statement.clone()));
jcs(Map::from_iter([
("history".to_owned(), Value::Array(history)),
("consistency_to_anchor".to_owned(), to_anchor),
]))?
}
(None, Subject::Record(d)) => {
let [leaf] = selection.records[..] else {
return Err(AnswerError::RecordNotFound);
};
let record = record_at(records, leaf)?;
if record.digest != *d {
return Err(AnswerError::RecordNotFound);
}
let path = log.inclusion_path(record.leaf_index, at.checkpoint.mmr_size)?;
material.push((KIND_CHECKPOINT.into(), at.statement.clone()));
material.push((KIND_INCLUSION.into(), inclusion(record.leaf_index, &path)?));
if at.checkpoint.prev_size > 0 {
material.push((
KIND_CONSISTENCY.into(),
consistency(log, at.checkpoint.prev_size, at.checkpoint.mmr_size)?,
));
}
record.body
}
(None, _) => {
let set = record_set(log, records, selection, at, options, &mut material)?;
head.insert("records".into(), records_value(&set));
jcs(head)?
}
};
let freshness = match &request.coverage {
Coverage::MinFreshness(Freshness::Size(_)) => {
Some(AnchorFreshness::Size(at.checkpoint.mmr_size))
}
Coverage::MinFreshness(Freshness::Time(_)) => Some(AnchorFreshness::Time(profile_time(
&at.checkpoint.timestamp,
))),
Coverage::ExpectedPin(_) => None,
};
let profile = match crate::respond::requested_profile(request_bytes) {
Some(profile) => profile,
None => evidence_request::envelope::PROFILE.to_string(),
};
if !crate::respond::ANSWERED_PROFILES.contains(&profile.as_str()) {
return Err(AnswerError::Sign(
evidence_request::envelope::SignError::Profile,
));
}
Ok(sign_with_profile(
&profile,
request_bytes,
EnvelopeParts {
subject: request.subject.clone(),
derivation: request.derivation.clone(),
anchor: Anchor {
digest: anchor.digest().to_string(),
freshness,
},
artifact,
verification: material,
issued_at: issued_at.to_string(),
},
signer,
)?)
}
fn profile_time(timestamp: &str) -> String {
match timestamp.split_once('.') {
Some((seconds, _)) => format!("{seconds}Z"),
None => timestamp.to_string(),
}
}
fn jcs(object: Map<String, Value>) -> Result<Vec<u8>, AnswerError> {
evidence_request::jcs::to_string(&Value::Object(object))
.map(String::into_bytes)
.map_err(|e| AnswerError::Artifact(e.to_string()))
}
fn sampled(
log: &dyn CheckpointedLog,
chain: &[StatedCheckpoint],
positions: &[u64],
) -> Result<Vec<Value>, AnswerError> {
let mut entries = Vec::with_capacity(positions.len());
let mut before: Option<&StatedCheckpoint> = None;
for &p in positions {
let cp = usize::try_from(p)
.ok()
.and_then(|i| chain.get(i))
.ok_or(AnswerError::AnchorNotFound)?;
let proof = match before {
None => Value::Null,
Some(prev) if prev.checkpoint.mmr_size < cp.checkpoint.mmr_size => json!(hex::encode(
consistency(log, prev.checkpoint.mmr_size, cp.checkpoint.mmr_size)?
)),
Some(_) => {
return Err(AnswerError::Substrate(SubstrateError::Mmr(format!(
"checkpoint {p} does not grow the log past the checkpoint listed before it"
))))
}
};
entries.push(json!({
"position": p,
"checkpoint": hex::encode(&cp.statement),
"receipts": [],
"consistency_from_previous": proof,
}));
before = Some(cp);
}
Ok(entries)
}
fn consistency(log: &dyn CheckpointedLog, from: u64, to: u64) -> Result<Vec<u8>, AnswerError> {
let (old_peaks, paths, new_peaks) = log.consistency_parts(from, to)?;
encode_consistency_proof(from, to, &old_peaks, &paths, &new_peaks).ok_or_else(|| {
AnswerError::Substrate(SubstrateError::Mmr(format!(
"the log's consistency proof from {from} to {to} does not reach its own peaks"
)))
})
}
fn inclusion(leaf_index: u64, path: &[[u8; 32]]) -> Result<Vec<u8>, AnswerError> {
encode_inclusion_proof(leaf_index, path).ok_or_else(|| {
AnswerError::Substrate(SubstrateError::Mmr(format!(
"leaf {leaf_index} has no inclusion proof the profile can carry"
)))
})
}
fn record_set(
log: &dyn CheckpointedLog,
records: &dyn RecordSource,
selection: &Selection,
at: &StatedCheckpoint,
options: Options<'_>,
material: &mut Vec<(String, Vec<u8>)>,
) -> Result<Vec<Record>, AnswerError> {
if selection.records.is_empty() {
return Err(AnswerError::NoRecords);
}
let set = selection
.records
.iter()
.map(|&i| record_at(records, i))
.collect::<Result<Vec<_>, _>>()?;
if options.prove_beyond_profile {
material.push((KIND_CHECKPOINT.into(), at.statement.clone()));
for r in &set {
let path = log.inclusion_path(r.leaf_index, at.checkpoint.mmr_size)?;
material.push((KIND_INCLUSION.into(), inclusion(r.leaf_index, &path)?));
}
}
Ok(set)
}
fn record_at(records: &dyn RecordSource, leaf_index: u64) -> Result<Record, AnswerError> {
let record = records
.record_at(leaf_index)
.filter(|r| r.leaf_index == leaf_index)
.ok_or(AnswerError::RecordNotFound)?;
if records.entry_of(&record.body).as_deref() != Some(record.digest.as_str()) {
return Err(AnswerError::RecordDigest);
}
Ok(record)
}
fn projection(
source: &dyn RecordSource,
set: &[Record],
registered: &Registered,
) -> Result<Value, AnswerError> {
let mut out = Vec::with_capacity(set.len());
for record in set {
let header = source.header_of(record).ok_or(AnswerError::RecordHeader)?;
let mut entry = Map::new();
entry.insert("digest".into(), json!(record.digest));
entry.insert("leaf_index".into(), json!(record.leaf_index));
for name in registered.fields() {
if let Some(value) = header.get(name) {
entry.insert(name.clone(), value.clone());
}
}
out.push(Value::Object(entry));
}
Ok(Value::Array(out))
}
fn records_value(records: &[Record]) -> Value {
Value::Array(
records
.iter()
.map(|r| json!({"body": hex::encode(&r.body), "digest": r.digest, "leaf_index": r.leaf_index}))
.collect(),
)
}
#[rustfmt::skip]
pub(crate) fn citing_half(subject: &Subject) -> Option<&str> {
match subject { Subject::Exchange(half) => Some(half), _ => None } }
fn citing_anchor(
records: &dyn RecordSource,
checkpoints: &[StatedCheckpoint],
half: &str,
) -> Result<Option<usize>, SubstrateError> {
let Some(latest) = checkpoints.last() else {
return Ok(None);
};
let latest = latest.checkpoint.leaf_count()?;
let Some(last_citing) = records
.citing(half)
.into_iter()
.filter(|&i| i < latest)
.max()
else {
return Ok(None);
};
for (i, cp) in checkpoints.iter().enumerate() {
if cp.checkpoint.leaf_count()? > last_citing {
return Ok(Some(i));
}
}
Ok(None)
}
fn range_leaves(a: u64, b: u64, covered: u64, limit: u64) -> Result<Vec<u64>, AnswerError> {
if b >= covered || a > b {
return Err(AnswerError::RecordNotFound);
}
if b - a >= limit {
return Err(AnswerError::OverLimit);
}
Ok((a..=b).collect())
}
fn leaves_under(leaves: Vec<u64>, covered: u64, limit: u64) -> Result<Vec<u64>, AnswerError> {
let mut found: Vec<u64> = leaves.into_iter().filter(|&i| i < covered).collect();
found.sort_unstable();
found.dedup();
if found.is_empty() {
return Err(AnswerError::NoRecords);
}
if found.len() as u64 > limit {
return Err(AnswerError::OverLimit);
}
Ok(found)
}