# Does a blockchain need a distributed hash table?

In this question on StackOverflow, the OP is asking if there is a difference between distributed hash tables and blockchain. The answer to that question seems to indicate that there is no point of overlap between the two as they are for completely different purposes. However, I would like to clarify this point.

To the best of my knowledge, blockchain is a peer-to-peer implementation, which means that the entire blockchain is stored in every peer. However, if there is a need to broadcast consensus of a particular transaction, there is still a need to look up the other peers in some kind of table of addresses. Am I correct? (My underlying question is: In a blockchain, would all nodes or peers get the information about successful transactions simultaneously? It doesn't seem likely to me, and I'm trying to understand the protocol for doing this broadcast in a simultaneous, or near simultaneous manner).

No. Peer discovery does not use a distributed hash table and cannot use a DHT. Once you are connected to the network, there is no need for you to find more peers to connect to (and most nodes have a limit of 8 anyways as that is Core's outbound connection limit).

The broadcasting of transactions and blocks themselves does not rely on the broadcaster to find all peers and send the data to each peer. Rather it simply sends the transaction or block to the peers it is connected to, and then those peers check the block and transaction, and if it is valid, they will send the block or transaction to their peers, and so on and so forth.

• Sorry, I wasn't referring to "peer discovery". What I meant was "broadcasting consensus of transactions to other peers". I believe that the broadcast would have to go out from one peer to the second, and then to connections of that second peer, and so on. This seems to require some kind of table of addresses of peers. I will clarify this in my question. – Joebevo Jul 10 '17 at 6:10
• I have edited my answer to address transaction and block relay – Andrew Chow Jul 10 '17 at 6:14

A blockchain needs a distributed hash table like a fish needs a bicycle.

The standard distributed hash table constructions achieve little to no particular robustness to attack for any actually useful definition of security, as a result they are not particularly useful for our applications. Really, DHT just became a buzzword for "distributed" used most frequently by people who know only enough to be dangerous... until "blockchain" became a more popular buzzword for distributed.

What systems like Bitcoin do is distribute all the data to everyone. There is no need to look up routes or destinations, the system is a great big broadcast. When a transaction comes in to a node, it offers it to each of its peers and if they don't already have it they'll request it.

It would be possible to do some other things-- though not generally the things in existent DHT systems because they don't generally achieve useful strong security properties-- but since validation in the Bitcoin style design requires everyone sees all the data it isn't particularly useful to avoid broadcasting it to all of them because they'll eventually need to see it all.

Bitcoin nodes still need a "seed" ip to connect to the first time. A few backup ips are hardcoded into the bitcoin core software in case you don't know any yourself. From then, the node will get and maintain a list of working peers. The magic of the bitcoin protocol was to be trully decentralized. Meaning there is no central point of failure, not even a distributed common list.

But... How to achieve consensus in such situation would you ask ? With the "proof of work". (for Bitcoin, but other cryptos are experiencing other things)

To push a bloc of transactions on-chain and be rewarded, a miner needs to first check the said transactions, and then be the first one to find a valid answer to an equation involving the block, solvable only by brute-forcing it but easy to check (more on that later). Once done, it spreads the block and the associated solution to his peers, that will stop trying to "solve", re-check the bloc you gave them and add it in order to start trying solving the next one. The difficulty of the problem is (slowly) auto-adjusting to have a bloc every 10 minutes, no matter the power of the network. The resulting difficulty level is a snapshot of the power of the network at work on the chain.

When 2 nodes are peering, they "handshake" each other, they basically tell one another "I'm at bloc number 456, my last block has this fingerprint". If they disagree, the "longest chain" wins. But it's not really about size, longest means power speaking. Knowing the "difficulty level" of each block, you can do the math and know how much computational power was behind this version so far. If it happens that the other node as a more followed truth, you start retrieving his blocks, one by one, from where you disagree, and you check them one by one, transaction by transaction, while checking that every proof of work is a valid one. At the end, you have another truth, but as you checked everything yourself and there is more PoW, you know it's a better truth. It's why it's better to wait a few blocs before saying that a transaction is unalterable, time for the consensus to take place, time for a "longest chain" to take over.

But this is really theoretical, as with the current hashrate and level of interconnection between nodes, a "longest chain fight" as infinitesimal chances to last more than 2 blocks. The miner is allowed by the protocol to add one transaction to the block, his reward, from thin air. So if his block achieves consensus, he will be paid. Otherwise, it will have never happened.

This is how bitcoin achieve consensus. You can't mine blocs with invalid transactions, as every node re-checks them, and as every node will check it too, you must have a valid proof of work. Then, if you want to delete a transaction from a bloc, it will change the equation to solve, so you need to find a new solution for this bloc, and if you want to win the longest chain war (as this bloc was already mined), you need to be the first one to close the next block.

So, to be able to change the chain, you need to be "in average" faster that the rest of the network to compute proofs, and raise your own version of the chain aside until you succeed in making it bigger, PoW speaking, than the main one. The famous 51% problem.

Strategy Network Consensus Storage Clock-free
Bitcoin [1] Broadcast PoW Full Yes
BitCoin-NG [11] Broadcast PoW Full No
NEM [12] Broadcast PoS Full No
Snow White [13] Broadcast PoS Full Yes
Ouroboros [14] Broadcast PoS Full No
PPCoin [15] Broadcast PoW-PoS Full No
PoA-Bitcoin [16] Broadcast PoW-PoS Full Yes
NEO [17] Broadcast dBFT Full No
Ontology [18] Broadcast VBFT Full Yes
Elastico [19] Broadcast BFT Full No
Ripple [48] Broadcast BFT Full No
Tendermint [49] Gossiping BFT Full No
Hyperledger[27, 28] Gossiping BFT Full No
Omniledger [20] Gossiping BFT Full No
Avalanche [21] Gossiping Snowflake Full No
Skipchain [22] Gossiping BFT Full Yes
PeerCesus [23] Flooding PoW-PoS Full No
Rollerchain [24] Flooding PoW Distributed Yes
Trustchain [25] Gossiping PoW Distributed No
Rapidchain [26] Gossiping BFT Distributed No
BigChainDB [5] Broadcast Paxos Distributed No
LightChain DHT PoV Distributed Yes