Example costs

 

Let us assume we have m=4 auctioneers (so t=1, no single auctioneer can cheat or violate privacy), and let , so each point is 12 bytes. We will estimate the communication costs (in terms of rounds, messages, and bytes) for two sample auctions. We will assume that all bids must be verified immediately (this maximizes the number of messages needed during bid submission), that the leading digit of the selling price is non-zero (worst-case). Costs will be counted as the total of sent and received for both bytes and messages.

Example 1: Consider the case with n=1000 bidders, V=1024 possible prices, and base c=2 bid encoding (so d=10).

• Bid submission. Each bidder sends 4 messages of 480 bytes each. Each auctioneer receives one of these messages and then sends 120 bytes to each other auctioneer. Total communication for each auctioneer during submission is in 7000 total messages.
• Bid resolution. In the first round of the protocol, phase 1 is unnecessary, so there will be 10 multiplications over 3 communication rounds. The remaining 9 protocol rounds each require 1010 multiplications and 5 communication rounds. Each multiplication requires 480 bytes of communication between each pair of auctioneers. Total communication for each auctioneer is in 288 messages over 48 communication rounds.

Example 2: Consider the case with n=50 bidders, V=1024 possible prices, and base c=4 bid encoding (so d=5).

• Bid submission. Each bidder sends 4 messages of 720 bytes each. Each auctioneer receives one of these messages and then sends 180 bytes to each other auctioneer. Total communication for each auctioneer during submission is 90K bytes in 350 total messages.
• Bid resolution. In the first round of the protocol, phase 1 is unnecessary, so there will be 18 multiplications over 3 communication rounds. The remaining 4 protocol rounds each require 168 multiplications and 5 communication rounds. Each multiplication requires 480 bytes of communication between each pair of auctioneers. Total communication for each auctioneer is in 138 messages over 23 communication rounds.