Proof-of-Hashing

A Novel HMAC-Based Cryptographic Puzzle with Dual-Purpose Output

A new paradigm for computational proof-of-work systems that produces a cryptographic key that simultaneously demonstrates computational work and provides message authentication capability.

📄 Read the Paper 🔗 View on GitHub

What is Proof-of-Hashing?

Proof-of-Hashing (PoH) extends traditional proof-of-work systems by leveraging HMAC with key variation instead of nonce iteration.

🔐 Dual-Purpose Output

Unlike traditional PoW systems where the nonce is discarded after verification, Proof-of-Hashing produces a cryptographic key that:

  • Proves computational work was performed
  • Can be reused to authenticate future messages
  • Is cryptographically bound to the original challenge

⚡ Efficient & Scalable

The algorithm maintains comparable computational characteristics to traditional methods while offering enhanced functionality:

  • Configurable difficulty levels
  • Asynchronous solving for non-blocking operations
  • Fast verification with O(1) complexity

🛡️ Security Properties

Built on proven cryptographic primitives with formal security guarantees:

  • Pre-computation Resistance (Theorem 1): Keys cannot be pre-computed
  • Message Binding (Theorem 2): Keys are cryptographically bound to challenges
  • No Shortcuts (Theorem 3): No algorithm can find valid keys faster than expected
  • Collision Resistance (Theorem 4): Finding multiple valid keys requires independent work
  • Unpredictability (Theorem 5): Valid keys are unpredictable before computation

The Innovation

How Proof-of-Hashing differs from traditional proof-of-work systems

Traditional Proof-of-Work

In systems like Bitcoin or Hashcash, a nonce is varied until the hash meets the difficulty requirement:

SHA256(block_header || nonce) < target
// nonce is discarded after verification

Limitations:

  • The nonce cannot authenticate the message
  • The nonce cannot be reused for cryptographic purposes
  • The computational effort produces a single-use proof

Proof-of-Hashing

Instead of varying a nonce, Proof-of-Hashing searches for an HMAC key:

HMAC-SHA256(key, message)[0:D] = 0^D
// key can be reused for authentication!

Advantages:

  • The key demonstrates computational work
  • The key can authenticate the message (HMAC)
  • The key is cryptographically bound to the message
  • The key can remain private (unlike public nonces)

Comparison

Approach Variable Output Reusable Auth Capable
Hashcash Nonce Hash No No
Bitcoin PoW Nonce Hash No No
Scrypt PoW Nonce Hash No No
Proof-of-Hashing Key Key + Hash Yes Yes

Academic Paper

The theoretical foundations, security analysis, and experimental results are documented in a formal academic paper.

Proof-of-Hashing: A Novel HMAC-Based Cryptographic Puzzle with Dual-Purpose Output

This paper introduces Proof-of-Hashing (PoH), a novel cryptographic puzzle mechanism that extends traditional proof-of-work systems by leveraging HMAC (Hash-based Message Authentication Code) with key variation instead of nonce iteration. Unlike conventional approaches where the computational effort produces only a validity proof, the proposed method yields a cryptographic key that can be subsequently reused for message authentication.

Authors

CHPL Research

Contact

francesco@chpl.it

Date

January 2026

Version

1.0.0

Keywords

Proof-of-Work, HMAC, Cryptographic Puzzles

Pages

20 pages

📥 Download PDF 📝 View LaTeX Source 🔗 View Repository

Paper Contents

  • Abstract: Overview of the Proof-of-Hashing concept and contributions
  • Introduction: Context and motivation for the research
  • Related Work: Comprehensive review of existing PoW mechanisms (Hashcash, Bitcoin, Memory-Hard Functions, HMAC)
  • Algorithm: Formal definition, pseudocode, computational complexity, and variants
  • Security Analysis: Formal threat model, 5 security theorems with proofs, attack resistance analysis
  • Implementation: Reference implementation in Node.js (synchronous and asynchronous)
  • Experimental Results: Performance benchmarks on Apple M4 and Intel i9-12900K, statistical validation
  • Applications: Bot protection, anti-spam, DDoS mitigation, blockchain consensus
  • Discussion: Advantages, limitations, and future work
  • Appendices: Formal definitions, probability analysis, reference implementation

Applications

Practical use cases for Proof-of-Hashing technology

🤖 Bot Protection

Protect web applications from automated attacks by requiring clients to solve cryptographic puzzles before accessing resources.

Available View CHPL System →

📧 Anti-Spam

Require email senders to solve puzzles, making mass mailing economically infeasible while remaining negligible for legitimate users.

🛡️ DDoS Mitigation

Use computational puzzles to rate-limit requests and prevent distributed denial-of-service attacks.

⛓️ Blockchain Consensus

Potential application in blockchain systems where the discovered key could serve dual purposes in consensus and authentication.

Technical Details

Algorithm specification and implementation

Problem Definition

Given a message M and a difficulty parameter D, find a key K such that:

HMAC-SHA256(K, M)[0:D] = 0^D

where [0:D] denotes the first D hexadecimal characters and 0^D represents a string of D zeros.

Difficulty Levels

Level Leading Zeros Avg. Attempts Est. Time Use Case
Low 3 4,096 ~50ms High traffic sites
Medium 4 65,536 ~500ms General purpose
High 5 1,048,576 ~5s Sensitive operations
Very High 6 16,777,216 ~60s Critical protection