Created: 26th February 2023 by @Anonymous
This document is about how to run more benchmarks that may give more precise insights about the use of Lookups for Filecoin.
TL;DR: Somebody with engineering expertise may have to run them; this doc explains what/how
Background
- Background on the approach based on lookups (read this first if you are unfamiliar with what we want or you need a brush up)
- Background on the source of other numbers I provide for lookups below (see comments in that doc)
- Baloo code (in Baloo folder)
caulk-dev-main(1).zip
The experiments to be run
The Sealing step in Filecoin consists of approximately 77K SHA computations (I will refer to this number as N). We will ignore non-sha computations. We will consider N’ = N/10 for Groth16 since what we do is to run 10 Groth16 in parallel in Filecoin.
The way to approximate this is is to run on the same machine:
- run prover for Groth16 on N’ SHAs
- run the following on the same machine:
- Baloo for a table size $2^{16}$ with number of lookups $\ell = 4\cdot10^3\cdot N \approx 3 \cdot 10^8$
- this is roughly 4000 lookups per SHA multiplied by the number of SHA (see background documents)
- one multiexponentiation of size $\ell$
- this corresponds to the Kiltz-Wee proof required to link the lookup with Groth16
- Take the max between the two above and call this time T’
How to draw a comparison and understand if this is a dead-end
If $T’ < T/4$ or less then it is possible to Lookup approach is promising (Baloo is unoptimized). Otherwise it is not worth it until lookup techniques improve.