Support for Tip5

[ameya-deshmukh]

@irakliyk hi, I am doing research on recursive STARKs and was wondering if support for arithmetization-oriented hash functions which are suitable for recursive verification is possible within Winterfell. I am especially looking at Tip5 and was curious to know the feasibility of adding support in Winterfell for the same. Would be more than happy to take this up as an independent task under your guidance. Thanks!

[jan-ferdinand]

@ameya-deshmukh, I like your idea and have taken the liberty to start hacking on it. The PR (#188) is not complete yet, as described in greater detail there. I'm not sure how much additional time I'll spend coding on the PR – feel free to take it as a draft for your own hacking. 😊

[ameya-deshmukh]

Wow, one of the authors of the paper himself! Glad you liked the idea. I'll be hacking on it independently and would love to compare code across implementations. Are there any specific optimizations etc that you'd like to see added which you may not have the time to implement? Would love to do it

[jan-ferdinand]

Most of the code I wrote for that PR is adapter code, i.e., getting the reference implementation of Tip5 to fit the requirements of the winterfell codebase. As far as we can tell, the reference implementation of Tip5 is in a pretty good spot right now.¹ This does not mean you shouldn't go hunting for speedups if you want to – we welcome contributions to the code base!

Additionally, it's quite possible that the adapter stuff I hacked together for the PR is not optimal. For example, I chose to go with chaining iterators instead of updating mutable slices, without knowing which of the two approaches is faster. Gut feel says that this won't be the bottleneck, but gut feeling is not a very good profiler. 😁

Footnotes

1. There is one speed improvement that we will incorporate (hopefully) within the upcoming week, but other than that, I currently know of no optimizations that we haven't implemented yet. ↩

[ameya-deshmukh]

Got it! I actually want to discuss the project I'm working on with you, what's the best channel of communication for that?

[jan-ferdinand]

I messaged you on an instant messenger. 👍