Blake2b Compression Function F is too slow

[carver]

What is wrong?

Blake2b compression takes way too long in the all-python implementation. It's now trivial to DoS trinity & py-evm by filling a block with calls to the precompile one call to the precompile, specifying millions of rounds.

See #1818 for rough analysis:

It takes 25 seconds to run 2 million rounds (which is 2M gas). At that rate, it will take:

• 100 seconds to run a full 8 million gas block (just confirmed, it took 91s)
• 14 hours to run test vector 8, which has 4 billion rounds

So it's about 6 times too slow, at a minimum, assuming 15s blocks.

How can it be fixed

Ideally, write a python wrapper around the C implementation that is already distributed the stdlib blake2b module.

It should meet the same API as the current implementation:

py-evm/eth/_utils/blake2/compression.py

Lines 71 to 76 in 7696779

	def blake2b_compress(
	num_rounds: int,
	h_starting_state: TMessageBlock,
	block: bytes,
	t_offset_counters: Tuple[int, int],
	final_block_flag: bool) -> bytes:

It is not a requirement that everything beneath that ^ API is in C. If you want a python layer that prepares & returns the appropriate types, that's fine/great. The primary requirement is that it runs fast enough.

It should run 8 million rounds in under 8 seconds (of course, faster is better).

A working PR should include a hypothesis test that shows equivalence between the all-python implementation and the new API. It should also include a test showing that it runs fast enough, maybe run 100k rounds to make sure they complete in under 0.1s.

Note that some of the nomenclature on the types and variable names may be a little funky, since the author (@carver) was not familiar with the internals of Blake2. Bonus points for identifying better names, with citations. (Especially for variables and types like message, block, and state)

[carver]

I submitted a request to get this bountied.

[davesque]

Have a working Rust implementation: https://github.com/davesque/blake2.git

Still need to write and package Python bindings.

[davesque]

@pipermerriam @carver
My solution for this is now available:

pip install 'blake2b-py==0.1.2'

The functions in that package have essentially the same API as the native python implementation. The docstrings are pretty informative (though they're abridged here):

In [1]: import blake2b

In [2]: blake2b.compress?
Signature:
blake2b.compress(
    rounds,
    starting_state,
    block,
    offset_counters,
    final_block_flag,
)
...

In [3]: blake2b.decode_parameters?
Signature: blake2b.decode_parameters(input)
...

In [4]: blake2b.decode_and_compress?
Signature: blake2b.decode_and_compress(input)
...

[davesque]

@carver @pipermerriam By the way, if there's any need that blake2b-py be even faster, I saw a couple other optimized implementations in Rust that use SIMD instructions. We could try to incorporate some of those features into blake2b-py if necessary.

[carver]

It's not likely to be a problem, at least for a while. I ran it against 4B gas and it took 90s. That is about 400 blocks worth of gas at today's gas limits. Assuming it scales down linearly, you could fill a block and the compression function would run for less than 250ms.