# Byzantine Generals Problem & Merkle Trees

## It's Game Theory
Game theory is the formal study of how actors, given a set of rules and incentives, will behave based on those rules and incentives. It assumes at least some (but not all) actors within the system will employ strategies that will maximize their gain, even if it means breaking the rules if possible. This is a great way to model the real world when you're building a system, because in the real world those actors do exist.

The Byzantine Generals Problem is a game theory problem, which describes the difficulty decentralized parties have in arriving at consensus without relying on a trusted central party. In a network where no member can verify the identity of other members, how can members collectively agree on a certain truth?

The problem arises from the incentive to lie- the gain of which would be to execute transactions one did not first authorize.

## Merkle Trees
Merkle Trees are about more than just Bitcoin- for example when we talked about GPS satellites, we talked about [data degradation](https://en.wikipedia.org/wiki/Data_degradation). Merkle trees can be used to validate that data has integrity against interference from solar radiation, or unshielded cables that are subject to random interference from specialized equipment, like you might find in a hospital. These were the main first uses of Merkle Trees.

#### Merkle Trees Used In Not-Cryptocurrency

* [Git uses Merkle Trees, that's what commit hashes are.](https://initialcommit.com/blog/git-bitcoin-merkle-tree#:~:text=A%20Merkle%20tree%20is%20a,point%20to%20other%20Merkle%20trees.) (also mercurial)
* [Google wave](https://en.wikipedia.org/wiki/Google_Wave#Apache_Wave) used it in their protocol to validate changes between documents (our own Pamela Fox worked on this!)
* [B Tree File System](https://en.wikipedia.org/wiki/Btrfs)
* [Zettabyte File System](https://en.wikipedia.org/wiki/ZFS)
* [Cassandra, Riak, and Dynamo Storage use them](https://hackmd.io/ovPb7L_uTm-Z1uD0W_T1mw)
* [It's how Certificate Transparency works](https://en.wikipedia.org/wiki/Certificate_Transparency) (eg, [signed packages](https://en.wikipedia.org/wiki/Nix_(package_manager)) from app stores, or **https**, yes you heard that right, the protocol _**https**_ runs off a merkle tree)

and it's _also_ how the proof-of-work algorithm behind Bitcoin and Ethereum works.

## Hash Trees

[Here's a great post implementing a Merkle Tree in Python](https://trebaud.github.io/posts/merkle-tree/). After I read it I deleted mine, this one is much clearer. [I found another post](https://gruyaume.medium.com/create-your-own-blockchain-using-python-merkle-tree-pt-2-f84478a30690) that uses this guy's code to implement a blockchain, so we'll look at the posts together. I copied the code they both came up with below just in case either link goes down.

from typing import List
import typing
import hashlib

class Node:
    def __init__(self, left, right, value: str,content)-> None:
        self.left: Node = left
        self.right: Node = right
        self.value = value
        self.content = content
    
    @staticmethod
    def hash(val: str)-> str:
        return hashlib.sha256(value.encode("utf-8")).hexdigest()
    def __str__(self):
        return(str(self.value))
    
class MerkleTree:
    def __init__(self, values: List[str])-> None:
        self.__buildTree(values)
    
    def __buildTree(self, values: List[str])-> None:
        
        leaves: List[Node] = [Node(None, None, Node.hash(e),e) for e in values]
        if len(leaves) % 2 ==1:
           leaves.append(leaves[-1:][0])# duplicate last elem if odd number of elements
           self.root: Node = self.__buildTreeRec(leaves)
    
    def __buildTreeRec(self, nodes: List[Node])-> Node:
         half: int = len(nodes) // 2
        
         if len(nodes) == 2:
             return Node(nodes[0], nodes[1], Node.hash(nodes[0].value + nodes[1].value), nodes[0].content+"+"+nodes[1].content)
         left: Node = self.__buildTreeRec(nodes[:half])
         right: Node = self.__buildTreeRec(nodes[half:])
         value: str = Node.hash(left.value + right.value)
         content: str = self.__buildTreeRec(nodes[:half]).content+"+"+self.__buildTreeRec(nodes[half:]).content
         return Node(left, right, value,content)
    def printTree(self)-> None:
        self.__printTreeRec(self.root)
    def __printTreeRec(self, node)-> None:
        if node != None:
           if node.left != None:
            print("Left: "+str(node.left))
            print("Right: "+str(node.right))
           else:
            print("Input")
   
           print("Value: "+str(node.value))
           print("Content: "+str(node.content))
           print("")
           self.__printTreeRec(node.left)
           self.__printTreeRec(node.right)
 
    def getRootHash(self)-> str:
         return self.root.value
        
def mixmerkletree()-> None:
    elems = ["Mix", "Merkle", "Tree","From","Onur Atakan ULUSOY","https://github.com/onuratakan/mixmerkletree","GO"]
    print("Inputs: ")    
    print(*elems, sep = " | ")
    print("")
    mtree = MerkleTree(elems)
    print("Root Hash: "+mtree.getRootHash()+"\n")
    print(mtree.printTree())
mixmerkletree()

For a blockchain, we make some adjustments from the next post.

from Crypto.Hash import SHA256


def calculate_hash(data: str) -> str:
    bytes_data = bytearray(data, "utf-8")
    h = SHA256.new()
    h.update(bytes_data)
    return h.hexdigest()

import math
def compute_tree_depth(number_of_leaves: int) -> int:
    return math.ceil(math.log2(number_of_leaves))

This next block will, given a set of transactions, return a merkle tree that satisfies that set of transactions (the root is a stable cryptographic hash of it's leaf nodes)

from utils import calculate_hash


def build_merkle_tree(node_data: [str]) -> Node:
    old_set_of_nodes = [Node(calculate_hash(data)) for data in node_data]
    tree_depth = compute_tree_depth(len(old_set_of_nodes))

    for i in range(0, tree_depth):
        num_nodes = 2**(tree_depth-i)
        new_set_of_nodes = []
        for j in range(0, num_nodes, 2):
            child_node_0 = old_set_of_nodes[j]
            child_node_1 = old_set_of_nodes[j+1]
            new_node = Node(
                value=calculate_hash(f"{child_node_0.value}{child_node_1.value}"),
                left_child=child_node_0,
                right_child=child_node_1
            )
            new_set_of_nodes.append(new_node)
        old_set_of_nodes = new_set_of_nodes
    return new_set_of_nodes[0]

# merkle_tree.py
import math

def is_power_of_2(number_of_leaves: int) -> bool:
    return math.log2(number_of_leaves).is_integer()

def fill_set(list_of_nodes):
    current_number_of_leaves = len(list_of_nodes)
    if is_power_of_2(current_number_of_leaves):
        return list_of_nodes
    total_number_of_leaves = 2**compute_tree_depth(current_number_of_leaves)
    if current_number_of_leaves % 2 == 0:
        for i in range(current_number_of_leaves, total_number_of_leaves, 2):
            list_of_nodes = list_of_nodes + [list_of_nodes[-2], list_of_nodes[-1]]
    else:
        for i in range(current_number_of_leaves, total_number_of_leaves):
            list_of_nodes.append(list_of_nodes[-1])
    return list_of_nodes

- [The post I got these from actually will walk you through building a blockchain in Python](https://gruyaume.medium.com/create-your-own-blockchain-using-python-merkle-tree-pt-2-f84478a30690), it's a walkthrough in 10 parts!
- [Another coin (NaieveCoin)](https://lhartikk.github.io/)

## Other Consensus Algorithms

[The Lockstep Protocol](https://en.wikipedia.org/wiki/Lockstep_protocol) has been used in online multiplayer games to limit a form of [cheating called Look-Ahead cheating.](https://en.wikipedia.org/wiki/Cheating_in_online_games#Look-ahead)

[Paxos](https://en.wikipedia.org/wiki/Paxos_(computer_science)) is a protocol that covers a series of algorithms that are used to determine the validity of a message. It involves "voting", but it also requires a leader be elected, and is thus not a "trustless" or entirely decentralized system of message validation.

Largely, [Paxos is used in production in replication of data](https://en.wikipedia.org/wiki/Paxos_(computer_science)#Production_use_of_Paxos), in datastores where writes are slow and may conflict, in order to resolve distributed transaction conflicts. This comes in handy when a node has old data, is in a failure state, and continues to transmit that old data while not accepting new data. It also comes in handy when a hacker tries to overwrite data by compromising a single node in the system.