Precompiled BLAKE2b

[tjade273]

Title

  Title: Add precompiled BLAKE2b contract
  Author: Tjaden Hess <tah83@cornell.edu>
  Status: Draft
  Type: Standard Track
  Layer: Consensus (hard-fork)
  Created 2016-06-30

Abstract

This EIP introduces a new precompiled contract which implements the BLAKE2b cryptographic hashing algorithm, for the purpose of allowing interoperability between the Zcash blockchain and the EVM.

Parameters

• METROPOLIS_FORK_BLKNUM: TBD
• GBLAKEBASE: 30
• GBLAKEWORD: 6

Specification

Adds a precompile at address 0x0000....0c which accepts a variable length input interpreted as

[OUTSIZE, SALT[0...15], PERSONALIZATION[0...15], D_1, D_2, ..., D_INSIZE]

where INSIZE is the length in bytes of the input. Throws if OUTSIZE is greater than 64. Returns the OUTSIZE-byte BLAKE2b digest, as defined in RFC 7693.

Gas costs would be equal to GBLAKEBASE + GBLAKEWORD * floor(INSIZE / 32)

In order to maintain backwards compatibility, the precompile will return 0 if CURRENT_BLOCKNUM < METROPOLIS_FORK_BLKNUM

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. One BLAKE2 digest in Soldity, (see https://github.com/tjade273/eth-blake2/blob/optimise_everything/contracts/blake2.sol) currently requires ~480,000 + ~90*INSIZE gas, and a single verification of an Equihash PoW verification requires 2⁵ to 2⁷ iterations of the hash function, making verification of Zcash block headers prohibitively expensive.

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

Interoperability with Zcash would enable 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 is little-endian. 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.

Note that the function can produce a variable-length digest, up to 64 bytes, which is a feature currently missing from the hash functions included in the EVM and is an important component in the Equihash PoW algorithm.

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....0000c 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.

[tjade273]

PRs implementing the changes are in the works

[kumavis]

@tjade273 excellent EIP - clear and easy to follow. can you explain how this enables Zcash atomic swaps? BTC relay does not enable atomic BTC swaps, only tx confirmation.

[tjade273]

Even with BTC relay, one can construct a sort of swap contract. If Alice wants to buy 1 BTC from Bob,

Alice can create a contract which pays 100 ETH to whomever can provide a merkle proof of a transaction to Alice's BTC address, or sends the ETH back to Alice if no one provides a valid transaction within some time limit.

The Zrelay would enable the same thing

[kumavis]

👍 right ok, requires a market+escrow contract 👍

[daira]

Note that the variation of BLAKE2b used by the Zcash PoW is set to have an output length other than the default 512 bits, and a custom personalisation string (both of these depend on the Equihash parameters, which have not been nailed down yet): https://github.com/zcash/zcash/blob/zc.v0.11.2.latest/src/crypto/equihash.cpp#L30

I recommend allowing arbitrary personalisation strings and output lengths (and maybe salts, which are not used by Zcash but may be used by other protocols) to be specified.

[tjade273]

Yes, I originally drafted the EIP with arbitrary length output, but in the
interests of getting the idea out there, I made it a little simpler.

I recently added personalisation to Solidity implementation as well, so
that shouldn't be a problem

On Sat, Jul 23, 2016, 8:54 PM Daira Hopwood notifications@github.com
wrote:

Note that the variation of BLAKE2b used by the Zcash PoW is set to have an
output length other than the default 512 bits, and a custom personalisation
string (both of these depend on the Equihash parameters, which have not
been nailed down yet):
https://github.com/zcash/zcash/blob/zc.v0.11.2.latest/src/crypto/equihash.cpp#L30

I recommend allowing arbitrary personalisation strings and output lengths
to be specified.

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
#129 (comment), or mute
the thread
https://github.com/notifications/unsubscribe-auth/ADwRiHAsf5PwvCgpgRG5v_taTCYkdY6hks5qYmNJgaJpZM4JGVJJ
.

[zookozcash]

Way to go!

Questions:

• Is it likely to go into Metropolis? Is there anything I can do to help get it in?

• Why does the Solidity version take ~480K gas to set up the state, but then only ~12K gas per 128-byte input block? It shouldn't be that expensive to set up the state! What's going on there?

• How much gas does a Solidity implementation of BLAKE2s cost? We could switch from BLAKE2b to BLAKE2s and it would be a modest performance benefit in C/C++ — reducing the cost of hashing to about 75% of previous levels. I wonder if it would be an even bigger win in Solidity.

• Suppose we changed it from:

  X_i = H(block header up to end of nonce | index_i)

  to

  U = H(block header up to end of nonce)
  X_i = H(U | index_i)

  Then an Equihash implementation would need to generate a lot (like 2^5 or 2^7) X_i's, but the smaller input (U | index_i) would fit into a single BLAKE2b or BLAKE2s input block, so it should take about half as much gas per X_i as hashing H(block header up to end of nonce | index_i) for each X_i, like we currently do.

[zookozcash]

Oh, is the high cost of gas to initialize the state due to the fact that memory isn't free? In that case, I would expect BLAKE2s to cost about half as much gas, for both the initialization and the per-byte processing, as BLAKE2b. So maybe ~240K + 45 * INSIZE.

[tjade273]

@zookozcash Yes, the gas cost is almost entirely from the high memory costs. BLAKE2s may well be much more practical, I can modify the implementation and run some tests pretty quickly.

[daira]

Right, but note that BLAKE2b with an arbitrary personalisation string and output length is what Equihash needs.

[tjade273]

Yes, the current proposal allows for arbitrary output length. The
personalization and salt are padded to 16 bytes, as per the BLAKE2b specification.

[zookozcash]

GBLAKEBASE: 30
GBLAKEWORD: 6

(See also someone asking what is the cheapest hash function available in solidity.)

According to the yellow paper, SHA3 has base gas cost 30 and per-word gas cost 6.

According to bench.cr.yp.to, BLAKE2b costs roughly 3 times less than SHA3 ("keccakc512") per base and 2.7 times less per byte on a Knight's Landing CPU.

I'd suggest reflecting this efficiency in the gas costs. Dividing by those ratios and rounding up that would be:

GBLAKEBASE: 10
GBLAKEWORD: 3

By the way, here's an answer I just posted on crypto.stackexchange.com about why NIST chose Keccak instead of BLAKE (not BLAKE2) for SHA-3.

[zookozcash]

Sometimes protocols need to incrementally process inputs, i.e. to produce a series of chunks, and after producing each one, add it into the hash computation, and then after many of these chunks, generate the hash result.

If the Ethereum precompile for BLAKE2b has a way to initialize a hasher object, update it with some more bytes, and then finalize it, then Ethereum apps can do the this — updating the hasher object with each successive chunk until all the chunks have been processed, and then producing the hash result by finalizing the hasher object.

With the API in the current proposal, above, Ethereum apps would instead have to accumulate a buffer of all the chunks, wait until they've produced or received the last chunk, and then pass the entire buffer into the hash precompile at once. Depending on the protocol, this could impose a much higher memory cost — the Ethereum app would need to use enough memory to store all of the chunks put together, vs. enough to store the biggest chunk.

Some other protocols (i.e. not Ethereum apps, but pre-existing or external protocols) may assume this kind of incremental hashing ability, and the absence of it could hinder the ability of an Ethereum app to interoperate with that other protocol.

The discussion about the "block header" in #129 (comment) is an example of someone wanting to write an Ethereum app that is compatible with a pre-existing protocol — Zcash — and the absence of the incremental hasher causing the Ethereum implementation to be unnecessarily expensive.