kheavyhash 0.1.0

Python implementation of the kHeavyHash Proof-of-Work algorithm

kheavyhash

A Python implementation of the kHeavyHash Proof-of-Work algorithm, used by the Zork Network, Kaspa network and related cryptocurrencies.

Overview

kHeavyHash is a "Keccak-Matrix-Keccak" sandwich algorithm that combines:

• cSHAKE256 hashing (customizable SHAKE from SHA-3/Keccak family)
• 64×64 matrix multiplication over GF(16) (4-bit arithmetic)
• xoshiro256++ pseudorandom number generation for matrix seeding

This package provides a pure Python implementation with optional performance extensions via Cython/C.

⚠️ Important Disclaimer: This implementation is not optimized for mining and is intended for basic usage, testing, and educational purposes only. For production mining operations, please use optimized implementations specifically designed for that purpose. This reference implementation prioritizes correctness and clarity over performance.

Installation

Basic Installation

pip install kheavyhash

This installs the pure Python implementation with pycryptodome for cSHAKE256 support.

Development Installation

git clone https://github.com/blkutil/kheavyhash.git
cd kheavyhash
pip install -e ".[dev]"

Building with C Extension (Optional)

The package provides a native C implementation that is automatically built if Cython is available. If Cython is not available or the build fails, the package gracefully falls back to the pure Python implementation.

To ensure the C extension is built, install with the cython extra:

pip install -e ".[cython]"

Note: The package will work correctly even if the C extension cannot be built. The pure Python implementation provides identical results, just with lower performance. The sections below describe how the C extension and Python fallback interact.

Usage

Basic Usage

from kheavyhash import kheavyhash

# Input: 80-byte work order
# Format: [32 bytes PrePowHash][8 bytes Timestamp][32 bytes padding][8 bytes Nonce]
work_order = bytes(80)  # Your mining work order

# Compute kHeavyHash
result = kheavyhash(work_order)
# Returns: 32-byte hash digest
print(result.hex())

Constructing a Work Order

from kheavyhash import kheavyhash

# This example uses the first hardcoded test vector from tests/test_vectors.py.
# Using a real test vector makes it easy to verify that your environment
# matches the reference implementation.

# Full 80-byte work order (hex-encoded):
#   PrePowHash (32 bytes)
#   Timestamp  (8 bytes, little-endian)
#   Padding    (32 bytes of zeros)
#   Nonce      (8 bytes, little-endian)
input_hex = (
    "0ad86e9bef09726cdc75913e44ec96521391c7ceb2aae3c633f46a94bf4d2546"
    "3e6bd36895010000"
    "0000000000000000000000000000000000000000000000000000000000000000"
    "39fd069384065157"
)

# Convert to bytes and check length
work_order = bytes.fromhex(input_hex)
assert len(work_order) == 80

# Compute hash and compare with expected result from the test vector
result = kheavyhash(work_order)
expected_hex = "e097f2e49b05978b2b5b387a46798a0c463082b6546f24afcc8aae4fe68b702f"
assert result.hex() == expected_hex
print("kHeavyHash(work_order) =", result.hex())

Fallback Mechanism

The package automatically handles fallback between implementations:

from kheavyhash import kheavyhash

# This will use the Cython extension if available,
# otherwise fall back to pure Python
result = kheavyhash(work_order)

You can check which implementation is being used:

try:
    from kheavyhash._c_ext import kheavyhash
    print("Using optimized Cython extension")
except ImportError:
    from kheavyhash.kheavyhash_python import kheavyhash
    print("Using pure Python implementation")

Algorithm Details

Input Format

The algorithm expects exactly 80 bytes of input, structured as follows:

Field	Size	Offset	Description
PrePowHash	32 bytes	0–31	Precomputed hash of block header (timestamp=0, nonce=0)
Timestamp	8 bytes	32–39	UNIX time, little-endian
Padding	32 bytes	40–71	All zero bytes (reserved)
Nonce	8 bytes	72–79	Mining nonce, little-endian

Algorithm Steps

The kHeavyHash algorithm implements a "Keccak-Matrix-Keccak" sandwich:

1. Initial Hash (Keccak)

   • Hash the 80-byte work order using cSHAKE256 with customization string "ProofOfWorkHash".
   • Produces a 32-byte digest.

2. Matrix Generation (Heavy Step)

   • Seed the xoshiro256++ PRNG from the PrePowHash field (first 32 bytes of the work order), interpreted as four little‑endian 64‑bit words.
   • Generate a 64×64 matrix over GF(16) (each element is a 4-bit nibble, 0–15).
   • Each uint64 from the PRNG provides 16 matrix elements (4 bits each).
   • The matrix must have full rank (rank = 64). If not, regenerate with modified state until full‑rank.

3. Vector Initialization

   • Extract 64 nibbles from the 32-byte initial hash: each byte yields two 4-bit values.
   • High nibble (upper 4 bits) first, then low nibble (lower 4 bits).
   • Forms a 64-element vector over GF(16).

4. Matrix-Vector Multiplication

   • Multiply the 64×64 matrix by the 64-element vector over GF(16).
   • For each row: compute dot product, then right-shift by 10 bits to scale.
   • Result is a 64-element vector of GF(16) values.

5. Digest Reconstruction

   • Combine pairs of nibbles from the result vector into bytes: (nibble[2*i] << 4) | nibble[2*i+1].
   • XOR this 32-byte result with the original 32-byte initial hash from step 1.

6. Final Hash (Keccak)

   • Hash the XOR result using cSHAKE256 with customization string "HeavyHash".
   • Produces a 32-byte digest.

7. Byte Reversal

   • Reverse the bytes of the final hash to produce the output.
   • This is the final 32-byte kHeavyHash result.

GF(16) Arithmetic

The algorithm operates over GF(16), a finite field with 16 elements (0-15). Arithmetic is performed modulo 16:

• Addition: (a + b) % 16
• Multiplication: (a * b) % 16
• Matrix operations use standard linear algebra over this field

Matrix Full-Rank Requirement

The generated matrix must be invertible (full rank = 64). This ensures the matrix-vector multiplication is a meaningful transformation. The implementation:

• Generates a candidate matrix using the PRNG
• Computes rank using Gaussian elimination over GF(16)
• If rank < 64, modifies the seed and regenerates
• Repeats until a full-rank matrix is found (up to 1000 attempts)

Performance

Pure Python Implementation

The default implementation is 100% pure Python:

• Uses pycryptodome for cSHAKE256 (NIST SP 800-185).
• Implements xoshiro256++ PRNG in Python.
• Matrix operations use Python lists and loops.
• Suitable for verification and testing.
• Always available – this is the fallback if the C extension cannot be built.

C / Cython Extension (Optional)

The package automatically attempts to build a C/Cython extension during installation:

• If Cython and a C compiler are available, the extension is built.
• If dependencies are missing or the build fails, installation continues with pure Python only.
• No build errors occur – the package gracefully falls back.

The optional C/Cython extension provides:

• Optimized matrix-vector multiplication using C loops.
• Reduced Python overhead for the heavy computation step.
• Automatic runtime fallback if the extension is unavailable (ImportError handling).

Performance improvement depends on your use case, but typically provides a multi‑x speedup for the heavy matrix operations compared to pure Python.

Testing

Run the test suite:

pytest

With coverage:

pytest --cov=src/kheavyhash --cov-report=html

The test suite includes:

• Hardcoded test vectors for algorithm validation (requires vectors from Go implementation - see scripts/readme_test_vectors.md)
• Edge cases: all zeros, all ones, various patterns
• Determinism tests: same input produces same output
• Optional Go binary comparison: compares output with Go reference implementation if available locally

IMPORTANT: To fully validate correctness, you must obtain test vectors from the Go reference implementation. See scripts/readme_test_vectors.md for instructions.

Running Specific Tests

# Run all tests
pytest

# Run only basic functionality tests
pytest tests/test_kheavyhash.py::TestKHeavyHash

# Run Go binary comparison (requires Go binary in PATH)
pytest tests/test_kheavyhash.py::TestGoBinaryComparison

Large-Scale Comparison Testing

For comprehensive validation, you can run a large-scale comparison test (e.g., 1000 iterations) that compares C, Python, and Go implementations:

# Build C test program and Go wrapper
make

# Run comparison (default: 1000 tests)
make compare

# Or run directly with custom number of tests
./scripts/compare_implementations.sh 1000

This script:

• Generates random test cases
• Compares C, Python, and Go implementations
• Reports any mismatches
• Useful for validating correctness across many inputs

Publishing

This project uses PyPI Trusted Publishing with automatic attestation support.

Trusted Publisher Setup

To enable publishing, configure a Trusted Publisher on PyPI:

1. Go to your project's PyPI settings: https://pypi.org/manage/project/kheavyhash/settings/publishing/

2. Add a new Trusted Publisher with:

   • Publisher: GitHub
   • Owner: blkutil
   • Repository name: kheavyhash
   • Workflow filename: .github/workflows/publish.yml
   • Environment name: pypi (optional, but recommended for security)

3. The workflow will automatically:

   • Use OIDC for authentication (no API tokens needed)
   • Generate and upload attestations automatically
   • Publish on GitHub releases

Attestation Support

The package includes automatic attestation support via PEP 740:

• SLSA Provenance: Attests to the package's source location and build process
• PyPI Publish: Provides verifiable proof the package was published via Trusted Publisher

Attestations are automatically generated and uploaded by pypa/gh-action-pypi-publish - no additional configuration needed.

Development

Project Structure

kheavyhash/
├── src/
│   └── kheavyhash/
│       ├── __init__.py           # Main entry point with fallback logic
│       ├── kheavyhash_python.py  # Pure Python implementation
│       ├── _c_ext.pyx            # Cython bindings for C implementation
│       ├── kheavyhash_core.c     # C implementation of kHeavyHash
│       ├── kheavyhash_core.h     # C header
│       ├── keccak_nano.c         # cSHAKE256 (keccak) implementation
│       └── keccak_nano.h         # cSHAKE256 header
├── tests/
│   ├── test_kheavyhash.py           # High-level tests
│   ├── test_c_implementation.py     # C implementation tests
│   ├── test_native_implementation.py # Python implementation tests
│   └── test_vectors.py              # Hardcoded test vectors
├── scripts/
│   ├── test_kheavyhash_c.c          # C test runner source
│   ├── compare_implementations.sh   # C/Python/Go comparison harness
│   ├── generate_test_vectors.go     # Go-based test vector generator
│   ├── generate_comparison_tests.go # Go-based random test generator
│   ├── go_kheavyhash_wrapper.go     # Go wrapper binary
│   └── readme_test_vectors.md       # Test vector generation docs
├── pyproject.toml                    # PEP 621 project metadata
├── setup.py                          # Cython/C build configuration
└── README.md                         # This file

Code Standards

This project follows:

• Semantic Versioning (SemVer) - version numbers follow MAJOR.MINOR.PATCH
• Conventional Commits - commit messages use feat:, fix:, docs:, test:, chore:, etc.
• PEP 621 - modern Python project metadata in pyproject.toml
• FIRST principles - tests are Fast, Independent, Repeatable, Self-Validating, Timely
• Google-style docstrings - all functions have comprehensive documentation

Building from Source

# Clone repository
git clone https://github.com/blkutil/kheavyhash.git
cd kheavyhash

# Install in development mode
pip install -e ".[dev]"

# Build Cython extension (optional)
pip install -e ".[cython]"
python setup.py build_ext --inplace

# Run tests
pytest

Contributing

Contributions are welcome! Please:

1. Fork the repository
2. Create a feature branch
3. Make your changes with tests
4. Ensure all tests pass: pytest
5. Follow conventional commits format
6. Submit a pull request

References

• Technical Overview - Detailed algorithm specification
• Go Reference Implementation - Canonical Go implementation
• TypeScript Reference Implementation - TypeScript port

Related Networks

• Kaspa Network - Uses kHeavyHash as its Proof-of-Work algorithm
• Zork Network - Uses kHeavyHash for mining

License

MIT License - see LICENSE file for details.

Organization

blkutil - github.com/blkutil/kheavyhash

Support

For issues, questions, or contributions, please use the GitHub Issues page.