NimbleCoin is a new cryptocurrency I’ll be hopefully launching soon. One of its nice features is that it uses the FastBlock5 protocol (a 5 seconds block interval) to achieve near instant payments. Because NimbleCoin also implements merged mining, each block header can be as large as 700 bytes (including Merkle branch and coinbase transaction). Yesterday Mike Hearn asked my a difficult question: how would NimbleCoin SPV nodes (such as the ones running on smartphones) process tons of headers if the bandwidth is limited or the clients are disconnected from the Internet for long periods?
The answer is Smart-SPV, a variation of the standard SPV headers-only mode that allows a smartphone to keep a fairly accurate state of the wallet balance without downloading all the missing headers and without sacrificing battery life and time.
Headers-only SPV clients downloads a complete copy of the headers for all blocks in the entire blockchain but not all the transactions. In order to update the user wallet, SPV clients ask their peers to filter those blocks that contains transactions that the SPV is interested in, such as those that have payments to their own bitcoin addresses. This is done using bloom filters.
In Smart-SPV mode, when a client is missing block headers three things happen simultaneously:
1. The clients starts downloading block headers from the last currently solved block, forward. This allows the wallet to receive new payments.
2. The client starts downloading block headers from the last one solved, backwards. This allows the wallet to catchup wit very recent payments.
3. The client starts downloading the blocks headers from the first missing header, forward. This allow the client to detect old missing payments.
While the client catches up with all the missing blocks, the wallet balance may not be fully reliable. Nevertheless if a new payment is received and confirmed, or a new payment is made, the wallet will increased the balance and show it. This is what the user expects. The following diagram shows how the block-chain is downloaded simultaneously:
Security Assumptions
First let’s review the main security assumption of headers-only SPV:
- The attacker does not control all your communications with the payment network.
This means that there is at least a single connected peer that behaves honestly. This assumption is quite strong and may not hold during short periods of time, such as during application power-on (when only a few peers have been connected), or when moving to a place where the ISP is untrusted. For SmartSPV we’ll require weaker security assumptions:
- The attacker cannot control all your communications with the payment network for more than a fixed period of time (e.g. 2016 blocks for Bitcoin or approximately 15 days)
- The attacker is rational: it won’t spend an huge amount of money to steal a much smaller amount.
This assumptions imply that the attacker may control all your Internet connections while he sends you a malicious block branch containing a fake payment to you.
And we’ll require a payment network performance assumption (which is not as security assumption but a usability requirement):
- The network difficulty won’t drop abruptly in a short period of time (e.g. a drop to 1/4 of the difficulty in 2016 blocks)
The last assumption allow us to verify and accept orphan SPV branches with a few confirmations as long as the accumulated work in the orphan chain is near the last verified network difficulty multiplied by the chain length. If the network hashing power dropped abruptly and the SmartSPV hadn’t yet downloaded the chain that includes the re-target block, then the SmartSPV client would require additional confirmation blocks to accept a payment, slowing down the confirmation to the user, but still preserving the security properties.
How it works
A live block is a block which is the last block of the block-chain and it’s received on time (it has a time-stamp near the current time). Each time a live block is received, it is flagged as LIVE and this flag is stored permanently with the block. A live transaction is a transaction that is included in a live block. The target work of the last block known rooted to the genesis block is LAST_WORK. When a live transaction is confirmed by N blocks flagged as LIVE the transaction is considered mature. N is chosen such that the cumulative work of the confirmation chain is 6*LAST_WORK. This means that an attacker trying to send fake blocks with lower than the almost current difficulty is forced to create more of such confirmation blocks and gains nothing. If difficulty is unchanged, then 6 confirmation blocks are required. A mature transaction may be present in a block that is still orphan. All mature transactions are scanned and used to compute the balance of the wallet. Also all transactions that are included in blocks rooted at the last checkpoint and finishing in the last live block are also considered mature (this is the standard condition). Since the wallet always modifies the balance according to mature transactions, a payment is received and acknowledged even if the branch where it is included is still orphaned. If the SPV client clock is correctly synchronized, the Smart-SPV protocol does not pose any additional security risk different from the known SPV limitations.
Attacks and countermeasures
If the height distance between the last known block rooted in the genesis block and the live block is too high (e.g. more than 2016 blocks) then the SmartSPV client may try to request intermediate blocks (preferably the re-target ones) before accepting a mature branch to attest if the difficulty has gone up too much during the inactive period. Nevertheless it’s not generally expected that a smartphone is left unconnected from the Internet for more than 15 days, nor it is normally expected that the difficulty increases by a factor of 2 or more in a single re-target, so by increasing the confirmation blocks from 6 to 12 any difficulty change can be compensated.
Last but not least, we may protect from an attacker trying to send to the SmartSPV node a pre-computed chain as if it were live. This attack is costly and 6 blocks need to be mined by the attacker at current difficulty. Nevertheless there is a protective measure. If a transaction of interest is found in a live block X with height H and the required confirmation blocks have been received, the SmartSPV client asks every peer for the block hash of the block at height H in their best chains.This assumes at at least one peer is honest. If any peer node reports a different block hash from the hash of X, the competing block is fetched and validated. If the competing block is also correct, then the block X is not considered live (the LIVE flag is removed). As previously said, this prevents an attacker from taking considerable time by pre-computing a chain of blocks with future times, waiting for the prepared moment and executing the attack as if the blocks were recently mined. Because we assumed that during the attack all peers may be dishonest, to preserve security of the method the attack should be too expensive (so the attacker is being irrational). If the attacker can re-use the pre-computed orphan chain to attack several SmartSPV nodes at once, then the cost of the attack stays the same, but the attack reward is increased proportionally to the nodes he manages to cheat. This attack is difficult to prepare, the attacker requires that all victims are attacked at the same time (if not, SmartSPV nodes wouldn’t tag the fake blocks as LIVE). Although this may be practically impossible, theoretically it breaks the security assumptions. But if the attacker is given a new unique previously unknown payment address just before the payment is made then the per-computing attack cannot be performed. Then SmartSPV nodes should accept payments from untrusted parties if either:
- A secure connection with the payment network is granted (at least one honest node in peers). This can be assumed if you’re using your own Wi-fi router.
- A signed checkpoint was recent
- A payor was recently given a new address for the transaction.
- The payment amount is lower than the block reward divided by the number of SmartSPV nodes that can be simultaneously attacked (which can never be more than 2000 for the current Bitcoin block-size, but would be practically never more than 100). For a 25 BTC reward, 100 nodes attacked, and an exchange of 600 USD/BTC, this is equal to 150 USD.
All these checks can be performed automatically by the smartphone, so a red-flag will only appear if non of them is true.
When querying peers for a block at certain height the SmartSPV node may opt to require a majority of peers to agree instead of a single dissident one to protect from a malicious peer, but the cost incurred by the malicious peer to create a fake block to invalidate the mature transaction is high and the effect is only a temporary DoS.
Off-Topic
I’m trying to achieve the best possible user experience buying with NimbleCoin and I hope all of you take part of the project when launched!
FYI NimbleCoin reference implementation is not based on the Satoshi Core (c++), but on the marvelous Mike Hearn’s BitcoinJ project (java), so everyone will be able to modify it more easily. I also plan to contribute back to BitcoinJ offering to merge added server code, such as sending and receiving address broadcasts and spam/dust prevention..
Bitslog 