Bound the type-graph traversal and fail with a coded error

[ichbindas]

hashTypedData places no bound on the size or depth of the type graph it walks. A payload built from a linear chain of struct types — L0.next → L1.next → …, each instantiated once — costs time quadratic in the chain length, because encodeType(T) emits T plus all of its transitive dependencies, so n distinct types each build a string of length O(n).

Measured against the current sources:

depth   500    41,089 bytes  ->  ok in 227ms
depth  1000    82,089 bytes  ->  ok in 707ms
depth  2000   166,089 bytes  ->  ok in 3,103ms
depth  4000   334,089 bytes  ->  RangeError: Maximum call stack size exceeded

There are two separate problems here.

Quadratic cost. Doubling the depth roughly quadruples the time. 3.1 seconds on a 166 KB payload.

Uncatchable failure. Past roughly depth 3000, collectStructDeps exhausts the call stack and throws a plain RangeError, not a TypedDataError. The library's error convention is that malformed input produces a coded TypedDataError, so a consumer following that convention does not catch this. In a signer, an uncaught throw on the approval path is what blanks the approval screen.

Memoizing typeHash does not fix it

This was tried in a patched copy before proposing anything else:

depth |  plain ms | memoized ms | same digest
 1600 |      1902 |        1822 |        true

No improvement. Every type in the chain is distinct, so the cache never hits. The quadratic is inherent to the definition of encodeType, not a missing cache. A fix has to bound the input rather than memoize the work.

The exposed party is the verifier, not the signer

The Wallet is not affected. src/background/rpc.js calls checkPolicyLimits(typedInput) at line 1029 before hashTypedDataHex at line 1031, and the policy check rejects every payload above in under a millisecond.

Verifiers are affected. verifyTypedDataSignature hashes before it compares anything:

depth  500  ->    245ms before returning E_SIG_INVALID
depth 1000  ->    772ms before returning E_SIG_INVALID
depth 2000  ->   3172ms before returning E_SIG_INVALID

Three seconds spent on a payload that was always going to be rejected, without reaching the cheap chainId comparison. A dApp backend accepting signatures from untrusted clients can be stalled by small, well-formed requests.

@dusk/connect is the package those verifiers actually install. It exports hashTypedData, hashTypedDataHex, hashTypedDataDebug, validateTypedDataParams and verifyTypedDataSignature, and no limit function at all — src/entrypoints.test.ts:32 asserts checkPolicyLimits is absent. Its docs/typed-data-v1.md directs integrators to @dusk/typed-data/policy, which for a dApp that installed only @dusk/connect means importing from a transitive dependency.

That entry-point split came out of an earlier review comment and it was right for its stated reason: a verifier that applies signer limits rejects signatures over digests everyone agrees on. The consequence was that the hash path lost any reachable bound on the surface most likely to face hostile input.

Proposal

Two things are currently conflated under "limits" and should be separated.

Resource policy — how large a payload a signer is willing to accept — is signer-side, optional, and correctly lives at @dusk/typed-data/policy. No change proposed.

Structural safety of the encoder — that hashing terminates in bounded time and fails cleanly — is not policy. It is a property the encoder owes every caller, verifiers included, and it cannot be delegated to an optional import.

Concretely:

1. The encoder bounds its own traversal and rejects with a coded TypedDataError — E_COMPLEXITY, or whichever code fits — rather than a RangeError.
2. The specification fixes that bound as a constant. It is a ceiling that every implementation MUST refuse above, distinct from the §11 floor that every implementation MUST accept below. Both are normative.
3. The ceiling belongs in the specification rather than in each implementation. If one implementation bounds at depth 1024 and another at 4096, a payload at depth 2000 is accepted by one and refused by the other, which is the kind of divergence the vector corpus exists to prevent.
4. Because the ceiling sits far above the floor, no conforming payload is affected and no digest changes.

A fixed ceiling also wants vectors: one payload just under it that every implementation must accept, one just over it that every implementation must refuse with the same code.

[HDauven]

The follow-up for #8 uses reference-implementation structural guards above §11's existing floor, rather than introducing a universal protocol ceiling: depth 64, 128 structs / 8,192 fields per dependency closure, and 1,048,576 type-encoding characters, all inclusive. It adds TypedDataError / E_COMPLEXITY through hash, debug, verification and policy graph traversal, plus per-call type-hash reuse and streamed field/array encoding.

This deliberately changes some above-floor acceptance, while preserving accepted encodings and all 41 fixtures. Initial shape validation remains only a shape check. Local checks cover each boundary, shared-dependency depth, early graph refusal, wide arrays and verifier propagation; 160 tests and 16 existing real-BLS/SQLite example groups pass. These guards are not wall-clock or peak-memory guarantees.

I am leaving the proposed universal MUST ceiling / just-below-ceiling acceptance rule as a separate maintainer/specification decision, so this is not a claim that every part of the issue is settled. The original RangeError was catchable but uncoded; the retained Wallet integration catches it before approval, rather than demonstrating an approval bypass. Thanks for identifying the shared traversal boundary.

Indexed traversal and refusal-code follow-up

The additional #8 follow-up closes the in-process field-list/policy iterator gap across validation, dependency collection, type text and value encoding/measurement, including caller-replaceable .map(). It also requires E_COMPLEXITY for every implementation's above-floor encoder structural refusal: the thresholds stay local; optional signer-policy rejection remains distinct (E_POLICY_LIMIT). This does not add a universal validity ceiling.

Total value-work budgeting remains open here: shared objects and arrays are re-encoded per path, and a structHash-only counter misses shared arrays. A follow-up budget must preserve every otherwise-valid input within the interoperability floor. The spec now states this limitation explicitly. JSON text cannot express aliases, but in-process inputs and structured-clone transports can preserve them; this is not a claim that every RPC boundary is protected by JSON parsing. See the work-budget proposal. No new work counter was added.

Latest local checks for this follow-up: 183 library tests +16 real-BLS/SQLite application groups; 14 installed-package regression checks; six isolated traversal reversions rejected; all 41 fixture bytes preserved. Genuine signatures for different indexed values now fail verification, and a required indexed field cannot be omitted. These constructed-object checks are not a demonstrated wallet-approval/JSON-RPC exploit, general hostile-object safety guarantee, independent encoding review, or release. Thanks to @ichbindas for the additional reports.

Per-call typed-value visit budget follow-up

Draft #9, head a4756af009c8905e08dc3f5ff64681231f0096e5, follows merged #8 with an inclusive 262,144 typed-value visits per call guard. It counts both roots, every atomic value, array container and struct (including empty structs), charging shared references on every path rather than only counting struct hashes. Hash/debug/verification and the optional policy value walks propagate E_COMPLEXITY on excess work; ordinary signer-floor refusals remain E_POLICY_LIMIT. Hashing still does not call policy or serialize the input.

The threshold preserves otherwise-valid complete JSON inputs within §11's floor: every visited occurrence has a distinct serialized token/delimiter byte, with the single implicit contract visit charged to the unvisited top-level opening delimiter. This includes alias-preserving copies with identical expanded JSON values. Lossy/custom in-process serialization cannot establish that floor guarantee.

This bounds typed-value visits, not total CPU/byte work, wall-clock time, peak memory or arbitrary JavaScript. Large contents, type/property processing, policy serialization of unused metadata and transport limits remain separate. Accepted encodings and all 41 fixtures are unchanged. This is still a local reference refusal, not a universal validity ceiling. As agreed in the #8 discussion, implementation-local guards replace the original universal-ceiling proposal. Together with merged #8, #9 completes the agreed traversal-bounds scope and will close this issue when merged. Broader resource hardening is separate.

Fresh source build/coverage and 191 library tests pass. The unchanged application-approval example separately passes its 16 real-BLS/SQLite checks; no database dependency was added to hashing. Same-tree old-main controls give seven intended failures/143 passes; eight isolated counter mutations are rejected. Installed-package, public-type, prior field/array regressions and native BLS checks are described with their limitations in #9. No package publication or protocol freeze. Thanks to @ichbindas for the shared-work report.