viff

changeset 667:e41ce22ed035

Basic support for pre-processing. This adds support for pre-processing to the BasicRuntime. The idea is that a protocol run records the needed data using the preprocess decorator, and using a description of this data, the runtime can begin the following executions generating it. The data needed is recorded based on the methods name and program counter, so this assumes that every execution produces the same tree of program counters. This is true for simple programs like the benchmark, but need not be true for programs that branch on the input data. Please see Issue 3: http://tracker.viff.dk/issue3.
author Martin Geisler <mg@daimi.au.dk>
date Sun, 13 Apr 2008 23:24:46 +0200
parents 876f98730e4c
children 66e0f8fdac7c
files apps/benchmark.py viff/runtime.py viff/test/test_active_runtime.py
diffstat 3 files changed, 138 insertions(+), 12 deletions(-) [+]
line diff
     1.1 --- a/apps/benchmark.py	Sun Apr 13 22:16:28 2008 +0200
     1.2 +++ b/apps/benchmark.py	Sun Apr 13 23:24:46 2008 +0200
     1.3 @@ -57,6 +57,7 @@
     1.4  import time
     1.5  from optparse import OptionParser
     1.6  import operator
     1.7 +from pprint import pprint
     1.8  
     1.9  from twisted.internet import reactor
    1.10  
    1.11 @@ -122,9 +123,23 @@
    1.12  class Benchmark:
    1.13  
    1.14      def __init__(self, rt, operation):
    1.15 -        print "Runtime ready, starting protocol"
    1.16          self.rt = rt
    1.17          self.operation = operation
    1.18 +
    1.19 +        if isinstance(self.rt, ActiveRuntime) and self.operation == operator.mul:
    1.20 +            print "Starting preprocessing"
    1.21 +            program_desc = {
    1.22 +                ("generate_triples", (Zp,)):
    1.23 +                    [(i, 1, 0) for i in range(3 + 2*count, 3 + 3*count)]
    1.24 +                }
    1.25 +            preproc = rt.preprocess(program_desc)
    1.26 +            preproc.addCallback(self.begin)
    1.27 +        else:
    1.28 +            print "Need no preprocessing"
    1.29 +            self.begin(None)
    1.30 +
    1.31 +    def begin(self, _):
    1.32 +        print "Runtime ready, starting protocol"
    1.33          self.a_shares = [self.rt.prss_share_random(Zp) for _ in range(count)]
    1.34          self.b_shares = [self.rt.prss_share_random(Zp) for _ in range(count)]
    1.35          shares_ready = gather_shares(self.a_shares + self.b_shares)
    1.36 @@ -151,6 +166,11 @@
    1.37  
    1.38      def finished(self, _):
    1.39          print "Finished, synchronizing shutdown."
    1.40 +
    1.41 +        if self.rt._needed_data:
    1.42 +            print "Missing pre-processed data:"
    1.43 +            pprint(self.rt._needed_data)
    1.44 +
    1.45          sync = self.rt.synchronize()
    1.46          sync.addCallback(self.shutdown)
    1.47  
     2.1 --- a/viff/runtime.py	Sun Apr 13 22:16:28 2008 +0200
     2.2 +++ b/viff/runtime.py	Sun Apr 13 23:24:46 2008 +0200
     2.3 @@ -44,7 +44,7 @@
     2.4  from viff.util import wrapper, rand
     2.5  
     2.6  from twisted.internet import reactor
     2.7 -from twisted.internet.defer import Deferred, DeferredList, gatherResults
     2.8 +from twisted.internet.defer import Deferred, DeferredList, gatherResults, succeed
     2.9  from twisted.internet.protocol import ClientFactory, ServerFactory
    2.10  from twisted.protocols.basic import Int16StringReceiver
    2.11  
    2.12 @@ -370,6 +370,38 @@
    2.13      return inc_pc_wrapper
    2.14  
    2.15  
    2.16 +def preprocess(generator):
    2.17 +    """Track calls to this method.
    2.18 +
    2.19 +    The decorated method will be replaced with a proxy method which
    2.20 +    first tries to get the data needed from C{self._pool}, and if that
    2.21 +    fails it falls back to the original method.
    2.22 +
    2.23 +    The C{generator} method is only used to record where the data
    2.24 +    should be generated from, the method is not actually called.
    2.25 +
    2.26 +    @param generator: Use this method as the generator for
    2.27 +    pre-processed data.
    2.28 +    @type generator: C{str}
    2.29 +    """
    2.30 +
    2.31 +    def preprocess_decorator(method):
    2.32 +
    2.33 +        @wrapper(method)
    2.34 +        def preprocess_wrapper(self, *args, **kwargs):
    2.35 +            pc = tuple(self.program_counter)
    2.36 +            try:
    2.37 +                return self._pool[pc]
    2.38 +            except KeyError:
    2.39 +                key = (generator, args)
    2.40 +                pcs = self._needed_data.setdefault(key, [])
    2.41 +                pcs.append(pc)
    2.42 +                return method(self, *args, **kwargs)
    2.43 +
    2.44 +        return preprocess_wrapper
    2.45 +    return preprocess_decorator
    2.46 +
    2.47 +
    2.48  class BasicRuntime:
    2.49      """Basic VIFF runtime with no crypto.
    2.50  
    2.51 @@ -426,6 +458,11 @@
    2.52              from twisted.internet import defer
    2.53              defer.setDebugging(True)
    2.54  
    2.55 +        #: Pool of preprocessed data.
    2.56 +        self._pool = {}
    2.57 +        #: Description of needed preprocessed data.
    2.58 +        self._needed_data = {}
    2.59 +
    2.60          #: Current program counter.
    2.61          #:
    2.62          #: Whenever a share is sent over the network, it must be
    2.63 @@ -607,6 +644,72 @@
    2.64          self._expect_data(peer_id, "share", share)
    2.65          return share
    2.66  
    2.67 +    @increment_pc
    2.68 +    def preprocess(self, program):
    2.69 +        """Generate preprocess material.
    2.70 +
    2.71 +        The C{program} specifies which methods to call and with which
    2.72 +        arguments. The generator methods called must adhere to the
    2.73 +        following interface:
    2.74 +
    2.75 +          - They must return a C{(int, Deferred)} tuple where the
    2.76 +            C{int} tells us how many items of pre-processed data the
    2.77 +            Deferred will yield.
    2.78 +
    2.79 +          - The Deferred must yield a C{list} of the promissed length.
    2.80 +
    2.81 +          - The C{list} contains the actual data. This data can be
    2.82 +            either a Deferred or a C{tuple} of Deferreds.
    2.83 +
    2.84 +        The L{ActiveRuntime.generate_triples} method is an example of
    2.85 +        a method fulfilling this interface.
    2.86 +
    2.87 +        @param program: A description of the needed data.
    2.88 +        @type program: C{dict} mapping C{(str, args)} tuples to
    2.89 +        program counters
    2.90 +        """
    2.91 +
    2.92 +        def update(results, program_counters):
    2.93 +            # We concatenate the sub-lists in results.
    2.94 +            results = sum(results, [])
    2.95 +
    2.96 +            wait_list = []
    2.97 +            for result in results:
    2.98 +                # We allow pre-processing methods to return tuples of
    2.99 +                # shares or individual shares as their result. Here we
   2.100 +                # deconstruct result (if possible) and wait on its
   2.101 +                # individual parts.
   2.102 +                if isinstance(result, tuple):
   2.103 +                    wait_list.extend(result)
   2.104 +                else:
   2.105 +                    wait_list.append(result)
   2.106 +
   2.107 +            # The pool must map program counters to Deferreds to
   2.108 +            # present a uniform interface for the functions we
   2.109 +            # pre-process.
   2.110 +            results = map(succeed, results)
   2.111 +
   2.112 +            # Update the pool with pairs of program counter and data.
   2.113 +            self._pool.update(zip(program_counters, results))
   2.114 +            # Return a Deferred that waits on the individual results.
   2.115 +            # This is important to make it possible for the players to
   2.116 +            # avoid starting before the pre-processing is complete.
   2.117 +            return gatherResults(wait_list)
   2.118 +
   2.119 +        wait_list = []
   2.120 +        for ((generator, args), program_counters) in program.iteritems():
   2.121 +            print "Preprocessing %s (%d items)" % (generator, len(program_counters))
   2.122 +            func = getattr(self, generator)
   2.123 +            results = []
   2.124 +            items = 0
   2.125 +            while items < len(program_counters):
   2.126 +                item_count, result = func(*args)
   2.127 +                items += item_count
   2.128 +                results.append(result)
   2.129 +            ready = gatherResults(results)
   2.130 +            ready.addCallback(update, program_counters)
   2.131 +            wait_list.append(ready)
   2.132 +        return DeferredList(wait_list)
   2.133  
   2.134  class Runtime(BasicRuntime):
   2.135      """The VIFF runtime.
   2.136 @@ -1206,12 +1309,11 @@
   2.137          return result
   2.138  
   2.139      @increment_pc
   2.140 +    @preprocess("generate_triples")
   2.141      def get_triple(self, field):
   2.142 -        # TODO: This is of course insecure... We should move
   2.143 -        # generate_triples to a preprocessing step and draw the
   2.144 -        # triples from a pool instead. Also, using only the first
   2.145 -        # triple is quite wasteful...
   2.146 -        result = self.generate_triples(field)
   2.147 +        # This is a waste, but this function is only called if there
   2.148 +        # are no pre-processed triples left.
   2.149 +        count, result = self.generate_triples(field)
   2.150          result.addCallback(lambda triples: triples[0])
   2.151          return result
   2.152  
   2.153 @@ -1220,10 +1322,12 @@
   2.154          """Generate multiplication triples.
   2.155  
   2.156          These are random numbers M{a}, M{b}, and M{c} such that M{c =
   2.157 -        ab}.
   2.158 +        ab}. This function can be used in pre-processing.
   2.159  
   2.160 -        @return: C{list} of 3-tuples.
   2.161 -        @returntype: C{list} of C{(Share, Share, Share)}
   2.162 +        @return: Number of triples returned and a Deferred which will
   2.163 +        yield a C{list} of 3-tuples.
   2.164 +        @returntype: (C{int}, C{list} of Deferred C{(Share, Share,
   2.165 +        Share)})
   2.166          """
   2.167          n = self.num_players
   2.168          t = self.threshold
   2.169 @@ -1250,7 +1354,7 @@
   2.170  
   2.171          result = gatherResults([single_a, single_b, double_c])
   2.172          self.schedule_callback(result, make_triple)
   2.173 -        return result
   2.174 +        return T, result
   2.175  
   2.176      @increment_pc
   2.177      def _broadcast(self, sender, message=None):
     3.1 --- a/viff/test/test_active_runtime.py	Sun Apr 13 22:16:28 2008 +0200
     3.2 +++ b/viff/test/test_active_runtime.py	Sun Apr 13 23:24:46 2008 +0200
     3.3 @@ -132,6 +132,8 @@
     3.4                  results.append(result)
     3.5              return gatherResults(results)
     3.6  
     3.7 -        triples = runtime.generate_triples(self.Zp)
     3.8 +        count, triples = runtime.generate_triples(self.Zp)
     3.9 +        self.assertEquals(count, runtime.num_players - 2*runtime.threshold)
    3.10 +
    3.11          triples.addCallback(check)
    3.12          return triples