viff

view apps/sort.py @ 1575:cfb8e1485006

find changesets by author, revision, files, or words in the commit message
Updated email address.
author Thomas P Jakobsen <tpj@cs.au.dk>
date Wed Dec 15 13:00:00 2010 +0100 (17 months ago)
parents 6cd5ceb87542
children
line source
1 #!/usr/bin/env python
2
3 # Copyright 2008 VIFF Development Team.
4 #
5 # This file is part of VIFF, the Virtual Ideal Functionality Framework.
6 #
7 # VIFF is free software: you can redistribute it and/or modify it
8 # under the terms of the GNU Lesser General Public License (LGPL) as
9 # published by the Free Software Foundation, either version 3 of the
10 # License, or (at your option) any later version.
11 #
12 # VIFF is distributed in the hope that it will be useful, but WITHOUT
13 # ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14 # or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
15 # Public License for more details.
16 #
17 # You should have received a copy of the GNU Lesser General Public
18 # License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
19
20 # This example demonstrates how a secure sorting algorithm can be
21 # implemented using VIFF. The algorithm used is bitonic sort which was
22 # chosen in order to maximize the amount of work (comparisons) done in
23 # parallel. Bitonic sort uses 1/2 * log n * (log n + 1) comparator
24 # stages and each stage consists of n/2 parallel comparisons. The
25 # total number of comparisons is thus in O(n log^2 n).
26 #
27 # This is larger than the lower bound of Omega(n log n) for comparison
28 # based sorting algorithms, achieved by mergesort and other well known
29 # algorithms. The problem with mergesort is its merging step: to merge
30 # two sorted arrays of length n/2 one needs up to n comparisons, and
31 # what is worse, the comparisons must be made one after another. The
32 # mergesort does one merge with lists of size n/2, two merges with
33 # lists of size n/4, and so on. This gives a total chain of
34 # comparisons of length n + n/2 + n/4 + ... + 1 = 2n - 1, which is
35 # more than the O(log^2 n) stages needed by the Bitonic Sort.
36 #
37 # TODO: Implement mergesort too to better back this up.
38 #
39 # See this page for more analysis and a Java implementation:
40 #
41 # http://iti.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/bitonicen.htm
42 #
43 # It requires ProgressBar v. 2.2 found on
44 # http://pypi.python.org/pypi/progressbar/
45 #
46 # TODO: Predict the number of comparisons and support preprocessing.
47 #
48
49 # Give a player configuration file as a command line argument or run
50 # the example with '--help' for help with the command line options.
51
52 from math import log, floor
53 from optparse import OptionParser
54 import viff.reactor
55 viff.reactor.install()
56 from twisted.internet import reactor
57
58 from progressbar import ProgressBar, Percentage, Bar, ETA, ProgressBarWidget
59
60 from viff.field import GF
61 from viff.runtime import Runtime, create_runtime, gather_shares
62 from viff.comparison import Toft07Runtime
63 from viff.config import load_config
64 from viff.util import find_prime, rand, dprint
65
66 # Parse command line arguments.
67 parser = OptionParser()
68 parser.add_option("--modulus",
69 help="lower limit for modulus (can be an expression)")
70 parser.add_option("-s", "--size", type="int",
71 help="array size")
72 parser.add_option("-m", "--max", type="int",
73 help="maximum size of array numbers")
74 parser.add_option("-t", "--test", action="store_true",
75 help="run doctests on this file")
76
77 parser.set_defaults(modulus=2**65, size=8, max=100, test=False)
78
79 Runtime.add_options(parser)
80
81 options, args = parser.parse_args()
82
83 if len(args) == 0:
84 parser.error("you must specify a config file")
85
86 Zp = GF(find_prime(options.modulus, blum=True))
87
88
89 class Protocol:
90
91 def setup_progress_bar(self):
92
93 class HowManyWidget(ProgressBarWidget):
94 "Showing the number of finished comparisons/total number"
95
96 def update(self, pbar):
97 return "Comparisons %s/%s" % (pbar.currval, pbar.maxval)
98
99 widgets = ['Sorting: ', Percentage(), ' ',
100 Bar(marker='0', left='[', right=']'),
101 ' ', ETA(), ' ', HowManyWidget()]
102 return ProgressBar(widgets=widgets,
103 maxval=Protocol.predict_sort(options.size))
104
105 def __init__(self, runtime):
106 self.progressbar = self.setup_progress_bar()
107 self.rt = runtime
108 self.comparisons = 0
109
110 array = self.make_array()
111 sorted = self.sort(array)
112
113 array = gather_shares(map(runtime.open, array))
114 sorted = gather_shares(map(runtime.open, sorted))
115
116 self.progressbar.start()
117
118 def finish(result):
119 self.progressbar.finish()
120 print # This line goes on top of the progressbar
121 dprint("Original array: %s", array)
122 dprint("Sorted array: %s", result)
123 print "Made %d comparisons" % self.comparisons
124 runtime.shutdown()
125
126 sorted.addCallback(finish)
127
128 @staticmethod
129 def predict_sort(array_size):
130 """ Calculate how many comparisons will be made by the bitonic
131 sort
132 >>> predict_sort(8)
133 24
134 >>> predict_sort(10)
135 33
136 """
137
138 def predict_bitonic_sort(n):
139 if n > 1:
140 m = n >> 1
141 return predict_bitonic_sort(m) + \
142 predict_bitonic_sort(n - m) + predict_bitonic_merge(n)
143 else:
144 return 0
145
146 def predict_bitonic_merge(n):
147 if n > 1:
148 m = 1 << (int(floor(log(n-1, 2))))
149 return n-m + predict_bitonic_merge(m) + \
150 predict_bitonic_merge(n - m)
151 else:
152 return 0
153
154 return predict_bitonic_sort(array_size)
155
156 def make_array(self):
157 array = []
158 for i in range(options.size):
159 inputter = (i % 3) + 1
160 if inputter == self.rt.id:
161 number = rand.randint(1, options.max)
162 print "Sharing array[%d] = %s" % (i, number)
163 else:
164 number = None
165 share = self.rt.shamir_share([inputter], Zp, number)
166 array.append(share)
167 return array
168
169 def sort(self, array):
170 # Make a shallow copy -- the algorithm wont be in-place anyway
171 # since we create lots of new Shares as we go along.
172 array = array[:]
173
174 def bitonic_sort(low, n, ascending):
175 if n > 1:
176 m = n // 2
177 bitonic_sort(low, m, ascending=not ascending)
178 bitonic_sort(low + m, n - m, ascending)
179 bitonic_merge(low, n, ascending)
180
181 def bitonic_merge(low, n, ascending):
182 if n > 1:
183 # Choose m as the greatest power of 2 less than n.
184 m = 2**int(floor(log(n-1, 2)))
185 for i in range(low, low + n - m):
186 compare(i, i+m, ascending)
187 bitonic_merge(low, m, ascending)
188 bitonic_merge(low + m, n - m, ascending)
189
190 def compare(i, j, ascending):
191
192 def tick_progressbar(dummy):
193 """This is added as a callback to the deferred in le, and
194 therefor must pass on the result of the comparison to
195 where it is actually used."""
196 self.comparisons += 1
197 self.progressbar.update(self.comparisons)
198 return dummy
199
200 def xor(a, b):
201 # TODO: We use this simple xor until
202 # http://tracker.viff.dk/issue60 is fixed.
203 return a + b - 2*a*b
204
205 le = array[i] <= array[j] # a deferred
206 le.addCallback(tick_progressbar)
207
208 # We must swap array[i] and array[j] when they sort in the
209 # wrong direction, that is, when ascending is True and
210 # array[i] > array[j], or when ascending is False (meaning
211 # descending) and array[i] <= array[j].
212 #
213 # Using array[i] <= array[j] in both cases we see that
214 # this is the exclusive-or:
215 b = xor(ascending, le)
216
217 # We now wish to calculate
218 #
219 # ai = b * array[j] + (1-b) * array[i]
220 # aj = b * array[i] + (1-b) * array[j]
221 #
222 # which uses four secure multiplications. We can rewrite
223 # this to use only one secure multiplication:
224 ai, aj = array[i], array[j]
225 b_ai_aj = b * (ai - aj)
226
227 array[i] = ai - b_ai_aj
228 array[j] = aj + b_ai_aj
229
230 bitonic_sort(0, len(array), ascending=True)
231 return array
232
233 # Run doctests
234 if options.test:
235 import doctest #pragma NO COVER
236 doctest.testmod(verbose=True) #pragma NO COVER
237
238 # Load configuration file.
239 id, players = load_config(args[0])
240
241 # Create a deferred Runtime and ask it to run our protocol when ready.
242 pre_runtime = create_runtime(id, players, 1,
243 options, runtime_class=Toft07Runtime)
244 pre_runtime.addCallback(Protocol)
245
246 # Start the Twisted event loop.
247 reactor.run()