Implementation of "Virtual Blockchain" (for faster boot up)

[muneeb-ali]

I've been thinking about speeding up initial indexing / boot up of blockstore (see Issue #69 #82 etc).

The main problem seems to be that:

a) We need txindex=1 for bitcoind which is something that most normal users don't do and significantly increases the system requirements for running a bitcoind node

b) Assuming you're not running your own bitcoind and are connecting to a remote bitcoind (like the one at btcd.onename.com) the sheer amount of remote RPC calls (for getting blocks and all transactions in blocks) will slow this down

We've discussed the concept of a "Virtual Blockchain" in our docs, but in the current implementation we don't really explicitly store anything resembling a virtual blockchain. I propose a solution where:

-- Each blockstored node stores the virtual blockchain (block number + transaction IDs which are relevant to blockstore). Let's assume that bitcoin_block 343883 is virtual_block 1 and any transactions in bicoin_block 343883 that has a valid OP_RETURN for blockstore can stored in virtual_block 1 (we only need to store the transaction ID). Let's say that in bitcoin_block 343889 there was another valid blockstore transaction, now bitcoind_block 343889 is stored as virtual_block 2 and so on.

-- Every LIVE blockstored node has the latest copy of virtual_blocks (just like every bitcoind node has a list/copy of bitcoin blocks).

-- When a new blockstored node boots up, it connects to peer blockstored nodes (through a discovery process) and fetches the "virtual blockchain". After getting the virtual blockchain (from multiple sources) the new node then talks to a bitcoind node to get the actual blocks and transactions. The virtual blockchain effectively acts as a filter for "only get these blocks and transactions, forget about processing all the other blocks/transactions".

-- The new blockstored node, calculates the namespace and the hash of the Merkle tree root independently after processing the blocks/transactions and checks if their view of the namespace is consistent with others (similar to how we're detecting if you're on a fork or not).

-- This significantly reduces the no. of blocks/transactions that new nodes will need to process to catch up to the rest of the network while maintaining the security properties.

-- Once a blockstore node has synced up with the rest of the network, it only needs to look at the new incoming bitcoin blocks and can update it's own virtual blockchain without any assistance from other peer blockstored nodes.

Thoughts?

[jcnelson]

It's not clear to me that this is just as secure. If a blockstored node starts up and begins auditing the virtual blocks only, doesn't it implicitly trust that the majority of the peer blockstored nodes are honest? This is dangerous if so, since there are way fewer blockstored nodes than cryptocurrency nodes--it's much easier to "51%-attack" them.

I think that no matter how you slice it, the new blockstored node will need to cross-validate virtual blocks against the cryptocurrency blockchain before processing any requests if it wants the same level of tamper-resistance assurance. And to do so, it will either needed to audit the cryptocurrency itself, or verify with a trusted auditor. Moreover, the virtual blockchain still grows linearly, so in the long run, it's not clear that this strategy alone will be a worthwhile time-saver (maybe it cuts the time down from weeks to days, but that's still too long).

Can we tweak the rules of the virtual blockchain to cut down on the amount of verification that needs to happen? One idea I had was to implement a "genesis-checkpoint" virtual block, which can serve as the first block for a new blockstored peer to fetch but is guaranteed by the protocol to get added at most once every K virtual blocks written (for some constant K). Then, a new blockstored node only needs to fetch the last genesis-checkpoint block and validate all blocks since then, and bootstrapping becomes an O(1) operation.

The problem the peer has then is then determining which is the last valid genesis-checkpoint. What if we could make generating one so hard that a single genesis-checkpoint could only have been created e.g. once a day even if the whole cryptocurrency's mining peers worked at it? We might do so by requiring it to include the crypto-puzzle solutions found in the past N blocks of the cryptocurrency blockchain, for example, and adapt our value of N over the course of days or weeks in response to the cryptocurrency's hashing power. This would prove to the new blockstored node that the genesis-checkpoint (1) was the most recent, and (2) is likely correct, since it would be way too much work for malicious blockstored nodes to spoof. We'd timestamp genesis-checkpoints, so the blockstored node would assume that any one of them older than e.g. 2 days is not the latest, and we'd pick N so that it's not feasible for a malicious minority of blockstored nodes to generate a valid but wrong genesis-checkpoint.

The bootstrapping process then becomes:

1. Get the last genesis-checkpoint block
2. Verify the cryptocurrency blocks AND the virtual blockchain blocks created since the genesis-checkpoint block
3. Start servicing requests

Thoughts?

[muneeb-ali]

I definitely see your point about no. of blockstored nodes being less than bitcoind nodes. My thinking was that, if we require hash of the root of Merkle tree announced with our nameops then the new node gets the hash from lastest name ops that it has seen on the blockchain and then when it gets the "virtual chain" from the peers it can verify that the "virtual chain" is correct by comparing to the Merkle tree hash. You don't need to trust the peers. Even just getting the virtual-chain for a single peer is enough (because you're explicitly validating it). There is a forking issue here, say a partition on the network thinks the namespace is in state A and another partition thinks it's in state B. A new incoming node, will see two different root hashes and will need to "pick" which fork to become a part of. This is a more general problem that we need to solve anyway.

And yes @shea256 and I have discussed periodic check-points idea before, but we haven't discussed it in too much detail. If I remember correctly, in the last discussion we were talking about who gets to write the check-point and how do we determine what's a valid check-point. I like your idea of making it a function of bicoin difficulty, but I need to think more about it.

Also, isn't the Merkle tree hash (from what I described earlier) working kind of like a check-point anyway?

[metacoin]

Let:

n = number of honest blockstored nodes
m = n+1
// "honesty" in this case means their merkle trees actually reflect what is in the block chain

What happens when there are m or more dishonest nodes connected to the network, and new blockstored nodes come online? According to your proposal, new blockstored nodes check with the other live nodes to see if they agree, but in this case there are disagreements everywhere.

How does a newcomer to the network determine which nodes to trust?

Edit: a checkpoint is a centralized idea, published by the developers (who usually control the repo) and adopted by consensus. Essentially, you could have a centralized checkpoint within your code that thwarts attackers up to the last checkpointed virtual block.

[jcnelson]

@muneeb-ali Ah, I see. If you get the latest Merkle root hash, you can verify the integrity of the virtual blockchain. The remaining problems are getting the latest Merkle root hash, and keeping the virtual blockchain short enough to download quickly.

The genesis-checkpoint concept could also solve the Merkle root discovery problem, wouldn't it? If we embed the Merkle root hash in a genesis-checkpoint block, it should be possible to point new peers towards the current genesis-checkpoint block without worrying about adversaries racing ahead and publishing an alternative (i.e. if the adversary has enough computing power to generate an alternative genesis-checkpoint block in a reasonable amount of time, they should have enough to 51%-attack the blockchain anyway). If there are two or more conflicting genesis-checkpoint blocks, the blockstored peer selects the one that was harder to generate--that is, the one that required the most hashing power.

[metacoin]

imo,

• let users specify a trusted web endpoint or a node to connect to to get the latest merkle root hash
• their node searches for other nodes broadcasting the same merkle root hash on the network
• they only download virtual blocks from nodes matching the trusted source

checkpoints are only valid in a trusted context. the checkpoint could be a broadcast from a trusted node, source code found in the blockstore github, or published in the most recent block by a trusted source. to make the process more automated, it would be advantageous to allow nodes to subscribe to trusted peers who constantly announce their highest merkle root hash. you could even hard-code a trusted node in the software, that's essentially what every coin dev who publishes a checkpoints.cpp is doing.

at this point you'd have three "classes" of nodes:

• trusted nodes (whom other users have added to their trusted peers list)
• virtual block seeds (people who allow others to download the virtual block chain)
• everyone else (those who seed and transmit nothing, only get data from the network)

[jcnelson]

In the mean time, we now have branch 'parallel-startup' which should shorten the initial bootstrapping time, especially if you're using our bitcoind fleet instead of a local bitcoind peer.

[jcnelson]

We have implemented virtualchain to separate Blockstore from the blockchain-crawling logic, and virtualchain itself is already somewhat fast--it crawls many blocks in parallel, using multiple processes.

Marking this issue as resolved. Please re-open it if it is still a problem. Thanks!

[blockstack-devops]

This issue has been automatically locked since there has not been any recent activity after it was closed. Please open a new issue for related bugs.