hash-zig

A pure Zig implementation of Generalized XMSS hash-based signatures with 100% Rust compatibility. This library implements the complete GeneralizedXMSS signature scheme based on the framework from this paper, matching the hash-sig Rust implementation exactly.

⚠️ Prototype Status: This is a prototype implementation for research and development purposes. Use at your own risk.

🌟 Features

✅ 100% Rust Compatibility

• Complete GeneralizedXMSS Implementation: Full signature scheme matching Rust implementation exactly
• Identical API: Same function signatures and behavior as Rust version
• Cross-Implementation Interop: Signatures can be verified exactly between Rust and Zig
• Random Parameter Generation: Uses truly random PRF keys and parameters (matching Rust behavior)
• Top-Bottom Tree Architecture: Implements the complete Merkle tree construction with parallel processing
• Secret Key Management: Full support for activation intervals and key advancement
• Verified Compatibility: Comprehensive test suite ensures identical behavior with Rust implementation
• Proper Encapsulation: Private fields with controlled access methods, matching Rust's security model

🔐 Cryptographic Components

• Poseidon2 Hash Function: KoalaBear field with Montgomery arithmetic (via zig-poseidon)
• ShakePRFtoF: SHAKE128-based PRF for key derivation with domain separation
• TargetSum Encoding: Incomparable binary encoding with randomness
• Merkle Tree Construction: Complete tree building with parallel processing support
• Hash Chain Computation: Full chain computation matching Rust implementation

🚀 Performance & Quality

• 128-bit Classical / 64-bit Quantum Security: Post-quantum security parameters
• Multiple Lifetimes: Support for 2^8, 2^18, and 2^32 signatures per keypair
• Memory Safe: Proper memory management with no leaks
• Pure Zig: Minimal dependencies, fully type-safe
• Comprehensive Testing: Full test suite with compatibility verification
• Built-in Benchmark Suite: Performance comparison and cross-compatibility testing with Rust implementation

📋 Table of Contents

• Installation
• Quick Start
• Architecture
• API Reference
• Testing
• Performance
• Built-in Benchmark Suite
• Contributing
• License

🚀 Installation

Using Zig Package Manager

Add to your build.zig.zon:

.{
    .name = "my_project",
    .version = "0.1.0",
    .dependencies = .{
        .@"hash-zig" = .{
            .url = "https://github.com/ch4r10t33r/hash-zig/archive/refs/tags/v2.0.0.tar.gz",
            .hash = "1220...", // Will be generated by zig build
        },
        .@"zig-poseidon" = .{
            .url = "https://github.com/blockblaz/zig-poseidon/archive/refs/heads/main.tar.gz",
            .hash = "1220...", // Will be generated by zig build
        },
    },
}

In your build.zig:

const hash_zig_dep = b.dependency("hash-zig", .{
    .target = target,
    .optimize = optimize,
});
const zig_poseidon_dep = b.dependency("zig_poseidon", .{
    .target = target,
    .optimize = optimize,
});

exe.root_module.addImport("hash-zig", hash_zig_dep.module("hash-zig"));
exe.root_module.addImport("poseidon", zig_poseidon_dep.module("poseidon"));

Manual Installation

git clone https://github.com/ch4r10t33r/hash-zig.git
cd hash-zig
zig build test

⚡ Quick Start

const std = @import("std");
const hash_zig = @import("hash-zig");

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    // Initialize the GeneralizedXMSS signature scheme
    var scheme = try hash_zig.GeneralizedXMSSSignatureScheme.init(allocator, .lifetime_2_8);
    defer scheme.deinit();

    // Generate a keypair with activation parameters
    const keypair = try scheme.keyGen(0, 256); // activation_epoch=0, num_active_epochs=256
    defer keypair.secret_key.deinit();

    // Sign a message
    const message = [_]u8{0x42} ** 32;
    const signature = try scheme.sign(keypair.secret_key, 0, message);
    defer signature.deinit();

    // Verify the signature
    const is_valid = try scheme.verify(&keypair.public_key, 0, message, signature);
    std.debug.print("Signature valid: {}\n", .{is_valid});
}

💡 Performance Tip: For testing with larger lifetimes (2^18, 2^32), build with zig build -Doptimize=ReleaseFast for significantly better performance. Remember this is prototype software.

🏗️ Architecture

Core Components

GeneralizedXMSSSignatureScheme

The main signature scheme implementation that provides:

• keyGen(activation_epoch, num_active_epochs) - Generate keypairs
• sign(secret_key, epoch, message) - Sign messages
• verify(public_key, epoch, message, signature) - Verify signatures

Data Structures

• GeneralizedXMSSPublicKey: Contains root and parameters (private fields with controlled access)
• GeneralizedXMSSSecretKey: Contains PRF key, parameters, and tree state (private fields with controlled access)
• GeneralizedXMSSSignature: Contains Merkle path, randomness, and hashes (private fields with controlled access)

Cryptographic Primitives

• ShakePRFtoF: SHAKE128-based PRF for key derivation
• Poseidon2: KoalaBear field hash function for tree construction
• TargetSum Encoding: Binary encoding with randomness

Lifetime Support

Lifetime	Signatures	Use Case	Performance Note
2^8	256	Testing, short-term keys	Fast in both debug and optimized builds
2^18	262,144	Medium-term applications	Requires optimized build for reasonable performance
2^32	4,294,967,296	Long-term, high-volume	Requires optimized build for reasonable performance

📖 API Reference

Key Generation

// Generate a keypair for lifetime 2^8
const keypair = try scheme.keyGen(0, 256);

// Access the public key (using controlled access methods)
const public_key = keypair.public_key;
const root = public_key.getRoot();
std.debug.print("Root: {}\n", .{root.value});

// Access the secret key (using controlled access methods)
const secret_key = keypair.secret_key;
const activation_interval = secret_key.getActivationInterval();
const prepared_interval = secret_key.getPreparedInterval(8);

Signing and Verification

// Sign a message at epoch 0
const message = [_]u8{0x42} ** 32;
const signature = try scheme.sign(secret_key, 0, message);

// Verify the signature
const is_valid = try scheme.verify(&public_key, 0, message, signature);

// Access signature components (using controlled access methods)
const path = signature.getPath();
const rho = signature.getRho();
const hashes = signature.getHashes();

Secret Key Management

// Check if key is active for a given epoch
const activation_interval = secret_key.getActivationInterval();
if (activation_interval.contains(epoch)) {
    // Key is active for this epoch
}

// Check if key is prepared for a given epoch
const prepared_interval = secret_key.getPreparedInterval(log_lifetime);
if (prepared_interval.contains(epoch)) {
    // Key is prepared for this epoch
}

// Advance key preparation (when needed)
try secret_key.advancePreparation(log_lifetime);

🧪 Testing

Run All Tests

# Run comprehensive test suite
zig build test

# Run only Rust compatibility tests
zig build test-rust-compat

# Run specific compatibility tests
zig build test-generalized-xmss-compat
zig build test-shake-prf-compat
zig build test-poseidon2-compat

Test Coverage

• ✅ Unit Tests: Individual component testing
• ✅ Integration Tests: Full signature scheme testing
• ✅ Compatibility Tests: Rust implementation matching (100% verified)
• ✅ Performance Tests: Benchmarking and timing
• ✅ Memory Tests: Leak detection and management
• ✅ Comprehensive Rust Compatibility: Full test suite covering all Rust hash-sig functionality

🚀 Performance

Building for Performance

⚠️ Important: This is a prototype implementation. For larger lifetimes (2^18, 2^32), always use optimized builds, but be aware this is experimental software.

# Optimized build (for testing only - this is prototype software)
zig build -Doptimize=ReleaseFast

# Debug build (for development only)
zig build

Benchmarking

# Run performance benchmarks (prototype software - use at your own risk)
zig build benchmark -Doptimize=ReleaseFast

# Run key generation benchmarks
zig build benchmark-keygen -Doptimize=ReleaseFast

Key generation benchmarks (multiple lifetimes, fixed 256 keys)

The standalone key-generation benchmark compares lifetime configurations while always generating 256 keys for each:

# Debug build (slower, good for development)
zig run scripts/benchmark_keygen.zig -- -i3

# Include lifetime 2^32 as well (can be slower due to larger trees)
zig run scripts/benchmark_keygen.zig -- --include-2-32 -i3

# Recommended for accurate results (prototype software)
zig run scripts/benchmark_keygen.zig -- -i5 -Doptimize=ReleaseFast

What it measures:

• Lifetime 2^8, 2^18, and optionally 2^32
• Always generates 256 keys for apples-to-apples comparison
• Reports average/min/max time and derived keys/second

Example output (abbreviated):

hash-zig Key Generation Benchmark (Multiple Lifetimes)
=======================================================
Iterations per configuration: 3
Include 2^32 lifetime: true
Note: All tests generate 256 keys to compare lifetime performance

Benchmarking lifetime 2^8 (generating 256 keys)
... ✅ 0.01s | ... ✅ 0.02s | ... ✅ 0.01s
📊 Results for lifetime 2^8 (256 keys):
  Average time: 0.01 seconds
  Generation rate: 17,000+ keys/second

Benchmarking lifetime 2^18 (generating 256 keys)
... ✅ 0.05s | ... ✅ 0.05s | ... ✅ 0.05s
📊 Results for lifetime 2^18 (256 keys):
  Average time: 0.05 seconds
  Generation rate: ~5,000 keys/second

Benchmarking lifetime 2^32 (generating 256 keys)
... ✅ 0.21s | ... ✅ 0.21s | ... ✅ 0.21s
📊 Results for lifetime 2^32 (256 keys):
  Average time: 0.21 seconds
  Generation rate: ~1,200 keys/second

Notes:

• 2^32 uses larger internal tree structures and is expected to be slower per key.
• Use -Doptimize=ReleaseFast for realistic throughput numbers.

Performance Characteristics

⚠️ Prototype Performance (ReleaseFast):

• Key Generation (2^8): ~1.1 seconds (230 signatures/second) on M2 MacBook
• Key Generation (2^18): Use optimized build - significantly faster than debug
• Key Generation (2^32): Use optimized build - required for reasonable performance
• Signing: <1ms per signature (279,000 signatures/second)
• Verification: <1ms per signature (23,800,000 verifications/second)
• Memory Usage: Efficient with proper cleanup

Debug Build Performance (Prototype):

• Key Generation (2^8): ~14.8 seconds (17 signatures/second) - much slower
• Signing: <1ms per signature (25,900 signatures/second)
• Verification: <1ms per signature (5,900,000 verifications/second)
• Larger lifetimes: Not recommended for production use (this is prototype software)

Performance Recommendations

⚠️ This is prototype software - use at your own risk

1. Always use -Doptimize=ReleaseFast for testing deployments
2. 2^8 lifetime: Suitable for testing and small-scale applications
3. 2^18 lifetime: Use optimized builds, suitable for medium-term applications
4. 2^32 lifetime: Use optimized builds, suitable for long-term, high-volume applications

🔧 Development

Building

# Build library and examples
zig build

# Build with documentation
zig build -Ddocs

# Run linting
zig build lint

# Run basic usage example (with timing)
zig build example

# Run basic usage example (optimized)
zig build example -Doptimize=ReleaseFast

Project Structure

src/
├── core/           # Core types and parameters
├── hash/           # Hash function implementations
├── prf/            # PRF implementations
├── signature/      # Main signature scheme
├── merkle/         # Merkle tree construction
├── wots/           # Winternitz OTS
└── utils/          # Utility functions

examples/
├── basic_usage.zig                     # Basic usage example with timing
├── test_generalized_xmss_compat.zig    # Main compatibility test
├── test_shake_prf_compatibility.zig    # PRF compatibility test
└── test_poseidon2_compatibility.zig    # Hash function compatibility test

test/
├── performance_test.zig               # Performance benchmarks
└── rust_compatibility_test.zig        # Rust compatibility tests

🤝 Contributing

1. Fork the repository
2. Create a feature branch
3. Make your changes
4. Add tests for new functionality
5. Ensure all tests pass: zig build test
6. Submit a pull request

Development Guidelines

• Follow Zig naming conventions
• Add comprehensive tests for new features
• Ensure Rust compatibility is maintained
• Document public APIs
• Use proper memory management

📄 License

This project is licensed under the Apache License 2.0 - see the LICENSE file for details.

🙏 Acknowledgments

• hash-sig - Rust reference implementation (100% compatible)
• zig-poseidon - Poseidon2 implementation with KoalaBear field support
• Generalized XMSS Paper - Cryptographic framework
• Rust hash-sig compatibility investigation - Detailed compatibility analysis

🔄 Rust Compatibility Status

✅ Fully Compatible Implementation

The Zig implementation has been thoroughly tested and verified to match the Rust hash-sig implementation exactly:

• ✅ Key Generation: Identical behavior with random parameter generation
• ✅ Signing: Same signature generation process and output
• ✅ Verification: Cross-compatible signature verification
• ✅ Secret Key Management: Full support for activation intervals and advancement
• ✅ Tree Construction: Complete Merkle tree building with parallel processing
• ✅ Hash Chain Computation: Identical chain computation algorithm
• ✅ PRF Implementation: ShakePRFtoF with proper domain separation
• ✅ Poseidon2 Integration: KoalaBear field implementation via zig-poseidon

Compatibility Verification

The implementation includes comprehensive tests that verify:

• Identical API behavior with Rust implementation
• Same random parameter generation patterns
• Cross-implementation signature verification
• Memory safety and proper resource management

See the compatibility investigation for detailed analysis and test results.

📞 Support

For questions, issues, or contributions:

• Open an issue on GitHub
• Check the analysis directory for detailed implementation notes
• Review the RUST_COMPATIBILITY.md for compatibility details
• See verification strategy for testing approach