coracle-rust/book/08-proof-of-work.md

Proof of Work

Every event id is a SHA-256 hash. Most of the time that hash is whatever it happens to be — nobody cares about the specific bit pattern. Proof of work changes that. NIP-13 defines a convention where a client burns CPU time searching for a nonce that makes the event id start with a target number of leading zero bits. The result is an event that carries a verifiable proof of computational effort baked into its identity.

The purpose is spam resistance. A relay can require that incoming events have, say, 20 leading zero bits. Generating one costs the publisher roughly 2^20 hash attempts — a second or two on modern hardware — but spamming a thousand events costs a thousand times that. It is not a substitute for moderation, but it raises the floor.

The protocol mechanism is a single tag: ["nonce", "<counter>", "<target>"]. The first value is the nonce that was found; the second is the difficulty the miner was aiming for. Both are needed: the nonce changes the event id (because tags are part of the hash input), and the target records intent so that a verifier can distinguish a miner who committed to 20 bits of work from one who committed to 4 and got lucky.

This chapter builds three things: a function to count leading zero bits, a function to read the validated proof-of-work difficulty from an event, and a pair of mining functions that search for a valid nonce and return a HashedEvent with the proof embedded. The mining API is batch-based: callers control the loop, which keeps the library free of platform-specific threading or async machinery.

The module

pub mod pow;

//! NIP-13 proof of work: difficulty validation and mining.
//!
//! [`mine_pow`] blocks until a valid nonce is found. [`mine_pow_batch`]
//! tries a bounded range of nonces and returns `None` if the batch is
//! exhausted, giving the caller control over cancellation and
//! parallelization.

use sha2::{Digest, Sha256};

use crate::events::{HasId, HasTags, HashedEvent, OwnedEvent};
use crate::tags::{Tag, Tags};

Counting leading zero bits

Everything else in this module builds on one primitive: counting how many leading bits of a byte slice are zero. A hash with 20 leading zero bits starts with at least five zero hex characters (20 / 4 = 5). Difficulty is measured in bits, not hex characters, because bits give finer granularity — you can require 21 bits of work, not just 20 or 24.

The algorithm walks through bytes. Each fully-zero byte contributes eight bits. The first non-zero byte contributes its own leading zeros (via the leading_zeros intrinsic, which compiles to a single CPU instruction on most architectures), and then we stop — no byte after that can contribute leading zeros.

/// Count the number of leading zero bits in a byte slice.
///
/// Returns 0 for an empty slice. For a 32-byte SHA-256 hash, the
/// maximum return value is 256.
pub fn get_leading_zero_bits(hash: &[u8]) -> u8 {
    let mut count: u8 = 0;
    for &byte in hash {
        if byte == 0 {
            count += 8;
        } else {
            count += byte.leading_zeros() as u8;
            break;
        }
    }
    count
}

Validation

Validating proof of work on an existing event means answering the question: how much work did this event commit to? That's the minimum of two values — the actual leading zero bits in the hash and the difficulty claimed in the nonce tag. The hash proves work was done; the tag proves intent. A miner who targeted difficulty 4 and happened to land on 20 zero bits only committed to 4 bits of work.

The core logic takes just an id and tags so it can be shared across event types.

/// Return the validated proof-of-work difficulty for an event id and tags.
///
/// The result is the minimum of the actual leading zero bits in `id`
/// and the difficulty target claimed in the `nonce` tag. Returns 0 if
/// no nonce tag is present.
pub fn get_pow(id: &[u8; 32], tags: &Tags) -> u8 {
    let leading = get_leading_zero_bits(id);

    let claimed: u8 = tags
        .find("nonce")
        .and_then(|t| t.get(2))
        .and_then(|s| s.parse().ok())
        .unwrap_or(0);

    leading.min(claimed)
}

The nonce tag's third entry (index 2) holds the difficulty target as a decimal string. If the tag is absent or the value doesn't parse, the claimed target is zero, so get_pow returns zero — no verifiable commitment was made.

Methods on event types

Proof of work is the first query that needs the event id as well as its tags, so its extension trait is bounded on both HasId and HasTags from the events chapter. The method body delegates to the free function through those accessors, and the blanket impl puts get_pow on every type that satisfies the bound — both HashedEvent and Event do. Callers write event.get_pow() >= 20 regardless of whether the event has been signed yet, as long as the trait is in scope (via coracle_lib::prelude::*).

/// Proof-of-work queries on any event that has an id and tags.
pub trait EventExtensionProofOfWork: HasId + HasTags {
    /// Return the validated proof-of-work difficulty of this event.
    ///
    /// The result is the minimum of the actual leading zero bits in the
    /// event id and the difficulty claimed in the nonce tag.
    fn get_pow(&self) -> u8 {
        get_pow(self.id(), self.tags())
    }
}

impl<T: HasId + HasTags> EventExtensionProofOfWork for T {}

pub use crate::pow::EventExtensionProofOfWork;

Mining

Mining is a brute-force search. For each candidate nonce, the miner builds a nonce tag, constructs the canonical serialization that the events chapter defined, hashes it, and checks the leading zero bits. If the hash meets the target, the search is over; if not, it tries the next nonce.

The canonical form is the same JSON array from the events chapter: [0, pubkey, created_at, kind, tags, content]. The nonce tag is appended to the event's existing tags before serialization, so the nonce value feeds into the hash. Changing the nonce changes the hash — that's the whole mechanism.

Two free functions expose this search at different levels of control, and OwnedEvent gets methods that delegate to them.

mine_pow — the simple interface

For callers who just want a result and are willing to block until it arrives:

/// Mine proof of work for an event, blocking until a valid nonce is found.
///
/// Appends a `["nonce", "<counter>", "<difficulty>"]` tag to the event's
/// tags and searches for a nonce that produces an event id with at least
/// `difficulty` leading zero bits. Returns the resulting `HashedEvent`.
///
/// This function does not return until a solution is found. For
/// cancellation or parallelization, use [`mine_pow_batch`] instead.
pub fn mine_pow(event: &OwnedEvent, difficulty: u8) -> HashedEvent {
    let mut start: u64 = 0;
    loop {
        let batch_size: u64 = 1_000_000;
        if let Some(result) = mine_pow_batch(event, difficulty, start, batch_size) {
            return result;
        }
        start += batch_size;
    }
}

mine_pow_batch — the batch interface

For callers who need control over when to stop or how to distribute work across threads or web workers:

/// Try to mine proof of work over a bounded range of nonces.
///
/// Searches nonces from `start` to `start + count - 1`. Returns
/// `Some(HashedEvent)` if a nonce producing at least `difficulty`
/// leading zero bits is found, or `None` if the entire range is
/// exhausted without a match.
///
/// # Parallelization
///
/// To distribute work across N workers, give each worker a
/// non-overlapping range: worker *i* calls
/// `mine_pow_batch(event, difficulty, i * chunk, chunk)`.
/// The first worker to return `Some` wins; the rest can be cancelled
/// by simply not issuing further batches.
pub fn mine_pow_batch(
    event: &OwnedEvent,
    difficulty: u8,
    start: u64,
    count: u64,
) -> Option<HashedEvent> {
    let difficulty_str = difficulty.to_string();
    let mut tags = event.tags.clone();
    tags.0.push(Tag::new("nonce", ["0", &difficulty_str]));
    let nonce_idx = tags.0.len() - 1;

    let end = start.saturating_add(count);
    for nonce in start..end {
        tags.0[nonce_idx].0[1] = nonce.to_string();

        let canonical = serde_json::json!([
            0,
            event.pubkey.to_hex(),
            event.created_at,
            event.kind,
            &tags,
            &event.content,
        ])
        .to_string();

        let id: [u8; 32] = Sha256::digest(canonical.as_bytes()).into();

        if get_leading_zero_bits(&id) >= difficulty {
            return Some(HashedEvent {
                content: event.content.clone(),
                kind: event.kind,
                tags,
                created_at: event.created_at,
                pubkey: event.pubkey,
                id,
            });
        }
    }

    None
}

The batch function clones the event's tags once, appends a placeholder nonce tag, then mutates the nonce value in place on each iteration. The canonical JSON is rebuilt every iteration — the nonce string changes each time, so the serialization must too — but the tag vector itself is reused rather than reallocated.

The returned HashedEvent includes the winning nonce tag in its tags. From there it slots into the normal event pipeline: call .sign() to produce a full Event ready for the wire.

Methods on OwnedEvent

For callers who prefer the method style, OwnedEvent delegates to the free functions:

impl OwnedEvent {
    /// Mine proof of work, blocking until a valid nonce is found.
    ///
    /// See [`mine_pow`] for details.
    pub fn mine_pow(&self, difficulty: u8) -> HashedEvent {
        mine_pow(self, difficulty)
    }

    /// Try to mine proof of work over a bounded range of nonces.
    ///
    /// See [`mine_pow_batch`] for details.
    pub fn mine_pow_batch(
        &self,
        difficulty: u8,
        start: u64,
        count: u64,
    ) -> Option<HashedEvent> {
        mine_pow_batch(self, difficulty, start, count)
    }
}

Usage patterns

The split between mine_pow and mine_pow_batch keeps the library code simple while supporting a range of caller strategies:

Blocking single-threaded — the common case. event.mine_pow(20) blocks until it finds a valid nonce and returns the HashedEvent.

Batched with cancellation — a UI that wants to let the user abort. The caller loops over event.mine_pow_batch(20, cursor, 100_000), incrementing cursor by 100,000 each round. Between rounds it checks whether the user pressed cancel.

Parallel native threads — each of N threads gets a non-overlapping chunk of the nonce space. The first thread to return Some wins; the rest are abandoned.

WASM web workers — the main thread posts a batch range to a worker via postMessage. The worker calls mine_pow_batch, posts the result back. To cancel, the main thread simply stops posting new batches. No shared memory, no atomics, no platform-specific API in the library.

Validation — a relay checking incoming events writes event.get_pow() >= 20. The method works on both HashedEvent and Event.

What's next

The next chapter introduces filters — the query language clients use to ask relays for events matching a set of criteria.