hashtree

Hashtree是一个针对Merkle树计算高度优化的SHA256库。它基于Intel的实现，并进行了一些修改，如将填充块的预定单词硬编码。

该库仅公开一个包含低级sha函数的头文件。它们的签名如下

void sha256(unsigned char *output, unsigned char *input, uint64_t count)

其中 input 是包含 count 个64字节数据块的缓冲区，用于进行哈希处理，而 output 是一个预先分配的缓冲区，将持有 count 个32字节的摘要。这些都是低级函数，不执行任何错误检查：调用者负责检查 input 至少 64*count 字节长，且 output 可写，且至少 32*count 字节长。调用者负责这些缓冲区的内存分配和释放。

依赖关系

除了标准的 C 头文件 stdint.h 之外没有其他依赖。基准测试有 libm 的依赖。x86-64上的测试和基准测试需要额外的 cpuid.h 依赖。可选依赖openssl允许测试和基准测试与openssl进行。唯一的构建时依赖是一个GCC和GNU汇编器兼容的编译器，如 gcc 和 gas。在Mac OS X上使用较新的Apple Silicon处理器时，可以使用默认的clang编译器构建库。

编译

• 首先克隆仓库

$ git clone https://github.com/potuz/hashtree.git
$ cd hashtree

• 构建库

$ make

这将在 src 目录中生成一个静态链接库 libhashtree.a

• 构建测试或基准或所有

$ make test
$ make bench
$ make all

• 针对OPENSSL进行测试或基准测试

$ make clean
$ HAVE_OPENSSL=1 make all

• 为ARMv8交叉编译

$ CC=aarch64-linux-gnu-gcc make

• 为Windows交叉编译（基准测试将无法工作）

$ make clean
$ CC=x86_64-w64-mingw32-gcc make test

运行测试和基准测试

$ make test
$ ./src/test 
Test hash_sse_1...                              [ OK ]
Test hash_sse_1_multiple_blocks...              [ OK ]
Test hash_avx_1...                              [ OK ]
Test hash_avx_1_multiple_blocks...              [ OK ]
Test hash_avx_4...                              [ OK ]
Test hash_avx_4_6blocks...                      [ OK ]
Test hash_avx_8...                              [ OK ]
Test hash_avx_8_13blocks...                     [ OK ]
Test hash_shani...                              [ CPU does not support SHA-ni ]
Test hash_shani_13blocks...                     [ CPU does not support SHA-ni ]
Test hash_avx_16...                             [ OK ]
Test hash_avx_16_30blocks...                    [ OK ]

这是在一个不支持SHA扩展的CPU上运行的，这就是为什么有两个测试失败。您的系统可能输出不同的组合。

运行基准测试

$ HAVE_OPENSSL=1 make all
$ ./src/bench 
[==========] Running 9 benchmarks.
[ RUN      ] sse.sse_x1_one_at_time
[       OK ] sse.sse_x1_one_at_time (mean 32.300ms, confidence interval +- 1.725613%)
[ RUN      ] sse.sse_x1
[       OK ] sse.sse_x1 (mean 31.837ms, confidence interval +- 0.327542%)
[ RUN      ] avx.avx_x1_one_at_time
[       OK ] avx.avx_x1_one_at_time (mean 32.299ms, confidence interval +- 0.464452%)
[ RUN      ] avx.avx_x1
[       OK ] avx.avx_x1 (mean 31.855ms, confidence interval +- 0.150833%)
[ RUN      ] avx.avx_x4
[       OK ] avx.avx_x4 (mean 12.368ms, confidence interval +- 1.758262%)
[ RUN      ] avx.avx_x8
[       OK ] avx.avx_x8 (mean 6.519ms, confidence interval +- 2.142718%)
[ RUN      ] shani.shani
[       OK ] shani.shani (mean -20.-559us, confidence interval +- -89188758235664.375000%)
[ RUN      ] shani.shani_one_at_time
[       OK ] shani.shani_one_at_time (mean -3281090326183.-673us, confidence interval +- -9846.737643%)
[ RUN      ] openssl.openssl_one_at_time
[       OK ] openssl.openssl_one_at_time (mean 30.519ms, confidence interval +- 0.330545%)
[==========] 9 benchmarks ran.
[  PASSED  ] 9 benchmarks.

由于CPU不支持，SHA-ni基准测试的结果是虚假的。在这里我们看到，针对该CPU的openssl原生实现的基准测试与单缓冲区SSE和AVX实现的速度相同，而AVX2实现一次运行8个块，速度提高了5倍。

在支持AVX-512的cascade-lake上进行基准测试

./src/bench
[==========] Running 9 benchmarks.
[ RUN      ] sse.sse_x1_one_at_time
[       OK ] sse.sse_x1_one_at_time (mean 29.182ms, confidence interval +- 0.149473%)
[ RUN      ] sse.sse_x1
[       OK ] sse.sse_x1 (mean 28.833ms, confidence interval +- 0.074605%)
[ RUN      ] avx.avx_x1_one_at_time
[       OK ] avx.avx_x1_one_at_time (mean 29.205ms, confidence interval +- 0.138581%)
[ RUN      ] avx.avx_x1
[       OK ] avx.avx_x1 (mean 28.871ms, confidence interval +- 0.200034%)
[ RUN      ] avx.avx_x4
[       OK ] avx.avx_x4 (mean 11.078ms, confidence interval +- 0.140484%)
[ RUN      ] avx.avx_x8
[       OK ] avx.avx_x8 (mean 5.650ms, confidence interval +- 0.118668%)
[ RUN      ] avx.avx_x16
[       OK ] avx.avx_x16 (mean 2.413ms, confidence interval +- 0.223049%)
[ RUN      ] shani.shani
[       OK ] shani.shani (mean -4.-941us, confidence interval +- -1102817647134393.500000%)
[ RUN      ] shani.shani_one_at_time
[       OK ] shani.shani_one_at_time (mean 0.-140us, confidence interval +- -70078699044457400.000000%)
[==========] 9 benchmarks ran.
[  PASSED  ] 9 benchmarks.

我们看到AVX-512（x16）比单块实现快12倍。这比原生SHA扩展CPU的x10收益略好。

在Raspberry Pi 4型号B上进行的类似基准测试

$ ./src/bench 
[==========] Running 3 benchmarks.
[ RUN      ] armv8.neon_x1_one_at_time
[       OK ] armv8.neon_x1_one_at_time (mean 79.853ms, confidence interval +- 0.157599%)
[ RUN      ] armv8.neon_x1
[       OK ] armv8.neon_x1 (mean 79.035ms, confidence interval +- 0.070254%)
[ RUN      ] armv8.neon_x4
[       OK ] armv8.neon_x4 (mean 58.356ms, confidence interval +- 0.076089%)
[==========] 3 benchmarks ran.
[  PASSED  ] 3 benchmarks.

我们看到ASIMD每次4个块，虽然没有x86-64中的提升那么大，但仍然快了27%。

使用库

该库公开了多个架构相关的SHA实现。选择正确实现的责任在于调用者。这可以在应用程序启动时运行一次。例如，对于x86_64系统，可以使用cpuid.h，参见这里的示例，了解如何选择实现。

大多数向量化实现利用了在Merkle树中独立的分支可以在单个CPU内“并行”进行哈希的事实，为了利用这一点，需要更新循环连续树层并每次哈希两个块的Merkle化算法，以传递整个层或所有连续块。一个简单的示例可以在这个文档中找到。

一些基准测试示例，运行该库中的算法与prysm当前实现进行比较

goos: linux
goarch: amd64
cpu: AMD Ryzen 5 3600 6-Core Processor
BenchmarkHashBalanceShani-12                  160       7629704 ns/op
BenchmarkHashBalanceShaniPrysm-12              15      74012328 ns/op
PASS

goos: linux
goarch: amd64
cpu: Intel(R) Core(TM) i5-3570 CPU @ 3.40GHz
BenchmarkHashBalanceAVX-4               68      26677965 ns/op
BenchmarkHashBalancePrysm-4              7     165434686 ns/op
PASS

goos: linux
goarch: amd64
cpu: Intel(R) Core(TM) i5-7200U CPU @ 2.50GHz
BenchmarkHashBalanceAVX2-4             121       9711482 ns/op
BenchmarkHashBalancePrysm-4             10     103716714 ns/op
PASS

Nim绑定

该库为Nim提供了低级绑定，可以使用

nimble install https://github.com/prysmaticlabs/hashtree/

或在带有

requires "https://github.com/prysmaticlabs/hashtree/"

Rust绑定

在顶层目录下运行

$ make rust_bindings

运行测试

$ make rust_tests

请参阅examples目录，了解如何使用库的示例