changeset 863:5e2a190baf4a

Some documentation on preprocessing.
author Martin Geisler <mg@daimi.au.dk>
date Thu, 31 Jul 2008 21:18:55 +0200
parents 14be5568022c
children 175a77921da9
files doc/implementation.txt doc/preprocessing.txt doc/runtime.txt
diffstat 3 files changed, 92 insertions(+), 0 deletions(-) [+]
line wrap: on
line diff
--- a/doc/implementation.txt	Thu Jul 31 19:23:05 2008 +0200
+++ b/doc/implementation.txt	Thu Jul 31 21:18:55 2008 +0200
@@ -16,6 +16,7 @@
    prss
    config
    program-counters
+   preprocessing
    coding-style
    development
    unit-testing
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/doc/preprocessing.txt	Thu Jul 31 21:18:55 2008 +0200
@@ -0,0 +1,89 @@
+
+Preprocessing
+=============
+
+Some of the protocols in VIFF use auxiliary data which does not depend
+on the protocol inputs. Since the values does not depend on the actual
+inputs we can calculate them in advance in a *pre-processing* step.
+This is also called an *offline* calculation, not because it does not
+require network communication, but because it can be done outside of
+the peek hours.
+
+The best example is the multiplication protocol which is secure
+against active adversaries. It uses random numbers *a*, *b*, and *c*
+where *ab = c*. Since they are random they cannot depend on the inputs
+to the multiplication and we can thus safely calculate them in
+advance.
+
+
+Knowing how much to preprocess
+------------------------------
+
+When a program is invoked for the first time we cannot know how much
+preprocessed data it will need and all data must therefore be produced
+on demand (online). The problem is that there is no parsing step in
+the execution of a program using VIFF, so we have no chance of
+analysing the program in advance and since Python is a general
+Turing-complete programming language doing analysis would probably end
+up either impossible or very conservative meaning that the estimate
+would be higher than the actual need for would preprocessed data.
+
+What we can do is to monitor the program when it runs and note when
+preprocessed data was needed and how much. We then use this data on
+the next run.
+
+We record the following:
+
+* the program counter,
+* the function that produced the data,
+* the arguments used function.
+
+Using this information the next program run can start with a
+preprocessing phase where data is produced and associated with the
+program counters stored.
+
+This will obviously only work if executing the program always produces
+the same trace of program counters. And indeed a secure program must
+behave like this, for if the program counter trace changed depending
+on the (private) inputs to the program, then this would be observable
+from the outside and thus leak information.
+
+One can therefore build a program and test it on toy-input to
+establish the program counter trace. This trace can then be used when
+the program is deployed and used on real data.
+
+Branching programs
+~~~~~~~~~~~~~~~~~~
+
+The above is not entirely true for a program like the double auction.
+This program branches on values opened during the execution and could
+thus potentially produce different traces on each run while still
+being secure.
+
+There is no problem in this particular case since the double auction
+has the same trace in each branch, but this is not true in general. We
+will need to find a better mechanism for dealing with programs that
+intentionally leak information when executing and branch to different
+parts.
+
+
+Implementing preprocessing
+--------------------------
+
+Preprocessing is implemented using two tools: the
+:func:`viff.runtime.preprocess` decorator is used on methods that
+produce data which can be preprocessed. It replaces the methods with
+proxies which will attempt to return preprocessed data. If the data
+could not be satisfied from the pool of preprocessed data, then the
+program counter and function arguments are stored before falling back
+to calculating the data online using the original method.
+
+To generate preprocessed data based on a trace of program counters one
+must call the :meth:`viff.runtime.BasicRuntime.preprocess` method. It
+returns a :class:`Deferred` which triggers when all preprocessed data
+is ready which means that the online part of the computation can
+begin.
+
+Instead of starting the online phase immediately, one could also
+choose to store the preprocessed data for later use, but this has not
+been implemented yet.
--- a/doc/runtime.txt	Thu Jul 31 19:23:05 2008 +0200
+++ b/doc/runtime.txt	Thu Jul 31 21:18:55 2008 +0200
@@ -23,6 +23,8 @@
 
    .. autofunction:: increment_pc
 
+   .. autofunction:: preprocess
+
    .. autofunction:: create_runtime
 
    .. autoclass:: BasicRuntime