Wednesday, August 14, 2013

SIGCOMM2013: Verifiable auctions for online ad exchanges

Presenter: Sebastian Angel

Today's online advertising ecosystem is unnecessarily predicated on trusting ad exchanges, disenfranchising advertisers and publishers.  The goal of this work is remove that trust requirement by making auctions verifiable.  Providing verifiability while respecting today's online advertising ecosystem is technically challenging for several reasons: we need to be able to handle millions of auctions per second, we do not want to introduce significantly latency in web page load times, submitted bids cannot be disclosed, and we cannot require participants to know each other.

VEX provides verifiablity through two phases: action and audit.  During the auction phase, advertisers provide both their bid price and an encoding of their bid price, and the ad exchange provides the selected price (and advertiser) and a list of encoded bids received from all advertisers. Bids are encoded by computing a chain of n+1 hashes, where n is the bid price, on a seed shared by all advertisers.  Given an encoded bid it is hard to determine the number of nodes in the chain (i.e., the bid price), but we can use an encoding from an earlier node in the chain to prove an encoded bid is correct.  This allows us to check three correctness conditions: there exists a bid that equals the selected price, there are m-2 bids less than the selected price, and there exists a highest bid that is greater than or equal to the second-highest bid.

The limits of VEX include disclosing the sale price and only achieving suitable performance for small bid ranges.  Most of VEX's latency overhead comes from an extra round of communication.  The overhead decreases as the number of bidders increases, but so does the maximum throughput.

Q: Why is verifiability implemented inline on a per-auction basis?
A: Verifiability is offline, but performance is still important.

Q: Auctions do not have an incentive to deviate from the status quo because advertisers known their click-through rate and the cost they paid for advertising. What additional information is this verifying is provided from an economic perspective?
Answer taken offline.