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 wrap: on
line diff
--- a/viff/hash_broadcast.py	Tue Oct 06 10:05:24 2009 +0200
+++ b/viff/hash_broadcast.py	Tue Oct 06 10:05:24 2009 +0200
@@ -96,7 +96,8 @@
             self._expect_data_with_pc(unique_pc, peer_id, HASH, d_hash)
             d_signal = Deferred().addCallbacks(signal_received, 
                                                self.error_handler, 
-                                               callbackArgs=(peer_id, message, len(receivers), g_hashes, signals))
+                                               callbackArgs=(peer_id, message, len(receivers), 
+                                                             g_hashes, signals))
             self._expect_data_with_pc(unique_pc, peer_id, SIGNAL, d_signal)
 
         # Set up receiving of the message.
--- a/viff/orlandi.py	Tue Oct 06 10:05:24 2009 +0200
+++ b/viff/orlandi.py	Tue Oct 06 10:05:24 2009 +0200
@@ -15,7 +15,7 @@
 # You should have received a copy of the GNU Lesser General Public
 # License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
 
-from twisted.internet.defer import Deferred, gatherResults
+from twisted.internet.defer import Deferred, DeferredList, gatherResults
 
 from viff.runtime import Runtime, Share, ShareList, gather_shares
 from viff.util import rand
@@ -383,6 +383,82 @@
         result.addCallbacks(compute_subs, self.error_handler)
         return result
 
+    def input(self, inputters, field, number=None, threshold=None):
+        """Input *number* to the computation.
+
+        The input is shared using the :meth:`shift` method.
+        """
+        return self.shift(inputters, field, number)
+
+
+    def shift(self, inputters, field, number=None):
+        """Shift of a share.
+        
+        Useful for input.
+
+        Communication cost: ???.
+
+        Assume the parties are given a random share ``[r]`` by a trusted dealer. 
+        Then we denote the following protocol but ``[x] = Shift(P_i, x, [r])``.
+
+        1) ``r = OpenTo(P_i, [r]``
+
+        2) ``P_i broadcasts Delta = r - x``
+
+        3) ``[x] = [r] - Delta``
+
+        """
+        # TODO: Communitcation costs?
+        assert (self.id in inputters and number != None) or (self.id not in inputters)
+
+        self.program_counter[-1] += 1
+
+        results = []
+        def hack(_, peer_id):
+            # Assume the parties are given a random share [r] by a trusted dealer.
+            share_r = self.random_share(field)
+            # 1) r = OpenTo(P_i, [r])
+            open_r = self.open(share_r, [peer_id])
+            def subtract_delta(delta, share_r):
+                delta = field(long(delta))
+                x = self.sub(share_r, delta)
+                return x
+            if peer_id == self.id:
+                def g(r, x):
+                    delta = r - x
+                    delta = self.broadcast([peer_id], self.players.keys(), str(delta.value))
+                    self.schedule_callback(delta, subtract_delta, share_r)
+                    delta.addErrback(self.error_handler)
+                    return delta
+                self.schedule_callback(open_r, g, number)
+                open_r.addErrback(self.error_handler)
+                return open_r
+            else:
+                d = Deferred()
+                def g(_, peer_id, share_r):
+                    delta = self.broadcast([peer_id], self.players.keys())
+                    self.schedule_callback(delta, subtract_delta, share_r)
+                    delta.addErrback(self.error_handler)
+                    return delta
+                self.schedule_callback(d, g, peer_id, share_r)
+                d.addErrback(self.error_handler)
+                d.callback(None)
+                return d
+
+        for peer_id in inputters:
+            s = Share(self, field)
+            self.schedule_callback(s, hack, peer_id)
+            s.addErrback(self.error_handler)
+            s.callback(None)
+            results.append(s)
+
+        # do actual communication
+        self.activate_reactor()
+
+        if len(results) == 1:
+             return results[0]
+        return results       
+
     def _additive_constant(self, zero, field_element):
         """Greate an additive constant.
 
--- a/viff/test/test_orlandi_runtime.py	Tue Oct 06 10:05:24 2009 +0200
+++ b/viff/test/test_orlandi_runtime.py	Tue Oct 06 10:05:24 2009 +0200
@@ -15,15 +15,17 @@
 # You should have received a copy of the GNU Lesser General Public
 # License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
 
-from twisted.internet.defer import gatherResults
+from twisted.internet.defer import gatherResults, DeferredList
 
 from viff.test.util import RuntimeTestCase, protocol, BinaryOperatorTestCase
-from viff.runtime import Share
+from viff.runtime import Share, gather_shares
 from viff.orlandi import OrlandiRuntime
 
 from viff.field import FieldElement, GF
 from viff.passive import PassiveRuntime
 
+from viff.util import rand
+
 import commitment
 
 class OrlandiBasicCommandsTest(RuntimeTestCase):
@@ -239,3 +241,101 @@
         return d
 
 
+class OrlandiAdvancedCommandsTest(RuntimeTestCase):
+    """Test for advanced commands."""
+    
+    # Number of players.
+    num_players = 3
+ 
+    runtime_class = OrlandiRuntime
+
+    timeout = 60
+
+    @protocol
+    def test_shift(self, runtime):
+        """Test addition of the shift command."""
+
+        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+        
+        def check(v):
+            self.assertEquals(v, 42)
+ 
+        x = runtime.shift([2], self.Zp, 42)
+        d = runtime.open(x)
+        d.addCallback(check)
+        return d
+
+    @protocol
+    def test_shift_two_inputters(self, runtime):
+        """Test addition of the shift command."""
+
+        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+        
+        def check(v):
+            self.assertEquals(v, 42)
+ 
+        x, y = runtime.shift([1,3], self.Zp, 42)
+        d1 = runtime.open(x)
+        d1.addCallback(check)
+        d2 = runtime.open(y)
+        d2.addCallback(check)
+        return DeferredList([d1, d2])
+
+
+    @protocol
+    def test_shift_two_consequtive_inputters(self, runtime):
+        """Test addition of the shift command."""
+
+        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+        
+        def r1(ls):
+            x, y = ls
+            self.assertEquals(runtime.program_counter, [4])
+ 
+        x = runtime.shift([1], self.Zp, 42)
+        y = runtime.shift([2], self.Zp, 42)
+        r = gather_shares([x, y])
+        r.addCallback(r1)
+        return r
+
+    @protocol
+    def test_shift_two_consequtive_inputters2(self, runtime):
+        """Test addition of the shift command."""
+
+        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+        
+        def check(v):
+            self.assertEquals(v, 42)
+
+        def r1((x, y)):
+            self.assertEquals(x, 42)
+            self.assertEquals(y, 42)
+ 
+        x = runtime.shift([1], self.Zp, 42)
+        y = runtime.shift([2], self.Zp, 42)
+        r = gather_shares([runtime.open(x), runtime.open(y)])
+        r.addCallback(r1)
+        return r
+
+    @protocol
+    def test_input(self, runtime):
+        """Test of many uses of the input command."""
+
+        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+        count = 20
+
+        a_shares = []
+        b_shares = []
+        for i in range(count):
+            inputter = (i % len(runtime.players)) + 1
+            if inputter == runtime.id:
+                a = rand.randint(0, self.Zp.modulus)
+                b = rand.randint(0, self.Zp.modulus)
+            else:
+                a, b = None, None
+            a_shares.append(runtime.input([inputter], self.Zp, a))
+            b_shares.append(runtime.input([inputter], self.Zp, b))
+        shares_ready = gather_shares(a_shares + b_shares)
+        return shares_ready
+