viff

changeset 907:c898cac3f98a

Moved ActiveRuntime to a new viff.active module.
author Martin Geisler <mg@daimi.au.dk>
date Mon, 15 Sep 2008 15:46:50 +0200
parents fb42b645ca5b
children fe815100b30e
files apps/benchmark.py doc/active.txt doc/implementation.txt doc/runtime.txt viff/active.py viff/comparison.py viff/runtime.py viff/test/test_active_runtime.py
diffstat 8 files changed, 504 insertions(+), 469 deletions(-) [+]
line diff
     1.1 --- a/apps/benchmark.py	Mon Sep 15 14:30:20 2008 +0200
     1.2 +++ b/apps/benchmark.py	Mon Sep 15 15:46:50 2008 +0200
     1.3 @@ -62,7 +62,8 @@
     1.4  from twisted.internet import reactor
     1.5  
     1.6  from viff.field import GF, GF256
     1.7 -from viff.runtime import Runtime, ActiveRuntime, create_runtime, gather_shares
     1.8 +from viff.runtime import Runtime, create_runtime, gather_shares
     1.9 +from viff.active import ActiveRuntime
    1.10  from viff.comparison import Toft05Runtime, Toft07Runtime
    1.11  from viff.comparison import ActiveToft05Runtime, ActiveToft07Runtime
    1.12  from viff.paillier import PaillierRuntime
     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/doc/active.txt	Mon Sep 15 15:46:50 2008 +0200
     2.3 @@ -0,0 +1,8 @@
     2.4 +
     2.5 +Actively Secure Protocols
     2.6 +=========================
     2.7 +
     2.8 +.. automodule:: viff.active
     2.9 +
    2.10 +   .. autoclass:: ActiveRuntime
    2.11 +      :members:
     3.1 --- a/doc/implementation.txt	Mon Sep 15 14:30:20 2008 +0200
     3.2 +++ b/doc/implementation.txt	Mon Sep 15 15:46:50 2008 +0200
     3.3 @@ -12,6 +12,7 @@
     3.4     shamir
     3.5     matrix
     3.6     runtime
     3.7 +   active
     3.8     comparison
     3.9     prss
    3.10     config
     4.1 --- a/doc/runtime.txt	Mon Sep 15 14:30:20 2008 +0200
     4.2 +++ b/doc/runtime.txt	Mon Sep 15 15:46:50 2008 +0200
     4.3 @@ -87,6 +87,3 @@
     4.4  
     4.5     .. autoclass:: Runtime
     4.6        :members:
     4.7 -
     4.8 -   .. autoclass:: ActiveRuntime
     4.9 -      :members: mul, single_share_random, double_share_random, get_triple, generate_triples, broadcast
     5.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     5.2 +++ b/viff/active.py	Mon Sep 15 15:46:50 2008 +0200
     5.3 @@ -0,0 +1,490 @@
     5.4 +# Copyright 2008 VIFF Development Team.
     5.5 +#
     5.6 +# This file is part of VIFF, the Virtual Ideal Functionality Framework.
     5.7 +#
     5.8 +# VIFF is free software: you can redistribute it and/or modify it
     5.9 +# under the terms of the GNU Lesser General Public License (LGPL) as
    5.10 +# published by the Free Software Foundation, either version 3 of the
    5.11 +# License, or (at your option) any later version.
    5.12 +#
    5.13 +# VIFF is distributed in the hope that it will be useful, but WITHOUT
    5.14 +# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
    5.15 +# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
    5.16 +# Public License for more details.
    5.17 +#
    5.18 +# You should have received a copy of the GNU Lesser General Public
    5.19 +# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
    5.20 +
    5.21 +"""Actively secure protocols."""
    5.22 +
    5.23 +__docformat__ = "restructuredtext"
    5.24 +
    5.25 +from math import ceil
    5.26 +
    5.27 +from twisted.internet.defer import gatherResults, Deferred, succeed
    5.28 +
    5.29 +from viff import shamir
    5.30 +from viff.util import rand
    5.31 +from viff.matrix import Matrix, hyper
    5.32 +from viff.runtime import Runtime, Share, increment_pc, preprocess, gather_shares
    5.33 +
    5.34 +
    5.35 +class ActiveRuntime(Runtime):
    5.36 +    """A runtime secure against active adversaries.
    5.37 +
    5.38 +    This class currently inherits most of its functionality from the
    5.39 +    normal :class:`Runtime` class and is thus **not** yet secure.
    5.40 +    """
    5.41 +
    5.42 +    def __init__(self, player, threshold, options=None):
    5.43 +        """Initialize runtime."""
    5.44 +
    5.45 +        #: A hyper-invertible matrix.
    5.46 +        #:
    5.47 +        #: It should be suitable for :attr:`num_players` players, but
    5.48 +        #: since we don't know the total number of players yet, we set
    5.49 +        #: it to :const:`None` here and update it as necessary.
    5.50 +        self._hyper = None
    5.51 +        Runtime.__init__(self, player, threshold, options)
    5.52 +
    5.53 +    @increment_pc
    5.54 +    def mul(self, share_x, share_y):
    5.55 +        """Multiplication of shares.
    5.56 +
    5.57 +        Preprocessing: 1 multiplication triple.
    5.58 +        Communication: 2 openings.
    5.59 +        """
    5.60 +        assert isinstance(share_x, Share) or isinstance(share_y, Share), \
    5.61 +            "At least one of share_x and share_y must be a Share."
    5.62 +
    5.63 +        if not isinstance(share_x, Share):
    5.64 +            # Then share_y must be a Share => local multiplication. We
    5.65 +            # clone first to avoid changing share_y.
    5.66 +            result = share_y.clone()
    5.67 +            result.addCallback(lambda y: share_x * y)
    5.68 +            return result
    5.69 +        if not isinstance(share_y, Share):
    5.70 +            # Likewise when share_y is a constant.
    5.71 +            result = share_x.clone()
    5.72 +            result.addCallback(lambda x: x * share_y)
    5.73 +            return result
    5.74 +
    5.75 +        # At this point both share_x and share_y must be Share
    5.76 +        # objects. We multiply them via a multiplication triple.
    5.77 +        def finish_mul(triple):
    5.78 +            a, b, c = triple
    5.79 +            d = self.open(share_x - a)
    5.80 +            e = self.open(share_y - b)
    5.81 +
    5.82 +            # TODO: We ought to be able to simply do
    5.83 +            #
    5.84 +            #   return d*e + d*y + e*x + c
    5.85 +            #
    5.86 +            # but that leads to infinite recursion since d and e are
    5.87 +            # Shares, not FieldElements. So we have to do a bit more
    5.88 +            # work... The following callback also leads to recursion, but
    5.89 +            # only one level since d and e are FieldElements now, which
    5.90 +            # means that we return in the above if statements.
    5.91 +            result = gather_shares([d, e])
    5.92 +            result.addCallback(lambda (d,e): d*e + d*b + e*a + c)
    5.93 +            return result
    5.94 +
    5.95 +        # This will be the result, a Share object.
    5.96 +        result = Share(self, share_x.field)
    5.97 +        # This is the Deferred we will do processing on.
    5.98 +        triple = self.prss_get_triple(share_x.field)
    5.99 +        self.schedule_callback(triple, finish_mul)
   5.100 +        # We add the result to the chains in triple.
   5.101 +        triple.chainDeferred(result)
   5.102 +        return result
   5.103 +
   5.104 +    @increment_pc
   5.105 +    def single_share_random(self, T, degree, field):
   5.106 +        """Share a random secret.
   5.107 +
   5.108 +        The guarantee is that a number of shares are made and out of
   5.109 +        those, the *T* that are returned by this method will be
   5.110 +        correct sharings of a random number using *degree* as the
   5.111 +        polynomial degree.
   5.112 +        """
   5.113 +        # TODO: Move common code between single_share and
   5.114 +        # double_share_random out to their own methods.
   5.115 +        inputters = range(1, self.num_players + 1)
   5.116 +        if self._hyper is None:
   5.117 +            self._hyper = hyper(self.num_players, field)
   5.118 +
   5.119 +        # Generate a random element.
   5.120 +        si = rand.randint(0, field.modulus - 1)
   5.121 +
   5.122 +        # Every player shares the random value with two thresholds.
   5.123 +        shares = self.shamir_share(inputters, field, si, degree)
   5.124 +
   5.125 +        # Turn the shares into a column vector.
   5.126 +        svec = Matrix([shares]).transpose()
   5.127 +
   5.128 +        # Apply the hyper-invertible matrix to svec1 and svec2.
   5.129 +        rvec = (self._hyper * svec)
   5.130 +
   5.131 +        # Get back to normal lists of shares.
   5.132 +        svec = svec.transpose().rows[0]
   5.133 +        rvec = rvec.transpose().rows[0]
   5.134 +
   5.135 +        def verify(shares):
   5.136 +            """Verify shares.
   5.137 +
   5.138 +            It is checked that they correspond to polynomial of the
   5.139 +            expected degree.
   5.140 +
   5.141 +            If the verification succeeds, the T shares are returned,
   5.142 +            otherwise the errback is called.
   5.143 +            """
   5.144 +            # TODO: This is necessary since shamir.recombine expects
   5.145 +            # to receive a list of *pairs* of field elements.
   5.146 +            shares = map(lambda (i, s): (field(i+1), s), enumerate(shares))
   5.147 +
   5.148 +            # Verify the sharings. If any of the assertions fail and
   5.149 +            # raise an exception, the errbacks will be called on the
   5.150 +            # share returned by single_share_random.
   5.151 +            assert shamir.verify_sharing(shares, degree), \
   5.152 +                   "Could not verify %s, degree %d" % (shares, degree)
   5.153 +
   5.154 +            # If we reach this point the n - T shares were verified
   5.155 +            # and we can safely return the first T shares.
   5.156 +            return rvec[:T]
   5.157 +
   5.158 +        def exchange(svec):
   5.159 +            """Exchange and (if possible) verify shares."""
   5.160 +            pc = tuple(self.program_counter)
   5.161 +
   5.162 +            # We send our shares to the verifying players.
   5.163 +            for offset, share in enumerate(svec):
   5.164 +                if T+1+offset != self.id:
   5.165 +                    self.protocols[T+1+offset].sendShare(pc, share)
   5.166 +
   5.167 +            if self.id > T:
   5.168 +                # The other players will send us their shares of si_1
   5.169 +                # and si_2 and we will verify it.
   5.170 +                si = []
   5.171 +                for peer_id in inputters:
   5.172 +                    if self.id == peer_id:
   5.173 +                        si.append(Share(self, field, svec[peer_id - T - 1]))
   5.174 +                    else:
   5.175 +                        si.append(self._expect_share(peer_id, field))
   5.176 +                result = gatherResults(si)
   5.177 +                self.schedule_callback(result, verify)
   5.178 +                return result
   5.179 +            else:
   5.180 +                # We cannot verify anything, so we just return the
   5.181 +                # first T shares.
   5.182 +                return rvec[:T]
   5.183 +
   5.184 +        result = gather_shares(svec[T:])
   5.185 +        self.schedule_callback(result, exchange)
   5.186 +        return result
   5.187 +
   5.188 +    @increment_pc
   5.189 +    def double_share_random(self, T, d1, d2, field):
   5.190 +        """Double-share a random secret using two polynomials.
   5.191 +
   5.192 +        The guarantee is that a number of shares are made and out of
   5.193 +        those, the *T* that are returned by this method will be correct
   5.194 +        double-sharings of a random number using *d1* and *d2* as the
   5.195 +        polynomial degrees.
   5.196 +        """
   5.197 +        inputters = range(1, self.num_players + 1)
   5.198 +        if self._hyper is None:
   5.199 +            self._hyper = hyper(self.num_players, field)
   5.200 +
   5.201 +        # Generate a random element.
   5.202 +        si = rand.randint(0, field.modulus - 1)
   5.203 +
   5.204 +        # Every player shares the random value with two thresholds.
   5.205 +        d1_shares = self.shamir_share(inputters, field, si, d1)
   5.206 +        d2_shares = self.shamir_share(inputters, field, si, d2)
   5.207 +
   5.208 +        # Turn the shares into a column vector.
   5.209 +        svec1 = Matrix([d1_shares]).transpose()
   5.210 +        svec2 = Matrix([d2_shares]).transpose()
   5.211 +
   5.212 +        # Apply the hyper-invertible matrix to svec1 and svec2.
   5.213 +        rvec1 = (self._hyper * svec1)
   5.214 +        rvec2 = (self._hyper * svec2)
   5.215 +
   5.216 +        # Get back to normal lists of shares.
   5.217 +        svec1 = svec1.transpose().rows[0]
   5.218 +        svec2 = svec2.transpose().rows[0]
   5.219 +        rvec1 = rvec1.transpose().rows[0]
   5.220 +        rvec2 = rvec2.transpose().rows[0]
   5.221 +
   5.222 +        def verify(shares):
   5.223 +            """Verify shares.
   5.224 +
   5.225 +            It is checked that they correspond to polynomial of the
   5.226 +            expected degrees and that they can be recombined to the
   5.227 +            same value.
   5.228 +
   5.229 +            If the verification succeeds, the T double shares are
   5.230 +            returned, otherwise the errback is called.
   5.231 +            """
   5.232 +            si_1, si_2 = shares
   5.233 +
   5.234 +            # TODO: This is necessary since shamir.recombine expects
   5.235 +            # to receive a list of *pairs* of field elements.
   5.236 +            si_1 = map(lambda (i, s): (field(i+1), s), enumerate(si_1))
   5.237 +            si_2 = map(lambda (i, s): (field(i+1), s), enumerate(si_2))
   5.238 +
   5.239 +            # Verify the sharings. If any of the assertions fail and
   5.240 +            # raise an exception, the errbacks will be called on the
   5.241 +            # double share returned by double_share_random.
   5.242 +            assert shamir.verify_sharing(si_1, d1), \
   5.243 +                   "Could not verify %s, degree %d" % (si_1, d1)
   5.244 +            assert shamir.verify_sharing(si_2, d2), \
   5.245 +                   "Could not verify %s, degree %d" % (si_2, d2)
   5.246 +            assert shamir.recombine(si_1[:d1+1]) == shamir.recombine(si_2[:d2+1]), \
   5.247 +                "Shares do not recombine to the same value"
   5.248 +
   5.249 +            # If we reach this point the n - T shares were verified
   5.250 +            # and we can safely return the first T shares.
   5.251 +            return (rvec1[:T], rvec2[:T])
   5.252 +
   5.253 +        def exchange(shares):
   5.254 +            """Exchange and (if possible) verify shares."""
   5.255 +            svec1, svec2 = shares
   5.256 +            pc = tuple(self.program_counter)
   5.257 +
   5.258 +            # We send our shares to the verifying players.
   5.259 +            for offset, (s1, s2) in enumerate(zip(svec1, svec2)):
   5.260 +                if T+1+offset != self.id:
   5.261 +                    self.protocols[T+1+offset].sendShare(pc, s1)
   5.262 +                    self.protocols[T+1+offset].sendShare(pc, s2)
   5.263 +
   5.264 +            if self.id > T:
   5.265 +                # The other players will send us their shares of si_1
   5.266 +                # and si_2 and we will verify it.
   5.267 +                si_1 = []
   5.268 +                si_2 = []
   5.269 +                for peer_id in inputters:
   5.270 +                    if self.id == peer_id:
   5.271 +                        si_1.append(Share(self, field, svec1[peer_id - T - 1]))
   5.272 +                        si_2.append(Share(self, field, svec2[peer_id - T - 1]))
   5.273 +                    else:
   5.274 +                        si_1.append(self._expect_share(peer_id, field))
   5.275 +                        si_2.append(self._expect_share(peer_id, field))
   5.276 +                result = gatherResults([gatherResults(si_1), gatherResults(si_2)])
   5.277 +                self.schedule_callback(result, verify)
   5.278 +                return result
   5.279 +            else:
   5.280 +                # We cannot verify anything, so we just return the
   5.281 +                # first T shares.
   5.282 +                return (rvec1[:T], rvec2[:T])
   5.283 +
   5.284 +        result = gather_shares([gather_shares(svec1[T:]), gather_shares(svec2[T:])])
   5.285 +        self.schedule_callback(result, exchange)
   5.286 +        return result
   5.287 +
   5.288 +    @increment_pc
   5.289 +    @preprocess("generate_triples")
   5.290 +    def get_triple(self, field):
   5.291 +        # This is a waste, but this function is only called if there
   5.292 +        # are no pre-processed triples left.
   5.293 +        count, result = self.generate_triples(field)
   5.294 +        result.addCallback(lambda triples: triples[0])
   5.295 +        return result
   5.296 +
   5.297 +    @increment_pc
   5.298 +    def generate_triples(self, field):
   5.299 +        """Generate multiplication triples.
   5.300 +
   5.301 +        These are random numbers *a*, *b*, and *c* such that ``c =
   5.302 +        ab``. This function can be used in pre-processing.
   5.303 +
   5.304 +        Returns a tuple with the number of triples generated and a
   5.305 +        Deferred which will yield a list of 3-tuples.
   5.306 +        """
   5.307 +        n = self.num_players
   5.308 +        t = self.threshold
   5.309 +        T = n - 2*t
   5.310 +
   5.311 +        def make_triple(shares):
   5.312 +            a_t, b_t, (r_t, r_2t) = shares
   5.313 +
   5.314 +            c_2t = []
   5.315 +            for i in range(T):
   5.316 +                # Multiply a[i] and b[i] without resharing.
   5.317 +                ci = gather_shares([a_t[i], b_t[i]])
   5.318 +                ci.addCallback(lambda (ai, bi): ai * bi)
   5.319 +                c_2t.append(ci)
   5.320 +
   5.321 +            d_2t = [c_2t[i] - r_2t[i] for i in range(T)]
   5.322 +            d = [self.open(d_2t[i], threshold=2*t) for i in range(T)]
   5.323 +            c_t = [r_t[i] + d[i] for i in range(T)]
   5.324 +            return zip(a_t, b_t, c_t)
   5.325 +
   5.326 +        single_a = self.single_share_random(T, t, field)
   5.327 +        single_b = self.single_share_random(T, t, field)
   5.328 +        double_c = self.double_share_random(T, t, 2*t, field)
   5.329 +
   5.330 +        result = gatherResults([single_a, single_b, double_c])
   5.331 +        self.schedule_callback(result, make_triple)
   5.332 +        return T, result
   5.333 +
   5.334 +    @increment_pc
   5.335 +    @preprocess("generate_triple")
   5.336 +    def prss_get_triple(self, field):
   5.337 +        count, result = self.prss_generate_triple(field)
   5.338 +        result.addCallback(lambda triples: triples[0])
   5.339 +        return result
   5.340 +
   5.341 +    @increment_pc
   5.342 +    def prss_generate_triple(self, field):
   5.343 +        """Generate a multiplication triple using PRSS.
   5.344 +
   5.345 +        These are random numbers *a*, *b*, and *c* such that ``c =
   5.346 +        ab``. This function can be used in pre-processing.
   5.347 +
   5.348 +        Returns a tuple with the number of triples generated (1) and a
   5.349 +        Deferred which will yield a singleton-list with a 3-tuple.
   5.350 +        """
   5.351 +        a_t = self.prss_share_random(field)
   5.352 +        b_t = self.prss_share_random(field)
   5.353 +        r_t, r_2t = self.prss_double_share(field)
   5.354 +
   5.355 +        # Multiply a and b without resharing.
   5.356 +        c_2t = gather_shares([a_t, b_t])
   5.357 +        c_2t.addCallback(lambda (a, b): a * b)
   5.358 +
   5.359 +        d_2t = c_2t - r_2t
   5.360 +        d = self.open(d_2t, threshold=2*self.threshold)
   5.361 +        c_t = r_t + d
   5.362 +        return 1, succeed([(a_t, b_t, c_t)])
   5.363 +
   5.364 +    @increment_pc
   5.365 +    def _broadcast(self, sender, message=None):
   5.366 +        """Perform a Bracha broadcast.
   5.367 +
   5.368 +        A Bracha broadcast is reliable against an active adversary
   5.369 +        corrupting up to t < n/3 of the players. For more details, see
   5.370 +        the paper "An asynchronous [(n-1)/3]-resilient consensus
   5.371 +        protocol" by G. Bracha in Proc. 3rd ACM Symposium on
   5.372 +        Principles of Distributed Computing, 1984, pages 154-162.
   5.373 +        """
   5.374 +
   5.375 +        result = Deferred()
   5.376 +        pc = tuple(self.program_counter)
   5.377 +        n = self.num_players
   5.378 +        t = self.threshold
   5.379 +
   5.380 +        # For each distinct message (and program counter) we save a
   5.381 +        # dictionary for each of the following variables. The reason
   5.382 +        # is that we need to count for each distinct message how many
   5.383 +        # echo and ready messages we have received.
   5.384 +
   5.385 +        bracha_echo = {}
   5.386 +        bracha_ready = {}
   5.387 +        bracha_sent_ready = {}
   5.388 +        bracha_delivered = {}
   5.389 +        
   5.390 +        def unsafe_broadcast(data_type, message):
   5.391 +            # Performs a regular broadcast without any guarantees. In
   5.392 +            # other words, it sends the message to each player except
   5.393 +            # for this one.
   5.394 +            for protocol in self.protocols.itervalues():
   5.395 +                protocol.sendData(pc, data_type, message)
   5.396 +
   5.397 +        def echo_received(message, peer_id):
   5.398 +            # This is called when we receive an echo message. It
   5.399 +            # updates the echo count for the message and enters the
   5.400 +            # ready state if the count is high enough.
   5.401 +            ids = bracha_echo.setdefault(message, [])
   5.402 +            ready = bracha_sent_ready.setdefault(message, False)
   5.403 +
   5.404 +            if peer_id not in ids:
   5.405 +                ids.append(peer_id)
   5.406 +                if len(ids) >= ceil((n+t+1)/2) and not ready:
   5.407 +                    bracha_sent_ready[message] = True
   5.408 +                    unsafe_broadcast("ready", message)
   5.409 +                    ready_received(message, self.id)
   5.410 +
   5.411 +        def ready_received(message, peer_id):
   5.412 +            # This is called when we receive a ready message. It
   5.413 +            # updates the ready count for the message. Depending on
   5.414 +            # the count, we may either stay in the same state or enter
   5.415 +            # the ready or delivered state.
   5.416 +            ids = bracha_ready.setdefault(message, [])
   5.417 +            ready = bracha_sent_ready.setdefault(message, False)
   5.418 +            delivered = bracha_delivered.setdefault(message, False)
   5.419 +            if peer_id not in ids:
   5.420 +                ids.append(peer_id)
   5.421 +                if len(ids) == t+1 and not ready:
   5.422 +                    bracha_sent_ready[message] = True
   5.423 +                    unsafe_broadcast("ready", message)
   5.424 +                    ready_received(message, self.id)
   5.425 +
   5.426 +                elif len(ids) == 2*t+1 and not delivered:
   5.427 +                    bracha_delivered[message] = True
   5.428 +                    result.callback(message)
   5.429 +
   5.430 +        def send_received(message):
   5.431 +            # This is called when we receive a send message. We react
   5.432 +            # by sending an echo message to each player. Since the
   5.433 +            # unsafe broadcast doesn't send a message to this player,
   5.434 +            # we simulate it by calling the echo_received function.
   5.435 +            unsafe_broadcast("echo", message)
   5.436 +            echo_received(message, self.id)
   5.437 +
   5.438 +
   5.439 +        # In the following we prepare to handle a send message from
   5.440 +        # the sender and at most one echo and one ready message from
   5.441 +        # each player.
   5.442 +        d_send = Deferred().addCallback(send_received)
   5.443 +        self._expect_data(sender, "send", d_send)
   5.444 +
   5.445 +        for peer_id in self.players:
   5.446 +            if peer_id != self.id:
   5.447 +                d_echo = Deferred().addCallback(echo_received, peer_id)
   5.448 +                self._expect_data(peer_id, "echo", d_echo)
   5.449 +
   5.450 +                d_ready = Deferred().addCallback(ready_received, peer_id)
   5.451 +                self._expect_data(peer_id, "ready", d_ready)
   5.452 +
   5.453 +        # If this player is the sender, we transmit a send message to
   5.454 +        # each player. We send one to this player by calling the
   5.455 +        # send_received function.
   5.456 +        if self.id == sender:
   5.457 +            unsafe_broadcast("send", message)
   5.458 +            send_received(message)
   5.459 +
   5.460 +        return result
   5.461 +
   5.462 +    @increment_pc
   5.463 +    def broadcast(self, senders, message=None):
   5.464 +        """Perform one or more Bracha broadcast(s).
   5.465 +
   5.466 +        The list of *senders* given will determine the subset of players
   5.467 +        who wish to broadcast a message. If this player wishes to
   5.468 +        broadcast, its ID must be in the list of senders and the
   5.469 +        optional *message* parameter must be used.
   5.470 +
   5.471 +        If the list of senders consists only of a single sender, the
   5.472 +        result will be a single element, otherwise it will be a list.
   5.473 +
   5.474 +        A Bracha broadcast is reliable against an active adversary
   5.475 +        corrupting up to t < n/3 of the players. For more details, see
   5.476 +        the paper "An asynchronous [(n-1)/3]-resilient consensus
   5.477 +        protocol" by G. Bracha in Proc. 3rd ACM Symposium on
   5.478 +        Principles of Distributed Computing, 1984, pages 154-162.
   5.479 +        """
   5.480 +        assert message is None or self.id in senders
   5.481 +
   5.482 +        result = []
   5.483 +
   5.484 +        for sender in senders:
   5.485 +            if sender == self.id:
   5.486 +                result.append(self._broadcast(sender, message))
   5.487 +            else:
   5.488 +                result.append(self._broadcast(sender))
   5.489 +
   5.490 +        if len(result) == 1:
   5.491 +            return result[0]
   5.492 +
   5.493 +        return result
     6.1 --- a/viff/comparison.py	Mon Sep 15 14:30:20 2008 +0200
     6.2 +++ b/viff/comparison.py	Mon Sep 15 15:46:50 2008 +0200
     6.3 @@ -26,7 +26,7 @@
     6.4  
     6.5  from viff.util import rand
     6.6  from viff.runtime import Runtime, Share, gather_shares, increment_pc
     6.7 -from viff.runtime import ActiveRuntime
     6.8 +from viff.active import ActiveRuntime
     6.9  from viff.field import GF256, FieldElement
    6.10  
    6.11  
     7.1 --- a/viff/runtime.py	Mon Sep 15 14:30:20 2008 +0200
     7.2 +++ b/viff/runtime.py	Mon Sep 15 15:46:50 2008 +0200
     7.3 @@ -36,13 +36,11 @@
     7.4  import time
     7.5  import marshal
     7.6  from optparse import OptionParser, OptionGroup
     7.7 -from math import ceil
     7.8  from collections import deque
     7.9  
    7.10  from viff import shamir
    7.11  from viff.prss import prss, prss_lsb, prss_zero
    7.12  from viff.field import GF256, FieldElement
    7.13 -from viff.matrix import Matrix, hyper
    7.14  from viff.util import wrapper, rand
    7.15  
    7.16  from twisted.internet import reactor
    7.17 @@ -1067,467 +1065,6 @@
    7.18          return result
    7.19  
    7.20  
    7.21 -class ActiveRuntime(Runtime):
    7.22 -    """A runtime secure against active adversaries.
    7.23 -
    7.24 -    This class currently inherits most of its functionality from the
    7.25 -    normal :class:`Runtime` class and is thus **not** yet secure.
    7.26 -    """
    7.27 -
    7.28 -    def __init__(self, player, threshold, options=None):
    7.29 -        """Initialize runtime."""
    7.30 -
    7.31 -        #: A hyper-invertible matrix.
    7.32 -        #:
    7.33 -        #: It should be suitable for :attr:`num_players` players, but
    7.34 -        #: since we don't know the total number of players yet, we set
    7.35 -        #: it to :const:`None` here and update it as necessary.
    7.36 -        self._hyper = None
    7.37 -        Runtime.__init__(self, player, threshold, options)
    7.38 -
    7.39 -    @increment_pc
    7.40 -    def mul(self, share_x, share_y):
    7.41 -        """Multiplication of shares.
    7.42 -
    7.43 -        Preprocessing: 1 multiplication triple.
    7.44 -        Communication: 2 openings.
    7.45 -        """
    7.46 -        assert isinstance(share_x, Share) or isinstance(share_y, Share), \
    7.47 -            "At least one of share_x and share_y must be a Share."
    7.48 -
    7.49 -        if not isinstance(share_x, Share):
    7.50 -            # Then share_y must be a Share => local multiplication. We
    7.51 -            # clone first to avoid changing share_y.
    7.52 -            result = share_y.clone()
    7.53 -            result.addCallback(lambda y: share_x * y)
    7.54 -            return result
    7.55 -        if not isinstance(share_y, Share):
    7.56 -            # Likewise when share_y is a constant.
    7.57 -            result = share_x.clone()
    7.58 -            result.addCallback(lambda x: x * share_y)
    7.59 -            return result
    7.60 -
    7.61 -        # At this point both share_x and share_y must be Share
    7.62 -        # objects. We multiply them via a multiplication triple.
    7.63 -        def finish_mul(triple):
    7.64 -            a, b, c = triple
    7.65 -            d = self.open(share_x - a)
    7.66 -            e = self.open(share_y - b)
    7.67 -
    7.68 -            # TODO: We ought to be able to simply do
    7.69 -            #
    7.70 -            #   return d*e + d*y + e*x + c
    7.71 -            #
    7.72 -            # but that leads to infinite recursion since d and e are
    7.73 -            # Shares, not FieldElements. So we have to do a bit more
    7.74 -            # work... The following callback also leads to recursion, but
    7.75 -            # only one level since d and e are FieldElements now, which
    7.76 -            # means that we return in the above if statements.
    7.77 -            result = gather_shares([d, e])
    7.78 -            result.addCallback(lambda (d,e): d*e + d*b + e*a + c)
    7.79 -            return result
    7.80 -
    7.81 -        # This will be the result, a Share object.
    7.82 -        result = Share(self, share_x.field)
    7.83 -        # This is the Deferred we will do processing on.
    7.84 -        triple = self.prss_get_triple(share_x.field)
    7.85 -        self.schedule_callback(triple, finish_mul)
    7.86 -        # We add the result to the chains in triple.
    7.87 -        triple.chainDeferred(result)
    7.88 -        return result
    7.89 -
    7.90 -    @increment_pc
    7.91 -    def single_share_random(self, T, degree, field):
    7.92 -        """Share a random secret.
    7.93 -
    7.94 -        The guarantee is that a number of shares are made and out of
    7.95 -        those, the *T* that are returned by this method will be
    7.96 -        correct sharings of a random number using *degree* as the
    7.97 -        polynomial degree.
    7.98 -        """
    7.99 -        # TODO: Move common code between single_share and
   7.100 -        # double_share_random out to their own methods.
   7.101 -        inputters = range(1, self.num_players + 1)
   7.102 -        if self._hyper is None:
   7.103 -            self._hyper = hyper(self.num_players, field)
   7.104 -
   7.105 -        # Generate a random element.
   7.106 -        si = rand.randint(0, field.modulus - 1)
   7.107 -
   7.108 -        # Every player shares the random value with two thresholds.
   7.109 -        shares = self.shamir_share(inputters, field, si, degree)
   7.110 -
   7.111 -        # Turn the shares into a column vector.
   7.112 -        svec = Matrix([shares]).transpose()
   7.113 -
   7.114 -        # Apply the hyper-invertible matrix to svec1 and svec2.
   7.115 -        rvec = (self._hyper * svec)
   7.116 -
   7.117 -        # Get back to normal lists of shares.
   7.118 -        svec = svec.transpose().rows[0]
   7.119 -        rvec = rvec.transpose().rows[0]
   7.120 -
   7.121 -        def verify(shares):
   7.122 -            """Verify shares.
   7.123 -
   7.124 -            It is checked that they correspond to polynomial of the
   7.125 -            expected degree.
   7.126 -
   7.127 -            If the verification succeeds, the T shares are returned,
   7.128 -            otherwise the errback is called.
   7.129 -            """
   7.130 -            # TODO: This is necessary since shamir.recombine expects
   7.131 -            # to receive a list of *pairs* of field elements.
   7.132 -            shares = map(lambda (i, s): (field(i+1), s), enumerate(shares))
   7.133 -
   7.134 -            # Verify the sharings. If any of the assertions fail and
   7.135 -            # raise an exception, the errbacks will be called on the
   7.136 -            # share returned by single_share_random.
   7.137 -            assert shamir.verify_sharing(shares, degree), \
   7.138 -                   "Could not verify %s, degree %d" % (shares, degree)
   7.139 -
   7.140 -            # If we reach this point the n - T shares were verified
   7.141 -            # and we can safely return the first T shares.
   7.142 -            return rvec[:T]
   7.143 -
   7.144 -        def exchange(svec):
   7.145 -            """Exchange and (if possible) verify shares."""
   7.146 -            pc = tuple(self.program_counter)
   7.147 -
   7.148 -            # We send our shares to the verifying players.
   7.149 -            for offset, share in enumerate(svec):
   7.150 -                if T+1+offset != self.id:
   7.151 -                    self.protocols[T+1+offset].sendShare(pc, share)
   7.152 -
   7.153 -            if self.id > T:
   7.154 -                # The other players will send us their shares of si_1
   7.155 -                # and si_2 and we will verify it.
   7.156 -                si = []
   7.157 -                for peer_id in inputters:
   7.158 -                    if self.id == peer_id:
   7.159 -                        si.append(Share(self, field, svec[peer_id - T - 1]))
   7.160 -                    else:
   7.161 -                        si.append(self._expect_share(peer_id, field))
   7.162 -                result = gatherResults(si)
   7.163 -                self.schedule_callback(result, verify)
   7.164 -                return result
   7.165 -            else:
   7.166 -                # We cannot verify anything, so we just return the
   7.167 -                # first T shares.
   7.168 -                return rvec[:T]
   7.169 -
   7.170 -        result = gather_shares(svec[T:])
   7.171 -        self.schedule_callback(result, exchange)
   7.172 -        return result
   7.173 -
   7.174 -    @increment_pc
   7.175 -    def double_share_random(self, T, d1, d2, field):
   7.176 -        """Double-share a random secret using two polynomials.
   7.177 -
   7.178 -        The guarantee is that a number of shares are made and out of
   7.179 -        those, the *T* that are returned by this method will be correct
   7.180 -        double-sharings of a random number using *d1* and *d2* as the
   7.181 -        polynomial degrees.
   7.182 -        """
   7.183 -        inputters = range(1, self.num_players + 1)
   7.184 -        if self._hyper is None:
   7.185 -            self._hyper = hyper(self.num_players, field)
   7.186 -
   7.187 -        # Generate a random element.
   7.188 -        si = rand.randint(0, field.modulus - 1)
   7.189 -
   7.190 -        # Every player shares the random value with two thresholds.
   7.191 -        d1_shares = self.shamir_share(inputters, field, si, d1)
   7.192 -        d2_shares = self.shamir_share(inputters, field, si, d2)
   7.193 -
   7.194 -        # Turn the shares into a column vector.
   7.195 -        svec1 = Matrix([d1_shares]).transpose()
   7.196 -        svec2 = Matrix([d2_shares]).transpose()
   7.197 -
   7.198 -        # Apply the hyper-invertible matrix to svec1 and svec2.
   7.199 -        rvec1 = (self._hyper * svec1)
   7.200 -        rvec2 = (self._hyper * svec2)
   7.201 -
   7.202 -        # Get back to normal lists of shares.
   7.203 -        svec1 = svec1.transpose().rows[0]
   7.204 -        svec2 = svec2.transpose().rows[0]
   7.205 -        rvec1 = rvec1.transpose().rows[0]
   7.206 -        rvec2 = rvec2.transpose().rows[0]
   7.207 -
   7.208 -        def verify(shares):
   7.209 -            """Verify shares.
   7.210 -
   7.211 -            It is checked that they correspond to polynomial of the
   7.212 -            expected degrees and that they can be recombined to the
   7.213 -            same value.
   7.214 -
   7.215 -            If the verification succeeds, the T double shares are
   7.216 -            returned, otherwise the errback is called.
   7.217 -            """
   7.218 -            si_1, si_2 = shares
   7.219 -
   7.220 -            # TODO: This is necessary since shamir.recombine expects
   7.221 -            # to receive a list of *pairs* of field elements.
   7.222 -            si_1 = map(lambda (i, s): (field(i+1), s), enumerate(si_1))
   7.223 -            si_2 = map(lambda (i, s): (field(i+1), s), enumerate(si_2))
   7.224 -
   7.225 -            # Verify the sharings. If any of the assertions fail and
   7.226 -            # raise an exception, the errbacks will be called on the
   7.227 -            # double share returned by double_share_random.
   7.228 -            assert shamir.verify_sharing(si_1, d1), \
   7.229 -                   "Could not verify %s, degree %d" % (si_1, d1)
   7.230 -            assert shamir.verify_sharing(si_2, d2), \
   7.231 -                   "Could not verify %s, degree %d" % (si_2, d2)
   7.232 -            assert shamir.recombine(si_1[:d1+1]) == shamir.recombine(si_2[:d2+1]), \
   7.233 -                "Shares do not recombine to the same value"
   7.234 -
   7.235 -            # If we reach this point the n - T shares were verified
   7.236 -            # and we can safely return the first T shares.
   7.237 -            return (rvec1[:T], rvec2[:T])
   7.238 -
   7.239 -        def exchange(shares):
   7.240 -            """Exchange and (if possible) verify shares."""
   7.241 -            svec1, svec2 = shares
   7.242 -            pc = tuple(self.program_counter)
   7.243 -
   7.244 -            # We send our shares to the verifying players.
   7.245 -            for offset, (s1, s2) in enumerate(zip(svec1, svec2)):
   7.246 -                if T+1+offset != self.id:
   7.247 -                    self.protocols[T+1+offset].sendShare(pc, s1)
   7.248 -                    self.protocols[T+1+offset].sendShare(pc, s2)
   7.249 -
   7.250 -            if self.id > T:
   7.251 -                # The other players will send us their shares of si_1
   7.252 -                # and si_2 and we will verify it.
   7.253 -                si_1 = []
   7.254 -                si_2 = []
   7.255 -                for peer_id in inputters:
   7.256 -                    if self.id == peer_id:
   7.257 -                        si_1.append(Share(self, field, svec1[peer_id - T - 1]))
   7.258 -                        si_2.append(Share(self, field, svec2[peer_id - T - 1]))
   7.259 -                    else:
   7.260 -                        si_1.append(self._expect_share(peer_id, field))
   7.261 -                        si_2.append(self._expect_share(peer_id, field))
   7.262 -                result = gatherResults([gatherResults(si_1), gatherResults(si_2)])
   7.263 -                self.schedule_callback(result, verify)
   7.264 -                return result
   7.265 -            else:
   7.266 -                # We cannot verify anything, so we just return the
   7.267 -                # first T shares.
   7.268 -                return (rvec1[:T], rvec2[:T])
   7.269 -
   7.270 -        result = gather_shares([gather_shares(svec1[T:]), gather_shares(svec2[T:])])
   7.271 -        self.schedule_callback(result, exchange)
   7.272 -        return result
   7.273 -
   7.274 -    @increment_pc
   7.275 -    @preprocess("generate_triples")
   7.276 -    def get_triple(self, field):
   7.277 -        # This is a waste, but this function is only called if there
   7.278 -        # are no pre-processed triples left.
   7.279 -        count, result = self.generate_triples(field)
   7.280 -        result.addCallback(lambda triples: triples[0])
   7.281 -        return result
   7.282 -
   7.283 -    @increment_pc
   7.284 -    def generate_triples(self, field):
   7.285 -        """Generate multiplication triples.
   7.286 -
   7.287 -        These are random numbers *a*, *b*, and *c* such that ``c =
   7.288 -        ab``. This function can be used in pre-processing.
   7.289 -
   7.290 -        Returns a tuple with the number of triples generated and a
   7.291 -        Deferred which will yield a list of 3-tuples.
   7.292 -        """
   7.293 -        n = self.num_players
   7.294 -        t = self.threshold
   7.295 -        T = n - 2*t
   7.296 -
   7.297 -        def make_triple(shares):
   7.298 -            a_t, b_t, (r_t, r_2t) = shares
   7.299 -
   7.300 -            c_2t = []
   7.301 -            for i in range(T):
   7.302 -                # Multiply a[i] and b[i] without resharing.
   7.303 -                ci = gather_shares([a_t[i], b_t[i]])
   7.304 -                ci.addCallback(lambda (ai, bi): ai * bi)
   7.305 -                c_2t.append(ci)
   7.306 -
   7.307 -            d_2t = [c_2t[i] - r_2t[i] for i in range(T)]
   7.308 -            d = [self.open(d_2t[i], threshold=2*t) for i in range(T)]
   7.309 -            c_t = [r_t[i] + d[i] for i in range(T)]
   7.310 -            return zip(a_t, b_t, c_t)
   7.311 -
   7.312 -        single_a = self.single_share_random(T, t, field)
   7.313 -        single_b = self.single_share_random(T, t, field)
   7.314 -        double_c = self.double_share_random(T, t, 2*t, field)
   7.315 -
   7.316 -        result = gatherResults([single_a, single_b, double_c])
   7.317 -        self.schedule_callback(result, make_triple)
   7.318 -        return T, result
   7.319 -
   7.320 -    @increment_pc
   7.321 -    @preprocess("prss_generate_triple")
   7.322 -    def prss_get_triple(self, field):
   7.323 -        count, result = self.prss_generate_triple(field)
   7.324 -        result.addCallback(lambda triples: triples[0])
   7.325 -        return result
   7.326 -
   7.327 -    @increment_pc
   7.328 -    def prss_generate_triple(self, field):
   7.329 -        """Generate a multiplication triple using PRSS.
   7.330 -
   7.331 -        These are random numbers *a*, *b*, and *c* such that ``c =
   7.332 -        ab``. This function can be used in pre-processing.
   7.333 -
   7.334 -        Returns a tuple with the number of triples generated (1) and a
   7.335 -        Deferred which will yield a singleton-list with a 3-tuple.
   7.336 -        """
   7.337 -        a_t = self.prss_share_random(field)
   7.338 -        b_t = self.prss_share_random(field)
   7.339 -        r_t, r_2t = self.prss_double_share(field)
   7.340 -
   7.341 -        # Multiply a and b without resharing.
   7.342 -        c_2t = gather_shares([a_t, b_t])
   7.343 -        c_2t.addCallback(lambda (a, b): a * b)
   7.344 -
   7.345 -        d_2t = c_2t - r_2t
   7.346 -        d = self.open(d_2t, threshold=2*self.threshold)
   7.347 -        c_t = r_t + d
   7.348 -        return 1, succeed([(a_t, b_t, c_t)])
   7.349 -
   7.350 -    @increment_pc
   7.351 -    def _broadcast(self, sender, message=None):
   7.352 -        """Perform a Bracha broadcast.
   7.353 -
   7.354 -        A Bracha broadcast is reliable against an active adversary
   7.355 -        corrupting up to t < n/3 of the players. For more details, see
   7.356 -        the paper "An asynchronous [(n-1)/3]-resilient consensus
   7.357 -        protocol" by G. Bracha in Proc. 3rd ACM Symposium on
   7.358 -        Principles of Distributed Computing, 1984, pages 154-162.
   7.359 -        """
   7.360 -
   7.361 -        result = Deferred()
   7.362 -        pc = tuple(self.program_counter)
   7.363 -        n = self.num_players
   7.364 -        t = self.threshold
   7.365 -
   7.366 -        # For each distinct message (and program counter) we save a
   7.367 -        # dictionary for each of the following variables. The reason
   7.368 -        # is that we need to count for each distinct message how many
   7.369 -        # echo and ready messages we have received.
   7.370 -
   7.371 -        bracha_echo = {}
   7.372 -        bracha_ready = {}
   7.373 -        bracha_sent_ready = {}
   7.374 -        bracha_delivered = {}
   7.375 -        
   7.376 -        def unsafe_broadcast(data_type, message):
   7.377 -            # Performs a regular broadcast without any guarantees. In
   7.378 -            # other words, it sends the message to each player except
   7.379 -            # for this one.
   7.380 -            for protocol in self.protocols.itervalues():
   7.381 -                protocol.sendData(pc, data_type, message)
   7.382 -
   7.383 -        def echo_received(message, peer_id):
   7.384 -            # This is called when we receive an echo message. It
   7.385 -            # updates the echo count for the message and enters the
   7.386 -            # ready state if the count is high enough.
   7.387 -            ids = bracha_echo.setdefault(message, [])
   7.388 -            ready = bracha_sent_ready.setdefault(message, False)
   7.389 -
   7.390 -            if peer_id not in ids:
   7.391 -                ids.append(peer_id)
   7.392 -                if len(ids) >= ceil((n+t+1)/2) and not ready:
   7.393 -                    bracha_sent_ready[message] = True
   7.394 -                    unsafe_broadcast("ready", message)
   7.395 -                    ready_received(message, self.id)
   7.396 -
   7.397 -        def ready_received(message, peer_id):
   7.398 -            # This is called when we receive a ready message. It
   7.399 -            # updates the ready count for the message. Depending on
   7.400 -            # the count, we may either stay in the same state or enter
   7.401 -            # the ready or delivered state.
   7.402 -            ids = bracha_ready.setdefault(message, [])
   7.403 -            ready = bracha_sent_ready.setdefault(message, False)
   7.404 -            delivered = bracha_delivered.setdefault(message, False)
   7.405 -            if peer_id not in ids:
   7.406 -                ids.append(peer_id)
   7.407 -                if len(ids) == t+1 and not ready:
   7.408 -                    bracha_sent_ready[message] = True
   7.409 -                    unsafe_broadcast("ready", message)
   7.410 -                    ready_received(message, self.id)
   7.411 -
   7.412 -                elif len(ids) == 2*t+1 and not delivered:
   7.413 -                    bracha_delivered[message] = True
   7.414 -                    result.callback(message)
   7.415 -
   7.416 -        def send_received(message):
   7.417 -            # This is called when we receive a send message. We react
   7.418 -            # by sending an echo message to each player. Since the
   7.419 -            # unsafe broadcast doesn't send a message to this player,
   7.420 -            # we simulate it by calling the echo_received function.
   7.421 -            unsafe_broadcast("echo", message)
   7.422 -            echo_received(message, self.id)
   7.423 -
   7.424 -
   7.425 -        # In the following we prepare to handle a send message from
   7.426 -        # the sender and at most one echo and one ready message from
   7.427 -        # each player.
   7.428 -        d_send = Deferred().addCallback(send_received)
   7.429 -        self._expect_data(sender, "send", d_send)
   7.430 -
   7.431 -        for peer_id in self.players:
   7.432 -            if peer_id != self.id:
   7.433 -                d_echo = Deferred().addCallback(echo_received, peer_id)
   7.434 -                self._expect_data(peer_id, "echo", d_echo)
   7.435 -
   7.436 -                d_ready = Deferred().addCallback(ready_received, peer_id)
   7.437 -                self._expect_data(peer_id, "ready", d_ready)
   7.438 -
   7.439 -        # If this player is the sender, we transmit a send message to
   7.440 -        # each player. We send one to this player by calling the
   7.441 -        # send_received function.
   7.442 -        if self.id == sender:
   7.443 -            unsafe_broadcast("send", message)
   7.444 -            send_received(message)
   7.445 -
   7.446 -        return result
   7.447 -
   7.448 -    @increment_pc
   7.449 -    def broadcast(self, senders, message=None):
   7.450 -        """Perform one or more Bracha broadcast(s).
   7.451 -
   7.452 -        The list of *senders* given will determine the subset of players
   7.453 -        who wish to broadcast a message. If this player wishes to
   7.454 -        broadcast, its ID must be in the list of senders and the
   7.455 -        optional *message* parameter must be used.
   7.456 -
   7.457 -        If the list of senders consists only of a single sender, the
   7.458 -        result will be a single element, otherwise it will be a list.
   7.459 -
   7.460 -        A Bracha broadcast is reliable against an active adversary
   7.461 -        corrupting up to t < n/3 of the players. For more details, see
   7.462 -        the paper "An asynchronous [(n-1)/3]-resilient consensus
   7.463 -        protocol" by G. Bracha in Proc. 3rd ACM Symposium on
   7.464 -        Principles of Distributed Computing, 1984, pages 154-162.
   7.465 -        """
   7.466 -        assert message is None or self.id in senders
   7.467 -
   7.468 -        result = []
   7.469 -
   7.470 -        for sender in senders:
   7.471 -            if sender == self.id:
   7.472 -                result.append(self._broadcast(sender, message))
   7.473 -            else:
   7.474 -                result.append(self._broadcast(sender))
   7.475 -
   7.476 -        if len(result) == 1:
   7.477 -            return result[0]
   7.478 -
   7.479 -        return result
   7.480 -
   7.481 -
   7.482  def create_runtime(id, players, threshold, options=None, runtime_class=Runtime):
   7.483      """Create a :class:`Runtime` and connect to the other players.
   7.484  
     8.1 --- a/viff/test/test_active_runtime.py	Mon Sep 15 14:30:20 2008 +0200
     8.2 +++ b/viff/test/test_active_runtime.py	Mon Sep 15 15:46:50 2008 +0200
     8.3 @@ -20,7 +20,8 @@
     8.4  from twisted.internet.defer import gatherResults
     8.5  
     8.6  from viff.test.util import RuntimeTestCase, protocol, BinaryOperatorTestCase
     8.7 -from viff.runtime import ActiveRuntime, Share
     8.8 +from viff.runtime import Share
     8.9 +from viff.active import ActiveRuntime
    8.10  
    8.11  
    8.12  class MulTest(BinaryOperatorTestCase, RuntimeTestCase):