changeset 99:3e0aadd17eb7

A millionaires example which uses ideal_functionality.
author Janus Dam Nielsen <janus.nielsen@alexandra.dk>
date Wed, 08 Jul 2009 13:20:22 +0200
parents 856feae68946
children b861d026f3df 49d36bd742b0
files examples/millionaires.py
diffstat 1 files changed, 261 insertions(+), 0 deletions(-) [+]
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/examples/millionaires.py	Wed Jul 08 13:20:22 2009 +0200
@@ -0,0 +1,261 @@
+
+from pysmcl.ideal_functionality import ideal_functionality
+
+import sys
+from optparse import OptionParser
+
+import viff.reactor
+viff.reactor.install()
+from twisted.internet import reactor
+from twisted.internet.defer import Deferred, DeferredList, gatherResults
+
+from viff.field import GF
+from viff.runtime import Share, create_runtime, gather_shares
+from viff.config import load_config
+from viff.util import dprint, find_prime
+from viff.comparison import Toft07Runtime
+
+# Load the configuration from the player configuration files.
+id, players = load_config(sys.argv[1])
+
+# Initialize the field we do arithmetic over.
+Zp = GF(30916444023318367583)
+
+# Read input from the commandline.
+input = int(sys.argv[2])
+
+print "I am player %d and will input %s" % (id, input)
+
+# ===========================================================================
+
+
+# The ugly millionaires program
+def mill1(runtime):
+    print "-" * 64
+    print "Program started"
+    print
+
+    networths = runtime.input(runtime.players.keys(), Zp, input)
+    ids = runtime.input(runtime.players.keys(), Zp, runtime.id)
+    ls = zip(ids, networths)
+
+    def max(ls, client, value):
+        print "Max..."
+        if ls == []:
+            return (client, value)
+        def update(r, ls, id, networth, client, value):
+            print "  update", id, networth
+            if r:
+                print "  true"
+                client = id
+                value = networth
+            return max(ls, client, value)
+        id, networth = ls.pop()
+        d = runtime.output(networth >= value)
+        d.addCallback(update, ls, id, networth, client, value)
+        return d
+
+    d = max(ls, Share(runtime, Zp, Zp(0)), Share(runtime, Zp, Zp(0)))
+    def rest((c,v)):
+        d1 = runtime.open(c)
+        d2 = runtime.open(v)
+        results = gather_shares([d1, d2])
+        def result((c,v)):
+            print "Result", c, v
+        results.addCallback(result)
+    d.addCallback(rest)
+
+    runtime.schedule_callback(d, lambda _: runtime.synchronize())
+    runtime.schedule_callback(d, lambda _: runtime.shutdown())
+
+def field_converter(field, x):
+    def convert(x):
+        return field(x.value)
+    x.addCallback(convert)
+    return x
+
+# ===========================================================================
+
+# The not so nice millionaires program
+def runNotNiceMills(runtime):
+    # Input player identity.
+    ids = runtime.input(runtime.players.keys(), Zp, runtime.id)
+    # Input player networths.
+    networths = runtime.input(runtime.players.keys(), Zp, input)
+
+    # Create a list of tuples of identity and corresponding networths. 
+    ls = zip(ids, networths)
+
+    richest, max = millionaries(runtime, ls)
+
+    output_to_all(runtime, richest, max)
+
+def not_nice_millionaries(runtime, ls):
+    """Computes the richest millionaire given a list of
+    pairs of identity and networth.
+    
+    Returns a pair of identity and networth of the richest millionaire.
+    """
+
+    # Declare temporary variables. 
+    # *richest* contains the identity of the currently richest player.
+    # *max* contains the networth of the currently richest player.
+    richest = Share(runtime, Zp, Zp(0))
+    max = Share(runtime, Zp, Zp(0))
+
+    # Loop over all the pairs of identity and networth and compute the maximum.
+    for id, networth in ls:
+        b = networth >= current_max
+        max     = b * networth + (1 - b) * max
+        richest = b * id + (1 - b) * richest
+        
+    return richest, max
+
+# ===========================================================================
+
+# The nice millionaires program
+
+@ideal_functionality
+def maximum(current_id, current_max, id, networth):
+    """Computes the maximum of current_max and networth.
+
+    Returns the pair corresponding to the maximum value of 
+    current_max and networth.
+    """
+    identity = current_id
+    money = current_max
+    if networth >= current_max:
+        money = networth
+        identity = id
+    return identity, money
+
+def millionaries(runtime, ls):
+    """Computes the richest millionaire given a list of
+    pairs of identity and networth.
+    
+    Returns a pair of identity and networth of the richest millionaire.
+    """
+
+    # Declare temporary variables. 
+    # *richest* contains the identity of the currently richest player.
+    # *max* contains the networth of the currently richest player.
+    richest = Share(runtime, Zp, Zp(0))
+    max = Share(runtime, Zp, Zp(0))
+
+    # Loop over all the pairs of identity and networth and compute the maximum.
+    for id, networth in ls:
+        richest, max = maximum(richest, max, id, networth)
+
+    return richest, max
+
+def output_to_all(runtime, richest, max):
+    # Everyone learns the identity and the networth of the richest.
+    deferred_identity = runtime.output(richest)
+    deferred_max = runtime.output(max)
+
+    result = gather_shares([deferred_identity, deferred_max])
+
+    def result_reporter((id, max)):
+        print "The richest is player %s he has USD %s" % (id.value, max.value)
+    result.addCallback(result_reporter)
+
+    runtime.schedule_callback(result, lambda _: runtime.synchronize())
+    runtime.schedule_callback(result, lambda _: runtime.shutdown())
+
+def output_to_richest(runtime, richest, max):
+    """Everyone learns the identity of the richest, but not his networth.
+    
+    This corresponds to Figur 4(A) in the paper
+    "A Domain-Specific Programming Language for Secure Multiparty Computation"
+    by Janus Dam Nielsen and Michael I. Schwartzbach.
+
+    """
+
+    deferred_identity = runtime.output(richest)
+
+    def result_reporter(id):
+        print "The richest is player %s" % id.value
+    deferred_identity.addCallback(result_reporter)
+
+    runtime.schedule_callback(deferred_identity, lambda _: runtime.synchronize())
+    runtime.schedule_callback(deferred_identity, lambda _: runtime.shutdown())
+
+def output_status(runtime, richest, max):
+    """Everyone learns their own status, but not the others.
+    
+    This corresponds to Figur 4(B) in the paper
+    "A Domain-Specific Programming Language for Secure Multiparty Computation"
+    by Janus Dam Nielsen and Michael I. Schwartzbach.
+
+    """
+
+    deferred_identity1 = None
+    deferred_identity2 = None
+
+    secret_ids = runtime.input(runtime.players.keys(), Zp, runtime.id)
+    ids = runtime.players.keys()
+    
+    ls = zip(ids, secret_ids)
+
+    for id, secret_id in ls:
+        # This is a bit ugly because the runtime does not provide a equals method.
+        r1 = secret_id >= richest
+        r2 = richest >= secret_id
+        d1 = runtime.output(r1, [id])
+        d2 = runtime.output(r2, [id])
+        if d1 is not None:
+            deferred_identity1 = d1
+            deferred_identity2 = d2
+
+    def result_reporter((status1, status2)):
+        if status1.value and status2.value:
+            print "> You are the richest."
+        else:
+            print "> You are not so rich."
+
+    deferred_identity = gather_shares([deferred_identity1, deferred_identity2])
+
+    deferred_identity.addCallback(result_reporter)
+
+    runtime.schedule_callback(deferred_identity, lambda _: runtime.synchronize())
+    runtime.schedule_callback(deferred_identity, lambda _: runtime.shutdown())
+
+
+def runMills(runtime):
+    # Input player identity.
+    ids = runtime.input(runtime.players.keys(), Zp, runtime.id)
+    # Input player networths.
+    networths = runtime.input(runtime.players.keys(), Zp, input)
+
+    # Create a list of tuples of identity and corresponding networths. 
+    ls = zip(ids, networths)
+
+    richest, max = millionaries(runtime, ls)
+
+#    output_to_all(runtime, richest, max)
+
+#    output_to_richest(runtime, richest, max)
+
+    output_status(runtime, richest, max)
+
+def errorHandler(failure):
+    print "Error: %s" % failure
+
+
+# Parse command line arguments.
+parser = OptionParser()
+Toft07Runtime.add_options(parser)
+options, args = parser.parse_args()
+
+if len(args) == 0:
+    parser.error("you must specify a config file")
+else:
+    id, players = load_config(args[0])
+
+# Create a deferred Runtime and ask it to run our protocol when ready.
+pre_runtime = create_runtime(id, players, 1, options, Toft07Runtime)
+#pre_runtime.addCallback(runNotNiceMills)
+pre_runtime.addCallback(runMills)
+pre_runtime.addErrback(errorHandler)
+# Start the Twisted event loop.
+reactor.run()