viff

changeset 908:fe815100b30e

Turned Bracha broadcast into a mixin class.
author Martin Geisler <mg@daimi.au.dk>
date Mon, 15 Sep 2008 15:57:37 +0200
parents c898cac3f98a
children e36009fd979a
files doc/active.txt viff/active.py viff/test/test_active_runtime.py
diffstat 3 files changed, 179 insertions(+), 153 deletions(-) [+]
line diff
     1.1 --- a/doc/active.txt	Mon Sep 15 15:46:50 2008 +0200
     1.2 +++ b/doc/active.txt	Mon Sep 15 15:57:37 2008 +0200
     1.3 @@ -6,3 +6,6 @@
     1.4  
     1.5     .. autoclass:: ActiveRuntime
     1.6        :members:
     1.7 +
     1.8 +   .. autoclass:: BrachaBroadcastMixin
     1.9 +      :members:
     2.1 --- a/viff/active.py	Mon Sep 15 15:46:50 2008 +0200
     2.2 +++ b/viff/active.py	Mon Sep 15 15:57:37 2008 +0200
     2.3 @@ -29,6 +29,144 @@
     2.4  from viff.runtime import Runtime, Share, increment_pc, preprocess, gather_shares
     2.5  
     2.6  
     2.7 +class BrachaBroadcastMixin:
     2.8 +    """Bracha broadcast mixin class. This mixin class adds a
     2.9 +    :meth:`broadcast` method which can be used for a reliable
    2.10 +    broadcast.
    2.11 +    """
    2.12 +
    2.13 +    @increment_pc
    2.14 +    def _broadcast(self, sender, message=None):
    2.15 +        """Perform a Bracha broadcast.
    2.16 +
    2.17 +        A Bracha broadcast is reliable against an active adversary
    2.18 +        corrupting up to t < n/3 of the players. For more details, see
    2.19 +        the paper "An asynchronous [(n-1)/3]-resilient consensus
    2.20 +        protocol" by G. Bracha in Proc. 3rd ACM Symposium on
    2.21 +        Principles of Distributed Computing, 1984, pages 154-162.
    2.22 +        """
    2.23 +
    2.24 +        result = Deferred()
    2.25 +        pc = tuple(self.program_counter)
    2.26 +        n = self.num_players
    2.27 +        t = self.threshold
    2.28 +
    2.29 +        # For each distinct message (and program counter) we save a
    2.30 +        # dictionary for each of the following variables. The reason
    2.31 +        # is that we need to count for each distinct message how many
    2.32 +        # echo and ready messages we have received.
    2.33 +
    2.34 +        bracha_echo = {}
    2.35 +        bracha_ready = {}
    2.36 +        bracha_sent_ready = {}
    2.37 +        bracha_delivered = {}
    2.38 +        
    2.39 +        def unsafe_broadcast(data_type, message):
    2.40 +            # Performs a regular broadcast without any guarantees. In
    2.41 +            # other words, it sends the message to each player except
    2.42 +            # for this one.
    2.43 +            for protocol in self.protocols.itervalues():
    2.44 +                protocol.sendData(pc, data_type, message)
    2.45 +
    2.46 +        def echo_received(message, peer_id):
    2.47 +            # This is called when we receive an echo message. It
    2.48 +            # updates the echo count for the message and enters the
    2.49 +            # ready state if the count is high enough.
    2.50 +            ids = bracha_echo.setdefault(message, [])
    2.51 +            ready = bracha_sent_ready.setdefault(message, False)
    2.52 +
    2.53 +            if peer_id not in ids:
    2.54 +                ids.append(peer_id)
    2.55 +                if len(ids) >= ceil((n+t+1)/2) and not ready:
    2.56 +                    bracha_sent_ready[message] = True
    2.57 +                    unsafe_broadcast("ready", message)
    2.58 +                    ready_received(message, self.id)
    2.59 +
    2.60 +        def ready_received(message, peer_id):
    2.61 +            # This is called when we receive a ready message. It
    2.62 +            # updates the ready count for the message. Depending on
    2.63 +            # the count, we may either stay in the same state or enter
    2.64 +            # the ready or delivered state.
    2.65 +            ids = bracha_ready.setdefault(message, [])
    2.66 +            ready = bracha_sent_ready.setdefault(message, False)
    2.67 +            delivered = bracha_delivered.setdefault(message, False)
    2.68 +            if peer_id not in ids:
    2.69 +                ids.append(peer_id)
    2.70 +                if len(ids) == t+1 and not ready:
    2.71 +                    bracha_sent_ready[message] = True
    2.72 +                    unsafe_broadcast("ready", message)
    2.73 +                    ready_received(message, self.id)
    2.74 +
    2.75 +                elif len(ids) == 2*t+1 and not delivered:
    2.76 +                    bracha_delivered[message] = True
    2.77 +                    result.callback(message)
    2.78 +
    2.79 +        def send_received(message):
    2.80 +            # This is called when we receive a send message. We react
    2.81 +            # by sending an echo message to each player. Since the
    2.82 +            # unsafe broadcast doesn't send a message to this player,
    2.83 +            # we simulate it by calling the echo_received function.
    2.84 +            unsafe_broadcast("echo", message)
    2.85 +            echo_received(message, self.id)
    2.86 +
    2.87 +
    2.88 +        # In the following we prepare to handle a send message from
    2.89 +        # the sender and at most one echo and one ready message from
    2.90 +        # each player.
    2.91 +        d_send = Deferred().addCallback(send_received)
    2.92 +        self._expect_data(sender, "send", d_send)
    2.93 +
    2.94 +        for peer_id in self.players:
    2.95 +            if peer_id != self.id:
    2.96 +                d_echo = Deferred().addCallback(echo_received, peer_id)
    2.97 +                self._expect_data(peer_id, "echo", d_echo)
    2.98 +
    2.99 +                d_ready = Deferred().addCallback(ready_received, peer_id)
   2.100 +                self._expect_data(peer_id, "ready", d_ready)
   2.101 +
   2.102 +        # If this player is the sender, we transmit a send message to
   2.103 +        # each player. We send one to this player by calling the
   2.104 +        # send_received function.
   2.105 +        if self.id == sender:
   2.106 +            unsafe_broadcast("send", message)
   2.107 +            send_received(message)
   2.108 +
   2.109 +        return result
   2.110 +
   2.111 +    @increment_pc
   2.112 +    def broadcast(self, senders, message=None):
   2.113 +        """Perform one or more Bracha broadcast(s).
   2.114 +
   2.115 +        The list of *senders* given will determine the subset of players
   2.116 +        who wish to broadcast a message. If this player wishes to
   2.117 +        broadcast, its ID must be in the list of senders and the
   2.118 +        optional *message* parameter must be used.
   2.119 +
   2.120 +        If the list of senders consists only of a single sender, the
   2.121 +        result will be a single element, otherwise it will be a list.
   2.122 +
   2.123 +        A Bracha broadcast is reliable against an active adversary
   2.124 +        corrupting up to t < n/3 of the players. For more details, see
   2.125 +        the paper "An asynchronous [(n-1)/3]-resilient consensus
   2.126 +        protocol" by G. Bracha in Proc. 3rd ACM Symposium on
   2.127 +        Principles of Distributed Computing, 1984, pages 154-162.
   2.128 +        """
   2.129 +        assert message is None or self.id in senders
   2.130 +
   2.131 +        result = []
   2.132 +
   2.133 +        for sender in senders:
   2.134 +            if sender == self.id:
   2.135 +                result.append(self._broadcast(sender, message))
   2.136 +            else:
   2.137 +                result.append(self._broadcast(sender))
   2.138 +
   2.139 +        if len(result) == 1:
   2.140 +            return result[0]
   2.141 +
   2.142 +        return result
   2.143 +
   2.144 +
   2.145  class ActiveRuntime(Runtime):
   2.146      """A runtime secure against active adversaries.
   2.147  
   2.148 @@ -358,133 +496,3 @@
   2.149          c_t = r_t + d
   2.150          return 1, succeed([(a_t, b_t, c_t)])
   2.151  
   2.152 -    @increment_pc
   2.153 -    def _broadcast(self, sender, message=None):
   2.154 -        """Perform a Bracha broadcast.
   2.155 -
   2.156 -        A Bracha broadcast is reliable against an active adversary
   2.157 -        corrupting up to t < n/3 of the players. For more details, see
   2.158 -        the paper "An asynchronous [(n-1)/3]-resilient consensus
   2.159 -        protocol" by G. Bracha in Proc. 3rd ACM Symposium on
   2.160 -        Principles of Distributed Computing, 1984, pages 154-162.
   2.161 -        """
   2.162 -
   2.163 -        result = Deferred()
   2.164 -        pc = tuple(self.program_counter)
   2.165 -        n = self.num_players
   2.166 -        t = self.threshold
   2.167 -
   2.168 -        # For each distinct message (and program counter) we save a
   2.169 -        # dictionary for each of the following variables. The reason
   2.170 -        # is that we need to count for each distinct message how many
   2.171 -        # echo and ready messages we have received.
   2.172 -
   2.173 -        bracha_echo = {}
   2.174 -        bracha_ready = {}
   2.175 -        bracha_sent_ready = {}
   2.176 -        bracha_delivered = {}
   2.177 -        
   2.178 -        def unsafe_broadcast(data_type, message):
   2.179 -            # Performs a regular broadcast without any guarantees. In
   2.180 -            # other words, it sends the message to each player except
   2.181 -            # for this one.
   2.182 -            for protocol in self.protocols.itervalues():
   2.183 -                protocol.sendData(pc, data_type, message)
   2.184 -
   2.185 -        def echo_received(message, peer_id):
   2.186 -            # This is called when we receive an echo message. It
   2.187 -            # updates the echo count for the message and enters the
   2.188 -            # ready state if the count is high enough.
   2.189 -            ids = bracha_echo.setdefault(message, [])
   2.190 -            ready = bracha_sent_ready.setdefault(message, False)
   2.191 -
   2.192 -            if peer_id not in ids:
   2.193 -                ids.append(peer_id)
   2.194 -                if len(ids) >= ceil((n+t+1)/2) and not ready:
   2.195 -                    bracha_sent_ready[message] = True
   2.196 -                    unsafe_broadcast("ready", message)
   2.197 -                    ready_received(message, self.id)
   2.198 -
   2.199 -        def ready_received(message, peer_id):
   2.200 -            # This is called when we receive a ready message. It
   2.201 -            # updates the ready count for the message. Depending on
   2.202 -            # the count, we may either stay in the same state or enter
   2.203 -            # the ready or delivered state.
   2.204 -            ids = bracha_ready.setdefault(message, [])
   2.205 -            ready = bracha_sent_ready.setdefault(message, False)
   2.206 -            delivered = bracha_delivered.setdefault(message, False)
   2.207 -            if peer_id not in ids:
   2.208 -                ids.append(peer_id)
   2.209 -                if len(ids) == t+1 and not ready:
   2.210 -                    bracha_sent_ready[message] = True
   2.211 -                    unsafe_broadcast("ready", message)
   2.212 -                    ready_received(message, self.id)
   2.213 -
   2.214 -                elif len(ids) == 2*t+1 and not delivered:
   2.215 -                    bracha_delivered[message] = True
   2.216 -                    result.callback(message)
   2.217 -
   2.218 -        def send_received(message):
   2.219 -            # This is called when we receive a send message. We react
   2.220 -            # by sending an echo message to each player. Since the
   2.221 -            # unsafe broadcast doesn't send a message to this player,
   2.222 -            # we simulate it by calling the echo_received function.
   2.223 -            unsafe_broadcast("echo", message)
   2.224 -            echo_received(message, self.id)
   2.225 -
   2.226 -
   2.227 -        # In the following we prepare to handle a send message from
   2.228 -        # the sender and at most one echo and one ready message from
   2.229 -        # each player.
   2.230 -        d_send = Deferred().addCallback(send_received)
   2.231 -        self._expect_data(sender, "send", d_send)
   2.232 -
   2.233 -        for peer_id in self.players:
   2.234 -            if peer_id != self.id:
   2.235 -                d_echo = Deferred().addCallback(echo_received, peer_id)
   2.236 -                self._expect_data(peer_id, "echo", d_echo)
   2.237 -
   2.238 -                d_ready = Deferred().addCallback(ready_received, peer_id)
   2.239 -                self._expect_data(peer_id, "ready", d_ready)
   2.240 -
   2.241 -        # If this player is the sender, we transmit a send message to
   2.242 -        # each player. We send one to this player by calling the
   2.243 -        # send_received function.
   2.244 -        if self.id == sender:
   2.245 -            unsafe_broadcast("send", message)
   2.246 -            send_received(message)
   2.247 -
   2.248 -        return result
   2.249 -
   2.250 -    @increment_pc
   2.251 -    def broadcast(self, senders, message=None):
   2.252 -        """Perform one or more Bracha broadcast(s).
   2.253 -
   2.254 -        The list of *senders* given will determine the subset of players
   2.255 -        who wish to broadcast a message. If this player wishes to
   2.256 -        broadcast, its ID must be in the list of senders and the
   2.257 -        optional *message* parameter must be used.
   2.258 -
   2.259 -        If the list of senders consists only of a single sender, the
   2.260 -        result will be a single element, otherwise it will be a list.
   2.261 -
   2.262 -        A Bracha broadcast is reliable against an active adversary
   2.263 -        corrupting up to t < n/3 of the players. For more details, see
   2.264 -        the paper "An asynchronous [(n-1)/3]-resilient consensus
   2.265 -        protocol" by G. Bracha in Proc. 3rd ACM Symposium on
   2.266 -        Principles of Distributed Computing, 1984, pages 154-162.
   2.267 -        """
   2.268 -        assert message is None or self.id in senders
   2.269 -
   2.270 -        result = []
   2.271 -
   2.272 -        for sender in senders:
   2.273 -            if sender == self.id:
   2.274 -                result.append(self._broadcast(sender, message))
   2.275 -            else:
   2.276 -                result.append(self._broadcast(sender))
   2.277 -
   2.278 -        if len(result) == 1:
   2.279 -            return result[0]
   2.280 -
   2.281 -        return result
     3.1 --- a/viff/test/test_active_runtime.py	Mon Sep 15 15:46:50 2008 +0200
     3.2 +++ b/viff/test/test_active_runtime.py	Mon Sep 15 15:57:37 2008 +0200
     3.3 @@ -21,7 +21,7 @@
     3.4  
     3.5  from viff.test.util import RuntimeTestCase, protocol, BinaryOperatorTestCase
     3.6  from viff.runtime import Share
     3.7 -from viff.active import ActiveRuntime
     3.8 +from viff.active import ActiveRuntime, BrachaBroadcastMixin
     3.9  
    3.10  
    3.11  class MulTest(BinaryOperatorTestCase, RuntimeTestCase):
    3.12 @@ -41,28 +41,6 @@
    3.13      runtime_class = ActiveRuntime
    3.14  
    3.15      @protocol
    3.16 -    def test_broadcast(self, runtime):
    3.17 -        """Test Bracha broadcast."""
    3.18 -        # TODO: Figure out how to introduce network errors and test
    3.19 -        # those too.
    3.20 -        if runtime.id == 1:
    3.21 -            x = runtime.broadcast([1], "Hello world!")
    3.22 -        else:
    3.23 -            x = runtime.broadcast([1])
    3.24 -
    3.25 -        if runtime.id == 2:
    3.26 -            y, z = runtime.broadcast([2, 3], "Hello two!")
    3.27 -        elif runtime.id == 3:
    3.28 -            y, z = runtime.broadcast([2, 3], "Hello three!")
    3.29 -        else:
    3.30 -            y, z = runtime.broadcast([2, 3])
    3.31 -
    3.32 -        x.addCallback(self.assertEquals, "Hello world!")
    3.33 -        y.addCallback(self.assertEquals, "Hello two!")
    3.34 -        z.addCallback(self.assertEquals, "Hello three!")
    3.35 -        return gatherResults([x, y, z])
    3.36 -
    3.37 -    @protocol
    3.38      def test_single_share_random(self, runtime):
    3.39          """Test sharing of random numbers."""
    3.40          T = runtime.num_players - 2 * runtime.threshold
    3.41 @@ -138,3 +116,40 @@
    3.42  
    3.43          triples.addCallback(check)
    3.44          return triples
    3.45 +
    3.46 +
    3.47 +class BrachaBroadcastRuntime(ActiveRuntime, BrachaBroadcastMixin):
    3.48 +    pass
    3.49 +
    3.50 +class BrachaBroadcastTest(RuntimeTestCase):
    3.51 +    """Test for active security."""
    3.52 +
    3.53 +    #: Number of players.
    3.54 +    #:
    3.55 +    #: The protocols for active security needs n > 3t+1, so with the
    3.56 +    #: default threshold of t=1, we need n=4.
    3.57 +    num_players = 4
    3.58 +
    3.59 +    runtime_class = BrachaBroadcastRuntime
    3.60 +
    3.61 +    @protocol
    3.62 +    def test_broadcast(self, runtime):
    3.63 +        """Test Bracha broadcast."""
    3.64 +        # TODO: Figure out how to introduce network errors and test
    3.65 +        # those too.
    3.66 +        if runtime.id == 1:
    3.67 +            x = runtime.broadcast([1], "Hello world!")
    3.68 +        else:
    3.69 +            x = runtime.broadcast([1])
    3.70 +
    3.71 +        if runtime.id == 2:
    3.72 +            y, z = runtime.broadcast([2, 3], "Hello two!")
    3.73 +        elif runtime.id == 3:
    3.74 +            y, z = runtime.broadcast([2, 3], "Hello three!")
    3.75 +        else:
    3.76 +            y, z = runtime.broadcast([2, 3])
    3.77 +
    3.78 +        x.addCallback(self.assertEquals, "Hello world!")
    3.79 +        y.addCallback(self.assertEquals, "Hello two!")
    3.80 +        z.addCallback(self.assertEquals, "Hello three!")
    3.81 +        return gatherResults([x, y, z])