Replace SHA256 with BLAKE2 everywhere

[ebfull]

Anywhere we use SHA256, let's replace it with BLAKE2 or come up with a good reason why we shouldn't.

One exception is the circuit where more factors come into play, see #705.

[zookozcash]

Let's use BLAKE2s (instead of BLAKE2b or something else).

[maaku]

A good reason why you shouldn't: SHA256 has pervasive hardware support.

[daira]

I don't see a strong motivation for this. Enumerating all the options, we have:

1. SHA-256 everywhere.
   • Already implemented.
2. Subset-sum for the commitment tree, SHA-256 everywhere else.
   • This option makes sense; the engineering and analysis cost of changing the commitment tree hash is significant but the performance gain is substantial.
3. Blake2s everywhere.
   • Requires significant engineering effort and security review to update the circuit; writing a hash implementation in libsnark is difficult and error-prone. Possibly a slight performance improvement (10% or thereabouts?) over 1.
4. Blake2s outside the circuit, SHA-256 inside.
   • Ugh, why would we do this? What advantage does it have over 1?
5. Blake2s outside the circuit, subset-sum for the commitment tree, SHA-256 for the other circuit hashes.
   • Ugh, even worse than 4.
6. Subset-sum for the commitment tree, Blake2s everywhere else.
   • This still requires significant engineering effort and security review to update the circuit, as for option 3, and in addition to the cost for option 2.

None of the Blake2s options (3 to 6) look attractive to me.

[ebfull]

An additional downside from deviating from Bitcoin in this respect is that some tools which use these hashes for various purposes would have to be updated to work with our system.

[zookozcash]

@ebfull: can you give an example of a tool, using SHA256 (probably because it was designed for Bitcoin), which would need to be changed if we used BLAKE2s instead of SHA256 in Zcash?

[zmanian]

For generating tx ids from from serialized txs. ie. tx_id = sha256(sha256(txhex) with javascript, python etc.

Parsing transactions in other languages is a common thing

[ebfull]

I was thinking of lightning network "commitments" which are used to create multiparty bi-directional channels. These use SHA256 in the scripting system. However, we don't necessarily have to remove SHA256 there, we can just add BLAKE2 as an alternative, so that point is a little moot.

Other than that, what @zmanian said also applies, but I can't think of anything else.

[zookozcash]

I really strongly prefer BLAKE2 over SHA256. Here are at least some of
my reasons:

• SHA256 was designed by NSA (publicly released to the world in
  2001). BLAKE was designed by Jean-Philippe Aumasson et al. (in
  2008).
• SHA256 was based on SHA1 (which is weak). BLAKE was based on
  ChaCha20 (which is strong).
• [NOTA BENE: the following is presented, not as evidence that SHA256
  is weak, but as evidence that SHA256 will have a worse reputation in
  the future. Don't confuse the two.] NIST/NSA have repeatedly
  signaled lack of confidence in SHA256: first by hastily organising
  the SHA3 contest in the aftermath of Wang's breakthrough, then by
  making "Don't be like SHA256" a requirement of that contest, and
  most recently by banning SHA256 from new designs (https://www.iad.gov/iad/customcf/openAttachment.cfm?FilePath=/iad/library/ia-guidance/ia-solutions-for-classified/algorithm-guidance/assets/public/upload/CNSA-Suite-and-Quantum-Computing-FAQ.pdf&WpKes=aF6woL7fQp3dJieGY3pmDtEBdP8vHA2987qb9n).
• BLAKE was very well-studied during the SHA3 competition. In NIST's
  final report on the SHA3 process, they stated that the depth of
  scientific analysis applied to BLAKE exceeded even that applied to
  Keccak (the final SHA3 winner).
• SHA256 has realistically feasible attacks against 31 out of 64
  rounds. BLAKE2 has no feasible attacks against more than 2 out of 10
  (BLAKE2s) or 2 out of 12 (BLAKE2b) rounds.
• BLAKE2 has security features which could be useful for us, such as
  protection against length-extension, a standard method of keying,
  "personalization tags" to guarantee domain separation, etc.
• BLAKE2 is more efficient than SHA256 in software on most
  platforms. For example, on ARM chips, it is usually about twice as
  efficient as SHA256 when hashing 64 bytes.
• BLAKE2 might be a little more efficient than SHA256 inside
  libsnark — unclear.
• BLAKE2 is the de facto standard hash function used by all of the
  skilled symmetric cryptographers working on things like Password
  Hashing Competition, new Proofs-of-Work such as Equihash,
  etc. Whatever Proof-of-Work function we choose, it'll probably turn
  out to come defined to use BLAKE2.

In short, BLAKE2 already offers better security and performance, and I
predict that from now on BLAKE2 is going to look better and better and
SHA256 is going to look worse and worse.

I would like to ban SHA256 from the Zcash codebase. We should use
BLAKE2 anywhere that we might otherwise have used SHA256, and
separately we will hopefully replace the inner hash in the
coin-commitment Merkle Tree with the Ajtai subset sum hash if we get
satisfactory security analysis of that.

[jcb82]

I think it's easy to make a strong case for BLAKE over SHA-256 with the only downside being "widespread support."

What is the case for BLAKE over Keccak/SHA3 though? There are some pros and cons of Keccak vs. BLAKE, but if we laid them all would we end up making a different conclusion than the SHA3 competition did? Also even if it is close, by virtue of Keccak's previous win it will (over time) have much more widespread support.

I think the right debate to have is not BLAKE vs. SHA-256 but BLAKE vs. SHA3.

[zookozcash]

Thanks for the comment, @jcb82! I don't agree that SHA3 is a good candidate. It's very inefficient in the two contexts we care about — inside libsnark and in software on ARM chips — and it doesn't have any major advantages for us that could compensate for that. Even if you're right that SHA3 will have the most widespread support, we don't need the most widespread support! We just need adequate security analysis and implementation support, which BLAKE2 already has.

[zmanian]

I'd suggest the following phased replacement strategy for SHA256.

1. Replace SHA256 in libzerocash. Justification: No external software uses libzerocash
2. Add BLAKE2 opcode to bitcoin script and make it the preferred hash function for signatures, pay to script hash and pay to pubkey hash transactions. I'd reccomend against completely eliminating the SHA256 opcode for lightning , interledger and atomic cross chain trade compatibility.
3. Eliminate SHA256 everywhere else like TXIDs etc.

It would be cool to publicize notice of pull requests acceptance for each of the proposed phases. 2 especially contains a bunch of low hanging fruit.

[zookozcash]

Thanks, @zmanian — that seems like a very good proposal!

[jcb82]

Better performance in libsnark is a legitimate reason to prefer BLAKE over SHA3. I have no idea how they compare but if that's well established then it's a reasonable choice. I don't think hardware support on ARM will matter much in the long run.

[daira]

I'm not flatly opposed to Blake2s (I do think it's a better algorithm than SHA-256 in many technical aspects), but I'd just like to reiterate that writing and reviewing another hash implementation in libsnark will be difficult, time-consuming, and error-prone. There are many other improvements and necessary security fixes that I'd give a much higher priority than switching to Blake2s, since there is nothing actually wrong with SHA-256 for this use.

[daira]

Incidentally, I believe that NSA's semi-deprecation of SHA-256 was purely motivated by quantum resistance, and what they were recommending instead was SHA[2 or 3]-384 and -512. (The link is broken so I wasn't able to confirm that.) They're probably wrong about 384-bit hashes being necessary for quantum resistance, as Dan Bernstein has argued. [Edit: he actually argued that the Brassard-Høyer-Tapp algorithm doesn't provide an attack improving on classical methods.] Besides, Zcash can't aim for quantum resistance (yet) because there is no known practical and quantum-resistant zkSNARK construction.

[zookozcash]

If you liked this ticket, you might like zcash/zips#36 (comment)

[daira]

Sapling essentially does this. The remaining uses of SHA-256 are only in Sprout and things inherited from Bitcoin, like the difficulty filter. So I'm going to consider this ticket fixed.