tinybid module

Minimal pure-Python library that implements a basic single-item first-price auction via a secure multi-party computation (MPC) protocol.

class tinybid.tinybid.node

Bases: object

Data structure for maintaining the information associated with a node and performing node operations.

Suppose that a workflow is supported by three nodes (parties performing a decentralized auction). The node objects would be instantiated locally by each of these three parties.

>>> nodes = [node(), node(), node()]

The preprocessing workflow that the nodes must execute can be simulated using the preprocess function. The number of bids that a workflow requires must be known, and it is assumed that all permitted bid prices are integers greater than or equal to 0 and strictly less than a fixed maximum value. The number of bids and the number of distinct prices must be supplied to the preprocess function.

>>> preprocess(nodes, bids=4, prices=16)

Each bidder must then submit a request for the opportunity to submit a bid. The bidders can create request instances for this purpose. In the example below, each of the four bidders creates such a request.

>>> request_zero = request(identifier=0)
>>> request_one = request(identifier=1)
>>> request_two = request(identifier=2)
>>> request_three = request(identifier=3)

Each bidder can deliver their request to each node, and each node can then locally use its masks method to generate masks that can be returned to the requesting bidder.

>>> masks_zero = [node.masks(request_zero) for node in nodes]
>>> masks_one = [node.masks(request_one) for node in nodes]
>>> masks_two = [node.masks(request_two) for node in nodes]
>>> masks_three = [node.masks(request_three) for node in nodes]

Each bidder can then generate locally a bid instance (i.e., a masked bid price).

>>> bid_zero = bid(masks_zero, 7)
>>> bid_one = bid(masks_one, 11)
>>> bid_two = bid(masks_two, 2)
>>> bid_three = bid(masks_three, 11)

Every bidder can broadcast its masked bid to all the nodes. Each node can locally assemble these as they arrive. Once a node has received all masked bids, it can determine its shares of the overall outcome of the auction using the outcome method.

>>> shares = [
...     node.outcome([bid_zero, bid_one, bid_two, bid_three])
...     for node in nodes
... ]

The overall outcome can be reconstructed from the shares by the auction operator using the reveal function. The outcome is represented as a set containing the int identifiers of the winning bidders.

>>> list(sorted(reveal(shares)))
[1, 3]

masks(request)

Return masks for a given request.

Parameters

request (Iterable[Tuple[int, int]]) – Request from bidder.

Return type

List[Dict[Tuple[int, int], modulo]]

outcome(bids)

Perform computation to determine a share of the auction outcome.

Parameters

bids (Sequence[bid]) – Sequence of masked bids.

Return type

List[modulo]

class tinybid.tinybid.request(identifier)

Bases: List[Tuple[int, int]]

Data structure for representing a request to submit a bid. A request can be submitted to each node to obtain corresponding masks for a bid.

Parameters

identifier (int) – Integer identifying the requesting bidder.

The example below demonstrates how requests can be created.

>>> request(identifier=1),
([(0, 1)],)
>>> request(identifier=3),
([(0, 3)],)

class tinybid.tinybid.bid(masks, price)

Bases: List[Dict[Tuple[int, int], modulo.modulo.modulo]]

Data structure for representing a bid that can be broadcast to nodes.

Parameters

• masks (List[List[Dict[Tuple[int, int], modulo]]]) – Collection of masks to be applied to the bid price.

• price (int) – Non-negative integer representing the bid price.

Suppose masks have already been obtained from the nodes via the steps below.

>>> nodes = [node(), node(), node()]
>>> preprocess(nodes, bids=4, prices=16)
>>> identifier = 2
>>> price = 7
>>> masks = [node.masks(request(identifier)) for node in nodes]

This method can be used to mask the bid price (in preparation for broadcasting it to the nodes).

>>> isinstance(bid(masks, price), bid)
True

tinybid.tinybid.preprocess(nodes, bids, prices)

Simulate a preprocessing workflow among the supplied nodes for a workflow that supports the specified number of bids and distinct prices (where prices are assumed to be integers greater than or equal to 0 and strictly less than the value prices).

Parameters

• nodes (Sequence[node]) – Collection of nodes involved in the workflow.

• bids (int) – Number of bids.

• prices (int) – Number of distinct prices (from 0 to prices).

The example below performs a preprocessing workflow involving three nodes.

>>> nodes = [node(), node(), node()]
>>> preprocess(nodes, bids=4, prices=16)

tinybid.tinybid.reveal(shares)

Reconstruct the auction outcome from the shares obtained from each node.

Parameters

shares (List[List[modulo]]) – Outcome shares (where each share is a list of components, with one component per permitted price).

Suppose the shares below are returned from the three nodes in a workflow.

>>> p = 4215209819
>>> shares = [
...     [modulo(3, p), modulo(5, p), modulo(4, p)],
...     [modulo(1, p), modulo(2, p), modulo(9, p)],
...     [modulo(8, p), modulo(0, p), modulo(8, p)]
... ]

This method combines such shares into an overall outcome be reconstructing the individual components and decoding the identifiers of the winning bidders.

>>> reveal(shares)
{1}

Return type

Set[int]