4

我在 Python 中的实现计算了大约 1500 个输入哈希的 merkle 根哈希：

import numpy as np
from binascii import unhexlify, hexlify
from hashlib import sha256

txids = np.loadtxt("txids.txt", dtype=str)

def double_sha256(a, b):
    inp = unhexlify(a)[::-1] + unhexlify(b)[::-1]
    sha1 = sha256(inp).digest()
    sha2 = sha256(sha1).digest()
    return hexlify(sha2[::-1])


def calculate_merkle_root(inp_list):
    if len(inp_list) == 1:
        return inp_list[0]
    out_list = []
    for i in range(0, len(inp_list)-1, 2):
        out_list.append(double_sha256(inp_list[i], inp_list[i+1]))
    if len(inp_list) % 2 == 1:
        out_list.append(double_sha256(inp_list[-1], inp_list[-1]))
    return calculate_merkle_root(out_list)

for i in range(1000):
    merkle_root_hash = calculate_merkle_root(txids)

print(merkle_root_hash)

由于 merkle 根计算了 1000 次，因此一次计算大约需要 5ms：

$ time python3 test.py 
b'289792577c66cd75f5b1f961e50bd8ce6f36adfc4c087dc1584f573df49bd32e'

real    0m5.132s
user    0m5.501s
sys     0m0.133s

如何提高计算速度？这段代码可以优化吗？

到目前为止，我已经尝试在 Python 和 C++ 中展开递归函数。但是，性能并没有提高，大约花了 6 毫秒。

编辑

该文件可在此处获得： txids.txt

编辑 2

由于评论中的建议，我删除了unhexlify和的不必要步骤hexlify。在循环之前，列表准备一次。

def double_sha256(a, b):
    inp = a + b
    sha1 = sha256(inp).digest()
    sha2 = sha256(sha1).digest()
    return sha2

def map_func(t):
    return unhexlify(t)[::-1]
txids = list(map(map_func, txids))

for i in range(1000):
    merkle_root_hash = calculate_merkle_root(txids)
    merkle_root_hash = hexlify(merkle_root_hash[::-1])

现在执行时间约为 4 毫秒：

$ time python3 test2.py 
b'289792577c66cd75f5b1f961e50bd8ce6f36adfc4c087dc1584f573df49bd32e'

real    0m3.697s
user    0m4.069s
sys     0m0.128s
4

2 回答 2

5

我决定从头开始完全实现 SHA-256 并使用SIMD指令集（在此处阅读它们SSE2、AVX2、AVX512）。

因此，我在下面的 AVX2 案例代码的3.5x速度比 OpenSSL 版本7.3x快几倍，比 Python 的hashlib实现快几倍。

我还创建了有关 C++ 版本的相关第二篇文章，请在此处查看。阅读 C++ 帖子以了解有关我的库的更多详细信息，这篇 Python 帖子更高级。

首先提供时间：

simple 3.006
openssl 1.426
simd gen 1 1.639
simd gen 2 1.903
simd gen 4 0.847
simd gen 8 0.457
simd sse2 1 0.729
simd sse2 2 0.703
simd sse2 4 0.718
simd sse2 8 0.776
simd avx2 1 0.461
simd avx2 2 0.41
simd avx2 4 0.549
simd avx2 8 0.521

这simple是与您提供的接近的 hashlib 版本，openssl代表 OpenSSL 版本，其余simd版本是我的 SIMD (SSE2/AVX2/AVX512) 实现。如您所见，AVX2 版本3.5x比OpenSSL版本快7.3x几倍，比原生 Python 的hashlib.

上述时序是在 Google Colab中完成的，因为它们具有相当先进的 AVX2 CPU。

在底部提供库的代码，因为代码非常庞大，它作为单独的链接发布，因为它不符合30 KBStackOverflow 的限制。有两个文件sha256_simd.py和sha256_simd.hpp. Python 的文件包含计时和使用示例以及基于Cython的包装器，以使用我在 .hpp 文件中提供的 C++ 库。这个 python 文件包含编译和运行代码所需的一切，只需将这两个文件放在附近并运行 python 文件。

我在 Windows（MSVC 编译器）和 Linux（CLang 编译器）上测试了这个程序/库。

我的库的使用示例位于merkle_root_simd_example()和main()函数中。基本上你做以下事情：

  1. 首先通过 导入我的库mod = sha256_simd_import(cap = 'avx2')，每个程序运行只执行一次，不要多次执行，记住这个返回的模块到一些全局变量中。在cap参数中，您应该放置您的 CPU 支持的任何内容，它可以是gen或sse2或avx2或avx512以增加技术复杂性和提高速度的顺序。gen是通用的非 SIMD 操作，sse2是 128 位操作，avx2是 256 位操作，avx512是 512 位操作。

  2. 导入后使用导入的模块，例如mod.merkle_root_simd('avx2', 2, txs). 这里你又放了gen///技术之一sse2。为什么又来了？第一次导入时放置编译选项，告诉编译器支持给定的和所有以下技术。这里你放了将用于 merkle-root 调用的 SIMD 技术，该技术可以低于（但不能高于）编译技术。例如，如果您编译了 for那么您可以使用库 for or or ，但不能使用 for 。avx2avx512avx2gensse2avx2avx512

  3. 你可以在2)中看到我使用了options ('avx2', 2, txs)，这里的2意思是并行化参数，不是多核而是单核并行化，意思是两个avx2寄存器会连续计算。您应该输入 1 或 2 或 4 或 8，无论您的计算速度如何。

为了使用库，您必须安装两件事 - 一个是编译器（Windows 的 MSVC 和 Linux 的 CLang（或 GCC）），第二 - 通过安装一次 Cython 模块python -m pip install cython，Cython 是一个用于编程 C++ 代码的高级库在 Python 中，它充当了我的 Python.py和 C++.hpp模块之间的薄包装器。此外，我的代码是使用最现代的 C++20 标准编写的，请注意这一点，您必须拥有最新的 C++ 编译器才能编译我的代码，以便在 Windows 上下载最新的MSVC和/或在 Linux 上下载最新的 CLang（通过此处bash -c "$(wget -O - https://apt.llvm.org/llvm.sh)"描述的命令）。

在 .py 文件中，您可以看到我有时会提供额外的参数has_ossl = True, win_ossl_dir = 'd:/bin/openssl/'，仅当您需要将 OpenSSL 版本编译到我的库中时才需要这两个参数。Windows openssl 可以从这里下载。以后的 openssl 版本可以通过 使用mod.merkle_root_ossl(txs)，只需提供单个参数和事务。

在我的 .py 模块中的所有函数版本中，您需要为事务提供字节列表，这意味着如果您有十六进制事务，那么您必须先取消它们的十六进制。此外，所有函数都返回字节哈希，这意味着如果需要，您必须对其进行 hexlify。这种仅字节传输仅出于性能原因。

我知道我的代码很难理解和使用。因此，如果您对拥有最快代码的愿望非常认真，那么如果您愿意，请向我询问有关如何使用和理解我的代码的问题。另外我应该说我的代码很脏，我并不是要为所有人使用一个干净闪亮的库，我只是想让 SIMD 版本比 hashlib 版本甚至 openssl 快得多的概念验证版本，仅当您的 CPU 非常先进以支持 SSE2/AVX2/AVX512 中的至少一个时，大多数 CPU 都支持 SSE2，但并非所有 CPU 都支持 AVX2 和 AVX512。

sha256_simd.py

sha256_simd.hpp

于 2021-05-08T17:16:21.127 回答
1

在最后一次更新中（2021 年 5 月 2 日 17:00），调用到sha256(value).digest()我的机器大约需要 80% 的时间。解决这个问题的可能解决方案很少。

第一个是使用multiprocessing假设工作对于每次迭代都是独立的来并行化计算。这是一个例子：

from multiprocessing.pool import Pool

# [...] same as in the question

def iteration(txids):
    merkle_root_hash = calculate_merkle_root(txids)
    merkle_root_hash = hexlify(merkle_root_hash[::-1])
    return merkle_root_hash

processPool = Pool()
res = processPool.map(iteration, [txids for i in range(1000)])

print(res[-1])

这在我的 6 核机器上快了 4 倍。

另一种解决方案是找到一个更快的 Python 模块，该模块可以同时计算多个 sha256 哈希，以减少来自 CPython 解释器的昂贵的 C 调用。我不知道有任何包裹这样做。

最后，一种有效的解决方案是（至少部分地）calculate_merkle_root用 C 或 C++ 重写昂贵的计算并并行运行。这应该比您当前的代码快得多，因为这消除了函数调用开销和多处理成本。有许多库可以计算 sha256 哈希（如Crypto++库）。

于 2021-05-02T15:09:17.980 回答