# 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**.