viff

changeset 1261:ed2d02202af0

Merged with Janus.
author Marcel Keller <mkeller@cs.au.dk>
date Thu, 08 Oct 2009 14:27:37 +0200
parents 824ae3770456 4b6f9e4db99e
children f626a6dfef43
files apps/benchmark.py viff/active.py viff/paillier.py viff/passive.py viff/runtime.py
diffstat 12 files changed, 2765 insertions(+), 118 deletions(-) [+]
line diff
     1.1 --- a/apps/benchmark.py	Wed Oct 07 15:23:12 2009 +0200
     1.2 +++ b/apps/benchmark.py	Thu Oct 08 14:27:37 2009 +0200
     1.3 @@ -63,6 +63,7 @@
     1.4  import viff.reactor
     1.5  viff.reactor.install()
     1.6  from twisted.internet import reactor
     1.7 +from twisted.internet.defer import Deferred
     1.8  
     1.9  from viff.field import GF, GF256, FakeGF
    1.10  from viff.runtime import Runtime, create_runtime, gather_shares, \
    1.11 @@ -87,25 +88,38 @@
    1.12      print "Started", what
    1.13  
    1.14  
    1.15 -def record_stop(_, what):
    1.16 +def record_stop(x, what):
    1.17      stop = time.time()
    1.18      print
    1.19      print "Total time used: %.3f sec" % (stop-start)
    1.20      print "Time per %s operation: %.0f ms" % (what, 1000*(stop-start) / count)
    1.21      print "*" * 6
    1.22 +    return x
    1.23  
    1.24 +operations = {"mul": (operator.mul,[]),
    1.25 +              "compToft05": (operator.ge, [ComparisonToft05Mixin]),
    1.26 +              "compToft07": (operator.ge, [ComparisonToft07Mixin]),
    1.27 +              "eq": (operator.eq, [ProbabilisticEqualityMixin])}
    1.28  
    1.29 -operations = ["mul", "compToft05", "compToft07", "eq"]
    1.30 +runtimes = {"PassiveRuntime": PassiveRuntime,
    1.31 +            "PaillierRuntime": PaillierRuntime, 
    1.32 +            "BasicActiveRuntime": BasicActiveRuntime}
    1.33 +
    1.34 +mixins = {"TriplesHyperinvertibleMatricesMixin" : TriplesHyperinvertibleMatricesMixin, 
    1.35 +          "TriplesPRSSMixin": TriplesPRSSMixin, 
    1.36 +          "ComparisonToft05Mixin": ComparisonToft05Mixin,
    1.37 +          "ComparisonToft07Mixin": ComparisonToft07Mixin, 
    1.38 +          "ProbabilisticEqualityMixin": ProbabilisticEqualityMixin}
    1.39  
    1.40  parser = OptionParser(usage="Usage: %prog [options] config_file")
    1.41  parser.add_option("-m", "--modulus",
    1.42                    help="lower limit for modulus (can be an expression)")
    1.43 -parser.add_option("-a", "--active", action="store_true",
    1.44 -                  help="use actively secure runtime")
    1.45 -parser.add_option("--passive", action="store_false", dest="active",
    1.46 -                  help="use passively secure runtime")
    1.47 -parser.add_option("-2", "--twoplayer", action="store_true",
    1.48 -                  help="use twoplayer runtime")
    1.49 +parser.add_option("-r", "--runtime", type="choice", choices=runtimes.keys(),
    1.50 +                  help="the name of the basic runtime to test")
    1.51 +parser.add_option("-n", "--num_players", action="store_true", dest="num_players",
    1.52 +                  help="number of players")
    1.53 +parser.add_option("--mixins", type="string",
    1.54 +                  help="operation to benchmark")
    1.55  parser.add_option("--prss", action="store_true",
    1.56                    help="use PRSS for preprocessing")
    1.57  parser.add_option("--hyper", action="store_false", dest="prss",
    1.58 @@ -114,7 +128,7 @@
    1.59                    help="corruption threshold")
    1.60  parser.add_option("-c", "--count", type="int",
    1.61                    help="number of operations")
    1.62 -parser.add_option("-o", "--operation", type="choice", choices=operations,
    1.63 +parser.add_option("-o", "--operation", type="choice", choices=operations.keys(),
    1.64                    help="operation to benchmark")
    1.65  parser.add_option("-p", "--parallel", action="store_true",
    1.66                    help="execute operations in parallel")
    1.67 @@ -122,10 +136,12 @@
    1.68                    help="execute operations in sequence")
    1.69  parser.add_option("-f", "--fake", action="store_true",
    1.70                    help="skip local computations using fake field elements")
    1.71 +parser.add_option("--args", type="string",
    1.72 +                  help="additional arguments to the runtime, the format is a comma separated list of id=value pairs e.g. --args s=1,d=0,lambda=1")
    1.73  
    1.74  parser.set_defaults(modulus=2**65, threshold=1, count=10,
    1.75 -                    active=False, twoplayer=False, prss=True,
    1.76 -                    operation=operations[0], parallel=True, fake=False)
    1.77 +                    runtime=runtimes.keys()[0], mixins="", num_players=2, prss=True,
    1.78 +                    operation=operations.keys()[0], parallel=True, fake=False)
    1.79  
    1.80  # Add standard VIFF options.
    1.81  Runtime.add_options(parser)
    1.82 @@ -158,55 +174,46 @@
    1.83  class Benchmark:
    1.84  
    1.85      def __init__(self, rt, operation):
    1.86 +        print "init"
    1.87          self.rt = rt
    1.88          self.operation = operation
    1.89 -        self.sync_preprocess()
    1.90 -
    1.91 -    def sync_preprocess(self):
    1.92 -        print "Synchronizing preprocessing"
    1.93 +        self.pc = None
    1.94          sys.stdout.flush()
    1.95          sync = self.rt.synchronize()
    1.96 +        self.doTest(sync, lambda x: x)
    1.97          self.rt.schedule_callback(sync, self.preprocess)
    1.98 +        self.doTest(sync, lambda x: self.rt.shutdown())
    1.99 +        
   1.100 +#     def sync_preprocess(self):
   1.101 +#         print "Synchronizing preprocessing"
   1.102 +#         sys.stdout.flush()
   1.103 +#         sync = self.rt.synchronize()
   1.104 +#         self.rt.schedule_callback(sync, self.preprocess)
   1.105  
   1.106 -    def preprocess(self, _):
   1.107 -        program_desc = {}
   1.108 -
   1.109 -        if isinstance(self.rt, BasicActiveRuntime):
   1.110 -            # TODO: Make this optional and maybe automatic. The
   1.111 -            # program descriptions below were found by carefully
   1.112 -            # studying the output reported when the benchmarks were
   1.113 -            # run with no preprocessing. So they are quite brittle.
   1.114 -            if self.operation == operator.mul:
   1.115 -                key = ("generate_triples", (Zp,))
   1.116 -                desc = [(i, 1, 0) for i in range(3, 3 + count)]
   1.117 -                program_desc.setdefault(key, []).extend(desc)
   1.118 -            elif isinstance(self.rt, ComparisonToft05Mixin):
   1.119 -                key = ("generate_triples", (GF256,))
   1.120 -                desc = sum([[(c, 64, i, 1, 1, 0) for i in range(2, 33)] +
   1.121 -                            [(c, 64, i, 3, 1, 0) for i in range(17, 33)]
   1.122 -                            for c in range(3 + 2*count, 3 + 3*count)],
   1.123 -                           [])
   1.124 -                program_desc.setdefault(key, []).extend(desc)
   1.125 -            elif isinstance(self.rt, ComparisonToft07Mixin):
   1.126 -                key = ("generate_triples", (Zp,))
   1.127 -                desc = sum([[(c, 2, 4, i, 2, 1, 0) for i in range(1, 33)] +
   1.128 -                            [(c, 2, 4, 99, 2, 1, 0)] +
   1.129 -                            [(c, 2, 4, i, 1, 0) for i in range(65, 98)]
   1.130 -                            for c in range(3 + 2*count, 3 + 3*count)],
   1.131 -                           [])
   1.132 -                program_desc.setdefault(key, []).extend(desc)
   1.133 -
   1.134 -        if program_desc:
   1.135 +    def preprocess(self, needed_data):
   1.136 +        print "Preprocess", needed_data
   1.137 +        if needed_data:
   1.138              print "Starting preprocessing"
   1.139              record_start("preprocessing")
   1.140 -            preproc = self.rt.preprocess(program_desc)
   1.141 +            preproc = self.rt.preprocess(needed_data)
   1.142              preproc.addCallback(record_stop, "preprocessing")
   1.143 -            self.rt.schedule_callback(preproc, self.begin)
   1.144 +            return preproc
   1.145          else:
   1.146              print "Need no preprocessing"
   1.147 -            self.begin(None)
   1.148 +            return None
   1.149 +
   1.150 +    def doTest(self, d, termination_function):
   1.151 +        print "doTest", self.rt.program_counter
   1.152 +        self.rt.schedule_callback(d, self.begin)
   1.153 +        self.rt.schedule_callback(d, self.sync_test)
   1.154 +#         self.rt.schedule_callback(d, self.countdown, 3)
   1.155 +        self.rt.schedule_callback(d, self.run_test)
   1.156 +        self.rt.schedule_callback(d, self.sync_test)
   1.157 +        self.rt.schedule_callback(d, self.finished, termination_function)
   1.158 +        return d
   1.159  
   1.160      def begin(self, _):
   1.161 +        print "begin", self.rt.program_counter
   1.162          print "Runtime ready, generating shares"
   1.163          self.a_shares = []
   1.164          self.b_shares = []
   1.165 @@ -220,43 +227,49 @@
   1.166              self.a_shares.append(self.rt.input([inputter], Zp, a))
   1.167              self.b_shares.append(self.rt.input([inputter], Zp, b))
   1.168          shares_ready = gather_shares(self.a_shares + self.b_shares)
   1.169 -        self.rt.schedule_callback(shares_ready, self.sync_test)
   1.170 +        return shares_ready
   1.171  
   1.172 -    def sync_test(self, _):
   1.173 +    def sync_test(self, x):
   1.174          print "Synchronizing test start."
   1.175          sys.stdout.flush()
   1.176          sync = self.rt.synchronize()
   1.177 -        self.rt.schedule_callback(sync, self.countdown, 3)
   1.178 +        self.rt.schedule_callback(sync, lambda y: x)
   1.179 +        return sync
   1.180  
   1.181 -    def countdown(self, _, seconds):
   1.182 -        if seconds > 0:
   1.183 -            print "Starting test in %d" % seconds
   1.184 -            sys.stdout.flush()
   1.185 -            reactor.callLater(1, self.countdown, None, seconds - 1)
   1.186 -        else:
   1.187 -            print "Starting test now"
   1.188 -            sys.stdout.flush()
   1.189 -            self.run_test(None)
   1.190 +#     def countdown(self, _, seconds):
   1.191 +#         if seconds > 0:
   1.192 +#             print "Starting test in %d" % seconds
   1.193 +#             sys.stdout.flush()
   1.194 +#             reactor.callLater(1, self.countdown, None, seconds - 1)
   1.195 +#         else:
   1.196 +#             print "Starting test now"
   1.197 +#             sys.stdout.flush()
   1.198 +#             self.run_test(None)
   1.199  
   1.200      def run_test(self, _):
   1.201          raise NotImplemented("Override this abstract method in a sub class.")
   1.202  
   1.203 -    def finished(self, _):
   1.204 +    def finished(self, needed_data, termination_function):
   1.205          sys.stdout.flush()
   1.206  
   1.207          if self.rt._needed_data:
   1.208              print "Missing pre-processed data:"
   1.209 -            for (func, args), pcs in self.rt._needed_data.iteritems():
   1.210 +            for (func, args), pcs in needed_data.iteritems():
   1.211                  print "* %s%s:" % (func, args)
   1.212                  print "  " + pformat(pcs).replace("\n", "\n  ")
   1.213  
   1.214 -        self.rt.shutdown()
   1.215 +        return termination_function(needed_data)
   1.216  
   1.217  # This class implements a benchmark where run_test executes all
   1.218  # operations in parallel.
   1.219  class ParallelBenchmark(Benchmark):
   1.220  
   1.221 -    def run_test(self, _):
   1.222 +    def run_test(self, shares):
   1.223 +        print "rt", self.rt.program_counter, self.pc
   1.224 +        if self.pc != None:
   1.225 +            self.rt.program_counter = self.pc
   1.226 +        else:
   1.227 +            self.pc = list(self.rt.program_counter)
   1.228          c_shares = []
   1.229          record_start("parallel test")
   1.230          while self.a_shares and self.b_shares:
   1.231 @@ -266,60 +279,51 @@
   1.232  
   1.233          done = gather_shares(c_shares)
   1.234          done.addCallback(record_stop, "parallel test")
   1.235 -        self.rt.schedule_callback(done, self.finished)
   1.236 +        def f(x):
   1.237 +            needed_data = self.rt._needed_data
   1.238 +            self.rt._needed_data = {}
   1.239 +            return needed_data
   1.240 +        done.addCallback(f)
   1.241 +        return done
   1.242 +
   1.243  
   1.244  # A benchmark where the operations are executed one after each other.
   1.245  class SequentialBenchmark(Benchmark):
   1.246  
   1.247 -    def run_test(self, _):
   1.248 +    def run_test(self, _, termination_function, d):
   1.249          record_start("sequential test")
   1.250 -        self.single_operation(None)
   1.251 +        self.single_operation(None, termination_function)
   1.252  
   1.253 -    def single_operation(self, _):
   1.254 +    def single_operation(self, _, termination_function):
   1.255          if self.a_shares and self.b_shares:
   1.256              a = self.a_shares.pop()
   1.257              b = self.b_shares.pop()
   1.258              c = self.operation(a, b)
   1.259 -            self.rt.schedule_callback(c, self.single_operation)
   1.260 +            self.rt.schedule_callback(c, self.single_operation, termination_function)
   1.261          else:
   1.262              record_stop(None, "sequential test")
   1.263 -            self.finished(None)
   1.264 +            self.finished(None, termination_function)
   1.265  
   1.266 -mixins = []
   1.267 -if options.twoplayer:
   1.268 -    # Then there is just one possible runtime:
   1.269 -    operation = operator.mul
   1.270 -    base_runtime_class = PaillierRuntime
   1.271 -else:
   1.272 -    # There are several options for a multiplayer runtime:
   1.273 -    if options.active:
   1.274 -        base_runtime_class = BasicActiveRuntime
   1.275 -        if options.prss:
   1.276 -            mixins.append(TriplesPRSSMixin)
   1.277 -        else:
   1.278 -            mixins.append(TriplesHyperinvertibleMatricesMixin)
   1.279 -    else:
   1.280 -        base_runtime_class = PassiveRuntime
   1.281 +# Identify the base runtime class.
   1.282 +base_runtime_class = runtimes[options.runtime]
   1.283  
   1.284 -    if options.operation == "mul":
   1.285 -        operation = operator.mul
   1.286 -    elif options.operation == "compToft05":
   1.287 -        operation = operator.ge
   1.288 -        mixins.append(ComparisonToft05Mixin)
   1.289 -    elif options.operation == "compToft07":
   1.290 -        operation = operator.ge
   1.291 -        mixins.append(ComparisonToft07Mixin)
   1.292 -    elif options.operation == "eq":
   1.293 -        operation = operator.eq
   1.294 -        mixins.append(ProbabilisticEqualityMixin)
   1.295 +# Identify the additional mixins.
   1.296 +actual_mixins = []
   1.297 +if options.mixins != "":
   1.298 +    actual_mixins = [mixins[mixin] for mixin in options.mixins.split(',')]
   1.299 +
   1.300 +
   1.301 +# Identify the operation and it mixin dependencies.
   1.302 +operation = operations[options.operation][0]
   1.303 +actual_mixins += operations[options.operation][1]
   1.304  
   1.305  print "Using the base runtime: %s." % base_runtime_class
   1.306 -if mixins:
   1.307 +if actual_mixins:
   1.308      print "With the following mixins:"
   1.309 -    for mixin in mixins:
   1.310 +    for mixin in actual_mixins:
   1.311          print "- %s" % mixin
   1.312  
   1.313 -runtime_class = make_runtime_class(base_runtime_class, mixins)
   1.314 +runtime_class = make_runtime_class(base_runtime_class, actual_mixins)
   1.315  
   1.316  if options.parallel:
   1.317      benchmark = ParallelBenchmark
   1.318 @@ -328,6 +332,19 @@
   1.319  
   1.320  pre_runtime = create_runtime(id, players, options.threshold,
   1.321                               options, runtime_class)
   1.322 +
   1.323 +def update_args(runtime, options):
   1.324 +    args = {}
   1.325 +    if options.args != "":
   1.326 +        for arg in options.args.split(','):
   1.327 +            id, value = arg.split('=')
   1.328 +            args[id] = long(value)
   1.329 +        runtime.setArgs(args)
   1.330 +    return runtime
   1.331 +
   1.332 +
   1.333 +pre_runtime.addCallback(update_args, options)
   1.334 +
   1.335  pre_runtime.addCallback(benchmark, operation)
   1.336  
   1.337  print "#### Starting reactor ###"
     2.1 --- a/viff/active.py	Wed Oct 07 15:23:12 2009 +0200
     2.2 +++ b/viff/active.py	Thu Oct 08 14:27:37 2009 +0200
     2.3 @@ -28,7 +28,7 @@
     2.4  from viff.matrix import Matrix, hyper
     2.5  from viff.passive import PassiveRuntime
     2.6  from viff.runtime import Share, preprocess, gather_shares
     2.7 -from viff.runtime import ECHO, READY, SEND
     2.8 +from viff.constants import ECHO, READY, SEND
     2.9  
    2.10  
    2.11  class BrachaBroadcastMixin:
    2.12 @@ -378,11 +378,11 @@
    2.13      def get_triple(self, field):
    2.14          # This is a waste, but this function is only called if there
    2.15          # are no pre-processed triples left.
    2.16 -        count, result = self.generate_triples(field)
    2.17 +        count, result = self.generate_triples(field, quantity=1)
    2.18          result.addCallback(lambda triples: triples[0])
    2.19          return result
    2.20  
    2.21 -    def generate_triples(self, field):
    2.22 +    def generate_triples(self, field, quantity):
    2.23          """Generate multiplication triples.
    2.24  
    2.25          These are random numbers *a*, *b*, and *c* such that ``c =
    2.26 @@ -436,6 +436,8 @@
    2.27          Returns a tuple with the number of triples generated and a
    2.28          Deferred which will yield a singleton-list with a 3-tuple.
    2.29          """
    2.30 +        quantity = min(quantity, 20)
    2.31 +
    2.32          a_t = self.prss_share_random_multi(field, quantity)
    2.33          b_t = self.prss_share_random_multi(field, quantity)
    2.34          r_t, r_2t = self.prss_double_share(field, quantity)
     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/viff/constants.py	Thu Oct 08 14:27:37 2009 +0200
     3.3 @@ -0,0 +1,34 @@
     3.4 +# -*- coding: utf-8 -*-
     3.5 +#
     3.6 +# Copyright 2009 VIFF Development Team.
     3.7 +#
     3.8 +# This file is part of VIFF, the Virtual Ideal Functionality Framework.
     3.9 +#
    3.10 +# VIFF is free software: you can redistribute it and/or modify it
    3.11 +# under the terms of the GNU Lesser General Public License (LGPL) as
    3.12 +# published by the Free Software Foundation, either version 3 of the
    3.13 +# License, or (at your option) any later version.
    3.14 +#
    3.15 +# VIFF is distributed in the hope that it will be useful, but WITHOUT
    3.16 +# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
    3.17 +# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
    3.18 +# Public License for more details.
    3.19 +#
    3.20 +# You should have received a copy of the GNU Lesser General Public
    3.21 +# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
    3.22 +
    3.23 +__docformat__ = "restructuredtext"
    3.24 +
    3.25 +# Constants used for communication.
    3.26 +SHARE    = 0
    3.27 +ECHO     = 1
    3.28 +READY    = 2
    3.29 +SEND     = 3
    3.30 +PAILLIER = 4
    3.31 +TEXT     = 5
    3.32 +
    3.33 +# Used by the HashBroadcastMixin
    3.34 +INCONSISTENTHASH = 6
    3.35 +OK               = 7
    3.36 +HASH             = 8
    3.37 +SIGNAL           = 9
     4.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     4.2 +++ b/viff/hash_broadcast.py	Thu Oct 08 14:27:37 2009 +0200
     4.3 @@ -0,0 +1,167 @@
     4.4 +#!/usr/bin/env python
     4.5 +
     4.6 +# Copyright 2009 VIFF Development Team.
     4.7 +#
     4.8 +# This file is part of VIFF, the Virtual Ideal Functionality Framework.
     4.9 +#
    4.10 +# VIFF is free software: you can redistribute it and/or modify it
    4.11 +# under the terms of the GNU Lesser General Public License (LGPL) as
    4.12 +# published by the Free Software Foundation, either version 3 of the
    4.13 +# License, or (at your option) any later version.
    4.14 +#
    4.15 +# VIFF is distributed in the hope that it will be useful, but WITHOUT
    4.16 +# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
    4.17 +# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
    4.18 +# Public License for more details.
    4.19 +#
    4.20 +# You should have received a copy of the GNU Lesser General Public
    4.21 +# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
    4.22 +
    4.23 +from twisted.internet.defer import gatherResults, Deferred, DeferredList
    4.24 +
    4.25 +from hashlib import sha1
    4.26 +from viff.constants import TEXT, INCONSISTENTHASH, OK, HASH, SIGNAL
    4.27 +
    4.28 +error_msg = "Player %i, has received an inconsistent hash %s."
    4.29 +
    4.30 +class InconsistentHashException(Exception):
    4.31 +    pass
    4.32 +
    4.33 +class HashBroadcastMixin:
    4.34 +    """A non-consistent broadcast scheme mainly useful for full threshold security.
    4.35 +
    4.36 +    A value is send using `send_value` and when received a hash is generated and
    4.37 +    exchanged among the receivers. If a receiver receives a hash which is not equal
    4.38 +    to the one he generated, then he sends an error signal to the others and 
    4.39 +    they stop the computation. Else he sends an ok signal and the computation continues."""
    4.40 +
    4.41 +    def _send_message(self, pc, sender, receivers, message):
    4.42 +        for peer_id in receivers:
    4.43 +            self.protocols[peer_id].sendData(pc, TEXT, message)
    4.44 +
    4.45 +    def _receive_broadcast(self, pc, unique_pc, sender, receivers):
    4.46 +        # The result.
    4.47 +        result = Deferred()
    4.48 +        # The message store.
    4.49 +        message = []
    4.50 +        # The hash store
    4.51 +        g_hashes = {}
    4.52 +        # The signal store
    4.53 +        signals = {}
    4.54 +
    4.55 +        def signal_received(signal, peer_id, message, num_receivers, hashes, signals):
    4.56 +            # Store the signal.
    4.57 +            signals[peer_id] = long(signal)
    4.58 +            # If all signals are received then check if they are OK or INCONSISTENTHASH.
    4.59 +            if num_receivers == len(signals.keys()):
    4.60 +                s = reduce(lambda x, y: OK if OK == y else INCONSISTENTHASH, signals.values())
    4.61 +                if OK == s:
    4.62 +                    # Make the result ready.
    4.63 +                    result.callback(message[0])
    4.64 +                else:
    4.65 +                    raise InconsistentHashException(error_msg % (self.id, hashes))
    4.66 +
    4.67 +        def hash_received(h, unique_pc, peer_id, receivers, a_hashes):
    4.68 +            # Store the hash.
    4.69 +            a_hashes[peer_id] = h
    4.70 +            # If we have received a hash from everybody, then compute the signal and send it.
    4.71 +            if len(receivers) == len(a_hashes.keys()):
    4.72 +                signal = OK
    4.73 +                # First we check if the hashes we received are equal to the hash we computed ourselves.
    4.74 +                for peer_id in receivers:
    4.75 +                    signal = signal if a_hashes[peer_id] == a_hashes[self.id] else INCONSISTENTHASH
    4.76 +                # Then we send the SAME signal to everybody. 
    4.77 +                for peer_id in receivers:
    4.78 +                    self.protocols[peer_id].sendData(unique_pc, SIGNAL, str(signal))           
    4.79 +            # The return value does not matter.
    4.80 +            return None
    4.81 +
    4.82 +        def message_received(m, unique_pc, message, receivers, hashes):
    4.83 +            # Store the message.
    4.84 +            message.append(m)
    4.85 +            # Compute hash of message.
    4.86 +            h = sha1(m).hexdigest()
    4.87 +            # Store hash.
    4.88 +            hashes[self.id] = h
    4.89 +            # Send the hash to all receivers.
    4.90 +            for peer_id in receivers:
    4.91 +                self.protocols[peer_id].sendData(unique_pc, HASH, str(h))
    4.92 +
    4.93 +        # Set up receivers for hashes and signals.
    4.94 +        # Note, we use the unique_pc to avoid data to cross method invocation boundaries.
    4.95 +        for peer_id in receivers:
    4.96 +            d_hash = Deferred().addCallbacks(hash_received,
    4.97 +                                             self.error_handler, 
    4.98 +                                             callbackArgs=(unique_pc, peer_id, receivers, g_hashes))
    4.99 +            self._expect_data_with_pc(unique_pc, peer_id, HASH, d_hash)
   4.100 +            d_signal = Deferred().addCallbacks(signal_received, 
   4.101 +                                               self.error_handler, 
   4.102 +                                               callbackArgs=(peer_id, message, len(receivers), 
   4.103 +                                                             g_hashes, signals))
   4.104 +            self._expect_data_with_pc(unique_pc, peer_id, SIGNAL, d_signal)
   4.105 +
   4.106 +        # Set up receiving of the message.
   4.107 +        d_message = Deferred().addCallbacks(message_received, 
   4.108 +                                            self.error_handler, 
   4.109 +                                            callbackArgs=(unique_pc, message, receivers, g_hashes))
   4.110 +        self._expect_data(sender, TEXT, d_message)
   4.111 +        return result
   4.112 +
   4.113 +
   4.114 +    def broadcast(self, senders, receivers, message=None):
   4.115 +        """Broadcast the messeage from senders to receivers.
   4.116 +
   4.117 +        Returns a list of deferreds if the calling player is among 
   4.118 +        the receivers and there are multiple senders.
   4.119 +        Returns a single element if there is only on sender, or the 
   4.120 +        calling player is among the senders only.
   4.121 +
   4.122 +        The order of the resulting list is guaranteed to be the same order 
   4.123 +        as the list of senders.
   4.124 +
   4.125 +        Senders and receivers should be lists containing the id of the senders 
   4.126 +        and receivers, respectively.
   4.127 +
   4.128 +        Note: You send implicitly to your self."""
   4.129 +        assert message is None or self.id in senders
   4.130 +
   4.131 +        self.program_counter[-1] += 1
   4.132 +
   4.133 +        pc = tuple(self.program_counter)
   4.134 +        if (self.id in receivers or self.id in senders):
   4.135 +            results = [None] * len(senders)
   4.136 +        else:
   4.137 +            results = []
   4.138 +
   4.139 +        if self.id in senders:
   4.140 +            self._send_message(pc, self.id, receivers, message)
   4.141 +
   4.142 +        if self.id in receivers:
   4.143 +            for x in xrange(len(senders)):
   4.144 +                sender = senders[x]
   4.145 +                new_pc = list(self.program_counter)
   4.146 +                new_pc.append(x)
   4.147 +                results[x] = self._receive_broadcast(pc, tuple(new_pc), sender, receivers)
   4.148 +
   4.149 +        if self.id in senders and self.id not in receivers:
   4.150 +            d = Deferred()
   4.151 +            d.callback(message)
   4.152 +            results = [d]
   4.153 +
   4.154 +        self.program_counter[-1] += 1
   4.155 +
   4.156 +        if len(results) == 1:
   4.157 +            return results[0]
   4.158 +
   4.159 +        return results
   4.160 +          
   4.161 +    def list_str(self, s):
   4.162 +        ls = []
   4.163 +        for x in s[1:-1].split(','):
   4.164 +            x = x.strip()
   4.165 +            ls.append(str(x)[1:-1])
   4.166 +        return ls
   4.167 +
   4.168 +    def error_handler(self, ex):
   4.169 +        print "Error: ", ex
   4.170 +        return ex
     5.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     5.2 +++ b/viff/orlandi.py	Thu Oct 08 14:27:37 2009 +0200
     5.3 @@ -0,0 +1,1314 @@
     5.4 +# Copyright 2009 VIFF Development Team.
     5.5 +#
     5.6 +# This file is part of VIFF, the Virtual Ideal Functionality Framework.
     5.7 +#
     5.8 +# VIFF is free software: you can redistribute it and/or modify it
     5.9 +# under the terms of the GNU Lesser General Public License (LGPL) as
    5.10 +# published by the Free Software Foundation, either version 3 of the
    5.11 +# License, or (at your option) any later version.
    5.12 +#
    5.13 +# VIFF is distributed in the hope that it will be useful, but WITHOUT
    5.14 +# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
    5.15 +# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
    5.16 +# Public License for more details.
    5.17 +#
    5.18 +# You should have received a copy of the GNU Lesser General Public
    5.19 +# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
    5.20 +
    5.21 +from twisted.internet.defer import Deferred, DeferredList, gatherResults
    5.22 +
    5.23 +from viff.runtime import Runtime, Share, ShareList, gather_shares
    5.24 +from viff.util import rand
    5.25 +from viff.constants import TEXT, PAILLIER
    5.26 +from viff.field import FieldElement
    5.27 +from viff.paillier import encrypt_r, decrypt
    5.28 +
    5.29 +from hash_broadcast import HashBroadcastMixin
    5.30 +
    5.31 +import commitment
    5.32 +commitment.set_reference_string(23434347834783478783478L, 489237823478234783478020L)
    5.33 +
    5.34 +# import logging
    5.35 +# LOG_FILENAME = 'logging_example.out'
    5.36 +# logging.basicConfig(filename=LOG_FILENAME,level=logging.DEBUG,)
    5.37 +
    5.38 +class OrlandiException(Exception):
    5.39 +    pass
    5.40 +
    5.41 +class OrlandiShare(Share):
    5.42 +    """A share in the Orlandi runtime.
    5.43 +
    5.44 +    A share in the Orlandi runtime is a 3-tuple ``(x_i, rho_i, Cr_i)`` of:
    5.45 +    - A share of a number, ``x_i``
    5.46 +    - A tuple of two random numbers, ``rho_i = (rho_i1, rho_i2)``
    5.47 +    - A commitment to the number and the random numbers, ``Cr_i``
    5.48 +
    5.49 +    The :class:`Runtime` operates on shares, represented by this class.
    5.50 +    Shares are asynchronous in the sense that they promise to attain a
    5.51 +    value at some point in the future.
    5.52 +
    5.53 +    Shares overload the arithmetic operations so that ``x = a + b``
    5.54 +    will create a new share *x*, which will eventually contain the
    5.55 +    sum of *a* and *b*. Each share is associated with a
    5.56 +    :class:`Runtime` and the arithmetic operations simply call back to
    5.57 +    that runtime.
    5.58 +    """
    5.59 +
    5.60 +    def __init__(self, runtime, field, value=None, rho=None, commitment=None):
    5.61 +        self.share = value
    5.62 +        self.rho = rho
    5.63 +        self.commitment = commitment
    5.64 +        Share.__init__(self, runtime, field, (value, rho, commitment))
    5.65 +
    5.66 +
    5.67 +class OrlandiRuntime(Runtime, HashBroadcastMixin):
    5.68 +    """The Orlandi runtime.
    5.69 +
    5.70 +    The runtime is used for sharing values (:meth:`secret_share` or
    5.71 +    :meth:`shift`) into :class:`OrlandiShare` object and opening such
    5.72 +    shares (:meth:`open`) again. Calculations on shares is normally
    5.73 +    done through overloaded arithmetic operations, but it is also
    5.74 +    possible to call :meth:`add`, :meth:`mul`, etc. directly if one
    5.75 +    prefers.
    5.76 +
    5.77 +    Each player in the protocol uses a :class:`Runtime` object. To
    5.78 +    create an instance and connect it correctly with the other
    5.79 +    players, please use the :func:`create_runtime` function instead of
    5.80 +    instantiating a Runtime directly. The :func:`create_runtime`
    5.81 +    function will take care of setting up network connections and
    5.82 +    return a :class:`Deferred` which triggers with the
    5.83 +    :class:`Runtime` object when it is ready.
    5.84 +    """
    5.85 +
    5.86 +    def __init__(self, player, threshold=None, options=None):
    5.87 +        """Initialize runtime."""
    5.88 +        Runtime.__init__(self, player, threshold, options)
    5.89 +        self.threshold = self.num_players - 1
    5.90 +        self.s = 1
    5.91 +        self.d = 0
    5.92 +        self.s_lambda = 1
    5.93 +
    5.94 +    def compute_delta(self, d):
    5.95 +        def product(j):
    5.96 +            pt = 1
    5.97 +            pn = 1
    5.98 +            for k in xrange(1, 2 * d + 2):
    5.99 +                if k != j:
   5.100 +                    pt *= k
   5.101 +                    pn *= k - j
   5.102 +            return pt // pn
   5.103 +
   5.104 +        delta = []
   5.105 +        for j in xrange(1, 2 * d + 2):
   5.106 +            delta.append(product(j))
   5.107 +        return delta
   5.108 +
   5.109 +    def output(self, share, receivers=None, threshold=None):
   5.110 +        return self.open(share, receivers, threshold)
   5.111 +
   5.112 +    def _send_orlandi_share(self, other_id, pc, xi, rhoi, Cx):
   5.113 +        """Send the share *xi*, *rhoi*, and the commitment *Cx* to party *other_id*."""
   5.114 +        self.protocols[other_id].sendShare(pc, xi)
   5.115 +        self.protocols[other_id].sendShare(pc, rhoi[0])
   5.116 +        self.protocols[other_id].sendShare(pc, rhoi[1])
   5.117 +        self.protocols[other_id].sendData(pc, TEXT, repr(Cx))
   5.118 +
   5.119 +    def _expect_orlandi_share(self, peer_id, field):
   5.120 +        """Waits for a number ``x``, ``rho``, and the commitment for ``x``."""
   5.121 +        xi = self._expect_share(peer_id, field)
   5.122 +        Cx = Deferred()        
   5.123 +        rhoi1 = self._expect_share(peer_id, field)
   5.124 +        rhoi2 = self._expect_share(peer_id, field)
   5.125 +        self._expect_data(peer_id, TEXT, Cx)
   5.126 +        sls = ShareList([xi, rhoi1, rhoi2, Cx])
   5.127 +        def combine(ls):
   5.128 +            expected_num = 4;
   5.129 +            if len(ls) is not expected_num:
   5.130 +                raise OrlandiException("Cannot share number, trying to create a share,"
   5.131 +                                       " expected %s components got %s." % (expected_num, len(ls)))
   5.132 +            s1, xi = ls[0]
   5.133 +            s2, rhoi1 = ls[1]
   5.134 +            s3, rhoi2 = ls[2]
   5.135 +            s4, Cx = ls[3]
   5.136 +            Cxx = commitment.deserialize(Cx)
   5.137 +            if not (s1 and s2 and s3 and s4):
   5.138 +                raise OrlandiException("Cannot share number, trying to create share,"
   5.139 +                                       " but a component did arrive properly.")
   5.140 +            return OrlandiShare(self, field, xi, (rhoi1, rhoi2), Cxx)
   5.141 +        sls.addCallbacks(combine, self.error_handler)
   5.142 +        return sls
   5.143 +
   5.144 +    def _expect_orlandi_share_xi_rhoi(self, peer_id, field):
   5.145 +        xi = self._expect_share(peer_id, field)
   5.146 +        rhoi1 = self._expect_share(peer_id, field)
   5.147 +        rhoi2 = self._expect_share(peer_id, field)
   5.148 +        sls = ShareList([xi, rhoi1, rhoi2])
   5.149 +        def combine(ls):
   5.150 +            expected_num = 3;
   5.151 +            if len(ls) is not expected_num:
   5.152 +                raise OrlandiException("Cannot share number, trying to create a share,"
   5.153 +                                       " expected %s components got %s." % (expected_num, len(ls)))
   5.154 +
   5.155 +            s1, xi = ls[0]
   5.156 +            s2, rhoi1 = ls[1]
   5.157 +            s3, rhoi2 = ls[2]
   5.158 +            if not (s1 and s2 and s3):
   5.159 +                raise OrlandiException("Cannot share number, trying to create share "
   5.160 +                                       "but a component did arrive properly.")
   5.161 +            return OrlandiShare(self, field, xi, (rhoi1, rhoi2))
   5.162 +        sls.addCallbacks(combine, self.error_handler)
   5.163 +        return sls
   5.164 +
   5.165 +    def secret_share(self, inputters, field, number=None, threshold=None):
   5.166 +        """Share the value, number, among all the parties using additive shareing.
   5.167 +
   5.168 +        To share an element ``x in Z_p``, choose random ``x_1, ..., x_n-1 in Z_p``, 
   5.169 +        define ``x_n = x - SUM_i=1^n-1 x_i mod p``.
   5.170 +
   5.171 +        Choose random values ``rho_x1, ..., rho_xn in (Z_p)^2``, define 
   5.172 +        ``rho_x = SUM_i=1^n rho_x,i`` and ``C_x = Com_ck(x, p_x)``.
   5.173 +        
   5.174 +        Send ``[x]_i = (x_i, rho_xi, C_x)`` to party ``P_i``.
   5.175 +        """
   5.176 +        assert number is None or self.id in inputters
   5.177 +        self.threshold = self.num_players - 1
   5.178 +
   5.179 +        self.program_counter[-1] += 1
   5.180 +
   5.181 +        def additive_shares_with_rho(x):
   5.182 +            """Returns a tuple of a list of tuples (player id, share, rho) and rho.
   5.183 +
   5.184 +            Chooses random elements ``x_1, ..., x_n-1`` in field and ``x_n`` st. 
   5.185 +            ``x_n = x - Sum_i=1^n-1 x_i``.
   5.186 +
   5.187 +            Chooses random pair of elements ``rho_1, ..., rho_n in Z_p^2``
   5.188 +            and define ``rho_n = Sum_i=1^n rho_i``.
   5.189 +
   5.190 +            Returns a pair of ``((player id, x_i, rho_i), rho)``.
   5.191 +            """ 
   5.192 +            shares = []
   5.193 +            rhos = []
   5.194 +            sum = 0
   5.195 +            rho1 = 0
   5.196 +            rho2 = 0
   5.197 +            for i in xrange(1, self.num_players):
   5.198 +                xi = field(rand.randint(0, field.modulus - 1))
   5.199 +                rhoi1 = field(rand.randint(0, field.modulus - 1))
   5.200 +                rhoi2 = field(rand.randint(0, field.modulus - 1))
   5.201 +                sum += xi
   5.202 +                rho1 += rhoi1
   5.203 +                rho2 += rhoi2
   5.204 +                shares.append((i, xi, (rhoi1, rhoi2)))    
   5.205 +            xn = field(x) - sum
   5.206 +            rhon1 = field(rand.randint(0, field.modulus - 1))
   5.207 +            rhon2 = field(rand.randint(0, field.modulus - 1))
   5.208 +            shares.append((self.num_players, xn, (rhon1, rhon2)))
   5.209 +            rho1 += rhon1
   5.210 +            rho2 += rhon2
   5.211 +            return shares, (rho1, rho2)
   5.212 +
   5.213 +        # Send ``[x]_i = (x_i, rho_x,i, C_x)`` to party ``P_i``.
   5.214 +        results = []
   5.215 +        for peer_id in inputters:
   5.216 +            if peer_id == self.id:
   5.217 +                pc = tuple(self.program_counter)
   5.218 +                shares, rho = additive_shares_with_rho(number)
   5.219 +                Cx = commitment.commit(number, rho[0].value, rho[1].value)
   5.220 +                # Distribute the shares
   5.221 +                the_others = []
   5.222 +                for other_id, xi, rhoi in shares:
   5.223 +                    if other_id == self.id:
   5.224 +                        results.append(OrlandiShare(self, field, xi, rhoi, Cx))
   5.225 +                    else:
   5.226 +                        # Send ``xi``, ``rhoi``, and commitment
   5.227 +                        self._send_orlandi_share(other_id, pc, xi, rhoi, Cx)
   5.228 +            else:
   5.229 +                # Expect ``xi``, ``rhoi``, and commitment
   5.230 +                results.append(self._expect_orlandi_share(peer_id, field))
   5.231 +        # do actual communication
   5.232 +        self.activate_reactor()
   5.233 +        # Unpack a singleton list.
   5.234 +        if len(results) == 1:
   5.235 +            return results[0]
   5.236 +        return results
   5.237 +
   5.238 +    def open(self, share, receivers=None, threshold=None):
   5.239 +        """Share reconstruction.
   5.240 +
   5.241 +        Every partyi broadcasts a share pair ``(x_i', rho_x,i')``.
   5.242 +
   5.243 +        The parties compute the sums ``x'``, ``rho_x'`` and 
   5.244 +        check ``Com_ck(x',rho_x' = C_x``.
   5.245 +
   5.246 +        If yes, return ``x = x'``, else else return :const:`None`.
   5.247 +        """
   5.248 +        assert isinstance(share, Share)
   5.249 +        # all players receive result by default
   5.250 +        if receivers is None:
   5.251 +            receivers = self.players.keys()
   5.252 +        assert threshold is None
   5.253 +        threshold = self.num_players - 1
   5.254 +
   5.255 +        field = share.field
   5.256 +
   5.257 +        self.program_counter[-1] += 1
   5.258 +
   5.259 +        def recombine_value(shares, Cx):
   5.260 +            x = 0
   5.261 +            rho1 = 0
   5.262 +            rho2 = 0
   5.263 +            for xi, rhoi1, rhoi2 in shares:
   5.264 +                x += xi
   5.265 +                rho1 += rhoi1
   5.266 +                rho2 += rhoi2
   5.267 +            Cx1 = commitment.commit(x.value, rho1.value, rho2.value)
   5.268 +            if Cx1 == Cx:
   5.269 +                return x
   5.270 +            else:
   5.271 +                #return x
   5.272 +                raise OrlandiException("Wrong commitment for value %s, %s, %s, found %s expected %s." % 
   5.273 +                                       (x, rho1, rho2, Cx1, Cx))
   5.274 +
   5.275 +        def deserialize(ls):
   5.276 +            shares = [(field(long(x)), field(long(rho1)), field(long(rho2))) for x, rho1, rho2 in map(self.list_str, ls)]
   5.277 +            return shares
   5.278 +            
   5.279 +        def exchange((xi, (rhoi1, rhoi2), Cx), receivers):
   5.280 +            # Send share to all receivers.
   5.281 +            ds = self.broadcast(self.players.keys(), receivers, str((str(xi.value), str(rhoi1.value), str(rhoi2.value))))
   5.282 +
   5.283 +            if self.id in receivers:
   5.284 +                result = gatherResults(ds)
   5.285 +                result.addCallbacks(deserialize, self.error_handler)
   5.286 +                result.addCallbacks(recombine_value, self.error_handler, callbackArgs=(Cx,))
   5.287 +                return result
   5.288 +
   5.289 +        result = share.clone()
   5.290 +        self.schedule_callback(result, exchange, receivers)
   5.291 +        result.addErrback(self.error_handler)
   5.292 +
   5.293 +        # do actual communication
   5.294 +        self.activate_reactor()
   5.295 +
   5.296 +        if self.id in receivers:
   5.297 +            return result
   5.298 +
   5.299 +    def random_share(self, field):
   5.300 +        """Generate a random share in the field, field.
   5.301 +
   5.302 +        To generate a share of a random element ``r in Z_p``, party ``P_i`` 
   5.303 +        chooses at random ``r_i, rho_ri in Z_p X (Z_p)^2`` and
   5.304 +        broadcast ``C_r^i = Com_ck(r_i, rho_ri)``.
   5.305 +
   5.306 +        Every party computes ``C_r = PRODUCT_i=1^n C_r^i = Com_ck(r, rho_r)``,
   5.307 +        where ``r_i = SUM_i=1^n r_i and rho_r = SUM_i=1^n rho_ri``.
   5.308 +
   5.309 +        Party ``P_i sets [r]_i = (r_i, rho_ri, C_r)``.
   5.310 +
   5.311 +        """
   5.312 +        self.program_counter[-1] += 1
   5.313 +
   5.314 +        # P_i chooses at random r_i, rho_ri in Z_p x (Z_p)^2
   5.315 +        ri = field(rand.randint(0, field.modulus - 1))     
   5.316 +        rhoi1 = field(rand.randint(0, field.modulus - 1))
   5.317 +        rhoi2 = field(rand.randint(0, field.modulus - 1))
   5.318 +
   5.319 +        # compute C_r^i = Com_ck(r_i, rho_ri).
   5.320 +        Cri = commitment.commit(ri.value, rhoi1, rhoi2)
   5.321 +
   5.322 +        # Broadcast C_r^i.
   5.323 +        sls = gatherResults(self.broadcast(self.players.keys(), self.players.keys(), repr(Cri)))
   5.324 +
   5.325 +        def compute_commitment(ls):
   5.326 +            Cr = ls.pop()
   5.327 +            for Cri in ls:
   5.328 +                Cr = Cr * Cri
   5.329 +            return OrlandiShare(self, field, ri, (rhoi1, rhoi2), Cr)
   5.330 +
   5.331 +        def deserialize(ls):
   5.332 +            return [ commitment.deserialize(x) for x in ls ]
   5.333 +
   5.334 +        sls.addCallbacks(deserialize, self.error_handler)
   5.335 +        sls.addCallbacks(compute_commitment, self.error_handler)
   5.336 +
   5.337 +        s = Share(self, field)
   5.338 +        # We add the result to the chains in triple.
   5.339 +        sls.chainDeferred(s)
   5.340 +
   5.341 +        # do actual communication
   5.342 +        self.activate_reactor()
   5.343 +
   5.344 +        return s
   5.345 +    
   5.346 +    def add(self, share_a, share_b):
   5.347 +        """Addition of shares.
   5.348 +
   5.349 +        Communication cost: none.
   5.350 +
   5.351 +        Each party ``P_i`` computes:
   5.352 +        ``[z]_i = [x]_i + [y]_i
   5.353 +                = (x_i + y_i mod p, rho_xi + rho_yi mod p, C_x * C_y)``.
   5.354 +
   5.355 +        """
   5.356 +        def is_share(s, field):
   5.357 +            if not isinstance(s, Share):
   5.358 +                if not isinstance(s, FieldElement):
   5.359 +                    s = field(s)
   5.360 +                (v, rhov, Cv) = self._additive_constant(field(0), s)
   5.361 +                return OrlandiShare(self, field, v, rhov, Cv)
   5.362 +            return s
   5.363 +
   5.364 +        # Either share_a or share_b must have an attribute called "field". 
   5.365 +        field = getattr(share_a, "field", getattr(share_b, "field", None))
   5.366 +
   5.367 +        share_a = is_share(share_a, field)
   5.368 +        share_b = is_share(share_b, field)
   5.369 +
   5.370 +        # Add rho_xi and rho_yi and compute the commitment.
   5.371 +        def compute_sums((x, y)):
   5.372 +            (zi, (rhozi1, rhozi2), Cz) = self._plus(x, y)
   5.373 +            return OrlandiShare(self, field, zi, (rhozi1, rhozi2), Cz)
   5.374 +
   5.375 +        result = gather_shares([share_a, share_b])
   5.376 +        result.addCallbacks(compute_sums, self.error_handler)
   5.377 +        return result
   5.378 +
   5.379 +    def sub(self, share_a, share_b):
   5.380 +        """Subtraction of shares.
   5.381 +
   5.382 +        Communication cost: none.
   5.383 +
   5.384 +        Each party ``P_i`` computes:
   5.385 +        ``[z]_i = [x]_i - [y]_i
   5.386 +                = (x_i - y_i mod p, rho_x,i - rho_y,i mod p, C_x * C_y)``.
   5.387 +
   5.388 +        """
   5.389 +        def is_share(s, field):
   5.390 +            if not isinstance(s, Share):
   5.391 +                if not isinstance(s, FieldElement):
   5.392 +                    s = field(s)
   5.393 +                (v, rhov, Cv) = self._additive_constant(field(0), s)
   5.394 +                return OrlandiShare(self, field, v, rhov, Cv)
   5.395 +            return s
   5.396 +
   5.397 +        # Either share_a or share_b must have an attribute called "field". 
   5.398 +        field = getattr(share_a, "field", getattr(share_b, "field", None))
   5.399 +
   5.400 +        share_a = is_share(share_a, field)
   5.401 +        share_b = is_share(share_b, field)
   5.402 +
   5.403 +        # Subtract xi and yi, rhoxi and rhoyi, and compute the commitment
   5.404 +        def compute_subs((x, y)):
   5.405 +            zi, (rhozi1, rhozi2), Cz = self._minus(x, y)
   5.406 +            return OrlandiShare(self, field, zi, (rhozi1, rhozi2), Cz)
   5.407 +
   5.408 +        result = gather_shares([share_a, share_b])
   5.409 +        result.addCallbacks(compute_subs, self.error_handler)
   5.410 +        return result
   5.411 +
   5.412 +    def input(self, inputters, field, number=None, threshold=None):
   5.413 +        """Input *number* to the computation.
   5.414 +
   5.415 +        The input is shared using the :meth:`shift` method.
   5.416 +        """
   5.417 +        return self.shift(inputters, field, number)
   5.418 +
   5.419 +
   5.420 +    def shift(self, inputters, field, number=None):
   5.421 +        """Shift of a share.
   5.422 +        
   5.423 +        Useful for input.
   5.424 +
   5.425 +        Communication cost: ???.
   5.426 +
   5.427 +        Assume the parties are given a random share ``[r]`` by a trusted dealer. 
   5.428 +        Then we denote the following protocol but ``[x] = Shift(P_i, x, [r])``.
   5.429 +
   5.430 +        1) ``r = OpenTo(P_i, [r]``
   5.431 +
   5.432 +        2) ``P_i broadcasts Delta = r - x``
   5.433 +
   5.434 +        3) ``[x] = [r] - Delta``
   5.435 +
   5.436 +        """
   5.437 +        # TODO: Communitcation costs?
   5.438 +        assert (self.id in inputters and number != None) or (self.id not in inputters)
   5.439 +
   5.440 +        self.program_counter[-1] += 1
   5.441 +
   5.442 +        results = []
   5.443 +        def hack(_, peer_id):
   5.444 +            # Assume the parties are given a random share [r] by a trusted dealer.
   5.445 +            share_r = self.random_share(field)
   5.446 +            # 1) r = OpenTo(P_i, [r])
   5.447 +            open_r = self.open(share_r, [peer_id])
   5.448 +            def subtract_delta(delta, share_r):
   5.449 +                delta = field(long(delta))
   5.450 +                x = self.sub(share_r, delta)
   5.451 +                return x
   5.452 +            if peer_id == self.id:
   5.453 +                def g(r, x):
   5.454 +                    delta = r - x
   5.455 +                    delta = self.broadcast([peer_id], self.players.keys(), str(delta.value))
   5.456 +                    self.schedule_callback(delta, subtract_delta, share_r)
   5.457 +                    delta.addErrback(self.error_handler)
   5.458 +                    return delta
   5.459 +                self.schedule_callback(open_r, g, number)
   5.460 +                open_r.addErrback(self.error_handler)
   5.461 +                return open_r
   5.462 +            else:
   5.463 +                d = Deferred()
   5.464 +                def g(_, peer_id, share_r):
   5.465 +                    delta = self.broadcast([peer_id], self.players.keys())
   5.466 +                    self.schedule_callback(delta, subtract_delta, share_r)
   5.467 +                    delta.addErrback(self.error_handler)
   5.468 +                    return delta
   5.469 +                self.schedule_callback(d, g, peer_id, share_r)
   5.470 +                d.addErrback(self.error_handler)
   5.471 +                d.callback(None)
   5.472 +                return d
   5.473 +
   5.474 +        for peer_id in inputters:
   5.475 +            s = Share(self, field)
   5.476 +            self.schedule_callback(s, hack, peer_id)
   5.477 +            s.addErrback(self.error_handler)
   5.478 +            s.callback(None)
   5.479 +            results.append(s)
   5.480 +
   5.481 +        # do actual communication
   5.482 +        self.activate_reactor()
   5.483 +
   5.484 +        if len(results) == 1:
   5.485 +             return results[0]
   5.486 +        return results       
   5.487 +
   5.488 +    def mul(self, share_x, share_y):
   5.489 +        """Multiplication of shares.
   5.490 +
   5.491 +        Communication cost: ???.
   5.492 +        """
   5.493 +        # TODO: Communication cost?
   5.494 +        assert isinstance(share_x, Share) or isinstance(share_y, Share), \
   5.495 +            "At least one of share_x and share_y must be a Share."
   5.496 +
   5.497 +        self.program_counter[-1] += 1
   5.498 +
   5.499 +        field = getattr(share_x, "field", getattr(share_y, "field", None))
   5.500 +
   5.501 +        def finish_mul((a, b, c)):
   5.502 +            return self._basic_multiplication(share_x, share_y, a, b, c)
   5.503 +
   5.504 +        # This will be the result, a Share object.
   5.505 +        result = Share(self, share_x.field)
   5.506 +        # This is the Deferred we will do processing on.
   5.507 +        triple = self._get_triple(field)
   5.508 +        triple = self.schedule_complex_callback(triple, finish_mul)
   5.509 +        # We add the result to the chains in triple.
   5.510 +        triple.chainDeferred(result)
   5.511 +        return result
   5.512 +
   5.513 +    def _additive_constant(self, zero, field_element):
   5.514 +        """Greate an additive constant.
   5.515 +
   5.516 +        Any additive constant can be interpreted as:
   5.517 +        ``[c]_1 = (c, 0, Com_ck(c,0))`` and
   5.518 +        ``[c]_i = (0, 0, Com_ck(c,0)) for i != 1``.
   5.519 +        """
   5.520 +        v = zero
   5.521 +        if self.id == 1:
   5.522 +            v = field_element
   5.523 +        Cx = commitment.commit(field_element.value, zero.value, zero.value)
   5.524 +        return (v, (zero, zero), Cx)
   5.525 +
   5.526 +    def _plus(self, x, y):
   5.527 +        """Addition of share-tuples *x* and *y*.
   5.528 +
   5.529 +        Each party ``P_i`` computes:
   5.530 +        ``[x]_i = (x_i, rho_xi, C_x)``
   5.531 +        ``[y]_i = (y_i, rho_yi, C_y)``
   5.532 +        ``[z]_i = [x]_i + [y]_i
   5.533 +                = (x_i + y_i mod p, rho_xi + rho_yi mod p, C_x * C_y)``.
   5.534 +        """
   5.535 +        (xi, (rhoxi1, rhoxi2), Cx) = x
   5.536 +        (yi, (rhoyi1, rhoyi2), Cy) = y
   5.537 +        zi = xi + yi
   5.538 +        rhozi1 = rhoxi1 + rhoyi1
   5.539 +        rhozi2 = rhoxi2 + rhoyi2
   5.540 +        Cz = Cx * Cy
   5.541 +        return (zi, (rhozi1, rhozi2), Cz)
   5.542 +
   5.543 +    def _minus(self, x, y):
   5.544 +        """Subtraction of share-tuples *x* and *y*.
   5.545 +
   5.546 +        Each party ``P_i`` computes:
   5.547 +        ``[x]_i = (x_i, rho_x,i, C_x)``
   5.548 +        ``[y]_i = (y_i, rho_y,i, C_y)``
   5.549 +        ``[z]_i = [x]_i - [y]_i
   5.550 +                = (x_i - y_i mod p, rho_x,i - rho_y,i mod p, C_x / C_y)``.
   5.551 +        """
   5.552 +        xi, (rhoxi1, rhoxi2), Cx = x
   5.553 +        yi, (rhoyi1, rhoyi2), Cy = y
   5.554 +        zi = xi - yi
   5.555 +        rhozi1 = rhoxi1 - rhoyi1
   5.556 +        rhozi2 = rhoxi2 - rhoyi2
   5.557 +        Cz = Cx / Cy
   5.558 +        return (zi, (rhozi1, rhozi2), Cz)
   5.559 +
   5.560 +    def _cmul(self, share_x, share_y, field):
   5.561 +        """Multiplication of a share with a constant.
   5.562 +
   5.563 +        Either share_x or share_y must be an OrlandiShare but not both.
   5.564 +        Returns None if both share_x and share_y are OrlandiShares.
   5.565 +
   5.566 +        """
   5.567 +        def constant_multiply(x, c):
   5.568 +            assert(isinstance(c, FieldElement))
   5.569 +            zi, rhoz, Cx = self._const_mul(c.value, x)
   5.570 +            return OrlandiShare(self, field, zi, rhoz, Cx)
   5.571 +        if not isinstance(share_x, Share):
   5.572 +            # Then share_y must be a Share => local multiplication. We
   5.573 +            # clone first to avoid changing share_y.
   5.574 +            assert isinstance(share_y, Share), \
   5.575 +                "At least one of the arguments must be a share."
   5.576 +            result = share_y.clone()
   5.577 +            result.addCallback(constant_multiply, share_x)
   5.578 +            return result
   5.579 +        if not isinstance(share_y, Share):
   5.580 +            # Likewise when share_y is a constant.
   5.581 +            assert isinstance(share_x, Share), \
   5.582 +                "At least one of the arguments must be a share."
   5.583 +            result = share_x.clone()
   5.584 +            result.addCallback(constant_multiply, share_y)
   5.585 +            return result
   5.586 +        return None
   5.587 +
   5.588 +    def _const_mul(self, c, x):
   5.589 +        """Multiplication of a share-tuple with a constant c."""
   5.590 +        assert(isinstance(c, long) or isinstance(c, int))
   5.591 +        xi, (rhoi1, rhoi2), Cx = x
   5.592 +        zi = xi * c
   5.593 +        rhoz = (rhoi1 * c, rhoi2 * c)
   5.594 +        Cz = Cx**c
   5.595 +        return (zi, rhoz, Cz)
   5.596 +
   5.597 +    def _get_share(self, field, value):
   5.598 +        Cc = commitment.commit(value * 3, 0, 0)
   5.599 +        c = OrlandiShare(self, field, field(value), (field(0), field(0)), Cc)
   5.600 +        return c
   5.601 +
   5.602 +    def _get_triple(self, field):
   5.603 +        c, d = self.random_triple(field, 1)
   5.604 +        def f(ls):
   5.605 +            return ls[0]
   5.606 +        d.addCallbacks(f, self.error_handler)
   5.607 +        return d
   5.608 +
   5.609 +    def _basic_multiplication(self, share_x, share_y, triple_a, triple_b, triple_c):
   5.610 +        """Multiplication of shares give a triple.
   5.611 +
   5.612 +        Communication cost: ???.
   5.613 +        
   5.614 +        ``d = Open([x] - [a])``
   5.615 +        ``e = Open([y] - [b])``
   5.616 +        ``[z] = e[x] + d[y] - [de] + [c]``
   5.617 +        """
   5.618 +        assert isinstance(share_x, Share) or isinstance(share_y, Share), \
   5.619 +            "At least one of share_x and share_y must be a Share."
   5.620 +
   5.621 +        self.program_counter[-1] += 1
   5.622 +
   5.623 +        field = getattr(share_x, "field", getattr(share_y, "field", None))
   5.624 +        n = field(0)
   5.625 +
   5.626 +        cmul_result = self._cmul(share_x, share_y, field)
   5.627 +        if cmul_result is  not None:
   5.628 +            return cmul_result
   5.629 +
   5.630 +        def multiply((x, y, d, e, c)):
   5.631 +            # [de]
   5.632 +            de = self._additive_constant(field(0), d * e)
   5.633 +            # e[x]
   5.634 +            t1 = self._const_mul(e.value, x)
   5.635 +            # d[y]
   5.636 +            t2 = self._const_mul(d.value, y)
   5.637 +            # d[y] - [de]
   5.638 +            t3 = self._minus(t2, de)
   5.639 +            # d[y] - [de] + [c]
   5.640 +            t4 = self._plus(t3, c)
   5.641 +            # [z] = e[x] + d[y] - [de] + [c]
   5.642 +            zi, rhoz, Cz = self._plus(t1, t4)
   5.643 +            return OrlandiShare(self, field, zi, rhoz, Cz)
   5.644 +
   5.645 +        # d = Open([x] - [a])
   5.646 +        d = self.open(share_x - triple_a)
   5.647 +        # e = Open([y] - [b])
   5.648 +        e = self.open(share_y - triple_b)
   5.649 +        result = gather_shares([share_x, share_y, d, e, triple_c])
   5.650 +        result.addCallbacks(multiply, self.error_handler)
   5.651 +
   5.652 +        # do actual communication
   5.653 +        self.activate_reactor()
   5.654 +
   5.655 +        return result
   5.656 +
   5.657 +    def sum_poly(self, j, ls):
   5.658 +        exp  = j
   5.659 +        fj, (rhoj1, rhoj2), Cfj = ls[0]
   5.660 +        x    = fj*exp
   5.661 +        rho1 = rhoj1 * exp
   5.662 +        rho2 = rhoj2 * exp
   5.663 +        Cx   = Cfj**exp
   5.664 +        exp *= j
   5.665 +
   5.666 +        for (fj, (rhoj1, rhoj2), Cfj) in ls[1:]:
   5.667 +            x += fj * exp
   5.668 +            rho1 += rhoj1 * exp
   5.669 +            rho2 += rhoj2 * exp
   5.670 +            Cx = Cx * (Cfj**exp)
   5.671 +            exp *= j
   5.672 +        return x, (rho1, rho2), Cx
   5.673 +
   5.674 +    def leak_tolerant_mul(self, share_x, share_y, M):
   5.675 +        """Leak tolerant multiplication of shares.
   5.676 +
   5.677 +        Communication cost: ???.
   5.678 +
   5.679 +        Assuming a set of multiplicative triples:
   5.680 +        ``M = ([a_i], [b_i], [c_i]) for 1 <= i <= 2d + 1``.
   5.681 +
   5.682 +        1) ``for i = 1, ..., d do [f_i] = rand(), [g_i] = rand()``
   5.683 +
   5.684 +        2) ``for j = 1, ..., 2d+1 do
   5.685 +             [F_j] = [x] + SUM_i=1^d [f_i]*j^i 
   5.686 +             and
   5.687 +             [G_j] = [y] + SUM_i=1^d [g_i]*j^i`` 
   5.688 +
   5.689 +        3) for j = 1, ..., 2d+1 do [H_j] = Mul([F_j], [G_j], [a_j], [b_j], [c_j])
   5.690 +
   5.691 +        4) compute [H_0] = SUM_j=1^2d+1 delta_j[H_j] 
   5.692 +
   5.693 +        5) output [z] = [H_0]
   5.694 +
   5.695 +        delta_j = PRODUCT_k=1, k!=j^2d+1 k/(k-j).
   5.696 +        """
   5.697 +        assert isinstance(share_x, Share) or isinstance(share_y, Share), \
   5.698 +            "At least one of share_x and share_y must be a Share."
   5.699 +
   5.700 +        self.program_counter[-1] += 1
   5.701 +
   5.702 +        field = getattr(share_x, "field", getattr(share_y, "field", None))
   5.703 +        n = field(0)
   5.704 +
   5.705 +        cmul_result = self._cmul(share_x, share_y, field)
   5.706 +        if cmul_result is not None:
   5.707 +            return cmul_result
   5.708 +
   5.709 +        # 1) for i = 1, ..., d do [f_i] = rand(), [g_i] = rand()
   5.710 +        d = (len(M) - 1) // 2
   5.711 +        deltas = self.compute_delta(d)
   5.712 +        f = []
   5.713 +        g = []
   5.714 +        for x in xrange(d):
   5.715 +            f.append(self.random_share(field))
   5.716 +            g.append(self.random_share(field))
   5.717 +
   5.718 +        def compute_polynomials(t):
   5.719 +            x, y = t[0]
   5.720 +            f = []
   5.721 +            g = []
   5.722 +            if 1 in t:
   5.723 +                f = t[1]
   5.724 +            if 2 in t:
   5.725 +                g = t[2]
   5.726 +#             print "==> poly", self.id
   5.727 +#             print "x:", x
   5.728 +#             print "y:", y
   5.729 +#             print "f:", f
   5.730 +#             print "g:", g
   5.731 +            # 2) for j = 1, ..., 2d+1 do
   5.732 +            # [F_j] = [x] + SUM_i=1^d [f_i]*j^i 
   5.733 +            # and
   5.734 +            # [G_j] = [y] + SUM_i=1^d [g_i]*j^i 
   5.735 +            h0i, rhoh0, Ch0 = self._additive_constant(field(0), n)
   5.736 +            H0 = OrlandiShare(self, field, h0i, rhoh0, Ch0)
   5.737 +            xi, (rhoxi1, rhoxi2), Cx = x
   5.738 +            yi, (rhoyi1, rhoyi2), Cy = y
   5.739 +
   5.740 +            for j in xrange(1, 2*d + 2):
   5.741 +                Fji = xi
   5.742 +                rho1_Fji = rhoxi1
   5.743 +                rho2_Fji = rhoxi2
   5.744 +                C_Fji = Cx
   5.745 +                if f != []:
   5.746 +                    # SUM_i=1^d [f_i]*j^i 
   5.747 +                    vi, (rhovi1, rhovi2), Cv = self.sum_poly(j, f)
   5.748 +                    # [F_j] = [x] + SUM_i=1^d [f_i]*j^i 
   5.749 +                    Fji += vi
   5.750 +                    rho1_Fji += rhovi1
   5.751 +                    rho2_Fji += rhovi2
   5.752 +                    C_Fji *= Cv
   5.753 +                Gji = yi
   5.754 +                rho1_Gji = rhoyi1
   5.755 +                rho2_Gji = rhoyi2
   5.756 +                C_Gji = Cy
   5.757 +                if g != []:
   5.758 +                    # SUM_i=1^d [g_i]*j^i 
   5.759 +                    wi, (rhowi1, rhowi2), Cw = self.sum_poly(j, g)
   5.760 +                    # [G_j] = [y] + SUM_i=1^d [g_i]*j^i
   5.761 +                    Gji += wi
   5.762 +                    rho1_Gji += rhowi1
   5.763 +                    rho2_Gji += rhowi2
   5.764 +                    C_Gji *= Cw
   5.765 +                Fj = OrlandiShare(self, field, Fji, (rho1_Fji, rho2_Fji), C_Fji)
   5.766 +                Gj = OrlandiShare(self, field, Gji, (rho1_Gji, rho2_Gji), C_Gji)
   5.767 +                a, b, c = M.pop(0)
   5.768 +
   5.769 +                # [H_j] = Mul([F_j], [G_j], [a_j], [b_j], [c_j])
   5.770 +                Hj = self._basic_multiplication(Fj, Gj, a, b, c)
   5.771 +                dj = self._cmul(field(deltas[j - 1]), Hj, field)
   5.772 +                H0 = H0 + dj
   5.773 +            # 5) output [z] = [H_0]
   5.774 +            return H0
   5.775 +
   5.776 +        ls = [gather_shares([share_x, share_y])]
   5.777 +        if g:
   5.778 +            ls.append(gather_shares(g))
   5.779 +        if f:
   5.780 +            ls.append(gather_shares(f))
   5.781 +        result = gather_shares(ls)
   5.782 +        self.schedule_callback(result, compute_polynomials)
   5.783 +        result.addErrback(self.error_handler)
   5.784 +
   5.785 +        # do actual communication
   5.786 +        self.activate_reactor()
   5.787 +
   5.788 +        return result
   5.789 +
   5.790 +    def triple_gen(self, field):
   5.791 +        """Generate a triple ``a, b, c`` s.t. ``c = a * b``.
   5.792 +
   5.793 +        1) Every party ``P_i`` chooses random values ``a_i, r_i in Z_p X (Z_p)^2``,
   5.794 +        compute ``alpha_i = Enc_eki(a_i)`` and ``Ai = Com_ck(a_i, r_i)``, and
   5.795 +        broadcast them.
   5.796 +
   5.797 +        2) Every party ``P_j`` does:
   5.798 +           (a) choose random ``b_j, s_j in Z_p X (Z_p)^2``.
   5.799 +
   5.800 +           (b) compute ``B_j = ``Com_ck(b_j, s_j)`` and broadcast it.
   5.801 +
   5.802 +           (c) ``P_j`` do towards every other party:
   5.803 +                i. choose random ``d_ij in Z_p^3``
   5.804 +               ii. compute and send 
   5.805 +                   ``gamma_ij = alpha_i^b_j Enc_ek_i(1;1)^d_ij`` to ``P_i``.
   5.806 +
   5.807 +        3) Every party ``P_i`` does:
   5.808 +           (a) compute ``c_i = SUM_j Dec_sk_i(gamma_ij) - SUM_j d_ij mod p``
   5.809 +
   5.810 +           (b) pick random ``t_i in (Z_p)^2``, compute and 
   5.811 +               broadcast ``C_i = Com_ck(c_i, t_i)``
   5.812 +
   5.813 +        4) Everyone computes:
   5.814 +           ``(A, B, C) = (PRODUCT_i A_i, PRODUCT_i B_i, PRODUCT_i C_i)``
   5.815 +        
   5.816 +        5) Every party ``P_i`` outputs shares ``[a_i] = (a_i, r_i, A)``, 
   5.817 +           ``[b_i] = (b_i, s_i, B)``, and ``[c_i] = (c_i, t_i, C)``.
   5.818 +
   5.819 +        """
   5.820 +        self.program_counter[-1] += 1
   5.821 +
   5.822 +        def random_number(p):
   5.823 +            return field(rand.randint(0, p - 1))
   5.824 +
   5.825 +        def product(ls):
   5.826 +            """Compute the product of the elements in the list *ls*."""
   5.827 +            b = commitment.deserialize(ls[0])
   5.828 +            for x in ls[1:]:
   5.829 +                b *= commitment.deserialize(x)
   5.830 +            return b
   5.831 +
   5.832 +        def sum(ls):
   5.833 +            """Compute the sum of the elements in the list *ls*."""
   5.834 +            b = field(0)
   5.835 +            for x in ls:
   5.836 +                b += x
   5.837 +            return b
   5.838 +
   5.839 +        def step45(Cs, alphas, gammas, alpha_randomness,
   5.840 +                   As, Bs, ai, bi, ci, r, s, t, dijs):
   5.841 +            """4) Everyone computes:
   5.842 +                  ``A = PRODUCT_i A_i``
   5.843 +                  ``B = PRODUCT_i B_i``
   5.844 +                  ``C = PRODUCT_i C_i``
   5.845 +        
   5.846 +               5) Every party ``P_i`` outputs shares ``[a_i] = (a_i, r_i, A)``, 
   5.847 +                  ``[b_i] = (b_i, s_i, B)``, and ``[c_i] = (c_i, t_i, C)``.
   5.848 +            """
   5.849 +            A = product(As)
   5.850 +            B = product(Bs)
   5.851 +            C = product(Cs)
   5.852 +            a = OrlandiShare(self, field, ai, r, A)
   5.853 +            b = OrlandiShare(self, field, bi, s, B)
   5.854 +            c = OrlandiShare(self, field, ci, t, C)
   5.855 +            return (a, b, c, (alphas, alpha_randomness, gammas, dijs))
   5.856 +
   5.857 +        def decrypt_gammas(ls):
   5.858 +            """Decrypt all the elements of the list *ls*."""
   5.859 +            rs = []
   5.860 +            for x in ls:
   5.861 +                rs.append(field(decrypt(x, self.players[self.id].seckey)))
   5.862 +            return rs
   5.863 +
   5.864 +        def step3(gammas, alphas, alpha_randomness, As, Bs, ai, bi, r, s, dijs):
   5.865 +            """3) Every party ``P_i`` does:
   5.866 +                  (a) compute 
   5.867 +                  ``c_i = SUM_j Dec_sk_i(gamma_ij) - SUM_j d_ji mod p``
   5.868 +
   5.869 +                  (b) pick random ``t_i in (Z_p)^2``, compute and 
   5.870 +                      broadcast ``C_i = Com_ck(c_i, t_i)``
   5.871 +            """
   5.872 +            # c_i = SUM_j Dec_sk_i(gamma_ij) - SUM_j d_ji mod p.
   5.873 +            ls = decrypt_gammas(gammas)
   5.874 +            ci = sum(ls) - sum(dijs)
   5.875 +            # (b) pick random t_i in (Z_p)^2.
   5.876 +            t1 = random_number(field. modulus)
   5.877 +            t2 = random_number(field. modulus)
   5.878 +            t = (t1, t2)
   5.879 +            # C_i = Com_ck(c_i, t_i).
   5.880 +            Ci = commitment.commit(ci.value, t1.value, t2.value)
   5.881 +            
   5.882 +            # Broadcast Ci.
   5.883 +            Cs = self.broadcast(self.players.keys(), self.players.keys(), repr(Ci))
   5.884 +            result = gatherResults(Cs)
   5.885 +            result.addCallbacks(step45, self.error_handler, callbackArgs=(alphas, gammas, alpha_randomness, 
   5.886 +                                                                          As, Bs, ai, bi, ci, r, s, t, dijs))
   5.887 +            return result
   5.888 +
   5.889 +        def step2c(Bs, As, alphas, alpha_randomness, ai, bj, r, s):
   5.890 +            """(c) P_j do, towards every other party:
   5.891 +                   i. choose random d_i,j in Z_p^3
   5.892 +                   ii. compute and send 
   5.893 +            gamma_ij = alpha_i^b_j Enc_ek_i(1;1)^d_ij to P_i.
   5.894 +            """
   5.895 +
   5.896 +            # (c) P_j do, towards every other party:
   5.897 +            dijs = [None] * len(self.players.keys())
   5.898 +            results = [None] * len(self.players.keys())
   5.899 +            pc = tuple(self.program_counter)
   5.900 +            for pi in self.players.keys():
   5.901 +                n = self.players[pi].pubkey[0]
   5.902 +                nsq = n * n
   5.903 +                # choose random d_i,j in Z_p^3
   5.904 +                dij = random_number(field.modulus**3)
   5.905 +                # Enc_ek_i(1;1)^d_ij
   5.906 +                enc = encrypt_r(1, 1, self.players[pi].pubkey)
   5.907 +                t1 = pow(enc, dij.value, nsq)
   5.908 +                # alpha_i^b_j.
   5.909 +                t2 = pow(alphas[pi - 1], bj.value, nsq)
   5.910 +                # gamma_ij = alpha_i^b_j Enc_ek_i(1;1)^d_ij
   5.911 +                gammaij = (t2) * (t1) % nsq
   5.912 +                # Broadcast gamma_ij
   5.913 +                if pi != self.id:
   5.914 +                    self.protocols[pi].sendData(pc, PAILLIER, str(gammaij))
   5.915 +                    d = Deferred()
   5.916 +                    d.addCallbacks(lambda value: long(value), self.error_handler)
   5.917 +                    self._expect_data(pi, PAILLIER, d)
   5.918 +                else:
   5.919 +                    d = Deferred()
   5.920 +                    d.callback(gammaij)
   5.921 +                dijs[pi - 1] = dij
   5.922 +                results[pi - 1] = d
   5.923 +            result = gatherResults(results)
   5.924 +            self.schedule_callback(result, step3, alphas, alpha_randomness, 
   5.925 +                                   As, Bs, ai, bj, r, s, dijs)
   5.926 +            result.addErrback(self.error_handler)
   5.927 +            return result
   5.928 +
   5.929 +        def step2ab((alphas, As), ai, r, alpha_randomness):
   5.930 +            """2) Every party P_j does:
   5.931 +                  (a) choose random b_j, s_j in Z_p X (Z_p)^2.
   5.932 +
   5.933 +                  (b) compute B_j = Com_ck(b_j, s_j) and broadcast it.
   5.934 +            """
   5.935 +            # (a) choose random b_j, s_j in Z_p X (Z_p)^2.
   5.936 +            bj = random_number(field.modulus)
   5.937 +            s1 = random_number(field.modulus)
   5.938 +            s2 = random_number(field.modulus)
   5.939 +            # (b) compute B_j = Com_ck(b_j, s_j).
   5.940 +            Bj = commitment.commit(bj.value, s1.value, s2.value)
   5.941 +
   5.942 +            # Broadcast B_j.
   5.943 +            results = self.broadcast(self.players.keys(), self.players.keys(), repr(Bj))
   5.944 +            result = gatherResults(results)
   5.945 +            self.schedule_callback(result, step2c, As, alphas, alpha_randomness, 
   5.946 +                                   ai, bj, r, (s1, s2))
   5.947 +            result.addErrback(self.error_handler)
   5.948 +            return result
   5.949 +        
   5.950 +        # 1) Every party P_i chooses random values a_i, r_i in Z_p X (Z_p)^2,
   5.951 +        #    compute alpha_i = Enc_eki(a_i) and Ai = Com_ck(a_i, r_i), and
   5.952 +        #    broadcast them.
   5.953 +
   5.954 +        # Every party P_i chooses random values a_i, r_i in Z_p X (Z_p)^2
   5.955 +        ai = random_number(field.modulus)
   5.956 +        r1 = random_number(field.modulus)
   5.957 +        r2 = random_number(field.modulus)
   5.958 +
   5.959 +        # compute alpha_i = Enc_eki(a_i) 
   5.960 +        n, g = self.players[self.id].pubkey
   5.961 +        alpha_randomness = rand.randint(1, long(n))
   5.962 +        alphai = encrypt_r(ai.value, alpha_randomness, (n, g))
   5.963 +        # and A_i = Com_ck(a_i, r_i).
   5.964 +        Ai = commitment.commit(ai.value, r1.value, r2.value)
   5.965 +
   5.966 +        # broadcast alpha_i and A_i.
   5.967 +        ds = self.broadcast(sorted(self.players.keys()), sorted(self.players.keys()), str(alphai) + ":" + repr(Ai))
   5.968 +
   5.969 +        result = gatherResults(ds)
   5.970 +        def split_alphas_and_As(ls):
   5.971 +            alphas = []
   5.972 +            As = []
   5.973 +            for x in ls:
   5.974 +                alpha, Ai = x.split(':')
   5.975 +                alphas.append(long(alpha))
   5.976 +                As.append(Ai)
   5.977 +            return alphas, As
   5.978 +        self.schedule_callback(result, split_alphas_and_As)
   5.979 +        self.schedule_callback(result, step2ab, ai, (r1, r2), alpha_randomness)
   5.980 +        result.addErrback(self.error_handler)
   5.981 +        return result
   5.982 +    
   5.983 +    def triple_test(self, field):
   5.984 +        """Generate a triple ``(a, b, c)`` where ``c = a * b``.
   5.985 +
   5.986 +        The triple ``(a, b, c)`` is checked against the 
   5.987 +        triple ``(x, y, z)`` and a random value ``r``.
   5.988 +
   5.989 +        """
   5.990 +        triple1 = self.triple_gen(field)
   5.991 +        triple2 = self.triple_gen(field)
   5.992 +        r = self.open(self.random_share(field))
   5.993 +        
   5.994 +        def check((v, oa, ob, oc, ox, oy, oz), a, b, c, ec):
   5.995 +            if v is 0:
   5.996 +                return None
   5.997 +            return (a, b, c, ec)
   5.998 +        
   5.999 +        def compute_value(((a, b, c, ec), (x, y, z, _), r)):
  5.1000 +            oa = self.open(a)
  5.1001 +            ob = self.open(b)
  5.1002 +            oc = self.open(c)
  5.1003 +            ox = self.open(x)
  5.1004 +            oy = self.open(y)
  5.1005 +            oz = self.open(z)
  5.1006 +            l = self._cmul(r, x, field)
  5.1007 +            m = self._cmul(r, y, field)
  5.1008 +            n = self._cmul(r*r, z, field)
  5.1009 +            d = c - self._basic_multiplication(a, b, l, m, n)
  5.1010 +            r = gather_shares([d, oa, ob, oc, ox, oy, oz])
  5.1011 +            r.addCallbacks(check, self.error_handler, callbackArgs=(a, b, c, ec))
  5.1012 +            return r
  5.1013 +
  5.1014 +        result = gatherResults([triple1, triple2, r])
  5.1015 +        self.schedule_callback(result, compute_value)
  5.1016 +        result.addErrback(self.error_handler)
  5.1017 +
  5.1018 +        # do actual communication
  5.1019 +        self.activate_reactor()
  5.1020 +
  5.1021 +        return result
  5.1022 +
  5.1023 +    def random_triple(self, field, number_of_requested_triples):
  5.1024 +        """Generate a list of triples ``(a, b, c)`` where ``c = a * b``.
  5.1025 +
  5.1026 +        The triple ``(a, b, c)`` is secure in the Fcrs-hybrid model.
  5.1027 +
  5.1028 +        """
  5.1029 +        self.program_counter[-1] += 1
  5.1030 +
  5.1031 +        M = []
  5.1032 +
  5.1033 +# print "Generating %i triples... relax, have a brak..." % ((1 + self.s_lambda) * (2 * self.d + 1) * number_of_requested_triples)
  5.1034 +
  5.1035 +        for x in xrange((1 + self.s_lambda) * (2 * self.d + 1) * number_of_requested_triples):
  5.1036 +            M.append(self.triple_test(field))
  5.1037 +
  5.1038 +        def step3(ls):
  5.1039 +            """Coin-flip a subset test_set of M of size lambda(2d + 1)M."""
  5.1040 +            size = self.s_lambda * (2 * self.d + 1) * number_of_requested_triples
  5.1041 +            inx = 0
  5.1042 +            p_half = field.modulus // 2
  5.1043 +            def coin_flip(v, ls, test_set):
  5.1044 +                candidate = ls.pop(0)
  5.1045 +                if p_half > v:
  5.1046 +                    test_set.append(candidate)
  5.1047 +                else:
  5.1048 +                    ls.append(candidate)
  5.1049 +                if size > len(test_set):
  5.1050 +                    r = self.random_share(field)
  5.1051 +                    r = self.output(r)
  5.1052 +                    self.schedule_callback(r, coin_flip, ls, test_set)
  5.1053 +                    r.addErrback(self.error_handler)
  5.1054 +                    return r
  5.1055 +                return ls, test_set
  5.1056 +            r = self.random_share(field)
  5.1057 +            r = self.output(r)
  5.1058 +            self.schedule_callback(r, coin_flip, ls, [])
  5.1059 +            r.addErrback(self.error_handler)
  5.1060 +            return r            
  5.1061 +
  5.1062 +        def step45(lists):
  5.1063 +            """For all i in test_set the parties reveal 
  5.1064 +            the randomness used for TripleTest() and checks that
  5.1065 +            the randomness is consistent with the actual values."""
  5.1066 +            M_without_test_set = lists[0]
  5.1067 +            T = lists[1]
  5.1068 +
  5.1069 +            def defer_share(xi, (rho1, rho2), commitment):
  5.1070 +                d1 = Deferred()
  5.1071 +                d2 = Deferred()
  5.1072 +                d3 = Deferred()
  5.1073 +                d4 = Deferred()
  5.1074 +                d1.callback(xi)
  5.1075 +                d2.callback(rho1)
  5.1076 +                d3.callback(rho2)
  5.1077 +                d4.callback(commitment)
  5.1078 +                return gatherResults([d1, d2, d3, d4])
  5.1079 +
  5.1080 +            def get_share(x, ls):
  5.1081 +                share = ls[x * 4]
  5.1082 +                rho1 = ls[x * 4 + 1]
  5.1083 +                rho2 = ls[x * 4 + 2]
  5.1084 +                commitment = ls[x * 4 + 3]
  5.1085 +                return (share, rho1, rho2, commitment)
  5.1086 +
  5.1087 +            def send_share(player_id, pc, a):
  5.1088 +                self._send_orlandi_share(player_id, pc, a.share, a.rho, a.commitment) 
  5.1089 +                
  5.1090 +            def receive_shares(player_id):
  5.1091 +                Cx = Deferred()
  5.1092 +                xi = self._expect_share(player_id, field)
  5.1093 +                rho1 = self._expect_share(player_id, field)
  5.1094 +                rho2 = self._expect_share(player_id, field)
  5.1095 +                self._expect_data(player_id, TEXT, Cx)
  5.1096 +                Cx.addCallbacks(lambda Cx: commitment.deserialize(Cx), 
  5.1097 +                                        self.error_handler)
  5.1098 +                return gatherResults([xi, rho1, rho2, Cx])
  5.1099 +
  5.1100 +            def send_long(player_id, pc, l):
  5.1101 +                self.protocols[player_id].sendData(pc, TEXT, str(l))
  5.1102 +
  5.1103 +            def receive_long(player_id):
  5.1104 +                l = Deferred()
  5.1105 +                self._expect_data(player_id, TEXT, l)
  5.1106 +                l.addCallbacks(lambda x: long(x), self.error_handler)
  5.1107 +                return l
  5.1108 +
  5.1109 +            def defer_value(l):
  5.1110 +                d = Deferred()
  5.1111 +                d.callback(l)
  5.1112 +                return d
  5.1113 +
  5.1114 +            def check((ais, bis, cis, alpha_randomness, dijs), alphas, gammas):
  5.1115 +                """So if B receives ai, bi, dij, ri, si, and the randomness used in the
  5.1116 +                computation of alpha, he then checks that:
  5.1117 +                1) the alpha_i he received is equals to the encryption of ai and the
  5.1118 +                commitment he received, Ai, is equal to the commitment of ai and ri
  5.1119 +                2) the commitment he received, Bj, is equal to the commitment of bj and sj
  5.1120 +                3) the gammaij he received is equal to the gammaij he now computes based on
  5.1121 +                the values he reveives
  5.1122 +                4) a, b, c is a triple, a * b = c
  5.1123 +                5) ai, bi < p and dij < p^3
  5.1124 +                """
  5.1125 +                a = 0
  5.1126 +                a_rho1 = 0
  5.1127 +                a_rho2 = 0
  5.1128 +                b = 0
  5.1129 +                b_rho1 = 0
  5.1130 +                b_rho2 = 0
  5.1131 +                c = 0
  5.1132 +                c_rho1 = 0
  5.1133 +                c_rho2 = 0
  5.1134 +                
  5.1135 +                for x in xrange(len(ais)):
  5.1136 +                    (ai, a_rhoi1, a_rhoi2, A) = ais[x]
  5.1137 +                    (bi, b_rhoi1, b_rhoi2, B) = bis[x]
  5.1138 +                    (ci, c_rhoi1, c_rhoi2, C) = cis[x]
  5.1139 +                    # 5) ai, bi < p...
  5.1140 +                    if ai >= field.modulus:
  5.1141 +                        raise OrlandiException("Inconsistent share ai, ai >= p: %i" % ai)
  5.1142 +                    if bi >= field.modulus:
  5.1143 +                        raise OrlandiException("Inconsistent share bi, bi >= p: %i" % bi)
  5.1144 +                    a += ai
  5.1145 +                    a_rho1 += a_rhoi1
  5.1146 +                    a_rho2 += a_rhoi2
  5.1147 +                    b += bi
  5.1148 +                    b_rho1 += b_rhoi1
  5.1149 +                    b_rho2 += b_rhoi2
  5.1150 +                    c += ci
  5.1151 +                    c_rho1 += c_rhoi1
  5.1152 +                    c_rho2 += c_rhoi2
  5.1153 +                    # 1) the alpha_i he received is equals to the encryption of ai...
  5.1154 +                    alphai = encrypt_r(ai.value, alpha_randomness[x],
  5.1155 +                                       self.players[x + 1].pubkey)
  5.1156 +                    if not(alphas[x] == alphai):
  5.1157 +                        raise OrlandiException("Inconsistent alpha from player %i, %i, %i" % (x + 1, alphas[x], alphai))
  5.1158 +
  5.1159 +                A1 = commitment.commit(a.value, a_rho1.value, a_rho2.value)
  5.1160 +                B1 = commitment.commit(b.value, b_rho1.value, b_rho2.value)
  5.1161 +                C1 = commitment.commit(c.value, c_rho1.value, c_rho2.value)
  5.1162 +
  5.1163 +                # 1) ... and the commitment he received, Ai, is equal
  5.1164 +                # to the commitment of ai and ri.
  5.1165 +                if A1 != A:
  5.1166 +                    raise OrlandiException("Inconsistent commitment for value %s, found %s expected %s." % (a, A1, A))
  5.1167 +                # 2) the commitment he received, Bj, is equal to the commitment of bj and sj.
  5.1168 +                if B1 != B:
  5.1169 +                    raise OrlandiException("Inconsistent commitment for value %s, found %s expected %s." % (b, B1, B))
  5.1170 +                if C1 != C:
  5.1171 +                    raise OrlandiException("Inconsistent commitment for value %s, found %s expected %s." % (c, C1, C))
  5.1172 +                # 4) a, b, c is a triple, a * b = c
  5.1173 +                if a * b != c:
  5.1174 +                    raise OrlandiException("Inconsistent triple, %i * %i does not equals %i." % (a, b, c))
  5.1175 +
  5.1176 +
  5.1177 +                # 3) the gammaij he received is equal to the gammaij he now computes based on
  5.1178 +                # the values he reveives
  5.1179 +                for j in xrange(len(ais)):
  5.1180 +                    n = self.players[self.id].pubkey[0]
  5.1181 +                    nsq = n * n
  5.1182 +                    dij = dijs[j]
  5.1183 +                    # 5) ... and dij < p^3.
  5.1184 +                    if dij >= (field.modulus**3):
  5.1185 +                        raise OrlandiException("Inconsistent random value dij %i from player %i" % (dij, j + 1))
  5.1186 +                    # Enc_ek_i(1;1)^d_ij
  5.1187 +                    enc = encrypt_r(1, 1, self.players[self.id].pubkey)
  5.1188 +                    t1 = pow(enc, dij.value, nsq)
  5.1189 +                    # alpha_i^b_j.
  5.1190 +                    t2 = pow(alphas[self.id - 1], bis[j][0].value, nsq)
  5.1191 +                    # gamma_ij = alpha_i^b_j Enc_ek_i(1;1)^d_ij
  5.1192 +                    gammaij = (t2) * (t1) % nsq
  5.1193 +                    if gammaij != gammas[j]:
  5.1194 +                        raise OrlandiException("Inconsistent gammaij, %i, %i" % (gammaij, gammas[j]))
  5.1195 +
  5.1196 +                return True
  5.1197 +
  5.1198 +            dls_all = []
  5.1199 +            for (a, b, c, (alphas, alpha_randomness, gammas, dijs)) in T:
  5.1200 +                ds_a = [None] * len(self.players)
  5.1201 +                ds_b = [None] * len(self.players)
  5.1202 +                ds_c = [None] * len(self.players)
  5.1203 +                ds_alpha_randomness = [None] * len(self.players)
  5.1204 +                ds_dijs = [None] * len(self.players)
  5.1205 +                pc = tuple(self.program_counter)
  5.1206 +
  5.1207 +                for player_id in xrange(1, len(self.players.keys()) + 1):
  5.1208 +                    if player_id == self.id:
  5.1209 +                        ds_a[player_id - 1] = defer_share(a.share, a.rho, a.commitment)
  5.1210 +                        ds_b[player_id - 1] = defer_share(b.share, b.rho, b.commitment)
  5.1211 +                        ds_c[player_id - 1] = defer_share(c.share, c.rho, c.commitment)
  5.1212 +                        ds_alpha_randomness[player_id - 1] = defer_value(alpha_randomness)
  5.1213 +                        ds_dijs[player_id - 1] = defer_value(dijs[player_id - 1])
  5.1214 +                    # Receive and recombine shares if this player is a receiver.
  5.1215 +                    else:
  5.1216 +                        send_share(player_id, pc, a)
  5.1217 +                        send_share(player_id, pc, b)
  5.1218 +                        send_share(player_id, pc, c)
  5.1219 +                        send_long(player_id, pc, alpha_randomness)
  5.1220 +                        self.protocols[player_id].sendShare(pc, dijs[player_id - 1])
  5.1221 +
  5.1222 +                        ds_a[player_id - 1] = receive_shares(player_id)
  5.1223 +                        ds_b[player_id - 1] = receive_shares(player_id)
  5.1224 +                        ds_c[player_id - 1] = receive_shares(player_id)
  5.1225 +                        ds_alpha_randomness[player_id - 1] = receive_long(player_id)
  5.1226 +                        ds_dijs[player_id - 1] = self._expect_share(player_id, field)
  5.1227 +                dls_a = gatherResults(ds_a)
  5.1228 +                dls_b = gatherResults(ds_b)
  5.1229 +                dls_c = gatherResults(ds_c)
  5.1230 +                dls_dijs = gatherResults(ds_dijs)
  5.1231 +                dls_alpha_randomness = gatherResults(ds_alpha_randomness)
  5.1232 +
  5.1233 +            dls = gatherResults([dls_a, dls_b, dls_c, dls_alpha_randomness, dls_dijs])
  5.1234 +            dls.addCallbacks(check, self.error_handler, callbackArgs=[alphas, gammas])
  5.1235 +            dls_all.append(dls)
  5.1236 +
  5.1237 +            def result(x):
  5.1238 +                ls = []
  5.1239 +                for a, b, c, _ in M_without_test_set:
  5.1240 +                    ls.append((a, b, c))
  5.1241 +                return ls
  5.1242 +
  5.1243 +            dls_all = gatherResults(dls_all)
  5.1244 +            dls_all.addCallbacks(result, self.error_handler)
  5.1245 +            return dls_all
  5.1246 +
  5.1247 +        def step6(M_without_test_set):
  5.1248 +            """Partition M without test_set in number_of_requested_triples
  5.1249 +            random subsets M_i of size (2d + 1).
  5.1250 +            """
  5.1251 +            subsets = []
  5.1252 +            size = 2 * self.d + 1
  5.1253 +            for x in xrange(number_of_requested_triples):
  5.1254 +                subsets.append([])
  5.1255 +
  5.1256 +            def put_in_set(v, M_without_test_set, subsets):
  5.1257 +                if 0 == len(M_without_test_set):
  5.1258 +                    return subsets
  5.1259 +                v = v.value % number_of_requested_triples
  5.1260 +                if size > len(subsets[v]):
  5.1261 +                    subsets[v].append(M_without_test_set.pop(0))
  5.1262 +                r = self.random_share(field)
  5.1263 +                r = self.output(r)
  5.1264 +                self.schedule_callback(r, put_in_set, M_without_test_set, subsets)
  5.1265 +                r.addErrback(self.error_handler)
  5.1266 +                return r
  5.1267 +            r = self.random_share(field)
  5.1268 +            r = self.output(r)
  5.1269 +            self.schedule_callback(r, put_in_set, M_without_test_set, subsets)
  5.1270 +            r.addErrback(self.error_handler)
  5.1271 +            return r
  5.1272 +            
  5.1273 +
  5.1274 +        def step7(Msets):
  5.1275 +            """For i = 1,...,M do:
  5.1276 +            a) [a] <- Fpp(rand,...), [b] <- Fpp(rand,...)
  5.1277 +            b) [r] <- Fpp(rand,...), 
  5.1278 +            c) [c] <- LTMUL([a], [b], M_i)
  5.1279 +            d) Open([c] + [r])
  5.1280 +            """
  5.1281 +            ds = []
  5.1282 +            for Mi in Msets:
  5.1283 +                a = self.random_share(field)
  5.1284 +                b = self.random_share(field)
  5.1285 +                r = self.random_share(field)
  5.1286 +                c = self.leak_tolerant_mul(a, b, Mi)
  5.1287 +                d = self.open(c + r)
  5.1288 +                def return_abc(x, a, b, c):
  5.1289 +                    return a, b, c
  5.1290 +                d.addCallbacks(return_abc, self.error_handler, callbackArgs=(a, b, c))
  5.1291 +                ds.append(d)
  5.1292 +            result = gather_shares(ds)
  5.1293 +            def triples(ls):
  5.1294 +                return ls
  5.1295 +            result.addCallbacks(triples, self.error_handler)
  5.1296 +            return result
  5.1297 +
  5.1298 +        result = gatherResults(M)
  5.1299 +        self.schedule_callback(result, step3)
  5.1300 +        result.addErrback(self.error_handler)
  5.1301 +        self.schedule_callback(result, step45)
  5.1302 +        self.schedule_callback(result, step6)
  5.1303 +        self.schedule_callback(result, step7)
  5.1304 +
  5.1305 +        # do actual communication
  5.1306 +        self.activate_reactor()
  5.1307 +
  5.1308 +        s = Share(self, field)
  5.1309 +        def f(ls, s):
  5.1310 +            s.callback(ls)
  5.1311 +        result.addCallbacks(f, self.error_handler, callbackArgs=(s,))
  5.1312 +        return number_of_requested_triples, s
  5.1313 +
  5.1314 +    def error_handler(self, ex):
  5.1315 +        print "Error: ", ex
  5.1316 +        return ex
  5.1317 +
     6.1 --- a/viff/paillier.py	Wed Oct 07 15:23:12 2009 +0200
     6.2 +++ b/viff/paillier.py	Thu Oct 08 14:27:37 2009 +0200
     6.3 @@ -28,7 +28,7 @@
     6.4  import gmpy
     6.5  
     6.6  from viff.runtime import Runtime, Share, gather_shares
     6.7 -from viff.runtime import PAILLIER
     6.8 +from viff.constants import PAILLIER
     6.9  from viff.util import rand, find_random_prime
    6.10  
    6.11  def L(u, n):
     7.1 --- a/viff/passive.py	Wed Oct 07 15:23:12 2009 +0200
     7.2 +++ b/viff/passive.py	Thu Oct 08 14:27:37 2009 +0200
     7.3 @@ -472,6 +472,7 @@
     7.4      def prss_powerchains(self, max=7, quantity=20):
     7.5          """Does *quantity* times the same as :meth:`prss_powerchain`.
     7.6          Used for preprocessing."""
     7.7 +        quantity = min(quantity, 20)
     7.8          shares = self.prss_share_random_multi(GF256, quantity)
     7.9          return quantity, succeed([self.powerchain(share, max)
    7.10                                    for share in shares])
     8.1 --- a/viff/runtime.py	Wed Oct 07 15:23:12 2009 +0200
     8.2 +++ b/viff/runtime.py	Thu Oct 08 14:27:37 2009 +0200
     8.3 @@ -41,6 +41,7 @@
     8.4  
     8.5  from viff.field import GF256, FieldElement
     8.6  from viff.util import wrapper, rand, deep_wait, track_memory_usage, begin, end
     8.7 +from viff.constants import SHARE
     8.8  import viff.reactor
     8.9  
    8.10  from twisted.internet import reactor
    8.11 @@ -51,13 +52,6 @@
    8.12  from twisted.internet.protocol import ReconnectingClientFactory, ServerFactory
    8.13  from twisted.protocols.basic import Int16StringReceiver
    8.14  
    8.15 -# Constants used by ShareExchanger.
    8.16 -SHARE    = 0
    8.17 -ECHO     = 1
    8.18 -READY    = 2
    8.19 -SEND     = 3
    8.20 -PAILLIER = 4
    8.21 -
    8.22  
    8.23  class Share(Deferred):
    8.24      """A shared number.
    8.25 @@ -382,6 +376,65 @@
    8.26          """Disconnect this protocol instance."""
    8.27          self.transport.loseConnection()
    8.28  
    8.29 +class SelfShareExchanger(ShareExchanger):
    8.30 +
    8.31 +    def __init__(self, id, factory):
    8.32 +        ShareExchanger.__init__(self)
    8.33 +        self.peer_id = id
    8.34 +        self.factory = factory
    8.35 +
    8.36 +    def stringReceived(self, program_counter, data_type, data):
    8.37 +        """Called when a share is received.
    8.38 +
    8.39 +        The string received is unpacked into the program counter, and
    8.40 +        a data part. The data is passed the appropriate Deferred in
    8.41 +        :class:`self.incoming_data`.
    8.42 +        """
    8.43 +        try:
    8.44 +            key = (program_counter, data_type)
    8.45 +                         
    8.46 +            if key in self.waiting_deferreds:
    8.47 +                deq = self.waiting_deferreds[key]
    8.48 +                deferred = deq.popleft()
    8.49 +                if not deq:
    8.50 +                    del self.waiting_deferreds[key]
    8.51 +                self.factory.runtime.handle_deferred_data(deferred, data)
    8.52 +            else:
    8.53 +                deq = self.incoming_data.setdefault(key, deque())
    8.54 +                deq.append(data)
    8.55 +        except struct.error, e:
    8.56 +            self.factory.runtime.abort(self, e)
    8.57 +
    8.58 +    def sendData(self, program_counter, data_type, data):
    8.59 +        """Send data to the self.id."""
    8.60 +        self.stringReceived(program_counter, data_type, data)
    8.61 +
    8.62 +    def loseConnection(self):
    8.63 +        """Disconnect this protocol instance."""
    8.64 +        self.lost_connection.callback(self)
    8.65 +        return None
    8.66 +
    8.67 +
    8.68 +class SelfShareExchangerFactory(ReconnectingClientFactory, ServerFactory):
    8.69 +    """Factory for creating SelfShareExchanger protocols."""
    8.70 +
    8.71 +    protocol = SelfShareExchanger
    8.72 +    maxDelay = 3
    8.73 +    factor = 1.234567 # About half of the Twisted default
    8.74 +
    8.75 +    def __init__(self, runtime):
    8.76 +        """Initialize the factory."""
    8.77 +        self.runtime = runtime
    8.78 +
    8.79 +    def identify_peer(self, protocol):
    8.80 +        raise Exception("Is identify_peer necessary?")
    8.81 +
    8.82 +    def clientConnectionLost(self, connector, reason):
    8.83 +        reason.trap(ConnectionDone)
    8.84 +
    8.85 +class FakeTransport(object):
    8.86 +    def close(self):
    8.87 +        return True
    8.88  
    8.89  class ShareExchangerFactory(ReconnectingClientFactory, ServerFactory):
    8.90      """Factory for creating ShareExchanger protocols."""
    8.91 @@ -540,7 +593,9 @@
    8.92          self.players = {}
    8.93          # Add ourselves, but with no protocol since we wont be
    8.94          # communicating with ourselves.
    8.95 -        self.add_player(player, None)
    8.96 +        protocol = SelfShareExchanger(self.id, SelfShareExchangerFactory(self))
    8.97 +        protocol.transport = FakeTransport()
    8.98 +        self.add_player(player, protocol)
    8.99  
   8.100          #: Queue of deferreds and data.
   8.101          self.deferred_queue = deque()
   8.102 @@ -556,9 +611,7 @@
   8.103      def add_player(self, player, protocol):
   8.104          self.players[player.id] = player
   8.105          self.num_players = len(self.players)
   8.106 -        # There is no protocol for ourselves, so we wont add that:
   8.107 -        if protocol is not None:
   8.108 -            self.protocols[player.id] = protocol
   8.109 +        self.protocols[player.id] = protocol
   8.110  
   8.111      def shutdown(self):
   8.112          """Shutdown the runtime.
   8.113 @@ -688,10 +741,12 @@
   8.114          return result
   8.115  
   8.116      def _expect_data(self, peer_id, data_type, deferred):
   8.117 -        assert peer_id != self.id, "Do not expect data from yourself!"
   8.118          # Convert self.program_counter to a hashable value in order to
   8.119          # use it as a key in self.protocols[peer_id].incoming_data.
   8.120          pc = tuple(self.program_counter)
   8.121 +        return self._expect_data_with_pc(pc, peer_id, data_type, deferred)
   8.122 +
   8.123 +    def _expect_data_with_pc(self, pc, peer_id, data_type, deferred):
   8.124          key = (pc, data_type)
   8.125  
   8.126          if key in self.protocols[peer_id].incoming_data:
   8.127 @@ -776,7 +831,8 @@
   8.128              while items < len(program_counters):
   8.129                  self.increment_pc()
   8.130                  self.fork_pc()
   8.131 -                item_count, result = func(*args)
   8.132 +                item_count, result = func(*args,
   8.133 +                                          **{"quantity": len(program_counters) - items})
   8.134                  items += item_count
   8.135                  results.append(result)
   8.136                  self.unfork_pc()
     9.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     9.2 +++ b/viff/test/test_hash_broadcast.py	Thu Oct 08 14:27:37 2009 +0200
     9.3 @@ -0,0 +1,181 @@
     9.4 +# Copyright 2009 VIFF Development Team.
     9.5 +#
     9.6 +# This file is part of VIFF, the Virtual Ideal Functionality Framework.
     9.7 +#
     9.8 +# VIFF is free software: you can redistribute it and/or modify it
     9.9 +# under the terms of the GNU Lesser General Public License (LGPL) as
    9.10 +# published by the Free Software Foundation, either version 3 of the
    9.11 +# License, or (at your option) any later version.
    9.12 +#
    9.13 +# VIFF is distributed in the hope that it will be useful, but WITHOUT
    9.14 +# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
    9.15 +# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
    9.16 +# Public License for more details.
    9.17 +#
    9.18 +# You should have received a copy of the GNU Lesser General Public
    9.19 +# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
    9.20 +
    9.21 +from twisted.internet.defer import gatherResults, Deferred, DeferredList
    9.22 +
    9.23 +from viff.test.util import RuntimeTestCase, protocol
    9.24 +from viff.field import GF
    9.25 +from viff.runtime import Share
    9.26 +
    9.27 +from viff.comparison import Toft05Runtime
    9.28 +from viff.hash_broadcast import HashBroadcastMixin
    9.29 +
    9.30 +class BroadcastRuntime(Toft05Runtime, HashBroadcastMixin):
    9.31 +    """Mix of :class:`Toft05Runtime` and
    9.32 +    :class:`HashBroadcastRuntime`."""
    9.33 +    pass
    9.34 +
    9.35 +class HashBroadcastTest(RuntimeTestCase):
    9.36 +    """Test for the hash broadcast mixin."""
    9.37 +
    9.38 +    # Number of players.
    9.39 +    num_players = 3
    9.40 +
    9.41 +    runtime_class = BroadcastRuntime
    9.42 +
    9.43 +    timeout = 10
    9.44 +    @protocol
    9.45 +    def test_send(self, runtime):
    9.46 +        """Test of send a value."""
    9.47 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
    9.48 +
    9.49 +        value = 42
    9.50 +
    9.51 +        receivers = [2, 3]
    9.52 +        if 1 == runtime.id:
    9.53 +            d = runtime.broadcast([1], receivers, str(value))
    9.54 +        else:
    9.55 +            d = runtime.broadcast([1], receivers)
    9.56 +        def check(x):
    9.57 +            self.assertEquals(int(x), 42)
    9.58 +        d.addCallback(check)
    9.59 +        return d
    9.60 +            
    9.61 +
    9.62 +    @protocol
    9.63 +    def test_send_two_senders_in_parallel(self, runtime):
    9.64 +        """Test of send a value."""
    9.65 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
    9.66 +
    9.67 +        def check(ls):
    9.68 +            for s, x in ls:
    9.69 +                self.assertEquals(int(x), 42)
    9.70 +            return ls
    9.71 +
    9.72 +        value = 42
    9.73 +
    9.74 +        receivers = [2, 3]
    9.75 +        if 1 == runtime.id:
    9.76 +            d1 = runtime.broadcast([1], receivers, str(value))
    9.77 +        else:
    9.78 +            d1 = runtime.broadcast([1], receivers)
    9.79 +
    9.80 +        if 2 == runtime.id:
    9.81 +            d2 = runtime.broadcast([2], [3], str(value))
    9.82 +        else:
    9.83 +            d2 = runtime.broadcast([2], [3])
    9.84 +
    9.85 +        ds = [d1]
    9.86 +        if [] != d2:
    9.87 +            ds.append(d2)
    9.88 +        dls = DeferredList(ds)
    9.89 +        dls.addCallback(check)
    9.90 +        return dls
    9.91 +            
    9.92 +    @protocol
    9.93 +    def test_send_multiple_senders_in_one_burst(self, runtime):
    9.94 +        """Test of send a value."""
    9.95 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
    9.96 +
    9.97 +        value = 42
    9.98 +        if 1 == runtime.id:
    9.99 +            value = 7
   9.100 +
   9.101 +        if 1 == runtime.id or 3 == runtime.id:
   9.102 +            ds = runtime.broadcast([1, 3], [2], str(value))
   9.103 +
   9.104 +        if 2 == runtime.id:
   9.105 +            ds = runtime.broadcast([1, 3], [2])
   9.106 +            dls = DeferredList(ds)
   9.107 +            def check(ls):
   9.108 +                self.assertEquals(int(ls[0][1]), 7)
   9.109 +                self.assertEquals(int(ls[1][1]), 42)
   9.110 +                return ls
   9.111 +            dls.addCallback(check)
   9.112 +            return dls
   9.113 +        return None
   9.114 +            
   9.115 +
   9.116 +    @protocol
   9.117 +    def test_sender_in_receivers(self, runtime):
   9.118 +        """Test of send a value."""
   9.119 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
   9.120 +
   9.121 +        value = 42
   9.122 +        if 1 == runtime.id:
   9.123 +            d = runtime.broadcast([1], [1, 2, 3], str(value))
   9.124 +        else:
   9.125 +            d = runtime.broadcast([1], [1, 2, 3])
   9.126 +
   9.127 +        def check(x):
   9.128 +            self.assertEquals(int(x), 42)
   9.129 +            return x
   9.130 +        d.addCallback(check)
   9.131 +        return d
   9.132 +
   9.133 +    @protocol
   9.134 +    def test_complex(self, runtime):
   9.135 +        def check(ls):
   9.136 +            for x, v in ls:
   9.137 +                self.assertEquals(runtime.list_str(v), ['7', '9', '13'])
   9.138 +            
   9.139 +        receivers = [1, 2, 3]
   9.140 +        def exchange((xi, rhoi1, rhoi2)):
   9.141 +            # Send share to all receivers.
   9.142 +            ds = runtime.broadcast(receivers, receivers, str((str(xi), str(rhoi1), str(rhoi2))))
   9.143 +            dls = DeferredList(ds)
   9.144 +            dls.addCallbacks(check, runtime.error_handler)
   9.145 +            return dls
   9.146 +
   9.147 +        result = Deferred()
   9.148 +        result.addCallbacks(exchange, runtime.error_handler)
   9.149 +        result.callback((7, 9, 13))
   9.150 +        return result
   9.151 +
   9.152 +    @protocol
   9.153 +    def test_complex2(self, runtime):
   9.154 +        def check(ls):
   9.155 +            if (2 == runtime.id) or (1 == runtime.id):
   9.156 +                self.assertEquals(ls[0][1], "V1")
   9.157 +                self.assertEquals(ls[1][1], "V1")
   9.158 +                self.assertEquals(ls[2][1], "V1")
   9.159 +                self.assertEquals(ls[3][1], "V2")
   9.160 +            else:
   9.161 +                self.assertEquals(ls[0][1], "V1")
   9.162 +                self.assertEquals(ls[1][1], "V1")
   9.163 +                self.assertEquals(ls[2][1], "V1")
   9.164 +                self.assertEquals(ls[3][1], "V2")
   9.165 +                self.assertEquals(ls[4][1], "V2")
   9.166 +        field = self.Zp
   9.167 +        results = []
   9.168 +        results += runtime.broadcast(runtime.players.keys(), runtime.players.keys(), "V1")
   9.169 +        if runtime.id in [1, 2]:
   9.170 +            v = runtime.broadcast([1, 2], [3], "V2")
   9.171 +            if isinstance(v, list):
   9.172 +                results += v
   9.173 +            else:
   9.174 +                results.append(v)
   9.175 +        else:
   9.176 +            results += runtime.broadcast([1, 2], [3])
   9.177 +        if 3 == runtime.id:
   9.178 +            results += [runtime.broadcast([3], runtime.players.keys(), str(7))]
   9.179 +        else:
   9.180 +            results += [runtime.broadcast([3], runtime.players.keys())]
   9.181 +        dls = DeferredList(results)
   9.182 +        runtime.schedule_callback(dls, check)
   9.183 +        dls.addErrback(runtime.error_handler)
   9.184 +        return dls
    10.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    10.2 +++ b/viff/test/test_orlandi_runtime.py	Thu Oct 08 14:27:37 2009 +0200
    10.3 @@ -0,0 +1,825 @@
    10.4 +# Copyright 2009 VIFF Development Team.
    10.5 +#
    10.6 +# This file is part of VIFF, the Virtual Ideal Functionality Framework.
    10.7 +#
    10.8 +# VIFF is free software: you can redistribute it and/or modify it
    10.9 +# under the terms of the GNU Lesser General Public License (LGPL) as
   10.10 +# published by the Free Software Foundation, either version 3 of the
   10.11 +# License, or (at your option) any later version.
   10.12 +#
   10.13 +# VIFF is distributed in the hope that it will be useful, but WITHOUT
   10.14 +# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
   10.15 +# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
   10.16 +# Public License for more details.
   10.17 +#
   10.18 +# You should have received a copy of the GNU Lesser General Public
   10.19 +# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
   10.20 +
   10.21 +from twisted.internet.defer import gatherResults, DeferredList
   10.22 +
   10.23 +from viff.test.util import RuntimeTestCase, protocol, BinaryOperatorTestCase
   10.24 +from viff.runtime import Share, gather_shares
   10.25 +from viff.orlandi import OrlandiRuntime, OrlandiShare
   10.26 +
   10.27 +from viff.field import FieldElement, GF
   10.28 +from viff.passive import PassiveRuntime
   10.29 +
   10.30 +from viff.util import rand
   10.31 +
   10.32 +# import commitment
   10.33 +
   10.34 +
   10.35 +def _get_triple(runtime, field):
   10.36 +    n = field(0)
   10.37 +    Ca = commitment.commit(6, 0, 0)
   10.38 +    a = OrlandiShare(runtime, field, field(2), (n, n), Ca)
   10.39 +    Cb = commitment.commit(12, 0, 0)
   10.40 +    b = OrlandiShare(runtime, field, field(4), (n, n), Cb)
   10.41 +    Cc = commitment.commit(72, 0, 0)
   10.42 +    c = OrlandiShare(runtime, field, field(24), (n, n), Cc)
   10.43 +    return (a, b, c)
   10.44 +
   10.45 +
   10.46 +class OrlandiBasicCommandsTest(RuntimeTestCase):
   10.47 +    """Test for basic commands."""
   10.48 +
   10.49 +    # Number of players.
   10.50 +    num_players = 3
   10.51 +
   10.52 +    runtime_class = OrlandiRuntime
   10.53 +
   10.54 +    @protocol
   10.55 +    def test_secret_share(self, runtime):
   10.56 +        """Test sharing of random numbers."""
   10.57 +
   10.58 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
   10.59 +
   10.60 +        def check((xi, (rho1, rho2), Cr)):
   10.61 +            # Check that we got the expected number of shares.
   10.62 +            self.assert_type(xi, FieldElement)
   10.63 +            self.assert_type(rho1, FieldElement)
   10.64 +            self.assert_type(rho2, FieldElement)
   10.65 +            self.assert_type(Cr, commitment.Commitment)
   10.66 +
   10.67 +        if 1 == runtime.id:
   10.68 +            share = runtime.secret_share([1], self.Zp, 42)
   10.69 +        else:
   10.70 +            share = runtime.secret_share([1], self.Zp)
   10.71 +        share.addCallback(check)
   10.72 +        return share
   10.73 +
   10.74 +    test_secret_share.skip = "Commitment module is not included in VIFF."
   10.75 +
   10.76 +    @protocol
   10.77 +    def test_open_secret_share(self, runtime):
   10.78 +        """Test sharing and open of a number."""
   10.79 +
   10.80 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
   10.81 +
   10.82 +        def check(v):
   10.83 +            self.assertEquals(v, 42)
   10.84 +
   10.85 +        if 1 == runtime.id:
   10.86 +            x = runtime.secret_share([1], self.Zp, 42)
   10.87 +        else:
   10.88 +            x = runtime.secret_share([1], self.Zp)
   10.89 +        d = runtime.open(x)
   10.90 +        d.addCallback(check)
   10.91 +        return d
   10.92 +
   10.93 +    test_open_secret_share.skip = "Commitment module is not included in VIFF."
   10.94 +
   10.95 +    @protocol
   10.96 +    def test_random_share(self, runtime):
   10.97 +        """Test creation of a random shared number."""
   10.98 +
   10.99 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  10.100 +
  10.101 +        def check(v):
  10.102 +            self.assertEquals(True, True)           
  10.103 +
  10.104 +        x = runtime.random_share(self.Zp)
  10.105 +        d = runtime.open(x)
  10.106 +        d.addCallback(check)
  10.107 +        return d
  10.108 + 
  10.109 +    test_random_share.skip = "Commitment module is not included in VIFF."
  10.110 +
  10.111 +    @protocol
  10.112 +    def test_sum(self, runtime):
  10.113 +        """Test addition of two numbers."""
  10.114 +
  10.115 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  10.116 + 
  10.117 +        x1 = 42
  10.118 +        y1 = 7
  10.119 +
  10.120 +        def check(v):
  10.121 +            self.assertEquals(v, x1 + y1)
  10.122 +
  10.123 +        if 1 == runtime.id:
  10.124 +            x2 = runtime.secret_share([1], self.Zp, x1)
  10.125 +        else:
  10.126 +            x2 = runtime.secret_share([1], self.Zp)
  10.127 +
  10.128 +        if 3 == runtime.id:
  10.129 +            y2 = runtime.secret_share([3], self.Zp, y1)
  10.130 +        else:
  10.131 +            y2 = runtime.secret_share([3], self.Zp)
  10.132 +
  10.133 +        z2 = runtime.add(x2, y2)
  10.134 +        d = runtime.open(z2)
  10.135 +        d.addCallback(check)
  10.136 +        return d
  10.137 +
  10.138 +    test_sum.skip = "Commitment module is not included in VIFF."
  10.139 +
  10.140 +    @protocol
  10.141 +    def test_sum_plus(self, runtime):
  10.142 +        """Test addition of two numbers."""
  10.143 +
  10.144 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  10.145 +
  10.146 +        x1 = 42
  10.147 +        y1 = 7
  10.148 +
  10.149 +        def check(v):
  10.150 +            self.assertEquals(v, x1 + y1)
  10.151 +
  10.152 +        if 1 == runtime.id:
  10.153 +            x2 = runtime.secret_share([1], self.Zp, x1)
  10.154 +        else:
  10.155 +            x2 = runtime.secret_share([1], self.Zp)
  10.156 +
  10.157 +        if 3 == runtime.id:
  10.158 +            y2 = runtime.secret_share([3], self.Zp, y1)
  10.159 +        else:
  10.160 +            y2 = runtime.secret_share([3], self.Zp)
  10.161 +
  10.162 +        z2 = x2 + y2
  10.163 +        d = runtime.open(z2)
  10.164 +        d.addCallback(check)
  10.165 +        return d
  10.166 +
  10.167 +    test_sum_plus.skip = "Commitment module is not included in VIFF."
  10.168 +
  10.169 +    @protocol
  10.170 +    def test_sum_constant(self, runtime):
  10.171 +        """Test addition of two numbers."""
  10.172 +
  10.173 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  10.174 +
  10.175 +        x1 = 42
  10.176 +        y1 = 7
  10.177 +
  10.178 +        def check(v):
  10.179 +            self.assertEquals(v, x1 + y1)
  10.180 +
  10.181 +        if 1 == runtime.id:
  10.182 +            x2 = runtime.secret_share([1], self.Zp, x1)
  10.183 +        else:
  10.184 +            x2 = runtime.secret_share([1], self.Zp)
  10.185 +
  10.186 +        z2 = x2 + y1
  10.187 +        d = runtime.open(z2)
  10.188 +        d.addCallback(check)
  10.189 +        return d
  10.190 +
  10.191 +    test_sum_constant.skip = "Commitment module is not included in VIFF."
  10.192 +
  10.193 +    @protocol
  10.194 +    def test_sub(self, runtime):
  10.195 +        """Test subtration of two numbers."""
  10.196 +
  10.197 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  10.198 +
  10.199 +        x1 = 42
  10.200 +        y1 = 7
  10.201 + 
  10.202 +        def check(v):
  10.203 +            self.assertEquals(v, x1 - y1)
  10.204 +
  10.205 +        if 1 == runtime.id:
  10.206 +            x2 = runtime.secret_share([1], self.Zp, x1)
  10.207 +        else:
  10.208 +            x2 = runtime.secret_share([1], self.Zp)
  10.209 +
  10.210 +        if 3 == runtime.id:
  10.211 +            y2 = runtime.secret_share([3], self.Zp, y1)
  10.212 +        else:
  10.213 +            y2 = runtime.secret_share([3], self.Zp)
  10.214 +
  10.215 +        z2 = runtime.sub(x2, y2)
  10.216 +        d = runtime.open(z2)
  10.217 +        d.addCallback(check)
  10.218 +        return d
  10.219 +
  10.220 +    test_sub.skip = "Commitment module is not included in VIFF."
  10.221 +
  10.222 +    @protocol
  10.223 +    def test_sub_minus(self, runtime):
  10.224 +        """Test subtration of two numbers."""
  10.225 +
  10.226 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  10.227 +
  10.228 +        x1 = 42
  10.229 +        y1 = 7
  10.230 +
  10.231 +        def check(v):
  10.232 +            self.assertEquals(v, x1 - y1)
  10.233 +
  10.234 +        if 1 == runtime.id:
  10.235 +            x2 = runtime.secret_share([1], self.Zp, x1)
  10.236 +        else:
  10.237 +            x2 = runtime.secret_share([1], self.Zp)
  10.238 +
  10.239 +        if 3 == runtime.id:
  10.240 +            y2 = runtime.secret_share([3], self.Zp, y1)
  10.241 +        else:
  10.242 +            y2 = runtime.secret_share([3], self.Zp)
  10.243 +
  10.244 +        z2 = x2 - y2
  10.245 +        d = runtime.open(z2)
  10.246 +        d.addCallback(check)
  10.247 +        return d
  10.248 +
  10.249 +    test_sub_minus.skip = "Commitment module is not included in VIFF."
  10.250 +
  10.251 +    @protocol
  10.252 +    def test_sub_constant(self, runtime):
  10.253 +        """Test subtration of two numbers."""
  10.254 +
  10.255 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  10.256 +
  10.257 +        x1 = 42
  10.258 +        y1 = 7
  10.259 +
  10.260 +        def check(v):
  10.261 +            self.assertEquals(v, x1 - y1)
  10.262 +
  10.263 +        if 1 == runtime.id:
  10.264 +            x2 = runtime.secret_share([1], self.Zp, x1)
  10.265 +        else:
  10.266 +            x2 = runtime.secret_share([1], self.Zp)
  10.267 +
  10.268 +        z2 = x2 - y1
  10.269 +        d = runtime.open(z2)
  10.270 +        d.addCallback(check)
  10.271 +        return d
  10.272 +
  10.273 +    test_sub_constant.skip = "Commitment module is not included in VIFF."
  10.274 +
  10.275 +class OrlandiAdvancedCommandsTest(RuntimeTestCase):
  10.276 +    """Test for advanced commands."""
  10.277 +    
  10.278 +    # Number of players.
  10.279 +    num_players = 3
  10.280 + 
  10.281 +    runtime_class = OrlandiRuntime
  10.282 +
  10.283 +    timeout = 800
  10.284 +
  10.285 +    @protocol
  10.286 +    def test_shift(self, runtime):
  10.287 +        """Test addition of the shift command."""
  10.288 +
  10.289 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  10.290 +        
  10.291 +        def check(v):
  10.292 +            self.assertEquals(v, 42)
  10.293 + 
  10.294 +        x = runtime.shift([2], self.Zp, 42)
  10.295 +        d = runtime.open(x)
  10.296 +        d.addCallback(check)
  10.297 +        return d
  10.298 +
  10.299 +    test_shift.skip = "Commitment module is not included in VIFF."
  10.300 +
  10.301 +    @protocol
  10.302 +    def test_shift_two_inputters(self, runtime):
  10.303 +        """Test addition of the shift command."""
  10.304 +
  10.305 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  10.306 +        
  10.307 +        def check(v):
  10.308 +            self.assertEquals(v, 42)
  10.309 + 
  10.310 +        x, y = runtime.shift([1,3], self.Zp, 42)
  10.311 +        d1 = runtime.open(x)
  10.312 +        d1.addCallback(check)
  10.313 +        d2 = runtime.open(y)
  10.314 +        d2.addCallback(check)
  10.315 +        return DeferredList([d1, d2])
  10.316 +
  10.317 +    test_shift_two_inputters.skip = "Commitment module is not included in VIFF."
  10.318 +
  10.319 +    @protocol
  10.320 +    def test_shift_two_consequtive_inputters(self, runtime):
  10.321 +        """Test addition of the shift command."""
  10.322 +
  10.323 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  10.324 +        
  10.325 +        def r1(ls):
  10.326 +            x, y = ls
  10.327 +            self.assertEquals(runtime.program_counter, [4])
  10.328 + 
  10.329 +        x = runtime.shift([1], self.Zp, 42)
  10.330 +        y = runtime.shift([2], self.Zp, 42)
  10.331 +        r = gather_shares([x, y])
  10.332 +        r.addCallback(r1)
  10.333 +        return r
  10.334 +
  10.335 +    test_shift_two_consequtive_inputters.skip = "Commitment module is not included in VIFF."
  10.336 +
  10.337 +    @protocol
  10.338 +    def test_shift_two_consequtive_inputters2(self, runtime):
  10.339 +        """Test addition of the shift command."""
  10.340 +
  10.341 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  10.342 +        
  10.343 +        def check(v):
  10.344 +            self.assertEquals(v, 42)
  10.345 +
  10.346 +        def r1((x, y)):
  10.347 +            self.assertEquals(x, 42)
  10.348 +            self.assertEquals(y, 42)
  10.349 + 
  10.350 +        x = runtime.shift([1], self.Zp, 42)
  10.351 +        y = runtime.shift([2], self.Zp, 42)
  10.352 +        r = gather_shares([runtime.open(x), runtime.open(y)])
  10.353 +        r.addCallback(r1)
  10.354 +        return r
  10.355 +
  10.356 +    test_shift_two_consequtive_inputters2.skip = "Commitment module is not included in VIFF."
  10.357 +
  10.358 +    @protocol
  10.359 +    def test_input(self, runtime):
  10.360 +        """Test of many uses of the input command."""
  10.361 +
  10.362 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  10.363 +
  10.364 +        count = 9
  10.365 +
  10.366 +        a_shares = []
  10.367 +        b_shares = []
  10.368 +        for i in range(count):
  10.369 +            inputter = (i % len(runtime.players)) + 1
  10.370 +            if inputter == runtime.id:
  10.371 +                a = rand.randint(0, self.Zp.modulus)
  10.372 +                b = rand.randint(0, self.Zp.modulus)
  10.373 +            else:
  10.374 +                a, b = None, None
  10.375 +            a_shares.append(runtime.input([inputter], self.Zp, a))
  10.376 +            b_shares.append(runtime.input([inputter], self.Zp, b))
  10.377 +        shares_ready = gather_shares(a_shares + b_shares)
  10.378 +        return shares_ready
  10.379 +
  10.380 +    test_input.skip = "Commitment module is not included in VIFF."
  10.381 +
  10.382 +    @protocol
  10.383 +    def test_basic_multiply(self, runtime):
  10.384 +        """Test multiplication of two numbers."""
  10.385 +
  10.386 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  10.387 +
  10.388 +        x1 = 42
  10.389 +        y1 = 7
  10.390 + 
  10.391 +        def check(v):
  10.392 +            self.assertEquals(v, x1 * y1)
  10.393 + 
  10.394 +        x2 = runtime.shift([2], self.Zp, x1)
  10.395 +        y2 = runtime.shift([3], self.Zp, y1)
  10.396 +
  10.397 +        a, b, c = _get_triple(self, self.Zp)
  10.398 +        z2 = runtime._basic_multiplication(x2, y2, a, b, c)
  10.399 +        d = runtime.open(z2)
  10.400 +        d.addCallback(check)
  10.401 +        return d
  10.402 +
  10.403 +    test_basic_multiply.skip = "Commitment module is not included in VIFF."
  10.404 +
  10.405 +    @protocol
  10.406 +    def test_mul_mul(self, runtime):
  10.407 +        """Test multiplication of two numbers."""
  10.408 +
  10.409 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  10.410 +
  10.411 +        x1 = 42
  10.412 +        y1 = 7
  10.413 + 
  10.414 +        def check(v):
  10.415 +            self.assertEquals(v, x1 * y1)
  10.416 + 
  10.417 +        x2 = runtime.shift([2], self.Zp, x1)
  10.418 +        y2 = runtime.shift([3], self.Zp, y1)
  10.419 +
  10.420 +        z2 = x2 * y2
  10.421 +        d = runtime.open(z2)
  10.422 +        d.addCallback(check)
  10.423 +        return d
  10.424 +
  10.425 +    test_mul_mul.skip = "Commitment module is not included in VIFF."
  10.426 +
  10.427 +    @protocol
  10.428 +    def test_basic_multiply_constant_right(self, runtime):
  10.429 +        """Test multiplication of two numbers."""
  10.430 +
  10.431 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  10.432 +
  10.433 +        x1 = 42
  10.434 +        y1 = 7
  10.435 +
  10.436 +        def check(v):
  10.437 +            self.assertEquals(v, x1 * y1)
  10.438 +
  10.439 +        x2 = runtime.shift([1], self.Zp, x1)
  10.440 +
  10.441 +        a, b, c = _get_triple(self, self.Zp)
  10.442 +        z2 = runtime._basic_multiplication(x2, self.Zp(y1), a, b, c)
  10.443 +        d = runtime.open(z2)
  10.444 +        d.addCallback(check)
  10.445 +        return d
  10.446 +
  10.447 +    test_basic_multiply_constant_right.skip = "Commitment module is not included in VIFF."
  10.448 +
  10.449 +    @protocol
  10.450 +    def test_basic_multiply_constant_left(self, runtime):
  10.451 +        """Test multiplication of two numbers."""
  10.452 +
  10.453 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  10.454 +
  10.455 +        x1 = 42
  10.456 +        y1 = 7
  10.457 +
  10.458 +        def check(v):
  10.459 +            self.assertEquals(v, x1 * y1)
  10.460 +
  10.461 +        x2 = runtime.shift([1], self.Zp, x1)
  10.462 +
  10.463 +        a, b, c = _get_triple(self, self.Zp)
  10.464 +        z2 = runtime._basic_multiplication(self.Zp(y1), x2, a, b, c)
  10.465 +        d = runtime.open(z2)
  10.466 +        d.addCallback(check)
  10.467 +        return d
  10.468 +
  10.469 +    test_basic_multiply_constant_left.skip = "Commitment module is not included in VIFF."
  10.470 +
  10.471 +    @protocol
  10.472 +    def test_constant_multiplication_constant_left(self, runtime):
  10.473 +        """Test multiplication of two numbers."""
  10.474 +
  10.475 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  10.476 +
  10.477 +        x1 = 42
  10.478 +        y1 = 7
  10.479 +
  10.480 +        def check(v):
  10.481 +            self.assertEquals(v, x1 * y1)
  10.482 +
  10.483 +        x2 = runtime.shift([1], self.Zp, x1)
  10.484 +
  10.485 +        z2 = runtime._cmul(self.Zp(y1), x2, self.Zp)
  10.486 +        d = runtime.open(z2)
  10.487 +        d.addCallback(check)
  10.488 +        return d
  10.489 +
  10.490 +    test_constant_multiplication_constant_left.skip = "Commitment module is not included in VIFF."
  10.491 +
  10.492 +    @protocol
  10.493 +    def test_constant_multiplication_constant_right(self, runtime):
  10.494 +        """Test multiplication of two numbers."""
  10.495 +
  10.496 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  10.497 +
  10.498 +        x1 = 42
  10.499 +        y1 = 7
  10.500 +
  10.501 +        def check(v):
  10.502 +            self.assertEquals(v, x1 * y1)
  10.503 +
  10.504 +        x2 = runtime.shift([1], self.Zp, x1)
  10.505 +
  10.506 +        z2 = runtime._cmul(x2, self.Zp(y1), self.Zp)
  10.507 +        d = runtime.open(z2)
  10.508 +        d.addCallback(check)
  10.509 +        return d
  10.510 +
  10.511 +    test_constant_multiplication_constant_right.skip = "Commitment module is not included in VIFF."
  10.512 +
  10.513 +    @protocol
  10.514 +    def test_constant_multiplication_constant_None(self, runtime):
  10.515 +        """Test multiplication of two numbers."""
  10.516 +
  10.517 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  10.518 +
  10.519 +        x1 = 42
  10.520 +        y1 = 7
  10.521 +
  10.522 +        x2 = runtime.shift([1], self.Zp, x1)
  10.523 +        y2 = runtime.shift([1], self.Zp, y1)
  10.524 +
  10.525 +    test_constant_multiplication_constant_None.skip = "Commitment module is not included in VIFF."
  10.526 +
  10.527 +    @protocol
  10.528 +    def test_sum_poly(self, runtime):
  10.529 +        """Test implementation of sum_poly."""
  10.530 +
  10.531 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  10.532 +
  10.533 +        f = []
  10.534 +        f.append((self.Zp(7), (self.Zp(7), self.Zp(7)), self.Zp(7)))
  10.535 +        f.append((self.Zp(9), (self.Zp(9), self.Zp(9)), self.Zp(9)))
  10.536 +        f.append((self.Zp(13), (self.Zp(13), self.Zp(13)), self.Zp(13)))
  10.537 +        
  10.538 +        x, (rho1, rho2), Cx = runtime.sum_poly(1, f)
  10.539 +        self.assertEquals(x, 29)
  10.540 +        self.assertEquals(rho1, 29)
  10.541 +        self.assertEquals(rho2, 29)
  10.542 +        self.assertEquals(Cx, 29)
  10.543 +        return x
  10.544 +
  10.545 +    test_sum_poly.skip = "Commitment module is not included in VIFF."
  10.546 + 
  10.547 +    @protocol
  10.548 +    def test_sum_poly(self, runtime):
  10.549 +        """Test implementation of sum_poly."""
  10.550 +
  10.551 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  10.552 +        
  10.553 +        Cf1 = commitment.commit(21, 21, 21)
  10.554 +        Cf2 = commitment.commit(27, 27, 27)
  10.555 +        Cf3 = commitment.commit(39, 39, 39)
  10.556 +
  10.557 +        f = []
  10.558 +        f.append((self.Zp(7), (self.Zp(7), self.Zp(7)), Cf1))
  10.559 +        f.append((self.Zp(9), (self.Zp(9), self.Zp(9)), Cf2))
  10.560 +        f.append((self.Zp(13), (self.Zp(13), self.Zp(13)), Cf3))
  10.561 +        
  10.562 +        x, (rho1, rho2), Cx = runtime.sum_poly(3, f)
  10.563 +        self.assertEquals(x, 453)
  10.564 +        self.assertEquals(rho1, 453)
  10.565 +        self.assertEquals(rho2, 453)
  10.566 +        self.assertEquals(Cx, Cf1**3 * Cf2**9 * Cf3**27)
  10.567 +        return x
  10.568 +
  10.569 +    test_sum_poly.skip = "Commitment module is not included in VIFF."
  10.570 +
  10.571 +    @protocol
  10.572 +    def test_delta(self, runtime):
  10.573 +        """Test implementation of compute_delta."""
  10.574 +
  10.575 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  10.576 +
  10.577 +        delta = runtime.compute_delta(3)
  10.578 +        self.assertEquals(delta[0], 7)
  10.579 +        self.assertEquals(delta[1], -21)
  10.580 +        self.assertEquals(delta[2], 35)
  10.581 +        self.assertEquals(delta[3], -35)
  10.582 +        self.assertEquals(delta[4], 21)
  10.583 +        self.assertEquals(delta[5], -7)
  10.584 +        self.assertEquals(delta[6], 1)
  10.585 + 
  10.586 +        return delta
  10.587 +
  10.588 +    test_delta.skip = "Commitment module is not included in VIFF."
  10.589 +
  10.590 +    @protocol
  10.591 +    def test_leak_mul(self, runtime):
  10.592 +        """Test leaktolerant multiplication of two numbers."""
  10.593 +        commitment.set_reference_string(long(2), long(6))
  10.594 +
  10.595 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  10.596 +       
  10.597 +        x1 = 42
  10.598 +        y1 = 7
  10.599 +
  10.600 +        runtime.d = 2
  10.601 +
  10.602 +        def check(v):
  10.603 +            self.assertEquals(v, x1 * y1)
  10.604 + 
  10.605 +        x2 = runtime.shift([1], self.Zp, x1)
  10.606 +        y2 = runtime.shift([2], self.Zp, y1)
  10.607 +
  10.608 +        c, sls = runtime.random_triple(self.Zp, 2*runtime.d + 1)
  10.609 +
  10.610 +        def cont(M):
  10.611 +            z2 = runtime.leak_tolerant_mul(x2, y2, M)
  10.612 +            d = runtime.open(z2)
  10.613 +            d.addCallback(check)
  10.614 +            return d
  10.615 +        sls.addCallbacks(cont, runtime.error_handler)
  10.616 +        return sls
  10.617 +
  10.618 +        z2 = runtime._cmul(y2, x2, self.Zp)
  10.619 +        self.assertEquals(z2, None)
  10.620 +        return z2
  10.621 +
  10.622 +    test_leak_mul.skip = "Commitment module is not included in VIFF."
  10.623 +
  10.624 +class TripleGenTest(RuntimeTestCase):
  10.625 +    """Test for generation of triples."""
  10.626 +    
  10.627 +    # Number of players.
  10.628 +    num_players = 3
  10.629 + 
  10.630 +    runtime_class = OrlandiRuntime
  10.631 + 
  10.632 +    timeout = 1600
  10.633 +
  10.634 +    @protocol
  10.635 +    def test_tripleGen(self, runtime):
  10.636 +        """Test the triple_gen command."""
  10.637 +
  10.638 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  10.639 +
  10.640 +        def check((a, b, c)):
  10.641 +            self.assertEquals(c, a * b)
  10.642 +
  10.643 +        def open((a, b, c, _)):
  10.644 +            d1 = runtime.open(a)
  10.645 +            d2 = runtime.open(b)
  10.646 +            d3 = runtime.open(c)
  10.647 +            d = gatherResults([d1, d2, d3])
  10.648 +            d.addCallback(check)
  10.649 +            return d
  10.650 +        d = runtime.triple_gen(self.Zp)
  10.651 +        d.addCallbacks(open, runtime.error_handler)
  10.652 +        return d
  10.653 +
  10.654 +    test_tripleGen.skip = "Commitment module is not included in VIFF."
  10.655 +
  10.656 +    @protocol
  10.657 +    def test_tripleGen2(self, runtime):
  10.658 +        """Test the triple_gen command."""
  10.659 +
  10.660 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  10.661 +
  10.662 +        def check((a, b, c, dx, dy, dz)):
  10.663 +            self.assertEquals(c, a * b)
  10.664 +            self.assertEquals(dz, dx * dy)
  10.665 +
  10.666 +        def open(((a, b, c, control), (x, y, z, _))):
  10.667 +            d1 = runtime.open(a)
  10.668 +            d2 = runtime.open(b)
  10.669 +            d3 = runtime.open(c)
  10.670 +            dx = runtime.open(x)
  10.671 +            dy = runtime.open(y)
  10.672 +            dz = runtime.open(z)
  10.673 +            d = gatherResults([d1, d2, d3, dx, dy, dz])
  10.674 +            d.addCallback(check)
  10.675 +            return d
  10.676 +        t1 = runtime.triple_gen(self.Zp)
  10.677 +        t2 = runtime.triple_gen(self.Zp)
  10.678 +        d = gatherResults([t1, t2])
  10.679 +        d.addCallbacks(open, runtime.error_handler)
  10.680 +        return d
  10.681 +
  10.682 +    test_tripleGen2.skip = "Commitment module is not included in VIFF."
  10.683 +    
  10.684 +    @protocol
  10.685 +    def test_tripleTest(self, runtime):
  10.686 +        """Test the triple_test command."""
  10.687 +
  10.688 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  10.689 +
  10.690 +        def check((a, b, c)):
  10.691 +            self.assertEquals(c, a * b)
  10.692 +
  10.693 +        def open((a, b, c, _)):
  10.694 +            d1 = runtime.open(a)
  10.695 +            d2 = runtime.open(b)
  10.696 +            d3 = runtime.open(c)
  10.697 +            d = gatherResults([d1, d2, d3])
  10.698 +            d.addCallback(check)
  10.699 +            return d
  10.700 +        d = runtime.triple_test(self.Zp)
  10.701 +        d.addCallbacks(open, runtime.error_handler)
  10.702 +        return d
  10.703 +
  10.704 +    test_tripleTest.skip = "Commitment module is not included in VIFF."
  10.705 +
  10.706 +    @protocol
  10.707 +    def test_random_triple(self, runtime):
  10.708 +        """Test the triple_combiner command."""
  10.709 +
  10.710 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  10.711 +
  10.712 +        def check(ls):
  10.713 +            for x in xrange(len(ls) // 3):
  10.714 +                a = ls[x * 3]
  10.715 +                b = ls[x * 3 + 1]
  10.716 +                c = ls[x * 3 + 2]
  10.717 +                self.assertEquals(c, a * b)
  10.718 +
  10.719 +        def open(ls):
  10.720 +            ds = []
  10.721 +            for (a, b, c) in ls:
  10.722 +                d1 = runtime.open(a)
  10.723 +                d2 = runtime.open(b)
  10.724 +                d3 = runtime.open(c)
  10.725 +                ds.append(d1)
  10.726 +                ds.append(d2)
  10.727 +                ds.append(d3)
  10.728 +
  10.729 +            d = gatherResults(ds)
  10.730 +            d.addCallback(check)
  10.731 +            return d
  10.732 +        c, d = runtime.random_triple(self.Zp, 1)
  10.733 +        d.addCallbacks(open, runtime.error_handler)
  10.734 +        return d
  10.735 +
  10.736 +    test_random_triple.skip = "Commitment module is not included in VIFF."
  10.737 +
  10.738 +    @protocol
  10.739 +    def test_random_triple3_parallel(self, runtime):
  10.740 +        """Test the triple_combiner command."""
  10.741 +
  10.742 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  10.743 +
  10.744 +        def check(ls):
  10.745 +            for x in xrange(len(ls) // 3):
  10.746 +                a = ls[x * 3]
  10.747 +                b = ls[x * 3 + 1]
  10.748 +                c = ls[x * 3 + 2]
  10.749 +                self.assertEquals(c, a * b)
  10.750 +
  10.751 +        def open(ls):
  10.752 +            ds = []
  10.753 +            for [(a, b, c)] in ls:
  10.754 +                d1 = runtime.open(a)
  10.755 +                d2 = runtime.open(b)
  10.756 +                d3 = runtime.open(c)
  10.757 +                ds.append(d1)
  10.758 +                ds.append(d2)
  10.759 +                ds.append(d3)
  10.760 +
  10.761 +            d = gatherResults(ds)
  10.762 +            d.addCallback(check)
  10.763 +            return d
  10.764 +        ac, a = runtime.random_triple(self.Zp, 1)
  10.765 +        bc, b = runtime.random_triple(self.Zp, 1)
  10.766 +        cc, c = runtime.random_triple(self.Zp, 1)
  10.767 +        d = gather_shares([a, b, c])
  10.768 +        d.addCallbacks(open, runtime.error_handler)
  10.769 +        return d
  10.770 +
  10.771 +    test_random_triple3_parallel.skip = "Commitment module is not included in VIFF."
  10.772 +
  10.773 +    @protocol
  10.774 +    def test_random_triple_parallel(self, runtime):
  10.775 +        """Test the triple_combiner command."""
  10.776 +
  10.777 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  10.778 +
  10.779 +        def check(ls):
  10.780 +            for x in xrange(len(ls) // 3):
  10.781 +                a = ls[x * 3]
  10.782 +                b = ls[x * 3 + 1]
  10.783 +                c = ls[x * 3 + 2]
  10.784 +                self.assertEquals(c, a * b)
  10.785 +
  10.786 +        def open(ls):
  10.787 +            ds = []
  10.788 +            for [(a, b, c)] in ls:
  10.789 +                d1 = runtime.open(a)
  10.790 +                d2 = runtime.open(b)
  10.791 +                d3 = runtime.open(c)
  10.792 +                ds.append(d1)
  10.793 +                ds.append(d2)
  10.794 +                ds.append(d3)
  10.795 +
  10.796 +            d = gatherResults(ds)
  10.797 +            d.addCallback(check)
  10.798 +            return d
  10.799 +
  10.800 +        a_shares = []
  10.801 +        b_shares = []
  10.802 +        c_shares = []
  10.803 +
  10.804 +        def cont(x):
  10.805 +            while a_shares and b_shares:
  10.806 +                a = a_shares.pop()
  10.807 +                b = b_shares.pop()
  10.808 +                c_shares.append(runtime.mul(a, b))
  10.809 +            done = gather_shares(c_shares)
  10.810 +            return done
  10.811 +
  10.812 +        count = 5
  10.813 +
  10.814 +        for i in range(count):
  10.815 +            inputter = (i % len(runtime.players)) + 1
  10.816 +            if inputter == runtime.id:
  10.817 +                a = rand.randint(0, self.Zp.modulus)
  10.818 +                b = rand.randint(0, self.Zp.modulus)
  10.819 +            else:
  10.820 +                a, b = None, None
  10.821 +            a_shares.append(runtime.input([inputter], self.Zp, a))
  10.822 +            b_shares.append(runtime.input([inputter], self.Zp, b))
  10.823 +        shares_ready = gather_shares(a_shares + b_shares)
  10.824 +
  10.825 +        runtime.schedule_callback(shares_ready, cont)
  10.826 +        return shares_ready
  10.827 +
  10.828 +    test_random_triple_parallel.skip = "Commitment module is not included in VIFF."
    11.1 --- a/viff/test/test_runtime.py	Wed Oct 07 15:23:12 2009 +0200
    11.2 +++ b/viff/test/test_runtime.py	Thu Oct 08 14:27:37 2009 +0200
    11.3 @@ -27,10 +27,11 @@
    11.4  from random import Random
    11.5  import operator
    11.6  
    11.7 -from twisted.internet.defer import gatherResults
    11.8 +from twisted.internet.defer import gatherResults, Deferred, DeferredList
    11.9  
   11.10  from viff.field import GF256
   11.11  from viff.runtime import Share
   11.12 +from viff.constants import SHARE
   11.13  from viff.comparison import Toft05Runtime
   11.14  from viff.test.util import RuntimeTestCase, BinaryOperatorTestCase, protocol
   11.15  
   11.16 @@ -191,6 +192,49 @@
   11.17  
   11.18          return gatherResults([opened_a, opened_b, opened_c])
   11.19  
   11.20 +    @protocol
   11.21 +    def test_send_receive_self(self, runtime):
   11.22 +        """Test send and receive of values."""
   11.23 +        value = 42
   11.24 +        
   11.25 +        pc = tuple(runtime.program_counter)
   11.26 +        runtime.protocols[runtime.id].sendData(pc, SHARE, str(value))
   11.27 +
   11.28 +        d = Deferred()
   11.29 +        runtime._expect_data(runtime.id, SHARE, d)
   11.30 +        def check(x):
   11.31 +            self.assertEquals(int(x), value)
   11.32 +            return x
   11.33 +        d.addCallback(check)
   11.34 +        return d
   11.35 +
   11.36 +    @protocol
   11.37 +    def test_send_receive_self2(self, runtime):
   11.38 +        """Test send and receive of values."""
   11.39 +        value = 42
   11.40 +        
   11.41 +        pc = tuple(runtime.program_counter)
   11.42 +        for peer_id in runtime.players:
   11.43 +            data = str(value)
   11.44 +            runtime.protocols[peer_id].sendData(pc, SHARE, data)
   11.45 +
   11.46 +        ds = []
   11.47 +        for peer_id in runtime.players:
   11.48 +            d = Deferred()
   11.49 +            runtime._expect_data(peer_id, SHARE, d)
   11.50 +            ds.append(d)
   11.51 +
   11.52 +        dls = DeferredList(ds)
   11.53 +        def check(ls):
   11.54 +            for s, x in ls:
   11.55 +                self.assertEquals(int(x), value)
   11.56 +            return ls
   11.57 +
   11.58 +        dls.addCallback(check)
   11.59 +        return dls
   11.60 +
   11.61 +
   11.62 +
   11.63  
   11.64  class ConvertBitShareTest(RuntimeTestCase):
   11.65      runtime_class = Toft05Runtime
    12.1 --- a/viff/test/util.py	Wed Oct 07 15:23:12 2009 +0200
    12.2 +++ b/viff/test/util.py	Thu Oct 08 14:27:37 2009 +0200
    12.3 @@ -22,7 +22,7 @@
    12.4  from twisted.internet import reactor
    12.5  
    12.6  from viff.passive import PassiveRuntime
    12.7 -from viff.runtime import Share, ShareExchanger, ShareExchangerFactory
    12.8 +from viff.runtime import Share, ShareExchanger, ShareExchangerFactory, SelfShareExchanger, SelfShareExchangerFactory, FakeTransport
    12.9  from viff.field import GF
   12.10  from viff.config import generate_configs, load_config
   12.11  from viff.util import rand
   12.12 @@ -220,7 +220,13 @@
   12.13                      # fire.
   12.14                      sentinel = loopbackAsync(server, client)
   12.15                      self.close_sentinels.append(sentinel)
   12.16 -
   12.17 +            else:
   12.18 +                protocol = SelfShareExchanger(id, SelfShareExchangerFactory(runtime))
   12.19 +                protocol.transport = FakeTransport()
   12.20 +                # Keys for when we are the client and when we are the server.
   12.21 +                server_key = (id, id)
   12.22 +                # Store a protocol used when we are the server.
   12.23 +                self.protocols[server_key] = protocol     
   12.24  
   12.25  class BinaryOperatorTestCase:
   12.26      """Test a binary operator.