viff

changeset 1228:a62e12c9947a

Implementation of input and shift commands.
author Janus Dam Nielsen <janus.nielsen@alexandra.dk>
date Tue, 06 Oct 2009 10:05:24 +0200
parents 5636b02c6bef
children eb0443115206
files viff/hash_broadcast.py viff/orlandi.py viff/test/test_orlandi_runtime.py
diffstat 3 files changed, 181 insertions(+), 4 deletions(-) [+]
line diff
     1.1 --- a/viff/hash_broadcast.py	Tue Oct 06 10:05:24 2009 +0200
     1.2 +++ b/viff/hash_broadcast.py	Tue Oct 06 10:05:24 2009 +0200
     1.3 @@ -96,7 +96,8 @@
     1.4              self._expect_data_with_pc(unique_pc, peer_id, HASH, d_hash)
     1.5              d_signal = Deferred().addCallbacks(signal_received, 
     1.6                                                 self.error_handler, 
     1.7 -                                               callbackArgs=(peer_id, message, len(receivers), g_hashes, signals))
     1.8 +                                               callbackArgs=(peer_id, message, len(receivers), 
     1.9 +                                                             g_hashes, signals))
    1.10              self._expect_data_with_pc(unique_pc, peer_id, SIGNAL, d_signal)
    1.11  
    1.12          # Set up receiving of the message.
     2.1 --- a/viff/orlandi.py	Tue Oct 06 10:05:24 2009 +0200
     2.2 +++ b/viff/orlandi.py	Tue Oct 06 10:05:24 2009 +0200
     2.3 @@ -15,7 +15,7 @@
     2.4  # You should have received a copy of the GNU Lesser General Public
     2.5  # License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
     2.6  
     2.7 -from twisted.internet.defer import Deferred, gatherResults
     2.8 +from twisted.internet.defer import Deferred, DeferredList, gatherResults
     2.9  
    2.10  from viff.runtime import Runtime, Share, ShareList, gather_shares
    2.11  from viff.util import rand
    2.12 @@ -383,6 +383,82 @@
    2.13          result.addCallbacks(compute_subs, self.error_handler)
    2.14          return result
    2.15  
    2.16 +    def input(self, inputters, field, number=None, threshold=None):
    2.17 +        """Input *number* to the computation.
    2.18 +
    2.19 +        The input is shared using the :meth:`shift` method.
    2.20 +        """
    2.21 +        return self.shift(inputters, field, number)
    2.22 +
    2.23 +
    2.24 +    def shift(self, inputters, field, number=None):
    2.25 +        """Shift of a share.
    2.26 +        
    2.27 +        Useful for input.
    2.28 +
    2.29 +        Communication cost: ???.
    2.30 +
    2.31 +        Assume the parties are given a random share ``[r]`` by a trusted dealer. 
    2.32 +        Then we denote the following protocol but ``[x] = Shift(P_i, x, [r])``.
    2.33 +
    2.34 +        1) ``r = OpenTo(P_i, [r]``
    2.35 +
    2.36 +        2) ``P_i broadcasts Delta = r - x``
    2.37 +
    2.38 +        3) ``[x] = [r] - Delta``
    2.39 +
    2.40 +        """
    2.41 +        # TODO: Communitcation costs?
    2.42 +        assert (self.id in inputters and number != None) or (self.id not in inputters)
    2.43 +
    2.44 +        self.program_counter[-1] += 1
    2.45 +
    2.46 +        results = []
    2.47 +        def hack(_, peer_id):
    2.48 +            # Assume the parties are given a random share [r] by a trusted dealer.
    2.49 +            share_r = self.random_share(field)
    2.50 +            # 1) r = OpenTo(P_i, [r])
    2.51 +            open_r = self.open(share_r, [peer_id])
    2.52 +            def subtract_delta(delta, share_r):
    2.53 +                delta = field(long(delta))
    2.54 +                x = self.sub(share_r, delta)
    2.55 +                return x
    2.56 +            if peer_id == self.id:
    2.57 +                def g(r, x):
    2.58 +                    delta = r - x
    2.59 +                    delta = self.broadcast([peer_id], self.players.keys(), str(delta.value))
    2.60 +                    self.schedule_callback(delta, subtract_delta, share_r)
    2.61 +                    delta.addErrback(self.error_handler)
    2.62 +                    return delta
    2.63 +                self.schedule_callback(open_r, g, number)
    2.64 +                open_r.addErrback(self.error_handler)
    2.65 +                return open_r
    2.66 +            else:
    2.67 +                d = Deferred()
    2.68 +                def g(_, peer_id, share_r):
    2.69 +                    delta = self.broadcast([peer_id], self.players.keys())
    2.70 +                    self.schedule_callback(delta, subtract_delta, share_r)
    2.71 +                    delta.addErrback(self.error_handler)
    2.72 +                    return delta
    2.73 +                self.schedule_callback(d, g, peer_id, share_r)
    2.74 +                d.addErrback(self.error_handler)
    2.75 +                d.callback(None)
    2.76 +                return d
    2.77 +
    2.78 +        for peer_id in inputters:
    2.79 +            s = Share(self, field)
    2.80 +            self.schedule_callback(s, hack, peer_id)
    2.81 +            s.addErrback(self.error_handler)
    2.82 +            s.callback(None)
    2.83 +            results.append(s)
    2.84 +
    2.85 +        # do actual communication
    2.86 +        self.activate_reactor()
    2.87 +
    2.88 +        if len(results) == 1:
    2.89 +             return results[0]
    2.90 +        return results       
    2.91 +
    2.92      def _additive_constant(self, zero, field_element):
    2.93          """Greate an additive constant.
    2.94  
     3.1 --- a/viff/test/test_orlandi_runtime.py	Tue Oct 06 10:05:24 2009 +0200
     3.2 +++ b/viff/test/test_orlandi_runtime.py	Tue Oct 06 10:05:24 2009 +0200
     3.3 @@ -15,15 +15,17 @@
     3.4  # You should have received a copy of the GNU Lesser General Public
     3.5  # License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
     3.6  
     3.7 -from twisted.internet.defer import gatherResults
     3.8 +from twisted.internet.defer import gatherResults, DeferredList
     3.9  
    3.10  from viff.test.util import RuntimeTestCase, protocol, BinaryOperatorTestCase
    3.11 -from viff.runtime import Share
    3.12 +from viff.runtime import Share, gather_shares
    3.13  from viff.orlandi import OrlandiRuntime
    3.14  
    3.15  from viff.field import FieldElement, GF
    3.16  from viff.passive import PassiveRuntime
    3.17  
    3.18 +from viff.util import rand
    3.19 +
    3.20  import commitment
    3.21  
    3.22  class OrlandiBasicCommandsTest(RuntimeTestCase):
    3.23 @@ -239,3 +241,101 @@
    3.24          return d
    3.25  
    3.26  
    3.27 +class OrlandiAdvancedCommandsTest(RuntimeTestCase):
    3.28 +    """Test for advanced commands."""
    3.29 +    
    3.30 +    # Number of players.
    3.31 +    num_players = 3
    3.32 + 
    3.33 +    runtime_class = OrlandiRuntime
    3.34 +
    3.35 +    timeout = 60
    3.36 +
    3.37 +    @protocol
    3.38 +    def test_shift(self, runtime):
    3.39 +        """Test addition of the shift command."""
    3.40 +
    3.41 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
    3.42 +        
    3.43 +        def check(v):
    3.44 +            self.assertEquals(v, 42)
    3.45 + 
    3.46 +        x = runtime.shift([2], self.Zp, 42)
    3.47 +        d = runtime.open(x)
    3.48 +        d.addCallback(check)
    3.49 +        return d
    3.50 +
    3.51 +    @protocol
    3.52 +    def test_shift_two_inputters(self, runtime):
    3.53 +        """Test addition of the shift command."""
    3.54 +
    3.55 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
    3.56 +        
    3.57 +        def check(v):
    3.58 +            self.assertEquals(v, 42)
    3.59 + 
    3.60 +        x, y = runtime.shift([1,3], self.Zp, 42)
    3.61 +        d1 = runtime.open(x)
    3.62 +        d1.addCallback(check)
    3.63 +        d2 = runtime.open(y)
    3.64 +        d2.addCallback(check)
    3.65 +        return DeferredList([d1, d2])
    3.66 +
    3.67 +
    3.68 +    @protocol
    3.69 +    def test_shift_two_consequtive_inputters(self, runtime):
    3.70 +        """Test addition of the shift command."""
    3.71 +
    3.72 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
    3.73 +        
    3.74 +        def r1(ls):
    3.75 +            x, y = ls
    3.76 +            self.assertEquals(runtime.program_counter, [4])
    3.77 + 
    3.78 +        x = runtime.shift([1], self.Zp, 42)
    3.79 +        y = runtime.shift([2], self.Zp, 42)
    3.80 +        r = gather_shares([x, y])
    3.81 +        r.addCallback(r1)
    3.82 +        return r
    3.83 +
    3.84 +    @protocol
    3.85 +    def test_shift_two_consequtive_inputters2(self, runtime):
    3.86 +        """Test addition of the shift command."""
    3.87 +
    3.88 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
    3.89 +        
    3.90 +        def check(v):
    3.91 +            self.assertEquals(v, 42)
    3.92 +
    3.93 +        def r1((x, y)):
    3.94 +            self.assertEquals(x, 42)
    3.95 +            self.assertEquals(y, 42)
    3.96 + 
    3.97 +        x = runtime.shift([1], self.Zp, 42)
    3.98 +        y = runtime.shift([2], self.Zp, 42)
    3.99 +        r = gather_shares([runtime.open(x), runtime.open(y)])
   3.100 +        r.addCallback(r1)
   3.101 +        return r
   3.102 +
   3.103 +    @protocol
   3.104 +    def test_input(self, runtime):
   3.105 +        """Test of many uses of the input command."""
   3.106 +
   3.107 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
   3.108 +
   3.109 +        count = 20
   3.110 +
   3.111 +        a_shares = []
   3.112 +        b_shares = []
   3.113 +        for i in range(count):
   3.114 +            inputter = (i % len(runtime.players)) + 1
   3.115 +            if inputter == runtime.id:
   3.116 +                a = rand.randint(0, self.Zp.modulus)
   3.117 +                b = rand.randint(0, self.Zp.modulus)
   3.118 +            else:
   3.119 +                a, b = None, None
   3.120 +            a_shares.append(runtime.input([inputter], self.Zp, a))
   3.121 +            b_shares.append(runtime.input([inputter], self.Zp, b))
   3.122 +        shares_ready = gather_shares(a_shares + b_shares)
   3.123 +        return shares_ready
   3.124 +