VIFF runtime. This is where the virtual ideal functionality is hiding! The runtime is responsible for sharing inputs, handling communication, and running the calculations.
Each player participating in the protocol will instantiate a Runtime object and use it for the calculations.
The Runtime returns Share objects for most operations, and these can be added, subtracted, and multiplied as normal thanks to overloaded arithmetic operators. The runtime will take care of scheduling things correctly behind the scenes.
A shared number.
The Runtime operates on shares, represented by this class. Shares are asynchronous in the sense that they promise to attain a value at some point in the future.
Shares overload the arithmetic operations so that x = a + b will create a new share x, which will eventually contain the sum of a and b. Each share is associated with a Runtime and the arithmetic operations simply call back to that runtime.
Clone a share.
Works like util.clone_deferred() except that it returns a new Share instead of a Deferred.
Create a share that waits on a number of other shares.
Roughly modelled after the Twisted DeferredList class. The advantage of this class is that it is a Share (not just a Deferred) and that it can be made to trigger when a certain threshold of the shares are ready. This example shows how the pprint() callback is triggered when a and c are ready:
>>> from pprint import pprint
>>> from viff.field import GF256
>>> a = Share(None, GF256)
>>> b = Share(None, GF256)
>>> c = Share(None, GF256)
>>> shares = ShareList([a, b, c], threshold=2)
>>> shares.addCallback(pprint) # doctest: +ELLIPSIS
<ShareList at 0x...>
>>> a.callback(10)
>>> c.callback(20)
[(True, 10), None, (True, 20)]
The pprint() function is called with a list of pairs. The first component of each pair is a boolean indicating if the callback or errback method was called on the corresponding Share, and the second component is the value given to the callback/errback.
If a threshold less than the full number of shares is used, some of the pairs may be missing and None is used instead. In the example above the b share arrived later than a and c, and so the list contains a None on its place.
Send and receive shares.
All players are connected by pair-wise connections and this Twisted protocol is one such connection. It is used to send and receive shares from one other player.
The marshal module is used for converting the data to bytes for the network and to convert back again to structured data.
Send a share.
The program counter and the share are marshalled and sent to the peer.
Make method automatically increment the program counter.
Adding this decorator to a Runtime method will ensure that the program counter is incremented correctly when entering the method.
Create a Runtime and connect to the other players.
This function should be used in normal programs instead of instantiating the Runtime directly. This function makes sure that the Runtime is correctly connected to the other players.
The return value is a Deferred which will trigger when the runtime is ready. Add your protocol as a callback on this Deferred using code like this:
def protocol(runtime):
a, b, c = runtime.shamir_share([1, 2, 3], Zp, input)
a = runtime.open(a)
b = runtime.open(b)
c = runtime.open(c)
dprint("Opened a: %s", a)
dprint("Opened b: %s", b)
dprint("Opened c: %s", c)
runtime.wait_for(a,b,c)
pre_runtime = create_runtime(id, players, 1)
pre_runtime.addCallback(protocol)
This is the general template which VIFF programs should follow. Please see the example applications for more examples.
Basic VIFF runtime with no crypto.
This runtime contains only the most basic operations needed such as the program counter, the list of other players, etc.
Whenever a share is sent over the network, it must be uniquely identified so that the receiving player known what operation the share is a result of. This is done by associating a program counter with each operation.
Keeping the program counter synchronized between all players ought to be easy, but because of the asynchronous nature of network protocols, all players might not reach the same parts of the program at the same time.
Consider two players A and B who are both waiting on the variables a and b. Callbacks have been added to a and b, and the question is what program counter the callbacks should use when sending data out over the network.
Let A receive input for a and then for b a little later, and let B receive the inputs in reversed order so that the input for b arrives first. The goal is to keep the program counters synchronized so that program counter x refers to the same operation on all players. Because the inputs arrive in different order at different players, incrementing a simple global counter is not enough.
Instead, a tree is made, which follows the tree of execution. At the top level the program counter starts at [0]. At the next operation it becomes [1], and so on. If a callback is scheduled (see schedule_callback()) at program counter [x, y, z], any calls it makes will be numbered [x, y, z, 1], then [x, y, z, 2], and so on.
Maintaining such a tree of program counters ensures that different parts of the program execution never reuses the same program counter for different variables.
The increment_pc() decorator is responsible for dynamically building the tree as the execution unfolds and schedule_callback() is responsible for scheduling callbacks with the correct program counter.
See Program Counters for more background information.
Generate preprocess material.
The program specifies which methods to call and with which arguments. The generator methods called must adhere to the following interface:
The ActiveRuntime.generate_triples() method is an example of a method fulfilling this interface.
Schedule a callback on a deferred with the correct program counter.
If a callback depends on the current program counter, then use this method to schedule it instead of simply calling addCallback directly. Simple callbacks that are independent of the program counter can still be added directly to the Deferred as usual.
Any extra arguments are passed to the callback as with addCallback().
Shutdown the runtime.
All connections are closed and the runtime cannot be used again after this has been called.
Make the runtime wait for the variables given.
The runtime is shut down when all variables are calculated.
The VIFF runtime.
The runtime is used for sharing values (shamir_share() or prss_share()) into Share object and opening such shares (open()) again. Calculations on shares is normally done through overloaded arithmetic operations, but it is also possible to call add(), mul(), etc. directly if one prefers.
Each player in the protocol uses a Runtime object. To create an instance and connect it correctly with the other players, please use the create_runtime() function instead of instantiating a Runtime directly. The create_runtime() function will take care of setting up network connections and return a Deferred which triggers with the Runtime object when it is ready.
Addition of shares.
Communication cost: none.
Multiplication of shares.
Communication cost: 1 Shamir sharing.
Open a secret sharing.
The receivers are the players that will eventually obtain the opened result. The default is to let everybody know the result. By default the threshold + 1 shares are reconstructed, but threshold can be used to override this.
Communication cost: every player sends one share to each receiving player.
Creates pseudo-random secret sharings.
This protocol creates a secret sharing for each player in the subset of players specified in inputters. Each inputter provides an integer. The result is a list of shares, one for each inputter.
The protocol uses the pseudo-random secret sharing technique described in the paper “Share Conversion, Pseudorandom Secret-Sharing and Applications to Secure Computation” by Ronald Cramer, Ivan Damgård, and Yuval Ishai in Proc. of TCC 2005, LNCS 3378. Download
Communication cost: Each inputter does one broadcast.
Share a random bit over field and GF256.
The protocol is described in “Efficient Conversion of Secret-shared Values Between Different Fields” by Ivan Damgård and Rune Thorbek available as Cryptology ePrint Archive, Report 2008/221.
Generate shares of a uniformly random element from the field given.
If binary is True, a 0/1 element is generated. No player learns the value of the element.
Communication cost: none if binary=False, 1 open otherwise.
Secret share number over field using Shamir’s method.
The number is shared using polynomial of degree threshold (defaults to threshold). Returns a list of shares unless unless there is only one inputter in which case the share is returned directly.
Communication cost: n elements transmitted.
Subtraction of shares.
Communication cost: none.
A runtime secure against active adversaries.
This class currently inherits most of its functionality from the normal Runtime class and is thus not yet secure.
Multiplication of shares.
Preprocessing: 1 multiplication triple. Communication: 2 openings.
Share a random secret.
The guarantee is that a number of shares are made and out of those, the T that are returned by this method will be correct sharings of a random number using degree as the polynomial degree.
Double-share a random secret using two polynomials.
The guarantee is that a number of shares are made and out of those, the T that are returned by this method will be correct double-sharings of a random number using d1 and d2 as the polynomial degrees.
Generate multiplication triples.
These are random numbers a, b, and c such that c = ab. This function can be used in pre-processing.
Returns a tuple with the number of triples generated and a Deferred which will yield a list of 3-tuples.
Perform one or more Bracha broadcast(s).
The list of senders given will determine the subset of players who wish to broadcast a message. If this player wishes to broadcast, its ID must be in the list of senders and the optional message parameter must be used.
If the list of senders consists only of a single sender, the result will be a single element, otherwise it will be a list.
A Bracha broadcast is reliable against an active adversary corrupting up to t < n/3 of the players. For more details, see the paper “An asynchronous [(n-1)/3]-resilient consensus protocol” by G. Bracha in Proc. 3rd ACM Symposium on Principles of Distributed Computing, 1984, pages 154-162.