Part1Generic Techniques to Build Light Clients

In this section we provide an overview of several generic techniques and protocols that can be used towards designing blockchain light clients and list examples of light client implementations that are based on each technique.

1Header Verification and Consensus Evolution

A common approach when designing bootstrapping and synchronizing for light clients is to only have them verify the block headers and skip verification of transactions or account states (as opposed to standard clients who verify the full blockchain history). This popular technique is adopted by SPV , Ethereum and many others.

In Proof of Work consensus, block header verification is straightforward, as the client only needs to verify the proofs of work based on block hashes and nonces. However, additional considerations must be made in Proof of Stake or BFT consensus blockchains to preserve security. For instance, in Proof of Stake, normally the client also needs to verify account states and balances in the whole blockchain history, or consider the risk of long range attacks. In short, the client needs to be convinced that the blockchain consensus has evolved correctly and honestly throughout the history, and no malicious majority was ever present. For BFT-consensus, there is an additional challenge: BFT validators can join and leave, and a client needs to verify the consensus evolution through all validator signatures. A common technique to shorten the client's work is by storing intermediate checkpoints so that clients are not referring to the genesis block each time they verify the current validator set. On the other hand, validator set re-configurations, known as "epochs", present additional considerations.

2Compressing the State

Being append-only immutable ledgers, the issue of ever-growing storage requirements in blockchains was implied even in the original Bitcoin whitepaper, which considered pruning old, spent transaction information (although never adopted from the community due to security concerns). However, securely pruning "obsolete" data from a blockchain is a direct step towards client efficient bootstrapping and synchronizing.  As an example, Ethanos uses a form of "temporary" pruning in the account-based model.

We note that redacting is a relevant but stronger notion, with the main goal being to make the blockchain conditionally mutable rather than just reclaiming storage. This "mutable" blockchain approach mainly relies on the chameleon hash primitive.

As another method of compressing the state, aggregate signatures, such as Schnorr and pairing-based BLS signatures, can compress many signatures (even under different keys) into a single signature, which in case of BLS, is constant-sized. However in the blockchain setting, aggregate signatures are vulnerable to "rogue key" attacks, where an adversary can produce an aggregated signature for arbitrary public keys, and typically requires a zero-knowledge proof (ZKP) of correct public key computation. Non-interactive EdDSA half aggregation provides ways of compressing multiple Schnorr/EdDSA signatures to a single signature with half the size of the original signatures. One could also consider aggregating signatures using zero knowledge proofs. Overall, aggregate signatures, already used by Plumo, is a promising primitive towards light client implementations, as it is estimated to save a significant portion of the needed bandwidth and storage. Another potential option is for the validators to engage into some interactive protocol in advance as part of the consensus committee protocol, using threshold signatures.

3Removing the State

Taking it one step further, stateless blockchains aim to only keep a succinct and verifiable representation of the entire state at all times. Compacting a blockchain in this manner is light-client friendly(This approach is sometimes referenced in the literature as "extremely light clients". ), as the bootstrapping and syncing costs would be minimal, and the "stateless" blockchain approach used by Mina , Edrax and others, is also becoming popular. However this can potentially hurt security guarantees, for example the consensus algorithm should be able to securely handle forks, which can happen at any point; there is either a significant share of malicious consensus participants, or simply a network partition. Some works claim that stateless Proof of Stake blockchains are impossible, while others introduce special consensus considerations to maintain security.

Several works point towards the stateless blockchain direction. For instance, Vector Commitments and Subvector Commitments (a special category of Vector commitments), can be used to build a stateless cryptocurrency by committing to key-value maps. Pointproofs further improved this idea by enabling aggregation of individual subvector commitment proofs into a single proof by anyone, as well as cross-commitment proof aggregation (i.e from multiple subvector commitments) while also ensuring the hiding property (which vector commitments do not necessarily guarantee). Hyperproofs are tree-based data structures that are aggregateable and homomorphic, which are very useful properties for implementing stateless blockchains, and have polynomial commitments as their underlying primitive. Although efficient in their aggregation and update operations, hyperproofs require a trusted setup and have a public parameter size linear to the number of the proofs (i.e. the tree leaves). Finally, SNARKs seem to be a natural tool for implementing stateless or succinct blockchains, while also requiring very low computation for verification; however to be practical, ZKP friendly cryptographic primitives are recommended.

4Leveraging Game-theoretic Assumptions

In a unique approach, light clients can be built on top of a smart contract interacting with the client and a set of full nodes, thus offloading all blockchain queries and replies to those nodes, with the client themselves performing minimal computational work. In this setting, all participants (i.e. client and full nodes) need to lock funds in an "arbiter" contract as collateral to discourage dishonest behavior. Therefore, rational full nodes are incentivized to provide correct replies to the client's queries or risk being penalized. Such an approach naturally requires a blockchain that is augmented with smart-contract capabilities, but is otherwise agnostic to its other properties.

Part2Systematization Methodology

The design of light clients has always been a vibrant topic of discussion in the community. A number of proposals have been given ranging from simple forum or blog posts to rigorous theoretical works and actual deployed systems. In our systematization, we only consider works that represent a distinct light client proposal (i.e. not generic techniques as discussed above), and include at least some form of security discussion.

In particular, we first consider the functional and basic operation axis, where we categorize light client proposals based on their functional properties. These include their compatibility on existing systems (which is preferred), if they require modifications or if they propose a new standalone system. We also note if they are designed for a specific consensus algorithm, and the cryptographic primitives they use.

We observe that verifiable queries of non-existence are neglected by light client protocols and therefore omitted from the table. Also note that while clients should always be able to make verifiable queries, wallet functionality is not always included in each one of them. However, we omit a reference to this functionality from our table, as adding it to an existing client protocol or implementation is usually trivial.

The efficiency axis, includes several aspects of light client efficiency characteristics. Note that our systematization is not meant to be used as a direct asymptotic comparison between different light client proposals and protocols. Such a comparison is impossible as the clients operate on top of different underlying schemes.

In Table 2 we provide a coarse categorization based on their performance in each efficiency category, indicated with a "good" or "bad" practice icon (thumbs up and down icons respectively). In general, a sublinear cost with respect to the number of blocks is treated as good practice, however, in some cases we deviate from this rule to take concrete costs into account - we mark those with a "*" in the Table. For storage efficiency, we consider both the prover and verifier, where a thumbs up icon denotes good practice for both. Communication efficiency denotes the requirements for proof size, while bootstrapping efficiency denotes the initial cost of client joining the system as well as the syncing maintenance cost.

Finally we consider security as the third systematization axis and present our findings in Table 3. 

We start by listing any required assumptions (i.e. beyond the Basic Assumptions that each light client proposal needs, "_" means that no additional assumptions are made. Then, for each required security property (secure bootstrapping and querying), we indicate whether the light client scheme satisfies the property ( ) or a known vulnerability exists () In cases where a security guarantee of a light client has not been proven via a security (or sketch) of proof, we denote this by the exclamation mark symbol (). In Table 3 , we also consider the network-level assumption separately, as it is more secure for the light client to communicate with the blockchain in a distributed fashion. Therefore we mark schemes with that communicate independently (e.g. peer-to-peer) with the blockchain system, while schemes marked with rely on a centralized server or full node.

In all of our Tables, we group the schemes into two main categories based on their design. The first group follows the "stateless blockchain" approach for constructing efficient light clients, while the second group follows the "efficient bootstrapping - synchronization" approach. We keep the game theoretic-based work as a third separate category.

Part3Existing Light Client Constructions: Insights and Gaps

In this section we discuss the works listed in our Tables in more detail, and present a series of interesting insights and gaps. We organize our discussion in a similar way to our scheme grouping for each table, by first analyzing schemes that follow the stateless blockchain approach, then schemes which have efficient bootstrapping and synchronization as their main goal.

5Stateless Blockchains for Light Clients

Here we consider schemes that enable a stateless blockchain design, namely a blockchain with a succinct and verifiable representation of its entire state.

SNARKs are an effective tool for implementing a stateless blockchain, with Mina using them in an recursive fashion, chaining them together, eventually having a single SNARK to verify the whole blockchain state. It utilizes a variant of the Ouroboros Genesis Proof of Stake algorithm to preserve consensus properties in a stateless setting. Essentially, SNARKS are used as a tool to implement "incremental" verification of recursively-composed proofs, and follow-up works  improved this paradigm. However, SNARKs typically imply a significant burden on the prover. Plumo uses SNARKs for proving transitions in the consensus committee, enabling fast synchronization of light clients through "checkpoints", thus only needing to fetch data after the most recent checkpoint. These checkpoints also include periodic proofs of BFT consensus evolution to preserve consensus properties, efficiently verifiable by light clients such as resource-constrained mobile phones. PoNW also uses SNARKs and incremental verification, in addition to a Proof-or-Work variant (Proof of Necessary Work) to take advantage of the computation performed by the consensus layer, while Chen et al. in a more extensive study of incremental verification in blockchains, provide a framework to make an existing system incrementally verifiable using a "compatible" consensus algorithm. This work is also the first to provide directions for implementing this paradigm in the context of privacy-preserving blockchains like Zcash by applying incremental verification combined with ZKPs on the public state of the system (which for the case of Zcash is the set of serial numbers and coin commitments). Still, it leaves many questions open, such as which entities will be responsible for providing the proofs, or the overhead on the system which is already not among the most efficient ones.

Gap 1 Is a complete and efficient light-client scheme possible that is compatible with privacy-preserving systems?

We should also mention that zk-SNARKs were used in zk-rollups: a laver2 scalability solution to move data and computation off-chain. However, except for Chen et al , none of the SNARK-based approaches seem to consider the prover's substantial overhead, which in a blockchain system would be the consensus participants or the full nodes.

Beyond the prover costs, most SNARK approaches come with additional assumptions such as a trusted setup phase. That leads us to the following Gap:

Gap 2 Can we design a light-client scheme that satisfies all the security properties while being efficient and practical for the client with a minimal overhead to the consensus participants or full nodes?

As an intermediate solution, additional financial incentives for entities producing such proofs could alleviate the extra computational requirements, however this is only applicable to blockchains that implement or contain a cryptocurrency.

Improving on the Vector Commitment approach  Boneh et al. introduced techniques for efficiently batching various operations in RSA accumulators (e.g. additions, deletions and witness creation), all of which can potentially utilized for implementing stateless blockchains (e.g. committing to the UTXO set as an accumulator state). RSA accumulators are used by MiniLedger as an alternative model to Merkle trees. Since RSA Accumulators involve a trusted setup (or novel but more expensive class groups), hash-based accumulators were proposed by Utreexo, however with a different goal, to reduces storage for a fully validating node. An additional concern in the RSA accumulator approach is the extra overhead of maintaining the accumulator (which depending on the implementation, would be paid either by consensus participants or full nodes).

Edrax proposed a cryptocurrency where validators only need to verify a commitment of the most recent state. Edrax implemented this approach in the UTXO model by utilizing sparse Merkle trees to represent the UTXO set, and also in account model by utilizing distributed vector commitments. In the UTXO-based case, validators first verify if a transaction's input belongs in the set, and then simply remove that input and add the output in the set. In the account-based case, they utilize distributed vector commitments to still make transcations possible without requiring interaction between the sender and receiver. However, clients need to constantly synchronize their local proofs with respect to those commitments, and will have to pay a significant synchronization cost after an offline period. Although Edrax proposes an additional untrusted entity to provide synchronization proofs on behalf of the client, this nevertheless introduces a significant overhead overall in the system.

Insight 1 Redactable blockchains have not been explored as a solution towards implementing light clients.

Blockchain redaction has the potential to be utilized in several ways, for instance, a series of blocks can be replaced by a single block containing compressed information. An interesting direction might be to execute redaction operations at the consensus layer.

6Reducing Bootstrapping and Synchronization Costs

An important property of light clients is the requirement for an efficient way to initialize itself and join the system; downloading gigabytes of data and performing heavy verification operations on millions of transactions is prohibitive for a mobile or browser-based client. This is also important if the client is disconnected for some periods of time and needs to reconnect, or even just to maintain a synchronization with the current state of the blockchain.

Gap 3 No light client approach or implementation explicitly considers frequent offline phases, where the client needs to re-sync with the current system state.

SPV follows the Header verification approach, which while generally efficient for a light client, suffers from potential security issues (especially in Proof of Stake and BFT consnensus), and fully relies on the availability and honesty of a single server, while also exposing its privacy to that server. Ethereum's native light client also follows this paradigm without relying on a single server or full node, however its concrete bootstrapping, storage and communication requirements are practically prohibitive for a light client implementation.

Vault is a prominent example of a standalone system designed for significantly decreasing bootstrapping and participation costs. It is based on Algorand's proof of stake protocol, however it works in an account based model using sparse Merkle trees similar to Ethereum. Vault introduces techniques such as decoupling double-spend detection from account balances by making transactions valid only for a parameterized block window, while also pruning accounts with no balance, sharding the account state tree across participants, and using additional "stamping" certificates to convince new joining clients on block validity, which have reduced size by trading off liveness while still preserving safety. Although Vault (as a standalone cryptocurrency) was not designed with light clients in mind (e.g. a client needs to constantly perform an update operation while its transaction is pending), its techniques which seem to decrease bootstrapping costs by one or two orders of magnitude, can serve as a guideline for implementing light clients on top of existing systems.

In another approach. Ethanos chooses to reduce the bootstrapping costs on Ethereum by not downloading "inactive" accounts, and invoking a "restore" transaction when such an account needs to reactivate itself. This special transaction type has the inherent limitation of needing to be submitted by another "active" address, and is essentially a Merkle proof of the last known account state (or checkpoint), along with void proofs that no more recent checkpoint exists (paired with a Bloom filter for space efficiency). In this manner, Ethanos reduces bootstrapping costs by a constant factor of 2 .

Non-Interactive Proofs of Proof-of-Work (NIPoPoWs) further improve the notion of SPV client by introducing a new primitive under the same name. This primitive, designed for Proof of Work blockchains, constructs a multi-layer chain of blocks from the basic chain, where each layer is essentially a skip list of blocks that satisfy a lower target (i.e. higher dfficulty) in the PoW puzzle. In this way, a new client can avoid fetching the entire chain of block headers as in SPV, which translates to logarithmic asymptotic costs (or a few hundred kilobytes proof) making an even more efficient light client. While NIPoPoWs assumed static difficulty across the chain, Flyclient uses an efficiently-updatable Merkle tree variant (Merkle Mountain Range commitments) as underlying primitive for compatibility with variable-difficulty PoW chains.

We also mention some works further improving NIPoPoWs and FlyClient. Kiayias et al. discuss how to securely implement them on top of existing systems through a "velvet" fork, i.e. without requiring a soft or hard fork but only through a minority of the miners. TxChain extends NIPoPoWs and FlyClient to efficiently handle a large number of transaction verifications distributed across several blocks, by introducing a new transaction type ("contingent" transaction), serving as a single reference to other transactions and replacing the need to provide transaction and block inclusion proofs for the skipped blocks (which potentially can be more expensive even than a naive SPV client).

Diem's verifying light client fully relies on a full node to receive query replies and proofs (in contrast, Binance light client, which also relies on a full node, does not explicitly verifies any proofs). As Diem utilizes a BFT consensus, it also needs to receive "epoch proofs", which prove to the client correctness of evolution of validator signatures. In addition, recent work suggest to further compress epoch proofs by an epoch skipping technique, without however addressing long range attacks. Tendermint (used in Cosmos IBC) proposes a similar technique based on the latest block height which ensures that at least one validator is honest based on validator intersection and the byzantine threshold. Plumo's proofs of BFT consensus evolution also aim to reduce client synchronization load.

Insight 2 Light clients in BFT-based consensus blockchains can be implemented through full nodes, where clients make queries and full nodes provide verifiable proofs alongside with epoch proofs.

Insight 3 In BFT-based consensus blockchains, aggregate signatures (e.g. BLS signatures or ZK-friendly signatures) can be used to compress not only transactions, but also validator signatures, leading to further reduced bootstrapping and synchronization costs for light clients.

An alternative approach to Diem and Plumo is used by Dfinity's Internet computer, a blockchain-based protocol that creates a network of decentralized data centers running smart contracts, inspired by Ethereum. Dfinity utilizes key re-sharing within a threshold signature scheme to accommodate validators joining or leaving, aiming at circumventing the need for tracking their key evolution by a client. However, it is unclear whether this approach guarantees BFT security at all times, as it assumes that validators will delete their old shares afterwards. For instance, suppose the consensus system has 7 honest validators from a quorum of 10 validators, which guarantees the consensus security properties. Still, if 12 validators join afterwards, which now implies a tolerance of 7 Byzantine validators, this can potentially compromise consensus, as the previous 7 "honest" validators might not have deleted their key shares. In addition, Aumasson and Shlomovits highlighted the possibility of an adverary corrupting the key re-sharing process in some threshold signature schemes, which could potentially hurt consensus liveness.

Insight 4 For blockchains based on BFT consensus, frequent validator re-configurations (e.g. joining, leaving or key rotations) usually imply additional work for clients.

While the insight above is not applicable to off-chain reconfiguration approaches such as Dfinity, such approaches are typically prone to long range attacks.

Gap 4 A light client of a BFT-based consensus blockchain normally needs to verify the evolution of validator signatures using "epoch proofs" to prevent long range attacks. Is it possible to design a secure protocol for BFT consensus that either compress these proofs or circumvents this requirement entirely?

More recently, Chaidos and Kiayias proposed a new primitive, called stake-based threshold multisignatures. This primitive enables a client's bootstrapping through header verification in Proof of Stake systems like Cardano, in a similar way to SPV, without however needing to verify the participant's stake history and without the need of any modifications to the Proof of Stake consensus as in Mina.

7Smart-contract Based Approaches and Blockchain Interoperability

We briefly discuss implementing light clients by querying full nodes though a smart contract, and assuming "rational" behavior from the client and the full nodes after the required collateral deposits to participate, similar to the work by Lu et al. This approach can potentially address many of the previously discussed gaps, as the rational behavior assumption can circumvent technical difficulties or limitations which rise from complex cryptographic primitives. For instance, a light client can make a query of non-existence, and assuming full node rational behavior, will get a correct reply (i.e. inclusion proof if queried data exists, or a negative reply in case such data does not exist, which can be challenged if another node presents an inclusion proof thus penalizing a false non-existence claim). However there are several caveats to such an approach: First it naturally requires a smart-contract, which implies a time delay until it received the reply to its query, incompatibility with blockchains without a smart contract, and additional monetary costs for the contract's "gas" fees which can be potentially very high. Also, the client might merely receive an answer to its query (e.g. a simple "" reply if answer to query does not exist) without a cryptographic proof, which leaves this problem still open. Finally, the game-theoretic model might not capture cases where the client is considered a "high value target", where a full node (or a coalition of them) might choose to actually behave "irrationally" and intentionally risk being penalized in hope for other (not necessary monetary) gains.

Gap 5 Can we design a light client protocol compatible with queries of transaction or account state non-existence proofs?

From the above approach we observe however that it is trivial to implement an efficient light client that makes and receives queries to a "trusted oracle" (which in the above case were the rational full nodes following the protocol), without needing to make verifications, even if such an oracle is decentralized. This implies that such a client would be possible to exist even in extremely resource-constrained environments such as a smart contract itself:

Insight 5 Interoperability: Ideally, light clients should be implemented as a smart contract without the use of trusted oracles. This would allow for verifying transactions of a blockchain inside a contract of blockchain .

Gap 6 Implementing reasonably efficient light clients inside smart contracts might be impractical for many non zero-knowledge proof friendly blockchains or ledgers without succinct fraud proof in optimistic settings.

Although Cosmos makes a first step towards building a light client compatible with several blockchain systems (including those with smart contracts), it is still not known if we can also utilize previous techniques or primitives to implement such clients in pure smart-contract based blockchains, e.g. Ethereum.

Part4Conclusion

The blockchain community is witnessing a continuous effort towards implementing efficient light clients, suitable for resource-constrained devices or environments like browsers or mobile phones, while maintaining the underlying blockchain's security guarantees, and without introducing additional trust assumptions. As we observe different perceptions of light client properties across blockchain systems, we first provide a categorization of the most important light client properties. Then, we present a systematization of proposed light clients across three axes derived from our property categorization. Our systemization helps to identify a number of exciting open problems on implementing light clients which we summarize below.

We first observe that light clients satisfying our properties, and compatible with privacy preserving systems have not yet been implemented (Gap 1), with recent works providing preliminary directions. In addition, no current scheme seems to satisfy all of our functional, efficiency and security properties together (Gap 2). Also, existing works seem to neglect the case of frequent light client offline phases, which might be inefficient even for clients with efficient bootstrapping protocols (Gap 3). Distributing prover's work among the main blockchain participants (consensus layer or full nodes) along with providing incentives are possible directions.

Furthermore, it is not yet known if light clients can be efficient enough, such that they can be run from smart contracts across different blockchains (Gap 6). SNARKs seem to be a promising primitive towards this, although this still need to be shown in practice. Also there seems to be room for improvement for light clients implemented on BFT-consensus blockchains (Gap 4) by leveraging primitives such as key re-sharing and threshold signatures in off-chain protocols, while however considering Byzantine nodes in special cases. Finally, proofs of non-existence, a desired property in blockchain systems, is still missing from all current light client implementations (Gap 5). We hope our work will provide research directions for the community towards usable and secure light clients for blockchain systems.