Probabilistic Verification

The protocol randomly samples nonces from the benchmark. For each sampled nonce, the benchmarker must submit a Merkle proof containing the output data and Merkle branch.

This random sampling makes it irrational for Benchmarkers to fraudulently “pad” a benchmark with fake solutions:

If a Benchmarker computes N solutions, and pads M fraudulent solutions to the benchmark for a total of $N + M$ solutions, then the chance of their fraud being undetected is $\frac{N}{N+M}$ for each sample. With multiple samples, the fraud is likely to be detected, wasting the real work done to compute the N solutions.

For example, if 50% of the solutions are fraud, with 3 samples, the chance of the fraud being detected is 87.5%.

If a benchmarker’s benchmark fails probabilistic verification (due to fake solutions or errors) they are penalized.

Merkle Proof

A Merkle tree proof works by organizing data into a tree structure where each leaf node contains a hash of a data packet, and each parent node contains a hash of its children’s hashes, continuing up to a single root hash called the Merkle root. To verify a specific piece of data (shown in red in the figure below), the prover only needs to provide the data itself along with the sibling hashes (shown in blue in the figure below) at each level along the path to the root. The verifier can then recompute the path by hashing the data and combining it with the provided sibling hashes, ultimately confirming that the computation reaches the known Merkle root. This is a popular verification system because it allows efficient verification of large datasets without requiring the verifier to store or process all the data.

In TIG, the data packets that form the leaves of the Merkle tree are the nonce data submitted by benchmarkers for their benchmark runs. The data for each nonce includes the nonce, fuel_consumed, solution, cpu_arch and the runtime_signature:

    OutputData {
        nonce: u64,
        runtime_signature: u64,
        fuel_consumed: u64,
        solution: Solution,
        cpu_arch: CPUArchitecture,
    }

Runtime Signature

TIG has designed a new high-performance native runtime to execute algorithms as compiled machine code on:

x86_64: Intel and AMD processors
aarch64: ARM processors
CUDA: NVIDIA GPUs

Every algorithm run must produce a runtime_signature, which is a fingerprint of the exact execution path of the algorithm. This way, executions can be verified deterministically by the protocol.

Solution Discard Innovators