Introducing TACEO:OMap

In our previous post Foundations of Private Shared State, we introduced Private Shared State (PSS) and the services necessary to power it. To make that vision practical, PSS now needs a confidential data structure; one that can look up, retrieve values, and update state without ever revealing what’s inside.

Any privacy‑preserving application, from a private ledger to a confidential registry, relies on such a structure. Think of it as the “kernel” of Private Shared State.

Today, we’re introducing TACEO:OMap the first implementation of our Verifiable Oblivious Map Service , a private‑state equivalent to Solidity’s mapping primitive, capable of storing secrets while guaranteeing that all access patterns are hidden and all operations are provable.

The Problem: Access Pattern Leakage

In a system where state is secret-shared and encrypted across many nodes, the simple act of reading or writing data becomes a privacy threat via the Access Pattern Attack.

The Architectural Weakness

If an MPC network or a central server sees a user repeatedly querying the same memory location or following a predictable data access path, it learns something about the data the user is interested in, even if the data itself is cryptographically protected.

The mere act of accessing a piece of data is the greatest privacy threat. This access pattern leakage breaks all standard encrypted databases.

This vulnerability makes it hard to build trustworthy, long-running confidential applications for the internet. Pseudonyms, financial records, or reputation scores must be stored in a way that allows them to be updated or referenced over time without revealing which specific record is being acted upon.

The question then becomes: How can a confidential data structure maintain perfect privacy, ensuring that every read or write operation looks identical to an outside observer?

The Solution: Verifiable Oblivious Map (OMap)

We need a private counterpart of Solidity’s mapping primitive $\texttt{mapping}(\texttt{\_KeyType} \Rightarrow \texttt{\_ValueType})$ that is confidential, oblivious, and verifiable

Towards this, the insight was to combine two complementary cryptographic tools to create a data structure that is both oblivious and provable. The TACEO Network implements this structure as the Verifiable Oblivious Map (OMap).

A private shared state requires a cryptographic primitive that simultaneously guarantees:

1. Confidentiality: Neither the key nor the value of the map entries is ever exposed to any single MPC node.
2. Obliviousness: All access patterns must be hidden; every read/write operation must look identical regardless of the key being accessed.
3. Determinism: Updates must be consistent and deterministic.
4. Verifiable Commitment: The entire data structure must be representable as a sparse commitment (like a Merkle root) posted on-chain.
5. Provable Operations: Reads and updates must be accompanied by a Zero-Knowledge Proof attesting to the correctness of the operation against the on-chain commitment.

The TACEO:OMap is the first data structure designed to implement a “private and provable hashmap” by combining a Sparse Merkle Tree (SMT) for verifiability and Oblivious RAM (ORAM) for obliviousness.

The Cryptography Behind It

At the core of this design, the TACEO:OMap combines state-of-the-art cryptography via three distinct steps: structure, secrecy, and obliviousness.

1. The Structure: Sparse Merkle Tree (SMT)

We designed the data structure as a sparse Merkle-tree. The tree is built such that the path is the key of the data structure, whereas the actual values are located in the leaves of the tree. Values not present in the map are represented as a default value (e.g., $0$ in the leaves) and don’t need to be explicitly stored.

This enables users to prove membership of a value with a normale Merkle-proof: They prove that they know a path from the actual value to the root of the tree, where the path in our case is the key of the hashmap. Furthermore, this data structure allows non-membership proofs by proving the leave value is a default value. The commitment which will be posted on-chain is, as usual, the root of the Merkle-tree. This structure enables us to complete several requirements from our wishlist:

• Sparse Commitment: The root of the tree serves as the single, on-chain truth.
• Provable Reads: Users can prove membership of a value with a normal Merkle-proof.
• Efficient Write Proofs: Updates are proven by showing that the old value has a path to the existing commitment and demonstrating that the new value produces the new commitment using the same path.

2. Secrecy: MPC and CoSNARKs

To guarantee the Confidentiality of the contents, the sparse Merkle tree holds secret-shares of the actual elements instead of the elements themselves.

• Secret-Shared State: The data structure is managed by an MPC network. No individual MPC party on its own is able to reconstruct the Merkle-tree, or any individual key/value pair.
• Secret-Shared Path: We need to lookup and update all elements based on secret-shared indices. Furthermore, we must keep the intermediate hash layers in secret-shared fashion in order to not implicitly leak the path (and thus the identifier) from the updated hash values. Only the final root value is opened to the public.
• Collaborative SNARK (CoSNARK): Since we keep all values as secret-shares, we must also compute the ZK-Proof in MPC to ensure we do not leak the involved values and identifiers during the proof generation itself.

3. Obliviousness: ORAMs and Cuckoo Tables

The index of the reads and writes is secret-shared, making the MPC access costly. We must perform lookups and updates while ensuring the access trace is independent of the actual index.

There are two general approaches to lookup values based on secret-shared indices:

1. Linear Scan: Simple, but scales badly for larger hashmaps, as it involves comparing the index to the whole datastructure.
2. Oblivious RAM (ORAM) primitives: These are MPC primitives that allow read and write operations to be performed obliviously and asymptotically more efficient than a linear scan.

We focus on the ORAM-based solution. Since ORAM constructions scale with the size of the stored elements, and we only want to store the non-default leaf values, we first need to translate each layer from a $\texttt{map}(id, v)$ to a vector $\texttt{vector}(v)$.

To achieve this efficient translation, we implement an MPC-ified Cuckoo table for each layer of the SMT.

The Cuckoo table consists of two ORAM primitives, two random hash functions, and a stash.

• The index we want to lookup is first hashed with both hash functions to get two indices, one for each ORAM.
• Each ORAM is accessed based on these indices.
• The use of two ORAMs minimizes the collision rate, keeping the stash size small, as the stash must still be accessed via a linear scan approach.

The key result of this structure is that the underlying memory access pattern is identical for every query, regardless of which key is being looked up, ensuring total Obliviousness.

For a full view of the construction, see the paper here.

Scaling and Performance

Our first prototype of this oblivious sparse Merkle-tree primitive is implemented over the BN254 curve, using Poseidon2 as the hash function of the Merkle-tree, 3-party replicated secret sharing as the MPC protocol, DuORAM for ORAMs, Noir to write zero-knowledge proofs, and our CoGroth16 to create the proofs in MPC.

First Benchmarks

These initial benchmarks for a hashmap with 100,000 entries in a co-located setting (AWS m7a.8xlarge instances) already demonstrate its feasibility for real-world applications. The implementation is using a dealer party for precomputing random DPFs and is so far purely singlethreaded.

Note: Adding a CoSNARK proof adds approximately 200 ms for a Merkle-tree depth of 40.

Performance Optimizations

The current implementation is single-threaded, leaving substantial room for optimization. Next steps:

• Multithreading: For the most costly ORAM accesses.
• Hardware Acceleration: DPF creation (a core part of DuORAM) involves parallel AES cipher evaluations, which can be significantly sped up using graphic cards.
• Next-Generation ORAMs: Replacing DuORAM with hierarchical approaches like GigaDORAM is projected to give a large performance boost in co-located networks.

Scaling Consideration: While performance scales with the number of elements and the bit-length of the identifier (tree depth), for most use cases, identifiers need to be limited to a practical bit-length for optimal performance.

TACEO:OMap as a Foundational Primitive

In computer science, the hashmap (or dictionary/associative array) is arguably the single most important data structure. It is the primitive that forms the basis of almost all stateful systems, including:

• Databases: How keys map to records.
• Ledgers: How identifiers map to balances.
• Operating System Kernels: How file names or process IDs map to memory locations.

TACEO:OMap makes that hashmap private and provable.  With TACEO:OMap, a robust and ready-to-use component, projects can manage balances, records, or credentials confidentially while retaining mathematical verifiability.

It is the data structure of Private Shared State.

Foundational Capabilities Possible with OMap

The OMap itself is a fundamental cryptographic building block with direct applications in several advanced privacy primitives:

Real-World Applications and Use Cases

The ability to maintain a confidential, updatable, and provable state opens up solutions for long-standing privacy and custody challenges.

Core Use Cases: Private Payments & Identity

The TACEO Network is actively collaborating with partners to deploy TACEO:OMap for mission-critical applications:

1. Fully Private Token Transactions

The TACEO:OMap serves as the foundational data structure for a fully private token contract where user balances, sender, and receiver of transactions are all hidden.

The setup works as follows:

• State: A smart contract (on any EVM-compatible chain) stores the public commitment (the Merkle root) of the OMap. The TACEO MPC Network holds the actual, secret-shared OMap, where the leaves contain the users’ private token balances.
• Transaction Flow: When a user initiates a transfer, they secret-share the sender and receiver addresses, as well as the transfer amount, to the MPC network. The MPC network then:
  1. Updates the secret-shared balances in the OMap.
  2. Creates a new commitment (root).
  3. Generates a Zero-Knowledge Proof attesting that the update was correct and that the sender had sufficient tokens.
• Verification: The smart contract verifies this ZK-Proof and updates its commitment. The entire process hides sender, receiver, and amount.

For deposits and withdrawals, the smart contract manages a token pool:

• Deposit: A user sends tokens to the smart contract’s pool. The MPC network updates the user’s private OMap balance accordingly, proving the update on-chain.
• Withdrawal: The user posts a withdrawal intent. The MPC network proves that the user has enough private balance and generates an update proof. The chain then verifies the proof and sends the tokens from the pool to the user.

2. Confidential Identity & Reputation

The OMap can store and update a user’s private reputation score or access credentials. The network can update the score via a verifiable computation (such as a governance vote or a successful transaction), and the user can prove their standing, without exposing the underlying data or the access history.

Exploring the Horizon: Confidential Coordination

Beyond our core applications, the OMap architecture enables new forms of confidential coordination:

• Autonomous AI Agents: Providing autonomous agents with private memory and state management. An agent can read and write to its long-term state (e.g., its goals, accumulated data, or credentials) without revealing its internal activity patterns to the host network.
• Verifiable Private Key Recovery: Utilizing the OMap to store secret-shares of recovery data, which can only be accessed obliviously and released via a complex, verifiable recovery protocol.
• Decentralized Access Control: Implementing “private whitelists” where users can prove their eligibility for a service by looking up their anonymous ID, without revealing the full list of eligible members or the specific ID they are using.

The Durable Layer of Private Shared State

The core challenge in verifiable encrypted compute is ensuring that privacy persists over time and across updates. The TACEO:OMap solves the “Access Pattern Attack”, the structural weakness that breaks standard encrypted databases, by combining three pillars:

• Verifiability (SMT): A Sparse Merkle Tree commitment ensures that every state transition is publicly auditable and provable via ZK-Proofs.
• Secrecy (MPC): Multi-Party Computation fragments the data, ensuring no single entity ever learns the key or the value.
• Obliviousness (ORAM): Oblivious RAM guarantees that the act of accessing the data (the read/write pattern) is hidden, making every operation look identical.

This creates a verifiable network fabric where secrets stay secret, outcomes stay consistent, and trust derives from computation itself.

Join us

We invite you to join us in building the next generation of privacy-preserving applications.

The TACEO team is actively collaborating with partners across payments, identity, and AI to leverage the power of PSS. If you have a privacy-critical use case that requires verifiable, confidential collaboration, contact us today to explore how the TACEO Network can become the trusted computing fabric for your data.

Acknowledgements

Thanks to Philipp Sippl and Remco Bloemen (World Foundation) for their motivation and collaboration on the OMap design.

Follow TACEO on X for the latest news.