viff

changeset 1221:53d198cdf14c

An implementation of a broadcast mixin based on hashing of the received messages.
author Janus Dam Nielsen <janus.nielsen@alexandra.dk>
date Tue, 06 Oct 2009 10:05:24 +0200
parents 5a815629d825
children 7fe8f5835b61
files viff/constants.py viff/hash_broadcast.py viff/test/test_hash_broadcast.py
diffstat 3 files changed, 354 insertions(+), 0 deletions(-) [+]
line diff
     1.1 --- a/viff/constants.py	Tue Oct 06 10:05:24 2009 +0200
     1.2 +++ b/viff/constants.py	Tue Oct 06 10:05:24 2009 +0200
     1.3 @@ -25,3 +25,10 @@
     1.4  READY    = 2
     1.5  SEND     = 3
     1.6  PAILLIER = 4
     1.7 +TEXT     = 5
     1.8 +
     1.9 +# Used by the HashBroadcastMixin
    1.10 +INCONSISTENTHASH = 6
    1.11 +OK               = 7
    1.12 +HASH             = 8
    1.13 +SIGNAL           = 9
     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/viff/hash_broadcast.py	Tue Oct 06 10:05:24 2009 +0200
     2.3 @@ -0,0 +1,166 @@
     2.4 +#!/usr/bin/env python
     2.5 +
     2.6 +# Copyright 2009 VIFF Development Team.
     2.7 +#
     2.8 +# This file is part of VIFF, the Virtual Ideal Functionality Framework.
     2.9 +#
    2.10 +# VIFF is free software: you can redistribute it and/or modify it
    2.11 +# under the terms of the GNU Lesser General Public License (LGPL) as
    2.12 +# published by the Free Software Foundation, either version 3 of the
    2.13 +# License, or (at your option) any later version.
    2.14 +#
    2.15 +# VIFF is distributed in the hope that it will be useful, but WITHOUT
    2.16 +# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
    2.17 +# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
    2.18 +# Public License for more details.
    2.19 +#
    2.20 +# You should have received a copy of the GNU Lesser General Public
    2.21 +# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
    2.22 +
    2.23 +from twisted.internet.defer import gatherResults, Deferred, DeferredList
    2.24 +
    2.25 +from hashlib import sha1
    2.26 +from viff.constants import TEXT, INCONSISTENTHASH, OK, HASH, SIGNAL
    2.27 +
    2.28 +error_msg = "Player %i, has received an inconsistent hash %s."
    2.29 +
    2.30 +class InconsistentHashException(Exception):
    2.31 +    pass
    2.32 +
    2.33 +class HashBroadcastMixin:
    2.34 +    """A non-consistent broadcast scheme mainly useful for full threshold security.
    2.35 +
    2.36 +    A value is send using `send_value` and when received a hash is generated and
    2.37 +    exchanged among the receivers. If a receiver receives a hash which is not equal
    2.38 +    to the one he generated, then he sends an error signal to the others and 
    2.39 +    they stop the computation. Else he sends an ok signal and the computation continues."""
    2.40 +
    2.41 +    def _send_message(self, pc, sender, receivers, message):
    2.42 +        for peer_id in receivers:
    2.43 +            self.protocols[peer_id].sendData(pc, TEXT, message)
    2.44 +
    2.45 +    def _receive_broadcast(self, pc, unique_pc, sender, receivers):
    2.46 +        # The result.
    2.47 +        result = Deferred()
    2.48 +        # The message store.
    2.49 +        message = []
    2.50 +        # The hash store
    2.51 +        g_hashes = {}
    2.52 +        # The signal store
    2.53 +        signals = {}
    2.54 +
    2.55 +        def signal_received(signal, peer_id, message, num_receivers, hashes, signals):
    2.56 +            # Store the signal.
    2.57 +            signals[peer_id] = long(signal)
    2.58 +            # If all signals are received then check if they are OK or INCONSISTENTHASH.
    2.59 +            if num_receivers == len(signals.keys()):
    2.60 +                s = reduce(lambda x, y: OK if OK == y else INCONSISTENTHASH, signals.values())
    2.61 +                if OK == s:
    2.62 +                    # Make the result ready.
    2.63 +                    result.callback(message[0])
    2.64 +                else:
    2.65 +                    raise InconsistentHashException(error_msg % (self.id, hashes))
    2.66 +
    2.67 +        def hash_received(h, unique_pc, peer_id, receivers, a_hashes):
    2.68 +            # Store the hash.
    2.69 +            a_hashes[peer_id] = h
    2.70 +            # If we have received a hash from everybody, then compute the signal and send it.
    2.71 +            if len(receivers) == len(a_hashes.keys()):
    2.72 +                signal = OK
    2.73 +                # First we check if the hashes we received are equal to the hash we computed ourselves.
    2.74 +                for peer_id in receivers:
    2.75 +                    signal = signal if a_hashes[peer_id] == a_hashes[self.id] else INCONSISTENTHASH
    2.76 +                # Then we send the SAME signal to everybody. 
    2.77 +                for peer_id in receivers:
    2.78 +                    self.protocols[peer_id].sendData(unique_pc, SIGNAL, str(signal))           
    2.79 +            # The return value does not matter.
    2.80 +            return None
    2.81 +
    2.82 +        def message_received(m, unique_pc, message, receivers, hashes):
    2.83 +            # Store the message.
    2.84 +            message.append(m)
    2.85 +            # Compute hash of message.
    2.86 +            h = sha1(m).hexdigest()
    2.87 +            # Store hash.
    2.88 +            hashes[self.id] = h
    2.89 +            # Send the hash to all receivers.
    2.90 +            for peer_id in receivers:
    2.91 +                self.protocols[peer_id].sendData(unique_pc, HASH, str(h))
    2.92 +
    2.93 +        # Set up receivers for hashes and signals.
    2.94 +        # Note, we use the unique_pc to avoid data to cross method invocation boundaries.
    2.95 +        for peer_id in receivers:
    2.96 +            d_hash = Deferred().addCallbacks(hash_received,
    2.97 +                                             self.error_handler, 
    2.98 +                                             callbackArgs=(unique_pc, peer_id, receivers, g_hashes))
    2.99 +            self._expect_data_with_pc(unique_pc, peer_id, HASH, d_hash)
   2.100 +            d_signal = Deferred().addCallbacks(signal_received, 
   2.101 +                                               self.error_handler, 
   2.102 +                                               callbackArgs=(peer_id, message, len(receivers), g_hashes, signals))
   2.103 +            self._expect_data_with_pc(unique_pc, peer_id, SIGNAL, d_signal)
   2.104 +
   2.105 +        # Set up receiving of the message.
   2.106 +        d_message = Deferred().addCallbacks(message_received, 
   2.107 +                                            self.error_handler, 
   2.108 +                                            callbackArgs=(unique_pc, message, receivers, g_hashes))
   2.109 +        self._expect_data(sender, TEXT, d_message)
   2.110 +        return result
   2.111 +
   2.112 +
   2.113 +    def broadcast(self, senders, receivers, message=None):
   2.114 +        """Broadcast the messeage from senders to receivers.
   2.115 +
   2.116 +        Returns a list of deferreds if the calling player is among 
   2.117 +        the receivers and there are multiple senders.
   2.118 +        Returns a single element if there is only on sender, or the 
   2.119 +        calling player is among the senders only.
   2.120 +
   2.121 +        The order of the resulting list is guaranteed to be the same order 
   2.122 +        as the list of senders.
   2.123 +
   2.124 +        Senders and receivers should be lists containing the id of the senders 
   2.125 +        and receivers, respectively.
   2.126 +
   2.127 +        Note: You send implicitly to your self."""
   2.128 +        assert message is None or self.id in senders
   2.129 +
   2.130 +        self.program_counter[-1] += 1
   2.131 +
   2.132 +        pc = tuple(self.program_counter)
   2.133 +        if (self.id in receivers or self.id in senders):
   2.134 +            results = [None] * len(senders)
   2.135 +        else:
   2.136 +            results = []
   2.137 +
   2.138 +        if self.id in senders:
   2.139 +            self._send_message(pc, self.id, receivers, message)
   2.140 +
   2.141 +        if self.id in receivers:
   2.142 +            for x in xrange(len(senders)):
   2.143 +                sender = senders[x]
   2.144 +                new_pc = list(self.program_counter)
   2.145 +                new_pc.append(x)
   2.146 +                results[x] = self._receive_broadcast(pc, tuple(new_pc), sender, receivers)
   2.147 +
   2.148 +        if self.id in senders and self.id not in receivers:
   2.149 +            d = Deferred()
   2.150 +            d.callback(message)
   2.151 +            results = [d]
   2.152 +
   2.153 +        self.program_counter[-1] += 1
   2.154 +
   2.155 +        if len(results) == 1:
   2.156 +            return results[0]
   2.157 +
   2.158 +        return results
   2.159 +          
   2.160 +    def list_str(self, s):
   2.161 +        ls = []
   2.162 +        for x in s[1:-1].split(','):
   2.163 +            x = x.strip()
   2.164 +            ls.append(str(x)[1:-1])
   2.165 +        return ls
   2.166 +
   2.167 +    def error_handler(self, ex):
   2.168 +        print "Error: ", ex
   2.169 +        return ex
     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/viff/test/test_hash_broadcast.py	Tue Oct 06 10:05:24 2009 +0200
     3.3 @@ -0,0 +1,181 @@
     3.4 +# Copyright 2009 VIFF Development Team.
     3.5 +#
     3.6 +# This file is part of VIFF, the Virtual Ideal Functionality Framework.
     3.7 +#
     3.8 +# VIFF is free software: you can redistribute it and/or modify it
     3.9 +# under the terms of the GNU Lesser General Public License (LGPL) as
    3.10 +# published by the Free Software Foundation, either version 3 of the
    3.11 +# License, or (at your option) any later version.
    3.12 +#
    3.13 +# VIFF is distributed in the hope that it will be useful, but WITHOUT
    3.14 +# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
    3.15 +# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
    3.16 +# Public License for more details.
    3.17 +#
    3.18 +# You should have received a copy of the GNU Lesser General Public
    3.19 +# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
    3.20 +
    3.21 +from twisted.internet.defer import gatherResults, Deferred, DeferredList
    3.22 +
    3.23 +from viff.test.util import RuntimeTestCase, protocol
    3.24 +from viff.field import GF
    3.25 +from viff.runtime import Share
    3.26 +
    3.27 +from viff.comparison import Toft05Runtime
    3.28 +from viff.hash_broadcast import HashBroadcastMixin
    3.29 +
    3.30 +class BroadcastRuntime(Toft05Runtime, HashBroadcastMixin):
    3.31 +    """Mix of :class:`Toft05Runtime` and
    3.32 +    :class:`HashBroadcastRuntime`."""
    3.33 +    pass
    3.34 +
    3.35 +class HashBroadcastTest(RuntimeTestCase):
    3.36 +    """Test for the hash broadcast mixin."""
    3.37 +
    3.38 +    # Number of players.
    3.39 +    num_players = 3
    3.40 +
    3.41 +    runtime_class = BroadcastRuntime
    3.42 +
    3.43 +    timeout = 10
    3.44 +    @protocol
    3.45 +    def test_send(self, runtime):
    3.46 +        """Test of send a value."""
    3.47 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
    3.48 +
    3.49 +        value = 42
    3.50 +
    3.51 +        receivers = [2, 3]
    3.52 +        if 1 == runtime.id:
    3.53 +            d = runtime.broadcast([1], receivers, str(value))
    3.54 +        else:
    3.55 +            d = runtime.broadcast([1], receivers)
    3.56 +        def check(x):
    3.57 +            self.assertEquals(int(x), 42)
    3.58 +        d.addCallback(check)
    3.59 +        return d
    3.60 +            
    3.61 +
    3.62 +    @protocol
    3.63 +    def test_send_two_senders_in_parallel(self, runtime):
    3.64 +        """Test of send a value."""
    3.65 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
    3.66 +
    3.67 +        def check(ls):
    3.68 +            for s, x in ls:
    3.69 +                self.assertEquals(int(x), 42)
    3.70 +            return ls
    3.71 +
    3.72 +        value = 42
    3.73 +
    3.74 +        receivers = [2, 3]
    3.75 +        if 1 == runtime.id:
    3.76 +            d1 = runtime.broadcast([1], receivers, str(value))
    3.77 +        else:
    3.78 +            d1 = runtime.broadcast([1], receivers)
    3.79 +
    3.80 +        if 2 == runtime.id:
    3.81 +            d2 = runtime.broadcast([2], [3], str(value))
    3.82 +        else:
    3.83 +            d2 = runtime.broadcast([2], [3])
    3.84 +
    3.85 +        ds = [d1]
    3.86 +        if [] != d2:
    3.87 +            ds.append(d2)
    3.88 +        dls = DeferredList(ds)
    3.89 +        dls.addCallback(check)
    3.90 +        return dls
    3.91 +            
    3.92 +    @protocol
    3.93 +    def test_send_multiple_senders_in_one_burst(self, runtime):
    3.94 +        """Test of send a value."""
    3.95 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
    3.96 +
    3.97 +        value = 42
    3.98 +        if 1 == runtime.id:
    3.99 +            value = 7
   3.100 +
   3.101 +        if 1 == runtime.id or 3 == runtime.id:
   3.102 +            ds = runtime.broadcast([1, 3], [2], str(value))
   3.103 +
   3.104 +        if 2 == runtime.id:
   3.105 +            ds = runtime.broadcast([1, 3], [2])
   3.106 +            dls = DeferredList(ds)
   3.107 +            def check(ls):
   3.108 +                self.assertEquals(int(ls[0][1]), 7)
   3.109 +                self.assertEquals(int(ls[1][1]), 42)
   3.110 +                return ls
   3.111 +            dls.addCallback(check)
   3.112 +            return dls
   3.113 +        return None
   3.114 +            
   3.115 +
   3.116 +    @protocol
   3.117 +    def test_sender_in_receivers(self, runtime):
   3.118 +        """Test of send a value."""
   3.119 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
   3.120 +
   3.121 +        value = 42
   3.122 +        if 1 == runtime.id:
   3.123 +            d = runtime.broadcast([1], [1, 2, 3], str(value))
   3.124 +        else:
   3.125 +            d = runtime.broadcast([1], [1, 2, 3])
   3.126 +
   3.127 +        def check(x):
   3.128 +            self.assertEquals(int(x), 42)
   3.129 +            return x
   3.130 +        d.addCallback(check)
   3.131 +        return d
   3.132 +
   3.133 +    @protocol
   3.134 +    def test_complex(self, runtime):
   3.135 +        def check(ls):
   3.136 +            for x, v in ls:
   3.137 +                self.assertEquals(runtime.list_str(v), ['7', '9', '13'])
   3.138 +            
   3.139 +        receivers = [1, 2, 3]
   3.140 +        def exchange((xi, rhoi1, rhoi2)):
   3.141 +            # Send share to all receivers.
   3.142 +            ds = runtime.broadcast(receivers, receivers, str((str(xi), str(rhoi1), str(rhoi2))))
   3.143 +            dls = DeferredList(ds)
   3.144 +            dls.addCallbacks(check, runtime.error_handler)
   3.145 +            return dls
   3.146 +
   3.147 +        result = Deferred()
   3.148 +        result.addCallbacks(exchange, runtime.error_handler)
   3.149 +        result.callback((7, 9, 13))
   3.150 +        return result
   3.151 +
   3.152 +    @protocol
   3.153 +    def test_complex2(self, runtime):
   3.154 +        def check(ls):
   3.155 +            if (2 == runtime.id) or (1 == runtime.id):
   3.156 +                self.assertEquals(ls[0][1], "V1")
   3.157 +                self.assertEquals(ls[1][1], "V1")
   3.158 +                self.assertEquals(ls[2][1], "V1")
   3.159 +                self.assertEquals(ls[3][1], "V2")
   3.160 +            else:
   3.161 +                self.assertEquals(ls[0][1], "V1")
   3.162 +                self.assertEquals(ls[1][1], "V1")
   3.163 +                self.assertEquals(ls[2][1], "V1")
   3.164 +                self.assertEquals(ls[3][1], "V2")
   3.165 +                self.assertEquals(ls[4][1], "V2")
   3.166 +        field = self.Zp
   3.167 +        results = []
   3.168 +        results += runtime.broadcast(runtime.players.keys(), runtime.players.keys(), "V1")
   3.169 +        if runtime.id in [1, 2]:
   3.170 +            v = runtime.broadcast([1, 2], [3], "V2")
   3.171 +            if isinstance(v, list):
   3.172 +                results += v
   3.173 +            else:
   3.174 +                results.append(v)
   3.175 +        else:
   3.176 +            results += runtime.broadcast([1, 2], [3])
   3.177 +        if 3 == runtime.id:
   3.178 +            results += [runtime.broadcast([3], runtime.players.keys(), str(7))]
   3.179 +        else:
   3.180 +            results += [runtime.broadcast([3], runtime.players.keys())]
   3.181 +        dls = DeferredList(results)
   3.182 +        runtime.schedule_callback(dls, check)
   3.183 +        dls.addErrback(runtime.error_handler)
   3.184 +        return dls