Ex_sha3: Pure Elixir implementation of sha3 AND keccak-1600-f

Your Libraries & OS Mentoring Libraries
, , ,
1

Implementing ex_sha3 was an experiment of a pure Elixir version of the fips-202 sha3 and original keccak algorithms. ex_sha3 works platform independent without any nif wrapper, requires no c compilation. Also, this is the first library I’m aware of that exposes both algorithms, the original keccak hash as used in Ethereum, and the sha3 hash that got standardized. They are slightly different in padding and so return different hash results. Most implementations only do one or the other.

Size wise I’m pretty happy about this port. The implementation is in a single .ex file of 232 lines of code. Derived from the tiny-keccak implementation used by nim, exposing sha3, keccak and shake independently.

Compare https://github.com/dominicletz/exsha3/blob/master/lib/ex_sha3.ex vs. https://github.com/status-im/nim-keccak-tiny/blob/master/keccak_tiny/keccak-tiny.c

Unfortunately, the performance is abysmal compared to existing nif based implementations:

> mix run benchmark.exs 
Operating System: Linux
*snip*
Comparison: 
short nif_sha3_256      198.18 K
long  nif_sha3_256        2.13 K - 93.24x slower +465.43 μs
short  ex_sha3_256       0.102 K - 1946.84x slower +9818.31 μs
long   ex_sha3_256     0.00069 K - 285946.87x slower +1442824.24 μs

Haven’t yet looked into optimizing the performance as I was just in need of a short correct implementation, but would be happy to entertain anything to speed it up. The 2000x performance difference is a bit devastating I have to say.

Source: https://github.com/dominicletz/exsha3
Hex.pm: https://hex.pm/packages/ex_sha3
Docs: https://hexdocs.pm/ex_sha3/ExSha3.html

4 Likes
2

There are some algorithms, where the only known efficient implementations rely on in place mutation. I wouldn’t be surprised if this was one of them. If this is one of those, it’s likely you’ll always be better off using a NIF, which is ok. The language makes that tradeoff so we can get other things much more trivially, like concurrency and isolation.

There are some mutation API’s that in some situations might allow you to eek out better performance. Such as ETS and the process dictionary.

3 Likes
3

I wanted to look into it, but the nif is failing on me on macOS:

19:42:57.620 [warn]  The on_load function for module sha3 returned:
{:error, {:bad_lib, 'Failed to find library init function: \'dlsym(0x7fdcae50d740, _nif_init): symbol not found\''}}```
4

It’s worth noting that due to last call elimination, tight recursion can be basically the same thing as mutation. For example:

def sum([], acc), do: acc
def sum([h | tail], acc), do: sum(tail, h + acc)

The acc variable will be essentially mutated in place. Similar things can be done for binaries, so I expect performance can be improved by several orders of magnitude here.

5 Likes
5

Hi @dominicletz,

The best I could do is

Operating System: macOS
CPU Information: Intel(R) Core(TM) i7-4578U CPU @ 3.00GHz
Number of Available Cores: 4
Available memory: 16 GB
Elixir 1.8.1
Erlang 21.3.6

Benchmark suite executing with the following configuration:
warmup: 2 s
time: 5 s
memory time: 0 ns
parallel: 1
inputs: none specified
Estimated total run time: 28 s

Benchmarking long   ex_sha3_256...
Benchmarking long  Sharks_sha3_256...
Benchmarking short  ex_sha3_256...
Benchmarking short Sharks_sha3_256...

Name                            ips        average  deviation         median         99th %
short Sharks_sha3_256        242.72        4.12 ms    ±10.88%        3.99 ms        6.13 ms
short  ex_sha3_256           191.38        5.23 ms     ±8.28%        5.10 ms        7.14 ms
long  Sharks_sha3_256          1.57      635.73 ms     ±1.19%      634.23 ms      653.65 ms
long   ex_sha3_256             1.22      821.31 ms     ±0.70%      819.27 ms      829.02 ms

Comparison: 
short Sharks_sha3_256        242.72
short  ex_sha3_256           191.38 - 1.27x slower +1.11 ms
long  Sharks_sha3_256          1.57 - 154.31x slower +631.61 ms
long   ex_sha3_256             1.22 - 199.35x slower +817.19 ms

It’s not really that much faster, the reason why it’s a tiny bit faster than your implementation is because I refactored your code to be idiomatic Elixir.

For these kind of things you really want to use a low level language, most of the :crypto functions uses openssl.

6

Hi @michalmuskala, the sha3 dependency is a development dependency only used for the benchmark and the reference test. You don’t need any nif to run the actual code.

And yes, the pain that some of these nif’s just won’t compile cleanly depending on your actual architecture was reason to create this package.

1 Like
7

Hey @Schultzer, that’s pretty cool. Would you mind making a pull request with your changes? https://github.com/dominicletz/exsha3

1 Like
8

Thanks @Schultzer’s pull request and a faster rol() implementation we’ve got a new version now, that is still pure Elixir but nearly 10x faster… That said it’s still much slower than the nif:

##### With input long  string #####
Comparison: 
 nif_sha3_256       2243.02
  ex_sha3_256          9.36 - 239.60x slower +106.37 ms

##### With input short string #####
Comparison: 
 nif_sha3_256     215033.52
  ex_sha3_256        870.25 - 247.09x slower +1.14 ms
4 Likes
9

it seems the sha3 package was published to hex with с object files. Try to remove all *.o files in the deps/sha3/c_src dir and recompile sha3

find deps/sha3/c_src -name *.o -delete
mix deps.compile sha3

Why the author publish the lib with object files is not clear for me. Maybe just forgot to delete these files before publishing

1 Like