Page 31 - MSDN Magazine, March 2018

Digital Asset Owner 0
DATA
Sig0
Transaction 1
DATA
Susan’s Digital Asset
Transaction 2
DATA
Transaction 3
DATA
an agent to process his digital-asset transfer request, and he must trust the server that persists the hash structure. Without a central node to process a new transaction or a central authority to delegate them for processing, any node could process Bill’s pending transaction. A rogue or dominant node having superior processing power could allow invalid or fraudulent transactions to occur and those could propagate to honest nodes. To solve that, the net- work could try to randomly assign a node to process Bill’s transaction, but that again centralizes control and requires trust that the random number generator is indeed enforc- ing randomness. To eliminate this issue, blockchains use consensus algorithms, described next.
Sig1
Sig2
Bill’s Digital Asset
Figure 7 The Transaction Hash Chain Uses Digital Signatures to Transfer Ownership of a Digital Asset; Each Transaction Record Maintains a Cryptographic Backlink to the Previous Transaction on the Hash Chain
The Merkle binary hash tree structure offers some advantages. For example, it makes it easy to update data within a transaction and compute a new Merkle root hash without having to build the entire Merkle tree from scratch. For example, if Transaction E changes (it’s highlighted in Figure 8), all you need to do is walk the tree efficiently back to the Merkle root, computing new hashes once for each level. Thus, you first compute the new Leaf hash HE; then compute HEF from HE and HF; then compute HEFGH from HEF and HGH; then compute a new Merkle root hash from HABCD and HEFGH. Updating the Merkle root hash required only four computa- tions versus the 15 required to build the Merkle tree from scratch!
Building a Blockchain
To build a blockchain (see Figure 9), the binary hash chain data object containing transactions must somehow be committed to a tamper-proof data store that everyone can use (remember, this is a public blockchain—any node on the network can read from or write to it). The Merkle tree structure contains transactions and is tamper-proof, so it would seem it could serve as the blockchain. But there are several problems. In order for Bill to send his digital asset to Susan, Bill must trust the service or Web site that acts as
Consensus Algorithms Blockchain technologies avoid centralized data store and trust-authority issues by honoring a pro- tocol that dictates how blocks are added and maintained. They do so by enforcing a blockchain-building consensus algorithm. There are different kinds of consensus algorithms—I’ll discuss how the proof-of-work (PoW) algorithm works.
PoW is based on the idea that a node on the network needs to prove its honorable intentions by incurring a cost and consuming the time required to solve a computationally challenging prob- lem. To induce a node to participate in such a system and play by its rules, the network offers an incentive—often money—that is, node operators get paid when they add a block to the blockchain. To earn that money, nodes must validate all transactions (to ensure that they meet a blockchain’s specific rules) and then solve a cryptographic puzzle.
Earlier, I mentioned that a central authority could randomly assign a node to process a batch of new transactions. That approach would require a central random-number generator, which could be flawed, hacked or disabled. However, giving nodes a difficult puzzle to solve yields the desired effect: The node that will first solve the puz- zle can’t be determined in advance, making for a sort of node-lottery on the network. No central authority is needed—and that’s one of
Merkle Root HABCDEFGH H(HABCD + HEFGH)
HABCD H(HAB + HCD)
HEFGH H(HEF + HGH)
HAB H(HA + HB)
HCD H(HC + HD)
HEF H(HE + HF)
HGH H(HG + HH)
Leaf A HA
Leaf B HB
Leaf C HC
Leaf D HD
Leaf E HE
Leaf F HF
Leaf G HG
Leaf H HH
Transaction A Transaction B Transaction C Transaction D
Transaction E Transaction F Transaction G Transaction H
Figure 8 A Merkle Tree is a Type of Binary Hash Tree That Produces a Merkle Root Hash; This Data Structure Can Efficiently Add Leaf Nodes and Calculate a New Merkle Root Without Requiring Full Re-Computation
msdnmagazine.com March 2018 25