<p>The blockchain is either a tree structure (with each block just referencing its parent), or a single path through this tree (a singly linked list).</p>

<p>Internally in software (at least in the reference implementation), indexes exist of course to find blocks (by height, and by hash).</p>

<p>Technically however, there is no indexing of transactions at all. They're not necessary for validation. Instead, a database is maintained with just the <strong>outputs</strong> of transactions that <strong>have not been spent yet</strong> (which is indexed by transaction hash and nothing more). Every block that is validated updates this database: its new outputs are added, the outputs consumed by it are removed. This database is tiny, compared to the blockchain (400MB vs 16GB as of march 2014).</p>

<p>In fact, earlier blocks themselves are not used during validation at all. We only need them for serving them to other nodes that are starting up - otherwise they would have no way to know the current state in a zero-trust manner.</p>

<p>This last point is important for Bitcoin's security model: full nodes never trust data they have not validated themselves. This is why we can't just copy the database of unspent outputs from someone and forgetting about the blocks before that point.</p>

<p>Regarding separation of data across nodes: such mechanisms typically have very bad DoS properties, where knocking out a few network nodes can mean that some data becomes inaccessible.</p>

<p>For just blocks, it is certainly possible to not have every node store and serve every block ever (and this will likely be implemented somewhere in the future). Again, all they are needed for is bootstrapping a new node.</p>

<p>The database of unspent outputs can also be sharded, namely by only retaining outputs of transactions within a certain range of hashes. However, this still requires each node to validate each block, and the result is technucally not a full node. You would need a set of nodes, that together validate the full range of hashes, to be sure blocks are fully valid.</p>

CC BY-SA 3.0
2014-03-07T12:57:52.880Z
Is there any documentation about the exact organisation of the different Berkeley database files?
Jori
CC BY-SA 3.0
2014-03-07T13:44:58.833Z
Thanks for your help. I ask the second question because the bitcoin system use some mechanisms to make all the miners share the same block chain. I'm new to this field and it seems that [ZooKeeper](http://zookeeper.apache.org/doc/trunk/zookeeperOver.html) and [Paxos](http://en.wikipedia.org/wiki/Paxos_(computer_science)) are used for solving consensus and coordination problem in the distributed application, and I am curious about how does bitcoin system solve that problem :)
Ting
CC BY-SA 3.0
2014-03-07T18:12:37.687Z
@Jori: perhaps http://bitcoin.stackexchange.com/questions/11104/what-is-the-database-for answers that partially. Berkeley DB is only used for the wallet still - the rest is custom formats or LevelDB.
Pieter Wuille
CC BY-SA 3.0
2014-03-07T09:09:30.037Z
2014-03-07T12:20:34.623Z
2014-03-07T12:20:34.623Z
Pieter Wuille
<p>The blockchain looks like a double linked list, and all the transactions are stored into each block. What kind of algorithm does bitcoin use to find a specific transaction efficiently, since the blockchain is growing bigger and bigger?</p>

<p>The bitcoin network use its compute power to keep data consistency, if we simplify this model(write once read many, no update, no cheat) and use its consistency policy into the geographically distributed file system, does that work?</p>

<blockchain><protocol><algorithms>
Bitcoin blockchain search algorithm and consistency policy
Ting
# Bitcoin blockchain search algorithm and consistency policy

(Asked by: username_0 on 2014-03-07)

The blockchain looks like a double linked list, and all the transactions are stored into each block. What kind of algorithm does bitcoin use to find a specific transaction efficiently, since the blockchain is growing bigger and bigger?

The bitcoin network use its compute power to keep data consistency, if we simplify this model(write once read many, no update, no cheat) and use its consistency policy into the geographically distributed file system, does that work?

**Tags:** blockchain, protocol, algorithms


---

## 1 answers

### Answer by username_1 on 2014-03-07. Score: 3

The blockchain is either a tree structure (with each block just referencing its parent), or a single path through this tree (a singly linked list).

Internally in software (at least in the reference implementation), indexes exist of course to find blocks (by height, and by hash).

Technically however, there is no indexing of transactions at all. They're not necessary for validation. Instead, a database is maintained with just the **outputs** of transactions that **have not been spent yet** (which is indexed by transaction hash and nothing more). Every block that is validated updates this database: its new outputs are added, the outputs consumed by it are removed. This database is tiny, compared to the blockchain (400MB vs 16GB as of march 2014).

In fact, earlier blocks themselves are not used during validation at all. We only need them for serving them to other nodes that are starting up - otherwise they would have no way to know the current state in a zero-trust manner.

This last point is important for Bitcoin's security model: full nodes never trust data they have not validated themselves. This is why we can't just copy the database of unspent outputs from someone and forgetting about the blocks before that point.

Regarding separation of data across nodes: such mechanisms typically have very bad DoS properties, where knocking out a few network nodes can mean that some data becomes inaccessible.

For just blocks, it is certainly possible to not have every node store and serve every block ever (and this will likely be implemented somewhere in the future). Again, all they are needed for is bootstrapping a new node.

The database of unspent outputs can also be sharded, namely by only retaining outputs of transactions within a certain range of hashes. However, this still requires each node to validate each block, and the result is technucally not a full node. You would need a set of nodes, that together validate the full range of hashes, to be sure blocks are fully valid.

> **Comments:**
> **username_2**: Is there any documentation about the exact organisation of the different Berkeley database files?  
> **username_0**: Thanks for your help. I ask the second question because the bitcoin system use some mechanisms to make all the miners share the same block chain. I'm new to this field and it seems that [ZooKeeper](http://zookeeper.apache.org/doc/trunk/zookeeperOver.html) and [Paxos](http://en.wikipedia.org/wiki/Paxos_(computer_science)) are used for solving consensus and coordination problem in the distributed application, and I am curious about how does bitcoin system solve that problem :)  
> **username_1**: @username_2: perhaps http://bitcoin.stackexchange.com/questions/11104/what-is-the-database-for answers that partially. Berkeley DB is only used for the wallet still - the rest is custom formats or LevelDB.  

---

