• Have any questions?
  • info.zbook.org@gmail.com

Coda: Decentralized Cryptocurrency At Scale

3m ago
639.04 KB
47 Pages
Last View : 3d ago
Last Download : n/a
Upload by : Axel Lin

Coda: Decentralized Cryptocurrency at ScaleJoseph Bonneau1 , Izaak Meckler2 , Vanishree Rao2 , and EvanShapiro21 NewYork UniversityLabs2 O(1)AbstractWe introduce the notion of a succinct blockchain, a replicated statemachine in which each state transition (block) can be efficiently verified in constant time regardless of the number of prior transitions in thesystem. Traditional blockchains require verification time linear in thenumber of transitions. We show how to construct a succinct blockchainusing recursively composed succinct non-interactive arguments of knowledge (SNARKs). Finally, we instantiate this construction to implementCoda, a payment system (cryptocurrency) using a succinct blockchain.Coda offers payment functionality similar to Bitcoin, with a dramaticallyfaster verification time of 200ms making it practical for lightweight clientsand mobile devices to perform full verification of the system鈥檚 history.1IntroductionBitcoin and other distributed payment systems (also called cryptocurrencies orsimply blockchains) aim to provide a decentralized system for making and verifying payments. However, for traditional cryptocurrencies, including Bitcoin,decentralization comes at the cost of scalability as each node needs to processthe entire system history upon joining the network. Asymptotically, verifyinga blockchain containing 饾憽 transactions requires 饾浐(饾憽) time (usually more thanlinear in 饾憽 as bookkeeping is required to resolve transaction references duringverification). At the time of this writing, Bitcoin鈥檚 blockchain is over 250 GBand contains over 500 M transactions (see Figure 1). Downloading and verifyingthis history takes days on a typical laptop.These resource requirements deter most users from running a full node thatstores and verifies the blockchain. As seen in Figure 2, the number of full nodesin Bitcoin is not growing despite its increasing popularity over time. Insteadmost users run a light node, verifying only block headers but not transactions,or an ultralight node verifying nothing and relying on trusted advice from atrusted server. This undermines decentralization as most clients rely on trustrather than independent verification. It also undermines performance: block size1

(and therefore transaction throughput) is artificially capped in part to mitigatethe burden of verification.Figure 1: Growth of the Bitcoin blockchain over time, in GB. Source: www.blockchain.com.Figure 2: Estimated number of full nodes participating in the Bitcoin andEthereum networks over time. Source: www.bitnodes.earn.com and www.Ethernodes.org.2

In this work, our goal is to design a decentralized payment system thatoffers efficient verification of system history from genesis without relying onany external advice. Specifically, we aim to provide verification time constant(饾憘 (1)) in the number of transactions; we call such a blockchain, a succinctblockchain.We achieve this goal by including succinct proofs of state validity in eachblock. Generically, it is possible to compute a succinct non-interactive argumentof knowledge (a SNARK) of any NP statement, including for example thatthe system stated committed to by the current block in a blockchain can bereached from a the genesis state by a series of valid transactions in the system.This (large) list of transactions is a witness that the current block is valid.However, computing a new proof of validity of the entire system history foreach block would be prohibitively expensive. Instead, we employ techniquesfrom incrementally computable SNARKs to ensure that the cost of computinga proof for each block is proportional only to the number of transactions addedsince the previous block.We instantiate the notion of a succinct blockchain and introduce the Codaprotocol. Coda is a payment-oriented blockchain offering similar functionalityto Bitcoin, although with different transaction semantics. In particular, Codauses an account-based model (as in Ethereum [25]) (instead of the UTXO modelas in Bitcoin[19] and others [20]), wherein the current state of the blockchain isa list of all account balances rather than a list of unspent coins (UTXOs).Each block contains a commitment to this state (in a Merkle tree) and notthe entire state. Therefore a full node need not store the entire state, but canverify account balances efficiently given only the state commitment in the latestblock header. However, a prover in our system (roughly equivalent to a minerin Bitcoin) does needs to store the full state since it is part of the witness whenproving the validity of new blocks.For the consensus protocol of Coda, we present the first provably-secureproof-of-stake (PoS) consensus protocol for succinct blockchains called OuroborosSamasika. Note that an off-the-shelf consensus mechanism is not necessarilycompatible with a succinct blockchain framework, since the way consensus isachieved when there are multiple contending chains could relying on arbitrarytransaction history, forcing nodes to store the entire transaction history. Infact, this is a natural approach for consensus mechanisms, since the informationneeded to tell apart an honest chain from a dishonest one is likely to involvedetails at the point of the fork; since it is possible for a party to learn about afork long after it occurred, it may need to store the entire history to assist inthe chain selection process. This is indeed the case in the known PoS consensusmechanisms [17, 13, 4]. Furthermore, other PoS consensus mechanisms rely ona trusted external advice for bootstrapping [12].Concretely, in our current implementation, a state proof size is just and ittakes around 200ms to verify it. Thus, any device that can support this level ofcomputation, such as the current smartphones, can verify the current state ofthe system with no trusted advice.Beyond incrementally computable SNARKs, we employ multiple optimiza3

tions, the most significant of which is parallel scan state. At a high level, thisimproves transaction throughput beyond the limits of sequentially computedproofs. Roughly, the idea is to enqueue all the blocks that still need to be absorbed into a proof and distribute their proving across parallel provers. We alsointroduce a special queue of recent transactions to reduce transaction confirmation latency below the limits imposed by minimum proving times. Furthermore,we introduce a special incentive structure to maximizing prover participation inthe network.1.1Our ContributionsIn summary, our contributions are: We formalize the notion of a succinct blockchain. This notion may be ofindependent interest for alternative constructions of succinct blockchains. We present an approach to constructing a succinct blockchain for genericfunctionalities modeled as replicated state machines using incrementallycomputable SNARKs. We present a concrete implementation of our approach for the specificfunctionality of a payments system called Coda. We present Ouroboros Samasika, a provably-secure PoS consensus protocol that is adaptively secure and offers bootstrapping from genesis. We introduce the notion of a parallel scan state to improve transactionconfirmation time beyond the limits otherwise imposed by the proof construction. We present a performance evaluation report of executing the protocolinvolving a public community.2Succinct BlockchainsIn this section, we introduce the notion of succinct blockchains.Underlying concepts of a blockchain. We begin by recalling definitionsof certain underlying concepts of a blockchain [13]. This will assist in definingsuccinct blockchains.Definition 2.1 (State, Block Proof, Block Producer, Block, Blockchain, GenesisBlock). A state is a string st {0, 1}饾渾 . A block proof is a value (or a set ofvalues) 饾湅饾憱饾惖 containing information to verify whether the block is valid. Eachblock is associated with a unique party called its block producer. A block 饾惖饾憱 (sn饾憱 , st饾憱 , 饾湅饾憱饾惖 , 饾憫饾憱 , b-pk饾憱 , 饾憦-sig饾憱 ) generated with a serial number sn饾憱 N contains thecurrent state st饾憱 , a block proof 饾湅饾憱饾惖 , data 饾憫饾憱 {0, 1} , the block producer鈥檚 publickey b-pk饾憱 and a signature 饾憦-sig饾憱 on (sn饾憱 , st饾憱 , 饾湅饾憱饾惖 , 饾憫饾憱 ) with respect to b-pk饾憱 .4

A blockchain is a sequence of blocks C (饾惖1 , . . . , 饾惖饾憶 ) associated with astrictly increasing sequence of serial numbers. The first block 饾惖1 is called thegenesis block. The length len(C) 饾憶 of a blockchain is the number of blocks init.Succinct blockchains. We are now ready to introduce the definition of asuccinct blockchain protocol. The definition will also introduce the notion of ablockchain summary, which, at a high level, is some summary of a blockchainsuch that the summary is valid if and only if the blockchain is valid. The conceptof a blockchain underlying a blockchain summary will not be evident from thedefinition of a succinct blockchain protocol itself. However, it will be capturedvia the notion of chain extractability in Definition 2.4.Definition 2.2 (Succinct Blockchain Protocol). A succinct blockchain protocol 饾洷 is characterized by a tuple of five PPT algorithms (VerifyConsensus,UpdateConsensus, VerifyBlock, UpdateChain, VerifyChain) syntactically definedas follows. VerifyConsensus(consensusState, consensusProof) / : This algorithm takes as input a consensusState and a consensusProof, verifies according to some notion of correctness and outputs or , respectively. UpdateConsensus(consensusState, consensusProof) nextConsensusState :This algorithm also takes as input a consensusState and a consensusProofand outputs an updated consensus state. VerifyChainSummary(S饾憱 ) / : This algorithms verifies whether agiven blockchain summary S饾憱 is valid or not. VerifyBlock(S饾憱 1 , 饾惖饾憱 ) / : This algorithms verifies whether a givenblock 饾惖饾憱 is valid with respect to a given blockchain summary S饾憱 1 . As apart of the verification, it checks that VerifyConsensus(consensusState饾憱 1 ,consensusProof 饾憱 , where, S饾憱 1 contains consensusState饾憱 1 and 饾湅饾憱饾惖contains consensusProof 饾憱 , where, 饾惖饾憱 (路, 路, 饾湅饾憱饾惖 , 路, 路, 路). UpdateChainSummary(S饾憱 1 , 饾惖饾憱 ) S饾憱 : This algorithm takes a blockchainsummary S饾憱 1 and a new block 饾惖饾憱 and outputs an updated blockchainsummary S饾憱 .The protocol satisfies the following succinctness property.Succinctness. Each of the algorithms VerifyBlock, VerifyChainSummary, andVerifyConsensus runs in time poly(饾渾). Furthermore, the size of the blockchainsummary S饾憱 at any time 饾憽饾憱 is of size poly(饾渾) (i.e., constant in the numberof chain summary updates).Remark 2.1 (Consensus mechanism). The algorithm pair (VerifyConsensus,UpdateConsensus) is said to constitute a consensus mechanism. The following5

are some examples of how the notion can be instantiated. For proof-of-workprotocols (e.g. Bitcoin), the consensus state would contain several previousdifficulty targets and block times (from which to compute the current difficultytarget) and a consensus proof would contain the proof-of-work itself along witha new time to update the state with. For an Ouroboros Praos-style [13] proof-ofstake mechanism, the consensus state would contain the current random seed,the (Merkle root of) the current epoch鈥檚 stakes, and some information about theprevious blocks and block times. A consensus proof would contain a public-keyand a verifiable random function (VRF) evaluation proof meeting the thresholdtarget corresponding to that public-key and the stakes indicated in the consensusstate.Types of Roles. Per the above definition, there are three kinds of roles in asuccinct blockchain. (There can be additional roles depending on the instantiation.)1. Full node: In this role, a party keeps track of the blockchain summaryand verifies it.2. Block producer: In this role, a party produces a block.3. Blockchain summary producer: In this role, a party generates blockchainsummaries.Note that the significant advantage of a succinct blockchain is that any partywith reasonable resources can be a full node, due to the succinctness property.That is, a succinct blockchain does not require the role of light clients to copewith growing blockchain sizes.Relationship between blockchain summary and underlying blockchain.Having defined a succinct blockchain in terms of blockchain summaries, we willnow show how the summaries are related to the underlying blockchains. Roughlyspeaking, we would like that the blockchain summaries inherit validity of underlying blockchains. That is, a summary is valid if and only if the underlyingblockchain is valid.Furthermore, given a blockchain summary, we arrive at its underlyingblockchain through the notion of extractability. Specifically, we define extraction recursively; that is, given a blockchain summary with serial number 饾憱, anextractor (using some additional information) extracts a blockchain summarywith serial number 饾憱 1 and a block 饾惖饾憱 , wherein all the components satisfy thenecessary verification tests. The additional information the extractor uses is theexecution transcript which we call the execution trace formally defined below.Definition 2.3 (Execution Trace, Blockchain Summary in an Execution Trace).For an (adaptive) adversary A and an environment Z, an execution trace Eof a blockchain protocol 饾洷 by a set of parties U with security parameter 饾渾is a transcript including the inputs provided by Z, the random coins of the6

parties and the random coins of the adversary. This data determines the entiredynamics of the protocol: messages sent and delivered, the internal states of theparties at each step and the set of corrupt parties at each step. We denote thetrace by E 饾洷 (1饾渾 , U) or simply E 饾洷 (U).For every blockchain protocol 饾洷 , there exists an algorithm CurrChain, suchthat for every set of PPT parties U, E 饾洷 (U), time 饾憽, honest party 饾憙 U, wehave that CurrChain outputs a valid blockchain summary; i.e., CurrChain(E, 饾憙, 饾憽) S and VerifyChainSummary(S) . S is said to be the blockchain summary in 饾憙鈥檚 view of E at time 饾憽. A blockchain summary in an execution trace Eis a blockchain summary C in any honest party鈥檚 view at any time 饾憽; we denotethis by S E.We will now define the notion of chain extractability. This definition utilizesa notion of 鈥榮erial number of a blockchain summary鈥. Intuitively, it is justa natural number 饾憲 that represents the number of blocks in the underlyingblockchain. It is indicated in the subscript as S 饾憲 .Definition 2.4 (Chain Extractability). A succinct blockchain protocol 饾洷 (VerifyConsensus, UpdateConsensus, VerifyBlock, UpdateChain, VerifyChain) issaid to satisfy chain extractability if the following probability Adv 饾洷 , U (1饾渾 ) isnegligibly close to 1 for every U {A饾憱 }饾憱 , a set of PPT algorithms. For everyA饾憱 , there exists a PPT algorithm Ext A饾憱 , called an extractor, and Adv 饾洷 , U isdefined as follows. VerifyChainSummary(S 饾憲 1 ) VerifyBlock(S 饾憲 1 , 饾惖 饾憲 ) E 饾洷 (U) 饾渾 S 饾憲 E, A饾憱 U :Adv 饾洷 ,U (1 ) : Pr (S,饾惖) Ext饾惖isaGenesisblock(E,S,饾憻)饾憲 1饾憲A饾憱1饾憲 Sisanemptystring0 where, 饾憻 is the random coins of A饾憱 .Definition 2.5 (Blockchain underlying a Blockchain Summary). Let 饾洷 be ablockchain protocol which satisfies chain extractability. Let E be an executionof the protocol by a set of parties U. Let 饾憙 U be an honest party that hasbeen active since the beginning of the protocol. Let S鈩 be the blockchain inE 0. For every 1 饾憱 鈩, let 饾惖饾憱 be a block guaranteed by the property of chainextractability. The sequence (饾惖1 , . . . , 饾惖鈩 ) is called the blockchain underlying S鈩 .2.1Security Properties of a Succinct BlockchainWe will now enlist the security properties of a succinct blockchain. Rather thanthe blockchain summaries, the properties pertain to the underlying blockchainguaranteed by the chain extractability property.Consider a blockchain protocol 饾洷 and an execution E. Let C be the underlying blockchain of the blockchain summary S in E. We recall the following7

properties that were first rigorously formulated in [15]. We will assume thattime is divided into predefined slots.Common Prefix (CP); with parameters 饾憳 N. The blockchains C1 , C2 corresponding to two alert parties at the onset of the slots sl1 sl2 are suchthat C1 d饾憳 4 C2 , where C1 d饾憳 denotes the blockchain obtained by removingthe last 饾憳 blocks from C1 and 4 denotes the prefix relation.Chain Growth (CG); with parameters 饾湉 (0, 1] and 饾憼 N. Consider C, ablockchain possessed by an alert party at the onset of a slot sl. Let sl1and sl2 be two previous slots for which sl1 饾憼 sl2 sl, so sl1 is at least 饾憼slots prior to sl2 . Then C[sl1 , sl2 ] 饾湉 路 饾憼. We call 饾湉 the speed coefficient.Chain Quality (CQ); with parameters 饾渿 (0, 1] and 饾憳 N. Consider anyportion of length at least 饾憳 of the blockchain corresponding by an alertparty at the onset of a slot; the ratio of blocks originating from alertparties in this portion is at least 饾渿, called the chain quality coefficient.3PreliminariesIn this section we provide several requisite definitions of SNARK systems whichwe use to construct a succinct blockchain.Notations. We use the abbreviation PPT to stand for probabilistic polynomial time. We use 饾渾 to denote the security parameter.Definition 3.1 (SNARKs). Let 饾憛 {(饾湙, 饾懁)} be a polynomial relation of statements 饾湙 and witnesses 饾懁. A Succinct Non-interactive ARgument of Knowledgefor 饾憛 is a quadruple of algorithms (sSetup, sProve, sVerify, sSim), which is complete, succinct and knowledge sound (defined below) and works as follows: (srs, 饾湉) sSetup(饾憛): The setup algorithm generates the structured random string srs and a trapdoor 饾湉. 饾湅 sProve(srs, 饾湙, 饾懁): the prover algorithm generates a proof 饾湅. / sVerify(srs, 饾湙, 饾湅): the verifier algorithm verifies a given proof. 饾湅 sSim(srs, 饾湙, 饾湉): the PPT simulator simulates a proof without thewitness but by using the trapdoor.Completeness. It simply states that given a true statement, a prover with awitness can convince the verifier. That is, for every (srs, 饾湉) sSetup(饾憛) and饾湅 sProve(srs, 饾湙, 饾懁), we have that sVerify(srs, 饾湙, 饾湅).Succinctness.It states that the proof size 饾湅 is poly(饾渾).8

Knowledge soundness. It states that whenever somebody produces a validargument it is possible to extract a valid witness from their internal data. Formally, for every PPT adversary A, there exists a PPT extractor 饾湌 A , such thatthe following probability is negligible in 饾渾: (srs, 饾湉) sSetup(饾憛) (饾湙, 饾懁) 饾憛 Pr (饾湙, 饾湅) A (srs): 饾懁 饾湌 A (trans A ) sVerify(srs,饾湙,饾湅) Simulation-extractable SNARKs. A simulation-extractable SNARK is aSNARK that achieves a higher level of security, namely, simulation extractability. The notion of simulation extractability is similar to the notion of knowledgesoundness except that an adversary gets to see also simulated proofs.Signatures of Knowledge (SoK). An SoK is a generalization of digital signatures by replacing a public key with an instance in an NP language. Fora formal definition, see [16]. The notion of SoKs is related to the notionof simulation-extractable non-interactive zero-knowledge arguments, such as,SNARKs. In fact, [16] showed that the former can be constructed based on thelatter. In this work, we rely on SoKs constructed using SNARKs, thereby beingable to exploit succinctness of such SoKs.4Coda: A Succinct Blockchain based on Recursive SNARKsIn this section, we introduce a succinct blockchain construction called Codabased on SNARKs. At a high-level, validity of a blockchain鈥檚 sequence of transitions is proved using a SNARK. Then, the blockchain proof consists of thisSNARK and omits the detailed list of blocks, since verifying the SNARK verifies the embedded blocks. Succinctness of SNARK ensures succinctness of theblockchain.Note that a blockchain is dynamic and new blocks keep getting added toit. However, we would like to ensure succinctness at any given point in time.Therefore, as the blockchain 鈥済rows鈥, we compute a new SNARK proof that notonly validates the new blocks, but also the existing SNARK proof itself. Thenotion of a SNARK proof that attests to the verifiability of another SNARKproof is the notion of 鈥渋ncrementally-computable SNARK鈥 [24, 8, 6].We will first specify the SNARK construction and then demonstrate how itcan be employed to achieve a succinct blockchain.4.1Incrementally-computable SNARKsWe now recall the notion of incrementally-computable SNARKs described variously in [24], [8] and [6]. Instead of phrasing the construction in the language9

of incrementally verifiable computation as in [24] or in the language of PCD(proof-carrying data) systems as in [8] and [6], we opt to describe it in termsof state-transition systems as it maps more clearly onto the application of producing a succinct blockchain.We will first recall the definition of a state transition system.Definition 4.1 (State transition system). A state transition system is atuple (饾洿, T, Update), where 饾洿 is the set of states, T is the set of transitions andUpdate is a (non-deterministic) poly-time computable function Update : T 饾洿 饾洿. Update may also 鈥渢hrow an exception鈥 (i.e., fail to produce a new state forcertain inputs). Moreover, elements in 饾洿 and T need to be representable bybit-strings of length poly(饾渾).We now define SNARKs for state transition systems. At a high level, wewould like poly(饾渾)-size proofs (which are verifiable in poly(饾渾) time) which attestto statements of the form 鈥渢here exist a state 蟽1 and a sequence of transitions饾憽 1 , . . . , 饾憽 饾憳 T such that Update(饾憽 饾憳 , Update(饾憽 饾憳 1 , . . . , Update(饾憽 1 , 蟽1 ))) 蟽2 鈥.In other words, we would like succinct certificates of the existence of statetransition sequences joining two states. The application to blockchains is thefollowing: we will take our state to be the database of accounts (along withsome metadata needed for correctly validating new blocks) and transitions tobe blocks.Definition 4.2 (Incrementally-computable SNARKs). An incrementally-computable SNARK for a state transition system (饾洿, T, Update) is a tuple of algorithms (sSetup, sProve, sVerify, sSim) such that the following holds. Suppressingparameter generation and passing the parameters to sProve and sVerify,1. (sSetup, sProve, sVerify, sSim) is a SNARK.(sSetup, sProve, sVerify, sSim) is a SNARK for the relation 饾憛 {(蟽饾憱 饾憳 ),蟽饾憱 , 饾憽饾憱 1 , . . . , 饾憽 饾憱 饾憳 )}, where, 蟽饾憱 饾憳 Update(饾憽饾憱 饾憳 , Update(饾憽饾憱 饾憳 1 , . . . , Update(饾憽 饾憱 1 , 蟽饾憱 ))) for any 饾憳.2. (sSetup, sProve, sVerify, sSim) is succinct.Every honestly generated proof has size poly(饾渾) and for any 饾湅, 蟽, we havethat sVerify(蟽, 饾湅) runs in time poly(饾渾).4.1.1Incrementally-computable SNARKs using Recursive Proof CompositionNa谋虉ve recursive composition is theoretically viable, since, for a SNARK, proofverification is asymptotically cheaper than merely verifying the correspondingNP statement. However, it is extremely expensive. Although SNARK verifiersexecution is quite fast 鈥 in the order of just a few milliseconds on a desktopcomputer, generating a SNARK proof to attest to an accepting verifier circuitis expensive. This is because, executing the verifiers still takes millions of steps10

in computation, proving which is impractical even for a single layer of recursion,as explained in [6].To address this, we employ the 鈥渃ycle of elliptic curves鈥 technique (as described in [6]) in which two SNARK constructions 鈥 classically called Tick andTock 鈥 are designed such that each can efficiently verify proofs from the other.Then, to exploit the parallelism mentioned in Remark ?, we define the Tickand Tock SNARKs to result in a 鈥渂inary tree of proofs鈥 as follows. A TickSNARK is used to certify state transitions at the 鈥渂ase鈥 of the tree. Then, toenable efficient merging of those proofs, each of them is 鈥渨rapped鈥 using a TockSNARK. Then, two Tock proofs are merged using a Tick SNARK.Therefore, note that, we will need two Tick SNARKs - one for proving statetransitions and another for merging two Tock proofs. And we will need oneTock SNARK to wrap a Tick proof into a Tock proof. More formally:1. The base SNARK. A Tick-based SNARK for certifying single state transitions, which we will call the 鈥渂ase鈥 SNARK.Statement: (蟽1 , 蟽2 ) 饾洿 2 .Witness: 饾憽 T.Computation: There exists 饾憽 T such that Update(饾憽, 蟽1 ) 蟽2 .We will denote the proof by 蟽1 Tick 蟽2 .2. The merge SNARK. A Tick-based SNARK for merging two Tock proofs,which we will call the 鈥渕erge鈥 SNARK.Statement: (蟽1 , 蟽3 ) 饾洿 2 .Witness: 蟽2 饾洿 and Tock-proofs 饾湅1 , 饾湅2 .Computation: There exist 蟽2 饾洿 and Tock-proofs 饾湅1 , 饾湅2 such thatVerifyTock ((蟽1 , 蟽2 ), 饾湅1 ) and VerifyTock ((蟽2 , 蟽3 ), 饾湅2 )We will denote the proof by 蟽1 Tick 蟽3 . 蟽1 to 蟽2 and a SNARK proofcertifying the existence of transitions from 蟽2 to 蟽3 .3. The wrap SNARK. A Tock-based SNARK for wrapping a Tick proof,which we will call the 鈥渨rap鈥 SNARK.Statement: (蟽1 , 蟽2 ) 饾洿 2 .Witness: A Tick proof 饾湅.Computation: There exists a Tick proof 饾湅 such that VerifyTick ((蟽1 , 蟽2 ), 饾湅).We will denote the proof by 蟽1 Tock 蟽2 .This SNARK merely wraps aTick SNARK into a Tock SNARK so that another Tick SNARK can verifyit efficiently.4.1.2An example transition systemTo illustrate this, we鈥檒l show how it can be applied to prove statements in a verysimple transition system where each state is simply the hash H of the previous11

state. Assume the current state is 饾懃 0 H(H(. . . H(饾懃) . . . )) for some 饾憳, starting {z}饾憳from an initial state 饾懃. We apply the above technique with our state 饾洿 being theunion of domain and range of H, 饾憞 being a singleton set containing an emptystring, and the update function being Update(饾憽, 饾懃) H(饾懃).This gives us a SNARK for proving that there exists a sequence of transitions (饾憽 1 , . . . , 饾憽 饾憳 ) such that Update(饾憽 饾憳 , Update(饾憽 饾憳 1 , . . . , Update(饾憽 1 , 饾懃), . . . )) 饾懃 0,which since Update(饾憽, 饾懄) H(饾懄) gives us exactly what we want. For strings饾懃 0 , 饾懃4 with H(H(H(H(饾懃0 )))) 饾懃4 , the tree of SNARK proofs appears as follows:饾懃0 Tick 饾懃44.2饾懃0 Tock 饾懃 2饾懃2 Tock 饾懃4饾懃 0 Tick 饾懃2饾懃2 Tick 饾懃4饾懃 0 Tock 饾懃1饾懃1 Tock 饾懃2饾懃 2 Tock 饾懃 3饾懃3 Tock 饾懃4饾懃0 Tick 饾懃 1饾懃1 Tick 饾懃2饾懃 2 Tick 饾懃 3饾懃3 Tick 饾懃4CODA: A Succinct Blockchain Using Incrementallycomputable SNARKsIn this section, we present the Coda protocol, a succinct blockchain basedon incrementally-computable SNARKs. Intuitively, blockchain updates can beseen as a state transition system, and thus incrementally-computable SNARKs(which are simply SNARKs for state transition systems) can enable the construction of succinct blockchains.4.2.1Our ConstructionIn this section, we present the Coda protocol. Specifically, we discuss the detailsfor generic Turing-complete functionalities that transform a database. Then, inSection 5, we will instantiate the protocol with the payments functionality.At a high level, we will treat a blockchain as a state transition function.Consider, for example, a UTXO (Unpaid Transaction Output) model whereinevery party has an 鈥榓ccount鈥 with some 鈥榖alance鈥, like in Bitcoin. The state ofthe blockchain is a database (such as a Merkle tree) of all the account balances.A transition is transfer of some part of the balance from one account to anotheraccount. While this is just an example, our protocol is generic and considersany state set 饾洿 0 and a Turing-complete transition function Update0 with sometransition set T0; that is, we begin with (饾洿 0, T0, Update0).Then, the Coda protocol for (饾洿 0, T0, Update0) is constructed as follows. Weemploy our consensus protocol, namely Ouroboros Samasika, that we presentin Section 7. We will combine (饾洿 0, T0, Update0) and the consensus protocol12

to construct a new state transition system (饾洿, T, Update), mainly to subsumeconsensus verification in the update function. An incrementally-computableSNARK for (饾洿, T, Update) is employed and the proofs attest to the currentstate being computed correctly. The blockchain summary simply consists ofthe state in 饾洿 and the proof. A blockchain summary producer will just be aprover and a full node will only need to perform proof verification to verify theblockchain correctness.Having described the protocol at an intuitive level, we will now discuss thedetails. Given (饾洿 0, T0, Update0) and a collision-resistant hash function H, theprotocol components are as follows.The Coda ProtocolThe Coda protocol has the following components. Consensus mechanism (UpdateConsensus, VerifyConsensus): Theconsensus mechanism is the Ouroboros Samasika protocol that wepresent in Section 7. In Ouroboros Samasika VerifyConsensus runsin time poly(饾渾), as required.0 . The Blocks: Consider a transition 饾憽 饾憱0 饾憞 饾憥饾憿 0 that acts on a state 饾湈饾憱 1饾惖corresponding block 饾惖饾憱 (sn饾憱 , st饾憱 , 饾湅饾憱 , 饾憫饾憱 , b-pk饾憱 , 饾憦-sig饾憱 ) is constructed0 , 饾湅 饾惖 consensusProof and 饾憫 饾憽 0 .with st饾憱 饾湈饾憱 饾憱饾憱1饾憱饾憱 State transition system for SNARK: Consider the state transition system (饾洿, T, Update) defined as follows: 饾洿 {H(饾湈 0),consensusState} 饾湈0 饾洿 0 ,consensusState . A transition is a block. The function Update(饾惖饾憱 , 饾湈饾憱 1 ) verifies if H(st饾憱 ) 饾湈饾憱 1 , the signature verifies in the block verifies and that VerifyConsensus(consensusState饾憱 1 ,consensusProof 饾憱 ), where consensusState饾憱 1 is part of 饾湈饾憱 1 and 饾湅饾憱饾惖 contains consensusProof 饾憱 . Blockchain summary: The blockchain summary consists of a statein 饾洿 and a proof snark饾憱 . VerifyChainSummary(S饾憱 1 (饾湈饾憱 , snark饾憱 )): As mentioned earlier, thisalgorithm simply verifies the proof snark饾憱 against the statement 饾湈饾憱 . VerifyBlock(S饾憱1 , 饾惖饾憱 ): This algorithm, simply checks the consistencies,namely, verifying consensus, verifying signature and verifying thatthe state in S饾憱1 is the hash of the state in the block. UpdateChainSummary(S饾憱 1 , 饾惖饾憱 ): Let S饾憱 1 (饾湈饾憱 1 , snark饾憱 1 ). Thisalgorithm runs the Update function as Update(饾惖饾憱 , 饾湈饾憱 1 ) to obtain饾湈饾憱 . Then, it verifies the proof snark饾憱 1 . Finally, it runs the prover toobtain the new proof snark饾憱 .13

Figure 3: The Coda protocol.Remark 4.1. We assume that the length of the blockchain does not affect chainextractability, because no evidence suggests otherwise for the constructions ofSNARKs that we use, as also noted in [7].5The Coda Prot

Coda: Decentralized Cryptocurrency at Scale Joseph Bonneau1, Izaak Meckler2, Vanishree Rao2, and Evan Shapiro2 1New York University 2O(1) Labs Abstract We introduc