amiller/redblackmerkle

An authenticated data structure based on a red-black tree.

Red-Black Merkle Tree

This is a reference implementation of a Self-Balancing Merkle Search Tree (i.e., an Authenticated Data Structure [0]). This can be used to efficiently represent the essential state necessary to validate Bitcoin [1] transactions: the set of available unspent transaction outputs (UTXOs).

Authenticated Data Structures are used in protocols between three parties: 1) the trusted Source, which creates data and publishes a digest; 2) the untrusted Server, which maintains a copy of the data and responds to queries; and 3) the Client, which verifies the Server's responses against the known digest. In this implementation, the data structure requires O(N) storage and each operation takes O(log N) time. These operations can also be verified in worst-case O(log N) time using a Verification Object (a path through a Merkle tree). A verifying Client is only required to maintain O(1) state (specifically, the Merkle tree root hash).

• redblack.py: RedBlack is a general purpose Red-Black binary search tree [3] that can easily be augmented with a 'digest' function. Typically, the digest should include a secure hash function, forming a dynamic Merkle tree [4].

• utxo_merkle.py: a specialization of RedBlack by definining a digest/serialization protocol appropriate for Bitcoin UTXOs.

• merkle_scan.py: a script that iterates through the Bitcoin blockchain, from the genesis block to the head, incrementally updating the RedBlack as it goes (requires Gavin Andresen's python bitcointools.

• treedot: produces graphviz illustrations of the tree (requires graphviz (dot))

• test_redblack: unit tests for RedBlack

Illustrations

• Authenticated insertion/balancing in a red-black merkle tree http://imgur.com/a/KNeq5#0

• Teaser Image

[0] Authenticated Data Structures. Roberto Tamassia. 2003
[2] http://bitcoin.org/bitcoin.pdf
[3] http://www.eecs.usma.edu/webs/people/okasaki/jfp99.ps
[4] http://cs.brown.edu/people/aris/pubs/pad.pdf

Licensing

This software is released under the CRAPL license (appropriate for scientific use) and the AGPL license (appropriate for copyleft open source projects). If you would like a different or more permissive license, please contact me!

redblackmerkle's Issues

License?

Please add a license to this project so others can reuse your code.

MerkleRedBlack trees are not set-unique

The digests of MerkelRedBlack trees depend on the order in which elements are inserted. Specifically, if you remove some elements and add them back in the reverse of the order you removed them in (i.e. remove a, remove b, add b, add a), the digest will change.

This is problematic for representing the set of unspent outputs in the Bitcoin blockchain, because that set will often be updated with some new blocks (often just one), and then re-wound by backing out the changes from those blocks in order to go down a different, longer fork that shows up later. The root hash for your MerkleRedBlack tree at the end of the longer fork will depend on whether you saw the short fork first and had to back it out later, or whether you saw the long fork first and never removed and re-added the inputs of the transactions in the short fork.

Code to demonstrate this behavior (in the context of demo_redblack.py):

def demo_setunique():
    """
    Show that our trees are not set-unique. Instead, they have differing digests
    depending on insert order. This causes problems specifically for the case
    where we remove some nodes in a certain order (say, the order in which
    unspent outputs were spent in Bitcoin), but we then need to rewind to a
    previous state by re-adding the removed nodes in reverse-chronological order
    (say, because we need a previous state to validate a new incoming block
    that's part of a longer fork than the fork we were previously using).

    """

    import random

    # What should we insert?
    items = range(100)

    for i in xrange(10):
        # Shuffle the items
        random.shuffle(items)

        # Get the object that we use to operate on trees. Say we want Merkle
        # trees.
        RB = MerkleRedBlack()

        # Start with the empty tree
        D = RB.E
        for i in items:
            # Insert every item
            D = RB.insert(i, D)

        # The digest is the first element of the tree.
        print "Before replacing nodes: {}".format(D[0])

        # Remove and re-insert a sub-sequence of items
        to_replace = items[0:10]
        random.shuffle(to_replace)

        for i in to_replace:
            # Remove all the nodes we want to replace
            D = RB.delete(i, D)

        to_replace.reverse()

        for i in to_replace:
            # Add all the nodes back in reverse order. We want to be in the
            # state we were in before.
            D = RB.insert(i, D)

        print "After replacing nodes (we want it to be the same): {}".format(
            D[0])

I don't really know how to solve this problem. Can red-black trees be made set-unique? You could switch to treaps as in http://tamperevident.cs.rice.edu/papers/paper-pad.pdf, but those seem like they could be exploited by people generating transactions that come out to hashes that give a bad set of priorities.