[viff-devel] Optimizing preprocessing

[Marcel Keller]

Dear friends of VIFF,

I have a proprosal to optimize preprocessing in VIFF, which I would like 
to put up for discussion.

Notation:
- D(x): a Deferred object whose callback function will be called with x
- S(x): same for a Share object
- F: a FieldElement object
- [x, ...]: a Python list
- (x, ...): a Python tuple

Current situation:
The two generate_triples() functions in the active runtimes return
n, D([(S(F), S(F), S(F)), ...]),
where n denotes the length of the list. Runtime.preprocess() puts one 
D(S(F), S(F), S(F)) per program counter in the preprocessing pool and 
uses util.deep_wait() to return a Deferred whose callback is called when 
all field elements are available.

The get_triple() functions return
D(S(F), S(F), S(F)),
either taken from the preprocessing pool, or by calling 
generate_triples() and adding an extra callback to extract the first triple.

My proposal:
The generate_triples() functions return
[D([F, F, F]), ...],
and Runtime.preprocess() puts one [F, F, F] per program counter in the 
preprocessing pool. There is no need for deep_wait, we can just use 
gatherResults on the Deferreds return by the generator functions. The 
generator functions can use gatherResults to get D([F, F, F]) from 
[S(F), S(F), S(F)].

The get_triple() functions return
[F, F, F], True              if there is a triple in the pool, and
[S(F), S(F), S(F)], False    otherwise.
For the multiplication in BasicActiveRuntime it doesn't make a 
difference whether FieldElements or Shares are returned. Future 
applications which require Shares can wrap the FieldElements in Shares 
if the Boolean is True.

Benchmarks:
- 10000 multiplications in parallel with active security using PRSS
   - 4% faster preprocessing
   - 5% faster online operation
   - 50 MB less memory used
- 10 AES blocks in parallel using masked exponentiation with active 
security using PRSS
   - 10% faster preprocessing
   - 10% faster online operation
   - 140 MB less memory used

Further considerations:
- I don't see any problem for replacing FieldElement with anything that 
does not contain Deferreds in any form.
- Probably, it would also be possible to leave the generator functions 
as they are and use something similar to deep_wait(). However, I 
consider it as an overhead.
- One could also always wrap the FieldElements in Shares, but this would 
again be an overhead.

Best regards,
Marcel