# Merkle Proof of Compute HashCloud

## 1. Introduction

**HashCloud** uses **deterministic GPU computation** and **Merkle-rooted digest commitments** to validate miner proofs efficiently, securely, and with minimal bandwidth.

Instead of verifying every GPU-computed loop, the network performs **probabilistic Merkle subset auditing**, drastically reducing server CPU load while maintaining strong cheating detection.\
This method forms the foundation of **Merkle-Proof-of-Compute (M-PoC)** a cryptographic system ensuring that miners genuinely perform the work they claim, at a tiny verification cost.

## 2. Purpose

The **M-PoC protocol** verifies that miners truly execute GPU computations without forcing the verifier to recompute the entire workload.

It is designed to achieve:

* ✅ **High fraud detection probability**
* 📶 **Low bandwidth usage**
* ⚙️ **Low server CPU load**
* ⚡ **Compatibility with high-speed GPUs**
* 📈 **Scalable deterministic verification** via matrix multiplications (matmul)

## 3. Key Terminology

| Term                  | Description                                                      |
| --------------------- | ---------------------------------------------------------------- |
| **Loop**              | One deterministic GPU compute iteration (e.g., matrix multiply). |
| **Leaf**              | SHA-256 digest derived from a loop’s seed and output.            |
| **Merkle Root**       | The top hash committing all loop leaves.                         |
| **Sample Leaf**       | A subset of leaves (and their proofs) sent to the verifier.      |
| **Audit Set (m)**     | Number of sample leaves verified by the server.                  |
| **Digest Commitment** | The miner’s proof of computation (Merkle root).                  |

## 4. Core Concept – Merkle Commitment + Random Auditing

Each miner commits all loop results into a **Merkle tree** of digests but only transmits **s sampled leaves** with their Merkle proofs.

Why It Works

* The **Merkle root** cryptographically binds all loop digests the miner cannot alter missing parts.
* The **server only recomputes** a random subset (**m**) of the submitted sample leaves.
* If **any audited leaf fails**, the miner is caught instantly.
* To cheat safely, the attacker must compute nearly all genuine leaves rendering cheating pointless.

## 5. High-Level Protocol Flow

### Miner Steps

{% stepper %}
{% step %}

### Receive challenge payload

Payload structure:

```
{ seed, challenge_id, expiry, token }
```

{% endstep %}

{% step %}

### Compute deterministic GPU loops for duration T

Pseudo:

```
for each loop i:
    loop_seed_i = seed || ":" || i
    output_i = deterministic_matmul(loop_seed_i)
    leaf_i = SHA256(loop_seed_i || output_i)
```

{% endstep %}

{% step %}

### Build Merkle tree

Obtain `merkle_root` committing all leaves.
{% endstep %}

{% step %}

### Select samples

Select **s** sample indices distributed across all loops.
{% endstep %}

{% step %}

### Submit proof payload

Example JSON:

```json
{
  "challenge_id": "...",
  "token": "...",
  "seed": "...",
  "loops": 12345,
  "compute_time": 14.21,
  "merkle_root": "0x...",
  "samples": [
    { "index": 123, "leaf": "0x...", "proof": ["0x...", "..."] }
  ],
  "device_signature": "0x..."
}
```

{% endstep %}
{% endstepper %}

### Server Steps

{% stepper %}
{% step %}

### Validate credentials and sanity checks

* Validate `token` and `device_signature`.
* Sanity-check loop count, compute time, and rate limits.
  {% endstep %}

{% step %}

### Randomly choose audit set

Randomly choose **m** sample indices for audit.
{% endstep %}

{% step %}

### For each audited index

* Recompute deterministic matmul output.
* Recompute leaf hash.
* Verify Merkle proof against submitted `merkle_root`.
  {% endstep %}

{% step %}

### Decision

* ✅ If all **m** pass → Accept submission
* ❌ If any fail → Reject & apply penalty
  {% endstep %}
  {% endstepper %}

## 6. Default Parameters

| Parameter     | Symbol | Typical Value | Description                      |
| ------------- | ------ | ------------- | -------------------------------- |
| Sample count  | s      | 10            | Leaves submitted per proof       |
| Audit count   | m      | 3             | Random leaves verified by server |
| Loop duration | T      | Dynamic       | Mining challenge duration        |
| Hash function | —      | SHA-256       | Used for leaves and Merkle nodes |

## 7. Detection Probability

If a miner forges **X** leaves out of **s** samples, and the server audits **m** random samples, the probability of catching the cheat is:

$$
P\_{detect} = 1 - \frac{\binom{s - X}{m}}{\binom{s}{m}}
$$

Example:\
`s = 10`, `m = 3`\
Even if only a few samples are forged, detection probability approaches 99%. Therefore, miners gain no real advantage by cheating.

## 8. Server Audit Logic

The server **dynamically adjusts audit probability** based on:

* Claimed compute speed vs. device profile
* Loop-to-time ratio consistency
* Historical miner accuracy

This adaptivity ensures stronger audits for suspicious or near-limit behavior while minimizing overhead for honest miners.

## 9. Developer Implementation

### Miner Pseudocode

```python
for i in range(loops):
    output = matmul(i)
    leaf[i] = SHA256(seed + ":" + str(i) + output)
merkle_root = build_merkle_tree(leaf)
s_indices = choose_samples(loops, s)
samples = [(i, leaf[i], merkle_proof(i))]

submit({
    "seed": seed,
    "loops": loops,
    "merkle_root": merkle_root,
    "samples": samples
})
```

### Server Pseudocode

```python
verify_token()
verify_signature()
check_limits()

if should_audit():
    selected = random_subset(samples, m)
    for idx, leaf, proof in selected:
        recomputed = SHA256(seed + ":" + str(idx) + matmul(idx))
        assert verify_merkle_proof(leaf, proof, merkle_root)
```

## 10. Fairness

* **Fast GPUs** are not penalized results are normalized by compute time.
* **Merkle audits verify correctness**, not raw speed.
* **Low bandwidth** submissions make participation accessible even on constrained networks.

## 11. Best Practices & Recommendations

* Use **s = 10**, **m = 3** for baseline deployments.
* Increase `s` or `m` if miner behavior seems abnormal.
* General rule:

$$
s \approx \max(10, loops \times 0.01)
$$

* Distribute sample indices evenly across the full loop range.
* Always use deterministic matmul functions to ensure verifiable consistency.

## 12. Conclusion

The **Merkle-Proof-of-Compute (M-PoC)** protocol is a **scalable, secure, and efficient** system for verifying deterministic GPU computations in decentralized mining environments.

By combining **Merkle commitments** with **probabilistic subset audits**, M-PoC guarantees that every miner’s work is:

* Cryptographically verifiable
* Fraud-resistant
* Lightweight to audit
* Fair across heterogeneous hardware

This architecture establishes a foundation for **trustless, high-throughput GPU compute validation** the core of **HashCloud’s decentralized mining framework**.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://docs.hashcloud.sh/merkle-proof-of-compute-hashcloud.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.