Tlock Pay-What-You-Want

# Tlock Pay-What-You-Want This document discusses the usage of timelock encryption (TLE) to enable *honest* bidding for price discovery mechanisms. Specifically, we define a sealed-bid median-price auction and prove that truthful bidding is a dominant strategy. The goal is to allow a set of untrusted voters to reach consensus on a proposal's valuation (or various aspects of a proposal). ## Background ### Timelock Encryption > this is a very brief overview Timelock encryption is a cryptographic scheme where messages can be encrypted to future blocks in a chain (e.g. by running a drand-like protocol as a post-finality gadget, as in the Ideal Network - i.e. a randomness beacon based on threshold BLS signatures). Let $B$ be a blockchain and $ID$ be an identity function such that $ID(b) \in \{0, 1\}^*$ is collision-free. Then timelock encryption consists of the functions: ##### Encrypt For a message $m \in \{0, 1\}^*$ and block number $b$: $ct \xleftarrow{R} TL.Encrypt(m, ID(b))$ ##### Decrypt $m \leftarrow TL.Decrypt(ct, \sigma_b)$ where $\sigma_b$ is a signature produced by the blockchain which acts as a decryption key. ### Sealed-Bid Auctions Sealed-bid auctions are an auction technique where bids are all locked until a future deadline (the auction end). Apart from parties who collude, bidders are granted no insights into other bids until the deadline. There are two main types of sealed-bid auctions, first-price (where the winner pays what they bid) and second-price, or Vickrey auction (where the amount paid by the winner is the second highest bid). In a first-price auction, the Nash-equilibrium only ensures honest bids under specific conditions, meaning that it is not always an optimal solution to input a truthful bid. However, in a second-price auction, both theory and experimentation lead to the following theorem: Theorem 1. The dominant strategy in a sealed-bid second-price auction is to bid your true valuation. The proof can be found on page [59](https://homepages.cwi.nl/~apt/stra/ch7.pdf). ## Sealed-Bid Median-Price Discovery Mechanism We define a price discovery mechanism whose strategy encourages truthful bidding. I propose a sealed-bid approach where the final price is determined by calculating the median of the bids. The idea is that by relying on the median we are able to reduce the impacts of outlier bids that could skew the final valuation. First we will define the model and then prove that truthful bidding is a **dominant strategy** when participating. Auctions play a key part in price discovery within many industries, such as [setting the price of eggs](https://www.eggs.org/about) and [energy](https://www.usaid.gov/energy/auctions/introduction) in the USA. Our assumptions for price discovery mechanisms deviate from that of a standard auction, but the general principals remain truthful. In our case, participants are *cooperating* (rather than competing) to determine a reasonable valuation for a proposal which would recieve funding from a commonly owned treasury. #### Sealed-Bid Median Price Discovery Mechanism Let $P$ be a proposal whose voting period terminates at some time $D$ in the future. Let $n > 0$ and $V = \{V_i\}_{i \in [n]}$ be the set of voters. Each voter chooses a valuation $b_i$ and timelock encrypts it for the deadline $D$, calculating $b_i^D \leftarrow TL.Enc(b_i, ID_d)$ and submitting the ciphertext (or CID to the ciphertext). Assume that all voters participate and by the deadline $D$ all voters know the set $\{b_i^D\}_{i \in [n]}$. After all bids are decrypted, the final valuation is the median of the set, $b = median(\{b_i\}_{i \in [n]})$. > We assume there is some total reward amount $R$ that is distributed to voter who participate. Q: where should this reward come from? From the proposer? ##### Reward Function We introduce a Bell curve on top of the results which determine the reward function, with the greatest reward going to the voters who determined the median (split evenly if multiple). As votes move further away from the median, they are rewarded less, with significant outliers receiving no reward. Thus, the payout for a bidder is given by: $R(i) = exp(- \frac{(b_i - b)^2}{2\sigma^2})$ > Q: Where does the money come from for the reward? We assume that each voter can submit only a single, unweighted vote. In this simplified model voters are not influenced or restricted based on their stake in the network (e.g. no conviction voting). > for now assume no type of conviction voting, but something to explore in the near future #### Claim: Bidding an honest valuation is an optimal strategy in the SBMPD > Note: this is not a formal proof, more of a discussion. We claim that honest bidding is encouraged by the protocol. The idea is that since the median price being incalculable prior to the deadline, players have no specific means to determine what the current median valuation is. By defining a reward function based on proximity to the output median valuation, the protocol ensures that bidding a true valuation is an optimal strategy. Suppose a proposal $P$ is being considered with a deadline $D$. For a voter $V_i$, let $s_i$ be their honest bid. Then $V_i$'s bid can either be: 1) Below the median value: An honest valuation is below the median. 2) Above the median value: An honest valuation is above the median. 3) At the median: An honest valuation is at the median. We now show discuss each case to determine the best strategy for each bidder. We show that: 1) if a bid is below the median then a dominant strategy is to overbid 2) if a bid is above the median then a dominant strategy is to underbid. If bids were not sealed, then the median can easily be influenced or skewed upward or downard, making the final price easy to manipulate. However, with sealed bids, no information about the median calculation can be determined prior to the deadline. Since no information about the median value can be known before the deadline there is equal likelihood that a bid will be above or below the median. Thus, they are better off bidding a true valuation, else they risk forfeiture of potential rewards. ###### Case 1: Below the median We show that if a bid is below the median, then the dominant strategy is to **overbid**. Suppose $P_i$ bids some $b_i < m_i$. Then either (I) $s_i < b_i < m_i$ or (II) $b_i < s_i < m_i$. In both cases the bidder can potentially (but not necessarily) apply downward pressure to the median. In case (I), their reward is higher than in case (II), as it is based on proximity to the median. Thus, if a bid is less than the median then it is a dominant strategy to **overbid**, so choosing a valuation $b_i$ such that $s_i < b_i$. ###### Case 2: Underbidding Similarly to case 1, suppose $P_i$ bids some $m_i < b_i$. Then either (I) $m_i < b_i < s_i$ or (II) $m_i < s_i < b_i$. In both cases the bidder can potentially (but not necessarily) apply upward pressure to the median. In case (I), their reward is higher than in case (II), as it is based on proximity to the median. Thus, if a bid is less than the median then it is a dominant strategy to **underbid**, so choosing a valuation $b_i$ such that $b_i < s_i$. ###### Case 3: Honest Bids All bids are sealed until the deadline $D$, with no players learning information about bids until then. If a player submits an honest bid, then they have an equal opportunities of being above or below the median.