Succinct 백서 전문

[ KB23] introduced the notion of using excess energy in proof-of-work to generate ZK proofs. Another way of assigning rewards is by the order in which provers submitted proofs: the first prover to submit a valid proof earns the largest share of the rewards, and subsequent provers earn less. An advantage of mining is that it enables a decentralized prover set that 8 Mining Stake-basedSelection Reverseauction Proof contests Eﬀiciency 7 7 3 3 User experience 7 7 3 3 Prover decen- tralization 3 3 7 3 Spam proofs 7 3 3 3 Throughput 7 3 3 3 T able 2: Evaluating proof contests alongside several candidate mechanisms. allows for home provers and smaller hardware teams to continue to participate in the network. However, mining leads to significantly higher costs and reduced throughput due to contention, as many provers may be working on the same request at the same time, generating unnecessary, redundant proofs. Further, if provers are incentivized based on the diﬀiculty of proofs, there is an incentive to submit proof requests of high diﬀiculty but no economic value to collect rewards. Strawman mechanism: stake-based selection. A second approach involves choosing provers to prove requests via stake-based selection. This can be implemented by asking provers to deposit collateral or stake, and then selecting them to prove a request with probability proportional to their stake. The upside of this mechanism is that it avoids contention by assigning each request to a single prover. However, if implemented in isolation, without a fee mechanism that finds market clearing prices, it does not directly induce competition on cost, since provers are selected purely based on the amount of stake they hold in the system. It separates the incentives of running a prover, which involves algorithmic and hardware improvements, from those of running a staking service, which involves capital management. Strawman mechanism: reverse auction. A third approach involves asking provers to participate in a competitive auction to reduce the price of a proof as much as possible. In this mechanism, provers bid in a reverse or procurement auction for the right to satisfy proof requests. Provers submit bids for each request. The bid is interpreted as the lowest price at which a prover is willing to satisfy the request. The winner is the lowest bidder, and can win at either the lowest or second-lowest price. This mechanism leads to an eﬀicient allocation of requests and minimizes contention due to proof assignment to a single prover. However, it potentially leads to intense prover concentration, as a single prover who is capable of generating proofs at lower cost than any other may come to win every auction. 9 Figure 4: Proof contests ask provers to deposit collateral in order to bid for requests. Winning provers are assigned proofs and have to complete them within specified deadlines, or risk having their collateral slashed. 3.1 Mechanism Description The main novelty of the proof contest mechanism is that it solves for the desired criteria and offers competitive prices to users while encouraging a decentralized prover set, improving upon the mechanisms introduced earlier. Proof contests use a mixture of collateral (resembling stake-based selection) and an all-pay auction to earn market clearing fees (resembling a simple reverse auction) to cause provers to compete on proof generation. In our design, provers deposit collateral to be able to participate in an all-pay auction or Tullock contest to be assigned the right to generate proofs for requests. Tullock contests model competition between a set of participants for fixed rewards [BTT80]. They have been studied in other contexts in blockchains, most notably in modeling Bitcoin mining [ LS20] and Ethereum block building [ BGR24], and as part of a proposed mechanism to encourage decentralization in block building [ NGR24]. In our design, participation in the contest allows provers to compete for proof generation. The provers’ bids in the auction are interpreted as the amount they will pay to receive the right to generate proofs. All provers pay their bids, and the winning prover is selected randomly among the provers with probability that is some function of their bid. The all-pay auction feature of proof contests induces competition on proving, as in 10 order to win the contest, provers have to submit competitive bids. The collateral acts to solve the “nothing-at-stake” problem for provers such that they are incentivized to not grief on assigned requests. We first introduce the primitives that proof contests use. A schematic description of the mechanism is shown in Figure 4. A censorship resistant bulletin board. First, we assume that there exists a censorship resistant public bulletin board. In the case of the network implementation, we make use of an application-specific blockchain; we provide further details about the network’s implementation in Section 4. The board provides functions READ(·), WRITE(·), and EXECUTE(·). The function READ(·) allows anyone who calls the func- tion to read all messages written to the bulletin board. The function WRITE(m) allows a user to write a message m to the bulletin board. Finally, the function EXECUTE(·) allows the bulletin board to compute the output of an algorithm and write it to the bulletin board; this can be implemented using a smart contract functionality. Entry and collateral. First, each of the provers pi deposits a collateral amount Ci prior to receiving the ability to bid for proof requests. The collateral is set to prevent provers from griefing requests upon assignment; bids are also drawn from collateral. The collateral acts to prevent the provers from having “nothing-at-stake” while participating in proving. The amount of collateral that each prover deposits reflects the number of auctions that they are eligible to participate in. The mechanism. A proof request rj is written to the bulletin board via WRITE(rj) by a user, upon which it is publicly viewable to the entire set of provers via READ(·). Provers bid amounts b1, . . . , bm in an auction for the right to prove requests; the bids are drawn from the provers’ collateral. The bids are interpreted as the amount a prover is willing to pay to receive fj from requester rj and complete the proof. The auction resolves by awarding the proof to prover pi with probability bαi∑m k=1 bαk , where α > 0 is a parameter to be set by the protocol. All provers pay their bids; these bids can be collected in a contract and then disbursed either to requesters as a rebate or as a refund to bidders over time. The interpretation of this mechanism is that the prover who is willing to pay the most for the right to complete the request wins with the highest probability, but other provers who bid less also win some of the time. The degree of distribution is specified by α. When α = 0, the request is assigned to the bidders with uniform probability. When α = 1 , the assignment probability is proportional to each prover’s bid. As α ↗ ∞ , the proof is increasingly assigned to the highest bidder. The winning prover completes the request and the amount fj is transferred from the requester to the winning prover if the proof is completed within the deadline. If no proof is submitted prior to the deadline, the request expires and the prover who was assigned to generate the proof has their collateral slashed. The payment and collateral logic can be handled via EXECUTE(·). 11 Extension to recurring proofs. It is possible to extend the proof contest mech- anism for a single request to requests that recur over time, as is the case with rollups and applications with repeated transactions. This is a version of the above mechanism that functions without money. In this case, the user’s fee fj is interpreted as the amount they would like to pay per proof for recurring requests of cycle count sj. Now, instead of bidding money in an all-pay auction, each prover reserves a certain number of slots bi ahead of time to fill the proof requests. The total number of slots that provers reserved determines the price. Now, in contrast to the earlier mechanism with money, the per proof price is reduced to fj −∑mi=1 bi. Prover pi is assigned the right to prove a fraction bi∑m i=1 bi of the proofs, and provers rotate in this ratio in a round-robin fashion. The advantage of this mechanism is that it achieves a decentralized prover set without asking provers to bid in an auction per request. We now show how the behavior of provers in this recurring model is related to the earlier setup of an all-pay auction for each proof. Recalling that each prover has a marginal cost ci per proof. The total profit of the prover over a single cycle in which everyone rotates is the product of the number of slots the prover is assigned times the profit per slot, or bi ( fj − m∑ i=1 bi − cisj ) . Dividing through by ∑mi=1 bi, the per proof profit of the prover is bi∑m i=1 bi (fj − cisj) − bi, which can be interpreted as the prover bidding bi in the earlier, nonrecurring mecha- nism, with per proof profit fj − cisj for the proof and with α = 1. Setting collateral. The collateral Ci controls the number of auctions that a prover is allowed to participate in. The total sum of all the fees that a prover is currently bidding for should be less than the collateral they have put up at any time. The network automatically locks the number of auctions that a prover can participate in given the collateral they have deposited. Setting fees. We propose a candidate mechanism for setting the fees fj that clears proof requests while maintaining prover diversity in the auction. The fee mechanism we consider maintains a posted price, which is a uniform per-cycle fee (that is, fj = f sj for every request, for some fixed f ). Higher fees mean that the prospect of having multiple bidders in the auction increases. Fees can be set to achieve 100% clearing rate of outstanding proof requests, via a control system that increases fees if requests were left over in the last timestep. To ensure that the fee is set high enough to ensure prover diversity, the proof contest mechanism can be complemented by simple Dutch auctions for a fraction of proof requests. These auctions would start at discounted prices and provide a signal as to the fee that a simple reverse auction would clear at, which could help the proof contest mechanism set a comfortably higher fee in order to 12 Figure 5: The codesign of the network with SP1 prevents proof copying and reused work. encourage prover diversity. Parameterizing this fee adjustment mechanism to maintain a diverse set of provers that operate without manipulation is a topic for further study. In Appendix C, we derive the minimum transaction fees required to support multiple provers as a function of their costs. Setting bounds on bids. In order to incentivize competitive bidding, the protocol can also impose lower bounds on bids that can be increased over time. This means that the quality of provers, and therefore the costs experienced by requesters, improve. Proving pools and hardware teams jointly have to improve their hardware and proving software to be able to participate in the auction; these entry costs ensure that requesters receive cost-effective proving as performance improves. 3.2 Mechanism Implementation A practical implementation of the mechanism should prevent several failure modes such as copied proofs and reused work (Figure 5). We describe the modifications that are made to fulfilled proofs that are submitted to the network; this is realized in practice by codesigning the network with SP1. Suppose a proof request rj is fulfilled by prover pi. In the network, proofs are a function of the onchain address ai of prover pi and a unique nonce n, which is generated at the time the proof was requested. We succinctly represent this dependence by proof(rj, ai, n). Proofs are designed to satisfy the following properties. Embedded prover addresses: preventing copying. First, to prevent a proof generated by a given prover from being copied by another prover, we make use of prover address information. The main property we seek is that for any ak ̸= ai, it should be the case that the protocol can distinguish proof(rj, ai, n) from proof(rj, ak, n′), for any n, n′. Therefore, a prover cannot simply reuse a proof posted by another prover 13 to collect rewards or fees. This can be implemented by embedding the prover address during proof construction in SP1. Unique nonce: preventing reuse. Second, to prevent a prover from reusing the work they did for a given proof, we embed the proof with the unique nonce that is generated at request time. This nonce can be embedded in the challenger of the underlying proof system and can be used by an onchain verifier to check that the proof was constructed using the nonce. The main property we seek now is that for every ai and for any n, n′, the protocol can distinguish proof(rj, ai, n) from proof(rj, ai, n′) unless n = n′. Because the nonce is unique and generated at request time, this means that a prover cannot reuse their own work. 3.3 Analysis and Incentives We now describe several important features of the incentives that proof contests set up and how they solves the problems faced by alternate mechanisms. We consider how the all-pay feature trades off cost competition and decentralization, the Sybil resistance of the mechanism, and how proof contests increase throughput by breaking the contention found in mining. Prover competition. The proof contest mechanism induces competition on prov- ing by asking provers to bid for the right to fulfill requests. By asking provers to bid for requests, the mechanism aligns the provers’ incentives with a key require- ment of the user: finding provers that can competitively generate proofs. We con- sider a setting where m provers, each of whom have per cycle marginal proving costs c1 < c 2 < · · · < c m, participate in the proof contest mechanism for a proof request with fee f , cycle count s, and α = 1 . In this case, the utility of a prover who bids bi, while other provers bid b−i is given by ui(bi, b−i) = bi∑m j=1 bj (f − cis) − bi. Assuming that the fee is bigger than the proving cost for each prover that participates (f − cis > 0), we can calculate the equilibrium bids b∗i submitted by the provers via the first order conditions ∂ui∂bi (b∗i , b∗−i) = 0 , which are ∂ui ∂bi (b∗i , b∗−i) = ( f − cis) ∑ k̸=i b∗k (∑m k=1 b∗k)2 − 1 = 0 . Rearranging the conditions, ∑ k̸=i b∗k (∑m k=1 b∗k)2 = 1(f − cis) , and summing over all the provers, m∑ i=1 ∑ k̸=i b∗k (∑m k=1 b∗k)2 = m∑ i=1 1 (f − cis) . 14 Now, noting that ∑mi=1∑k̸=i b∗k = (m − 1)∑mk=1 b∗k, we see that m∑ k=1 b∗k = m − 1∑m i=1 1 f −cis (1) = m − 1m H(f − c1s, . . . , f − cms), (2) where H is the harmonic mean. In the setting where the bids provide a rebate to users over time, we can interpret this as follows: when the costs of the provers are very close to the costs of the best prover, the effective price quoted to the user is nearly the cost of the best prover. When the costs are very disparate, however, the effective price may be higher. We provide a model of how rebates, combined with a preference for decentralization, compare to a simple reverse auction in Appendix B. Prover decentralization. The allocation mechanism induced by proof contests (and by Tullock contests in general) intrinsically incentivizes a diverse set of provers to participate, and is the basis behind previous attempts in blockchains to achieve a decentralized set of service providers, such as miners in Bitcoin, validators in Ethereum, and block builders in the “execution tickets” mechanism described in [ NGR24]. A simple reverse auction would always allocate proofs to the prover who bids the lowest cost. While this should result in an eﬀicient assignment of proofs, it may not result in a robust prover marketplace, since if one prover is consistently more eﬀicient at generating proofs, it may never make sense for another prover to bid. By contrast, proportional allocation, the rule for proof contests with α = 1 , allo- cates proofs to provers proportional to their bids. This has the effect that a prover who has already bid a large amount faces diminishing marginal returns to increasing their bid (since it would increase the total amount of bids, which would decrease the expected likelihood of winning for each dollar they’ve already bid). The mechanism makes it diﬀicult for a prover to dominate and earn 100% of fees, because it is often profitable on the margin for small bidders to bid more than zero (and thus have some probability of winning a contest). While Tullock contests encourage decentralization, they present a tradeoff—since they sometimes allocate proofs to less eﬀicient provers, they will generally result in higher proving costs for users, relative to a simple reverse auction. The mechanism should be parameterized to balance the long-term robustness benefits of prover diver- sity against the immediate benefits of prover eﬀiciency. Sybil resistance. The proof contest mechanism disincentivizes provers from split- ting their identity while bidding in the auction through the all-pay feature and by requiring provers to put up collateral to be able to bid. We consider a prover who attempts to split their bid bi into M bids of size biM in a proof contest with fee f , cycle count s, and arbitrary α. We can compute the utility to this prover from the modified 15 Figure 6: Proof contests break the contention found in mining by assigning requests to a single prover and correspondingly increase throughput. bid profile ˜bi as ui(˜bi, b−i) = M   ( bi M )α M ( bi M )α + S (f − cis) − biM   , where S = ∑k̸=i bαk is fixed for all other provers. In Appendix D, we demonstrate that it is not in a prover’s interest to split their bids into multiple identities (that is, ui(bi, b−i) ≥ ui(˜bi, b−i)) in a proof contest for any α ≥ 1. Throughput. The proof contest mechanism breaks the contention found in mining by assigning proof requests to a single prover via bidding. This prevents reductions in throughput. We consider a model in which there are n requests that arrive every time unit and m provers are available to prove them. Each prover has enough capacity to fulfill exactly one request. In mechanisms like mining that allow provers to freely choose which requests they will work on, multiple provers can end up choosing to work on one of the requests, leaving some requests unfulfilled. On the other hand, in proof contests, the bidding phase prevents reductions in throughput and matches requests to available proving capacity. We suppose that in mining, each of the provers picks a request to work on uniformly at random. In Appendix E, we show that the reduction in throughput in mining, compared to proof contests, is 1 − nm[1 −( n − 1n )m] We depict a simple example of how this can happen with two requests ( n = 2) and two provers ( m = 2 ) in Figure 6. The reduction in throughput in this case is 25%. This 16 is because the maximum throughput, achieved by proof contests, is 2 proofs per time unit, whereas in mining, the expected number of completed requests is 1 2 · 1 + 12 · 2 = 1 .5, which gives us the reduction in throughput, 100 ( 1 − 1.52 ) = 25%. Spam proofs. Since in this model, all rewards received by provers are paid by requesters, there is no incentive for provers to submit “spam proofs” for which there is no real economic demand. Further, provers cannot earn bids from other provers by submitting spam requests either, since bids are collected in a contract and uniformly distributed as rebates. In future work, we will show how network rewards can be added to this mechanism to subsidize the cost of proofs without introducing an incentive to submit requests for proofs with zero economic value. 3.4 Proving Pools Individual provers who may not have suﬀicient sophistication or collatera