PRT FRAUD PROOF FOR NON-MATHEMATICIANS

Introduction

The need to scale programmable blockchains has created a strong demand for secure ways to offload computations outside the blockchain. One of the most popular options today is called rollups. Rollups involve off-chain nodes executing these offloaded computations, then proving the results back to the base layer. This is a good approach to solving the scalability issue, as these off-chain computers are not constrained by the limitations of the blockchain network. They, therefore, can be more specialised, faster and better equipped to handle complex transactions.

The decentralised and permissionless nature of the blockchain introduces new challenges. Anyone should be able to run one of these off-chain nodes, process computations and submit results to the base layer. The big question then is: How then do we handle conflicting results between these multiple off-chain validators? Or more importantly, how do these more computationally capable validators prove to a less computationally capable on-chain virtual machine that their execution is accurate even when others disagree?

One of the simplest ways to determine correctness among multiple claims is a simple majority rule consensus, where all participants provide the result of a computation and the result that appears most frequently gets accepted. While this may look valid, it offers no protection against a dishonest majority and is susceptible to Sybil attacks, where an attacker sets up multiple fake validators to overwhelm the network and then posts a false result using them. To mitigate such risks, a number of more robust methods to identify a valid result among multiple others have been developed, and two of the most widely used are validity and fraud proofs. Validity proofs are very computationally intensive to generate, requiring that the proving machine meet high performance requirements to produce a proof. Fraud proofs, on the other hand, optimistically treat claims as valid but offer a time window for honest participants to challenge/dispute said claim. Thereby requiring less computationally intensive computers to run as compared to validity proofs.

While both validity and fraud proof offer strong points and trade-offs over the other, we’ll be focusing solely on just one of them, being fraud proof.

Fraud proofs generally fall into two categories: interactive and non-interactive. While both of them optimistically treat claims as valid, they differ in how disputes are handled. In interactive fraud proofs, the resolution process involves a back-and-forth exchange between the validator and his challenger. This interaction spans over multiple rounds or tournaments. Non-interactive fraud proofs, by contrast, rely on a single self-contained proof that is submitted without requiring multiple rounds of interaction.

Interactive fraud proofs generally allow an honest validator to challenge incorrect results submitted by other validators. This is done by initiating a dispute, where both parties present evidence, and an on-chain smart contract acts as a judge. It uses a predefined dispute resolution algorithm to guide the resolution process and determine which party is correct.

In this article, we’ll focus on one of the most effective dispute resolution algorithms available today: PRT (Permissionless Refereed Tournament). PRT is an interactive and scalable, fraud-proof system designed to efficiently identify the correct result, even in large networks with many conflicting claims. PRT’s scalable feature ensures that the system remains performant and accurate regardless of the number of Sybils or dishonest participants, as long as a single honest participant exists.

PRT FRAUD PROOF

PRT (Permissionless Refereed Tournaments) is a fraud-proof algorithm developed by Diego Nehab and Augusto Teixeira, two researchers at Cartesi and IMPA. At its core, PRT allows a single honest validator to enforce the correct result of a computation against a multitude of other false claims. Today, it’s regarded as one of the most decentralised and secure fraud-proof mechanisms, and in a couple of minutes we’ll understand why and how it works.
Before discussing more, it’s important to understand off-chain computations and certain fundamental assumptions for understanding PRT. We’ll review these through these three questions:

1). How can off-chain validators be expected to arrive at the same result, especially when they are distributed and independently operated?

To ensure verifiability, all validators run the same deterministic virtual machine, meaning that with the same input and state, they always produce the same output.

To make the outcome of each computation traceable and verifiable, these validators maintain a state commitment over their entire state. A state commitment is a hash that uniquely represents the entire memory state of a machine at a given time. This commitment allows anyone to verify that a machine transitioned from one valid state to another without inspecting the full memory.

Various data structures such as Merkle trees, Verkle trees, Patricia trees, and KZG commitments can be used to efficiently organise state data and compute these state commitments efficiently, but for the purpose of this article, we’ll be focusing on the widely used Merkle tree approach.

To visualise this, imagine the machine’s memory as a large shelf made up of individual compartments; each compartment (sometimes called a “slot” or “word”) holds a piece of information such as data, a value, a register, or an instruction. A Merkle tree organises these compartments in a way that allows you to generate one final “root hash” that summarises everything on the shelf. This is achieved by concurrently pairing and hashing these slots until a final root hash is obtained. Even a tiny change in one compartment causes the root hash to change, so if two machines produce the same root hash, we can be confident they ran the same computation and ended up in the same state.

This use of Merkle trees not only secures the memory but also enables rapid and efficient verification of memory contents without needing access to the entire memory.

The diagram below shows a basic example of this: it compares the memory state before and after adding the values from slots x0 and x2, then saving the result to slot x4.

2). How are transactions executed in this deterministic virtual machine?

Deterministic environments are built so that no matter who runs a program, it will always produce the same result, so long as the input and initial state are the same. These environments process instructions one step at a time and track every memory change carefully.

Let’s take a simple maths expression as an example:

(5 × 3) + (8 × 2).

This is a high-level instruction a user wants to execute in a deterministic machine. A deterministic virtual machine wouldn’t just jump to the final answer. Instead, it would break this down into individual steps (low-level instructions), like loading values into memory, multiplying them, adding the results, and saving the final output. Each of these steps is recorded in what’s called an execution trace, a log of what the machine did at each step.

Here’s how that trace might look, using simplified labels:

At each step, the machine updates its memory and generates a new Merkle root that summarises the memory’s state. This root acts like a fingerprint of the machine’s memory at that moment. So, instead of revealing the entire memory to prove what changed, a small Merkle proof can be used to show that a specific value changed correctly, based on its position in memory.

In the rest of this article, we will be making reference and basing our dispute on these execution steps above.

3). How are computation results submitted to the base layer?

At this point, we understand how computations are executed and how a log or Merkle proof of every state transition is generated. It’s now important we understand how computation results are submitted back to the base layer.

In addition to using a virtual machine, rollups use consensus contracts on the base layer to verify off-chain computations. These contracts do not rerun the full computation. But use a simplified logic to verify small steps. Verification is done on the submitted claims using trace data and Merkle proofs. This allows the consensus contract, which we’ll be referring to in this article as the verifier or referee, to confirm that a specific instruction was executed correctly, without needing to examine the full memory.

How PRT resolves disputes:

Now that we understand that every off-chain validator in a rollup protocol runs the same set of executions and should naturally return the same results and also how they each submit their result back to the base layer, it’s time to go a bit deeper and discuss how PRT handles conflicting results and disputes.

Remember from our earlier conversation, we mentioned that PRT enables a single honest prover to successfully defend a correct result against multiple false results. Let’s illustrate this using our already explained mathematical computation request:

(5×3)+(8×2)

This example will be based on 4 off-chain validators, Bob, Alice, Lex, and Matt, of whom Bob is honest, while Alice, Lex, and Matt are all dishonest. Bob runs the execution and has an accurate final result of 31, while Alice, Matt, and Lex all come up with incorrect results of 175, 50, and 70, respectively.

For final submission of results back to the base layer, PRT requests that each of the 4 participants submit three data sets to the verifier; these are the final state hash, the computation hash and a Merkle proof that the final state hash is part of the computation hash. We’ll be focusing on just 3 of these, as they fall within the scope of our discussion.

1. Final state hash: This is the root hash of a Merkle tree of all the storage slots of the off-chain VM after the complete execution; it represents the final state of the machine after the computation.
2. Computation Hash: This is the root hash for a Merkle tree of the state hash after every step of the computation. Our model has 8 steps, so this would be a Merkle tree of 8 initial leaves, each representing the state of the machine after each step. What this means is that after every step, the off-chain VM generates a Merkle tree of its storage slots. At the end of the computation, we have 8 Merkle trees, one for each step, and then the root of each of the 8 Merkle trees is used to generate a new Merkle tree whose root becomes the computation hash.
3. Merkle proof: This is a Merkle proof that is used by the verifier to confirm that the submitted final state hash is part of the leaves recursively hashed to obtain the computation hash.

The Verifier contract, on receiving these different result claims, pairs them up as they arrive. Let’s say Alice sends her result first, followed by Bob, Lex, and Matt; they are then grouped in pairs as they arrive into Alice X Bob and Lex X Matt. Each pair begins a dispute tournament, as explained below.

For each pair, the verifier performs a binary search over the STEPS to find a bisection where both opponents agree on a previous state hash but conflict in the next state hash. To understand this better, let’s narrow down to Bob X Alice’s battle. From the table below showing the STEP trace of Bob and Alice, it’s clear that they were both in sync until step 5, where Alice loads 20 instead of 2 to memory slot x5, thereby causing the state from that step forward to differ from what Bob proposes.

The verifier starts the binary search between for Bob X Alice at the mid-step, being step 4. It proceeds to ask both participants to present the state hash at step 4 and a Merkle proof that this state hash is contained in the initial computation hash submitted. Remember that the computation hash is a Merkle root of all the state hashes in the steps. This would ensure that no participant can present a random state hash during the dispute, as every hash presented is verified to be contained in the initial computation hash presented.

Both Bob and Alice present the state hash and Merkle proof for step 4 and since they both ran the same execution, they would have the same hash, so the verifier knows that the conflicting step happens somewhere after step 4. The verifier therefore adjusts the lower band of the binary search to 5 and the higher band remains at 8. This time the binary search lands at step 6, so the verifier proceeds to ask both parties once again for the state hash and the Merkle proof of state 6, which they both provide, and the verifier confirms that there’s a conflicting state hash at step 6.

It’s now obvious to the verifier that since there’s a conflicting hash at step 6 and a matching hash at step 4, the error likely happens between steps 6 and 4, so it adjusts and asks both parties to present the state hash and proof of step 5. After this presentation, the verifier confirms that there’s a conflicting hash in step 5. Since both Bob and Alice present the same hash in step 4 and a different hash in step 5, it means one or even both parties must have altered the normal execution flow in step 5.

On identifying the false proof, the verifier asks both parties to present the following:

• The exact instruction ran: In our case, for step 5, Bob ran “Load 2 into slot x5,” while Alice ran “Load 20 into slot x5.”
• Merkle proof of every state accessed: This is a Merkle proof verifying that every storage slot read and used during that execution STEP was present in the previous state hash, and also every storage slot written to is present in the current state hash.

We expect Bob to present a Merkle proof that “2 was loaded to slot x5,” which the verifier confirms using the root hash of STEP 5. Meanwhile, if Alice lies that she “loaded 2 into slot x5,” she’ll need to present a Merkle proof that will be run against the state root hash of STEP 5 and since she added 20, not 2, she’ll definitely be unable to present a proof that would verify that 2 was loaded.

Even if Alice can generate a proof for loading the correct value, she’ll end up getting in the same state hash as the honest machine (Bob), since that’s the only modified state in the STEP. However, if she admits that she “loaded 20 into slot x5” and presents honest proof of that, then this is confirmed to be true, but the verifier can tell that the expected execution for that step was to “load 2 to slot x5,” meaning she gets caught.

Alice is identified as dishonest and kicked out of the tournament. While at the same time, either Lex or Matt wins their match, and the other is kicked off, leaving just two validators in the tournament.

Let’s say Matt survived the tournament despite also being dishonest (this mostly happens if Lex lies in an earlier step compared to Matt and therefore is caught earlier than Matt). The surviving participants in this level are then grouped once more, and a new round of battle begins between Bob X Matt. The verifier goes through the entire process of carrying out a binary search to find the exact STEP in which they both present their first conflicting claim, then goes further to verify the process ran in that STEP, and as expected, Matt is caught and eliminated, leaving Bob as the final winner.

As we can see from our sample model, a single honest machine, Bob, is able to defend a valid state hash against 3 other dishonest validators.

PRT 2 Levels:

While the explanation so far provides a solid foundation for understanding PRT’s structure and resolution process, it’s important to note that a single-level implementation (PRT 1L) would be too expensive and burdensome for the off-chain validators. This is because the kinds of complex computations that typically require off-chain validation are rarely simple; they often involve millions or billions of big steps, each composed of many micro-steps, like the example previously described.

Attempting to resolve real-world disputes using only PRT 1L would mean building a computation hash after every step of execution. For complex computations, often comprising billions or even trillions of steps, this would impose an immense computational load on validators. As a result, the process becomes too expensive and inefficient, especially for verifiers tasked with validating long-running or resource-intensive transactions.

To address this inefficiency, PRT 2L was introduced. The core idea behind PRT 2L remains similar to 1L: validators process off-chain requests and produce a computation hash. However, instead of doing so after every individual step, a sparse computation hash is generated after a large number of big steps; for example, a sparse computation hash can be generated after every 32,000 big steps (state transitions). This drastically reduces the overhead of generating Merkle proofs for every transition.

These 32k-interval state hashes are then compiled into a Merkle tree (i.e., a computation hash) to produce a final state commitment, which is submitted as a commitment to the verifier. The verifier, upon receiving multiple submissions, pairs them and feeds each pair into a two-level interactive dispute resolution tournament.

• Level 1: Top Level

At the first level, a binary search is carried out over the sparse computation hashes that were submitted. The verifier performs a binary search across this range from 0 to the total number of sparse computation hashes to identify the exact hash where the bisection occurred. This process closely resembles the original PRT 1L approach, where at a point in the binary search, the verifier requests state hashes and corresponding proofs from the validators, verifies them, then updates the binary search range (either upper or lower bound) accordingly, until the exact interval where the disagreement occurs is pinpointed. This divergence represents a block of 32,000 state transitions, so narrowing down to one still leaves a full interval in which the disagreement lies.

Once this interval is identified, the verifier escalates the pair by recursively creating a new tournament; this new tournament is called the second-level tournament or Level 2 tournament.

• Level 2: Bottom Level

This is the final stage of the tournament. By this point, we’ve narrowed down the dispute to a specific 32,000-step interval out of the original millions of state transitions. In this round, the verifier performs a binary search within that 32k range, requesting the computation hash and corresponding Merkle proof at each step it inspects. This process continues until the exact step at which the bisection occurs is found. Once this is identified, similar to PRT 1L, the verifier proceeds to check the execution logs and then identifies which of the pair is honest and which isn’t.

Transitioning from a single-level (PRT-1L) to a two-level (PRT-2L) dispute system significantly reduces the burden on both the validator and the verifier. Rather than performing a binary search over, say, ten million steps, the system narrows it down to just a few dozen hashes at the first level and then performs a more focused search in the second level. This drastically cuts down the number of interactions required for validators to submit computation hashes and Merkle proofs, leading to substantial savings in both computational effort and on-chain gas costs.

PRT 3 Levels and the Cartesi Honeypot:

The Cartesi Honeypot, currently deployed on both Mainnet and Sepolia, is the first real-world application utilising the PRT fraud-proof system. This application adopts a modified version of the standard PRT algorithm, which we’ll now refer to as PRT 3 Levels, in contrast to the earlier PRT 1 Level and PRT 2 Level approaches.

While the core components, such as off-chain computation, on-chain verification, and a consensus contract serving as the referee, remain unchanged, the major difference in PRT 3L is its tournament-level structure. In PRT 1L, disputes are resolved through a single-level binary search. PRT 2L improved on this by introducing a two-level structure; PRT 3L extends this idea by further adding a third level, making the process even more scalable.

With PRT 3L, computation hashes are generated even more sparsely when compared to PRT 2L; for example, a computation hash could be generated once every one million big steps. Thereby creating much larger intervals compared to the 32,000 big step intervals in PRT 2L. In PRT 3L, Level 1 performs a binary search across these 1 million-step sparse computation hashes, significantly reducing the number of top-level checkpoints, while Level 2 narrows the search to another smaller chunk of sparse computation hashes, for example, computation hashes generated after 128 big steps within the initially identified 1 million big step intervals. Finally, Level 3 then carries out a fine-grained binary search over the final 128 big steps to pinpoint the exact step where divergence occurs.

This three-level structure, when compared to previous versions, drastically reduces the number of required interactions and on-chain operations, making it more efficient for handling very large computations.

Conclusion

Fraud-proof systems like PRT offer a powerful foundation for scaling decentralised systems by enabling secure, permissionless computation without requiring trust in any single participant. They ensure that correctness can be enforced not by majority rule but by verifiable truth, protecting networks from manipulation and maintaining integrity at scale.

While there are currently multiple fraud-proof algorithms available, PRT stands out for its ability to handle large numbers of participants, resolve disputes step-by-step, and also empower honest provers to win even in the face of many dishonest claims.

So far, we’ve explored how PRT works and visualised its step-by-step dispute resolution process. In upcoming articles, we’ll dive into DAVE, an advanced evolution of PRT. It introduces key optimisations and addresses certain limitations that could help PRT even scale better.

REFERENCE

Ne­hab, D., & Teixeira, A. (2022, December 23). Permissionless Refereed Tournaments (arXiv:2212.12439). arXiv. https://doi.org/10.48550/arXiv.2212.12439