1 Introduction
Bitcoin, and more broadly blockchain systems, rely on the willingness of honest players to participate in the system. A good blockchain system should have simple, practical designs with suitable security guarantees against cheating. The incentive compatibility (IC) concept which seeks to incentivize the participants to be truthful is playing an increasingly central role in the design of distributed financial systems.
Recently, Lavi, Sattath and Zohar [8] started a study of the subject of Bitcoin Fee Market design. In this market, there are two kinds of players: the users who have transaction records that need to be certified and registered in the bitcoin system, and the miners who create new blocks to include the transactions and get them certified. Each user declares the maximal amount she is willing to pay for her transaction, and the miners use a mechanism to decide which transactions to include and how much fee to charge each user. A primary focus of their study is the Monopolistic Price (MP) mechanism, which is a natural and practical mechanism, although not IC in the strict sense (see Section 2 below). Their extensive simulations indicate that the mechanism does not deviate too much from being IC for most iii distributions, as the number of users grows large. An analysis was given for the special case of discrete distributions of finite size. They suggest that MP might be a good alternative to the “pay your bid” auction, which is subject to low bids and revenue. It is posed as a conjecture that the MP mechanism is nearly-IC for general iid distributions.
We will prove that MP is nearly-IC for any iid distribution as grows large, thus mathematically validating the strong simulation results obtained in [8]. Note that the standard IC criterion (in auction market) only addresses one kind of attack, namely, the reporting of an untruthful bid value. There are other possible attacks by Bitcoin users: for example, in the multiple strategic bids (MSB) attack discussed in [8], a user could gain advantage by splitting his transaction into several transactions and bidding separately. This strategy could even enable a losing transaction to be included in the block. We will also prove the nearly-IC conjecture for MP with respect to the MSB attack.
We consider another mechanism, called the RSOP (Random Sampling Optimal Price) auction, which was first defined by Goldberg et al. [5] in the digital goods context and shown to be truthful. We prove that the RSOP revenue is always dominated by the MP revenue, as conjectured in [8]. In fact, the revenue difference can be arbitrarily large for some distributions, prompting us to look more deeply into possible correlation between IC and revenue in general (Theorem 6-8).
The contributions of the present paper are two-fold. First, we prove the Monopolistic Price mechanism to be nearly-IC, confirming the previous strong experimental data. This holds true against the MSB attack as well. We also show MP to dominate the RSOP auction in revenue. These results lend support to MP as a Bitcoin fee design candidate. Secondly, the methodology used in our proofs involves sophisticated mathematical analysis. It demonstrates that theoretical computer science can provide powerful tools to complement system design for blockchains. Finally, we believe that the emerging area of incentive compatible blockchain design is an exciting research area with many intriguing problems to solve, for theorists and system designers alike.
Related Work: The basic model for Bitcoin fee market introduced in [8] in fact resembles the maximum revenue problem for Digital Goods as considered by Goldberg et al. [4][5]. The MP mechanism is similar to the optimal omniscient auction in [5]. However, The Bitcoin fee market differs from digital goods in its additional features: such as the auctioneer may delete or insert bids, or the users may split bids. This makes the Bitcoin fee design a rich and relevant new research subject for auction theory and mechanism design. Among those work closely related to the current subject include Babaioff et al. [1], Kroll et al. [6], Carlsten et al. [3], Bonneau [2], Huberman et al. [7]. To formulate meaningful incentive models, there is much research work in Bitcoin which provides important ingredients for consideration. A more complete survey of related work can be found in [8, Section 1.3].
2 Review of the Models and Known Results
We first review the Bitcoin fee model and several mechanisms defined and studied in [8]. A miner acts as a monopolist who offers users to include their transactions in the miner’s next block for a fee. Each user has one transaction that needs this service and is willing to pay a fee up to some value . The miner’s problem is to design a mechanism to extract good revenue. The standard Bitcoin mechanism in use is a pay-your-bid system, where the miner simply takes the highest bids to fill the capacity of the block. This mechanism may not receive good revenue, since some bidders may not reveal the true value of the fees they are willing to pay. In view of this, some alternative mechanisms are proposed in [8] and their security properties considered, which we will review below.
2.1 The Monopolistic Price (MP) Mechanism
Suppose user bids for . Sort into a decreasing sequence . Define the monopolistic price as . Denote by the maximizing (in case of ties, is taken to be the maximal one). The miner will include all users with the highest bids and simply charge each one of them the same fee . Call this the monopolistic price . This mechanism gives the miner revenue , which is obviously the maximum revenue obtainable if all accepted bids must be charged a single price.
The above MP Mechanism is not truthful. [8] analyzed how serious the non-truthfulness can be; we review their results below.
Consider any user
and the vector of bids
of the other users. Let, and
.
To measure how much temptation there is for the users to shade their bids, define the discount ratio for user :
This ratio captures the gain a user can obtain by bidding strategically (instead of truthfully).
A major theme of [8] is to investigate how large the discount ratio will typically be. Assume all true values are drawn iid from some distribution on . Two measures are defined: the worst-case measure and the average case one. For the former, let
For the latter, let
Clearly, for every and , we have , since for any .
An analysis was given in [8] for the special case of discrete distributions of finite size.
Theorem A [8, Theorem 2.3]
For any distribution with a finite support size, . (This implies also
for such .)
Based on extensive simulations done for a variety of distributions, the authors made the following conjecture that MP is nearly IC for general iid distributions as gets large.
Nearly IC Conjecture for MP [8, Conjecture 2.5]
1. For any distribution , . Specifically .
2. If has a bounded support, . Specifically .
3. There exists a distribution with an unbounded support such that .
In the -notation above, the constants may depend on . Part of the basis for their conjecture 3 is the Inverse distribution where (for ). Experimentally, it appears that for this , , while .
The main purpose of our paper is to settle the Nearly IC Conjecture for MP in the positive.
Multiple Strategic Bids (MSB) Attack
It was shown in [8] that a user could gain advantage by splitting his bid into several transactions with separate bids. This strategy could even enable a losing transaction to be included in the block. Let
It is conjectured that the Nearly-IC Conjecture holds even under this stronger attack. We will show that this is indeed the case.
2.2 The Random Sampling Optimal Price (RSOP) Auction
We consider another mechanism, called the RSOP (Random Sampling Optimal Price) auction, first defined by Goldberg et al. [5] in the digital goods context.
Definition. [RSOP auction]
Upon receiving bids , the auctioneer randomly partitions the bids into two disjoint sets and , and computes the monopolistic price for each set: , (with the monopolistic price for an empty set being set to ). Finally, the set of winning bids is , where and . The bidders in each pays , and the bidders in each pays .
Note the revenue obtained in this auction is
Theorem B (Goldberg et al. [5])
The RSOP auction is truthful. For any with (where is a constant) for all , we have
In [8], several variants of RSOP were examined and simulation carried out which led to the following conjecture.
Dominance Conjecture of MP over RSOP [8, Conjecture 5.4]
For any and all choices of and , the RSOP revenue is at most the monopolistic price revenue. That is, .
The MP Dominance Conjecture has relevance to the robustness of RSOP against adding false bids or deleting bids by the auctioneer (see discussions in [8]). In the present paper we prove the MP Dominance Conjecture to be true.
3 Main Results
In this paper we settle the Nearly-IC Conjecture (even allowing for the MSB attack) and the MP Dominance Conjecture mentioned above: the former in Theorem 1-4, and the latter in Theorem 5. Additionally, we investigate the possible correlation between incentive compatibility and revenue. In this regard, we demonstrate that distributions with unbounded support can exhibit different characteristics from the bounded ones, and these findings will be presented in Theorems 6-8.
3.1 Nearly Incentive Compatibility of MP
We prove that mechanism MP is nearly incentive compatible for large in Theorems 1-3.
Theorem 1. For any distribution on bounded support, .
Theorem 2. For any distribution , .
Remark 1. The proof in Theorem 1 can be refined to show that where is a constant independent of , while the constant in the -notation is -dependent. Similarly, Theorem 2 can be strengthened to when satisfies . The analysis follows the same outline as the proofs for Theorems 1, 2 above but the details are more complicated. They will be left for a later version of the paper.
Recall that the distribution Inverse is defined as for .
Theorem 3. For Inverse, for all , where is some absolute constant.
Theorem 4. With respect to the MSB attack, the Monopolistc Pricing Mechanism is nearly incentive compatible, i.e., Theorems 1-2 are still valid.
3.2 The Effect of IC on Revenue
Theorem 5. For any , .
Theorem B of Goldberg et al. [5] says that, RSOP yields asymptotically the same revenue as the monopolistic price mechanism when the distribution has a bounded support . We point out that this is not always true when has infinite support.
Theorem 6. For Inverse,
Let . For example, for Inverse. A key difference between RSOP and the monopolistic price mechanism is that, the former is incentive compatible (and thus cannot extract revenue more than ), while the latter is not incentive compatible.
Suppose we are given Inverse as value distribution. Theorem 6 above shows that Monopolistic Price can extract an unbounded revenue in this case. Is the property derived in Theorem 3 in fact a necessary condition for all such mechanisms? The following theorem shows that the answer is more complex.
For any mechanism and bid vector , let be the revenue collected.
Theorem 7. Let Inverse.
(a) There exists a mechanism such that and
(b) Let be any fixed constant. Any mechanism such that for all must satisfy
Note that and are not the only ways to quantify a mechanism’s closeness to being incentive compatible. Two standard ways to define being -close to IC (or more generally, to Nash equilibrium) are
(1) Additively -close: , or
(2) Multiplicatively -close: .
We will show that, adopting the “multiplicatively -close” definition, one can obtain nearly IC mechanisms that derive infinite revenue under the distribution Inverse. This is in contrast to the previous discount model defined in terms of .
Let be any IC mechanism (such as RSOP). For any bid vector , let be the fee paid by user (if is a winner), and be the utility. For any , let be the mechanism that uses the same allocation rule as , with the fee modified to be . The following theorem is easy to prove.
Theorem 8.
(a) is multiplicatively -close to IC;
(b)
Theorem 8 implies that RSOP can be easily modified to become a multiplicatively -close-to-IC mechanism such that, like MP, its revenue is infinite under Inverse.
We will prove Theorems 1-3, 5 in the following sections. The proof for the Multiple Strategic Bids model of Theorem 4 is similar in essence to the basic model, and hence will be omitted. We also leave out the proofs of Theorem 6-8.
4 An Overview of the Proof for Theorem 1
Theorem 1 is the most difficult to prove. In this section we give some intuition and an overview of the proof.
Let be a distribution over . Let be generated according to iid , and denote by the sorted list of the . By Claim A9 in [8], , i.e. the maximum discount ratio is achieved by the user with the highest bid. This leads immediately to a necessary condition on , the optimal strategic bid by the highest bidder, as we state below.
Lemma 1. [Optimal Strategic Bid (OSB) Condition]
Let . If , where , then there exists such that , where is defined by .
Lemma 1 states that, in order to have a sizable , there has to exist a some distance away from such that is only a constant smaller than the sampled maximum . We will prove Theorem 1 by showing that a random is stochastically unlikely to satisfy the OSB necessary condition.
As a start, we prove Theorem 1 when the distribution has a unique where
is achieved. The law of large number implies that, for large
, every satisfies (whereis some fixed constant) with overwhelming probability. Coupled with the fact
and probabilistically, we see that the OSB condition in Lemma 1 cannot hold. Hence we have shown Theorem 1 for the case when has a maximum achieved at a unique point .The above argument does not apply when achieves maximum value at multiple points. As an extreme case, consider the Inverse distribution modified as follows:
In this case, for all .
Hence the challenge is to prove that, even for extreme cases like the above, the OSB condition in Lemma 1 cannot be met except with vanishingly small probability. At the top level, we wish to show that, in any two subintervals separated by a non-negligible distance, the maximum values and cannot achieve perfect correlation to allow except with negligible probability for large . This claim takes a non-trivial proof since intervals and , being taken from the sorted version of , are correlated to a certain degree.
Before proving Theorem 1, we first recast Lemma 1 in an new form which does not reference the quantity . The main advantage of Lemma 1A is that, the condition now refers only to the quantities , thus making it easier to analyze how likely the condition can be satisfied stochastically.
Lemma 1A. [Optimal Strategic Bid (OSB) Condition]
Let and . If , then there exists such that
.
Proof. Take the as specified in Lemma 1. The following constraints are satisfied: write and , then
(1) | ||||
(2) |
Let for . Let such that where . It is easy to verify from Eq. (1), (2) that
(3) | ||||
(4) |
Note that Eq. (4) implies
(5) |
We now prove Lemma 1A.
Case 1. If , then choose depending on which gives the larger . This satisfies Lemma 1A, as a consequence of Eq. (1) and (5).
Case 2. . Eq. (3) implies , and thus
(6) |
From Eq. (4) and the fact , we have
Using Eq. (6), we obtin
Taking satisfies Lemma 1A. ∎
5 Proof of Theorem 1
For simplicity of presentation, we assume that has support . Without loss of generality, we can assume that for any . Some additional arguments are needed for the general case ; we omit them here.
We will demonstrate that for a random , the condition stated in Lemma 1A occurs with probability at most . That is, stochastically, the pair with the stated property rarely exists. First some notation. Let . To start the proof, we pick a point with the following properties:
P1: is a forbidden zone for . Precisely, for a random , the probability of is .
P2: .
Fact 1 exists.
Proof. Let be the maximal achieving .
Case 1. If , then is empty and .
Case 2. If , then choose any . Choose . Then for large , the probability of is , satisfying P1. We also have , thus satisfying P2. ∎
Divide into disjoint intervals of length , that is, write where for , and . Take a random , which is the sorted list of iid . Let
denote the random variable
. Let be the random variable . Let denote the event thatNow note that, for , the OSB condition for in Lemma 1A can hold only if either 1) and for some , or 2) .
Lemma 2. .
Proof. Immediate from property P1 and Lemma 1A. ∎
The rest of this section is devoted to the proof of the following lemma, which indicates that and are not correlated to be nearly identical.
Lemma 3. [Weak Correlation Lemma] For each , .
There are two cases to consider.
Case 1. ;
Case 2. .
We give the proof of Case 1. The proof for Case 2 uses the same general idea, and will only be sketched with details omitted here. Assume we have Case 1. Let be the distribution (normalized) when is restricted to the interval . Let
Consider the generation of a random in the following alternative (but equivalent) way.
Phase 1. Generate a random integer so that
for , where .
Phase 2. Generate iid random numbers , and sort them into decreasing order . (Note that is already determined after the completion of Phase 2.)
Phase 3. Generate one number at a time. After step , we sort the numbers into decreasing order . Let
At time , is exactly the same random variable as .
We prove two facts below, from which Lemma 3 follows immediately.
Fact 2 In Phase 1, with probability .
Proof. Chernoff’s bound. ∎
After Phase 1 and 2, we have and decided. To prove Lemma 3 we only need to show that, in Phase 3, there is enough randomness so that is unlikely to have a value within an additive constant to .
Let us examine the evolution of as a random process of infinite length. The random sequence satisfies , and
for .
Fact 3 At , we have
Proof. (Sketch). Let be the total number of times in the above process when either the second or third selection is made by , for . Let be the projected sequence. Note , , and in fact for any . Relabel as , and consider the random sequence . Let be the portion of the sequence in the range . It is easy to verify that, for the random sequence
(7) |
To see this, note that there is at least a constant probability to increase the next value by 1 (or more). Thus, to increase the value by , it takes only steps on average, rarely requiring a factor more steps.
As for any , we conclude that . This completes the proof of Case 1.
In Case 2, . We have lost the source of randomness critical for the above argument since . Yet the source of randomness can be obtained by splitting into suitably, so that does not contain any with anywhere close to the level of . (This will rely critically on the fact .) We omit here the details of implementing this plan, as well as the necessary handling of discontinuities in distribution . This finishes the proof of Lemma 3 and thus Theorem 1. ∎.
6 Proof of Theorem 2
For any , we show that
(8) |
for all sufficiently large . First pick such that . Take iid and let be the probability of exactly of the falling into . Let . By the law of large numbers, there exists such that for all ,
(9) |
Consider the distribution , obtained from restricting to . By Theorem 1, there exists such that
(10) |
for all . We are now set for proving Theorem 2. By definition of , we have
Using Eq. (9)-(10), we obtain for all ,
This proves Eq. (8) and Theorem 2. ∎
7 Proof of Theorem 3
Consider iid random variables distributed according to the Inverse distribution , and let be their sorted sequence. Let , , and let be the event . Let be the event . Theorem 3 is an immediate consequence of the following two lemmas.
Lemma 4. If satisfies event , then .
Lemma 5.
.
Lemma 4 and 5 imply
where
This proves Theorem 3.
To prove Lemma 4, note that when occurs, the highest bidder has a monopolistic price and a strategic price less than . Thus for the highest bidder , we have . This proves Lemma 4.
Lemma 5 follows from the following facts:
Fact 4 .
Proof.
∎
Fact 5 .
Proof. Let be iid distributed according to , where for ,
Define , where is the sorted sequence of . Clearly,
To prove Fact 5, it suffices to prove:
(11) |
For any , let be the number of ’s satisfying , and be the event that . Let for . As the event implies , we have
(12) |
Observe that . Using Chernoff’s bound, we have
(13) |
Equation (11) follows from (12) and (13) immediately. This completes the proof of Fact 5 and Theorem 3. ∎
8 Proof of Theorem 5
Without loss of generality, we assume that , are non-empty and that . Let consist of and consist of , with and . Let and be the winners from and respectively. By definition of RSOP,
It follows that
Now by definition . Theorem 5 follows.
References
- [1] M. Babaioff M, S. Dobzinski, S. Oren and A. Zohar. On Bitcoin and red balloons. In ACM Conference on Electronic Commerce, EC ’12, Valencia, Spain, 2012, pages 56-73.
- [2] J. Bonneau. Why buy them when you can rent- bribery attacks on Bitcoin-style consensus. In Financial Cryptograpphy and Data Security - FC 2016 International Workshops, BITCOIN, VOTING and WAHC, Christ Church, Barbados, 2016. Revised Selected Papers, pages 19-26.
- [3] M. Carlsten, H. A. Kalodner, S. M. Weinberg nd A. Narayanan. On the instability of Bitcoin without the block reward. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, 2016, pages 154-167.
- [4] A. V. Goldberg, J. D. Hartline and A. Wright. Competitive auctions and digital goods. In Proceedings of SODA 2001, pages 735-744
- [5] A. V. Goldberg, J. D. Hartline, A. R. Karlin, M. E. Saks and A. Wright. Competative auctions. Games and Econommic Behavior, 55(2): 242-269, 2006.
- [6] J. K. Kroll, I. C. Davey and E. W. Felten. The economics of Bitcoin mining, or Bitcoin in the resence of adversaries. In Proceedings of WEIS, Volume 2013.
- [7] G. Huberman, J. D. Leshno and C. C. Moallemi. Monopoly without a monopolist: An economic analysis of the Bitcoin payment system. https://ssrn.com/abstract=3025604, 2017
- [8] R. Lavi, O. Sattath and A. Zohar. Redesigning Bitcoin’s fee market. arXiv: 1709.08881v1 [cs.CR] 26 Sep 2017.
Comments
There are no comments yet.