datumesh_core/
verify.rs

1//! The verification procedure (10.1).
2
3use std::borrow::Cow;
4use std::collections::BTreeMap;
5
6use crate::crypto;
7use crate::descriptor::Descriptor;
8use crate::error::{err, member, Error, ErrorCode, Result};
9use crate::json::{self, Value};
10use crate::keys::Keys;
11use crate::lexical;
12use crate::model::{Cell, Scalar};
13use crate::receipt::Receipt;
14
15/// How far a receipt verified.
16#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
17pub enum Level {
18    /// Steps 1-6 passed: the holder of `computed_by` stated this value.
19    Signed,
20    /// Steps 7.1-7.6 passed as well.
21    Recomputed,
22}
23
24impl Level {
25    /// `"signed"` or `"recomputed"`.
26    pub const fn as_str(self) -> &'static str {
27        match self {
28            Level::Signed => "signed",
29            Level::Recomputed => "recomputed",
30        }
31    }
32}
33
34/// What step 7 of SPEC 10.1 obtains: the descriptor, the input receipts and the evaluated
35/// value. This crate evaluates no functions and fetches nothing; the caller supplies a
36/// resolver, and [`verify`] asks it only for what step 7 reaches for the receipt at hand:
37///
38/// * [`descriptor`](Resolver::descriptor) once, for `cell.fn_hash` (7.1);
39/// * [`receipt`](Resolver::receipt) once per hash in `inputs`, in order, stopping at the first
40///   input that fails (7.5);
41/// * [`evaluate`](Resolver::evaluate) once, only after 7.1-7.5 pass (7.6).
42///
43/// Nothing is asked when steps 1-6 fail, and nothing about receipts below the inputs. The
44/// descriptor and receipts are JSON text, so that 7.1 hashes the descriptor before checking
45/// it and 7.5 reports an unparseable input as `E_INPUT_INVALID`, as the specification orders.
46pub trait Resolver {
47    /// The descriptor JSON text offered for `fn_hash`, or `None` if unavailable
48    /// (`E_FN_UNAVAILABLE`).
49    fn descriptor(&self, fn_hash: &str) -> Option<Cow<'_, [u8]>>;
50
51    /// The receipt JSON text offered for receipt hash `hash`, or `None` if unavailable
52    /// (`E_INPUT_UNAVAILABLE`).
53    fn receipt(&self, hash: &str) -> Option<Cow<'_, [u8]>>;
54
55    /// The value of evaluating `cell` as of `asof` (for `stored`: the value looked up as of it,
56    /// SPEC 10.1 step 7.6), or `None` if this resolver cannot evaluate it: no runtime for the
57    /// language, a budget exceeded, inputs the evaluator cannot obtain
58    /// (`E_EVAL_UNAVAILABLE`, see [`VerifyResult`]). `asof` is the receipt's `asof`.
59    fn evaluate(&self, cell: &Cell, asof: &str) -> Option<Scalar>;
60}
61
62/// A [`Resolver`] backed by maps: descriptors by function hash, receipts by receipt hash, and
63/// evaluated values by cell id. It is what the vectors' `recompute` object describes
64/// (SPEC 11): the descriptor goes under the receipt's `cell.fn_hash`, the inputs under their
65/// hashes, and `value` under the receipt's own [`Cell::id`].
66///
67/// A map holds one value per cell: [`evaluate`](Resolver::evaluate) ignores `asof`.
68#[derive(Clone, Debug, Default, PartialEq, Eq)]
69pub struct MapResolver {
70    descriptors: BTreeMap<String, Vec<u8>>,
71    receipts: BTreeMap<String, Vec<u8>>,
72    values: BTreeMap<String, Scalar>,
73}
74
75impl MapResolver {
76    /// An empty resolver: every descriptor and receipt unavailable, nothing evaluable.
77    pub fn new() -> MapResolver {
78        MapResolver::default()
79    }
80
81    /// Offers descriptor JSON text for `fn_hash`.
82    pub fn insert_descriptor(&mut self, fn_hash: impl Into<String>, json: impl Into<Vec<u8>>) {
83        self.descriptors.insert(fn_hash.into(), json.into());
84    }
85
86    /// Offers receipt JSON text for receipt hash `hash`.
87    pub fn insert_receipt(&mut self, hash: impl Into<String>, json: impl Into<Vec<u8>>) {
88        self.receipts.insert(hash.into(), json.into());
89    }
90
91    /// Sets the value evaluating the cell with id `cell_id` gives.
92    pub fn insert_value(&mut self, cell_id: impl Into<String>, value: Scalar) {
93        self.values.insert(cell_id.into(), value);
94    }
95}
96
97impl Resolver for MapResolver {
98    fn descriptor(&self, fn_hash: &str) -> Option<Cow<'_, [u8]>> {
99        self.descriptors.get(fn_hash).map(|b| Cow::Borrowed(b.as_slice()))
100    }
101
102    fn receipt(&self, hash: &str) -> Option<Cow<'_, [u8]>> {
103        self.receipts.get(hash).map(|b| Cow::Borrowed(b.as_slice()))
104    }
105
106    fn evaluate(&self, cell: &Cell, _asof: &str) -> Option<Scalar> {
107        self.values.get(&cell.id()).cloned()
108    }
109}
110
111/// The outcome of [`verify`].
112///
113/// `code` is `None` when `ok`, with one exception: [`ErrorCode::EvalUnavailable`]. When a
114/// resolver is given and 7.1-7.5 pass but [`Resolver::evaluate`] returns `None`, the receipt
115/// is still signature-valid, so the result is `ok`, level [`Level::Signed`], with
116/// `code: Some(EvalUnavailable)`, `path` `$.value` and a `detail`: recomputation did not
117/// happen, and the code says why. Step 7.7 still runs afterwards; a failure there replaces it
118/// as a normal failure (`ok` false, its own code).
119#[derive(Clone, Debug, PartialEq, Eq)]
120pub struct VerifyResult {
121    /// Whether the receipt verified.
122    pub ok: bool,
123    /// The failure's code; `None` when `ok`, except [`ErrorCode::EvalUnavailable`].
124    pub code: Option<ErrorCode>,
125    /// The level reached; `None` unless `ok`.
126    pub level: Option<Level>,
127    /// The receipt hash, once the receipt was canonical enough to compute it.
128    pub hash: Option<String>,
129    /// The receipt's `computed_by` (`<host>#<key id>`), once steps 1-4 passed.
130    pub computed_by: Option<String>,
131    /// Whether step 7.7 ran and passed.
132    pub blob_checked: bool,
133    /// A human explanation of the failure (or of `EvalUnavailable`); empty otherwise.
134    pub detail: String,
135    /// Where the failure (or `EvalUnavailable`) was found; empty otherwise.
136    pub path: String,
137}
138
139impl VerifyResult {
140    /// `code` as an [`Error`], with `path` and `detail`: the failure, or `EvalUnavailable`.
141    pub fn error(&self) -> Option<Error> {
142        self.code.map(|c| Error::new(c, self.path.clone(), self.detail.clone()))
143    }
144}
145
146/// Verifies a receipt (10.1). Never touches the network and never panics.
147///
148/// * `receipt`: the receipt's JSON text.
149/// * `keys`: the keys resolved for signer hosts (absent hosts are `E_KEY_UNAVAILABLE`).
150/// * `resolver`: when given, steps 7.1-7.6 run, asking it only for what they reach (see
151///   [`Resolver`]); success is level `recomputed`, and an evaluation the resolver cannot do
152///   is `E_EVAL_UNAVAILABLE` at level `signed` (see [`VerifyResult`]).
153/// * `blob`: content for step 7.7 (the value must be a blob); success sets `blob_checked`.
154pub fn verify(receipt: &[u8], keys: &Keys, resolver: Option<&dyn Resolver>, blob: Option<&[u8]>) -> VerifyResult {
155    let mut out = VerifyResult {
156        ok: false,
157        code: None,
158        level: None,
159        hash: None,
160        computed_by: None,
161        blob_checked: false,
162        detail: String::new(),
163        path: String::new(),
164    };
165    let r = match signature_valid(receipt, keys) {
166        Ok(r) => r,
167        Err((e, r)) => {
168            if let Some(r) = r {
169                out.hash = Some(r.hash().to_string());
170                out.computed_by = Some(r.computed_by().to_string());
171            }
172            return fail(out, e);
173        }
174    };
175    out.hash = Some(r.hash().to_string());
176    out.computed_by = Some(r.computed_by().to_string());
177    let mut level = Level::Signed;
178    if let Some(res) = resolver {
179        match recompute_steps(&r, keys, res) {
180            Ok(Recomputed::Yes) => level = Level::Recomputed,
181            Ok(Recomputed::EvalUnavailable(e)) => out = fail(out, e),
182            Err(e) => return fail(out, e),
183        }
184    }
185    if let Some(content) = blob {
186        if let Err(e) = check_blob(&r, content) {
187            return fail(out, e);
188        }
189        out.blob_checked = true;
190    }
191    out.ok = true;
192    out.level = Some(level);
193    out
194}
195
196fn fail(mut out: VerifyResult, e: Error) -> VerifyResult {
197    out.code = Some(e.code());
198    out.detail = e.detail().to_string();
199    out.path = e.path().to_string();
200    out
201}
202
203/// A failure in steps 1-6, with the receipt when steps 1-4 passed.
204type StepError = (Error, Option<Box<Receipt>>);
205
206/// Steps 1-6 over JSON text.
207fn signature_valid(bytes: &[u8], keys: &Keys) -> core::result::Result<Receipt, StepError> {
208    let v = json::parse(bytes).map_err(|e| (e, None))?;
209    signature_valid_value(&v, keys)
210}
211
212/// Steps 2-6 over a parsed value (also used for receipts inside envelopes).
213pub(crate) fn signature_valid_value(v: &Value, keys: &Keys) -> core::result::Result<Receipt, StepError> {
214    let r = Receipt::from_value(v).map_err(|e| (e, None))?;
215    match key_and_signature(&r, keys) {
216        Ok(()) => Ok(r),
217        Err(e) => Err((e, Some(Box::new(r)))),
218    }
219}
220
221fn key_and_signature(r: &Receipt, keys: &Keys) -> Result<()> {
222    let doc = keys.get(r.signer_host()).map_err(|e| Error::new(e.code(), "$.computed_by", e.detail()))?;
223    let Some(key) = doc.key(r.key_id()) else {
224        return err(
225            ErrorCode::KeyUnknown,
226            "$.computed_by",
227            format!("{} publishes no key {}", r.signer_host(), r.key_id()),
228        );
229    };
230    if !key.usable_at(r.issued()) {
231        return err(ErrorCode::KeyNotValid, "$.issued", "issued is outside the key's validity window");
232    }
233    let Some(sig) = lexical::decode_hex_lower::<64>(r.sig()) else {
234        return err(ErrorCode::Signature, "$.sig", "signature is not 64 bytes");
235    };
236    if !crypto::verify_ed25519(&key.public, r.payload(), &sig) {
237        return err(ErrorCode::Signature, "$.sig", "Ed25519 verification failed");
238    }
239    Ok(())
240}
241
242/// How steps 7.1-7.6 ended when none failed.
243enum Recomputed {
244    /// The evaluated value equals the receipt's.
245    Yes,
246    /// The resolver could not evaluate the function (`E_EVAL_UNAVAILABLE`).
247    EvalUnavailable(Error),
248}
249
250fn recompute_steps(r: &Receipt, keys: &Keys, res: &dyn Resolver) -> Result<Recomputed> {
251    // 7.1
252    let Some(desc_bytes) = res.descriptor(&r.cell().fn_hash) else {
253        return err(ErrorCode::FnUnavailable, "$.cell.fn_hash", "no descriptor for fn_hash");
254    };
255    let desc_v = json::parse(&desc_bytes)?;
256    if crypto::sha256_hex(&desc_v.to_jcs()) != r.cell().fn_hash {
257        return err(ErrorCode::FnHashMismatch, "$.cell.fn_hash", "the descriptor does not hash to fn_hash");
258    }
259    let d = Descriptor::from_value(&desc_v)?;
260    let decl = &d.signature.args;
261    // 7.2: unknown, then missing, then types, each in JCS order of names.
262    for k in r.cell().args.keys() {
263        if !decl.contains_key(k) {
264            return err(ErrorCode::ArgUnknown, &member("$.cell.args", k), "the function declares no such argument");
265        }
266    }
267    for k in decl.keys() {
268        if !r.cell().args.contains_key(k) {
269            return err(ErrorCode::ArgMissing, &member("$.cell.args", k), "a declared argument is not bound");
270        }
271    }
272    for (k, a) in &r.cell().args {
273        let declared = decl.get(k).map(|x| x.ty);
274        if a.scalar().map(Scalar::ty) != declared {
275            return err(ErrorCode::ArgType, &member("$.cell.args", k), "type differs from the declaration");
276        }
277    }
278    // 7.3
279    let declared_valid: Vec<&String> = decl.iter().filter(|(_, x)| x.valid).map(|(k, _)| k).collect();
280    let given_valid: Vec<&String> = r.valid().keys().collect();
281    if declared_valid != given_valid {
282        return err(
283            ErrorCode::ValidMismatch,
284            "$.valid",
285            "valid does not hold exactly the declared valid-time arguments",
286        );
287    }
288    // 7.4
289    if r.ty() != d.signature.returns.ty {
290        return err(ErrorCode::ReturnType, "$.type", "type differs from the declared return type");
291    }
292    // 7.5
293    let mut latest_tx: Option<String> = None;
294    for h in r.inputs() {
295        let p = member("$.inputs", h);
296        let Some(bytes) = res.receipt(h) else {
297            return err(ErrorCode::InputUnavailable, &p, "no receipt offered for this input");
298        };
299        let input = match signature_valid(&bytes, keys) {
300            Ok(i) => i,
301            Err((e, _)) => return err(ErrorCode::InputInvalid, &p, format!("{}: {}", e.code(), e.detail())),
302        };
303        if input.hash() != h {
304            return err(ErrorCode::InputUnavailable, &p, "the receipt offered has another hash");
305        }
306        if !d.inputs.contains(&input.cell().function_name()) {
307            return err(
308                ErrorCode::InputUndeclared,
309                &p,
310                format!("{} is not a declared input", input.cell().function_name()),
311            );
312        }
313        if input.asof() != r.asof() {
314            return err(ErrorCode::TimeOrder, &p, "an input has another asof");
315        }
316        if latest_tx.as_ref().is_none_or(|t| input.tx() > t.as_str()) {
317            latest_tx = Some(input.tx().to_string());
318        }
319    }
320    if let Some(t) = latest_tx {
321        if r.tx() != t {
322            return err(ErrorCode::TimeOrder, "$.tx", "tx must equal the latest input tx");
323        }
324    }
325    // 7.6
326    let Some(value) = res.evaluate(r.cell(), r.asof()) else {
327        return Ok(Recomputed::EvalUnavailable(Error::new(
328            ErrorCode::EvalUnavailable,
329            "$.value",
330            "the resolver could not evaluate this function",
331        )));
332    };
333    if &value != r.value() {
334        return err(ErrorCode::ValueMismatch, "$.value", "recomputation gives a different type or value");
335    }
336    Ok(Recomputed::Yes)
337}
338
339fn check_blob(r: &Receipt, content: &[u8]) -> Result<()> {
340    let Scalar::Blob(b) = &r.value() else {
341        return err(ErrorCode::Schema, "$.value", "content supplied for a value that is not a blob");
342    };
343    let Ok((hash, len, _)) = lexical::parse_blob(b) else {
344        return err(ErrorCode::CanonBlob, "$.value", "not a blob");
345    };
346    if content.len() as u64 != len {
347        return err(
348            ErrorCode::BlobMismatch,
349            "$.value",
350            format!("content has {} bytes, the blob states {len}", content.len()),
351        );
352    }
353    if crypto::sha256(content) != hash {
354        return err(ErrorCode::BlobMismatch, "$.value", "content does not hash to the blob's sha256");
355    }
356    Ok(())
357}
datumesh_core/verify.rs

datumesh_core/
verify.rs
