Succinct 백서 전문

west bid. Due to the incentive compatibility of the second price auction, in equilibrium, the requester’s effective price will be f − (f − c2s) = c2s, the cost of the second best prover. The excess price due to supporting a decentralized prover set, therefore, can be calculated as E(c1, . . . , cm) = f − m − 1m H(f − c1s, . . . , f − cms) − c2s. This quantity is close to zero if the marginal costs of the provers are very similar, but has the potential to be large if there are a few ineﬀicient provers. 25 C Setting Fees We consider a model for setting fees with two provers (Alice and Bob) who bid in a proof contest with α = 1 for a request with cycle count s, with marginal proving costs c1 and c2, respectively. The utility of a prover bidding bi in a proof contest is then given by bi b1 + b2 (f − cis) − bi. As calculated in [ NGR24], the equilibrium bids b∗1(f ) and b∗2(f ) as a function of the fee are given by b∗1(f ) = (f − c1s)2(f − c2s)(2f − c1s − c2s)2 , b ∗2(f ) = (f − c2s)2(f − c1s)(2f − c1s − c2s)2 , and the effective price of the proof is f − b∗1(f ) − b∗2(f ) = f − (f − c1s)2(f − c2s)(2f − c1s − c2s)2 − (f − c2s)2(f − c1s)(2f − c1s − c2s)2 . (3) Suppose we want to find the smallest fee that the user can pay while maintaining both provers in the auction. We can do this by taking the derivative of ( 3) with respect to f and setting it equal to zero: 2(f 2 − f c1s − f c2s + c1c2s2) 4f 2 − 4f c1s − 4f c2s + c21s2 + 2c1c2s2 + c22s2 = 0. Setting f 2 − f c1s − f c2s + c1c2s2 = 0 , we get (f − c1s)(f − c2s) = 0 , which gives us the roots f = c1s, c2s. The fee that minimizes the price experienced by the user while preserving both provers in the auction is therefore the cost of the second best prover. Intuitively, this means that the user can minimize the effective price and receive proofs from a decentralized set of provers by incentivizing the second best prover to compete with the best prover. D Sybil Resistance Is it beneficial for a prover to split their bid bi into multiple bids? We demonstrate that the prover cannot profit by doing this in a proof contest for any α ≥ 1. Given a prover’s bid bi and fixing S =∑k̸=i bαk , the sum of other provers’ weighted bids, the expected utility of the prover bidding in a proof contest for fee f with cycle count s is ui(bi, b−i) = bαi∑m k=1 bαk (f − cis) − bi (4) = bαi bαi + S (f − cis) − bi. (5) 26 Suppose the prover decides to split the bid bi into M bids of size biM . The expected utility of the prover for this modified bid profile, which we denote by ˜bi, is ui(˜bi, b−i) = M   ( bi M )α M ( bi M )α + S (f − cis) − biM   (6) = bαi M α−1 bαi M α−1 + S (f − cis) − bi (7) = bαi bαi + SM α−1 (f − cis) − bi, (8) where the last equality is by multiplying the numerator and denominator with M α−1. Comparing ( 5) to ( 8), we see that for any α ≥ 1, ui(bi, b−i) − ui(˜bi, b−i) = bαibαi + S (f − cis) − bαibαi + SM α−1 (f − cis) ≥ 0. Therefore, provers are not incentivized to split their bids in proof contests. E Throughput We consider a model with n requests and m provers, where m ≤ n. Each prover can fulfill only one request. In mining, each prover randomly selects on of the requests to work on. Multiple provers can select the same request and contention can occur; only one prover fulfills the request, and the others remain idle. In contrast, proof contests mitigate this contention by assigning requests to a single prover; in this case, the maximum throughput is m proofs per time unit. We derive a formula for the net reduction in throughput due to contention for any given n and m. Each prover independently selects a request uniformly at random. The number of provers selecting a particular request rj follows a binomial distribution: P(Exactly k provers select rj) = (m k )( 1 n )k( 1 − 1n)m−k . Contention on the request occurs when k ≥ 2. The probability of contention is calcu- lated as P(Contention on rj) = 1 − P(0 provers select rj) − P(1 prover selects rj) = 1 − ( 1 − 1n)m − m( 1n)( 1 − 1n)m−1 . 27 The expected number of requests fulfilled without contention (those selected by exactly one prover) is E[Fulfilled without contention ] = n × P(1 prover selects rj) (9) = n × [ m ( 1 n )( 1 − 1n)m−1] (10) = m ( 1 − 1n)m−1 . (11) For requests with contention, only one prover fulfills the request. The expected number of such fulfilled requests in mining is E[Fulfilled with contention ] = n × P(Contention on rj) (12) = n [ 1 − ( 1 − 1n)m − m( 1n)( 1 − 1n)m−1] . (13) The expected number of requests fulfilled in mining is the sum of ( 13) and ( 11): E[Fulfilled (mining)] = m ( 1 − 1n)m−1 + n[1 −(1 − 1n)m − m( 1n)( 1 − 1n)m−1] = n [ 1 − ( 1 − 1n)m] . Recall that the maximum throughput, achieved by proof contests, is m. The reduction in throughput due to contention is therefore Throughput reduction = 1 − E[Fulfilled (mining)]m = 1 − nm[1 −(1 − 1n)m] . 28