Trust Without Trustees

Eighteen Months and a Million Dollars: Part 4

Excerpts from the Whitepaper

Key Takeaways

• A central question in decentralized compute: how do you trust computation done by a machine you don't control?
• Three categories of verifiable computing: cryptographic methods, secure enclaves (TEEs), and replication
• Local vs global consensus is a spectrum, not a binary choice
• In replication-based verification, local consensus can, in principle, drive the number of replications needed down to 1
• Approximate agreement can handle non-deterministic computations
• Every verification method is some combination of slow, inefficient, expensive, or insecure: the honest answer is tradeoffs

Verifying compute you didn't run

Outsourcing compute is easy. Outsourcing trust is not.

In our last post, we introduced Alkahest and the two-primitive architecture. Alkahest handles exchange and commitment. Agent-to-agent negotiation handles matchmaking. But there's a question we've been circling since the first post in this series: how do you trust computation done by a machine you don't control?

In a trustless, permissionless distributed computing marketplace, verifiability becomes central. How do clients know that they are getting the correct results returned to them, if not through the massive replication of Byzantine Fault Tolerance traditionally offered by blockchains?

This is the subject of a subfield of computer science known as verifiable computing, and it's arguably one of the hardest problems in decentralized infrastructure. The constraint is clear: verifying the result should have less overhead than computing the result in the first place. If verification costs more than doing the work yourself, there's no point in outsourcing it if you could handle it alone.

Different applications need different trust levels. A financial transaction might require cryptographic certainty. A scientific simulation might accept statistical confidence. A rendering job might only need visual inspection.

And many customers don't want verification at all; they want a counterparty they trust. This is one key reason non-Web3 neoclouds have been able to win: they start with a narrow set of customer needs and rely on reputation, contracts, and recourse instead of "trustless" verification.

One-size-fits-all verification doesn't exist, and pretending otherwise is how protocols end up building something nobody can actually use.

In what follows, we'll break verification into three broad categories, then frame consensus as a spectrum (not a binary), then look at what happens when computations aren't deterministic, and finally be explicit about the tradeoffs.

Three categories

There are three main categories of verifiable computing: cryptographic methods, secure enclaves (TEEs), and replication-based methods.

First, cryptographic methods. These rely on mathematics for their security. Zero-knowledge proofs let a prover convince a verifier that a computation was done correctly without revealing private inputs. Multi-party computation allows joint computation without exposing individual inputs. Fully homomorphic encryption enables computation over encrypted data. These methods provide the strongest guarantees, but they are also among the slowest and most expensive. For many practical workloads today, cryptographic verification costs far more than the computation itself.

Second, secure enclaves (TEEs). These are isolated environments where code and data are insulated from the rest of the system, including the operating system. The goal is to maintain both confidentiality and integrity. TEEs have a promising future, especially as exploits continue to be patched, but even the known exploits continue to limit applicability.

Third, replication-based methods (often called "optimistic" verification). These rely on recomputing the work and checking whether results match. This is the simplest approach to understand and implement, but it comes with extra computational cost. With proper incentive design, the overhead of recomputing can be reduced while still enabling network scaling. Replication often requires game-theoretic mechanisms like collateral slashing and reputation layers to counter cheating.

The consensus spectrum

The verification question is tied to a deeper question about consensus: how many entities need to agree that a computation was done correctly?

At one end of the spectrum is global consensus. Blockchains traditionally achieve consensus through massive replication across all participating nodes. This provides strong guarantees: Byzantine Fault Tolerance ensures the network reaches agreement even when some nodes act maliciously. But this level of replication becomes too costly when the corresponding level of security is not needed.

At the other end is local consensus, which at a minimum only requires a single agent to be convinced of the state. For a two-sided marketplace, only the client really needs to be convinced that a computation was done correctly. But these computations are not done in isolation. The interrelation between clients choosing nodes, and the need for new clients to arrive and be assured that cheating is disincentivized, implies the creation of a global game that, while not requiring global consensus in the traditional sense, emulates it.

Between these extremes are hybrid designs. Local versus global consensus is not a binary choice but a spectrum. The middle involves agreement among a subset of nodes, perhaps within a specific region or cluster, which can lead to faster and more efficient decision-making through reduced communication overhead. Systems can balance speed, efficiency, and security based on their specific requirements.

One of the primary benefits of local consensus, in the context of replication-based verification, is that market incentives can, in principle, be structured to drive the total number of replications needed for verifiability down to one. This minimizes computational cost, financial cost, and energy consumed. Getting to a single replication is the target: it means every unit of compute goes toward useful work, not redundant checking.

When computations aren't deterministic

Note: There has been significant research and practical progress on this topic since the whitepaper was completed in summer 2024. This section primarily summarizes the whitepaper's framing.

Replication-based verification sounds straightforward: run the job twice, compare results. But this assumes determinism. If the same program on two different machines produces exactly the same output, the comparison is trivial.

What happens when the computations are not deterministic? Neural network inference on different hardware can produce different results. Floating point arithmetic varies across architectures. Parallel workloads with race conditions produce different orderings.

Once outputs differ, the real question becomes: what does "match" mean?

One option is approximate agreement: if the verification yields a result close enough to the original, the result is considered valid. BOINC (the Berkeley Open Infrastructure for Network Computing) has been using approximate agreement for a long time. The approach works, but it requires an application-specific distance measure, which introduces developer overhead.

Approximate agreement might apply to some neural networks. In large language models, it might be possible to measure the distance between outputs before decoding. But slightly different outputs before decoding can still lead to large differences after decoding, which leaves room for abuse.

Another option is objective-function-based evaluation. Proof-of-Work is a classic example: solving a cryptographic puzzle is hard, but verifying the solution is cheap. The proof is in the result itself. Similar approaches work for problems where the answer is easy to check even if it's hard to find.

And sometimes the right answer is to trust the compute node and not verify at all. This doesn't count as verifiable computing, by definition; however, reputation systems have decades of research behind them, and for many applications the trust tradeoff is acceptable.

Honest about limitations

Every lock can be picked. Every verification approach has weaknesses.

• Cryptographic methods for verifiable computing are very slow and will almost certainly always be much more expensive than bare metal execution for many workloads.
• Secure enclaves have exploits, and while the future is promising as patches continue, they are not ready for highly sensitive applications.
• Optimistic verification suffers from issues of determinism, and even when those are solved or approximated away, there remain deep issues of collusion.

Verifiable computing options are, at present, some combination of slow, inefficient, expensive, or insecure.

This isn't a problem to be solved by picking the "right" method. Every method trades one thing for another. The most flexible approach is to support all three categories and let applications choose the verification that matches their risk tolerance, performance requirements, and budget.

Arkhai's design enables the incorporation of all of these methods. Alkahest's programmable conditions don't care whether the validator is checking a zero-knowledge proof, a TEE attestation, or the output of a replication check. The verification layer is modular. Swap in different validators for different trust levels.

The shortcomings of all of these approaches will decline with time and increasing use. Cryptographic methods are getting faster. TEE exploits are getting patched. Replication mechanisms are getting smarter about collusion. But waiting for a perfect solution means shipping nothing. The pragmatic choice is to build the system that supports all approaches and improves as each approach matures.

What this means for you

If you're building on decentralized compute, the verification question will define your architecture. Don't pick a verification method in the abstract. Start with your application's requirements. How sensitive is the data? How expensive is the computation? What's the cost of a wrong result?

One coarse way to think about it:

• For low-stakes workloads like rendering, batch processing, or data transformation, replication with reputation may be sufficient.
• For moderate-stakes workloads like scientific simulation or model training, approximate agreement or TEE-backed execution can provide stronger guarantees.
• For high-stakes workloads like financial computation or medical inference, cryptographic methods may be worth the overhead.

These aren't mutually exclusive. A single marketplace can support all three categories, with applications selecting the trust level they need. This is what Alkahest's modular validator system enables.

Next in the series

We've covered how Alkahest handles exchange and commitment, and how different verification methods handle trust. But there's a practical problem we haven't addressed: collateral.

When a compute node takes a job, how much collateral should it deposit? What if the computational cost isn't known ahead of time? In our next post, we'll introduce collateral markets and show how programmable escrow handles the unknown.

---

Arkhai is building machine-actionable marketplace infrastructure. If you're working on problems that intersect with compute markets, agent coordination, or decentralized infrastructure, we'd like to hear from you.