viff

changeset 1326:f933bd327750

viff: Merged with main tree.
author Marcel Keller <mkeller@cs.au.dk>
date Fri, 23 Oct 2009 13:50:19 +0200
parents 613aa672ba5e 51280703f0c9
children 75fbb52aea09
files apps/aes.py epydoc.conf viff/active.py viff/aes.py viff/field.py viff/passive.py viff/runtime.py viff/shamir.py viff/test/test_active_runtime.py
diffstat 42 files changed, 3441 insertions(+), 628 deletions(-) [+]
line diff
     1.1 --- a/MANIFEST.in	Thu Oct 22 19:38:31 2009 +0200
     1.2 +++ b/MANIFEST.in	Fri Oct 23 13:50:19 2009 +0200
     1.3 @@ -1,5 +1,4 @@
     1.4  graft doc/api
     1.5 -exclude epydoc.conf
     1.6  
     1.7  graft doc/html
     1.8  prune doc/html/.doctrees
     2.1 --- a/apps/aes.py	Thu Oct 22 19:38:31 2009 +0200
     2.2 +++ b/apps/aes.py	Fri Oct 23 13:50:19 2009 +0200
     2.3 @@ -111,7 +111,7 @@
     2.4  
     2.5      for i in range(options.keylength / 8):
     2.6          inputter = i % 3 + 1
     2.7 -        if (inputter == id):
     2.8 +        if inputter == id:
     2.9              key.append(rt.input([inputter], GF256, ord("b")))
    2.10          else:
    2.11              key.append(rt.input([inputter], GF256))
    2.12 @@ -125,36 +125,34 @@
    2.13  
    2.14      if options.active:
    2.15          if options.exponentiation is False:
    2.16 -            max = 301
    2.17 -            js = [3 + i * 15 + j for i in range(20) for j in range(7) + [8]]
    2.18 -        elif options.exponentiation == 0:
    2.19 -            max = 321
    2.20 -            js = [2 + i * 16 + j for i in range(20) for j in range(13)]
    2.21 +            max = 461
    2.22 +            js = [3 + i * 23 + j for i in range(20)
    2.23 +                  for j in range(0, 14, 2) + [15]]
    2.24 +        elif options.exponentiation == 0 or options.exponentiation == 3:
    2.25 +            max = 561
    2.26 +            js = [1 + i * 28 + j * 2 for i in range(20) for j in range(13)]
    2.27          elif options.exponentiation == 1 or options.exponentiation == 2:
    2.28 -            max = 261
    2.29 -            js = [1 + i * 13 + j for i in range(20) for j in range(11)]
    2.30 -        elif options.exponentiation == 3:
    2.31 -            max = 301
    2.32 -            js = [1 + i * 15 + j for i in range(20) for j in range(13)]
    2.33 +            max = 481
    2.34 +            js = [1 + i * 24 + j * 2 for i in range(20) for j in range(11)]
    2.35  
    2.36          if options.exponentiation == 4:
    2.37 -            pcs = [(1, 2 + 130 * options.count + 141 * i + j, 1, 0)
    2.38 +            pcs = [(2, 1 + i, 2 + 2 * j)
    2.39                     for i in range(10 * options.count)
    2.40                     for j in range(140)] + \
    2.41 -                  [(2, 18, k) + (121,) * i + (4 + 6 * j, l, 1, 0)
    2.42 +                  [(3, 17, k) + (121,) * i + (4 + 6 * j, 1 + 2 * l)
    2.43                     for k in range(1, options.count + 1)
    2.44                     for i in range(10)
    2.45                     for j in range(20)
    2.46 -                   for l in range(1, 7)]
    2.47 +                   for l in range(6)]
    2.48          else:
    2.49 -            pcs = [(2, 18, k) + (max,) * i + (j, 1, 0)
    2.50 +            pcs = [(2, 17, k) + (max,) * i + (j,)
    2.51                     for k in range(1, options.count + 1)
    2.52                     for i in range(10)
    2.53                     for j in js]
    2.54          program_desc[("generate_triples", (GF256,))] = pcs
    2.55  
    2.56      if options.exponentiation == 4:
    2.57 -        pcs = [(2, 18, k) + (121,) * i + (1 + j * 6, 0)
    2.58 +        pcs = [(3, 17, k) + (121,) * i + (1 + j * 6,)
    2.59                 for k in range(1, options.count + 1)
    2.60                 for i in range(10)
    2.61                 for j in range(20)]
     3.1 --- a/apps/benchmark.py	Thu Oct 22 19:38:31 2009 +0200
     3.2 +++ b/apps/benchmark.py	Fri Oct 23 13:50:19 2009 +0200
     3.3 @@ -1,6 +1,6 @@
     3.4  #!/usr/bin/env python
     3.5  
     3.6 -# Copyright 2007, 2008 VIFF Development Team.
     3.7 +# Copyright 2007, 2008, 2009 VIFF Development Team.
     3.8  #
     3.9  # This file is part of VIFF, the Virtual Ideal Functionality Framework.
    3.10  #
    3.11 @@ -57,55 +57,59 @@
    3.12  import time
    3.13  from math import log
    3.14  from optparse import OptionParser
    3.15 -import operator
    3.16 -from pprint import pformat
    3.17  
    3.18  import viff.reactor
    3.19  viff.reactor.install()
    3.20  from twisted.internet import reactor
    3.21  
    3.22 -from viff.field import GF, GF256, FakeGF
    3.23 -from viff.runtime import Runtime, create_runtime, gather_shares, \
    3.24 -    make_runtime_class
    3.25 +from viff.field import GF, FakeGF
    3.26 +from viff.runtime import Runtime, create_runtime, make_runtime_class
    3.27  from viff.passive import PassiveRuntime
    3.28  from viff.active import BasicActiveRuntime, \
    3.29      TriplesHyperinvertibleMatricesMixin, TriplesPRSSMixin
    3.30  from viff.comparison import ComparisonToft05Mixin, ComparisonToft07Mixin
    3.31  from viff.equality import ProbabilisticEqualityMixin
    3.32  from viff.paillier import PaillierRuntime
    3.33 +from viff.orlandi import OrlandiRuntime
    3.34  from viff.config import load_config
    3.35 -from viff.util import find_prime, rand
    3.36 +from viff.util import find_prime
    3.37 +
    3.38 +from benchmark_classes import SelfcontainedBenchmarkStrategy, \
    3.39 +    NeededDataBenchmarkStrategy, ParallelBenchmark, SequentialBenchmark, BinaryOperation, NullaryOperation
    3.40 +
    3.41 +# Hack in order to avoid Maximum recursion depth exceeded
    3.42 +# exception;
    3.43 +sys.setrecursionlimit(5000)
    3.44 +
    3.45  
    3.46  last_timestamp = time.time()
    3.47 -start = 0
    3.48  
    3.49 +operations = {"mul"       : ("mul", [], BinaryOperation),
    3.50 +              "compToft05": ("ge", [ComparisonToft05Mixin], BinaryOperation),
    3.51 +              "compToft07": ("ge", [ComparisonToft07Mixin], BinaryOperation),
    3.52 +              "eq"        : ("eq", [ProbabilisticEqualityMixin], BinaryOperation),
    3.53 +              "triple_gen": ("triple_gen", [], NullaryOperation)}
    3.54  
    3.55 -def record_start(what):
    3.56 -    global start
    3.57 -    start = time.time()
    3.58 -    print "*" * 64
    3.59 -    print "Started", what
    3.60 +runtimes = {"PassiveRuntime": PassiveRuntime,
    3.61 +            "PaillierRuntime": PaillierRuntime,
    3.62 +            "BasicActiveRuntime": BasicActiveRuntime,
    3.63 +            "OrlandiRuntime": OrlandiRuntime}
    3.64  
    3.65 -
    3.66 -def record_stop(_, what):
    3.67 -    stop = time.time()
    3.68 -    print
    3.69 -    print "Total time used: %.3f sec" % (stop-start)
    3.70 -    print "Time per %s operation: %.0f ms" % (what, 1000*(stop-start) / count)
    3.71 -    print "*" * 6
    3.72 -
    3.73 -
    3.74 -operations = ["mul", "compToft05", "compToft07", "eq"]
    3.75 +mixins = {"TriplesHyperinvertibleMatricesMixin" : TriplesHyperinvertibleMatricesMixin,
    3.76 +          "TriplesPRSSMixin": TriplesPRSSMixin,
    3.77 +          "ComparisonToft05Mixin": ComparisonToft05Mixin,
    3.78 +          "ComparisonToft07Mixin": ComparisonToft07Mixin,
    3.79 +          "ProbabilisticEqualityMixin": ProbabilisticEqualityMixin}
    3.80  
    3.81  parser = OptionParser(usage="Usage: %prog [options] config_file")
    3.82  parser.add_option("-m", "--modulus",
    3.83                    help="lower limit for modulus (can be an expression)")
    3.84 -parser.add_option("-a", "--active", action="store_true",
    3.85 -                  help="use actively secure runtime")
    3.86 -parser.add_option("--passive", action="store_false", dest="active",
    3.87 -                  help="use passively secure runtime")
    3.88 -parser.add_option("-2", "--twoplayer", action="store_true",
    3.89 -                  help="use twoplayer runtime")
    3.90 +parser.add_option("-r", "--runtime", type="choice", choices=runtimes.keys(),
    3.91 +                  help="the name of the basic runtime to test")
    3.92 +parser.add_option("-n", "--num_players", action="store_true", dest="num_players",
    3.93 +                  help="number of players")
    3.94 +parser.add_option("--mixins", type="string",
    3.95 +                  help="Additional mixins which must be added to the runtime")
    3.96  parser.add_option("--prss", action="store_true",
    3.97                    help="use PRSS for preprocessing")
    3.98  parser.add_option("--hyper", action="store_false", dest="prss",
    3.99 @@ -114,7 +118,7 @@
   3.100                    help="corruption threshold")
   3.101  parser.add_option("-c", "--count", type="int",
   3.102                    help="number of operations")
   3.103 -parser.add_option("-o", "--operation", type="choice", choices=operations,
   3.104 +parser.add_option("-o", "--operation", type="choice", choices=operations.keys(),
   3.105                    help="operation to benchmark")
   3.106  parser.add_option("-p", "--parallel", action="store_true",
   3.107                    help="execute operations in parallel")
   3.108 @@ -122,17 +126,33 @@
   3.109                    help="execute operations in sequence")
   3.110  parser.add_option("-f", "--fake", action="store_true",
   3.111                    help="skip local computations using fake field elements")
   3.112 +parser.add_option("--args", type="string",
   3.113 +                  help=("additional arguments to the runtime, the format is "
   3.114 +                        "a comma separated list of id=value pairs e.g. "
   3.115 +                        "--args s=1,d=0,lambda=1"))
   3.116 +parser.add_option("--needed_data", type="string",
   3.117 +                  help=("name of a file containing already computed "
   3.118 +                        "dictionary of needed_data. Useful for skipping "
   3.119 +                        "generating the needed data, which usually "
   3.120 +                        "elliminates half the execution time. Format of file: "
   3.121 +                        "\"{('random_triple', (Zp,)): [(3, 1), (3, 4)]}\""))
   3.122 +parser.add_option("--pc", type="string",
   3.123 +                  help=("The program counter to start from when using "
   3.124 +                        "explicitly provided needed_data. Format: [3,0]"))
   3.125  
   3.126  parser.set_defaults(modulus=2**65, threshold=1, count=10,
   3.127 -                    active=False, twoplayer=False, prss=True,
   3.128 -                    operation=operations[0], parallel=True, fake=False)
   3.129 +                    runtime="PassiveRuntime", mixins="", num_players=2, prss=True,
   3.130 +                    operation="mul", parallel=True, fake=False,
   3.131 +                    args="", needed_data="")
   3.132 +
   3.133 +print "*" * 60
   3.134  
   3.135  # Add standard VIFF options.
   3.136  Runtime.add_options(parser)
   3.137  
   3.138  (options, args) = parser.parse_args()
   3.139  
   3.140 -if len(args) == 0:
   3.141 +if not args:
   3.142      parser.error("you must specify a config file")
   3.143  
   3.144  id, players = load_config(args[0])
   3.145 @@ -146,189 +166,76 @@
   3.146  else:
   3.147      Field = GF
   3.148  
   3.149 +
   3.150  Zp = Field(find_prime(options.modulus))
   3.151  print "Using field elements (%d bit modulus)" % log(Zp.modulus, 2)
   3.152  
   3.153 +
   3.154  count = options.count
   3.155  print "I am player %d, will %s %d numbers" % (id, options.operation, count)
   3.156  
   3.157 -# Defining the protocol as a class makes it easier to write the
   3.158 -# callbacks in the order they are called. This class is a base class
   3.159 -# that executes the protocol by calling the run_test method.
   3.160 -class Benchmark:
   3.161  
   3.162 -    def __init__(self, rt, operation):
   3.163 -        self.rt = rt
   3.164 -        self.operation = operation
   3.165 -        self.sync_preprocess()
   3.166 +# Identify the base runtime class.
   3.167 +base_runtime_class = runtimes[options.runtime]
   3.168  
   3.169 -    def sync_preprocess(self):
   3.170 -        print "Synchronizing preprocessing"
   3.171 -        sys.stdout.flush()
   3.172 -        sync = self.rt.synchronize()
   3.173 -        self.rt.schedule_callback(sync, self.preprocess)
   3.174 +# Identify the additional mixins.
   3.175 +actual_mixins = []
   3.176 +if options.mixins:
   3.177 +    actual_mixins = [mixins[mixin] for mixin in options.mixins.split(',')]
   3.178  
   3.179 -    def preprocess(self, _):
   3.180 -        program_desc = {}
   3.181  
   3.182 -        if isinstance(self.rt, BasicActiveRuntime):
   3.183 -            # TODO: Make this optional and maybe automatic. The
   3.184 -            # program descriptions below were found by carefully
   3.185 -            # studying the output reported when the benchmarks were
   3.186 -            # run with no preprocessing. So they are quite brittle.
   3.187 -            if self.operation == operator.mul:
   3.188 -                key = ("generate_triples", (Zp,))
   3.189 -                desc = [(i, 1, 0) for i in range(3, 3 + count)]
   3.190 -                program_desc.setdefault(key, []).extend(desc)
   3.191 -            elif isinstance(self.rt, ComparisonToft05Mixin):
   3.192 -                key = ("generate_triples", (GF256,))
   3.193 -                desc = sum([[(c, 64, i, 1, 1, 0) for i in range(2, 33)] +
   3.194 -                            [(c, 64, i, 3, 1, 0) for i in range(17, 33)]
   3.195 -                            for c in range(3 + 2*count, 3 + 3*count)],
   3.196 -                           [])
   3.197 -                program_desc.setdefault(key, []).extend(desc)
   3.198 -            elif isinstance(self.rt, ComparisonToft07Mixin):
   3.199 -                key = ("generate_triples", (Zp,))
   3.200 -                desc = sum([[(c, 2, 4, i, 2, 1, 0) for i in range(1, 33)] +
   3.201 -                            [(c, 2, 4, 99, 2, 1, 0)] +
   3.202 -                            [(c, 2, 4, i, 1, 0) for i in range(65, 98)]
   3.203 -                            for c in range(3 + 2*count, 3 + 3*count)],
   3.204 -                           [])
   3.205 -                program_desc.setdefault(key, []).extend(desc)
   3.206 -
   3.207 -        if program_desc:
   3.208 -            print "Starting preprocessing"
   3.209 -            record_start("preprocessing")
   3.210 -            preproc = self.rt.preprocess(program_desc)
   3.211 -            preproc.addCallback(record_stop, "preprocessing")
   3.212 -            self.rt.schedule_callback(preproc, self.begin)
   3.213 -        else:
   3.214 -            print "Need no preprocessing"
   3.215 -            self.begin(None)
   3.216 -
   3.217 -    def begin(self, _):
   3.218 -        print "Runtime ready, generating shares"
   3.219 -        self.a_shares = []
   3.220 -        self.b_shares = []
   3.221 -        for i in range(count):
   3.222 -            inputter = (i % len(self.rt.players)) + 1
   3.223 -            if inputter == self.rt.id:
   3.224 -                a = rand.randint(0, Zp.modulus)
   3.225 -                b = rand.randint(0, Zp.modulus)
   3.226 -            else:
   3.227 -                a, b = None, None
   3.228 -            self.a_shares.append(self.rt.input([inputter], Zp, a))
   3.229 -            self.b_shares.append(self.rt.input([inputter], Zp, b))
   3.230 -        shares_ready = gather_shares(self.a_shares + self.b_shares)
   3.231 -        self.rt.schedule_callback(shares_ready, self.sync_test)
   3.232 -
   3.233 -    def sync_test(self, _):
   3.234 -        print "Synchronizing test start."
   3.235 -        sys.stdout.flush()
   3.236 -        sync = self.rt.synchronize()
   3.237 -        self.rt.schedule_callback(sync, self.countdown, 3)
   3.238 -
   3.239 -    def countdown(self, _, seconds):
   3.240 -        if seconds > 0:
   3.241 -            print "Starting test in %d" % seconds
   3.242 -            sys.stdout.flush()
   3.243 -            reactor.callLater(1, self.countdown, None, seconds - 1)
   3.244 -        else:
   3.245 -            print "Starting test now"
   3.246 -            sys.stdout.flush()
   3.247 -            self.run_test(None)
   3.248 -
   3.249 -    def run_test(self, _):
   3.250 -        raise NotImplemented("Override this abstract method in a sub class.")
   3.251 -
   3.252 -    def finished(self, _):
   3.253 -        sys.stdout.flush()
   3.254 -
   3.255 -        if self.rt._needed_data:
   3.256 -            print "Missing pre-processed data:"
   3.257 -            for (func, args), pcs in self.rt._needed_data.iteritems():
   3.258 -                print "* %s%s:" % (func, args)
   3.259 -                print "  " + pformat(pcs).replace("\n", "\n  ")
   3.260 -
   3.261 -        self.rt.shutdown()
   3.262 -
   3.263 -# This class implements a benchmark where run_test executes all
   3.264 -# operations in parallel.
   3.265 -class ParallelBenchmark(Benchmark):
   3.266 -
   3.267 -    def run_test(self, _):
   3.268 -        c_shares = []
   3.269 -        record_start("parallel test")
   3.270 -        while self.a_shares and self.b_shares:
   3.271 -            a = self.a_shares.pop()
   3.272 -            b = self.b_shares.pop()
   3.273 -            c_shares.append(self.operation(a, b))
   3.274 -
   3.275 -        done = gather_shares(c_shares)
   3.276 -        done.addCallback(record_stop, "parallel test")
   3.277 -        self.rt.schedule_callback(done, self.finished)
   3.278 -
   3.279 -# A benchmark where the operations are executed one after each other.
   3.280 -class SequentialBenchmark(Benchmark):
   3.281 -
   3.282 -    def run_test(self, _):
   3.283 -        record_start("sequential test")
   3.284 -        self.single_operation(None)
   3.285 -
   3.286 -    def single_operation(self, _):
   3.287 -        if self.a_shares and self.b_shares:
   3.288 -            a = self.a_shares.pop()
   3.289 -            b = self.b_shares.pop()
   3.290 -            c = self.operation(a, b)
   3.291 -            self.rt.schedule_callback(c, self.single_operation)
   3.292 -        else:
   3.293 -            record_stop(None, "sequential test")
   3.294 -            self.finished(None)
   3.295 -
   3.296 -mixins = []
   3.297 -if options.twoplayer:
   3.298 -    # Then there is just one possible runtime:
   3.299 -    operation = operator.mul
   3.300 -    base_runtime_class = PaillierRuntime
   3.301 -else:
   3.302 -    # There are several options for a multiplayer runtime:
   3.303 -    if options.active:
   3.304 -        base_runtime_class = BasicActiveRuntime
   3.305 -        if options.prss:
   3.306 -            mixins.append(TriplesPRSSMixin)
   3.307 -        else:
   3.308 -            mixins.append(TriplesHyperinvertibleMatricesMixin)
   3.309 -    else:
   3.310 -        base_runtime_class = PassiveRuntime
   3.311 -
   3.312 -    if options.operation == "mul":
   3.313 -        operation = operator.mul
   3.314 -    elif options.operation == "compToft05":
   3.315 -        operation = operator.ge
   3.316 -        mixins.append(ComparisonToft05Mixin)
   3.317 -    elif options.operation == "compToft07":
   3.318 -        operation = operator.ge
   3.319 -        mixins.append(ComparisonToft07Mixin)
   3.320 -    elif options.operation == "eq":
   3.321 -        operation = operator.eq
   3.322 -        mixins.append(ProbabilisticEqualityMixin)
   3.323 +# Identify the operation and it mixin dependencies.
   3.324 +operation = operations[options.operation][0]
   3.325 +actual_mixins += operations[options.operation][1]
   3.326 +operation_arity = operations[options.operation][2]
   3.327  
   3.328  print "Using the base runtime: %s." % base_runtime_class
   3.329 -if mixins:
   3.330 +if actual_mixins:
   3.331      print "With the following mixins:"
   3.332 -    for mixin in mixins:
   3.333 -        print "- %s" % mixin
   3.334 +    for mixin in actual_mixins:
   3.335 +        print "- %s" % mixin.__name__
   3.336  
   3.337 -runtime_class = make_runtime_class(base_runtime_class, mixins)
   3.338 +runtime_class = make_runtime_class(base_runtime_class, actual_mixins)
   3.339 +
   3.340 +pre_runtime = create_runtime(id, players, options.threshold,
   3.341 +                             options, runtime_class)
   3.342 +
   3.343 +def update_args(runtime, options):
   3.344 +    args = {}
   3.345 +    if options.args:
   3.346 +        for arg in options.args.split(','):
   3.347 +            id, value = arg.split('=')
   3.348 +            args[id] = long(value)
   3.349 +        runtime.set_args(args)
   3.350 +    return runtime
   3.351 +
   3.352 +
   3.353 +pre_runtime.addCallback(update_args, options)
   3.354  
   3.355  if options.parallel:
   3.356      benchmark = ParallelBenchmark
   3.357  else:
   3.358      benchmark = SequentialBenchmark
   3.359  
   3.360 -pre_runtime = create_runtime(id, players, options.threshold,
   3.361 -                             options, runtime_class)
   3.362 -pre_runtime.addCallback(benchmark, operation)
   3.363 +needed_data = ""
   3.364 +if options.needed_data:
   3.365 +    needed_data = eval(open(options.needed_data).read())
   3.366 +
   3.367 +if options.needed_data and options.pc:
   3.368 +    bases = (benchmark, NeededDataBenchmarkStrategy, operation_arity, object)
   3.369 +    options.pc = eval(options.pc)
   3.370 +else:
   3.371 +    bases = (benchmark, SelfcontainedBenchmarkStrategy, operation_arity, object)
   3.372 +
   3.373 +print "Using the Benchmark bases:"
   3.374 +for b in bases:
   3.375 +    print "- %s" % b.__name__
   3.376 +benchmark = type("ExtendedBenchmark", bases, {})
   3.377 +
   3.378 +def do_benchmark(runtime, operation, benchmark, field, count, *args):
   3.379 +    benchmark(runtime, operation, field, count).benchmark(*args)
   3.380 +
   3.381 +pre_runtime.addCallback(do_benchmark, operation, benchmark, Zp, count, needed_data, options.pc)
   3.382  
   3.383  print "#### Starting reactor ###"
   3.384  reactor.run()
     4.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     4.2 +++ b/apps/benchmark_classes.py	Fri Oct 23 13:50:19 2009 +0200
     4.3 @@ -0,0 +1,247 @@
     4.4 +# Copyright 2009 VIFF Development Team.
     4.5 +#
     4.6 +# This file is part of VIFF, the Virtual Ideal Functionality Framework.
     4.7 +#
     4.8 +# VIFF is free software: you can redistribute it and/or modify it
     4.9 +# under the terms of the GNU Lesser General Public License (LGPL) as
    4.10 +# published by the Free Software Foundation, either version 3 of the
    4.11 +# License, or (at your option) any later version.
    4.12 +#
    4.13 +# VIFF is distributed in the hope that it will be useful, but WITHOUT
    4.14 +# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
    4.15 +# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
    4.16 +# Public License for more details.
    4.17 +#
    4.18 +# You should have received a copy of the GNU Lesser General Public
    4.19 +# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
    4.20 +
    4.21 +import sys
    4.22 +import time
    4.23 +
    4.24 +from pprint import pformat
    4.25 +
    4.26 +from twisted.internet.defer import gatherResults
    4.27 +
    4.28 +from viff.runtime import gather_shares
    4.29 +from viff.util import rand
    4.30 +
    4.31 +start = 0
    4.32 +
    4.33 +
    4.34 +def record_start(what):
    4.35 +    global start
    4.36 +    start = time.time()
    4.37 +    print "*" * 64
    4.38 +    print "Started", what
    4.39 +
    4.40 +
    4.41 +def record_stop(x, what, count):
    4.42 +    stop = time.time()
    4.43 +    print
    4.44 +    print "Total time used: %.3f sec" % (stop-start)
    4.45 +    print "Time per %s operation: %.0f ms" % (what, 1000*(stop-start) / count)
    4.46 +    print "*" * 6
    4.47 +    return x
    4.48 +
    4.49 +
    4.50 +class Benchmark(object):
    4.51 +    """Abstract base class for all Benchmarks.
    4.52 +
    4.53 +    For concrete classes see the `ParallelBenchmark` and
    4.54 +    `SequentialBenchmark` classes. A concrete class must be mixed with
    4.55 +    a `BenchmarkStrategy` and an `Operator`.
    4.56 +    """
    4.57 +
    4.58 +    def __init__(self, rt, operation, field, count):
    4.59 +        self.rt = rt
    4.60 +        self.operation = getattr(rt, operation)
    4.61 +        self.pc = None
    4.62 +        self.field = field
    4.63 +        self.count = count
    4.64 +
    4.65 +    def preprocess(self, needed_data):
    4.66 +        print "Preprocess", needed_data
    4.67 +        if needed_data:
    4.68 +            print "Starting preprocessing"
    4.69 +            record_start("preprocessing")
    4.70 +            preproc = self.rt.preprocess(needed_data)
    4.71 +            preproc.addCallback(record_stop, "preprocessing", self.count)
    4.72 +            return preproc
    4.73 +        else:
    4.74 +            print "Need no preprocessing"
    4.75 +            return None
    4.76 +
    4.77 +    def test(self, d, termination_function):
    4.78 +        self.rt.schedule_callback(d, self.generate_operation_arguments)
    4.79 +        self.rt.schedule_callback(d, self.sync_test)
    4.80 +        self.rt.schedule_callback(d, self.run_test)
    4.81 +        self.rt.schedule_callback(d, self.sync_test)
    4.82 +        self.rt.schedule_callback(d, self.finished, termination_function)
    4.83 +        return d
    4.84 +
    4.85 +    def sync_test(self, x):
    4.86 +        print "Synchronizing test start."
    4.87 +        sys.stdout.flush()
    4.88 +        sync = self.rt.synchronize()
    4.89 +        self.rt.schedule_callback(sync, lambda y: x)
    4.90 +        return sync
    4.91 +
    4.92 +    def run_test(self, _):
    4.93 +        raise NotImplementedError
    4.94 +
    4.95 +    def finished(self, needed_data, termination_function):
    4.96 +        sys.stdout.flush()
    4.97 +
    4.98 +        if self.rt._needed_data:
    4.99 +            print "Missing pre-processed data:"
   4.100 +            for (func, args), pcs in needed_data.iteritems():
   4.101 +                print "* %s%s:" % (func, args)
   4.102 +                print "  " + pformat(pcs).replace("\n", "\n  ")
   4.103 +
   4.104 +        return termination_function(needed_data)
   4.105 +
   4.106 +
   4.107 +class ParallelBenchmark(Benchmark):
   4.108 +    """This class implements a benchmark where run_test executes all
   4.109 +    operations in parallel."""
   4.110 +
   4.111 +    def run_test(self, shares):
   4.112 +        print "rt", self.rt.program_counter, self.pc
   4.113 +        if self.pc != None:
   4.114 +            self.rt.program_counter = self.pc
   4.115 +        else:
   4.116 +            self.pc = list(self.rt.program_counter)
   4.117 +        c_shares = []
   4.118 +        record_start("parallel test")
   4.119 +        while not self.is_operation_done():
   4.120 +            c_shares.append(self.do_operation())
   4.121 +
   4.122 +        done = gatherResults(c_shares)
   4.123 +        done.addCallback(record_stop, "parallel test", self.count)
   4.124 +        def f(x):
   4.125 +            needed_data = self.rt._needed_data
   4.126 +            self.rt._needed_data = {}
   4.127 +            return needed_data
   4.128 +        done.addCallback(f)
   4.129 +        return done
   4.130 +
   4.131 +
   4.132 +class SequentialBenchmark(Benchmark):
   4.133 +    """A benchmark where the operations are executed one after each
   4.134 +    other."""
   4.135 +
   4.136 +    def run_test(self, _, termination_function, d):
   4.137 +        record_start("sequential test")
   4.138 +        self.single_operation(None, termination_function)
   4.139 +
   4.140 +    def single_operation(self, _, termination_function):
   4.141 +        if not self.is_operation_done():
   4.142 +            c = self.do_operation()
   4.143 +            self.rt.schedule_callback(c, self.single_operation, termination_function)
   4.144 +        else:
   4.145 +            record_stop(None, "sequential test", self.count)
   4.146 +            self.finished(None, termination_function)
   4.147 +
   4.148 +
   4.149 +class Operation(object):
   4.150 +    """An abstract mixin which encapsulate the behaviour of an operation.
   4.151 +
   4.152 +    An operation can be nullary, unary, binary, etc.
   4.153 +    """
   4.154 +
   4.155 +    def generate_operation_arguments(self, _):
   4.156 +        """Generate the input need for performing the operation.
   4.157 +
   4.158 +        Returns: None.
   4.159 +        """
   4.160 +        raise NotImplementedError
   4.161 +
   4.162 +    def is_operation_done(self):
   4.163 +        """Returns true if there are no more operations to perform.
   4.164 +        Used in sequential tests.
   4.165 +
   4.166 +        Returns: Boolean.
   4.167 +        """
   4.168 +        raise NotImplementedError
   4.169 +
   4.170 +    def do_operation(self):
   4.171 +        """Perform the operation.
   4.172 +
   4.173 +        Returns: A share containing the result of the operation.
   4.174 +        """
   4.175 +        raise NotImplementedError
   4.176 +
   4.177 +class BinaryOperation(Operation):
   4.178 +    """A binary operation."""
   4.179 +
   4.180 +    def generate_operation_arguments(self, _):
   4.181 +        print "Generate operation arguments", self.rt.program_counter
   4.182 +        print "Runtime ready, generating shares"
   4.183 +        self.a_shares = []
   4.184 +        self.b_shares = []
   4.185 +        for i in range(self.count):
   4.186 +            inputter = (i % len(self.rt.players)) + 1
   4.187 +            if inputter == self.rt.id:
   4.188 +                a = rand.randint(0, self.field.modulus)
   4.189 +                b = rand.randint(0, self.field.modulus)
   4.190 +            else:
   4.191 +                a, b = None, None
   4.192 +            self.a_shares.append(self.rt.input([inputter], self.field, a))
   4.193 +            self.b_shares.append(self.rt.input([inputter], self.field, b))
   4.194 +        shares_ready = gather_shares(self.a_shares + self.b_shares)
   4.195 +        return shares_ready
   4.196 +
   4.197 +    def is_operation_done(self):
   4.198 +        return not (self.a_shares and self.b_shares)
   4.199 +
   4.200 +    def do_operation(self):
   4.201 +        a = self.a_shares.pop()
   4.202 +        b = self.b_shares.pop()
   4.203 +        return self.operation(a, b)
   4.204 +
   4.205 +
   4.206 +class NullaryOperation(Operation):
   4.207 +    """A nullary operation."""
   4.208 +
   4.209 +    def generate_operation_arguments(self, _):
   4.210 +        self.nullary_tests = self.count
   4.211 +        return None
   4.212 +
   4.213 +    def is_operation_done(self):
   4.214 +        return self.nullary_tests == 0
   4.215 +
   4.216 +    def do_operation(self):
   4.217 +        self.nullary_tests -= 1
   4.218 +        return self.operation(self.field)
   4.219 +
   4.220 +
   4.221 +class BenchmarkStrategy(object):
   4.222 +    """A benchmark strategy defines how the benchmark is done."""
   4.223 +
   4.224 +    def benchmark(self, *args):
   4.225 +        raise NotImplementedError
   4.226 +
   4.227 +
   4.228 +class SelfcontainedBenchmarkStrategy(BenchmarkStrategy):
   4.229 +    """In a self contained benchmark strategy, all the needed data is
   4.230 +    generated on the fly."""
   4.231 +
   4.232 +    def benchmark(self, *args):
   4.233 +        sys.stdout.flush()
   4.234 +        sync = self.rt.synchronize()
   4.235 +        self.test(sync, lambda x: x)
   4.236 +        self.rt.schedule_callback(sync, self.preprocess)
   4.237 +        self.test(sync, lambda x: self.rt.shutdown())
   4.238 +
   4.239 +
   4.240 +class NeededDataBenchmarkStrategy(BenchmarkStrategy):
   4.241 +    """In a needed data benchmark strategy, all the needed data has to
   4.242 +    have been generated before the test is run."""
   4.243 +
   4.244 +    def benchmark(self, needed_data, pc, *args):
   4.245 +        self.pc = pc
   4.246 +        sys.stdout.flush()
   4.247 +        sync = self.rt.synchronize()
   4.248 +        self.rt.schedule_callback(sync, lambda x: needed_data)
   4.249 +        self.rt.schedule_callback(sync, self.preprocess)
   4.250 +        self.test(sync, lambda x: self.rt.shutdown())
     5.1 --- a/doc/active.txt	Thu Oct 22 19:38:31 2009 +0200
     5.2 +++ b/doc/active.txt	Fri Oct 23 13:50:19 2009 +0200
     5.3 @@ -1,6 +1,6 @@
     5.4  
     5.5 -Actively Secure Protocols
     5.6 -=========================
     5.7 +A Thresholdbased Actively Secure Runtime
     5.8 +========================================
     5.9  
    5.10  .. automodule:: viff.active
    5.11  
     6.1 --- a/doc/authors.txt	Thu Oct 22 19:38:31 2009 +0200
     6.2 +++ b/doc/authors.txt	Fri Oct 23 13:50:19 2009 +0200
     6.3 @@ -15,6 +15,7 @@
     6.4  * Marcel Keller <mkeller@cs.au.dk>
     6.5  * Tord Reistad
     6.6  * Ivan Damgård
     6.7 +* Janus Dam Nielsen <janus.nielsen@alexandra.dk>
     6.8  
     6.9  If you have been forgotten, then please checkout `the repository`_,
    6.10  add yourself to the list and `send us a patch`_!
     7.1 --- a/doc/conf.py	Thu Oct 22 19:38:31 2009 +0200
     7.2 +++ b/doc/conf.py	Fri Oct 23 13:50:19 2009 +0200
     7.3 @@ -63,7 +63,7 @@
     7.4  today_fmt = '%B %d, %Y'
     7.5  
     7.6  # List of documents that shouldn't be included in the build.
     7.7 -unused_docs = ['api/api-objects'] # Generated by epydoc.
     7.8 +unused_docs = []
     7.9  
    7.10  # If true, '()' will be appended to :func: etc. cross-reference text.
    7.11  #add_function_parentheses = True
     8.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     8.2 +++ b/doc/constants.txt	Fri Oct 23 13:50:19 2009 +0200
     8.3 @@ -0,0 +1,24 @@
     8.4 +Constants Module
     8.5 +================
     8.6 +
     8.7 +.. automodule:: viff.constants
     8.8 +
     8.9 +   .. attribute:: SHARE
    8.10 +                  ECHO
    8.11 +                  READY
    8.12 +                  SEND
    8.13 +                  PAILLIER
    8.14 +                  TEXT
    8.15 +
    8.16 +      Constants used by :class:`ShareExchanger` and others when sending 
    8.17 +      shares and other messages. They serve to distinguish messages sent 
    8.18 +      with the same program counter from one another.
    8.19 +
    8.20 +   .. attribute::INCONSISTENTHASH
    8.21 +                  OK
    8.22 +                  HASH
    8.23 +                  SIGNAL
    8.24 +
    8.25 +      Constants used by :class:`HashBroadcastMixin` when sending shares
    8.26 +      and other messages. They serve to distinguish messages sent with
    8.27 +      the same program counter from one another.
     9.1 --- a/doc/development.txt	Thu Oct 22 19:38:31 2009 +0200
     9.2 +++ b/doc/development.txt	Fri Oct 23 13:50:19 2009 +0200
     9.3 @@ -21,7 +21,7 @@
     9.4  also work offline and take advantage of the many fast operations
     9.5  offered by Mercurial.
     9.6  
     9.7 -.. _Mercurial: http://www.selenic.com/mercurial/
     9.8 +.. _Mercurial: http://mercurial.selenic.com/
     9.9  
    9.10  After installing Mercurial you can checkout a copy of the source using
    9.11  this command line::
    9.12 @@ -67,8 +67,7 @@
    9.13  your own address first to make sure everything looks okay. You can get
    9.14  the full list of options using ``hg help email``.
    9.15  
    9.16 -.. _patchbomb: http://www.selenic.com/mercurial/
    9.17 -                      wiki/index.cgi/PatchbombExtension
    9.18 +.. _patchbomb: http://mercurial.selenic.com/wiki/PatchbombExtension
    9.19  
    9.20  The advantage of using patchbomb is that allows everybody to go over
    9.21  the code and comment on it before the changesets are pulled into the
    9.22 @@ -77,6 +76,24 @@
    9.23  the changes into the repository, just as if the changesets had been
    9.24  pulled using ``hg pull``.
    9.25  
    9.26 +Commit Messages
    9.27 +"""""""""""""""
    9.28 +
    9.29 +Please format your commit messages as follows::
    9.30 +
    9.31 +   topic: terse one-line summary (60 characters max)
    9.32 +
    9.33 +   After the summary line, you're encouraged to provide a bigger
    9.34 +   description of your changes. If your change is small or obvious
    9.35 +   from the diff, you can leave this out.
    9.36 +
    9.37 +   Please wrap your paragraphs at ~70 characters or so. That ensures
    9.38 +   that they are readily readable on a standard terminal.
    9.39 +
    9.40 +The *topic* in the summary line describes which part of the code the
    9.41 +changeset touches. There's no fixed list of topics, but a change to
    9.42 +``viff/X.py`` normally gets the "X" topic.
    9.43 +
    9.44  
    9.45  Revising Changes
    9.46  ----------------
    9.47 @@ -152,7 +169,7 @@
    9.48  fix any remaining conflicts.
    9.49  
    9.50  
    9.51 -.. _Mercurial Queues extension: http://www.selenic.com/mercurial/
    9.52 -                                       wiki/index.cgi/MqExtension
    9.53 +.. _Mercurial Queues extension: http://mercurial.selenic.com/
    9.54 +                                wiki/MqExtension
    9.55  
    9.56  .. LocalWords:  changeset changesets
    10.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    10.2 +++ b/doc/hashbroadcast.txt	Fri Oct 23 13:50:19 2009 +0200
    10.3 @@ -0,0 +1,12 @@
    10.4 +
    10.5 +An Hash Based Broadcast Protocol
    10.6 +================================
    10.7 +
    10.8 +.. automodule:: viff.hash_broadcast
    10.9 +
   10.10 +   .. autoclass:: InconsistentHashException
   10.11 +      :members:
   10.12 +
   10.13 +   .. autoclass:: HashBroadcastMixin
   10.14 +      :members:
   10.15 +
    11.1 --- a/doc/implementation.txt	Thu Oct 22 19:38:31 2009 +0200
    11.2 +++ b/doc/implementation.txt	Fri Oct 23 13:50:19 2009 +0200
    11.3 @@ -13,9 +13,13 @@
    11.4     matrix
    11.5     runtime
    11.6     passive
    11.7 -   active
    11.8 +   active_runtimes
    11.9     paillier
   11.10     comparison
   11.11     prss
   11.12     config
   11.13     aes
   11.14 +   constants
   11.15 +   orlandi
   11.16 +   hashbroadcast
   11.17 +
    12.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    12.2 +++ b/doc/orlandi.txt	Fri Oct 23 13:50:19 2009 +0200
    12.3 @@ -0,0 +1,15 @@
    12.4 +
    12.5 +The Orlandi Runtime - An Actively Secure Protocol with Full Threshold
    12.6 +=======================================================================
    12.7 +
    12.8 +.. automodule:: viff.orlandi
    12.9 +
   12.10 +   .. autoclass:: OrlandiException
   12.11 +      :members:
   12.12 +
   12.13 +   .. autoclass:: OrlandiShare
   12.14 +      :members:
   12.15 +
   12.16 +   .. autoclass:: OrlandiRuntime
   12.17 +      :members:
   12.18 +
    13.1 --- a/doc/program-counters.txt	Thu Oct 22 19:38:31 2009 +0200
    13.2 +++ b/doc/program-counters.txt	Fri Oct 23 13:50:19 2009 +0200
    13.3 @@ -88,63 +88,41 @@
    13.4  point in the execution tree. The execution tree is never explicitly
    13.5  constructed in VIFF, so a simple static numbering is not possible.
    13.6  
    13.7 -Instead we mark methods that need to increment the program counter
    13.8 -with the :func:`viff.runtime.increment_pc` decorator. The program
    13.9 -counter starts at the value ``[0]`` and the decorated method will now
   13.10 -begin by doing::
   13.11 +The program counter starts at the value ``[0]``. It is changed in two
   13.12 +cases:
   13.13  
   13.14 -  self.program_counter[-1] += 1
   13.15 -  self.program_counter.append(0)
   13.16 +* when a callback is scheduled using
   13.17 +  :meth:`viff.runtime.BasicRuntime.schedule_callback`, a new
   13.18 +  sub-program counter is allocated. A sub-program counter is simply a
   13.19 +  program counter with another digit. Because of the asynchronous
   13.20 +  network, the callback will be invoked at an unknown later time. When
   13.21 +  invoked, it sees the sub-program counter. This ensures that that the
   13.22 +  parties agree on any network traffic produced in the callback.
   13.23  
   13.24 -before it executes its body. When the body is finished, the method
   13.25 -does::
   13.26 +  When a piece of code like this::
   13.27  
   13.28 -  self.program_counter.pop()
   13.29 +    def cb(ignored):
   13.30 +        print "callback:", self.program_counter
   13.31 +    d = Deferred()
   13.32  
   13.33 -before it returns. A method :meth:`foo` defined like this::
   13.34 +    print "main:", self.program_counter
   13.35 +    self.schedule_callback(d, cb)
   13.36 +    print "main:", self.program_counter
   13.37  
   13.38 -  @increment_pc
   13.39 -  def foo(self):
   13.40 -      print "foo:", self.program_counter
   13.41 +    d.callback(None)
   13.42  
   13.43 -is thus turned into this::
   13.44 +  is executed, one will see output like this:
   13.45  
   13.46 -  def foo(self):
   13.47 -      self.program_counter[-1] += 1
   13.48 -      self.program_counter.append(0)
   13.49 -      print "foo:", self.program_counter
   13.50 -      self.program_counter.pop()
   13.51 +  .. code-block:: none
   13.52  
   13.53 -and when executed starting from the initial program counter of ``[0]``
   13.54 -we see that it prints ``foo: [1, 0]`` and leaves the program counter
   13.55 -at ``[1]`` after it returns. It is very important that the program
   13.56 -counter is left changed like this, for this means that the next call
   13.57 -to :meth:`foo` will print ``foo: [2, 0]`` and increment the program
   13.58 -counter to ``[2]``.
   13.59 +     main: [0]
   13.60 +     main: [1]
   13.61 +     callback: [0, 0]
   13.62  
   13.63 -If we have a method :meth:`bar` which calls :meth:`foo` several times::
   13.64 +* some functions depend on a unique program counter. These functions
   13.65 +  simply increase the last digit in the current program counter::
   13.66  
   13.67 -  @increment_pc
   13.68 -  def bar(self):
   13.69 -      print "bar:", self.program_counter
   13.70 -      self.foo()
   13.71 -      print "bar:", self.program_counter
   13.72 -      self.foo()
   13.73 -      print "bar:", self.program_counter
   13.74 -
   13.75 -then the result of calling :meth:`bar` will be:
   13.76 -
   13.77 -.. code-block:: none
   13.78 -
   13.79 -   bar: [1, 0]
   13.80 -   foo: [1, 1, 0]
   13.81 -   bar: [1, 1]
   13.82 -   foo: [1, 2, 0]
   13.83 -   bar: [1, 2]
   13.84 -
   13.85 -Notice how each sub-call adds another digit to the counter and how it
   13.86 -increments the counter used at the level of the caller. This system
   13.87 -ensures that all program counters are unique.
   13.88 +    self.program_counter[-1] += 1
   13.89  
   13.90  
   13.91  Alternatives
    14.1 --- a/doc/runtime.txt	Thu Oct 22 19:38:31 2009 +0200
    14.2 +++ b/doc/runtime.txt	Fri Oct 23 13:50:19 2009 +0200
    14.3 @@ -21,18 +21,6 @@
    14.4           or the data itself if data is received from the other player
    14.5           before we are ready to use it.
    14.6  
    14.7 -   .. attribute:: SHARE
    14.8 -                  ECHO
    14.9 -                  READY
   14.10 -                  SEND
   14.11 -                  PAILLIER
   14.12 -
   14.13 -      Constants used by :class:`ShareExchanger` when sending shares
   14.14 -      and other messages. They serve to distinguish messages sent with
   14.15 -      the same program counter from one another.
   14.16 -
   14.17 -   .. autofunction:: increment_pc
   14.18 -
   14.19     .. autofunction:: preprocess
   14.20  
   14.21        See also :ref:`preprocessing` for more background information.
   14.22 @@ -88,9 +76,7 @@
   14.23           different parts of the program execution never reuses the
   14.24           same program counter for different variables.
   14.25  
   14.26 -         The :func:`increment_pc` decorator is responsible for
   14.27 -         dynamically building the tree as the execution unfolds and
   14.28 -         :meth:`schedule_callback` is responsible for scheduling
   14.29 -         callbacks with the correct program counter.
   14.30 +         The :meth:`schedule_callback` method is responsible for
   14.31 +         scheduling callbacks with the correct program counter.
   14.32  
   14.33           See :ref:`program-counters` for more background information.
    15.1 --- a/doc/todo.txt	Thu Oct 22 19:38:31 2009 +0200
    15.2 +++ b/doc/todo.txt	Fri Oct 23 13:50:19 2009 +0200
    15.3 @@ -34,13 +34,6 @@
    15.4    make the other honest players crash too, thereby effectively halting
    15.5    the protocol.
    15.6  
    15.7 -Self Trust
    15.8 -----------
    15.9 -
   15.10 -Implement an (actively) secure protocol with threshold ``t = n-1``
   15.11 -based on the "triples approach" of Claudio Orlandi and Jesper Buus
   15.12 -Nielsen. There will soon be a paper describing the protocol.
   15.13 -
   15.14  Covert Adversaries
   15.15  ------------------
   15.16  
    16.1 --- a/doc/util.txt	Thu Oct 22 19:38:31 2009 +0200
    16.2 +++ b/doc/util.txt	Fri Oct 23 13:50:19 2009 +0200
    16.3 @@ -21,11 +21,6 @@
    16.4        :envvar:`VIFF_SEED` is defined, but empty, then no seed is used
    16.5        and a protocol run cannot be reproduced exactly.
    16.6  
    16.7 -   .. envvar:: VIFF_NO_WRAP
    16.8 -
    16.9 -      Setting this environment variable to any value will turn
   16.10 -      :func:`wrapper` into a no-op.
   16.11 -
   16.12     .. envvar:: VIFF_PROFILE
   16.13  
   16.14        Defining this variable will change :func:`profile` from a no-op
    17.1 --- a/epydoc.conf	Thu Oct 22 19:38:31 2009 +0200
    17.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
    17.3 @@ -1,15 +0,0 @@
    17.4 -[epydoc]
    17.5 -
    17.6 -name: VIFF: Virtual Ideal Functionality Framework
    17.7 -url: http://viff.dk/
    17.8 -
    17.9 -modules: viff
   17.10 -exclude: test, libs
   17.11 -
   17.12 -output: html
   17.13 -target: doc/api
   17.14 -
   17.15 -graph: classtree
   17.16 -include-log: yes
   17.17 -
   17.18 -external-api: mod, func, data, const, class, exc, meth, attr, exc, file, envvar
    18.1 --- a/run.py	Thu Oct 22 19:38:31 2009 +0200
    18.2 +++ b/run.py	Fri Oct 23 13:50:19 2009 +0200
    18.3 @@ -105,11 +105,6 @@
    18.4          shutil.rmtree('doc/html')
    18.5      sphinx('doc/html')
    18.6  
    18.7 -    # Generate API docs in doc/api.
    18.8 -    if isdir('doc/api'):
    18.9 -        shutil.rmtree('doc/api')
   18.10 -    epydoc('doc/api')
   18.11 -
   18.12      # Pack everything up with Distutils.
   18.13      execute(["python", "setup.py", "sdist", "--force-manifest",
   18.14               "--formats=bztar,gztar,zip"])
   18.15 @@ -117,13 +112,6 @@
   18.16      # Generate binary Windows installer (which has no docs, though).
   18.17      execute(["python", "setup.py", "bdist", "--formats=wininst"])
   18.18  
   18.19 -@command('epydoc', 'target')
   18.20 -def epydoc(target):
   18.21 -    """Generate API documentation using epydoc."""
   18.22 -    ensure_dir(target)
   18.23 -    execute(["epydoc", "-vv", "--config", "epydoc.conf"],
   18.24 -            {'VIFF_NO_WRAP': 'YES', 'target': target})
   18.25 -
   18.26  @command('sphinx', 'target')
   18.27  def sphinx(target):
   18.28      """Generate VIFF manual using Sphinx."""
    19.1 --- a/viff/active.py	Thu Oct 22 19:38:31 2009 +0200
    19.2 +++ b/viff/active.py	Fri Oct 23 13:50:19 2009 +0200
    19.3 @@ -15,9 +15,7 @@
    19.4  # You should have received a copy of the GNU Lesser General Public
    19.5  # License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
    19.6  
    19.7 -"""Actively secure protocols."""
    19.8 -
    19.9 -__docformat__ = "restructuredtext"
   19.10 +"""A thresholdbased actively secure runtime."""
   19.11  
   19.12  from math import ceil
   19.13  
   19.14 @@ -27,8 +25,8 @@
   19.15  from viff.util import rand
   19.16  from viff.matrix import Matrix, hyper
   19.17  from viff.passive import PassiveRuntime
   19.18 -from viff.runtime import Share, increment_pc, preprocess, gather_shares
   19.19 -from viff.runtime import ECHO, READY, SEND
   19.20 +from viff.runtime import Share, preprocess, gather_shares
   19.21 +from viff.constants import ECHO, READY, SEND
   19.22  
   19.23  
   19.24  class BrachaBroadcastMixin:
   19.25 @@ -37,7 +35,6 @@
   19.26      broadcast.
   19.27      """
   19.28  
   19.29 -    @increment_pc
   19.30      def _broadcast(self, sender, message=None):
   19.31          """Perform a Bracha broadcast.
   19.32  
   19.33 @@ -47,6 +44,8 @@
   19.34          protocol" by G. Bracha in Proc. 3rd ACM Symposium on
   19.35          Principles of Distributed Computing, 1984, pages 154-162.
   19.36          """
   19.37 +        # We need a unique program counter for each call.
   19.38 +        self.increment_pc()
   19.39  
   19.40          result = Deferred()
   19.41          pc = tuple(self.program_counter)
   19.42 @@ -141,7 +140,6 @@
   19.43  
   19.44          return result
   19.45  
   19.46 -    @increment_pc
   19.47      def broadcast(self, senders, message=None):
   19.48          """Perform one or more Bracha broadcast(s).
   19.49  
   19.50 @@ -186,7 +184,6 @@
   19.51      #: to :const:`None` here and update it as necessary.
   19.52      _hyper = None
   19.53  
   19.54 -    @increment_pc
   19.55      def single_share_random(self, T, degree, field):
   19.56          """Share a random secret.
   19.57  
   19.58 @@ -205,16 +202,8 @@
   19.59          si = rand.randint(0, field.modulus - 1)
   19.60  
   19.61          # Every player shares the random value with two thresholds.
   19.62 -        shares = self.shamir_share(inputters, field, si, degree)
   19.63 -
   19.64 -        # Turn the shares into a column vector.
   19.65 -        svec = Matrix([shares]).transpose()
   19.66 -
   19.67 -        # Apply the hyper-invertible matrix to svec1 and svec2.
   19.68 -        rvec = (self._hyper * svec)
   19.69 -
   19.70 -        # Get back to normal lists of shares.
   19.71 -        svec = svec.transpose().rows[0]
   19.72 +        svec = self.shamir_share(inputters, field, si, degree)
   19.73 +        rvec = self._hyper * Matrix([svec]).transpose()
   19.74          rvec = rvec.transpose().rows[0]
   19.75  
   19.76          def verify(shares):
   19.77 @@ -259,7 +248,7 @@
   19.78                      else:
   19.79                          si.append(self._expect_share(peer_id, field))
   19.80                  result = gatherResults(si)
   19.81 -                self.schedule_callback(result, verify)
   19.82 +                result.addCallback(verify)
   19.83                  return result
   19.84              else:
   19.85                  # We cannot verify anything, so we just return the
   19.86 @@ -273,7 +262,6 @@
   19.87          self.schedule_callback(result, exchange)
   19.88          return result
   19.89  
   19.90 -    @increment_pc
   19.91      def double_share_random(self, T, d1, d2, field):
   19.92          """Double-share a random secret using two polynomials.
   19.93  
   19.94 @@ -290,20 +278,14 @@
   19.95          si = rand.randint(0, field.modulus - 1)
   19.96  
   19.97          # Every player shares the random value with two thresholds.
   19.98 -        d1_shares = self.shamir_share(inputters, field, si, d1)
   19.99 -        d2_shares = self.shamir_share(inputters, field, si, d2)
  19.100 -
  19.101 -        # Turn the shares into a column vector.
  19.102 -        svec1 = Matrix([d1_shares]).transpose()
  19.103 -        svec2 = Matrix([d2_shares]).transpose()
  19.104 +        svec1 = self.shamir_share(inputters, field, si, d1)
  19.105 +        svec2 = self.shamir_share(inputters, field, si, d2)
  19.106  
  19.107          # Apply the hyper-invertible matrix to svec1 and svec2.
  19.108 -        rvec1 = (self._hyper * svec1)
  19.109 -        rvec2 = (self._hyper * svec2)
  19.110 +        rvec1 = self._hyper * Matrix([svec1]).transpose()
  19.111 +        rvec2 = self._hyper * Matrix([svec2]).transpose()
  19.112  
  19.113          # Get back to normal lists of shares.
  19.114 -        svec1 = svec1.transpose().rows[0]
  19.115 -        svec2 = svec2.transpose().rows[0]
  19.116          rvec1 = rvec1.transpose().rows[0]
  19.117          rvec2 = rvec2.transpose().rows[0]
  19.118  
  19.119 @@ -362,7 +344,7 @@
  19.120                          si_1.append(self._expect_share(peer_id, field))
  19.121                          si_2.append(self._expect_share(peer_id, field))
  19.122                  result = gatherResults([gatherResults(si_1), gatherResults(si_2)])
  19.123 -                self.schedule_callback(result, verify)
  19.124 +                result.addCallback(verify)
  19.125                  return result
  19.126              else:
  19.127                  # We cannot verify anything, so we just return the
  19.128 @@ -376,15 +358,13 @@
  19.129          self.schedule_callback(result, exchange)
  19.130          return result
  19.131  
  19.132 -    @increment_pc
  19.133      @preprocess("generate_triples")
  19.134      def get_triple(self, field):
  19.135          # This is a waste, but this function is only called if there
  19.136          # are no pre-processed triples left.
  19.137 -        return self.generate_triples(field, gather=False)[0]
  19.138 +        return self.generate_triples(field, quantity=1, gather=False)[0]
  19.139  
  19.140 -    @increment_pc
  19.141 -    def generate_triples(self, field, gather=True):
  19.142 +    def generate_triples(self, field, quantity=None, gather=True):
  19.143          """Generate multiplication triples.
  19.144  
  19.145          These are random numbers *a*, *b*, and *c* such that ``c =
  19.146 @@ -434,13 +414,11 @@
  19.147  class TriplesPRSSMixin:
  19.148      """Mixin class for generating multiplication triples using PRSS."""
  19.149  
  19.150 -    @increment_pc
  19.151      @preprocess("generate_triples")
  19.152      def get_triple(self, field):
  19.153          result = self.generate_triples(field, quantity=1, gather=False)
  19.154          return result[0]
  19.155  
  19.156 -    @increment_pc
  19.157      def generate_triples(self, field, quantity=20, gather=True):
  19.158          """Generate *quantity* multiplication triples using PRSS.
  19.159  
  19.160 @@ -450,6 +428,8 @@
  19.161          Returns a tuple with the number of triples generated and a
  19.162          Deferred which will yield a singleton-list with a 3-tuple.
  19.163          """
  19.164 +        quantity = min(quantity, 20)
  19.165 +
  19.166          a_t = self.prss_share_random_multi(field, quantity)
  19.167          b_t = self.prss_share_random_multi(field, quantity)
  19.168          r_t, r_2t = self.prss_double_share(field, quantity)
  19.169 @@ -481,7 +461,9 @@
  19.170      :class:`ActiveRuntime` instead.
  19.171      """
  19.172  
  19.173 -    @increment_pc
  19.174 +    def get_triple(self, field):
  19.175 +        raise NotImplementedError
  19.176 +
  19.177      def mul(self, share_x, share_y):
  19.178          """Multiplication of shares.
  19.179  
  19.180 @@ -523,7 +505,7 @@
  19.181          return result
  19.182  
  19.183  
  19.184 -class ActiveRuntime(BasicActiveRuntime, TriplesPRSSMixin):
  19.185 +class ActiveRuntime(TriplesPRSSMixin, BasicActiveRuntime):
  19.186      """Default mix of :class:`BasicActiveRuntime` and
  19.187      :class:`TriplesPRSSMixin`."""
  19.188      pass
    20.1 --- a/viff/aes.py	Thu Oct 22 19:38:31 2009 +0200
    20.2 +++ b/viff/aes.py	Fri Oct 23 13:50:19 2009 +0200
    20.3 @@ -17,14 +17,11 @@
    20.4  
    20.5  """MPC implementation of AES (Rijndael)."""
    20.6  
    20.7 -__docformat__ = "restructuredtext"
    20.8 -
    20.9 -
   20.10  import time
   20.11  import operator
   20.12  
   20.13  from viff.field import GF256
   20.14 -from viff.runtime import Share, gather_shares, increment_pc
   20.15 +from viff.runtime import Share, gather_shares
   20.16  from viff.matrix import Matrix
   20.17  
   20.18  
   20.19 @@ -36,15 +33,14 @@
   20.20  
   20.21      r_bits = share.runtime.prss_share_random_multi(GF256, 8, binary=True)
   20.22  
   20.23 -    if (use_lin_comb):
   20.24 +    if use_lin_comb:
   20.25          r = share.runtime.lin_comb([2 ** i for i in range(8)], r_bits)
   20.26      else:
   20.27 -        r = reduce(lambda x,y: x + y, 
   20.28 -                   [r_bits[i] * 2 ** i for i in range(8)])
   20.29 +        r = sum([r_bits[i] * 2 ** i for i in range(8)])
   20.30  
   20.31      c = share.runtime.open(share + r)
   20.32      c_bits = [Share(share.runtime, GF256) for i in range(8)]
   20.33 -    
   20.34 +
   20.35      def decompose(byte, bits):
   20.36          value = byte.value
   20.37  
   20.38 @@ -73,7 +69,7 @@
   20.39      In every case *ciphertext* will be a list of shares over GF256.
   20.40      """
   20.41  
   20.42 -    def __init__(self, runtime, key_size, block_size=128, 
   20.43 +    def __init__(self, runtime, key_size, block_size=128,
   20.44                   use_exponentiation=False, quiet=False):
   20.45          """Initialize Rijndael.
   20.46  
   20.47 @@ -89,34 +85,33 @@
   20.48          self.n_b = block_size / 32
   20.49          self.rounds = max(self.n_k, self.n_b) + 6
   20.50          self.runtime = runtime
   20.51 -        self.program_counter = runtime.program_counter
   20.52  
   20.53 -        if (use_exponentiation is not False):
   20.54 +        if use_exponentiation is not False:
   20.55              if (isinstance(use_exponentiation, int) and
   20.56                  use_exponentiation < len(AES.exponentiation_variants)):
   20.57                  use_exponentiation = \
   20.58                      AES.exponentiation_variants[use_exponentiation]
   20.59 -            elif (use_exponentiation not in AES.exponentation_variants):
   20.60 +            elif use_exponentiation not in AES.exponentation_variants:
   20.61                  use_exponentiation = "shortest_sequential_chain"
   20.62  
   20.63 -            if (not quiet):
   20.64 +            if not quiet:
   20.65                  print "Use %s for inversion by exponentiation." % \
   20.66                      use_exponentiation
   20.67  
   20.68 -            if (use_exponentiation == "standard_square_and_multiply"):
   20.69 +            if use_exponentiation == "standard_square_and_multiply":
   20.70                  self.invert = lambda byte: byte ** 254
   20.71 -            elif (use_exponentiation == "shortest_chain_with_least_rounds"):
   20.72 +            elif use_exponentiation == "shortest_chain_with_least_rounds":
   20.73                  self.invert = self.invert_by_exponentiation_with_less_rounds
   20.74 -            elif (use_exponentiation == "chain_with_least_rounds"):
   20.75 +            elif use_exponentiation == "chain_with_least_rounds":
   20.76                  self.invert = self.invert_by_exponentiation_with_least_rounds
   20.77 -            elif (use_exponentiation == "masked"):
   20.78 +            elif use_exponentiation == "masked":
   20.79                  self.invert = self.invert_by_masked_exponentiation
   20.80              else:
   20.81                  self.invert = self.invert_by_exponentiation
   20.82          else:
   20.83              self.invert = self.invert_by_masking
   20.84  
   20.85 -            if (not quiet):
   20.86 +            if not quiet:
   20.87                  print "Use inversion by masking."
   20.88  
   20.89      exponentiation_variants = ["standard_square_and_multiply",
   20.90 @@ -132,7 +127,7 @@
   20.91              bits[j].addCallback(lambda x: 1 - x)
   20.92  #            bits[j] = 1 - bits[j]
   20.93  
   20.94 -        while(len(bits) > 1):
   20.95 +        while len(bits) > 1:
   20.96              bits.append(bits.pop(0) * bits.pop(0))
   20.97  
   20.98          # b == 1 if byte is 0, b == 0 else
   20.99 @@ -142,7 +137,7 @@
  20.100          c = Share(self.runtime, GF256)
  20.101  
  20.102          def get_masked_byte(c_opened, r_related, c, r, byte):
  20.103 -            if (c_opened == 0):
  20.104 +            if c_opened == 0:
  20.105                  r_trial = self.runtime.prss_share_random(GF256)
  20.106                  c_trial = self.runtime.open((byte + b) * r_trial)
  20.107                  self.runtime.schedule_callback(c_trial, get_masked_byte,
  20.108 @@ -241,11 +236,11 @@
  20.109  
  20.110          for h in range(len(state)):
  20.111              row = state[h]
  20.112 -            
  20.113 +
  20.114              for i in range(len(row)):
  20.115                  bits = bit_decompose(self.invert(row[i]))
  20.116  
  20.117 -                if (use_lin_comb):
  20.118 +                if use_lin_comb:
  20.119                      row[i] = self.runtime.lin_comb(sum(AES.A.rows, []),
  20.120                                                     bits * len(AES.A.rows))
  20.121                  else:
  20.122 @@ -287,7 +282,7 @@
  20.123  
  20.124          assert len(state) == 4, "Wrong state size."
  20.125  
  20.126 -        if (use_lin_comb):
  20.127 +        if use_lin_comb:
  20.128              columns = zip(*state)
  20.129  
  20.130              for i, row in enumerate(state):
  20.131 @@ -325,11 +320,11 @@
  20.132          for i in xrange(len(key), self.n_b * (new_length + 1)):
  20.133              temp = list(expanded_key[i - 1])
  20.134  
  20.135 -            if (i % self.n_k == 0):
  20.136 +            if i % self.n_k == 0:
  20.137                  temp.append(temp.pop(0))
  20.138                  self.byte_sub([temp])
  20.139                  temp[0] += GF256(2) ** (i / self.n_k - 1)
  20.140 -            elif (self.n_k > 6 and i % self.n_k == 4):
  20.141 +            elif self.n_k > 6 and i % self.n_k == 4:
  20.142                  self.byte_sub([temp])
  20.143  
  20.144              new_word = []
  20.145 @@ -342,8 +337,8 @@
  20.146          return expanded_key
  20.147  
  20.148      def preprocess(self, input):
  20.149 -        if (isinstance(input, str)):
  20.150 -            return [Share(self.runtime, GF256, GF256(ord(c))) 
  20.151 +        if isinstance(input, str):
  20.152 +            return [Share(self.runtime, GF256, GF256(ord(c)))
  20.153                      for c in input]
  20.154          else:
  20.155              for byte in input:
  20.156 @@ -352,14 +347,15 @@
  20.157                      "or of shares thereof."
  20.158              return input
  20.159  
  20.160 -    @increment_pc
  20.161      def encrypt(self, cleartext, key, benchmark=False, prepare_at_once=False):
  20.162          """Rijndael encryption.
  20.163  
  20.164 -        Cleartext and key should be either a string or a list of bytes 
  20.165 +        Cleartext and key should be either a string or a list of bytes
  20.166          (possibly shared as elements of GF256)."""
  20.167  
  20.168          start = time.time()
  20.169 +        self.runtime.increment_pc()
  20.170 +        self.runtime.fork_pc()
  20.171  
  20.172          assert len(cleartext) == 4 * self.n_b, "Wrong length of cleartext."
  20.173          assert len(key) == 4 * self.n_k, "Wrong length of key."
  20.174 @@ -370,7 +366,7 @@
  20.175          state = [cleartext[i::4] for i in xrange(4)]
  20.176          key = [key[4*i:4*i+4] for i in xrange(self.n_k)]
  20.177  
  20.178 -        if (benchmark):
  20.179 +        if benchmark:
  20.180              global preparation, communication
  20.181              preparation = 0
  20.182              communication = 0
  20.183 @@ -411,11 +407,11 @@
  20.184              self.mix_column(state)
  20.185              self.add_round_key(state, expanded_key[i*self.n_b:(i+1)*self.n_b])
  20.186  
  20.187 -            if (not prepare_at_once):
  20.188 +            if not prepare_at_once:
  20.189                  trigger = get_trigger(state)
  20.190                  trigger.addCallback(progress, i, time.time())
  20.191  
  20.192 -                if (i < self.rounds - 1):
  20.193 +                if i < self.rounds - 1:
  20.194                      self.runtime.schedule_complex_callback(trigger, round, state, i + 1)
  20.195                  else:
  20.196                      self.runtime.schedule_complex_callback(trigger, final_round, state)
  20.197 @@ -436,7 +432,7 @@
  20.198              trigger = get_trigger(state)
  20.199              trigger.addCallback(progress, self.rounds, time.time())
  20.200  
  20.201 -            if (benchmark):
  20.202 +            if benchmark:
  20.203                  trigger.addCallback(finish, state)
  20.204  
  20.205              # connect to final result
  20.206 @@ -455,7 +451,7 @@
  20.207  
  20.208          result = [Share(self.runtime, GF256) for i in xrange(4 * self.n_b)]
  20.209  
  20.210 -        if (prepare_at_once):
  20.211 +        if prepare_at_once:
  20.212              for i in range(1, self.rounds):
  20.213                  round(None, state, i)
  20.214  
  20.215 @@ -463,4 +459,5 @@
  20.216          else:
  20.217              round(None, state, 1)
  20.218  
  20.219 +        self.runtime.unfork_pc()
  20.220          return result
    21.1 --- a/viff/comparison.py	Thu Oct 22 19:38:31 2009 +0200
    21.2 +++ b/viff/comparison.py	Fri Oct 23 13:50:19 2009 +0200
    21.3 @@ -20,12 +20,10 @@
    21.4  <viff.runtime.Runtime>` they are mixed with.
    21.5  """
    21.6  
    21.7 -__docformat__ = "restructuredtext"
    21.8 -
    21.9  import math
   21.10  
   21.11  from viff.util import rand, profile
   21.12 -from viff.runtime import Share, gather_shares, increment_pc
   21.13 +from viff.runtime import Share, gather_shares
   21.14  from viff.passive import PassiveRuntime
   21.15  from viff.active import ActiveRuntime
   21.16  from viff.field import GF256, FieldElement
   21.17 @@ -34,7 +32,6 @@
   21.18  class ComparisonToft05Mixin:
   21.19      """Comparison by Tomas Toft, 2005."""
   21.20  
   21.21 -    @increment_pc
   21.22      def convert_bit_share(self, share, dst_field):
   21.23          """Convert a 0/1 share into dst_field."""
   21.24          bit = rand.randint(0, 1)
   21.25 @@ -67,7 +64,6 @@
   21.26          return int_b, bit_bits
   21.27  
   21.28      @profile
   21.29 -    @increment_pc
   21.30      def greater_than_equal(self, share_a, share_b):
   21.31          """Compute ``share_a >= share_b``.
   21.32  
   21.33 @@ -100,7 +96,6 @@
   21.34          self.schedule_callback(result, self._finish_greater_than_equal, l)
   21.35          return result
   21.36  
   21.37 -    @increment_pc
   21.38      def _finish_greater_than_equal(self, results, l):
   21.39          """Finish the calculation."""
   21.40          T = results[0]
   21.41 @@ -128,7 +123,6 @@
   21.42  
   21.43          return GF256(T.bit(l)) ^ (bit_bits[l] ^ vec[0][1])
   21.44  
   21.45 -    @increment_pc
   21.46      def _diamond(self, (top_a, bot_a), (top_b, bot_b)):
   21.47          """The "diamond-operator".
   21.48  
   21.49 @@ -160,7 +154,6 @@
   21.50      elements and gives a secret result shared over Zp.
   21.51      """
   21.52  
   21.53 -    @increment_pc
   21.54      def convert_bit_share(self, share, dst_field):
   21.55          """Convert a 0/1 share into *dst_field*."""
   21.56          l = self.options.security_parameter + math.log(dst_field.modulus, 2)
   21.57 @@ -188,7 +181,6 @@
   21.58          return tmp - full_mask
   21.59  
   21.60      @profile
   21.61 -    @increment_pc
   21.62      def greater_than_equal_preproc(self, field, smallField=None):
   21.63          """Preprocessing for :meth:`greater_than_equal`."""
   21.64          if smallField is None:
   21.65 @@ -243,7 +235,6 @@
   21.66          ##################################################
   21.67  
   21.68      @profile
   21.69 -    @increment_pc
   21.70      def greater_than_equal_online(self, share_a, share_b, preproc, field):
   21.71          """Compute ``share_a >= share_b``. Result is secret shared."""
   21.72          # increment l as a, b are increased
   21.73 @@ -272,7 +263,6 @@
   21.74                                 r_modl, r_bits, z)
   21.75          return c
   21.76  
   21.77 -    @increment_pc
   21.78      def _finish_greater_than_equal(self, c, field, smallField, s_bit, s_sign,
   21.79                                 mask, r_modl, r_bits, z):
   21.80          """Finish the calculation."""
   21.81 @@ -316,7 +306,6 @@
   21.82          return (z - result) * ~field(2**l)
   21.83      # END _finish_greater_than
   21.84  
   21.85 -    @increment_pc
   21.86      def greater_than_equal(self, share_a, share_b):
   21.87          """Compute ``share_a >= share_b``.
   21.88  
    22.1 --- a/viff/config.py	Thu Oct 22 19:38:31 2009 +0200
    22.2 +++ b/viff/config.py	Fri Oct 23 13:50:19 2009 +0200
    22.3 @@ -29,8 +29,6 @@
    22.4  :func:`load_config` function.
    22.5  """
    22.6  
    22.7 -__docformat__ = "restructuredtext"
    22.8 -
    22.9  from viff.libs.configobj import ConfigObj
   22.10  from viff.prss import generate_subsets, PRF
   22.11  from viff.util import rand
    23.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    23.2 +++ b/viff/constants.py	Fri Oct 23 13:50:19 2009 +0200
    23.3 @@ -0,0 +1,32 @@
    23.4 +# -*- coding: utf-8 -*-
    23.5 +#
    23.6 +# Copyright 2009 VIFF Development Team.
    23.7 +#
    23.8 +# This file is part of VIFF, the Virtual Ideal Functionality Framework.
    23.9 +#
   23.10 +# VIFF is free software: you can redistribute it and/or modify it
   23.11 +# under the terms of the GNU Lesser General Public License (LGPL) as
   23.12 +# published by the Free Software Foundation, either version 3 of the
   23.13 +# License, or (at your option) any later version.
   23.14 +#
   23.15 +# VIFF is distributed in the hope that it will be useful, but WITHOUT
   23.16 +# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
   23.17 +# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
   23.18 +# Public License for more details.
   23.19 +#
   23.20 +# You should have received a copy of the GNU Lesser General Public
   23.21 +# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
   23.22 +
   23.23 +# Constants used for communication.
   23.24 +SHARE    = 0
   23.25 +ECHO     = 1
   23.26 +READY    = 2
   23.27 +SEND     = 3
   23.28 +PAILLIER = 4
   23.29 +TEXT     = 5
   23.30 +
   23.31 +# Used by the HashBroadcastMixin
   23.32 +INCONSISTENTHASH = 6
   23.33 +OK               = 7
   23.34 +HASH             = 8
   23.35 +SIGNAL           = 9
    24.1 --- a/viff/equality.py	Thu Oct 22 19:38:31 2009 +0200
    24.2 +++ b/viff/equality.py	Fri Oct 23 13:50:19 2009 +0200
    24.3 @@ -20,13 +20,10 @@
    24.4  is mixed with.
    24.5  """
    24.6  
    24.7 -from viff.runtime import increment_pc
    24.8 -
    24.9  class ProbabilisticEqualityMixin:
   24.10      """This class implements probabilistic constant-round secure
   24.11      equality-testing of secret shared numbers."""
   24.12  
   24.13 -    @increment_pc
   24.14      def equal(self, share_x, share_y):
   24.15          """Equality testing with secret shared result.
   24.16  
    25.1 --- a/viff/field.py	Thu Oct 22 19:38:31 2009 +0200
    25.2 +++ b/viff/field.py	Fri Oct 23 13:50:19 2009 +0200
    25.3 @@ -75,9 +75,6 @@
    25.4  ``z`` are instances of two *different* classes called ``GFElement``.
    25.5  """
    25.6  
    25.7 -__docformat__ = "restructuredtext"
    25.8 -
    25.9 -
   25.10  from gmpy import mpz
   25.11  from math import log, ceil
   25.12  
    26.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    26.2 +++ b/viff/hash_broadcast.py	Fri Oct 23 13:50:19 2009 +0200
    26.3 @@ -0,0 +1,173 @@
    26.4 +#!/usr/bin/env python
    26.5 +
    26.6 +# Copyright 2009 VIFF Development Team.
    26.7 +#
    26.8 +# This file is part of VIFF, the Virtual Ideal Functionality Framework.
    26.9 +#
   26.10 +# VIFF is free software: you can redistribute it and/or modify it
   26.11 +# under the terms of the GNU Lesser General Public License (LGPL) as
   26.12 +# published by the Free Software Foundation, either version 3 of the
   26.13 +# License, or (at your option) any later version.
   26.14 +#
   26.15 +# VIFF is distributed in the hope that it will be useful, but WITHOUT
   26.16 +# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
   26.17 +# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
   26.18 +# Public License for more details.
   26.19 +#
   26.20 +# You should have received a copy of the GNU Lesser General Public
   26.21 +# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
   26.22 +
   26.23 +from twisted.internet.defer import Deferred
   26.24 +
   26.25 +try:
   26.26 +    from hashlib import sha1
   26.27 +except ImportError:
   26.28 +    from sha import sha as sha1
   26.29 +from viff.constants import TEXT, INCONSISTENTHASH, OK, HASH, SIGNAL
   26.30 +
   26.31 +error_msg = "Player %i, has received an inconsistent hash %s."
   26.32 +
   26.33 +class InconsistentHashException(Exception):
   26.34 +    pass
   26.35 +
   26.36 +class HashBroadcastMixin:
   26.37 +    """A non-consistent broadcast scheme mainly useful for full threshold security.
   26.38 +
   26.39 +    A value is send using `send_value` and when received a hash is generated and
   26.40 +    exchanged among the receivers. If a receiver receives a hash which is not equal
   26.41 +    to the one he generated, then he sends an error signal to the others and 
   26.42 +    they stop the computation. Else he sends an ok signal and the computation continues."""
   26.43 +
   26.44 +    def _send_message(self, pc, sender, receivers, message):
   26.45 +        for peer_id in receivers:
   26.46 +            self.protocols[peer_id].sendData(pc, TEXT, message)
   26.47 +
   26.48 +    def _receive_broadcast(self, pc, unique_pc, sender, receivers):
   26.49 +        # The result.
   26.50 +        result = Deferred()
   26.51 +        # The message store.
   26.52 +        message = []
   26.53 +        # The hash store
   26.54 +        g_hashes = {}
   26.55 +        # The signal store
   26.56 +        signals = {}
   26.57 +
   26.58 +        def signal_received(signal, peer_id, message, num_receivers, hashes, signals):
   26.59 +            # Store the signal.
   26.60 +            signals[peer_id] = long(signal)
   26.61 +            # If all signals are received then check if they are OK or INCONSISTENTHASH.
   26.62 +            if num_receivers == len(signals.keys()):
   26.63 +                s = reduce(lambda x, y: (OK == y and OK) or INCONSISTENTHASH, signals.values())
   26.64 +                if OK == s:
   26.65 +                    # Make the result ready.
   26.66 +                    result.callback(message[0])
   26.67 +                else:
   26.68 +                    raise InconsistentHashException(error_msg % (self.id, hashes))
   26.69 +
   26.70 +        def hash_received(h, unique_pc, peer_id, receivers, a_hashes):
   26.71 +            # Store the hash.
   26.72 +            a_hashes[peer_id] = h
   26.73 +            # If we have received a hash from everybody, then compute the signal and send it.
   26.74 +            if len(receivers) == len(a_hashes.keys()):
   26.75 +                signal = OK
   26.76 +                # First we check if the hashes we received are equal to the hash we computed ourselves.
   26.77 +                for peer_id in receivers:
   26.78 +                    if a_hashes[peer_id] == a_hashes[self.id]:
   26.79 +                        signal = signal
   26.80 +                    else:
   26.81 +                        signal = INCONSISTENTHASH
   26.82 +                # Then we send the SAME signal to everybody. 
   26.83 +                for peer_id in receivers:
   26.84 +                    self.protocols[peer_id].sendData(unique_pc, SIGNAL, str(signal))           
   26.85 +            # The return value does not matter.
   26.86 +            return None
   26.87 +
   26.88 +        def message_received(m, unique_pc, message, receivers, hashes):
   26.89 +            # Store the message.
   26.90 +            message.append(m)
   26.91 +            # Compute hash of message.
   26.92 +            h = sha1(m).hexdigest()
   26.93 +            # Store hash.
   26.94 +            hashes[self.id] = h
   26.95 +            # Send the hash to all receivers.
   26.96 +            for peer_id in receivers:
   26.97 +                self.protocols[peer_id].sendData(unique_pc, HASH, str(h))
   26.98 +
   26.99 +        # Set up receivers for hashes and signals.
  26.100 +        # Note, we use the unique_pc to avoid data to cross method invocation boundaries.
  26.101 +        for peer_id in receivers:
  26.102 +            d_hash = Deferred().addCallbacks(hash_received,
  26.103 +                                             self.error_handler, 
  26.104 +                                             callbackArgs=(unique_pc, peer_id, receivers, g_hashes))
  26.105 +            self._expect_data_with_pc(unique_pc, peer_id, HASH, d_hash)
  26.106 +            d_signal = Deferred().addCallbacks(signal_received, 
  26.107 +                                               self.error_handler, 
  26.108 +                                               callbackArgs=(peer_id, message, len(receivers), 
  26.109 +                                                             g_hashes, signals))
  26.110 +            self._expect_data_with_pc(unique_pc, peer_id, SIGNAL, d_signal)
  26.111 +
  26.112 +        # Set up receiving of the message.
  26.113 +        d_message = Deferred().addCallbacks(message_received, 
  26.114 +                                            self.error_handler, 
  26.115 +                                            callbackArgs=(unique_pc, message, receivers, g_hashes))
  26.116 +        self._expect_data(sender, TEXT, d_message)
  26.117 +        return result
  26.118 +
  26.119 +
  26.120 +    def broadcast(self, senders, receivers, message=None):
  26.121 +        """Broadcast the messeage from senders to receivers.
  26.122 +
  26.123 +        Returns a list of deferreds if the calling player is among 
  26.124 +        the receivers and there are multiple senders.
  26.125 +        Returns a single element if there is only on sender, or the 
  26.126 +        calling player is among the senders only.
  26.127 +
  26.128 +        The order of the resulting list is guaranteed to be the same order 
  26.129 +        as the list of senders.
  26.130 +
  26.131 +        Senders and receivers should be lists containing the id of the senders 
  26.132 +        and receivers, respectively.
  26.133 +
  26.134 +        Note: You send implicitly to your self."""
  26.135 +        assert message is None or self.id in senders
  26.136 +
  26.137 +        self.program_counter[-1] += 1
  26.138 +
  26.139 +        pc = tuple(self.program_counter)
  26.140 +        if self.id in receivers or self.id in senders:
  26.141 +            results = [None] * len(senders)
  26.142 +        else:
  26.143 +            results = []
  26.144 +
  26.145 +        if self.id in senders:
  26.146 +            self._send_message(pc, self.id, receivers, message)
  26.147 +
  26.148 +        if self.id in receivers:
  26.149 +            for x in xrange(len(senders)):
  26.150 +                sender = senders[x]
  26.151 +                new_pc = list(self.program_counter)
  26.152 +                new_pc.append(x)
  26.153 +                results[x] = self._receive_broadcast(pc, tuple(new_pc), sender, receivers)
  26.154 +
  26.155 +        if self.id in senders and self.id not in receivers:
  26.156 +            d = Deferred()
  26.157 +            d.callback(message)
  26.158 +            results = [d]
  26.159 +
  26.160 +        self.program_counter[-1] += 1
  26.161 +
  26.162 +        if len(results) == 1:
  26.163 +            return results[0]
  26.164 +
  26.165 +        return results
  26.166 +          
  26.167 +    def list_str(self, s):
  26.168 +        ls = []
  26.169 +        for x in s[1:-1].split(','):
  26.170 +            x = x.strip()
  26.171 +            ls.append(str(x)[1:-1])
  26.172 +        return ls
  26.173 +
  26.174 +    def error_handler(self, ex):
  26.175 +        print "Error: ", ex
  26.176 +        return ex
    27.1 --- a/viff/matrix.py	Thu Oct 22 19:38:31 2009 +0200
    27.2 +++ b/viff/matrix.py	Fri Oct 23 13:50:19 2009 +0200
    27.3 @@ -24,8 +24,6 @@
    27.4  
    27.5  from __future__ import division
    27.6  
    27.7 -__docformat__ = "restructuredtext"
    27.8 -
    27.9  class Matrix(object):
   27.10      """A matrix."""
   27.11  
    28.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    28.2 +++ b/viff/montgomery_exponentiation.py	Fri Oct 23 13:50:19 2009 +0200
    28.3 @@ -0,0 +1,166 @@
    28.4 +# Copyright 2009 VIFF Development Team.
    28.5 +#
    28.6 +# This file is part of VIFF, the Virtual Ideal Functionality Framework.
    28.7 +#
    28.8 +# VIFF is free software: you can redistribute it and/or modify it
    28.9 +# under the terms of the GNU Lesser General Public License (LGPL) as
   28.10 +# published by the Free Software Foundation, either version 3 of the
   28.11 +# License, or (at your option) any later version.
   28.12 +#
   28.13 +# VIFF is distributed in the hope that it will be useful, but WITHOUT
   28.14 +# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
   28.15 +# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
   28.16 +# Public License for more details.
   28.17 +#
   28.18 +# You should have received a copy of the GNU Lesser General Public
   28.19 +# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
   28.20 +
   28.21 +
   28.22 +def sizeinbits(a):
   28.23 +    acc = 0
   28.24 +    while a != 0:
   28.25 +        acc += 1
   28.26 +        a = a >> 1
   28.27 +    return acc
   28.28 +
   28.29 +
   28.30 +def calc_r(n):
   28.31 +    """Compute r."""
   28.32 +    n_size = sizeinbits(n)
   28.33 +    r = 2**(n_size+1)
   28.34 +
   28.35 +    while gcd(r, n) != 1:
   28.36 +        r = r << 1
   28.37 +		
   28.38 +    return r
   28.39 +
   28.40 +
   28.41 +def calc_r_r_inv(n):
   28.42 +    """Compute r and r inverse."""
   28.43 +    assert (n % 2) == 1, "n must be odd."
   28.44 +    n_size = sizeinbits(n)
   28.45 +    r = 2**(n_size+1)
   28.46 +
   28.47 +    while gcd(r, n) != 1:
   28.48 +        r = r << 1
   28.49 +		
   28.50 +    return r, inversemod(r, n)
   28.51 +
   28.52 +
   28.53 +def calc_np(n, r):
   28.54 +    """Compute n'."""
   28.55 +    assert (n % 2) == 1, "n must be odd."
   28.56 +    n_prime = inversemod(n, r)
   28.57 +    return r - n_prime 
   28.58 +
   28.59 +
   28.60 +def inversemod(a, n):
   28.61 +    g, x, y = xgcd(a, n)
   28.62 +    if g != 1:
   28.63 +        raise ZeroDivisionError, (a,n)
   28.64 +    assert g == 1, "a must be coprime to n."
   28.65 +    return x%n
   28.66 +
   28.67 +
   28.68 +def gcd(a, b):                                       
   28.69 +    if a < 0:  a = -a
   28.70 +    if b < 0:  b = -b
   28.71 +    if a == 0: return b
   28.72 +    if b == 0: return a
   28.73 +    while b != 0: 
   28.74 +        (a, b) = (b, a%b)
   28.75 +    return a
   28.76 +
   28.77 +
   28.78 +def xgcd(a, b):
   28.79 +    if a == 0 and b == 0: return (0, 0, 1)
   28.80 +    if a == 0: return (abs(b), 0, b/abs(b))
   28.81 +    if b == 0: return (abs(a), a/abs(a), 0)
   28.82 +    x_sign = 1; y_sign = 1
   28.83 +    if a < 0: a = -a; x_sign = -1
   28.84 +    if b < 0: b = -b; y_sign = -1
   28.85 +    x = 1; y = 0; r = 0; s = 1
   28.86 +    while b != 0:
   28.87 +        (c, q) = (a%b, a/b)
   28.88 +        (a, b, r, s, x, y) = (b, c, x-q*r, y-q*s, r, s)
   28.89 +    return (a, x*x_sign, y*y_sign)
   28.90 +
   28.91 +
   28.92 +def montgomery_exponentiation_reduction(a, r , n ):
   28.93 +    return (a * r) % n
   28.94 +
   28.95 +
   28.96 +def montgomery_product(a, b, n_prime, size_of_r, r, n):
   28.97 +    t = a * b 
   28.98 +    m = (t * n_prime) & r -1
   28.99 +    u = (t + m * n ) >> size_of_r - 1
  28.100 +    if u >= n:
  28.101 +        return u -n 
  28.102 +    return u
  28.103 +
  28.104 +
  28.105 +def montgomery_exponentiation(a, x, n, n_prime, r):
  28.106 +    ah = (a * r) % n 
  28.107 +    xh = r % n 
  28.108 +    x_s = sizeinbits(x) - 1
  28.109 +    px = 2**x_s
  28.110 +    size_of_r = sizeinbits(r)
  28.111 +    while px != 0:
  28.112 +        t = xh * xh 
  28.113 +        m = (t * n_prime) & r -1
  28.114 +        u = (t + m * n ) >> size_of_r - 1
  28.115 +        if u >= n:
  28.116 +            xh = u - n 
  28.117 +        else:
  28.118 +            xh = u
  28.119 +        if (px & x) > 0:
  28.120 +            t = ah * xh 
  28.121 +            m = (t * n_prime) & r - 1
  28.122 +            u = (t + m * n ) >> size_of_r - 1
  28.123 +            if u >= n:
  28.124 +                xh =  u -n 
  28.125 +            else:
  28.126 +                xh = u
  28.127 +	px = px >> 1
  28.128 +
  28.129 +    m = (xh * n_prime) & r - 1
  28.130 +    u = (xh + m * n ) >> size_of_r - 1
  28.131 +    if u >= n:
  28.132 +        return u - n 
  28.133 +    return u
  28.134 +
  28.135 +def montgomery_exponentiation2(a, x, n, n_prime,  r):
  28.136 +    ah = (a * r) % n 
  28.137 +    xh = r % n 
  28.138 +    x_s = sizeinbits(x) - 1
  28.139 +    px = 2**x_s
  28.140 +    size_of_r = sizeinbits(r)
  28.141 +    while px != 0:
  28.142 +        xh = montgomery_product(xh, xh, n_prime, size_of_r, r, n)
  28.143 +        if (px & x) > 0:
  28.144 +            xh = montgomery_product(ah, xh, n_prime, size_of_r, r, n)
  28.145 +	px = px >> 1
  28.146 +
  28.147 +    x  = montgomery_product(xh, 1, n_prime, size_of_r, r, n)
  28.148 +    return x
  28.149 +
  28.150 +
  28.151 +
  28.152 +
  28.153 +# n = 2328734783
  28.154 +# r, r_inv = calc_r(n)
  28.155 +# n_prime = calc_np(n, r) 
  28.156 +
  28.157 +if __name__ ==  '__main__':
  28.158 +    n = 2328734783
  28.159 +    r, r_inv = calc_r_r_inv(n)
  28.160 +    n_prime = calc_np(n, r) 
  28.161 +    a = 2987
  28.162 +    x = 1093874
  28.163 +    print montgomery_exponentiation(a, x, n, n_prime, r)
  28.164 +    print pow(a, x, n)
  28.165 +    print a**x % n
  28.166 +
  28.167 +
  28.168 +
  28.169 +
    29.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    29.2 +++ b/viff/orlandi.py	Fri Oct 23 13:50:19 2009 +0200
    29.3 @@ -0,0 +1,1366 @@
    29.4 +# Copyright 2009 VIFF Development Team.
    29.5 +#
    29.6 +# This file is part of VIFF, the Virtual Ideal Functionality Framework.
    29.7 +#
    29.8 +# VIFF is free software: you can redistribute it and/or modify it
    29.9 +# under the terms of the GNU Lesser General Public License (LGPL) as
   29.10 +# published by the Free Software Foundation, either version 3 of the
   29.11 +# License, or (at your option) any later version.
   29.12 +#
   29.13 +# VIFF is distributed in the hope that it will be useful, but WITHOUT
   29.14 +# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
   29.15 +# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
   29.16 +# Public License for more details.
   29.17 +#
   29.18 +# You should have received a copy of the GNU Lesser General Public
   29.19 +# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
   29.20 +
   29.21 +from twisted.internet.defer import Deferred, gatherResults
   29.22 +
   29.23 +from viff.runtime import Runtime, Share, ShareList, gather_shares, preprocess
   29.24 +from viff.util import rand
   29.25 +from viff.constants import TEXT, PAILLIER
   29.26 +from viff.field import FieldElement
   29.27 +from viff.paillier import encrypt_r, decrypt
   29.28 +
   29.29 +from hash_broadcast import HashBroadcastMixin
   29.30 +
   29.31 +try:
   29.32 +    import commitment
   29.33 +    commitment.set_reference_string(23434347834783478783478L,
   29.34 +                                    489237823478234783478020L)
   29.35 +except ImportError:
   29.36 +    # The commitment module is not public, so we cannot expect the
   29.37 +    # import to work. Catching the ImportError here allows the
   29.38 +    # benchmark and tests to import viff.orlandi without blowing up.
   29.39 +    # It is only if the OrlandiRuntime is used that things blow up.
   29.40 +    pass
   29.41 +
   29.42 +# import logging
   29.43 +# LOG_FILENAME = 'logging_example.out'
   29.44 +# logging.basicConfig(filename=LOG_FILENAME,level=logging.DEBUG,)
   29.45 +
   29.46 +class OrlandiException(Exception):
   29.47 +    pass
   29.48 +
   29.49 +class OrlandiShare(Share):
   29.50 +    """A share in the Orlandi runtime.
   29.51 +
   29.52 +    A share in the Orlandi runtime is a 3-tuple ``(x_i, rho_i, Cr_i)`` of:
   29.53 +
   29.54 +    - A share of a number, ``x_i``
   29.55 +    - A tuple of two random numbers, ``rho_i = (rho_i1, rho_i2)``
   29.56 +    - A commitment to the number and the random numbers, ``Cr_i``
   29.57 +
   29.58 +    The :class:`Runtime` operates on shares, represented by this class.
   29.59 +    Shares are asynchronous in the sense that they promise to attain a
   29.60 +    value at some point in the future.
   29.61 +
   29.62 +    Shares overload the arithmetic operations so that ``x = a + b``
   29.63 +    will create a new share *x*, which will eventually contain the
   29.64 +    sum of *a* and *b*. Each share is associated with a
   29.65 +    :class:`Runtime` and the arithmetic operations simply call back to
   29.66 +    that runtime.
   29.67 +    """
   29.68 +
   29.69 +    def __init__(self, runtime, field, value=None, rho=None, commitment=None):
   29.70 +        self.share = value
   29.71 +        self.rho = rho
   29.72 +        self.commitment = commitment
   29.73 +        Share.__init__(self, runtime, field, (value, rho, commitment))
   29.74 +
   29.75 +
   29.76 +class OrlandiRuntime(Runtime, HashBroadcastMixin):
   29.77 +    """The Orlandi runtime.
   29.78 +
   29.79 +    The runtime is used for sharing values (:meth:`secret_share` or
   29.80 +    :meth:`shift`) into :class:`OrlandiShare` object and opening such
   29.81 +    shares (:meth:`open`) again. Calculations on shares is normally
   29.82 +    done through overloaded arithmetic operations, but it is also
   29.83 +    possible to call :meth:`add`, :meth:`mul`, etc. directly if one
   29.84 +    prefers.
   29.85 +
   29.86 +    Each player in the protocol uses a :class:`Runtime` object. To
   29.87 +    create an instance and connect it correctly with the other
   29.88 +    players, please use the :func:`create_runtime` function instead of
   29.89 +    instantiating a Runtime directly. The :func:`create_runtime`
   29.90 +    function will take care of setting up network connections and
   29.91 +    return a :class:`Deferred` which triggers with the
   29.92 +    :class:`Runtime` object when it is ready.
   29.93 +    """
   29.94 +
   29.95 +    def __init__(self, player, threshold=None, options=None):
   29.96 +        """Initialize runtime."""
   29.97 +        Runtime.__init__(self, player, threshold, options)
   29.98 +        self.threshold = self.num_players - 1
   29.99 +        self.s = 1
  29.100 +        self.d = 0
  29.101 +        self.s_lambda = 1
  29.102 +
  29.103 +    def compute_delta(self, d):
  29.104 +        def product(j):
  29.105 +            pt = 1
  29.106 +            pn = 1
  29.107 +            for k in xrange(1, 2 * d + 2):
  29.108 +                if k != j:
  29.109 +                    pt *= k
  29.110 +                    pn *= k - j
  29.111 +            return pt // pn
  29.112 +
  29.113 +        delta = []
  29.114 +        for j in xrange(1, 2 * d + 2):
  29.115 +            delta.append(product(j))
  29.116 +        return delta
  29.117 +
  29.118 +    def output(self, share, receivers=None, threshold=None):
  29.119 +        return self.open(share, receivers, threshold)
  29.120 +
  29.121 +    def _send_orlandi_share(self, other_id, pc, xi, rhoi, Cx):
  29.122 +        """Send the share *xi*, *rhoi*, and the commitment *Cx* to
  29.123 +        party *other_id*."""
  29.124 +        self.protocols[other_id].sendShare(pc, xi)
  29.125 +        self.protocols[other_id].sendShare(pc, rhoi[0])
  29.126 +        self.protocols[other_id].sendShare(pc, rhoi[1])
  29.127 +        self.protocols[other_id].sendData(pc, TEXT, repr(Cx))
  29.128 +
  29.129 +    def _expect_orlandi_share(self, peer_id, field):
  29.130 +        """Waits for a number ``x``, ``rho``, and the commitment for
  29.131 +        ``x``."""
  29.132 +        xi = self._expect_share(peer_id, field)
  29.133 +        Cx = Deferred()
  29.134 +        rhoi1 = self._expect_share(peer_id, field)
  29.135 +        rhoi2 = self._expect_share(peer_id, field)
  29.136 +        self._expect_data(peer_id, TEXT, Cx)
  29.137 +        sls = ShareList([xi, rhoi1, rhoi2, Cx])
  29.138 +        def combine(ls):
  29.139 +            expected_num = 4;
  29.140 +            if len(ls) is not expected_num:
  29.141 +                raise OrlandiException("Cannot share number, trying to create a share,"
  29.142 +                                       " expected %s components got %s."
  29.143 +                                       % (expected_num, len(ls)))
  29.144 +            s1, xi = ls[0]
  29.145 +            s2, rhoi1 = ls[1]
  29.146 +            s3, rhoi2 = ls[2]
  29.147 +            s4, Cx = ls[3]
  29.148 +            Cxx = commitment.deserialize(Cx)
  29.149 +            if not (s1 and s2 and s3 and s4):
  29.150 +                raise OrlandiException("Cannot share number, trying to create share,"
  29.151 +                                       " but a component did arrive properly.")
  29.152 +            return OrlandiShare(self, field, xi, (rhoi1, rhoi2), Cxx)
  29.153 +        sls.addCallbacks(combine, self.error_handler)
  29.154 +        return sls
  29.155 +
  29.156 +    def _expect_orlandi_share_xi_rhoi(self, peer_id, field):
  29.157 +        xi = self._expect_share(peer_id, field)
  29.158 +        rhoi1 = self._expect_share(peer_id, field)
  29.159 +        rhoi2 = self._expect_share(peer_id, field)
  29.160 +        sls = ShareList([xi, rhoi1, rhoi2])
  29.161 +        def combine(ls):
  29.162 +            expected_num = 3;
  29.163 +            if len(ls) is not expected_num:
  29.164 +                raise OrlandiException("Cannot share number, trying to create a share,"
  29.165 +                                       " expected %s components got %s."
  29.166 +                                       % (expected_num, len(ls)))
  29.167 +
  29.168 +            s1, xi = ls[0]
  29.169 +            s2, rhoi1 = ls[1]
  29.170 +            s3, rhoi2 = ls[2]
  29.171 +            if not (s1 and s2 and s3):
  29.172 +                raise OrlandiException("Cannot share number, trying to create share "
  29.173 +                                       "but a component did arrive properly.")
  29.174 +            return OrlandiShare(self, field, xi, (rhoi1, rhoi2))
  29.175 +        sls.addCallbacks(combine, self.error_handler)
  29.176 +        return sls
  29.177 +
  29.178 +    def secret_share(self, inputters, field, number=None, threshold=None):
  29.179 +        """Share the value *number* among all the parties using
  29.180 +        additive sharing.
  29.181 +
  29.182 +        To share an element ``x in Z_p``, choose random ``x_1, ...,
  29.183 +        x_n-1 in Z_p``, define ``x_n = x - SUM_i=1^n-1 x_i mod p``.
  29.184 +
  29.185 +        Choose random values ``rho_x1, ..., rho_xn in (Z_p)^2``,
  29.186 +        define ``rho_x = SUM_i=1^n rho_x,i`` and ``C_x = Com_ck(x,
  29.187 +        p_x)``.
  29.188 +
  29.189 +        Send ``[x]_i = (x_i, rho_xi, C_x)`` to party ``P_i``.
  29.190 +        """
  29.191 +        assert number is None or self.id in inputters
  29.192 +        self.threshold = self.num_players - 1
  29.193 +
  29.194 +        self.program_counter[-1] += 1
  29.195 +
  29.196 +        def additive_shares_with_rho(x):
  29.197 +            """Returns a tuple of a list of tuples (player id, share,
  29.198 +            rho) and rho.
  29.199 +
  29.200 +            Chooses random elements ``x_1, ..., x_n-1`` in field and
  29.201 +            ``x_n`` st. ``x_n = x - Sum_i=1^n-1 x_i``.
  29.202 +
  29.203 +            Chooses random pair of elements ``rho_1, ..., rho_n in
  29.204 +            Z_p^2`` and define ``rho_n = Sum_i=1^n rho_i``.
  29.205 +
  29.206 +            Returns a pair of ``((player id, x_i, rho_i), rho)``.
  29.207 +            """
  29.208 +            shares = []
  29.209 +            rhos = []
  29.210 +            sum = 0
  29.211 +            rho1 = 0
  29.212 +            rho2 = 0
  29.213 +            for i in xrange(1, self.num_players):
  29.214 +                xi = field(rand.randint(0, field.modulus - 1))
  29.215 +                rhoi1 = field(rand.randint(0, field.modulus - 1))
  29.216 +                rhoi2 = field(rand.randint(0, field.modulus - 1))
  29.217 +                sum += xi
  29.218 +                rho1 += rhoi1
  29.219 +                rho2 += rhoi2
  29.220 +                shares.append((i, xi, (rhoi1, rhoi2)))
  29.221 +            xn = field(x) - sum
  29.222 +            rhon1 = field(rand.randint(0, field.modulus - 1))
  29.223 +            rhon2 = field(rand.randint(0, field.modulus - 1))
  29.224 +            shares.append((self.num_players, xn, (rhon1, rhon2)))
  29.225 +            rho1 += rhon1
  29.226 +            rho2 += rhon2
  29.227 +            return shares, (rho1, rho2)
  29.228 +
  29.229 +        # Send ``[x]_i = (x_i, rho_x,i, C_x)`` to party ``P_i``.
  29.230 +        results = []
  29.231 +        for peer_id in inputters:
  29.232 +            if peer_id == self.id:
  29.233 +                pc = tuple(self.program_counter)
  29.234 +                shares, rho = additive_shares_with_rho(number)
  29.235 +                Cx = commitment.commit(number, rho[0].value, rho[1].value)
  29.236 +                # Distribute the shares
  29.237 +                the_others = []
  29.238 +                for other_id, xi, rhoi in shares:
  29.239 +                    if other_id == self.id:
  29.240 +                        results.append(OrlandiShare(self, field, xi, rhoi, Cx))
  29.241 +                    else:
  29.242 +                        # Send ``xi``, ``rhoi``, and commitment
  29.243 +                        self._send_orlandi_share(other_id, pc, xi, rhoi, Cx)
  29.244 +            else:
  29.245 +                # Expect ``xi``, ``rhoi``, and commitment
  29.246 +                results.append(self._expect_orlandi_share(peer_id, field))
  29.247 +        # do actual communication
  29.248 +        self.activate_reactor()
  29.249 +        # Unpack a singleton list.
  29.250 +        if len(results) == 1:
  29.251 +            return results[0]
  29.252 +        return results
  29.253 +
  29.254 +    def open(self, share, receivers=None, threshold=None):
  29.255 +        """Share reconstruction.
  29.256 +
  29.257 +        Every partyi broadcasts a share pair ``(x_i', rho_x,i')``.
  29.258 +
  29.259 +        The parties compute the sums ``x'``, ``rho_x'`` and check
  29.260 +        ``Com_ck(x',rho_x' = C_x``.
  29.261 +
  29.262 +        If yes, return ``x = x'``, else else return :const:`None`.
  29.263 +        """
  29.264 +        assert isinstance(share, Share)
  29.265 +        # all players receive result by default
  29.266 +        if receivers is None:
  29.267 +            receivers = self.players.keys()
  29.268 +        assert threshold is None
  29.269 +        threshold = self.num_players - 1
  29.270 +
  29.271 +        field = share.field
  29.272 +
  29.273 +        self.program_counter[-1] += 1
  29.274 +
  29.275 +        def recombine_value(shares, Cx):
  29.276 +            x = 0
  29.277 +            rho1 = 0
  29.278 +            rho2 = 0
  29.279 +            for xi, rhoi1, rhoi2 in shares:
  29.280 +                x += xi
  29.281 +                rho1 += rhoi1
  29.282 +                rho2 += rhoi2
  29.283 +            Cx1 = commitment.commit(x.value, rho1.value, rho2.value)
  29.284 +            if Cx1 == Cx:
  29.285 +                return x
  29.286 +            else:
  29.287 +                #return x
  29.288 +                raise OrlandiException("Wrong commitment for value %s, %s, %s, found %s expected %s." %
  29.289 +                                       (x, rho1, rho2, Cx1, Cx))
  29.290 +
  29.291 +        def deserialize(ls):
  29.292 +            shares = [(field(long(x)), field(long(rho1)), field(long(rho2)))
  29.293 +                      for x, rho1, rho2 in map(self.list_str, ls)]
  29.294 +            return shares
  29.295 +
  29.296 +        def exchange((xi, (rhoi1, rhoi2), Cx), receivers):
  29.297 +            # Send share to all receivers.
  29.298 +            ds = self.broadcast(self.players.keys(), receivers,
  29.299 +                                str((str(xi.value),
  29.300 +                                     str(rhoi1.value),
  29.301 +                                     str(rhoi2.value))))
  29.302 +
  29.303 +            if self.id in receivers:
  29.304 +                result = gatherResults(ds)
  29.305 +                result.addCallbacks(deserialize, self.error_handler)
  29.306 +                result.addCallbacks(recombine_value, self.error_handler,
  29.307 +                                    callbackArgs=(Cx,))
  29.308 +                return result
  29.309 +
  29.310 +        result = share.clone()
  29.311 +        self.schedule_callback(result, exchange, receivers)
  29.312 +        result.addErrback(self.error_handler)
  29.313 +
  29.314 +        # do actual communication
  29.315 +        self.activate_reactor()
  29.316 +
  29.317 +        if self.id in receivers:
  29.318 +            return result
  29.319 +
  29.320 +    def random_share(self, field):
  29.321 +        """Generate a random share in the field, field.
  29.322 +
  29.323 +        To generate a share of a random element ``r in Z_p``, party
  29.324 +        ``P_i`` chooses at random ``r_i, rho_ri in Z_p X (Z_p)^2`` and
  29.325 +        broadcast ``C_r^i = Com_ck(r_i, rho_ri)``.
  29.326 +
  29.327 +        Every party computes ``C_r = PRODUCT_i=1^n C_r^i = Com_ck(r,
  29.328 +        rho_r)``, where ``r_i = SUM_i=1^n r_i and rho_r = SUM_i=1^n
  29.329 +        rho_ri``.
  29.330 +
  29.331 +        Party ``P_i sets [r]_i = (r_i, rho_ri, C_r)``.
  29.332 +        """
  29.333 +        self.program_counter[-1] += 1
  29.334 +
  29.335 +        # P_i chooses at random r_i, rho_ri in Z_p x (Z_p)^2
  29.336 +        ri = field(rand.randint(0, field.modulus - 1))
  29.337 +        rhoi1 = field(rand.randint(0, field.modulus - 1))
  29.338 +        rhoi2 = field(rand.randint(0, field.modulus - 1))
  29.339 +
  29.340 +        # compute C_r^i = Com_ck(r_i, rho_ri).
  29.341 +        Cri = commitment.commit(ri.value, rhoi1, rhoi2)
  29.342 +
  29.343 +        # Broadcast C_r^i.
  29.344 +        sls = gatherResults(self.broadcast(self.players.keys(), self.players.keys(), repr(Cri)))
  29.345 +
  29.346 +        def compute_commitment(ls):
  29.347 +            Cr = ls.pop()
  29.348 +            for Cri in ls:
  29.349 +                Cr = Cr * Cri
  29.350 +            return OrlandiShare(self, field, ri, (rhoi1, rhoi2), Cr)
  29.351 +
  29.352 +        def deserialize(ls):
  29.353 +            return [ commitment.deserialize(x) for x in ls ]
  29.354 +
  29.355 +        sls.addCallbacks(deserialize, self.error_handler)
  29.356 +        sls.addCallbacks(compute_commitment, self.error_handler)
  29.357 +
  29.358 +        s = Share(self, field)
  29.359 +        # We add the result to the chains in triple.
  29.360 +        sls.chainDeferred(s)
  29.361 +
  29.362 +        # do actual communication
  29.363 +        self.activate_reactor()
  29.364 +
  29.365 +        return s
  29.366 +
  29.367 +    def add(self, share_a, share_b):
  29.368 +        """Addition of shares.
  29.369 +
  29.370 +        Communication cost: none.
  29.371 +
  29.372 +        Each party ``P_i`` computes::
  29.373 +
  29.374 +          [z]_i = [x]_i + [y]_i
  29.375 +                = (x_i + y_i mod p, rho_xi + rho_yi mod p, C_x * C_y)
  29.376 +
  29.377 +        """
  29.378 +        def is_share(s, field):
  29.379 +            if not isinstance(s, Share):
  29.380 +                if not isinstance(s, FieldElement):
  29.381 +                    s = field(s)
  29.382 +                (v, rhov, Cv) = self._additive_constant(field(0), s)
  29.383 +                return OrlandiShare(self, field, v, rhov, Cv)
  29.384 +            return s
  29.385 +
  29.386 +        # Either share_a or share_b must have an attribute called "field".
  29.387 +        field = getattr(share_a, "field", getattr(share_b, "field", None))
  29.388 +
  29.389 +        share_a = is_share(share_a, field)
  29.390 +        share_b = is_share(share_b, field)
  29.391 +
  29.392 +        # Add rho_xi and rho_yi and compute the commitment.
  29.393 +        def compute_sums((x, y)):
  29.394 +            (zi, (rhozi1, rhozi2), Cz) = self._plus(x, y)
  29.395 +            return OrlandiShare(self, field, zi, (rhozi1, rhozi2), Cz)
  29.396 +
  29.397 +        result = gather_shares([share_a, share_b])
  29.398 +        result.addCallbacks(compute_sums, self.error_handler)
  29.399 +        return result
  29.400 +
  29.401 +    def sub(self, share_a, share_b):
  29.402 +        """Subtraction of shares.
  29.403 +
  29.404 +        Communication cost: none.
  29.405 +
  29.406 +        Each party ``P_i`` computes::
  29.407 +
  29.408 +          [z]_i = [x]_i - [y]_i
  29.409 +                = (x_i - y_i mod p, rho_x,i - rho_y,i mod p, C_x * C_y)
  29.410 +
  29.411 +        """
  29.412 +        def is_share(s, field):
  29.413 +            if not isinstance(s, Share):
  29.414 +                if not isinstance(s, FieldElement):
  29.415 +                    s = field(s)
  29.416 +                (v, rhov, Cv) = self._additive_constant(field(0), s)
  29.417 +                return OrlandiShare(self, field, v, rhov, Cv)
  29.418 +            return s
  29.419 +
  29.420 +        # Either share_a or share_b must have an attribute called "field".
  29.421 +        field = getattr(share_a, "field", getattr(share_b, "field", None))
  29.422 +
  29.423 +        share_a = is_share(share_a, field)
  29.424 +        share_b = is_share(share_b, field)
  29.425 +
  29.426 +        # Subtract xi and yi, rhoxi and rhoyi, and compute the commitment
  29.427 +        def compute_subs((x, y)):
  29.428 +            zi, (rhozi1, rhozi2), Cz = self._minus(x, y)
  29.429 +            return OrlandiShare(self, field, zi, (rhozi1, rhozi2), Cz)
  29.430 +
  29.431 +        result = gather_shares([share_a, share_b])
  29.432 +        result.addCallbacks(compute_subs, self.error_handler)
  29.433 +        return result
  29.434 +
  29.435 +    def input(self, inputters, field, number=None, threshold=None):
  29.436 +        """Input *number* to the computation.
  29.437 +
  29.438 +        The input is shared using the :meth:`shift` method.
  29.439 +        """
  29.440 +        return self.shift(inputters, field, number)
  29.441 +
  29.442 +
  29.443 +    def shift(self, inputters, field, number=None):
  29.444 +        """Shift of a share.
  29.445 +
  29.446 +        Useful for input.
  29.447 +
  29.448 +        Communication cost: ???.
  29.449 +
  29.450 +        Assume the parties are given a random share ``[r]`` by a
  29.451 +        trusted dealer. Then we denote the following protocol but
  29.452 +        ``[x] = Shift(P_i, x, [r])``.
  29.453 +
  29.454 +        1. ``r = OpenTo(P_i, [r]``
  29.455 +
  29.456 +        2. ``P_i broadcasts Delta = r - x``
  29.457 +
  29.458 +        3. ``[x] = [r] - Delta``
  29.459 +        """
  29.460 +        # TODO: Communitcation costs?
  29.461 +        assert (self.id in inputters and number != None) or (self.id not in inputters)
  29.462 +
  29.463 +        self.program_counter[-1] += 1
  29.464 +
  29.465 +        results = []
  29.466 +        def hack(_, peer_id):
  29.467 +            # Assume the parties are given a random share [r] by a
  29.468 +            # trusted dealer.
  29.469 +            share_r = self.random_share(field)
  29.470 +            # 1. r = OpenTo(P_i, [r])
  29.471 +            open_r = self.open(share_r, [peer_id])
  29.472 +            def subtract_delta(delta, share_r):
  29.473 +                delta = field(long(delta))
  29.474 +                x = self.sub(share_r, delta)
  29.475 +                return x
  29.476 +            if peer_id == self.id:
  29.477 +                def g(r, x):
  29.478 +                    delta = r - x
  29.479 +                    delta = self.broadcast([peer_id], self.players.keys(),
  29.480 +                                           str(delta.value))
  29.481 +                    self.schedule_callback(delta, subtract_delta, share_r)
  29.482 +                    delta.addErrback(self.error_handler)
  29.483 +                    return delta
  29.484 +                self.schedule_callback(open_r, g, number)
  29.485 +                open_r.addErrback(self.error_handler)
  29.486 +                return open_r
  29.487 +            else:
  29.488 +                d = Deferred()
  29.489 +                def g(_, peer_id, share_r):
  29.490 +                    delta = self.broadcast([peer_id], self.players.keys())
  29.491 +                    self.schedule_callback(delta, subtract_delta, share_r)
  29.492 +                    delta.addErrback(self.error_handler)
  29.493 +                    return delta
  29.494 +                self.schedule_callback(d, g, peer_id, share_r)
  29.495 +                d.addErrback(self.error_handler)
  29.496 +                d.callback(None)
  29.497 +                return d
  29.498 +
  29.499 +        for peer_id in inputters:
  29.500 +            s = Share(self, field)
  29.501 +            self.schedule_callback(s, hack, peer_id)
  29.502 +            s.addErrback(self.error_handler)
  29.503 +            s.callback(None)
  29.504 +            results.append(s)
  29.505 +
  29.506 +        # do actual communication
  29.507 +        self.activate_reactor()
  29.508 +
  29.509 +        if len(results) == 1:
  29.510 +             return results[0]
  29.511 +        return results
  29.512 +
  29.513 +    def mul(self, share_x, share_y):
  29.514 +        """Multiplication of shares.
  29.515 +
  29.516 +        Communication cost: ???.
  29.517 +        """
  29.518 +        # TODO: Communication cost?
  29.519 +        assert isinstance(share_x, Share) or isinstance(share_y, Share), \
  29.520 +            "At least one of share_x and share_y must be a Share."
  29.521 +
  29.522 +        self.program_counter[-1] += 1
  29.523 +
  29.524 +        field = getattr(share_x, "field", getattr(share_y, "field", None))
  29.525 +
  29.526 +        def finish_mul((a, b, c)):
  29.527 +            return self._basic_multiplication(share_x, share_y, a, b, c)
  29.528 +
  29.529 +        # This will be the result, a Share object.
  29.530 +        result = Share(self, share_x.field)
  29.531 +        # This is the Deferred we will do processing on.
  29.532 +        triple = self._get_triple(field)
  29.533 +        triple = self.schedule_complex_callback(triple, finish_mul)
  29.534 +        # We add the result to the chains in triple.
  29.535 +        triple.chainDeferred(result)
  29.536 +        return result
  29.537 +
  29.538 +    def _additive_constant(self, zero, field_element):
  29.539 +        """Greate an additive constant.
  29.540 +
  29.541 +        Any additive constant can be interpreted as:
  29.542 +        ``[c]_1 = (c, 0, Com_ck(c,0))`` and
  29.543 +        ``[c]_i = (0, 0, Com_ck(c,0)) for i != 1``.
  29.544 +        """
  29.545 +        v = zero
  29.546 +        if self.id == 1:
  29.547 +            v = field_element
  29.548 +        Cx = commitment.commit(field_element.value, zero.value, zero.value)
  29.549 +        return (v, (zero, zero), Cx)
  29.550 +
  29.551 +    def _plus(self, x, y):
  29.552 +        """Addition of share-tuples *x* and *y*.
  29.553 +
  29.554 +        Each party ``P_i`` computes:
  29.555 +        ``[x]_i = (x_i, rho_xi, C_x)``
  29.556 +        ``[y]_i = (y_i, rho_yi, C_y)``
  29.557 +        ``[z]_i = [x]_i + [y]_i
  29.558 +                = (x_i + y_i mod p, rho_xi + rho_yi mod p, C_x * C_y)``.
  29.559 +        """
  29.560 +        (xi, (rhoxi1, rhoxi2), Cx) = x
  29.561 +        (yi, (rhoyi1, rhoyi2), Cy) = y
  29.562 +        zi = xi + yi
  29.563 +        rhozi1 = rhoxi1 + rhoyi1
  29.564 +        rhozi2 = rhoxi2 + rhoyi2
  29.565 +        Cz = Cx * Cy
  29.566 +        return (zi, (rhozi1, rhozi2), Cz)
  29.567 +
  29.568 +    def _minus(self, x, y):
  29.569 +        """Subtraction of share-tuples *x* and *y*.
  29.570 +
  29.571 +        Each party ``P_i`` computes:
  29.572 +        ``[x]_i = (x_i, rho_x,i, C_x)``
  29.573 +        ``[y]_i = (y_i, rho_y,i, C_y)``
  29.574 +        ``[z]_i = [x]_i - [y]_i
  29.575 +                = (x_i - y_i mod p, rho_x,i - rho_y,i mod p, C_x / C_y)``.
  29.576 +        """
  29.577 +        xi, (rhoxi1, rhoxi2), Cx = x
  29.578 +        yi, (rhoyi1, rhoyi2), Cy = y
  29.579 +        zi = xi - yi
  29.580 +        rhozi1 = rhoxi1 - rhoyi1
  29.581 +        rhozi2 = rhoxi2 - rhoyi2
  29.582 +        Cz = Cx / Cy
  29.583 +        return (zi, (rhozi1, rhozi2), Cz)
  29.584 +
  29.585 +    def _cmul(self, share_x, share_y, field):
  29.586 +        """Multiplication of a share with a constant.
  29.587 +
  29.588 +        Either share_x or share_y must be an OrlandiShare but not
  29.589 +        both. Returns None if both share_x and share_y are
  29.590 +        OrlandiShares.
  29.591 +        """
  29.592 +        def constant_multiply(x, c):
  29.593 +            assert(isinstance(c, FieldElement))
  29.594 +            zi, rhoz, Cx = self._const_mul(c.value, x)
  29.595 +            return OrlandiShare(self, field, zi, rhoz, Cx)
  29.596 +        if not isinstance(share_x, Share):
  29.597 +            # Then share_y must be a Share => local multiplication. We
  29.598 +            # clone first to avoid changing share_y.
  29.599 +            assert isinstance(share_y, Share), \
  29.600 +                "At least one of the arguments must be a share."
  29.601 +            result = share_y.clone()
  29.602 +            result.addCallback(constant_multiply, share_x)
  29.603 +            return result
  29.604 +        if not isinstance(share_y, Share):
  29.605 +            # Likewise when share_y is a constant.
  29.606 +            assert isinstance(share_x, Share), \
  29.607 +                "At least one of the arguments must be a share."
  29.608 +            result = share_x.clone()
  29.609 +            result.addCallback(constant_multiply, share_y)
  29.610 +            return result
  29.611 +        return None
  29.612 +
  29.613 +    def _const_mul(self, c, x):
  29.614 +        """Multiplication of a share-tuple with a constant c."""
  29.615 +        assert(isinstance(c, long) or isinstance(c, int))
  29.616 +        xi, (rhoi1, rhoi2), Cx = x
  29.617 +        zi = xi * c
  29.618 +        rhoz = (rhoi1 * c, rhoi2 * c)
  29.619 +        Cz = Cx**c
  29.620 +        return (zi, rhoz, Cz)
  29.621 +
  29.622 +    def _get_share(self, field, value):
  29.623 +        Cc = commitment.commit(value * 3, 0, 0)
  29.624 +        c = OrlandiShare(self, field, field(value), (field(0), field(0)), Cc)
  29.625 +        return c
  29.626 +
  29.627 +    @preprocess("random_triple")
  29.628 +    def _get_triple(self, field):
  29.629 +        c, d = self.random_triple(field, 1)
  29.630 +        def f(ls):
  29.631 +            return ls[0]
  29.632 +        d.addCallbacks(f, self.error_handler)
  29.633 +        return d
  29.634 +
  29.635 +    def _basic_multiplication(self, share_x, share_y, triple_a, triple_b, triple_c):
  29.636 +        """Multiplication of shares give a triple.
  29.637 +
  29.638 +        Communication cost: ???.
  29.639 +
  29.640 +        ``d = Open([x] - [a])``
  29.641 +        ``e = Open([y] - [b])``
  29.642 +        ``[z] = e[x] + d[y] - [de] + [c]``
  29.643 +        """
  29.644 +        assert isinstance(share_x, Share) or isinstance(share_y, Share), \
  29.645 +            "At least one of share_x and share_y must be a Share."
  29.646 +
  29.647 +        self.program_counter[-1] += 1
  29.648 +
  29.649 +        field = getattr(share_x, "field", getattr(share_y, "field", None))
  29.650 +        n = field(0)
  29.651 +
  29.652 +        cmul_result = self._cmul(share_x, share_y, field)
  29.653 +        if cmul_result is  not None:
  29.654 +            return cmul_result
  29.655 +
  29.656 +        def multiply((x, y, d, e, c)):
  29.657 +            # [de]
  29.658 +            de = self._additive_constant(field(0), d * e)
  29.659 +            # e[x]
  29.660 +            t1 = self._const_mul(e.value, x)
  29.661 +            # d[y]
  29.662 +            t2 = self._const_mul(d.value, y)
  29.663 +            # d[y] - [de]
  29.664 +            t3 = self._minus(t2, de)
  29.665 +            # d[y] - [de] + [c]
  29.666 +            t4 = self._plus(t3, c)
  29.667 +            # [z] = e[x] + d[y] - [de] + [c]
  29.668 +            zi, rhoz, Cz = self._plus(t1, t4)
  29.669 +            return OrlandiShare(self, field, zi, rhoz, Cz)
  29.670 +
  29.671 +        # d = Open([x] - [a])
  29.672 +        d = self.open(share_x - triple_a)
  29.673 +        # e = Open([y] - [b])
  29.674 +        e = self.open(share_y - triple_b)
  29.675 +        result = gather_shares([share_x, share_y, d, e, triple_c])
  29.676 +        result.addCallbacks(multiply, self.error_handler)
  29.677 +
  29.678 +        # do actual communication
  29.679 +        self.activate_reactor()
  29.680 +
  29.681 +        return result
  29.682 +
  29.683 +    def sum_poly(self, j, ls):
  29.684 +        exp  = j
  29.685 +        fj, (rhoj1, rhoj2), Cfj = ls[0]
  29.686 +        x    = fj*exp
  29.687 +        rho1 = rhoj1 * exp
  29.688 +        rho2 = rhoj2 * exp
  29.689 +        Cx   = Cfj**exp
  29.690 +        exp *= j
  29.691 +
  29.692 +        for (fj, (rhoj1, rhoj2), Cfj) in ls[1:]:
  29.693 +            x += fj * exp
  29.694 +            rho1 += rhoj1 * exp
  29.695 +            rho2 += rhoj2 * exp
  29.696 +            Cx = Cx * (Cfj**exp)
  29.697 +            exp *= j
  29.698 +        return x, (rho1, rho2), Cx
  29.699 +
  29.700 +    def leak_tolerant_mul(self, share_x, share_y, M):
  29.701 +        """Leak tolerant multiplication of shares.
  29.702 +
  29.703 +        Communication cost: ???.
  29.704 +
  29.705 +        Assuming a set of multiplicative triples:
  29.706 +        ``M = ([a_i], [b_i], [c_i]) for 1 <= i <= 2d + 1``.
  29.707 +
  29.708 +        1. ``for i = 1, ..., d do [f_i] = rand(), [g_i] = rand()``
  29.709 +
  29.710 +        2. Compute::
  29.711 +
  29.712 +             for j = 1, ..., 2d+1 do
  29.713 +             [F_j] = [x] + SUM_i=1^d [f_i]*j^i
  29.714 +             and
  29.715 +             [G_j] = [y] + SUM_i=1^d [g_i]*j^i
  29.716 +
  29.717 +        3. ``for j = 1, ..., 2d+1 do [H_j] = Mul([F_j], [G_j], [a_j],
  29.718 +           [b_j], [c_j])``
  29.719 +
  29.720 +        4. compute ``[H_0] = SUM_j=1^2d+1 delta_j[H_j]`` where
  29.721 +           ``delta_j = PRODUCT_k=1, k!=j^2d+1 k/(k-j)``
  29.722 +
  29.723 +        5. output ``[z] = [H_0]``
  29.724 +        """
  29.725 +        assert isinstance(share_x, Share) or isinstance(share_y, Share), \
  29.726 +            "At least one of share_x and share_y must be a Share."
  29.727 +
  29.728 +        self.program_counter[-1] += 1
  29.729 +
  29.730 +        field = getattr(share_x, "field", getattr(share_y, "field", None))
  29.731 +        n = field(0)
  29.732 +
  29.733 +        cmul_result = self._cmul(share_x, share_y, field)
  29.734 +        if cmul_result is not None:
  29.735 +            return cmul_result
  29.736 +
  29.737 +        # 1. for i = 1, ..., d do [f_i] = rand(), [g_i] = rand()
  29.738 +        d = (len(M) - 1) // 2
  29.739 +        deltas = self.compute_delta(d)
  29.740 +        f = []
  29.741 +        g = []
  29.742 +        for x in xrange(d):
  29.743 +            f.append(self.random_share(field))
  29.744 +            g.append(self.random_share(field))
  29.745 +
  29.746 +        def compute_polynomials(t):
  29.747 +            x, y = t[0]
  29.748 +            f = []
  29.749 +            g = []
  29.750 +            if 1 in t:
  29.751 +                f = t[1]
  29.752 +            if 2 in t:
  29.753 +                g = t[2]
  29.754 +#             print "==> poly", self.id
  29.755 +#             print "x:", x
  29.756 +#             print "y:", y
  29.757 +#             print "f:", f
  29.758 +#             print "g:", g
  29.759 +            # 2) for j = 1, ..., 2d+1 do
  29.760 +            # [F_j] = [x] + SUM_i=1^d [f_i]*j^i
  29.761 +            # and
  29.762 +            # [G_j] = [y] + SUM_i=1^d [g_i]*j^i
  29.763 +            h0i, rhoh0, Ch0 = self._additive_constant(field(0), n)
  29.764 +            H0 = OrlandiShare(self, field, h0i, rhoh0, Ch0)
  29.765 +            xi, (rhoxi1, rhoxi2), Cx = x
  29.766 +            yi, (rhoyi1, rhoyi2), Cy = y
  29.767 +
  29.768 +            for j in xrange(1, 2*d + 2):
  29.769 +                Fji = xi
  29.770 +                rho1_Fji = rhoxi1
  29.771 +                rho2_Fji = rhoxi2
  29.772 +                C_Fji = Cx
  29.773 +                if f != []:
  29.774 +                    # SUM_i=1^d [f_i]*j^i
  29.775 +                    vi, (rhovi1, rhovi2), Cv = self.sum_poly(j, f)
  29.776 +                    # [F_j] = [x] + SUM_i=1^d [f_i]*j^i
  29.777 +                    Fji += vi
  29.778 +                    rho1_Fji += rhovi1
  29.779 +                    rho2_Fji += rhovi2
  29.780 +                    C_Fji *= Cv
  29.781 +                Gji = yi
  29.782 +                rho1_Gji = rhoyi1
  29.783 +                rho2_Gji = rhoyi2
  29.784 +                C_Gji = Cy
  29.785 +                if g != []:
  29.786 +                    # SUM_i=1^d [g_i]*j^i
  29.787 +                    wi, (rhowi1, rhowi2), Cw = self.sum_poly(j, g)
  29.788 +                    # [G_j] = [y] + SUM_i=1^d [g_i]*j^i
  29.789 +                    Gji += wi
  29.790 +                    rho1_Gji += rhowi1
  29.791 +                    rho2_Gji += rhowi2
  29.792 +                    C_Gji *= Cw
  29.793 +                Fj = OrlandiShare(self, field, Fji, (rho1_Fji, rho2_Fji), C_Fji)
  29.794 +                Gj = OrlandiShare(self, field, Gji, (rho1_Gji, rho2_Gji), C_Gji)
  29.795 +                a, b, c = M.pop(0)
  29.796 +
  29.797 +                # [H_j] = Mul([F_j], [G_j], [a_j], [b_j], [c_j])
  29.798 +                Hj = self._basic_multiplication(Fj, Gj, a, b, c)
  29.799 +                dj = self._cmul(field(deltas[j - 1]), Hj, field)
  29.800 +                H0 = H0 + dj
  29.801 +            # 5) output [z] = [H_0]
  29.802 +            return H0
  29.803 +
  29.804 +        ls = [gather_shares([share_x, share_y])]
  29.805 +        if g:
  29.806 +            ls.append(gather_shares(g))
  29.807 +        if f:
  29.808 +            ls.append(gather_shares(f))
  29.809 +        result = gather_shares(ls)
  29.810 +        self.schedule_callback(result, compute_polynomials)
  29.811 +        result.addErrback(self.error_handler)
  29.812 +
  29.813 +        # do actual communication
  29.814 +        self.activate_reactor()
  29.815 +
  29.816 +        return result
  29.817 +
  29.818 +    def triple_gen(self, field):
  29.819 +        """Generate a triple ``a, b, c`` s.t. ``c = a * b``.
  29.820 +
  29.821 +        1. Every party ``P_i`` chooses random values ``a_i, r_i in Z_p
  29.822 +           X (Z_p)^2``, compute ``alpha_i = Enc_eki(a_i)`` and ``Ai =
  29.823 +           Com_ck(a_i, r_i)``, and broadcast them.
  29.824 +
  29.825 +        2. Every party ``P_j`` does:
  29.826 +
  29.827 +           a. choose random ``b_j, s_j in Z_p X (Z_p)^2``.
  29.828 +
  29.829 +           b. compute ``B_j = ``Com_ck(b_j, s_j)`` and broadcast it.
  29.830 +
  29.831 +           c. ``P_j`` do towards every other party:
  29.832 +
  29.833 +                i. choose random ``d_ij in Z_p^3``
  29.834 +
  29.835 +                ii. compute and send
  29.836 +                    ``gamma_ij = alpha_i^b_j Enc_ek_i(1;1)^d_ij`` to ``P_i``.
  29.837 +
  29.838 +
  29.839 +        3. Every party ``P_i`` does:
  29.840 +
  29.841 +           a. compute ``c_i = SUM_j Dec_sk_i(gamma_ij) - SUM_j d_ij mod p``
  29.842 +
  29.843 +           b. pick random ``t_i in (Z_p)^2``, compute and
  29.844 +              broadcast ``C_i = Com_ck(c_i, t_i)``
  29.845 +
  29.846 +        4. Everyone computes:
  29.847 +           ``(A, B, C) = (PRODUCT_i A_i, PRODUCT_i B_i, PRODUCT_i C_i)``
  29.848 +
  29.849 +        5. Every party ``P_i`` outputs shares ``[a_i] = (a_i, r_i, A)``,
  29.850 +           ``[b_i] = (b_i, s_i, B)``, and ``[c_i] = (c_i, t_i, C)``.
  29.851 +
  29.852 +        """
  29.853 +        self.program_counter[-1] += 1
  29.854 +
  29.855 +        def random_number(p):
  29.856 +            return field(rand.randint(0, p - 1))
  29.857 +
  29.858 +        def product(ls):
  29.859 +            """Compute the product of the elements in the list *ls*."""
  29.860 +            b = commitment.deserialize(ls[0])
  29.861 +            for x in ls[1:]:
  29.862 +                b *= commitment.deserialize(x)
  29.863 +            return b
  29.864 +
  29.865 +        def sum(ls):
  29.866 +            """Compute the sum of the elements in the list *ls*."""
  29.867 +            b = field(0)
  29.868 +            for x in ls:
  29.869 +                b += x
  29.870 +            return b
  29.871 +
  29.872 +        def step45(Cs, alphas, gammas, alpha_randomness,
  29.873 +                   As, Bs, ai, bi, ci, r, s, t, dijs):
  29.874 +            """4) Everyone computes:
  29.875 +                  ``A = PRODUCT_i A_i``
  29.876 +                  ``B = PRODUCT_i B_i``
  29.877 +                  ``C = PRODUCT_i C_i``
  29.878 +
  29.879 +               5) Every party ``P_i`` outputs shares ``[a_i] = (a_i, r_i, A)``,
  29.880 +                  ``[b_i] = (b_i, s_i, B)``, and ``[c_i] = (c_i, t_i, C)``.
  29.881 +            """
  29.882 +            A = product(As)
  29.883 +            B = product(Bs)
  29.884 +            C = product(Cs)
  29.885 +            a = OrlandiShare(self, field, ai, r, A)
  29.886 +            b = OrlandiShare(self, field, bi, s, B)
  29.887 +            c = OrlandiShare(self, field, ci, t, C)
  29.888 +            return (a, b, c, (alphas, alpha_randomness, gammas, dijs))
  29.889 +
  29.890 +        def decrypt_gammas(ls):
  29.891 +            """Decrypt all the elements of the list *ls*."""
  29.892 +            rs = []
  29.893 +            for x in ls:
  29.894 +                rs.append(field(decrypt(x, self.players[self.id].seckey)))
  29.895 +            return rs
  29.896 +
  29.897 +        def step3(gammas, alphas, alpha_randomness, As, Bs, ai, bi, r, s, dijs):
  29.898 +            """3) Every party ``P_i`` does:
  29.899 +                  (a) compute
  29.900 +                  ``c_i = SUM_j Dec_sk_i(gamma_ij) - SUM_j d_ji mod p``
  29.901 +
  29.902 +                  (b) pick random ``t_i in (Z_p)^2``, compute and
  29.903 +                      broadcast ``C_i = Com_ck(c_i, t_i)``
  29.904 +            """
  29.905 +            # c_i = SUM_j Dec_sk_i(gamma_ij) - SUM_j d_ji mod p.
  29.906 +            ls = decrypt_gammas(gammas)
  29.907 +            ci = sum(ls) - sum(dijs)
  29.908 +            # (b) pick random t_i in (Z_p)^2.
  29.909 +            t1 = random_number(field. modulus)
  29.910 +            t2 = random_number(field. modulus)
  29.911 +            t = (t1, t2)
  29.912 +            # C_i = Com_ck(c_i, t_i).
  29.913 +            Ci = commitment.commit(ci.value, t1.value, t2.value)
  29.914 +
  29.915 +            # Broadcast Ci.
  29.916 +            Cs = self.broadcast(self.players.keys(), self.players.keys(),
  29.917 +                                repr(Ci))
  29.918 +            result = gatherResults(Cs)
  29.919 +            result.addCallbacks(step45, self.error_handler,
  29.920 +                                callbackArgs=(alphas, gammas, alpha_randomness,
  29.921 +                                              As, Bs, ai, bi, ci, r, s, t, dijs))
  29.922 +            return result
  29.923 +
  29.924 +        def step2c(Bs, As, alphas, alpha_randomness, ai, bj, r, s):
  29.925 +            """(c) P_j do, towards every other party:
  29.926 +                   i. choose random d_i,j in Z_p^3
  29.927 +                   ii. compute and send
  29.928 +            gamma_ij = alpha_i^b_j Enc_ek_i(1;1)^d_ij to P_i.
  29.929 +            """
  29.930 +
  29.931 +            # (c) P_j do, towards every other party:
  29.932 +            dijs = [None] * len(self.players.keys())
  29.933 +            results = [None] * len(self.players.keys())
  29.934 +            pc = tuple(self.program_counter)
  29.935 +            for pi in self.players.keys():
  29.936 +                n = self.players[pi].pubkey[0]
  29.937 +                nsq = n * n
  29.938 +                # choose random d_i,j in Z_p^3
  29.939 +                dij = random_number(field.modulus**3)
  29.940 +                # Enc_ek_i(1;1)^d_ij
  29.941 +                enc = encrypt_r(1, 1, self.players[pi].pubkey)
  29.942 +                t1 = pow(enc, dij.value, nsq)
  29.943 +                # alpha_i^b_j.
  29.944 +                t2 = pow(alphas[pi - 1], bj.value, nsq)
  29.945 +                # gamma_ij = alpha_i^b_j Enc_ek_i(1;1)^d_ij
  29.946 +                gammaij = (t2) * (t1) % nsq
  29.947 +                # Broadcast gamma_ij
  29.948 +                if pi != self.id:
  29.949 +                    self.protocols[pi].sendData(pc, PAILLIER, str(gammaij))
  29.950 +                    d = Deferred()
  29.951 +                    d.addCallbacks(lambda value: long(value), self.error_handler)
  29.952 +                    self._expect_data(pi, PAILLIER, d)
  29.953 +                else:
  29.954 +                    d = Deferred()
  29.955 +                    d.callback(gammaij)
  29.956 +                dijs[pi - 1] = dij
  29.957 +                results[pi - 1] = d
  29.958 +            result = gatherResults(results)
  29.959 +            self.schedule_callback(result, step3, alphas, alpha_randomness,
  29.960 +                                   As, Bs, ai, bj, r, s, dijs)
  29.961 +            result.addErrback(self.error_handler)
  29.962 +            return result
  29.963 +
  29.964 +        def step2ab((alphas, As), ai, r, alpha_randomness):
  29.965 +            """2) Every party P_j does:
  29.966 +                  (a) choose random b_j, s_j in Z_p X (Z_p)^2.
  29.967 +
  29.968 +                  (b) compute B_j = Com_ck(b_j, s_j) and broadcast it.
  29.969 +            """
  29.970 +            # (a) choose random b_j, s_j in Z_p X (Z_p)^2.
  29.971 +            bj = random_number(field.modulus)
  29.972 +            s1 = random_number(field.modulus)
  29.973 +            s2 = random_number(field.modulus)
  29.974 +            # (b) compute B_j = Com_ck(b_j, s_j).
  29.975 +            Bj = commitment.commit(bj.value, s1.value, s2.value)
  29.976 +
  29.977 +            # Broadcast B_j.
  29.978 +            results = self.broadcast(self.players.keys(), self.players.keys(), repr(Bj))
  29.979 +            result = gatherResults(results)
  29.980 +            self.schedule_callback(result, step2c, As, alphas, alpha_randomness,
  29.981 +                                   ai, bj, r, (s1, s2))
  29.982 +            result.addErrback(self.error_handler)
  29.983 +            return result
  29.984 +
  29.985 +        # 1) Every party P_i chooses random values a_i, r_i in Z_p X (Z_p)^2,
  29.986 +        #    compute alpha_i = Enc_eki(a_i) and Ai = Com_ck(a_i, r_i), and
  29.987 +        #    broadcast them.
  29.988 +
  29.989 +        # Every party P_i chooses random values a_i, r_i in Z_p X (Z_p)^2
  29.990 +        ai = random_number(field.modulus)
  29.991 +        r1 = random_number(field.modulus)
  29.992 +        r2 = random_number(field.modulus)
  29.993 +
  29.994 +        # compute alpha_i = Enc_eki(a_i)
  29.995 +        n, g = self.players[self.id].pubkey
  29.996 +        alpha_randomness = rand.randint(1, long(n))
  29.997 +        alphai = encrypt_r(ai.value, alpha_randomness, (n, g))
  29.998 +        # and A_i = Com_ck(a_i, r_i).
  29.999 +        Ai = commitment.commit(ai.value, r1.value, r2.value)
 29.1000 +
 29.1001 +        # broadcast alpha_i and A_i.
 29.1002 +        ds = self.broadcast(sorted(self.players.keys()),
 29.1003 +                            sorted(self.players.keys()),
 29.1004 +                            str(alphai) + ":" + repr(Ai))
 29.1005 +
 29.1006 +        result = gatherResults(ds)
 29.1007 +        def split_alphas_and_As(ls):
 29.1008 +            alphas = []
 29.1009 +            As = []
 29.1010 +            for x in ls:
 29.1011 +                alpha, Ai = x.split(':')
 29.1012 +                alphas.append(long(alpha))
 29.1013 +                As.append(Ai)
 29.1014 +            return alphas, As
 29.1015 +        self.schedule_callback(result, split_alphas_and_As)
 29.1016 +        self.schedule_callback(result, step2ab, ai, (r1, r2), alpha_randomness)
 29.1017 +        result.addErrback(self.error_handler)
 29.1018 +        return result
 29.1019 +
 29.1020 +    def triple_test(self, field):
 29.1021 +        """Generate a triple ``(a, b, c)`` where ``c = a * b``.
 29.1022 +
 29.1023 +        The triple ``(a, b, c)`` is checked against the
 29.1024 +        triple ``(x, y, z)`` and a random value ``r``.
 29.1025 +
 29.1026 +        """
 29.1027 +        triple1 = self.triple_gen(field)
 29.1028 +        triple2 = self.triple_gen(field)
 29.1029 +        r = self.open(self.random_share(field))
 29.1030 +
 29.1031 +        def check((v, oa, ob, oc, ox, oy, oz), a, b, c, ec):
 29.1032 +            if v is 0:
 29.1033 +                return None
 29.1034 +            return (a, b, c, ec)
 29.1035 +
 29.1036 +        def compute_value(((a, b, c, ec), (x, y, z, _), r)):
 29.1037 +            oa = self.open(a)
 29.1038 +            ob = self.open(b)
 29.1039 +            oc = self.open(c)
 29.1040 +            ox = self.open(x)
 29.1041 +            oy = self.open(y)
 29.1042 +            oz = self.open(z)
 29.1043 +            l = self._cmul(r, x, field)
 29.1044 +            m = self._cmul(r, y, field)
 29.1045 +            n = self._cmul(r*r, z, field)
 29.1046 +            d = c - self._basic_multiplication(a, b, l, m, n)
 29.1047 +            r = gather_shares([d, oa, ob, oc, ox, oy, oz])
 29.1048 +            r.addCallbacks(check, self.error_handler, callbackArgs=(a, b, c, ec))
 29.1049 +            return r
 29.1050 +
 29.1051 +        result = gatherResults([triple1, triple2, r])
 29.1052 +        self.schedule_callback(result, compute_value)
 29.1053 +        result.addErrback(self.error_handler)
 29.1054 +
 29.1055 +        # do actual communication
 29.1056 +        self.activate_reactor()
 29.1057 +
 29.1058 +        return result
 29.1059 +
 29.1060 +    def random_triple(self, field, quantity=1):
 29.1061 +        """Generate a list of triples ``(a, b, c)`` where ``c = a * b``.
 29.1062 +
 29.1063 +        The triple ``(a, b, c)`` is secure in the Fcrs-hybrid model.
 29.1064 +
 29.1065 +        """
 29.1066 +        self.program_counter[-1] += 1
 29.1067 +
 29.1068 +        M = []
 29.1069 +
 29.1070 +# print "Generating %i triples... relax, have a break..." % ((1 + self.s_lambda) * (2 * self.d + 1) * quantity)
 29.1071 +
 29.1072 +        for x in xrange((1 + self.s_lambda) * (2 * self.d + 1) * quantity):
 29.1073 +            M.append(self.triple_test(field))
 29.1074 +
 29.1075 +        def step3(ls):
 29.1076 +            """Coin-flip a subset test_set of M of size lambda(2d + 1)M."""
 29.1077 +            size = self.s_lambda * (2 * self.d + 1) * quantity
 29.1078 +            inx = 0
 29.1079 +            p_half = field.modulus // 2
 29.1080 +            def coin_flip(v, ls, test_set):
 29.1081 +                candidate = ls.pop(0)
 29.1082 +                if p_half > v:
 29.1083 +                    test_set.append(candidate)
 29.1084 +                else:
 29.1085 +                    ls.append(candidate)
 29.1086 +                if size > len(test_set):
 29.1087 +                    r = self.random_share(field)
 29.1088 +                    r = self.output(r)
 29.1089 +                    self.schedule_callback(r, coin_flip, ls, test_set)
 29.1090 +                    r.addErrback(self.error_handler)
 29.1091 +                    return r
 29.1092 +                return ls, test_set
 29.1093 +            r = self.random_share(field)
 29.1094 +            r = self.output(r)
 29.1095 +            self.schedule_callback(r, coin_flip, ls, [])
 29.1096 +            r.addErrback(self.error_handler)
 29.1097 +            return r
 29.1098 +
 29.1099 +        def step45(lists):
 29.1100 +            """For all i in test_set the parties reveal
 29.1101 +            the randomness used for TripleTest() and checks that
 29.1102 +            the randomness is consistent with the actual values."""
 29.1103 +            M_without_test_set = lists[0]
 29.1104 +            T = lists[1]
 29.1105 +
 29.1106 +            def defer_share(xi, (rho1, rho2), commitment):
 29.1107 +                d1 = Deferred()
 29.1108 +                d2 = Deferred()
 29.1109 +                d3 = Deferred()
 29.1110 +                d4 = Deferred()
 29.1111 +                d1.callback(xi)
 29.1112 +                d2.callback(rho1)
 29.1113 +                d3.callback(rho2)
 29.1114 +                d4.callback(commitment)
 29.1115 +                return gatherResults([d1, d2, d3, d4])
 29.1116 +
 29.1117 +            def get_share(x, ls):
 29.1118 +                share = ls[x * 4]
 29.1119 +                rho1 = ls[x * 4 + 1]
 29.1120 +                rho2 = ls[x * 4 + 2]
 29.1121 +                commitment = ls[x * 4 + 3]
 29.1122 +                return (share, rho1, rho2, commitment)
 29.1123 +
 29.1124 +            def send_share(player_id, pc, a):
 29.1125 +                self._send_orlandi_share(player_id, pc, a.share, a.rho, a.commitment)
 29.1126 +
 29.1127 +            def receive_shares(player_id):
 29.1128 +                Cx = Deferred()
 29.1129 +                xi = self._expect_share(player_id, field)
 29.1130 +                rho1 = self._expect_share(player_id, field)
 29.1131 +                rho2 = self._expect_share(player_id, field)
 29.1132 +                self._expect_data(player_id, TEXT, Cx)
 29.1133 +                Cx.addCallbacks(lambda Cx: commitment.deserialize(Cx),
 29.1134 +                                        self.error_handler)
 29.1135 +                return gatherResults([xi, rho1, rho2, Cx])
 29.1136 +
 29.1137 +            def send_long(player_id, pc, l):
 29.1138 +                self.protocols[player_id].sendData(pc, TEXT, str(l))
 29.1139 +
 29.1140 +            def receive_long(player_id):
 29.1141 +                l = Deferred()
 29.1142 +                self._expect_data(player_id, TEXT, l)
 29.1143 +                l.addCallbacks(lambda x: long(x), self.error_handler)
 29.1144 +                return l
 29.1145 +
 29.1146 +            def defer_value(l):
 29.1147 +                d = Deferred()
 29.1148 +                d.callback(l)
 29.1149 +                return d
 29.1150 +
 29.1151 +            def check((ais, bis, cis, alpha_randomness, dijs), alphas, gammas):
 29.1152 +                """So if B receives ai, bi, dij, ri, si, and the
 29.1153 +                randomness used in the computation of alpha, he then
 29.1154 +                checks that:
 29.1155 +
 29.1156 +                1) the alpha_i he received is equals to the encryption
 29.1157 +                   of ai and the commitment he received, Ai, is equal
 29.1158 +                   to the commitment of ai and ri
 29.1159 +
 29.1160 +                2) the commitment he received, Bj, is equal to the
 29.1161 +                   commitment of bj and sj
 29.1162 +
 29.1163 +                3) the gammaij he received is equal to the gammaij he
 29.1164 +                   now computes based on the values he reveives
 29.1165 +
 29.1166 +                4) a, b, c is a triple, a * b = c
 29.1167 +
 29.1168 +                5) ai, bi < p and dij < p^3
 29.1169 +                """
 29.1170 +                a = 0
 29.1171 +                a_rho1 = 0
 29.1172 +                a_rho2 = 0
 29.1173 +                b = 0
 29.1174 +                b_rho1 = 0
 29.1175 +                b_rho2 = 0
 29.1176 +                c = 0
 29.1177 +                c_rho1 = 0
 29.1178 +                c_rho2 = 0
 29.1179 +
 29.1180 +                for x in xrange(len(ais)):
 29.1181 +                    (ai, a_rhoi1, a_rhoi2, A) = ais[x]
 29.1182 +                    (bi, b_rhoi1, b_rhoi2, B) = bis[x]
 29.1183 +                    (ci, c_rhoi1, c_rhoi2, C) = cis[x]
 29.1184 +                    # 5) ai, bi < p...
 29.1185 +                    if ai >= field.modulus:
 29.1186 +                        raise OrlandiException("Inconsistent share ai, ai >= p: %i" % ai)
 29.1187 +                    if bi >= field.modulus:
 29.1188 +                        raise OrlandiException("Inconsistent share bi, bi >= p: %i" % bi)
 29.1189 +                    a += ai
 29.1190 +                    a_rho1 += a_rhoi1
 29.1191 +                    a_rho2 += a_rhoi2
 29.1192 +                    b += bi
 29.1193 +                    b_rho1 += b_rhoi1
 29.1194 +                    b_rho2 += b_rhoi2
 29.1195 +                    c += ci
 29.1196 +                    c_rho1 += c_rhoi1
 29.1197 +                    c_rho2 += c_rhoi2
 29.1198 +                    # 1) the alpha_i he received is equals to the encryption of ai...
 29.1199 +                    alphai = encrypt_r(ai.value, alpha_randomness[x],
 29.1200 +                                       self.players[x + 1].pubkey)
 29.1201 +                    if not(alphas[x] == alphai):
 29.1202 +                        raise OrlandiException("Inconsistent alpha from player %i, %i, %i" % (x + 1, alphas[x], alphai))
 29.1203 +
 29.1204 +                A1 = commitment.commit(a.value, a_rho1.value, a_rho2.value)
 29.1205 +                B1 = commitment.commit(b.value, b_rho1.value, b_rho2.value)
 29.1206 +                C1 = commitment.commit(c.value, c_rho1.value, c_rho2.value)
 29.1207 +
 29.1208 +                # 1) ... and the commitment he received, Ai, is equal
 29.1209 +                # to the commitment of ai and ri.
 29.1210 +                if A1 != A:
 29.1211 +                    raise OrlandiException("Inconsistent commitment for value %s, found %s expected %s." % (a, A1, A))
 29.1212 +                # 2) the commitment he received, Bj, is equal to the
 29.1213 +                # commitment of bj and sj.
 29.1214 +                if B1 != B:
 29.1215 +                    raise OrlandiException("Inconsistent commitment for value %s, found %s expected %s." % (b, B1, B))
 29.1216 +                if C1 != C:
 29.1217 +                    raise OrlandiException("Inconsistent commitment for value %s, found %s expected %s." % (c, C1, C))
 29.1218 +                # 4) a, b, c is a triple, a * b = c
 29.1219 +                if a * b != c:
 29.1220 +                    raise OrlandiException("Inconsistent triple, %i * %i does not equals %i." % (a, b, c))
 29.1221 +
 29.1222 +
 29.1223 +                # 3) the gammaij he received is equal to the gammaij
 29.1224 +                # he now computes based on the values he reveives
 29.1225 +                for j in xrange(len(ais)):
 29.1226 +                    n = self.players[self.id].pubkey[0]
 29.1227 +                    nsq = n * n
 29.1228 +                    dij = dijs[j]
 29.1229 +                    # 5) ... and dij < p^3.
 29.1230 +                    if dij >= (field.modulus**3):
 29.1231 +                        raise OrlandiException("Inconsistent random value dij %i from player %i" % (dij, j + 1))
 29.1232 +                    # Enc_ek_i(1;1)^d_ij
 29.1233 +                    enc = encrypt_r(1, 1, self.players[self.id].pubkey)
 29.1234 +                    t1 = pow(enc, dij.value, nsq)
 29.1235 +                    # alpha_i^b_j.
 29.1236 +                    t2 = pow(alphas[self.id - 1], bis[j][0].value, nsq)
 29.1237 +                    # gamma_ij = alpha_i^b_j Enc_ek_i(1;1)^d_ij
 29.1238 +                    gammaij = (t2) * (t1) % nsq
 29.1239 +                    if gammaij != gammas[j]:
 29.1240 +                        raise OrlandiException("Inconsistent gammaij, %i, %i" % (gammaij, gammas[j]))
 29.1241 +
 29.1242 +                return True
 29.1243 +
 29.1244 +            dls_all = []
 29.1245 +            for (a, b, c, (alphas, alpha_randomness, gammas, dijs)) in T:
 29.1246 +                ds_a = [None] * len(self.players)
 29.1247 +                ds_b = [None] * len(self.players)
 29.1248 +                ds_c = [None] * len(self.players)
 29.1249 +                ds_alpha_randomness = [None] * len(self.players)
 29.1250 +                ds_dijs = [None] * len(self.players)
 29.1251 +                pc = tuple(self.program_counter)
 29.1252 +
 29.1253 +                for player_id in xrange(1, len(self.players.keys()) + 1):
 29.1254 +                    if player_id == self.id:
 29.1255 +                        ds_a[player_id - 1] = defer_share(a.share, a.rho, a.commitment)
 29.1256 +                        ds_b[player_id - 1] = defer_share(b.share, b.rho, b.commitment)
 29.1257 +                        ds_c[player_id - 1] = defer_share(c.share, c.rho, c.commitment)
 29.1258 +                        ds_alpha_randomness[player_id - 1] = defer_value(alpha_randomness)
 29.1259 +                        ds_dijs[player_id - 1] = defer_value(dijs[player_id - 1])
 29.1260 +                    # Receive and recombine shares if this player is a
 29.1261 +                    # receiver.
 29.1262 +                    else:
 29.1263 +                        send_share(player_id, pc, a)
 29.1264 +                        send_share(player_id, pc, b)
 29.1265 +                        send_share(player_id, pc, c)
 29.1266 +                        send_long(player_id, pc, alpha_randomness)
 29.1267 +                        self.protocols[player_id].sendShare(pc, dijs[player_id - 1])
 29.1268 +
 29.1269 +                        ds_a[player_id - 1] = receive_shares(player_id)
 29.1270 +                        ds_b[player_id - 1] = receive_shares(player_id)
 29.1271 +                        ds_c[player_id - 1] = receive_shares(player_id)
 29.1272 +                        ds_alpha_randomness[player_id - 1] = receive_long(player_id)
 29.1273 +                        ds_dijs[player_id - 1] = self._expect_share(player_id, field)
 29.1274 +                dls_a = gatherResults(ds_a)
 29.1275 +                dls_b = gatherResults(ds_b)
 29.1276 +                dls_c = gatherResults(ds_c)
 29.1277 +                dls_dijs = gatherResults(ds_dijs)
 29.1278 +                dls_alpha_randomness = gatherResults(ds_alpha_randomness)
 29.1279 +
 29.1280 +            dls = gatherResults([dls_a, dls_b, dls_c, dls_alpha_randomness, dls_dijs])
 29.1281 +            dls.addCallbacks(check, self.error_handler, callbackArgs=[alphas, gammas])
 29.1282 +            dls_all.append(dls)
 29.1283 +
 29.1284 +            def result(x):
 29.1285 +                ls = []
 29.1286 +                for a, b, c, _ in M_without_test_set:
 29.1287 +                    ls.append((a, b, c))
 29.1288 +                return ls
 29.1289 +
 29.1290 +            dls_all = gatherResults(dls_all)
 29.1291 +            dls_all.addCallbacks(result, self.error_handler)
 29.1292 +            return dls_all
 29.1293 +
 29.1294 +        def step6(M_without_test_set):
 29.1295 +            """Partition M without test_set in quantity random subsets
 29.1296 +            M_i of size (2d + 1).
 29.1297 +            """
 29.1298 +            subsets = []
 29.1299 +            size = 2 * self.d + 1
 29.1300 +            for x in xrange(quantity):
 29.1301 +                subsets.append([])
 29.1302 +
 29.1303 +            def put_in_set(v, M_without_test_set, subsets):
 29.1304 +                if 0 == len(M_without_test_set):
 29.1305 +                    return subsets
 29.1306 +                v = v.value % quantity
 29.1307 +                if size > len(subsets[v]):
 29.1308 +                    subsets[v].append(M_without_test_set.pop(0))
 29.1309 +                r = self.random_share(field)
 29.1310 +                r = self.output(r)
 29.1311 +                self.schedule_callback(r, put_in_set, M_without_test_set, subsets)
 29.1312 +                r.addErrback(self.error_handler)
 29.1313 +                return r
 29.1314 +            r = self.random_share(field)
 29.1315 +            r = self.output(r)
 29.1316 +            self.schedule_callback(r, put_in_set, M_without_test_set, subsets)
 29.1317 +            r.addErrback(self.error_handler)
 29.1318 +            return r
 29.1319 +
 29.1320 +
 29.1321 +        def step7(Msets):
 29.1322 +            """For i = 1,...,M do:
 29.1323 +            a) [a] <- Fpp(rand,...), [b] <- Fpp(rand,...)
 29.1324 +            b) [r] <- Fpp(rand,...),
 29.1325 +            c) [c] <- LTMUL([a], [b], M_i)
 29.1326 +            d) Open([c] + [r])
 29.1327 +            """
 29.1328 +            ds = []
 29.1329 +            for Mi in Msets:
 29.1330 +                a = self.random_share(field)
 29.1331 +                b = self.random_share(field)
 29.1332 +                r = self.random_share(field)
 29.1333 +                c = self.leak_tolerant_mul(a, b, Mi)
 29.1334 +                d = self.open(c + r)
 29.1335 +                def return_abc(x, a, b, c):
 29.1336 +                    return a, b, c
 29.1337 +                d.addCallbacks(return_abc, self.error_handler, callbackArgs=(a, b, c))
 29.1338 +                ds.append(d)
 29.1339 +            result = gather_shares(ds)
 29.1340 +            def triples(ls):
 29.1341 +                return ls
 29.1342 +            result.addCallbacks(triples, self.error_handler)
 29.1343 +            return result
 29.1344 +
 29.1345 +        result = gatherResults(M)
 29.1346 +        self.schedule_callback(result, step3)
 29.1347 +        result.addErrback(self.error_handler)
 29.1348 +        self.schedule_callback(result, step45)
 29.1349 +        self.schedule_callback(result, step6)
 29.1350 +        self.schedule_callback(result, step7)
 29.1351 +
 29.1352 +        # do actual communication
 29.1353 +        self.activate_reactor()
 29.1354 +
 29.1355 +        s = Share(self, field)
 29.1356 +        # We add the result to the chains in result.
 29.1357 +        result.chainDeferred(s)
 29.1358 +
 29.1359 +        return quantity, s
 29.1360 +
 29.1361 +    def error_handler(self, ex):
 29.1362 +        print "Error: ", ex
 29.1363 +        return ex
 29.1364 +
 29.1365 +    def set_args(self, args):
 29.1366 +        """args is a dictionary."""
 29.1367 +        self.s = args['s']
 29.1368 +        self.d = args['d']
 29.1369 +        self.s_lambda = args['lambda']
    30.1 --- a/viff/paillier.py	Thu Oct 22 19:38:31 2009 +0200
    30.2 +++ b/viff/paillier.py	Fri Oct 23 13:50:19 2009 +0200
    30.3 @@ -27,8 +27,8 @@
    30.4  from twisted.internet.defer import Deferred, gatherResults
    30.5  import gmpy
    30.6  
    30.7 -from viff.runtime import Runtime, increment_pc, Share, gather_shares
    30.8 -from viff.runtime import PAILLIER
    30.9 +from viff.runtime import Runtime, Share, gather_shares
   30.10 +from viff.constants import PAILLIER
   30.11  from viff.util import rand, find_random_prime
   30.12  
   30.13  def L(u, n):
   30.14 @@ -78,7 +78,6 @@
   30.15          else:
   30.16              self.peer = player
   30.17  
   30.18 -    @increment_pc
   30.19      def prss_share_random(self, field):
   30.20          """Generate a share of a uniformly random element."""
   30.21          prfs = self.players[self.id].prfs(field.modulus)
   30.22 @@ -94,13 +93,15 @@
   30.23          """
   30.24          return self.share(inputters, field, number)
   30.25  
   30.26 -    @increment_pc
   30.27      def share(self, inputters, field, number=None):
   30.28          """Share *number* additively."""
   30.29          assert number is None or self.id in inputters
   30.30  
   30.31          results = []
   30.32          for peer_id in inputters:
   30.33 +            # Unique program counter per input.
   30.34 +            self.increment_pc()
   30.35 +
   30.36              if peer_id == self.id:
   30.37                  a = field(rand.randint(0, field.modulus - 1))
   30.38                  b = number - a
   30.39 @@ -121,7 +122,6 @@
   30.40      def output(self, share, receivers=None):
   30.41          return self.open(share, receivers)
   30.42  
   30.43 -    @increment_pc
   30.44      def open(self, share, receivers=None):
   30.45          """Open *share* to *receivers* (defaults to both players)."""
   30.46  
    31.1 --- a/viff/passive.py	Thu Oct 22 19:38:31 2009 +0200
    31.2 +++ b/viff/passive.py	Fri Oct 23 13:50:19 2009 +0200
    31.3 @@ -22,8 +22,7 @@
    31.4  import operator
    31.5  
    31.6  from viff import shamir
    31.7 -from viff.runtime import Runtime, increment_pc, Share, ShareList, \
    31.8 -     gather_shares, preprocess
    31.9 +from viff.runtime import Runtime, Share, ShareList, gather_shares, preprocess
   31.10  from viff.prss import prss, prss_lsb, prss_zero, prss_multi
   31.11  from viff.field import GF256, FieldElement
   31.12  from viff.util import rand, profile
   31.13 @@ -57,7 +56,6 @@
   31.14      def output(self, share, receivers=None, threshold=None):
   31.15          return self.open(share, receivers, threshold)
   31.16  
   31.17 -    @increment_pc
   31.18      def open(self, share, receivers=None, threshold=None):
   31.19          """Open a secret sharing.
   31.20  
   31.21 @@ -175,7 +173,6 @@
   31.22          return result
   31.23  
   31.24      @profile
   31.25 -    @increment_pc
   31.26      def mul(self, share_a, share_b):
   31.27          """Multiplication of shares.
   31.28  
   31.29 @@ -232,7 +229,6 @@
   31.30          else:
   31.31              return share * (share ** (exponent-1))
   31.32  
   31.33 -    @increment_pc
   31.34      def xor(self, share_a, share_b):
   31.35          field = share_a.field
   31.36          if not isinstance(share_b, Share):
   31.37 @@ -245,7 +241,18 @@
   31.38          else:
   31.39              return share_a + share_b - 2 * share_a * share_b
   31.40  
   31.41 -    @increment_pc
   31.42 +    def prss_key(self):
   31.43 +        """Create unique key for PRSS.
   31.44 +
   31.45 +        This increments the program counter and returns it as a tuple.
   31.46 +        Each straight-line program (typically a callback attached to
   31.47 +        some :class:`Deferred`) is executed in a context with unique
   31.48 +        starting program counter. This ensures that consequetive calls
   31.49 +        to PRSS-related methods will use unique program counters.
   31.50 +        """
   31.51 +        self.increment_pc()
   31.52 +        return tuple(self.program_counter)
   31.53 +
   31.54      def prss_share(self, inputters, field, element=None):
   31.55          """Creates pseudo-random secret sharings.
   31.56  
   31.57 @@ -273,7 +280,7 @@
   31.58          n = self.num_players
   31.59  
   31.60          # Key used for PRSS.
   31.61 -        key = tuple(self.program_counter)
   31.62 +        key = self.prss_key()
   31.63  
   31.64          # The shares for which we have all the keys.
   31.65          all_shares = []
   31.66 @@ -314,7 +321,6 @@
   31.67          else:
   31.68              return result
   31.69  
   31.70 -    @increment_pc
   31.71      def prss_share_random(self, field, binary=False):
   31.72          """Generate shares of a uniformly random element from the field given.
   31.73  
   31.74 @@ -329,7 +335,7 @@
   31.75              modulus = field.modulus
   31.76  
   31.77          # Key used for PRSS.
   31.78 -        prss_key = tuple(self.program_counter)
   31.79 +        prss_key = self.prss_key()
   31.80          prfs = self.players[self.id].prfs(modulus)
   31.81          share = prss(self.num_players, self.id, field, prfs, prss_key)
   31.82  
   31.83 @@ -354,7 +360,6 @@
   31.84          self.schedule_callback(result, finish, share, binary)
   31.85          return result
   31.86  
   31.87 -    @increment_pc
   31.88      def prss_share_random_multi(self, field, quantity, binary=False):
   31.89          """Does the same as calling *quantity* times :meth:`prss_share_random`,
   31.90          but with less calls to the PRF. Sampling of a binary element is only
   31.91 @@ -371,13 +376,12 @@
   31.92              modulus = field.modulus
   31.93  
   31.94          # Key used for PRSS.
   31.95 -        prss_key = tuple(self.program_counter)
   31.96 +        prss_key = self.prss_key()
   31.97          prfs = self.players[self.id].prfs(modulus ** quantity)
   31.98          shares = prss_multi(self.num_players, self.id, field, prfs, prss_key,
   31.99                              modulus, quantity)
  31.100          return [Share(self, field, share) for share in shares]
  31.101  
  31.102 -    @increment_pc
  31.103      def prss_share_zero(self, field, quantity):
  31.104          """Generate *quantity* shares of the zero element from the
  31.105          field given.
  31.106 @@ -385,13 +389,12 @@
  31.107          Communication cost: none.
  31.108          """
  31.109          # Key used for PRSS.
  31.110 -        prss_key = tuple(self.program_counter)
  31.111 +        prss_key = self.prss_key()
  31.112          prfs = self.players[self.id].prfs(field.modulus)
  31.113          zero_share = prss_zero(self.num_players, self.threshold, self.id,
  31.114                                 field, prfs, prss_key, quantity)
  31.115          return [Share(self, field, zero_share[i]) for i in range(quantity)]
  31.116  
  31.117 -    @increment_pc
  31.118      def prss_double_share(self, field, quantity):
  31.119          """Make *quantity* double-sharings using PRSS.
  31.120  
  31.121 @@ -402,7 +405,6 @@
  31.122          z_2t = self.prss_share_zero(field, quantity)
  31.123          return (r_t, [r_t[i] + z_2t[i] for i in range(quantity)])
  31.124  
  31.125 -    @increment_pc
  31.126      def prss_share_bit_double(self, field):
  31.127          """Share a random bit over *field* and GF256.
  31.128  
  31.129 @@ -414,7 +416,7 @@
  31.130          n = self.num_players
  31.131          k = self.options.security_parameter
  31.132          prfs = self.players[self.id].prfs(2**k)
  31.133 -        prss_key = tuple(self.program_counter)
  31.134 +        prss_key = self.prss_key()
  31.135  
  31.136          b_p = self.prss_share_random(field, binary=True)
  31.137          r_p, r_lsb = prss_lsb(n, self.id, field, prfs, prss_key)
  31.138 @@ -427,13 +429,12 @@
  31.139          # Use r_lsb to flip b as needed.
  31.140          return (b_p, b ^ r_lsb)
  31.141  
  31.142 -    @increment_pc
  31.143      def prss_shamir_share_bit_double(self, field):
  31.144          """Shamir share a random bit over *field* and GF256."""
  31.145          n = self.num_players
  31.146          k = self.options.security_parameter
  31.147          prfs = self.players[self.id].prfs(2**k)
  31.148 -        prss_key = tuple(self.program_counter)
  31.149 +        prss_key = self.prss_key()
  31.150          inputters = range(1, self.num_players + 1)
  31.151  
  31.152          ri = rand.randint(0, 2**k - 1)
  31.153 @@ -461,7 +462,6 @@
  31.154              result.append(share)
  31.155          return result
  31.156  
  31.157 -    @increment_pc
  31.158      @preprocess("prss_powerchains")
  31.159      def prss_powerchain(self, max=7):
  31.160          """Generate a random secret share in GF256 and returns
  31.161 @@ -472,6 +472,7 @@
  31.162      def prss_powerchains(self, max=7, quantity=20):
  31.163          """Does *quantity* times the same as :meth:`prss_powerchain`.
  31.164          Used for preprocessing."""
  31.165 +        quantity = min(quantity, 20)
  31.166          shares = self.prss_share_random_multi(GF256, quantity)
  31.167          return [gatherResults(self.powerchain(share, max)) for share in shares]
  31.168  
  31.169 @@ -482,7 +483,6 @@
  31.170          """
  31.171          return self.shamir_share(inputters, field, number, threshold)
  31.172  
  31.173 -    @increment_pc
  31.174      def shamir_share(self, inputters, field, number=None, threshold=None):
  31.175          """Secret share *number* over *field* using Shamir's method.
  31.176  
  31.177 @@ -525,6 +525,9 @@
  31.178  
  31.179          results = []
  31.180          for peer_id in inputters:
  31.181 +            # Unique program counter per input.
  31.182 +            self.increment_pc()
  31.183 +
  31.184              if peer_id == self.id:
  31.185                  pc = tuple(self.program_counter)
  31.186                  shares = shamir.share(field(number), threshold,
    32.1 --- a/viff/prss.py	Thu Oct 22 19:38:31 2009 +0200
    32.2 +++ b/viff/prss.py	Fri Oct 23 13:50:19 2009 +0200
    32.3 @@ -40,9 +40,6 @@
    32.4  `Download <http://www.cs.technion.ac.il/~yuvali/pubs/CDI05.ps>`__.
    32.5  """
    32.6  
    32.7 -__docformat__ = "restructuredtext"
    32.8 -
    32.9 -
   32.10  import sha
   32.11  from math import ceil
   32.12  from binascii import hexlify
    33.1 --- a/viff/reactor.py	Thu Oct 22 19:38:31 2009 +0200
    33.2 +++ b/viff/reactor.py	Fri Oct 23 13:50:19 2009 +0200
    33.3 @@ -19,8 +19,6 @@
    33.4  
    33.5  """VIFF reactor to have control over the scheduling."""
    33.6  
    33.7 -__docformat__ = "restructuredtext"
    33.8 -
    33.9  from twisted.internet.selectreactor import SelectReactor
   33.10  
   33.11  
   33.12 @@ -42,7 +40,7 @@
   33.13          self.runUntilCurrent()
   33.14          t2 = self.timeout()
   33.15  
   33.16 -        if (t2 is not None):
   33.17 +        if t2 is not None:
   33.18              t = min(t, self.running and t2)
   33.19  
   33.20          SelectReactor.doIteration(self, t)
    34.1 --- a/viff/runtime.py	Thu Oct 22 19:38:31 2009 +0200
    34.2 +++ b/viff/runtime.py	Fri Oct 23 13:50:19 2009 +0200
    34.3 @@ -31,16 +31,16 @@
    34.4  """
    34.5  from __future__ import division
    34.6  
    34.7 -__docformat__ = "restructuredtext"
    34.8 -
    34.9  import time
   34.10  import struct
   34.11  from optparse import OptionParser, OptionGroup
   34.12  from collections import deque
   34.13  import os
   34.14 +import sys
   34.15  
   34.16  from viff.field import GF256, FieldElement
   34.17  from viff.util import wrapper, rand, deep_wait, track_memory_usage, begin, end
   34.18 +from viff.constants import SHARE
   34.19  import viff.reactor
   34.20  
   34.21  from twisted.internet import reactor
   34.22 @@ -51,13 +51,6 @@
   34.23  from twisted.internet.protocol import ReconnectingClientFactory, ServerFactory
   34.24  from twisted.protocols.basic import Int16StringReceiver
   34.25  
   34.26 -# Constants used by ShareExchanger.
   34.27 -SHARE    = 0
   34.28 -ECHO     = 1
   34.29 -READY    = 2
   34.30 -SEND     = 3
   34.31 -PAILLIER = 4
   34.32 -
   34.33  
   34.34  class Share(Deferred):
   34.35      """A shared number.
   34.36 @@ -382,6 +375,65 @@
   34.37          """Disconnect this protocol instance."""
   34.38          self.transport.loseConnection()
   34.39  
   34.40 +class SelfShareExchanger(ShareExchanger):
   34.41 +
   34.42 +    def __init__(self, id, factory):
   34.43 +        ShareExchanger.__init__(self)
   34.44 +        self.peer_id = id
   34.45 +        self.factory = factory
   34.46 +
   34.47 +    def stringReceived(self, program_counter, data_type, data):
   34.48 +        """Called when a share is received.
   34.49 +
   34.50 +        The string received is unpacked into the program counter, and
   34.51 +        a data part. The data is passed the appropriate Deferred in
   34.52 +        :class:`self.incoming_data`.
   34.53 +        """
   34.54 +        try:
   34.55 +            key = (program_counter, data_type)
   34.56 +                         
   34.57 +            if key in self.waiting_deferreds:
   34.58 +                deq = self.waiting_deferreds[key]
   34.59 +                deferred = deq.popleft()
   34.60 +                if not deq:
   34.61 +                    del self.waiting_deferreds[key]
   34.62 +                self.factory.runtime.handle_deferred_data(deferred, data)
   34.63 +            else:
   34.64 +                deq = self.incoming_data.setdefault(key, deque())
   34.65 +                deq.append(data)
   34.66 +        except struct.error, e:
   34.67 +            self.factory.runtime.abort(self, e)
   34.68 +
   34.69 +    def sendData(self, program_counter, data_type, data):
   34.70 +        """Send data to the self.id."""
   34.71 +        self.stringReceived(program_counter, data_type, data)
   34.72 +
   34.73 +    def loseConnection(self):
   34.74 +        """Disconnect this protocol instance."""
   34.75 +        self.lost_connection.callback(self)
   34.76 +        return None
   34.77 +
   34.78 +
   34.79 +class SelfShareExchangerFactory(ReconnectingClientFactory, ServerFactory):
   34.80 +    """Factory for creating SelfShareExchanger protocols."""
   34.81 +
   34.82 +    protocol = SelfShareExchanger
   34.83 +    maxDelay = 3
   34.84 +    factor = 1.234567 # About half of the Twisted default
   34.85 +
   34.86 +    def __init__(self, runtime):
   34.87 +        """Initialize the factory."""
   34.88 +        self.runtime = runtime
   34.89 +
   34.90 +    def identify_peer(self, protocol):
   34.91 +        raise Exception("Is identify_peer necessary?")
   34.92 +
   34.93 +    def clientConnectionLost(self, connector, reason):
   34.94 +        reason.trap(ConnectionDone)
   34.95 +
   34.96 +class FakeTransport(object):
   34.97 +    def close(self):
   34.98 +        return True
   34.99  
  34.100  class ShareExchangerFactory(ReconnectingClientFactory, ServerFactory):
  34.101      """Factory for creating ShareExchanger protocols."""
  34.102 @@ -407,25 +459,6 @@
  34.103          reason.trap(ConnectionDone)
  34.104  
  34.105  
  34.106 -def increment_pc(method):
  34.107 -    """Make *method* automatically increment the program counter.
  34.108 -
  34.109 -    Adding this decorator to a :class:`Runtime` method will ensure
  34.110 -    that the program counter is incremented correctly when entering
  34.111 -    the method.
  34.112 -    """
  34.113 -
  34.114 -    @wrapper(method)
  34.115 -    def inc_pc_wrapper(self, *args, **kwargs):
  34.116 -        try:
  34.117 -            self.program_counter[-1] += 1
  34.118 -            self.program_counter.append(0)
  34.119 -            return method(self, *args, **kwargs)
  34.120 -        finally:
  34.121 -            self.program_counter.pop()
  34.122 -    return inc_pc_wrapper
  34.123 -
  34.124 -
  34.125  def preprocess(generator):
  34.126      """Track calls to this method.
  34.127  
  34.128 @@ -444,6 +477,7 @@
  34.129  
  34.130          @wrapper(method)
  34.131          def preprocess_wrapper(self, *args, **kwargs):
  34.132 +            self.increment_pc()
  34.133              pc = tuple(self.program_counter)
  34.134              try:
  34.135                  return self._pool.pop(pc)
  34.136 @@ -451,7 +485,11 @@
  34.137                  key = (generator, args)
  34.138                  pcs = self._needed_data.setdefault(key, [])
  34.139                  pcs.append(pc)
  34.140 -                return method(self, *args, **kwargs)
  34.141 +                self.fork_pc()
  34.142 +                try:
  34.143 +                    return method(self, *args, **kwargs)
  34.144 +                finally:
  34.145 +                    self.unfork_pc()
  34.146  
  34.147          return preprocess_wrapper
  34.148      return preprocess_decorator
  34.149 @@ -554,7 +592,9 @@
  34.150          self.players = {}
  34.151          # Add ourselves, but with no protocol since we wont be
  34.152          # communicating with ourselves.
  34.153 -        self.add_player(player, None)
  34.154 +        protocol = SelfShareExchanger(self.id, SelfShareExchangerFactory(self))
  34.155 +        protocol.transport = FakeTransport()
  34.156 +        self.add_player(player, protocol)
  34.157  
  34.158          #: Queue of deferreds and data.
  34.159          self.deferred_queue = deque()
  34.160 @@ -564,15 +604,15 @@
  34.161          #: Record the recursion depth.
  34.162          self.depth_counter = 0
  34.163          self.max_depth = 0
  34.164 +        #: Recursion depth limit by experiment, including security margin.
  34.165 +        self.depth_limit = int(sys.getrecursionlimit() / 50)
  34.166          #: Use deferred queues only if the ViffReactor is running.
  34.167          self.using_viff_reactor = isinstance(reactor, viff.reactor.ViffReactor)
  34.168  
  34.169      def add_player(self, player, protocol):
  34.170          self.players[player.id] = player
  34.171          self.num_players = len(self.players)
  34.172 -        # There is no protocol for ourselves, so we wont add that:
  34.173 -        if protocol is not None:
  34.174 -            self.protocols[player.id] = protocol
  34.175 +        self.protocols[player.id] = protocol
  34.176  
  34.177      def shutdown(self):
  34.178          """Shutdown the runtime.
  34.179 @@ -623,7 +663,18 @@
  34.180          dl = DeferredList(vars)
  34.181          self.schedule_callback(dl, lambda _: self.shutdown())
  34.182  
  34.183 -    @increment_pc
  34.184 +    def increment_pc(self):
  34.185 +        """Increment the program counter."""
  34.186 +        self.program_counter[-1] += 1
  34.187 +
  34.188 +    def fork_pc(self):
  34.189 +        """Fork the program counter."""
  34.190 +        self.program_counter.append(0)
  34.191 +
  34.192 +    def unfork_pc(self):
  34.193 +        """Leave a fork of the program counter."""
  34.194 +        self.program_counter.pop()
  34.195 +
  34.196      def schedule_callback(self, deferred, func, *args, **kwargs):
  34.197          """Schedule a callback on a deferred with the correct program
  34.198          counter.
  34.199 @@ -637,6 +688,7 @@
  34.200          Any extra arguments are passed to the callback as with
  34.201          :meth:`addCallback`.
  34.202          """
  34.203 +        self.increment_pc()
  34.204          saved_pc = self.program_counter[:]
  34.205  
  34.206          @wrapper(func)
  34.207 @@ -645,6 +697,7 @@
  34.208              try:
  34.209                  current_pc = self.program_counter[:]
  34.210                  self.program_counter[:] = saved_pc
  34.211 +                self.fork_pc()
  34.212                  return func(*args, **kwargs)
  34.213              finally:
  34.214                  self.program_counter[:] = current_pc
  34.215 @@ -673,7 +726,6 @@
  34.216          deferred.addCallback(queue_callback, self, fork)
  34.217          return self.schedule_callback(fork, func, *args, **kwargs)
  34.218  
  34.219 -    @increment_pc
  34.220      def synchronize(self):
  34.221          """Introduce a synchronization point.
  34.222  
  34.223 @@ -682,6 +734,7 @@
  34.224          adding callbacks to the returned :class:`Deferred`, one can
  34.225          divide a protocol execution into disjoint phases.
  34.226          """
  34.227 +        self.increment_pc()
  34.228          shares = [self._exchange_shares(player, GF256(0))
  34.229                    for player in self.players]
  34.230          result = gather_shares(shares)
  34.231 @@ -689,10 +742,12 @@
  34.232          return result
  34.233  
  34.234      def _expect_data(self, peer_id, data_type, deferred):
  34.235 -        assert peer_id != self.id, "Do not expect data from yourself!"
  34.236          # Convert self.program_counter to a hashable value in order to
  34.237          # use it as a key in self.protocols[peer_id].incoming_data.
  34.238          pc = tuple(self.program_counter)
  34.239 +        return self._expect_data_with_pc(pc, peer_id, data_type, deferred)
  34.240 +
  34.241 +    def _expect_data_with_pc(self, pc, peer_id, data_type, deferred):
  34.242          key = (pc, data_type)
  34.243  
  34.244          if key in self.protocols[peer_id].incoming_data:
  34.245 @@ -729,7 +784,6 @@
  34.246          self._expect_data(peer_id, SHARE, share)
  34.247          return share
  34.248  
  34.249 -    @increment_pc
  34.250      def preprocess(self, program):
  34.251          """Generate preprocess material.
  34.252  
  34.253 @@ -749,25 +803,37 @@
  34.254          example of a method fulfilling this interface.
  34.255          """
  34.256  
  34.257 -        def update(results, program_counters):
  34.258 +        def update(results, program_counters, start_time, count, what):
  34.259 +            stop = time.time()
  34.260 +
  34.261 +            print
  34.262 +            print "Total time used: %.3f sec" % (stop - start_time)
  34.263 +            print "Time per %s operation: %.0f ms" % (what, 1000*(stop - start_time) / count)
  34.264 +            print "*" * 6
  34.265 +
  34.266              # Update the pool with pairs of program counter and data.
  34.267              self._pool.update(zip(program_counters, results))
  34.268  
  34.269          wait_list = []
  34.270          for ((generator, args), program_counters) in program.iteritems():
  34.271              print "Preprocessing %s (%d items)" % (generator, len(program_counters))
  34.272 +            self.increment_pc()
  34.273 +            self.fork_pc()
  34.274              func = getattr(self, generator)
  34.275 +            count = 0
  34.276 +            start_time = time.time()
  34.277  
  34.278 -            block_size = 20
  34.279              while program_counters:
  34.280 -                results = []
  34.281 -                while len(results) < len(program_counters) and \
  34.282 -                          len(results) < block_size:
  34.283 -                    results += func(*args)
  34.284 +                count += 1
  34.285 +                self.increment_pc()
  34.286 +                self.fork_pc()
  34.287 +                results = func(quantity=len(program_counters), *args)
  34.288 +                self.unfork_pc()
  34.289                  ready = gatherResults(results)
  34.290 -                ready.addCallback(update, program_counters[:len(results)])
  34.291 +                ready.addCallback(update, program_counters[:len(results)], start_time, count, generator)
  34.292                  del program_counters[:len(results)]
  34.293                  wait_list.append(ready)
  34.294 +            self.unfork_pc()
  34.295          return gatherResults(wait_list)
  34.296  
  34.297      def input(self, inputters, field, number=None):
  34.298 @@ -779,7 +845,7 @@
  34.299          listed in *inputters*, then a :class:`Share` is given back
  34.300          directly.
  34.301          """
  34.302 -        raise NotImplemented("Override this abstract method in a subclass.")
  34.303 +        raise NotImplementedError
  34.304  
  34.305      def output(self, share, receivers=None):
  34.306          """Open *share* to *receivers* (defaults to all players).
  34.307 @@ -787,7 +853,7 @@
  34.308          Returns a :class:`Share` to players with IDs in *receivers*
  34.309          and :const:`None` to the remaining players.
  34.310          """
  34.311 -        raise NotImplemented("Override this abstract method in a subclass.")
  34.312 +        raise NotImplementedError
  34.313  
  34.314      def add(self, share_a, share_b):
  34.315          """Secure addition.
  34.316 @@ -795,7 +861,7 @@
  34.317          At least one of the arguments must be a :class:`Share`, the
  34.318          other can be a :class:`FieldElement` or a (possible long)
  34.319          Python integer."""
  34.320 -        raise NotImplemented("Override this abstract method in a subclass.")
  34.321 +        raise NotImplementedError
  34.322  
  34.323      def mul(self, share_a, share_b):
  34.324          """Secure multiplication.
  34.325 @@ -803,7 +869,7 @@
  34.326          At least one of the arguments must be a :class:`Share`, the
  34.327          other can be a :class:`FieldElement` or a (possible long)
  34.328          Python integer."""
  34.329 -        raise NotImplemented("Override this abstract method in a subclass.")
  34.330 +        raise NotImplementedError
  34.331  
  34.332      def handle_deferred_data(self, deferred, data):
  34.333          """Put deferred and data into the queue if the ViffReactor is running. 
  34.334 @@ -828,7 +894,7 @@
  34.335      def process_queue(self, queue):
  34.336          """Execute the callbacks of the deferreds in *queue*."""
  34.337  
  34.338 -        while(queue):
  34.339 +        while queue:
  34.340              deferred, data = queue.popleft()
  34.341              deferred.callback(data)
  34.342  
  34.343 @@ -850,13 +916,16 @@
  34.344              if self.depth_counter > self.max_depth:
  34.345                  # Record the maximal depth reached.
  34.346                  self.max_depth = self.depth_counter
  34.347 +                if self.depth_counter >= self.depth_limit:
  34.348 +                    print "Recursion depth limit reached."
  34.349  
  34.350 -            reactor.doIteration(0)
  34.351 +            if self.depth_counter < self.depth_limit:
  34.352 +                reactor.doIteration(0)
  34.353  
  34.354              self.depth_counter -= 1
  34.355              self.activation_counter = 0
  34.356  
  34.357 -    def print_transferred_data():
  34.358 +    def print_transferred_data(self):
  34.359          """Print the amount of transferred data for all connections."""
  34.360  
  34.361          for protocol in self.protocols.itervalues():
    35.1 --- a/viff/shamir.py	Thu Oct 22 19:38:31 2009 +0200
    35.2 +++ b/viff/shamir.py	Fri Oct 23 13:50:19 2009 +0200
    35.3 @@ -20,9 +20,6 @@
    35.4  (11): 612-613.
    35.5  """
    35.6  
    35.7 -__docformat__ = "restructuredtext"
    35.8 -
    35.9 -
   35.10  import operator
   35.11  from viff.util import rand, fake
   35.12  
    36.1 --- a/viff/test/test_basic_runtime.py	Thu Oct 22 19:38:31 2009 +0200
    36.2 +++ b/viff/test/test_basic_runtime.py	Fri Oct 23 13:50:19 2009 +0200
    36.3 @@ -18,7 +18,6 @@
    36.4  from twisted.internet.defer import Deferred, gatherResults
    36.5  
    36.6  from viff.test.util import RuntimeTestCase, protocol
    36.7 -from viff.runtime import increment_pc
    36.8  
    36.9  
   36.10  class ProgramCounterTest(RuntimeTestCase):
   36.11 @@ -29,31 +28,18 @@
   36.12          self.assertEquals(runtime.program_counter, [0])
   36.13  
   36.14      @protocol
   36.15 -    def test_simple_operation(self, runtime):
   36.16 -        """Test an operation which makes no further calls.
   36.17 +    def test_synchronize(self, runtime):
   36.18 +        """Test whether synchronize increases the program counter.
   36.19  
   36.20 -        Each call should increment the program counter by one.
   36.21 -        """
   36.22 +        Every synchronize operation should have its unique program
   36.23 +        counter."""
   36.24 +        self.assertEquals(runtime.program_counter, [0])
   36.25          runtime.synchronize()
   36.26          self.assertEquals(runtime.program_counter, [1])
   36.27          runtime.synchronize()
   36.28          self.assertEquals(runtime.program_counter, [2])
   36.29  
   36.30      @protocol
   36.31 -    def test_complex_operation(self, runtime):
   36.32 -        """Test an operation which makes nested calls.
   36.33 -
   36.34 -        This verifies that the program counter is only incremented by
   36.35 -        one, even for a complex operation.
   36.36 -        """
   36.37 -        # Exclusive-or is calculated as x + y - 2 * x * y, so add,
   36.38 -        # sub, and mul are called.
   36.39 -        runtime.xor(self.Zp(0), self.Zp(1))
   36.40 -        self.assertEquals(runtime.program_counter, [1])
   36.41 -        runtime.xor(self.Zp(0), self.Zp(1))
   36.42 -        self.assertEquals(runtime.program_counter, [2])
   36.43 -
   36.44 -    @protocol
   36.45      def test_callback(self, runtime):
   36.46          """Test a scheduled callback.
   36.47  
   36.48 @@ -62,62 +48,32 @@
   36.49          """
   36.50  
   36.51          def verify_program_counter(_):
   36.52 +            # The callback is run with its own sub-program counter.
   36.53              self.assertEquals(runtime.program_counter, [1, 0])
   36.54  
   36.55          d = Deferred()
   36.56 +
   36.57 +        self.assertEquals(runtime.program_counter, [0])
   36.58 +
   36.59 +        # Scheduling a callback increases the program counter.
   36.60          runtime.schedule_callback(d, verify_program_counter)
   36.61 -
   36.62 -        runtime.synchronize()
   36.63 -        self.assertEquals(runtime.program_counter, [2])
   36.64 +        self.assertEquals(runtime.program_counter, [1])
   36.65  
   36.66          # Now trigger verify_program_counter.
   36.67          d.callback(None)
   36.68  
   36.69      @protocol
   36.70 -    def test_nested_calls(self, runtime):
   36.71 -        """Test Runtime methods that call other methods.
   36.72 -
   36.73 -        We create a couple of functions that are used as fake methods.
   36.74 -        """
   36.75 -
   36.76 -        @increment_pc
   36.77 -        def method_a(runtime):
   36.78 -            # First top-level call, so first entry is 1. No calls to
   36.79 -            # other methods decorated with increment_pc has been made,
   36.80 -            # so the second entry is 0.
   36.81 -            self.assertEquals(runtime.program_counter, [1, 0])
   36.82 -            method_b(runtime, 1)
   36.83 -
   36.84 -            self.assertEquals(runtime.program_counter, [1, 1])
   36.85 -            method_b(runtime, 2)
   36.86 -
   36.87 -            # At this point two sub-calls has been made:
   36.88 -            self.assertEquals(runtime.program_counter, [1, 2])
   36.89 -
   36.90 -        @increment_pc
   36.91 -        def method_b(runtime, count):
   36.92 -            # This method is called twice from method_a:
   36.93 -            self.assertEquals(runtime.program_counter, [1, count, 0])
   36.94 -
   36.95 -        # Zero top-level calls:
   36.96 -        self.assertEquals(runtime.program_counter, [0])
   36.97 -        method_a(runtime)
   36.98 -
   36.99 -        # One top-level call:
  36.100 -        self.assertEquals(runtime.program_counter, [1])
  36.101 -
  36.102 -    @protocol
  36.103      def test_multiple_callbacks(self, runtime):
  36.104  
  36.105          d1 = Deferred()
  36.106          d2 = Deferred()
  36.107  
  36.108          def verify_program_counter(_, count):
  36.109 -            self.assertEquals(runtime.program_counter, [1, count, 0])
  36.110 +            self.assertEquals(runtime.program_counter, [count, 0])
  36.111  
  36.112 -        @increment_pc
  36.113          def method_a(runtime):
  36.114 -            self.assertEquals(runtime.program_counter, [1, 0])
  36.115 +            # No calls to schedule_callback yet.
  36.116 +            self.assertEquals(runtime.program_counter, [0])
  36.117  
  36.118              runtime.schedule_callback(d1, verify_program_counter, 1)
  36.119              runtime.schedule_callback(d2, verify_program_counter, 2)
    37.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    37.2 +++ b/viff/test/test_hash_broadcast.py	Fri Oct 23 13:50:19 2009 +0200
    37.3 @@ -0,0 +1,180 @@
    37.4 +# Copyright 2009 VIFF Development Team.
    37.5 +#
    37.6 +# This file is part of VIFF, the Virtual Ideal Functionality Framework.
    37.7 +#
    37.8 +# VIFF is free software: you can redistribute it and/or modify it
    37.9 +# under the terms of the GNU Lesser General Public License (LGPL) as
   37.10 +# published by the Free Software Foundation, either version 3 of the
   37.11 +# License, or (at your option) any later version.
   37.12 +#
   37.13 +# VIFF is distributed in the hope that it will be useful, but WITHOUT
   37.14 +# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
   37.15 +# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
   37.16 +# Public License for more details.
   37.17 +#
   37.18 +# You should have received a copy of the GNU Lesser General Public
   37.19 +# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
   37.20 +
   37.21 +from twisted.internet.defer import Deferred, DeferredList
   37.22 +
   37.23 +from viff.test.util import RuntimeTestCase, protocol
   37.24 +from viff.field import GF
   37.25 +
   37.26 +from viff.comparison import Toft05Runtime
   37.27 +from viff.hash_broadcast import HashBroadcastMixin
   37.28 +
   37.29 +class BroadcastRuntime(Toft05Runtime, HashBroadcastMixin):
   37.30 +    """Mix of :class:`Toft05Runtime` and
   37.31 +    :class:`HashBroadcastRuntime`."""
   37.32 +    pass
   37.33 +
   37.34 +class HashBroadcastTest(RuntimeTestCase):
   37.35 +    """Test for the hash broadcast mixin."""
   37.36 +
   37.37 +    # Number of players.
   37.38 +    num_players = 3
   37.39 +
   37.40 +    runtime_class = BroadcastRuntime
   37.41 +
   37.42 +    timeout = 10
   37.43 +    @protocol
   37.44 +    def test_send(self, runtime):
   37.45 +        """Test of send a value."""
   37.46 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
   37.47 +
   37.48 +        value = 42
   37.49 +
   37.50 +        receivers = [2, 3]
   37.51 +        if 1 == runtime.id:
   37.52 +            d = runtime.broadcast([1], receivers, str(value))
   37.53 +        else:
   37.54 +            d = runtime.broadcast([1], receivers)
   37.55 +        def check(x):
   37.56 +            self.assertEquals(int(x), 42)
   37.57 +        d.addCallback(check)
   37.58 +        return d
   37.59 +            
   37.60 +
   37.61 +    @protocol
   37.62 +    def test_send_two_senders_in_parallel(self, runtime):
   37.63 +        """Test of send a value."""
   37.64 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
   37.65 +
   37.66 +        def check(ls):
   37.67 +            for s, x in ls:
   37.68 +                self.assertEquals(int(x), 42)
   37.69 +            return ls
   37.70 +
   37.71 +        value = 42
   37.72 +
   37.73 +        receivers = [2, 3]
   37.74 +        if 1 == runtime.id:
   37.75 +            d1 = runtime.broadcast([1], receivers, str(value))
   37.76 +        else:
   37.77 +            d1 = runtime.broadcast([1], receivers)
   37.78 +
   37.79 +        if 2 == runtime.id:
   37.80 +            d2 = runtime.broadcast([2], [3], str(value))
   37.81 +        else:
   37.82 +            d2 = runtime.broadcast([2], [3])
   37.83 +
   37.84 +        ds = [d1]
   37.85 +        if [] != d2:
   37.86 +            ds.append(d2)
   37.87 +        dls = DeferredList(ds)
   37.88 +        dls.addCallback(check)
   37.89 +        return dls
   37.90 +            
   37.91 +    @protocol
   37.92 +    def test_send_multiple_senders_in_one_burst(self, runtime):
   37.93 +        """Test of send a value."""
   37.94 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
   37.95 +
   37.96 +        value = 42
   37.97 +        if 1 == runtime.id:
   37.98 +            value = 7
   37.99 +
  37.100 +        if 1 == runtime.id or 3 == runtime.id:
  37.101 +            ds = runtime.broadcast([1, 3], [2], str(value))
  37.102 +
  37.103 +        if 2 == runtime.id:
  37.104 +            ds = runtime.broadcast([1, 3], [2])
  37.105 +            dls = DeferredList(ds)
  37.106 +            def check(ls):
  37.107 +                self.assertEquals(int(ls[0][1]), 7)
  37.108 +                self.assertEquals(int(ls[1][1]), 42)
  37.109 +                return ls
  37.110 +            dls.addCallback(check)
  37.111 +            return dls
  37.112 +        return None
  37.113 +            
  37.114 +
  37.115 +    @protocol
  37.116 +    def test_sender_in_receivers(self, runtime):
  37.117 +        """Test of send a value."""
  37.118 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  37.119 +
  37.120 +        value = 42
  37.121 +        if 1 == runtime.id:
  37.122 +            d = runtime.broadcast([1], [1, 2, 3], str(value))
  37.123 +        else:
  37.124 +            d = runtime.broadcast([1], [1, 2, 3])
  37.125 +
  37.126 +        def check(x):
  37.127 +            self.assertEquals(int(x), 42)
  37.128 +            return x
  37.129 +        d.addCallback(check)
  37.130 +        return d
  37.131 +
  37.132 +    @protocol
  37.133 +    def test_complex(self, runtime):
  37.134 +        def check(ls):
  37.135 +            for x, v in ls:
  37.136 +                self.assertEquals(runtime.list_str(v), ['7', '9', '13'])
  37.137 +            
  37.138 +        receivers = [1, 2, 3]
  37.139 +        def exchange((xi, rhoi1, rhoi2)):
  37.140 +            # Send share to all receivers.
  37.141 +            ds = runtime.broadcast(receivers, receivers, str((str(xi), str(rhoi1), str(rhoi2))))
  37.142 +            dls = DeferredList(ds)
  37.143 +            dls.addCallbacks(check, runtime.error_handler)
  37.144 +            return dls
  37.145 +
  37.146 +        result = Deferred()
  37.147 +        result.addCallbacks(exchange, runtime.error_handler)
  37.148 +        result.callback((7, 9, 13))
  37.149 +        return result
  37.150 +
  37.151 +    @protocol
  37.152 +    def test_complex2(self, runtime):
  37.153 +        def check(ls):
  37.154 +            if (2 == runtime.id) or (1 == runtime.id):
  37.155 +                self.assertEquals(ls[0][1], "V1")
  37.156 +                self.assertEquals(ls[1][1], "V1")
  37.157 +                self.assertEquals(ls[2][1], "V1")
  37.158 +                self.assertEquals(ls[3][1], "V2")
  37.159 +            else:
  37.160 +                self.assertEquals(ls[0][1], "V1")
  37.161 +                self.assertEquals(ls[1][1], "V1")
  37.162 +                self.assertEquals(ls[2][1], "V1")
  37.163 +                self.assertEquals(ls[3][1], "V2")
  37.164 +                self.assertEquals(ls[4][1], "V2")
  37.165 +        field = self.Zp
  37.166 +        results = []
  37.167 +        results += runtime.broadcast(runtime.players.keys(), runtime.players.keys(), "V1")
  37.168 +        if runtime.id in [1, 2]:
  37.169 +            v = runtime.broadcast([1, 2], [3], "V2")
  37.170 +            if isinstance(v, list):
  37.171 +                results += v
  37.172 +            else:
  37.173 +                results.append(v)
  37.174 +        else:
  37.175 +            results += runtime.broadcast([1, 2], [3])
  37.176 +        if 3 == runtime.id:
  37.177 +            results += [runtime.broadcast([3], runtime.players.keys(), str(7))]
  37.178 +        else:
  37.179 +            results += [runtime.broadcast([3], runtime.players.keys())]
  37.180 +        dls = DeferredList(results)
  37.181 +        runtime.schedule_callback(dls, check)
  37.182 +        dls.addErrback(runtime.error_handler)
  37.183 +        return dls
    38.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    38.2 +++ b/viff/test/test_orlandi_runtime.py	Fri Oct 23 13:50:19 2009 +0200
    38.3 @@ -0,0 +1,774 @@
    38.4 +# Copyright 2009 VIFF Development Team.
    38.5 +#
    38.6 +# This file is part of VIFF, the Virtual Ideal Functionality Framework.
    38.7 +#
    38.8 +# VIFF is free software: you can redistribute it and/or modify it
    38.9 +# under the terms of the GNU Lesser General Public License (LGPL) as
   38.10 +# published by the Free Software Foundation, either version 3 of the
   38.11 +# License, or (at your option) any later version.
   38.12 +#
   38.13 +# VIFF is distributed in the hope that it will be useful, but WITHOUT
   38.14 +# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
   38.15 +# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
   38.16 +# Public License for more details.
   38.17 +#
   38.18 +# You should have received a copy of the GNU Lesser General Public
   38.19 +# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
   38.20 +
   38.21 +from twisted.internet.defer import gatherResults, DeferredList
   38.22 +
   38.23 +from viff.test.util import RuntimeTestCase, protocol
   38.24 +from viff.runtime import gather_shares
   38.25 +try:
   38.26 +    from viff.orlandi import OrlandiRuntime, OrlandiShare
   38.27 +    import commitment
   38.28 +except ImportError:
   38.29 +    commitment = None
   38.30 +    OrlandiRuntime = None
   38.31 +    OrlandiShare = None
   38.32 +
   38.33 +from viff.field import FieldElement, GF
   38.34 +
   38.35 +from viff.util import rand
   38.36 +
   38.37 +
   38.38 +def _get_triple(runtime, field):
   38.39 +    n = field(0)
   38.40 +    Ca = commitment.commit(6, 0, 0)
   38.41 +    a = OrlandiShare(runtime, field, field(2), (n, n), Ca)
   38.42 +    Cb = commitment.commit(12, 0, 0)
   38.43 +    b = OrlandiShare(runtime, field, field(4), (n, n), Cb)
   38.44 +    Cc = commitment.commit(72, 0, 0)
   38.45 +    c = OrlandiShare(runtime, field, field(24), (n, n), Cc)
   38.46 +    return (a, b, c)
   38.47 +
   38.48 +
   38.49 +class OrlandiBasicCommandsTest(RuntimeTestCase):
   38.50 +    """Test for basic commands."""
   38.51 +
   38.52 +    # Number of players.
   38.53 +    num_players = 3
   38.54 +
   38.55 +    runtime_class = OrlandiRuntime
   38.56 +
   38.57 +    @protocol
   38.58 +    def test_secret_share(self, runtime):
   38.59 +        """Test sharing of random numbers."""
   38.60 +
   38.61 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
   38.62 +
   38.63 +        def check((xi, (rho1, rho2), Cr)):
   38.64 +            # Check that we got the expected number of shares.
   38.65 +            self.assert_type(xi, FieldElement)
   38.66 +            self.assert_type(rho1, FieldElement)
   38.67 +            self.assert_type(rho2, FieldElement)
   38.68 +            self.assert_type(Cr, commitment.Commitment)
   38.69 +
   38.70 +        if 1 == runtime.id:
   38.71 +            share = runtime.secret_share([1], self.Zp, 42)
   38.72 +        else:
   38.73 +            share = runtime.secret_share([1], self.Zp)
   38.74 +        share.addCallback(check)
   38.75 +        return share
   38.76 +
   38.77 +    @protocol
   38.78 +    def test_open_secret_share(self, runtime):
   38.79 +        """Test sharing and open of a number."""
   38.80 +
   38.81 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
   38.82 +
   38.83 +        def check(v):
   38.84 +            self.assertEquals(v, 42)
   38.85 +
   38.86 +        if 1 == runtime.id:
   38.87 +            x = runtime.secret_share([1], self.Zp, 42)
   38.88 +        else:
   38.89 +            x = runtime.secret_share([1], self.Zp)
   38.90 +        d = runtime.open(x)
   38.91 +        d.addCallback(check)
   38.92 +        return d
   38.93 +
   38.94 +    @protocol
   38.95 +    def test_random_share(self, runtime):
   38.96 +        """Test creation of a random shared number."""
   38.97 +
   38.98 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
   38.99 +
  38.100 +        def check(v):
  38.101 +            self.assertEquals(True, True)
  38.102 +
  38.103 +        x = runtime.random_share(self.Zp)
  38.104 +        d = runtime.open(x)
  38.105 +        d.addCallback(check)
  38.106 +        return d
  38.107 +
  38.108 +    @protocol
  38.109 +    def test_sum(self, runtime):
  38.110 +        """Test addition of two numbers."""
  38.111 +
  38.112 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  38.113 +
  38.114 +        x1 = 42
  38.115 +        y1 = 7
  38.116 +
  38.117 +        def check(v):
  38.118 +            self.assertEquals(v, x1 + y1)
  38.119 +
  38.120 +        if 1 == runtime.id:
  38.121 +            x2 = runtime.secret_share([1], self.Zp, x1)
  38.122 +        else:
  38.123 +            x2 = runtime.secret_share([1], self.Zp)
  38.124 +
  38.125 +        if 3 == runtime.id:
  38.126 +            y2 = runtime.secret_share([3], self.Zp, y1)
  38.127 +        else:
  38.128 +            y2 = runtime.secret_share([3], self.Zp)
  38.129 +
  38.130 +        z2 = runtime.add(x2, y2)
  38.131 +        d = runtime.open(z2)
  38.132 +        d.addCallback(check)
  38.133 +        return d
  38.134 +
  38.135 +    @protocol
  38.136 +    def test_sum_plus(self, runtime):
  38.137 +        """Test addition of two numbers."""
  38.138 +
  38.139 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  38.140 +
  38.141 +        x1 = 42
  38.142 +        y1 = 7
  38.143 +
  38.144 +        def check(v):
  38.145 +            self.assertEquals(v, x1 + y1)
  38.146 +
  38.147 +        if 1 == runtime.id:
  38.148 +            x2 = runtime.secret_share([1], self.Zp, x1)
  38.149 +        else:
  38.150 +            x2 = runtime.secret_share([1], self.Zp)
  38.151 +
  38.152 +        if 3 == runtime.id:
  38.153 +            y2 = runtime.secret_share([3], self.Zp, y1)
  38.154 +        else:
  38.155 +            y2 = runtime.secret_share([3], self.Zp)
  38.156 +
  38.157 +        z2 = x2 + y2
  38.158 +        d = runtime.open(z2)
  38.159 +        d.addCallback(check)
  38.160 +        return d
  38.161 +
  38.162 +    @protocol
  38.163 +    def test_sum_constant(self, runtime):
  38.164 +        """Test addition of two numbers."""
  38.165 +
  38.166 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  38.167 +
  38.168 +        x1 = 42
  38.169 +        y1 = 7
  38.170 +
  38.171 +        def check(v):
  38.172 +            self.assertEquals(v, x1 + y1)
  38.173 +
  38.174 +        if 1 == runtime.id:
  38.175 +            x2 = runtime.secret_share([1], self.Zp, x1)
  38.176 +        else:
  38.177 +            x2 = runtime.secret_share([1], self.Zp)
  38.178 +
  38.179 +        z2 = x2 + y1
  38.180 +        d = runtime.open(z2)
  38.181 +        d.addCallback(check)
  38.182 +        return d
  38.183 +
  38.184 +    @protocol
  38.185 +    def test_sub(self, runtime):
  38.186 +        """Test subtration of two numbers."""
  38.187 +
  38.188 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  38.189 +
  38.190 +        x1 = 42
  38.191 +        y1 = 7
  38.192 +
  38.193 +        def check(v):
  38.194 +            self.assertEquals(v, x1 - y1)
  38.195 +
  38.196 +        if 1 == runtime.id:
  38.197 +            x2 = runtime.secret_share([1], self.Zp, x1)
  38.198 +        else:
  38.199 +            x2 = runtime.secret_share([1], self.Zp)
  38.200 +
  38.201 +        if 3 == runtime.id:
  38.202 +            y2 = runtime.secret_share([3], self.Zp, y1)
  38.203 +        else:
  38.204 +            y2 = runtime.secret_share([3], self.Zp)
  38.205 +
  38.206 +        z2 = runtime.sub(x2, y2)
  38.207 +        d = runtime.open(z2)
  38.208 +        d.addCallback(check)
  38.209 +        return d
  38.210 +
  38.211 +    @protocol
  38.212 +    def test_sub_minus(self, runtime):
  38.213 +        """Test subtration of two numbers."""
  38.214 +
  38.215 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  38.216 +
  38.217 +        x1 = 42
  38.218 +        y1 = 7
  38.219 +
  38.220 +        def check(v):
  38.221 +            self.assertEquals(v, x1 - y1)
  38.222 +
  38.223 +        if 1 == runtime.id:
  38.224 +            x2 = runtime.secret_share([1], self.Zp, x1)
  38.225 +        else:
  38.226 +            x2 = runtime.secret_share([1], self.Zp)
  38.227 +
  38.228 +        if 3 == runtime.id:
  38.229 +            y2 = runtime.secret_share([3], self.Zp, y1)
  38.230 +        else:
  38.231 +            y2 = runtime.secret_share([3], self.Zp)
  38.232 +
  38.233 +        z2 = x2 - y2
  38.234 +        d = runtime.open(z2)
  38.235 +        d.addCallback(check)
  38.236 +        return d
  38.237 +
  38.238 +    @protocol
  38.239 +    def test_sub_constant(self, runtime):
  38.240 +        """Test subtration of two numbers."""
  38.241 +
  38.242 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  38.243 +
  38.244 +        x1 = 42
  38.245 +        y1 = 7
  38.246 +
  38.247 +        def check(v):
  38.248 +            self.assertEquals(v, x1 - y1)
  38.249 +
  38.250 +        if 1 == runtime.id:
  38.251 +            x2 = runtime.secret_share([1], self.Zp, x1)
  38.252 +        else:
  38.253 +            x2 = runtime.secret_share([1], self.Zp)
  38.254 +
  38.255 +        z2 = x2 - y1
  38.256 +        d = runtime.open(z2)
  38.257 +        d.addCallback(check)
  38.258 +        return d
  38.259 +
  38.260 +
  38.261 +class OrlandiAdvancedCommandsTest(RuntimeTestCase):
  38.262 +    """Test for advanced commands."""
  38.263 +
  38.264 +    # Number of players.
  38.265 +    num_players = 3
  38.266 +
  38.267 +    runtime_class = OrlandiRuntime
  38.268 +
  38.269 +    timeout = 60
  38.270 +
  38.271 +    @protocol
  38.272 +    def test_shift(self, runtime):
  38.273 +        """Test addition of the shift command."""
  38.274 +
  38.275 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  38.276 +
  38.277 +        def check(v):
  38.278 +            self.assertEquals(v, 42)
  38.279 +
  38.280 +        x = runtime.shift([2], self.Zp, 42)
  38.281 +        d = runtime.open(x)
  38.282 +        d.addCallback(check)
  38.283 +        return d
  38.284 +
  38.285 +    @protocol
  38.286 +    def test_shift_two_inputters(self, runtime):
  38.287 +        """Test addition of the shift command."""
  38.288 +
  38.289 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  38.290 +
  38.291 +        def check(v):
  38.292 +            self.assertEquals(v, 42)
  38.293 +
  38.294 +        x, y = runtime.shift([1,3], self.Zp, 42)
  38.295 +        d1 = runtime.open(x)
  38.296 +        d1.addCallback(check)
  38.297 +        d2 = runtime.open(y)
  38.298 +        d2.addCallback(check)
  38.299 +        return DeferredList([d1, d2])
  38.300 +
  38.301 +    @protocol
  38.302 +    def test_shift_two_consequtive_inputters(self, runtime):
  38.303 +        """Test addition of the shift command."""
  38.304 +
  38.305 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  38.306 +
  38.307 +        def r1(ls):
  38.308 +            x, y = ls
  38.309 +            self.assertEquals(runtime.program_counter, [4])
  38.310 +
  38.311 +        x = runtime.shift([1], self.Zp, 42)
  38.312 +        y = runtime.shift([2], self.Zp, 42)
  38.313 +        r = gather_shares([x, y])
  38.314 +        r.addCallback(r1)
  38.315 +        return r
  38.316 +
  38.317 +    @protocol
  38.318 +    def test_shift_two_consequtive_inputters2(self, runtime):
  38.319 +        """Test addition of the shift command."""
  38.320 +
  38.321 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  38.322 +
  38.323 +        def check(v):
  38.324 +            self.assertEquals(v, 42)
  38.325 +
  38.326 +        def r1((x, y)):
  38.327 +            self.assertEquals(x, 42)
  38.328 +            self.assertEquals(y, 42)
  38.329 +
  38.330 +        x = runtime.shift([1], self.Zp, 42)
  38.331 +        y = runtime.shift([2], self.Zp, 42)
  38.332 +        r = gather_shares([runtime.open(x), runtime.open(y)])
  38.333 +        r.addCallback(r1)
  38.334 +        return r
  38.335 +
  38.336 +    @protocol
  38.337 +    def test_input(self, runtime):
  38.338 +        """Test of many uses of the input command."""
  38.339 +
  38.340 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  38.341 +
  38.342 +        count = 9
  38.343 +
  38.344 +        a_shares = []
  38.345 +        b_shares = []
  38.346 +        for i in range(count):
  38.347 +            inputter = (i % len(runtime.players)) + 1
  38.348 +            if inputter == runtime.id:
  38.349 +                a = rand.randint(0, self.Zp.modulus)
  38.350 +                b = rand.randint(0, self.Zp.modulus)
  38.351 +            else:
  38.352 +                a, b = None, None
  38.353 +            a_shares.append(runtime.input([inputter], self.Zp, a))
  38.354 +            b_shares.append(runtime.input([inputter], self.Zp, b))
  38.355 +        shares_ready = gather_shares(a_shares + b_shares)
  38.356 +        return shares_ready
  38.357 +
  38.358 +    @protocol
  38.359 +    def test_basic_multiply(self, runtime):
  38.360 +        """Test multiplication of two numbers."""
  38.361 +
  38.362 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  38.363 +
  38.364 +        x1 = 42
  38.365 +        y1 = 7
  38.366 +
  38.367 +        def check(v):
  38.368 +            self.assertEquals(v, x1 * y1)
  38.369 +
  38.370 +        x2 = runtime.shift([2], self.Zp, x1)
  38.371 +        y2 = runtime.shift([3], self.Zp, y1)
  38.372 +
  38.373 +        a, b, c = _get_triple(self, self.Zp)
  38.374 +        z2 = runtime._basic_multiplication(x2, y2, a, b, c)
  38.375 +        d = runtime.open(z2)
  38.376 +        d.addCallback(check)
  38.377 +        return d
  38.378 +
  38.379 +    @protocol
  38.380 +    def test_mul_mul(self, runtime):
  38.381 +        """Test multiplication of two numbers."""
  38.382 +
  38.383 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  38.384 +
  38.385 +        x1 = 42
  38.386 +        y1 = 7
  38.387 +
  38.388 +        def check(v):
  38.389 +            self.assertEquals(v, x1 * y1)
  38.390 +
  38.391 +        x2 = runtime.shift([2], self.Zp, x1)
  38.392 +        y2 = runtime.shift([3], self.Zp, y1)
  38.393 +
  38.394 +        z2 = x2 * y2
  38.395 +        d = runtime.open(z2)
  38.396 +        d.addCallback(check)
  38.397 +        return d
  38.398 +
  38.399 +    @protocol
  38.400 +    def test_basic_multiply_constant_right(self, runtime):
  38.401 +        """Test multiplication of two numbers."""
  38.402 +
  38.403 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  38.404 +
  38.405 +        x1 = 42
  38.406 +        y1 = 7
  38.407 +
  38.408 +        def check(v):
  38.409 +            self.assertEquals(v, x1 * y1)
  38.410 +
  38.411 +        x2 = runtime.shift([1], self.Zp, x1)
  38.412 +
  38.413 +        a, b, c = _get_triple(self, self.Zp)
  38.414 +        z2 = runtime._basic_multiplication(x2, self.Zp(y1), a, b, c)
  38.415 +        d = runtime.open(z2)
  38.416 +        d.addCallback(check)
  38.417 +        return d
  38.418 +
  38.419 +    @protocol
  38.420 +    def test_basic_multiply_constant_left(self, runtime):
  38.421 +        """Test multiplication of two numbers."""
  38.422 +
  38.423 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  38.424 +
  38.425 +        x1 = 42
  38.426 +        y1 = 7
  38.427 +
  38.428 +        def check(v):
  38.429 +            self.assertEquals(v, x1 * y1)
  38.430 +
  38.431 +        x2 = runtime.shift([1], self.Zp, x1)
  38.432 +
  38.433 +        a, b, c = _get_triple(self, self.Zp)
  38.434 +        z2 = runtime._basic_multiplication(self.Zp(y1), x2, a, b, c)
  38.435 +        d = runtime.open(z2)
  38.436 +        d.addCallback(check)
  38.437 +        return d
  38.438 +
  38.439 +    @protocol
  38.440 +    def test_constant_multiplication_constant_left(self, runtime):
  38.441 +        """Test multiplication of two numbers."""
  38.442 +
  38.443 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  38.444 +
  38.445 +        x1 = 42
  38.446 +        y1 = 7
  38.447 +
  38.448 +        def check(v):
  38.449 +            self.assertEquals(v, x1 * y1)
  38.450 +
  38.451 +        x2 = runtime.shift([1], self.Zp, x1)
  38.452 +
  38.453 +        z2 = runtime._cmul(self.Zp(y1), x2, self.Zp)
  38.454 +        d = runtime.open(z2)
  38.455 +        d.addCallback(check)
  38.456 +        return d
  38.457 +
  38.458 +    @protocol
  38.459 +    def test_constant_multiplication_constant_right(self, runtime):
  38.460 +        """Test multiplication of two numbers."""
  38.461 +
  38.462 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  38.463 +
  38.464 +        x1 = 42
  38.465 +        y1 = 7
  38.466 +
  38.467 +        def check(v):
  38.468 +            self.assertEquals(v, x1 * y1)
  38.469 +
  38.470 +        x2 = runtime.shift([1], self.Zp, x1)
  38.471 +
  38.472 +        z2 = runtime._cmul(x2, self.Zp(y1), self.Zp)
  38.473 +        d = runtime.open(z2)
  38.474 +        d.addCallback(check)
  38.475 +        return d
  38.476 +
  38.477 +    @protocol
  38.478 +    def test_constant_multiplication_constant_None(self, runtime):
  38.479 +        """Test multiplication of two numbers."""
  38.480 +
  38.481 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  38.482 +
  38.483 +        x1 = 42
  38.484 +        y1 = 7
  38.485 +
  38.486 +        x2 = runtime.shift([1], self.Zp, x1)
  38.487 +        y2 = runtime.shift([1], self.Zp, y1)
  38.488 +
  38.489 +    @protocol
  38.490 +    def test_sum_poly1(self, runtime):
  38.491 +        """Test implementation of sum_poly."""
  38.492 +
  38.493 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  38.494 +
  38.495 +        f = []
  38.496 +        f.append((self.Zp(7), (self.Zp(7), self.Zp(7)), self.Zp(7)))
  38.497 +        f.append((self.Zp(9), (self.Zp(9), self.Zp(9)), self.Zp(9)))
  38.498 +        f.append((self.Zp(13), (self.Zp(13), self.Zp(13)), self.Zp(13)))
  38.499 +
  38.500 +        x, (rho1, rho2), Cx = runtime.sum_poly(1, f)
  38.501 +        self.assertEquals(x, 29)
  38.502 +        self.assertEquals(rho1, 29)
  38.503 +        self.assertEquals(rho2, 29)
  38.504 +        self.assertEquals(Cx, 819)
  38.505 +        return x
  38.506 +
  38.507 +    @protocol
  38.508 +    def test_sum_poly2(self, runtime):
  38.509 +        """Test implementation of sum_poly."""
  38.510 +
  38.511 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  38.512 +
  38.513 +        Cf1 = commitment.commit(21, 21, 21)
  38.514 +        Cf2 = commitment.commit(27, 27, 27)
  38.515 +        Cf3 = commitment.commit(39, 39, 39)
  38.516 +
  38.517 +        f = []
  38.518 +        f.append((self.Zp(7), (self.Zp(7), self.Zp(7)), Cf1))
  38.519 +        f.append((self.Zp(9), (self.Zp(9), self.Zp(9)), Cf2))
  38.520 +        f.append((self.Zp(13), (self.Zp(13), self.Zp(13)), Cf3))
  38.521 +
  38.522 +        x, (rho1, rho2), Cx = runtime.sum_poly(3, f)
  38.523 +        self.assertEquals(x, 453)
  38.524 +        self.assertEquals(rho1, 453)
  38.525 +        self.assertEquals(rho2, 453)
  38.526 +        self.assertEquals(Cx, Cf1**3 * Cf2**9 * Cf3**27)
  38.527 +        return x
  38.528 +
  38.529 +    @protocol
  38.530 +    def test_delta(self, runtime):
  38.531 +        """Test implementation of compute_delta."""
  38.532 +
  38.533 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  38.534 +
  38.535 +        delta = runtime.compute_delta(3)
  38.536 +        self.assertEquals(delta[0], 7)
  38.537 +        self.assertEquals(delta[1], -21)
  38.538 +        self.assertEquals(delta[2], 35)
  38.539 +        self.assertEquals(delta[3], -35)
  38.540 +        self.assertEquals(delta[4], 21)
  38.541 +        self.assertEquals(delta[5], -7)
  38.542 +        self.assertEquals(delta[6], 1)
  38.543 +
  38.544 +        return delta
  38.545 +
  38.546 +    @protocol
  38.547 +    def test_leak_mul(self, runtime):
  38.548 +        """Test leaktolerant multiplication of two numbers."""
  38.549 +        commitment.set_reference_string(long(2), long(6))
  38.550 +
  38.551 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  38.552 +
  38.553 +        x1 = 42
  38.554 +        y1 = 7
  38.555 +
  38.556 +        runtime.s = 1
  38.557 +        runtime.d = 0
  38.558 +        runtime.s_lambda = 1
  38.559 +
  38.560 +        def check(v):
  38.561 +            self.assertEquals(v, x1 * y1)
  38.562 +
  38.563 +        x2 = runtime.shift([1], self.Zp, x1)
  38.564 +        y2 = runtime.shift([2], self.Zp, y1)
  38.565 +
  38.566 +        c, sls = runtime.random_triple(self.Zp, 2*runtime.d + 1)
  38.567 +
  38.568 +        def cont(M):
  38.569 +            z2 = runtime.leak_tolerant_mul(x2, y2, M)
  38.570 +            d = runtime.open(z2)
  38.571 +            d.addCallback(check)
  38.572 +            return d
  38.573 +        sls.addCallbacks(cont, runtime.error_handler)
  38.574 +        return sls
  38.575 +
  38.576 +        z2 = runtime._cmul(y2, x2, self.Zp)
  38.577 +        self.assertEquals(z2, None)
  38.578 +        return z2
  38.579 +
  38.580 +class TripleGenTest(RuntimeTestCase):
  38.581 +    """Test for generation of triples."""
  38.582 +
  38.583 +    # Number of players.
  38.584 +    num_players = 3
  38.585 +
  38.586 +    runtime_class = OrlandiRuntime
  38.587 +
  38.588 +    timeout = 1600
  38.589 +
  38.590 +    @protocol
  38.591 +    def test_tripleGen(self, runtime):
  38.592 +        """Test the triple_gen command."""
  38.593 +
  38.594 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  38.595 +
  38.596 +        def check((a, b, c)):
  38.597 +            self.assertEquals(c, a * b)
  38.598 +
  38.599 +        def open((a, b, c, _)):
  38.600 +            d1 = runtime.open(a)
  38.601 +            d2 = runtime.open(b)
  38.602 +            d3 = runtime.open(c)
  38.603 +            d = gatherResults([d1, d2, d3])
  38.604 +            d.addCallback(check)
  38.605 +            return d
  38.606 +        d = runtime.triple_gen(self.Zp)
  38.607 +        d.addCallbacks(open, runtime.error_handler)
  38.608 +        return d
  38.609 +
  38.610 +    @protocol
  38.611 +    def test_tripleGen2(self, runtime):
  38.612 +        """Test the triple_gen command."""
  38.613 +
  38.614 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  38.615 +
  38.616 +        def check((a, b, c, dx, dy, dz)):
  38.617 +            self.assertEquals(c, a * b)
  38.618 +            self.assertEquals(dz, dx * dy)
  38.619 +
  38.620 +        def open(((a, b, c, control), (x, y, z, _))):
  38.621 +            d1 = runtime.open(a)
  38.622 +            d2 = runtime.open(b)
  38.623 +            d3 = runtime.open(c)
  38.624 +            dx = runtime.open(x)
  38.625 +            dy = runtime.open(y)
  38.626 +            dz = runtime.open(z)
  38.627 +            d = gatherResults([d1, d2, d3, dx, dy, dz])
  38.628 +            d.addCallback(check)
  38.629 +            return d
  38.630 +        t1 = runtime.triple_gen(self.Zp)
  38.631 +        t2 = runtime.triple_gen(self.Zp)
  38.632 +        d = gatherResults([t1, t2])
  38.633 +        d.addCallbacks(open, runtime.error_handler)
  38.634 +        return d
  38.635 +
  38.636 +    @protocol
  38.637 +    def test_tripleTest(self, runtime):
  38.638 +        """Test the triple_test command."""
  38.639 +
  38.640 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  38.641 +
  38.642 +        def check((a, b, c)):
  38.643 +            self.assertEquals(c, a * b)
  38.644 +
  38.645 +        def open((a, b, c, _)):
  38.646 +            d1 = runtime.open(a)
  38.647 +            d2 = runtime.open(b)
  38.648 +            d3 = runtime.open(c)
  38.649 +            d = gatherResults([d1, d2, d3])
  38.650 +            d.addCallback(check)
  38.651 +            return d
  38.652 +        d = runtime.triple_test(self.Zp)
  38.653 +        d.addCallbacks(open, runtime.error_handler)
  38.654 +        return d
  38.655 +
  38.656 +    @protocol
  38.657 +    def test_random_triple(self, runtime):
  38.658 +        """Test the triple_combiner command."""
  38.659 +
  38.660 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  38.661 +
  38.662 +        def check(ls):
  38.663 +            for x in xrange(len(ls) // 3):
  38.664 +                a = ls[x * 3]
  38.665 +                b = ls[x * 3 + 1]
  38.666 +                c = ls[x * 3 + 2]
  38.667 +                self.assertEquals(c, a * b)
  38.668 +
  38.669 +        def open(ls):
  38.670 +            ds = []
  38.671 +            for (a, b, c) in ls:
  38.672 +                d1 = runtime.open(a)
  38.673 +                d2 = runtime.open(b)
  38.674 +                d3 = runtime.open(c)
  38.675 +                ds.append(d1)
  38.676 +                ds.append(d2)
  38.677 +                ds.append(d3)
  38.678 +
  38.679 +            d = gatherResults(ds)
  38.680 +            d.addCallback(check)
  38.681 +            return d
  38.682 +        c, d = runtime.random_triple(self.Zp, 1)
  38.683 +        d.addCallbacks(open, runtime.error_handler)
  38.684 +        return d
  38.685 +
  38.686 +    @protocol
  38.687 +    def test_random_triple3_parallel(self, runtime):
  38.688 +        """Test the triple_combiner command."""
  38.689 +
  38.690 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  38.691 +
  38.692 +        def check(ls):
  38.693 +            for x in xrange(len(ls) // 3):
  38.694 +                a = ls[x * 3]
  38.695 +                b = ls[x * 3 + 1]
  38.696 +                c = ls[x * 3 + 2]
  38.697 +                self.assertEquals(c, a * b)
  38.698 +
  38.699 +        def open(ls):
  38.700 +            ds = []
  38.701 +            for [(a, b, c)] in ls:
  38.702 +                d1 = runtime.open(a)
  38.703 +                d2 = runtime.open(b)
  38.704 +                d3 = runtime.open(c)
  38.705 +                ds.append(d1)
  38.706 +                ds.append(d2)
  38.707 +                ds.append(d3)
  38.708 +
  38.709 +            d = gatherResults(ds)
  38.710 +            d.addCallback(check)
  38.711 +            return d
  38.712 +        ac, a = runtime.random_triple(self.Zp, 1)
  38.713 +        bc, b = runtime.random_triple(self.Zp, 1)
  38.714 +        cc, c = runtime.random_triple(self.Zp, 1)
  38.715 +        d = gather_shares([a, b, c])
  38.716 +        d.addCallbacks(open, runtime.error_handler)
  38.717 +        return d
  38.718 +
  38.719 +    @protocol
  38.720 +    def test_random_triple_parallel(self, runtime):
  38.721 +        """Test the triple_combiner command."""
  38.722 +
  38.723 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
  38.724 +
  38.725 +        def check(ls):
  38.726 +            for x in xrange(len(ls) // 3):
  38.727 +                a = ls[x * 3]
  38.728 +                b = ls[x * 3 + 1]
  38.729 +                c = ls[x * 3 + 2]
  38.730 +                self.assertEquals(c, a * b)
  38.731 +
  38.732 +        def open(ls):
  38.733 +            ds = []
  38.734 +            for [(a, b, c)] in ls:
  38.735 +                d1 = runtime.open(a)
  38.736 +                d2 = runtime.open(b)
  38.737 +                d3 = runtime.open(c)
  38.738 +                ds.append(d1)
  38.739 +                ds.append(d2)
  38.740 +                ds.append(d3)
  38.741 +
  38.742 +            d = gatherResults(ds)
  38.743 +            d.addCallback(check)
  38.744 +            return d
  38.745 +
  38.746 +        a_shares = []
  38.747 +        b_shares = []
  38.748 +        c_shares = []
  38.749 +
  38.750 +        def cont(x):
  38.751 +            while a_shares and b_shares:
  38.752 +                a = a_shares.pop()
  38.753 +                b = b_shares.pop()
  38.754 +                c_shares.append(runtime.mul(a, b))
  38.755 +            done = gather_shares(c_shares)
  38.756 +            return done
  38.757 +
  38.758 +        count = 5
  38.759 +
  38.760 +        for i in range(count):
  38.761 +            inputter = (i % len(runtime.players)) + 1
  38.762 +            if inputter == runtime.id:
  38.763 +                a = rand.randint(0, self.Zp.modulus)
  38.764 +                b = rand.randint(0, self.Zp.modulus)
  38.765 +            else:
  38.766 +                a, b = None, None
  38.767 +            a_shares.append(runtime.input([inputter], self.Zp, a))
  38.768 +            b_shares.append(runtime.input([inputter], self.Zp, b))
  38.769 +        shares_ready = gather_shares(a_shares + b_shares)
  38.770 +
  38.771 +        runtime.schedule_callback(shares_ready, cont)
  38.772 +        return shares_ready
  38.773 +
  38.774 +if not commitment:
  38.775 +    OrlandiAdvancedCommandsTest.skip = "Skipped due to missing commitment module."
  38.776 +    OrlandiBasicCommandsTest.skip = "Skipped due to missing commitment module."
  38.777 +    TripleGenTest.skip = "Skipped due to missing commitment module."
    39.1 --- a/viff/test/test_runtime.py	Thu Oct 22 19:38:31 2009 +0200
    39.2 +++ b/viff/test/test_runtime.py	Fri Oct 23 13:50:19 2009 +0200
    39.3 @@ -27,10 +27,11 @@
    39.4  from random import Random
    39.5  import operator
    39.6  
    39.7 -from twisted.internet.defer import gatherResults
    39.8 +from twisted.internet.defer import gatherResults, Deferred, DeferredList
    39.9  
   39.10  from viff.field import GF256
   39.11  from viff.runtime import Share
   39.12 +from viff.constants import SHARE
   39.13  from viff.comparison import Toft05Runtime
   39.14  from viff.test.util import RuntimeTestCase, BinaryOperatorTestCase, protocol
   39.15  
   39.16 @@ -191,6 +192,49 @@
   39.17  
   39.18          return gatherResults([opened_a, opened_b, opened_c])
   39.19  
   39.20 +    @protocol
   39.21 +    def test_send_receive_self(self, runtime):
   39.22 +        """Test send and receive of values."""
   39.23 +        value = 42
   39.24 +        
   39.25 +        pc = tuple(runtime.program_counter)
   39.26 +        runtime.protocols[runtime.id].sendData(pc, SHARE, str(value))
   39.27 +
   39.28 +        d = Deferred()
   39.29 +        runtime._expect_data(runtime.id, SHARE, d)
   39.30 +        def check(x):
   39.31 +            self.assertEquals(int(x), value)
   39.32 +            return x
   39.33 +        d.addCallback(check)
   39.34 +        return d
   39.35 +
   39.36 +    @protocol
   39.37 +    def test_send_receive_self2(self, runtime):
   39.38 +        """Test send and receive of values."""
   39.39 +        value = 42
   39.40 +        
   39.41 +        pc = tuple(runtime.program_counter)
   39.42 +        for peer_id in runtime.players:
   39.43 +            data = str(value)
   39.44 +            runtime.protocols[peer_id].sendData(pc, SHARE, data)
   39.45 +
   39.46 +        ds = []
   39.47 +        for peer_id in runtime.players:
   39.48 +            d = Deferred()
   39.49 +            runtime._expect_data(peer_id, SHARE, d)
   39.50 +            ds.append(d)
   39.51 +
   39.52 +        dls = DeferredList(ds)
   39.53 +        def check(ls):
   39.54 +            for s, x in ls:
   39.55 +                self.assertEquals(int(x), value)
   39.56 +            return ls
   39.57 +
   39.58 +        dls.addCallback(check)
   39.59 +        return dls
   39.60 +
   39.61 +
   39.62 +
   39.63  
   39.64  class ConvertBitShareTest(RuntimeTestCase):
   39.65      runtime_class = Toft05Runtime
    40.1 --- a/viff/test/test_thresholds.py	Thu Oct 22 19:38:31 2009 +0200
    40.2 +++ b/viff/test/test_thresholds.py	Fri Oct 23 13:50:19 2009 +0200
    40.3 @@ -91,66 +91,26 @@
    40.4      num_players = 3
    40.5      threshold = 1
    40.6  
    40.7 -
    40.8  class Players4Threshold1Test(Tests, RuntimeTestCase):
    40.9      num_players = 4
   40.10      threshold = 1
   40.11  
   40.12 -
   40.13 -class Players5Threshold1Test(Tests, RuntimeTestCase):
   40.14 -    num_players = 5
   40.15 -    threshold = 1
   40.16 -
   40.17  class Players5Threshold2Test(Tests, RuntimeTestCase):
   40.18      num_players = 5
   40.19      threshold = 2
   40.20  
   40.21 -
   40.22 -class Players6Threshold1Test(Tests, RuntimeTestCase):
   40.23 -    num_players = 6
   40.24 -    threshold = 1
   40.25 -
   40.26  class Players6Threshold2Test(Tests, RuntimeTestCase):
   40.27      num_players = 6
   40.28      threshold = 2
   40.29  
   40.30 -
   40.31 -class Players7Threshold1Test(Tests, RuntimeTestCase):
   40.32 -    num_players = 7
   40.33 -    threshold = 1
   40.34 -
   40.35 -class Players7Threshold2Test(Tests, RuntimeTestCase):
   40.36 -    num_players = 7
   40.37 -    threshold = 2
   40.38 -
   40.39  class Players7Threshold3Test(Tests, RuntimeTestCase):
   40.40      num_players = 7
   40.41      threshold = 3
   40.42  
   40.43 -class Players8Threshold1Test(Tests, RuntimeTestCase):
   40.44 -    num_players = 8
   40.45 -    threshold = 1
   40.46 -
   40.47 -class Players8Threshold2Test(Tests, RuntimeTestCase):
   40.48 -    num_players = 8
   40.49 -    threshold = 2
   40.50 -
   40.51  class Players8Threshold3Test(Tests, RuntimeTestCase):
   40.52      num_players = 8
   40.53      threshold = 3
   40.54  
   40.55 -class Players9Threshold1Test(Tests, RuntimeTestCase):
   40.56 -    num_players = 9
   40.57 -    threshold = 1
   40.58 -
   40.59 -class Players9Threshold2Test(Tests, RuntimeTestCase):
   40.60 -    num_players = 9
   40.61 -    threshold = 2
   40.62 -
   40.63 -class Players9Threshold3Test(Tests, RuntimeTestCase):
   40.64 -    num_players = 9
   40.65 -    threshold = 3
   40.66 -
   40.67  class Players9Threshold4Test(Tests, RuntimeTestCase):
   40.68      num_players = 9
   40.69      threshold = 4
    41.1 --- a/viff/test/util.py	Thu Oct 22 19:38:31 2009 +0200
    41.2 +++ b/viff/test/util.py	Fri Oct 23 13:50:19 2009 +0200
    41.3 @@ -22,7 +22,7 @@
    41.4  from twisted.internet import reactor
    41.5  
    41.6  from viff.passive import PassiveRuntime
    41.7 -from viff.runtime import Share, ShareExchanger, ShareExchangerFactory
    41.8 +from viff.runtime import Share, ShareExchanger, ShareExchangerFactory, SelfShareExchanger, SelfShareExchangerFactory, FakeTransport
    41.9  from viff.field import GF
   41.10  from viff.config import generate_configs, load_config
   41.11  from viff.util import rand
   41.12 @@ -220,7 +220,13 @@
   41.13                      # fire.
   41.14                      sentinel = loopbackAsync(server, client)
   41.15                      self.close_sentinels.append(sentinel)
   41.16 -
   41.17 +            else:
   41.18 +                protocol = SelfShareExchanger(id, SelfShareExchangerFactory(runtime))
   41.19 +                protocol.transport = FakeTransport()
   41.20 +                # Keys for when we are the client and when we are the server.
   41.21 +                server_key = (id, id)
   41.22 +                # Store a protocol used when we are the server.
   41.23 +                self.protocols[server_key] = protocol     
   41.24  
   41.25  class BinaryOperatorTestCase:
   41.26      """Test a binary operator.
    42.1 --- a/viff/util.py	Thu Oct 22 19:38:31 2009 +0200
    42.2 +++ b/viff/util.py	Fri Oct 23 13:50:19 2009 +0200
    42.3 @@ -22,8 +22,6 @@
    42.4  ensures that a protocol run can be reproduced at a later time.
    42.5  """
    42.6  
    42.7 -__docformat__ = "restructuredtext"
    42.8 -
    42.9  import os
   42.10  import time
   42.11  import random
   42.12 @@ -64,29 +62,15 @@
   42.13      It is important to use this decorator on any wrapper functions in
   42.14      order to ensure that they end up with correct :attr:`__name__` and
   42.15      :attr:`__doc__` attributes.
   42.16 -
   42.17 -    In addition, if the environment variable :envvar:`VIFF_NO_WRAP` is
   42.18 -    defined, then the wrapper functions will be turned into functions
   42.19 -    that *do not* wrap -- instead they let their argument function
   42.20 -    through unchanged. This is done so that epydoc and Sphinx can see
   42.21 -    the true function arguments when generating documentation. Just
   42.22 -    remember that your code will break if :envvar:`VIFF_NO_WRAP` is
   42.23 -    set, so it should only be used when documentation is being
   42.24 -    generated.
   42.25      """
   42.26 -    if os.environ.get('VIFF_NO_WRAP'):
   42.27 -        # Return a decorator which ignores the functions it is asked
   42.28 -        # to decorate and instead returns func:
   42.29 -        return lambda _: func
   42.30 -    else:
   42.31 -        # Return a decorator which does nothing to the function it is
   42.32 -        # asked to decorate, except update the __name__ and __doc__
   42.33 -        # attributes to match the original wrapped function.
   42.34 -        def decorator(f):
   42.35 -            f.__name__ = func.__name__
   42.36 -            f.__doc__ = func.__doc__
   42.37 -            return f
   42.38 -        return decorator
   42.39 +    # Return a decorator which does nothing to the function it is
   42.40 +    # asked to decorate, except update the __name__ and __doc__
   42.41 +    # attributes to match the original wrapped function.
   42.42 +    def decorator(f):
   42.43 +        f.__name__ = func.__name__
   42.44 +        f.__doc__ = func.__doc__
   42.45 +        return f
   42.46 +    return decorator
   42.47  
   42.48  def fake(replacement):
   42.49      """Replace a function with a fake version.