Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

BLAKE2b `F` Compression Function Precompile #152

Open
tjade273 opened this issue Oct 4, 2016 · 37 comments

Comments

Projects
None yet
@tjade273
Copy link

commented Oct 4, 2016

Title

Title: Add RFC 7693 compression function `F` contract
Author: Tjaden Hess <tah83@cornell.edu>
Status: Draft
Type: Standard Track
Layer: Consensus (hard-fork)
Created 2016-10-04

Abstract

This EIP introduces a new precompiled contract which implements the compression function F used in the BLAKE2b cryptographic hashing algorithm, for the purpose of allowing interoperability between the Zcash blockchain and the EVM, and introducing more flexible cryptographic hash primitives to the EVM.

Parameters

  • METROPOLIS_FORK_BLKNUM: TBD
  • GFROUND: TBD

Specification

Adds a precompile at address 0x0000....0d which accepts ABI encoded arguments corresponding to the function signature

F(bytes32[2] h, bytes32[4] m, uint t , bool f, uint rounds) returns (bytes32[2] h_new);

where h, m, t and f are the current state, the new message, the byte counter and a finalization flag, as defined in RFC 7693, and rounds is the number of rounds of mixing to perform (BLAKE2b uses 12, BLAKE2s uses 10). h_new is the updated state of the hash.

Each operation will cost GFROUND * rounds.

Motivation

Besides being a useful cryptographic hash function and SHA3 finalist, BLAKE2b allows for efficient verification of the Equihash PoW used in Zcash, making a BTC Relay - style SPV client possible on Ethereum. A single verification of an Equihash PoW verification requires 512 iterations of the hash function, making verification of Zcash block headers prohibitively expensive if a Solidity implementation of BLAKE2b is used.

The BLAKE2b algorithm is highly optimized for 64-bit CPUs, and is faster than MD5 on modern processors.

Interoperability with Zcash could enable contracts like trustless atomic swaps between the chains, which could provide a much needed aspect of privacy to the very public Ethereum blockchain.

Rationale

The most frequent concern with EIPs of this type is that the addition of specific functions at the protocol level is an infringement on Ethereum's "featureless" design. It is true that a more elegant solution to the issue is to simply improve the scalability characteristics of the network so as to make calculating functions requiring millions of gas practical for everyday use. In the meantime, however, I believe that certain operations are worth subsidising via precompiled contracts and there is significant precedent for this, most notably the inclusion of the SHA256 prcompiled contract, which is included largely to allow inter-operation with the Bitcoin blockchain.

Additionally, BLAKE2b is an excellent candidate for precompilation because of the extremely asymetric efficiency which it exhibits. BLAKE2b is heavily optimized for modern 64-bit CPUs, specifically utilizing 24 and 63-bit rotations to allow parallelism through SIMD instructions and little-endian arithmetic. These characteristics provide exceptional speed on native CPUs: 3.08 cycles per byte, or 1 gibibyte per second on an Intel i5.

In contrast, the big-endian 32 byte semantics of the EVM are not conducive to efficient implementation of BLAKE2, and thus the gas cost associated with computing the hash on the EVM is disproportionate to the true cost of computing the function natively.

Implementation of only the core F compression function allows substantial flexibility and extensibility while keeping changes at the protocol level to a minimum. This will allow functions like tree hashing, incremental hashing, and keyed, salted, and personalized hashing as well as variable length digests, none of which are currently available on the EVM.

There is very little risk of breaking backwards-compatibility with this EIP, the sole issue being if someone were to build a contract relying on the address at 0x000....0000d being empty. Te likelihood of this is low, and should specific instances arise, the address could be chosen to be any arbitrary value, with negligible risk of collision.

@zookozcash

This comment has been minimized.

Copy link

commented Oct 4, 2016

Great! I think this is a good feature to add. It will allow "Project Alchemy" — BTCRelay-style interoperation between the Zcash and Ethereum blockchains, and it may also be useful as a general purpose secure hash function which is more efficient than SHA3.

@chriseth

This comment has been minimized.

Copy link
Contributor

commented Oct 4, 2016

Please add some more details about the gas costs. I guess they should at least depend on rounds.

@zookozcash

This comment has been minimized.

Copy link

commented Oct 4, 2016

In the earlier EIP about a precompiled full BLAKE2b, the following conversation happened about gas costs:

Okay, so for this new proposal — the precompiled BLAKE2b Compression Function F, the computational cost is not a base plus a cost per byte. Instead, every invocation of this precompile has the same size input (192 bytes, not counting t, f, or rounds).

I suggest the gas cost for invoking BLAKE2b Compression Function F should be 440 per invocation. That's from estimating that it will take about 440 microseconds to compute it. It is within 4X of what it would cost in gas to hash a 192-byte input with SHA3.

(I still don't understand what Zaki's rationale is for making the gas cost of BLAKE2b precompile be the same as gas cost of SHA3 precompile.)

@zookozcash

This comment has been minimized.

Copy link

commented Oct 4, 2016

Oh, good point about the gas cost of rounds. I propose that BLAKE2b Compression Function F gas cost be 37 gas per round. (12 rounds to be compatible with BLAKE2b.)

@tjade273

This comment has been minimized.

Copy link
Author

commented Oct 4, 2016

I think picking hard numbers right now would be somewhat pointless, until we can actually measure compute time in different clients. You're right that the gas is now going to be proportional to the number of rounds now, as opposed to the number of bytes.

@gcolvin

This comment has been minimized.

Copy link
Collaborator

commented Oct 4, 2016

I'd rather implement 64-bit operations in the EVM.

@matthewdgreen

This comment has been minimized.

Copy link

commented Dec 6, 2016

I think this would be a useful project, and I'd like to see it get restarted!

@zookozcash

This comment has been minimized.

Copy link

commented Dec 6, 2016

Okay, to make progress on this, I propose that we temporarily table @gcolvin's alternative suggestion of 64-bit arithmetic (interesting idea, but let's move it to a separate EIP), and satisfice on the gas costs (I still want the BLAKE2b Compression Function F to cost 37 gas per round, but if agreeing to any other number will get this project moving again, then I'll agree to that number!).

@tjade273, @vbuterin: What can we do to help make progress on this. Would it help if one of the Zcash team provided an implementation in some programming language?

@gcolvin

This comment has been minimized.

Copy link
Collaborator

commented Dec 6, 2016

Agreed.

@tjade273

This comment has been minimized.

Copy link
Author

commented Dec 6, 2016

Sorry if the project has slowed down a bit, I've been quite busy with school; I have a break coming up and I hope to get a PoC with a few of the implementations done.

Right now, I think the priority should be to get a precompile implemented in the Go and Rust implementations, since those are the most widely used. To that end, if anyone has experience with FFIs in Go or Rust, that'd be really helpful.

As for gas costs, I think it will become clear what a reasonable price is based on some simple benchmarking once we have an implementation in major clients

@zookozcash

This comment has been minimized.

Copy link

commented Dec 6, 2016

Great! @gcolvin agrees to move the 64-bit-arithmetic idea to another thread (and please let me know so I can subscribe to that one), and we all agree to defer decision about precise gas costs. I'll see if I know someone who wants to take a stab at implementing it in Rust.

@tjade273

This comment has been minimized.

Copy link
Author

commented Dec 21, 2016

The Go precompile is almost complete, and the benchmarks look good: the BLAKE2 precompile is almost exactly twice as fast as the SHA3 on my laptop. That's using a pretty un-optimized, pure-go implementation.

@zmanian

This comment has been minimized.

Copy link

commented Jan 3, 2017

@tjade273 So I was looking at this and I asked Veorq about it and it looks to me like you passing in 128 bits of counter data into the compression function. I believe that is supposed to be max 64 bits. It may not matter but it requires more invasively changing an existing Blake implementation to conform to your api like I'm doing with the Rust impl.

@tjade273

This comment has been minimized.

Copy link
Author

commented Jan 3, 2017

@zmanian The specification says that the compression function takes a

2w-bit offset counter "t"

i.e. 128 bits. This is consistent with the reference implementation.

The API is not set in stone, by the way. I'm totally open to alternative ones and I'm strongly considering getting rid of ABI encoding and just serializing the data in order.

@zmanian

This comment has been minimized.

Copy link

commented Jan 4, 2017

Yeah the spec says 2 words. There are some incidental complexities to storing the value in two state variables in the rust version. The single variable allows using checked arithmetic and typecast in token state update. i'll try and take a closer look at it.

@tjade273

This comment has been minimized.

Copy link
Author

commented Jan 6, 2017

@zmanian You may be safe just ignoring the higher-order word. You would have to be hashing ~10^10 GB of data for it to make any difference. It's hacky, but not the end of the world if it saves you a lot of trouble. We just need to make sure all of the implementations behave consistently.

@zmanian

This comment has been minimized.

Copy link

commented Jan 7, 2017

It really does save a lot of trouble. I mean nightly does have 128 bit checked arithmetic now...

I don't even @vbuterin has enough eth to so 10^10GB on the blockchain :-)

@chriseth

This comment has been minimized.

Copy link
Contributor

commented Jan 11, 2017

@tjade273 What are your numbers on the gas costs of https://github.com/ConsenSys/Project-Alchemy/blob/master/contracts/BLAKE2b/BLAKE2b.sol ? It seems to me that this contract can be heavily optimized. For example the constant could be moved from storage to code / memory (50 gas some time ago, now 200 gas for sload compared to 3 gas for mload / codecopy). This could make it viable to do all that without a precompile.

@tjade273

This comment has been minimized.

Copy link
Author

commented Jan 11, 2017

@chriseth I haven't worked on the BLAKE contract since before the gas cost readjustments, so I'm not sure exactly what the costs are. When I last ran it, each run was something like 200k gas. I'm sure I could optimize it more, but the equihash PoW verification requires 2^9 BLAKE compressions, and I though it unlikely that I would be able to get the gas costs below ~6,000.

I can take another crack at the optimizations, though and see if I can get the costs significantly lower

@zookozcash

This comment has been minimized.

Copy link

commented Apr 19, 2017

Is there anything I can do to move this EIP along? I'd really like to reduce barriers to cross-chain interoperation between Ethereum and Zcash, and this would help. (There are other approaches to cross-chain interop, but it isn't yet clear to me that any of the alternatives would be strictly better than this one.)

Additionally, making an efficient implementation of BLAKE2 available to Ethereum contracts could help with completely unrelated uses, such as if an Ethereum contract wanted to somehow interoperate with other systems like https://github.com/bramcohen/MerkleSet, or just because BLAKE2 is a highly efficient and secure hash function.

I see that the "editor-needs-to-review" label was added. Who is the editor? Thanks!

@MicahZoltu

This comment has been minimized.

Copy link
Contributor

commented Apr 19, 2017

@zookozcash I believe your best bet is probably to create a PR of this EIP. Issues are intended for discussion, which it seems there isn't much of at this point. Once there is no longer any "debate" then a PR that adds the EIP using the template is the next step in the process.

I believe the contributing guide was recently updated: https://github.com/ethereum/EIPs#contributing

Of course, I could be totally wrong about all this as I'm just a random guy on the internet with no authority, but if I were you the above is what I would do. :)

@zookozcash

This comment has been minimized.

Copy link

commented Jun 4, 2017

By the way, there are two different motivations for why this EIP should go into Ethereum. The first (dear to my heart) is to facilitate Zcash↔Ethereum interoperation using the "BTCRelay" technique. Basically allowing Ethereum contracts to "see into" the Zcash blockchain! This is already possible, but it is very slow and expensive without this precompile.

But I want to emphasize that there is another independent reason for this EIP, which is that BLAKE2 is just a more efficient and more widely used hash function than SHA-3, and this EIP could allow Ethereum contracts to efficiently interoperate with data generated by the growing number of BLAKE2-using data generators out there.

I was reminded of this latter fact when reading this blog post by the estimable Adam Langley “Maybe Skip SHA-3” and the ensuing discussions on hackernews and reddit.

There appears to be a growing consensus among cryptographers that SHA-3 is not a great fit for most purposes and is not likely to become widely used. Even the authors of SHA-3 seem to be advocating not for adoption of SHA-3, but for adoption of newer, more efficient variants of SHA-3.

But everyone agrees that BLAKE2 is efficient, secure, and widely used.

By the way, you might enjoy this nice history of hash functions:

https://z.cash/technology/history-of-hash-function-attacks.html
screenshot 2017-06-03 at 19 30 50

@vbuterin

This comment has been minimized.

Copy link
Collaborator

commented Jun 4, 2017

Thanks a lot for the great feedback. This is definitely making me consider BLAKE2 support much more strongly.

@whyrusleeping

This comment has been minimized.

Copy link

commented Jul 5, 2017

The ipfs team is working towards switching our default hash function to blake2b-256, on the grounds of making future integrations much easier, i'm definitely in support of this

@axic

This comment has been minimized.

Copy link
Member

commented Sep 22, 2017

@tjade273 if it is already ABI encoded, why not have two functions: hash, hash_final? That would remove the need for the bool f (F(bytes32[2] h, bytes32[4] m, uint t , bool f, uint rounds) returns (bytes32[2] h_new);).

It may also make sense considering to make the rounds part of the name too.

I assume the code using this would either go for Blake2b or Blake2s and wouldn't really switch between them, it would mean cheaper execution as the number of parameters for ABI encoding is lower and uses less memory as well. The downside is of course if the rounds parameter is actually free to be anything based on the use case.

@holiman

This comment has been minimized.

Copy link
Contributor

commented Sep 25, 2017

I'm tentatively in favour of this, but I'm not so sure about having a precompile accept ABI-encoded data. Reasons being:

  • ABI-encoding (and the ABI-format) is currently not part of consensus, it's not implemented on the evm layer.
  • No other precompiles use that format
  • I believe it adds overhead when determining gascosts.

Furthermore, ABI-encoding is imo not fool-proof. It's possible to e.g. point two dynamic arrays to use the same data, or point the data-part to wrap around back to the start of the argument-field.

TLDR; I'd rather not have ABI-parsing as part of consensus.

@axic

This comment has been minimized.

Copy link
Member

commented Sep 25, 2017

@holiman I think it is certainly possible defining a restricted set of ABI encoding supported by this precompile the same way as the data format is described for every other precompile.

@holiman

This comment has been minimized.

Copy link
Contributor

commented Sep 25, 2017

restricted set sounds good

@tjade273

This comment has been minimized.

Copy link
Author

commented Sep 25, 2017

I'm actually not a huge fan of ABI encoding in this context either. It makes interaction with the precompile easier, but I'm not sure it is necessary and it does add overhead.

t, f, and rounds can all fit into a single 32 byte value as well, so using three separate uints is excessive.

@zookozcash

This comment has been minimized.

Copy link

commented Nov 7, 2017

I don't have a strong opinion about the encoding issues but I'm persuaded by #152 (comment) and #152 (comment) that we should just use a specified packing.

The next step is to write an EIP! (#152 (comment))

@jasondavies

This comment has been minimized.

Copy link

commented Feb 27, 2018

I used wasm-metering to measure the gas cost of a blake2b compress invocation when using blake2b-wasm, and it only took ~31.2 gas per compress invocation (much lower than I had expected based on the discussions above).

My branch of blake2b-wasm is here; it simply logs to the console the cost of every compress invocation, which should be the same every time.

@axic

This comment has been minimized.

Copy link
Member

commented Feb 27, 2018

@jasondavies note, the ewasm gas costs we have aren't final yet

@axic

This comment has been minimized.

Copy link
Member

commented Feb 27, 2018

@jasondavies also thank you for reporting this, will need to look into it. It would be nice if you could join https://gitter.im/ewasm/Lobby

@zookozcash

This comment has been minimized.

Copy link

commented Jun 14, 2018

Here's another implementation of BLAKE2 for wasm: https://github.com/nazar-pc/blake2.wasm

@sjalq

This comment has been minimized.

Copy link

commented Nov 1, 2018

We at Octobase.co would like to see this implememted.

@axic

This comment has been minimized.

Copy link
Member

commented Nov 1, 2018

We have a work in progress implementation for the ewasm (testnet) at ewasm/ewasm-precompiles#15

It doesn't fully model this EIP yet, but any contribution is welcome to do it.

It will be available and fully usable in the ewasm testnet, to be launched at devcon 😉

@Souptacular

This comment has been minimized.

Copy link
Member

commented May 1, 2019

Please see discussion on #131 where I will direct people to a FEM post.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.