The Tip5 Hash Function for Recursive STARKs

TL;DR

This paper presents a new hash function optimized for recursive Starks, providing fast and secure hashing for Merkle trees and the Fiat-Shamir transform.

Transcript

foreign a window select window or screen slides allow very good so the tip 5 hash function for recursive starts uh this is a paper written jointly by myself and for co-authors uh Alexander lemons young Ferdinand Sauer bobbin threadbear and Al kindy you are listening to the voice of Alan ship yenyets um and if you look at the paper you will notice t... Read More

Key Insights

• 🧩 The motivation behind designing a new hash function is the need for fast and arithmetizable hash functions for recursive Stark proofs in building Merkle trees.
• 🔒 Function like Mimsy, Rescue, Poseidon, etc., are secure but not designed with arithmetization in mind, making them unsuitable for the purpose.
• 🎛️ The reinforced concrete hash function, while fast, has non-uniform rounds, making it less desirable for arithmetization.
• 🔡 The new hash function, called Tip5, is designed for the Goldilocks field, which is highly arithmetizable and efficient for number theory operations.
• ️ Tip5 is significantly faster than other hash functions like Rescue Prime and Poseidon, making it a preferable choice for a Stark prover.
• 📊 The performance gain of Tip5 in a Trident VM is around 2.68x, with an observed speedup of over 3x in practice, justifying its adoption.
• ⚙️ A key component of Tip5 is the use of lookup gates, which are robust and enhance security in hash functions.
• 🔍 The Cascade table, used in Tip5, reduces the number of columns and provides a trade-off between performance and security. However, it has a limit beyond which it becomes infeasible.

Questions & Answers

Q: Why is it important for the hash function used in recursive Starks to be arithmetizable?

The hash function needs to be arithmetizable because it requires proving the correct evaluation of the hash function repeatedly. Arithmetization allows for efficient and secure evaluation of the hash function in recursive Starks.

Q: What makes the Tip5 hash function different from existing hash functions like Poseidon and Rescue Prime?

The Tip5 hash function utilizes lookup gates and a specific round structure to achieve fast and secure hashing. It has a uniform round structure, making it easily arithmetizable, and it also provides efficient support for building Merkle trees.

Q: How does the performance of Tip5 compare to other hash functions in the context of recursive Starks?

Tip5 outperforms other hash functions like Poseidon and Rescue Prime in terms of performance in recursive Starks. It provides almost a factor of three faster proof generation and compression of execution traces in Trident VM.

Q: Is there any potential vulnerability in the use of lookup gates in hash functions?

Lookup gates are generally considered a robust security enhancement, as they make algebraic attacks infeasible. However, the security of a hash function depends on the specifics of the lookup gate and its interaction with the rest of the construction. Analysis and evaluation are necessary to ensure the absence of vulnerabilities.

Summary & Key Takeaways

• The motivation behind designing a new hash function is to meet the high hashing demands of recursive Starks, which require a fast and arithmetizable hash function for proving correct evaluations.

• Existing hash functions like Blake3 and Chacha20 were not designed with arithmetization in mind, so a new hash function optimized for recursive Starks was needed.

• The proposed hash function, called Tip5, utilizes lookup gates and a specific round structure to achieve fast and secure hashing, with significant performance improvements compared to other hash functions like Poseidon and Rescue Prime.