sha3 算法优化

Owned by YSG
Last updated: 4月 13, 2022
2 min read

我现在对sha3算法还不是很清楚, 写的这些看法都不一定正确(我还在熟悉中)，

1.simd优化

看到有些论文里面提到使用simd可以做到性能提升1.4-2.6倍，我们accmulator大量依赖于这个计算,

目前看到sha2有一些优化

https://github.com/RustCrypto/hashes/commit/93d895de72c2cb3ac7bc106f03e33715f8f304c2

sha3有些论文

https://sol.sbc.org.br/index.php/sbseg/article/download/4266/4197/

https://caslab.csl.yale.edu/workshops/hasp2016/HASP16-10_slides.pdf

 

论文AVX512相关代码

https://github.com/rbCabral/SHA-3

用了2个优化方式

1)基于avx2指令的seq sha3优化，每个msg计算hash使用avx2来加速

2) 基于par计算msg hash,多条消息放入msg数组，基于avx2并行运算hash数组

目前cloudflare circlhttps://github.com/cloudflare/circl/blob/master/simd/keccakf1600/f1600x4_amd64.go

使用的是2)par计算

2.使用库对比

目前我们的accumulator使用sha3计算hash使用的tiny-keccak库，

可能原因是tiny-keccak先实现的，从文档上来看

https://github.com/debris/tiny-keccak#readme

性能比rust_crypto好，

running 4 tests test rust_crypto_sha3_256_input_32_bytes ... bench: 677 ns/iter (+/- 113) = 47 MB/s test rust_crypto_sha3_256_input_4096_bytes ... bench: 17,619 ns/iter (+/- 4,174) = 232 MB/s test tiny_keccak_sha3_256_input_32_bytes ... bench: 569 ns/iter (+/- 204) = 56 MB/s test tiny_keccak_sha3_256_input_4096_bytes ... bench: 17,185 ns/iter (+/- 4,575) = 238 MB/

这是2年前情况(tiny-keccack一直没有迭代)， 使用最新的sha3库，

 

修改tiny-keccak下comparison/Cargo.toml文件

 

% git diff comparison/Cargo.toml diff --git a/comparison/Cargo.toml b/comparison/Cargo.toml index 1b88b6a..b0dd061 100644 --- a/comparison/Cargo.toml +++ b/comparison/Cargo.toml @@ -6,4 +6,4 @@ authors = ["debris <marek.kotewicz@gmail.com>"] [dependencies] tiny-keccak = { path = "../", features = ["sha3"] } -sha3 = "0.8.2" +sha3 = "0.10.0"

修改sha3.rs

 

+++ b/comparison/benches/sha3.rs @@ -40,8 +40,8 @@ fn rust_crypto_sha3_256_input_32_bytes(b: &mut Bencher) { b.iter(|| { let mut sha3 = Sha3_256::default(); - sha3.input(&data); - sha3.result(); + sha3.update(&data); + sha3.finalize(); }); } @@ -53,7 +53,7 @@ fn rust_crypto_sha3_256_input_4096_bytes(b: &mut Bencher) { b.iter(|| { let mut sha3 = Sha3_256::default(); - sha3.input(&data); - sha3.result(); + sha3.update(&data); + sha3.finalize(); }); }

 

 

Intel(R) Xeon(R) CPU E5-2666 v3 @ 2.90GHz 7G Memory

我在跳板机上测试结论

rustup run nightly cargo bench running 4 tests test rust_crypto_sha3_256_input_32_bytes ... bench: 599 ns/iter (+/- 12) = 53 MB/s test rust_crypto_sha3_256_input_4096_bytes ... bench: 17,665 ns/iter (+/- 96) = 231 MB/s test tiny_keccak_sha3_256_input_32_bytes ... bench: 595 ns/iter (+/- 5) = 53 MB/s test tiny_keccak_sha3_256_input_4096_bytes ... bench: 17,737 ns/iter (+/- 158) = 230 MB/s

在macOs上

 

running 4 tests test rust_crypto_sha3_256_input_32_bytes ... bench: 441 ns/iter (+/- 47) = 72 MB/s test rust_crypto_sha3_256_input_4096_bytes ... bench: 12,875 ns/iter (+/- 775) = 318 MB/s test tiny_keccak_sha3_256_input_32_bytes ... bench: 452 ns/iter (+/- 23) = 70 MB/s test tiny_keccak_sha3_256_input_4096_bytes ... bench: 13,073 ns/iter (+/- 880) = 313 MB/s

目前看起来crypto hash效率慢慢赶上来了，可能会超过tiny-kecccak,前者一直在开发维护，后者两年都没有更新了

目前有一份从XKCP的C实现 ffi 给rust调用的实现

https://github.com/starcoinorg/starcoin-crypto/tree/main/crates/diem-crypto/ext