SpectreX

SpectreX is a versatile CPU mining algorithm library used by the Spectre On Rust full-node daemon.

Overview

SpectreX features the AstroBWTv3 algorithm, a proof-of-work (PoW) system based on the Burrows-Wheeler transform (BWT). This version of AstroBWTv3 is completely written in Rust, without any external C dependencies, relying solely on various Rust crates.

Hashing Function

The proof-of-work calculation involves a series of sequential hashing functions to form the final hash:

• Step 1: Calculate sha256 of the input data.
• Step 2: Expand data using Salsa20.
• Step 3: Encrypt data with RC4 based on the output from step 2.
• Step 4: Compute an initial FNV-1a hash of the result from step 3.
• Step 5: Apply a branchy loop using RC4 stream encryption on the data from step 4.
• Step 6: Build and sort a Suffix Array with the result from step 5.
• Step 7: Calculate the final sha256 of the data from step 6.

Improvements

The original algorithm utilized the SA-IS sorting algorithm. There exists an enhanced one with SACA-K for induced sorting, improving the linear-time complexity to be in-place for constant alphabets. However, this remains a single-core variant. The pSACAK algorithm offers a fast, linear-time, in-place parallel solution that utilizes multi-core machines. However, testing revealed that it still requires optimization. It is fully compatible with the original AstroBWTv3 Suffix Array.

Our AstroBWTv3 implementation is using cdivsufsort as it is still the fastest single threaded Suffix Array construction implementation.

There are numerous opportunities to enhance the computation of AstroBWTv3 hashes, including:

• Replacing most steps with highly optimized inline assembler code on CPU.
• Partitioning the Suffix Array and offloading sorting to GPUs to significantly boost performance.

We encourage developers to optimize individual calculation steps to evolve the algorithm over time and mature the codebase.

Usage

To include SpectreX in your project dependencies, just run the command cargo add spectrex. Here's a straightforward example:

use spectrex::astrobwtv3;

fn main() {
    let hash_in: [u8; 32] = [88, 101, 183, 41, 212, 156, 190, 48, 230, 97, 94, 105, 177, 86, 88, 84, 60, 239, 203, 124, 63, 32, 160, 222, 34, 141, 50, 108, 138, 16, 90, 230];
    let hash_out = astrobwtv3::astrobwtv3_hash(&hash_in);
    println!("hash_out: {:?}", hash_out);
}

Tests

Below is a basic computation test designed to ensure the accuracy of computed hashes across various byte orders. You can execute it using cargo test, and upon successful completion, it will display the following output:

running 1 test
test astrobwtv3_hash_10 ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.54s

Benchmarks

Included is a simple computation benchmark using Criterion. This benchmark helps verify any performance improvements or degradations if any calculation steps have been modified. You can run it using cargo bench, and it will return the following results:

astrobwtv3              time:   [8.8912 ms 9.0648 ms 9.2387 ms]
                        change: [-7.8592% -4.5050% -1.1622%] (p = 0.01 < 0.05)
                        Performance has improved.
Found 4 outliers among 100 measurements (4.00%)
  4 (4.00%) high mild