Advanced Data Structures

Starting from 0.16.0, Scalus includes a library of authenticated collections: data structures where you store data off-chain and keep only a small hash commitment on-chain. Cryptographic proofs verify that operations (membership, insert, delete) are valid — without the on-chain validator ever seeing the full dataset.

This matters on Cardano because of eUTxO constraints: limited transaction size, expensive on-chain storage, and tight script execution budgets. Authenticated collections let you work with arbitrarily large datasets while keeping transactions small and cheap.

When to Use Each Collection

Collection	Verification Cost	Proof Size	Grows with N?	Use Case
Merkle Tree	log₂(N)+1 blake2b calls	33 × ceil(log₂(N)) bytes	Yes (logarithmic)	Static set known at deploy time. Airdrop allowlists, governance voter registries.
Incremental Merkle Tree	Verify: log₂(N)+1 blake2b. Append: 2×log₂(N)+2 blake2b	32–33 × ceil(log₂(N)) bytes	Yes (logarithmic)	Append-only sets. Oracle price feeds, event logs, audit trails.
Frontier Merkle Tree	Same as Incremental MT	Same as Incremental MT	Yes (logarithmic)	Same as Incremental MT but with O(depth) off-chain memory instead of O(N).
Merkle Patricia Forestry	~5–15 blake2b calls per step	~200–800 bytes (Data-encoded)	No (max 2²⁵⁶ entries)	General key-value with insert/delete/update + non-membership proofs. Aiken-compatible. DEX order books, token registries.
Fused MPF	~8–12% less CPU than MPF	~100–500 bytes (flat ByteString)	No (max 2²⁵⁶ entries)	Same as MPF but cheaper on-chain. Not Aiken-compatible.
Bilinear Accumulators	2 pairings + MSM (~35× more CPU)	~48–96 bytes	No (constant, 1 group element)	Large sets where constant proof size matters. Many proofs per tx, tight size limits.

Decision Flowchart

Static set? → Merkle Tree (cheapest possible)
Append-only? → Incremental Merkle Tree / Frontier Merkle Tree
Need insert + delete? → Fused MPF (cheapest) or MPF (Aiken-compatible)
Proof size critical? → Bilinear Accumulator (smallest constant proof, ~35× CPU)
Need non-membership proofs? → MPF, Fused MPF, or Bilinear Accumulator


               What collection do you need?
                            │
                     ┌──────▼──────┐
                     │ Static set? │── Yes ──→  Merkle Tree (MT) @ cheapest
                     └──────┬──────┘
                            │ No
                     ┌──────▼───────┐
                     │ Append-only? │── Yes ──→  Incremental MT / Frontier MT
                     └──────┬───────┘
                            │ No
                            │
               ┌────────────▼────────────┐
               │ Proof size critical?    │── Yes ──→  Bilinear Accumulator
               │ (many proofs per tx,    │   (smallest constant proof size, ~35x CPU)
               │  tight tx size limits)  │
               └────────────┬────────────┘
                            │ No
               ┌────────────▼────────────┐
               │ Need Aiken              │── Yes ──→  Merkle Patricia Forestry (MPF)
               │ compatibility?          │
               └────────────┬────────────┘
                            │ No
                            ▼
                  Fused MPF (10% cheaper than MPF)

Supported Operations

Operation	Merkle Tree	Incremental MT / Frontier MT	Merkle Patricia Forestry	Fused MPF	Bilinear Accumulator
Verify membership	yes	yes	yes	yes	yes
Verify non-membership	—	—	yes	yes	yes
Insert (with proof)	—	append only	yes	yes	—
Delete (with proof)	—	—	yes	yes	—
Update (with proof)	—	—	yes	yes	—

Frontier Merkle Tree uses the same on-chain verifier as Incremental Merkle Tree — it is an off-chain memory optimization.

Benchmarks

For detailed performance benchmarks — including radix comparisons, fusing optimizations, and full Cardano transaction fee breakdowns — see Benchmarking Authenticated Collections on Cardano .

Examples

Each data structure page includes on-chain and off-chain code snippets from real validators in the scalus-examples module:

MembershipTokenValidator — Merkle Tree for allowlist-gated token minting
SetBenchImtValidator — Incremental Merkle Tree for oracle-managed sets
SetBenchMpf16oValidator — Standard MPF (Aiken-compatible)
SetBenchMpf16bValidator — Fused MPF (8–12% cheaper)
SetBenchAccValidator — Bilinear Accumulator with Ethereum KZG ceremony
AnonymousDataValidator — Merkle Tree + AssocMap for privacy-preserving storage

Design Patterns — Optimization and validation patterns for Cardano contracts
Smart Contract Optimization — Compiler-level optimizations
Testing — Test your authenticated collection implementations