Optimizations (maybe) worth doing

[nicola]

Construction optimization

• See this issue How to make circuits practical with 200 challenges. #157
• Check if it is worth to reduce the security (e.g. from 1% to 2% percentage of data that could be lost)

Circuit optimization

• Merkle tree last layer is the data
• Remove Pedersen MD and extend Pedersen Hash to take larger inputs
• Use pedersen with no padding Pad to 255 bits in circuits. #74
• Remove all the repeated inputs for the root hashes for drgporep
• Check if we can re-use the same challenge for all layers (@porcuquine knows)
• No need to specify double inclusion paths for commD and commR
• Pack more inclusion paths into 1 Fr. (We can safely include 6 to account for sectors of up to 4TiB: 6 * 42 = 252 < 254. Reconcile this calcultion with actual path lengths, which might be off by one.)
• Provide merkle inclusion paths for all nodes N rows deep in merkle tree, since these paths will be repeated in many inclusion proofs. Truncate inclusion proofs to terminate at already-proved nodes, and add constraints proving this was done.
• Check whether we include roots in merkle proofs, and if so don't include them as inputs to the circuit.

Witness generation optimization

• Cache the merkle tree and only pick the upper layer
• Sean's batched field inverse calculation optimization
• Parallel generation of merkle tree paths witnesses (and KDF parallelization)
• Make sloth cheaper in the forward direction by sampling a better exponent

Library/Hardware Optimization

• Running Proof Generation/Field operations on a GPU
• Optimize parallelization techniques in Bellman
• Improve multi-exponentiation

Sector Storage

Preprocessing (bit-padding)

• Use bit-shifting instead of BitVec to reduce operations per byte (if bit-padding proves slow).
• Use mmap
• Parallelize
• Parallel Merkle Tree generation
• Amortize Merkle Tree generation using Blake2s

General

• Use fixed size arrays instead of vectors where possible [perf] Use fixed size arrays instead of vectors where possible #54

[dignifiedquire]

Compare using xor vs addition for the encoding function here:

rust-fil-proofs/storage-proofs/src/crypto/sloth.rs

Line 26 in 41d7fe9

pub fn encode<E: Engine>(key: &E::Fr, plaintext: &E::Fr, rounds: usize) -> E::Fr {