5
$\begingroup$

Recently, new hash functions were invented. Their primary purpose is serving the needs of zero-knowledge proof systems. I'm talking about Poseidon-256, Starkad-256, etc. See the paper.

What is the main advantage of those hash functions against existing ones like Blake3 or SHA3? How are those functions different?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Typically, the complexity of generating a zero-knowledge proof heavily depends on the number of multiplication gates you have in the statement. Hence, novel hash functions try to minimize the multiplicative complexity in order to ease ZKP generation. This is the high-level motivation in designing these new hash functions. $\endgroup$
    – István András Seres
    May 15 '20 at 7:14
  • $\begingroup$ Blake3 seems to be pretty simple and extremely fast. Why not use it? $\endgroup$
    – Paul Miller
    May 15 '20 at 7:39
  • $\begingroup$ I just gave a quick look at the BLAKE3 spec (hadn't seen it yet). It looks like an ARX system is at its base, and looks a lot like ChaCha20 at first sight. I have an implementation of ChaCha20 in Bulletproofs laying around, which is takes around 20k multipliers. While a ARX ciphers and hashes are probably one of the more efficient symmetric primitives in arithmetic circuits, Poseidon still does quite a bit better! $\endgroup$
    – Ruben De Smet
    May 15 '20 at 13:02
3
$\begingroup$

Let us see an example of how cryptographic hash functions are used in Zero-Knowledge Proof Systems. Following code written in Zokrates DSL Toolbox is an example of computing a Hash using Zero-Knowledge Proof systems. The programming instructions are compiled first. Then we will proceed to the setup of the arithmetic circuit through the setup. Then we export the verifier and will compute the proof. 

import "hashes/sha256/512bitPacked" as sha256packed

def main(private field a, private field b, private field c, private field d) -> (field[2]):
    h = sha256packed([a, b, c, d])
    return h

Let us also analyse another code example to construct a Pedersen Hash in the construction of a Zero-Knowledge Proof using Zokrates Toolbox. 

import "hashes/pedersen/6bit" as pedersen

def main() -> (field):

    field[6] e = [1, 1, 0, 0, 0, 0]
    field[2] d = pedersen(e)

    5483803361072598088157572477433311028290255512997784196805059543720485966024 == d[0]
    8712718144085345152615259409576985937188455136179509057889474614313734076278 == d[1]

    return 1

As we can see in these two examples, proving the knowledge of a preimage under a cryptographic hash function expressed as a circuit over a large prime field becomes one of the most computationally expensive parts in the arithmetic circuit construction in a zero-knowledge proof system. Hence all the pursuits for inventing SNARK and STARK friendly cryptographic hash functions are greeted with much of enthusiasms!

The paper mentioned in this question claims a reduction in the number of constraints per message bit than Pedersen Hash which would potentially improve the performance in the construction of polynomial commitments for ZKSNARK. Likewise, the proposed binary hash function STARKAD could be beneficial in the construction of ZKSTARK based systems in the near future.

Our hash-function Poseidon uses up to 8x fewer constraints per message bit than Pedersen Hash, whereas our binary hash-function Starkad wins by a substantial margin over the other recent designs

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.