Aug 14, 2019
Security of Client Consensus
Abstract
There are two broadly different consensus strategies being employed by blockchain technologies today: miner and client consensus. Miner consensus is what is implemented in Bitcoin, so should be familiar to readers. In the client consensus model, the blockchain does not enforce validity rules. Its job is simply to unambiguously order a set of messages, letting each client determine their validity.
Understanding this difference and the client consensus security model is increasingly relevant today because many “layer 2” protocols have been developed that place their data into the OP_RETURN field of transactions, notable protocols implement tokens and human-friendly identity. This data is not validated by miners so these systems must use client consensus even though the “carrier blockchain” may use miner consensus.
Tokens are a key layer 2 protocol. “First class tokens” are tokens that have all the features and functionality as the carrier blockchain’s native cryptocurrency, analogous to “first class functions” in programming language design. First class tokens are enabled via miner consensus, either through sophisticated smart contracts or directly through blockchain consensus-level software changes. Client consensus models cannot achieve first class tokens, and so this work describes the functional gap that exists between first class token protocols and other non-first class protocols.
Overview
Interestingly, the Bitcoin whitepaper[1] is inconsistent when addressing the miner and client consensus models, making a correct blockchain unimplementable as specified.
The Blockchain Is Ordered, Timestamped Messages
To understand the issue, note that in section 3, the blockchain is introduced solely as a timestamp server:
The solution we propose begins with a timestamp server. A timestamp server works by taking a hash of a block of items to be timestamped and widely publishing the hash, such as in a newspaper or Usenet post [2–5]. The timestamp proves that the data must have existed at the time, obviously, in order to get into the hash. Each timestamp includes the previous timestamp in its hash, forming a chain, with each additional timestamp reinforcing the ones before it.
Section 2, on transactions, also reinforces this notion that transaction ordering is the critical purpose of the blockchain, and strongly implies that double spends may exist on the blockchain:
For our purposes, the earliest transaction is the one that counts, so we don’t care about later attempts to double-spend … and we need a system for participants to agree on a single history of the order in which they were received. The payee needs proof that at the time of each transaction, the majority of nodes agreed it was the first received.
This statement does not accurately describe the bitcoin software. A more accurate description would be “…a system for participants to agree on a single history of valid, non-conflicting, transactions”. In fact, the order of transactions on the bitcoin blockchain is irrelevant, since conflicting transactions are not allowed. The recent switch to lexical transaction ordering in the BCH blockchain is empirical proof of this irrelevance.
Clearly section 2 and 3 of the white paper more accurately describes a system that we would call “client consensus” today. Nodes can see double spends on the blockchain but use the order to determine which was the first received.
The Blockchain Is Unordered, Valid, Non-conflicting Messages
Let us re-examine the last sentence in the section 2 quote — “The payee needs proof that at the time of each transaction, the majority of nodes agreed it was the first received”. This is a complete fantasy. There is no code in bitcoin that implements anything like “the majority of nodes agreed it was the first received”. The blockchain extension algorithm is more accurately described as “the majority of nodes agree to accept the recent history presented by one lucky node, even if this history presents a wildly incorrect transaction receipt order, so long as the history is consistent — that is, it contains valid transactions with no double spends”.
And the whitepaper relies on this blockchain definition. In section 8, Simplified Payment Verification (SPV) is described as a method of verifying payments:
It is possible to verify payments without running a full network node. A user only needs to keep a copy of the block headers of the longest proof-of-work chain, which he can get by querying network nodes until he’s convinced he has the longest chain, and obtain the Merkle branch linking the transaction to the block it’s time stamped in. He can’t check the transaction for himself, but by linking it to a place in the chain, he can see that a network node has accepted it,and blocks added after it further confirm the network has accepted it.
The above paragraph about SPV clearly indicates that the author equates proof of a transaction’s existence on the blockchain with validation of that transaction.
However, if the blockchain is simply a “timestamp server”, meaning that arbitrary messages are allowed on it, then multiple transaction messages that spend the same coins would be allowed on the blockchain. Following the rules in section 8, it would be possible to provide SPV “proofs” for all of these spends, meaning that double spends would be easy to accomplish!
And when the white paper gets into implementation details in “5. Network”, it describes the actual bitcoin software more accurately, saying:
2)Each node collects new transactions into a block.
…
4)When a node finds a proof-of-work, it broadcasts the block to all nodes.
5)Nodes accept the block only if all transactions in it are valid and not already spent.
Note that there are no statements whatsoever about transaction time stamping, ordering, or making sure the majority of nodes agree upon that order. This information is actually completely unnecessary. If you gave me every transaction since the genesis block in a random order, I could use them to derive the UTXO set (which is the technical term for the current state of the bitcoin ledger).
This is the solution actually implemented in Bitcoin and is what we call “miner consensus” today. It makes the blockchain much more useful than a “timestamp server” that is not consensus, but one input into “client consensus” independently running on every node. In miner consensus, miners enforce transaction validity — invalid transactions, improper signature scripts, or double spent inputs are not allowed on the blockchain. This means that if clients trust the mining majority in certain ways (and this is one of the fundamental assumptions of bitcoin, since a mining majority can censor transactions, freeze accounts, double spend via blockchain rewind, and even “time warp” their way into minting coins faster), these clients can assume that a transaction that is sufficiently deep in the blockchain does not just exist, but is also valid. This is extremely powerful.
Repercussions of Client Consensus
Silent Fork
If miner consensus rules are different, or differ from a client’s consensus rules, a fork occurs. This results in either 2 “live” tips, if both forks have some hash power, or many clients that are “stuck” on an older block. In the former case, the existence of 2 tips is completely obvious to all participants since tips can be detected algorithmically and presented in a GUI or web site. In the latter case, these clients effectively remove themselves from the network and this is obvious to their users.
Client consensus errors can cause a “silent” fork in the sense that no participant realizes that the fork has occurred. The UTXO set has diverged and there is no proactive means to detect that situation. Detection may eventually occur when a forked client attempts a transaction that sends forked tokens to a client on a different fork. The receiving client will never see those tokens. Presumably an engineer will eventually be called in to analyze why the software is not showing the transaction and the fact that a fork has occurred will finally be discovered.
After the this article was first published, a reader brought a live example of a silent fork to my attention. Please examine https://explorer.bitcoin.com/bch/tx/9208368b809f34bca6cb5cdc0ea41feecf4e2de9d55d3a8e4a9640b38a3b122f and https://simpleledger.info/#tx/9208368b809f34bca6cb5cdc0ea41feecf4e2de9d55d3a8e4a9640b38a3b122f. According to one site the “mint baton” is simpleledger:qz2yga9cmdq9jvyhj0g4fdj7nkvtl9zxa5kyk7lhs5. According to the other it is simpleledger:qrx6z4u9c4paptgsd7lttdrep388sm7p8u95nkrys2. Since the “mint baton” controls creation of new tokens, it would presumably now be possible to create some “silent fork” tokens — that is tokens that exist according to one wallet but do not according to the other.
As an interesting aside, note that without miner consensus the BCH and BSV monetary fork could have happened without actually forking the blockchain! Instead, an output could have two valid TXOs on the same blockchain, one valid in BCH and one valid in BSV. Is this a desirable outcome?
Consensus Ambiguity
The Simple Ledger Protocol[4] (SLP) proposes a transaction set commitment to solve the silent fork problem, to be issued periodically by some entity (see [4] section “Transaction Detail.COMMIT”). If deployed, this creates an ambiguity between the two not-ideal choices of client consensus or a central authority, rather than solving the problem. Wallets now need to choose to either trust the commitment issuing entity (generally the token issuer), or the client consensus rules if there is a discrepancy. Although the SLP spec explicitly states that COMMIT transactions are not “consensus”, if many wallets use COMMIT transactions rather than separate analysis, then it becomes de-facto consensus. Any discrepancy could be used to double spend, and the COMMIT issuer can censor transactions for the view of wallets. Finally, a wallet could be very conservative, choosing to disallow further transactions if a discrepancy is found. But this may be the worst choice since the token issuer’s decision to stop trading may not be in the best interests of token holders.
Consensus ambiguity is also dangerous from a legal perspective: it allows the argument that trades that do not appear within one consensus framework were not made. This argument may be particularly strong for “registered” securities since transfers legally must be acknowledged by the registering authority. Without transaction commitments, there is an argument that can be made that the blockchain itself IS the registering authority’s database and therefore acknowledgement. But given commitments by the registering authority, the argument that these signed statements supersede the authority blockchain, seems very reasonable to this non-lawyer. This effectively turns SLP into a permissioned token system.
Differentiation of SPV and Validity
As described in the prior section, SPV proves that a message exists on the blockchain, not that it is valid, unless the blockchain only allows valid messages. Since client consensus models allow invalid transactions onto the blockchain, SPV can no longer be used to verify transaction validity.
Light clients must therefore rely on trusted validators.
Stronger SPV
SPV has some limitations — for example, it cannot be used to prove that a transaction output is currently unspent. However, these limitations can be fixed using a UTXO commitment system that allows SPV-style proofs. In review, in UTXO commitment scheme, a miner places a commitment (a merkle tree hash, or ECMH hash[3], for example) of the current UTXO set in each block created. In the miner consensus model, this commitment is then validated by all other miners. This means that light clients can utilize a technique similar to SPV to prove the existence of a transaction output in the committed UTXO set.
However, this technique cannot be used in client consensus models for two reasons. The UTXO commitment itself may be incorrect if is not validated by miners, and transactions within the UTXO may not be valid.
Trust-based Light Client Security Model
If light clients cannot use SPV validation, they must trust data provided to them by other entities (often full nodes). This solution dramatically changes the client security model, broadening it to encompass the security of the data provider (including physical security, software and hardware correctness, and the honesty of employed individuals), and that of the intervening network. Technologies like HTTPS can solve some of these problems, yet introduce additional risk themselves.
The security model becomes so broad it cannot be reasonably analyzed in this paper.
Upgrading Software
In the client consensus model, upgrading the protocol is problematic, given realistic assumptions (like everybody doesn’t upgrade when told to). Older clients will reject new format transactions as invalid so they will be on a “silent fork”. Mallory can double spend coins by first issuing a new format transaction, and then an old format transaction. If clients are coded to detect a new transaction version and stop functioning, Mallory can issue fake transactions coded with the new version to stop all clients before the new software version is ever released.
In the miner consensus system, the unforked blockchain typically is abandoned within 1 or 2 blocks, providing a clear indication of the fork to all older clients, since they see an invalid, most-work fork that is still growing, and a valid less-work fork that is not.
Attacks Against Partial SPV Clients that use Client Consensus
There have been many arguments for light clients within client consensus systems that change things by making the light client a bit heavier — the client does more validation than a SPV client, but less then a full node. This may work for cooperative users but, the following attacks show that this is not generally possible. Clients must hold the entire “client consensus” UTXO set, which can generally be made arbitrarily large by participants simply by making many messages, if the protocol allows participants to permissionlessly make any messages. These attacks are presented in the context of tokens, although they are generally applicable.
CPU/network Exhaustion Attack
Mallory creates a real extremely long or wide token history, and injects extra (fake) tokens somewhere in that graph. The client must validate this entire history to find the fake tokens that invalidate this entire history. It has been argued that the client could trace back just N steps for a certain level of security. But if Mallory knows or can discover N, he can inject fake tokens at N+1 to “print” tokens.
Since full nodes ignore all of these fake transactions, none of Mallory’s real tokens are lost in this process. The only expense is transaction fees.
It has been argued that clients could refuse to acknowledge tokens with a large history of say N validations. Mallory could create a valid token history that is N-M validations and then send dust transactions to every address holding tokens. Mallory has effectively inserted time “bombs” into every wallet that renders the token unspendable to certain wallets after M transfers.
Parallel Construction Attack
It has been argued that a client only needs to trace tokens he is interested in backwards to genesis or to a checkpoint.
In that case, Mallory first spends tokens to himself. In the next block, he spends the same tokens to Alice, creating essentially a parallel construction of token history. Mallory presents Alice with the full SPV proof history of this latter spend, back to token genesis, and doublespends by presenting Bob with the full SPV proof history of the former spend.
Full node wallets will see the first spend as valid, but the token transfer to Alice can be sent to Betty then Carol, etc and the invalid token will not be detected until one of them is running a full wallet.
Parallel Construction Spray Attack
Mallory can likely purchase or otherwise acquire arbitrarily old, already spent private keys that once held a large quantity of tokens and build an arbitrarily large parallel construction that is invalid yet trace to the genesis block.
He can then send these fake tokens to arbitrary addresses (that have received real tokens, as determined by blockchain analysis) forcing these wallets to fully download and validate a complex parallel construction only to discover a double spend deep in the transaction history. And note that the wallet is not guaranteed to discover the double spend. It will only discover the double spend if an ancestor of the wallet’s current holdings is one of the double spent coins, since the wallet is only tracking its own coins.
Unlike Bitcoin dust “attacks”, no real tokens are spent, making this attack considerably cheaper. Bitcoin dust attacks are practically avoided by just ignoring very low value outputs. But in this case, the output amounts could be considerable (since they are fake).
Conclusion
Client consensus models are weaker than miner consensus since forks can coexist without detection. This will allow attackers to exploit consensus issues for a potentially significant period of time before detection. Today, exchanges accept deposits of “miner consensus” coins after N “confirmations” (blocks) without seeing a fork. However, exchanges working with client consensus must understand the issue of silent forks, and realize that additional confirmations only reduce the likelihood of a reordering attack but do not reduce the likelihood of an invalid transaction.
It seems clear that protocols using client consensus must not use SPV validation. This has significant ramifications for blockchains that use on-chain scaling such as BCH and BSV since the end-user wallet is unlikely to be capable of handling the full blockchain transaction load. This means light clients must resort to trusting full nodes, which dramatically changes the security model. Problems have already occurred. The Electron Cash wallet does not trust full nodes — mostly. However, it did allow full nodes to tell wallets that an upgrade is needed, and to provide a download link. This notification was exploited to trick users into downloading malicious software that stole wallet balances[2].
One final thought — cross chain atomic swaps[5] may allow reasonably fluid inter-blockchain transactions. If such a technology is deployed, light clients may be able to track and perform exchanges between a “crypto” blockchain and a “token” blockchain (supporting first class tokens) more safely and efficiently than for crypto and non-first class tokens coexisting on a single chain.
References
[1] Bitcoin: A Peer-to-Peer Electronic Cash System
https://nakamotoinstitute.org/static/docs/bitcoin.pdf
[2] PSA: Electrum and Electron Cash servers are being Sybiled — AGAIN!
https://www.reddit.com/r/btc/comments/am88lh/psa_electrum_and_electron_cash_servers_are_being/
[3] Elliptic Curve Multiset Hash
[4] Simple Ledger Protocol
[5] Atomic Swap
