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

datumesh_core/
verify.rs
