<commit_before>"""
<NAME> <<EMAIL>>
May 2012

This RedBlack tree is an Authenticated Set [1], based on a balanced
binary search tree. The tree is strictly balanced, so that all usual
operations can be performed in O(log N) worst-case time. The tree is augmented
with secure hashes for each node, forming a Merkle tree. This allows each 
operation to be 'replayed' by a Verifier using only O(log N) data. Only O(1) of
'trusted' state (the Merkle tree root hash) must be maintained by the Verifier.

Additionally, this tree supports selection of an element by its rank, which is
especially useful in choosing elements at random for a Proof-of-Throughput.

This implementation uses a combination of Okasaki style balancing for 
insert [2] and Kazu Yamamato's version of delete [3,4,5].


[1] Persistent Authenticated Dictionaries and Their Applications
    Agnostopolous, Goodrich, and Tamassia.
    http://cs.brown.edu/people/aris/pubs/pad.pdf

[2] Purely Functional Data Structures
    <NAME>
    http://www.eecs.usma.edu/webs/people/okasaki/jfp99.ps

[3] Missing method: How to delete from Okasaki's red-black trees
    M<NAME>
    http://matt.might.net/articles/red-black-delete/

[4] Efficient Verified Red-Black Trees
    <NAME>
    http://www.cs.princeton.edu/~appel/papers/redblack.pdf

[5] Purely Functional Left-Leaning Red-Black Trees
    <NAME>
    http://www.mew.org/~kazu/proj/red-black-tree/


Type definitions and common notations:
======================================

RedBlack():
    A RedBlack tree that can be augmented with a 'digest' field, which is
    assumed to contain at least a collision-resistant hash function. The
    digests for the subtrees are stored along with each node. The digests
    are recomputed as necessary during insert and delete in order to maintain
    consistency.

 ** Note that RedBlack objects simply define functions, the actual data 
    structure D is just a tuple, as described below

D:
    A Node in the tree, especially the root. Of the form:
        (Color, Left, (Element, LeftDigest, RightDigest), Right) = D

    - Typically abbreviated
        (c, L, (k, dL, dR), R) = D

    - c in ('R', 'B'): red and black labels for balancing
        L, R: the children, also Nodes,
        dL, dR: digests of the children
        k: each non-leaf's value is equal to the largest leaf value in the left
           sub-tree

    - () represents the empty tree.
    - dO == digest(()) is the empty-digest

    - The following operations are defined as you'd expect:

        D = insert(q, D)   # unless q is already in the set
        D = delete(q, D)   # unless the set does not contain q
        v = search(q, D)   # Returns the smallest element >= q, unless q is the
                           # largest element in the tree

VO:
    Each of the tree operations is defined in terms of a stateful 'Traversal'
    object, which runs in one of two modes:

    Record: 
        The data for every node visited during subsequent operations on T
        is appended to a Verification Object (VO).

        T = record(D)
        d0 = T.insert(q)
        VO = T.VO

    Replay: 
        A VO created from a recording can be replayed, simulating the
        operation on the full tree.

        T = replay(d0, VO)
        d0 = T.insert(q)

 ** Security Claim **

    If an operation on a Replay traversal returns a value, then it is the same
    value that would be returned by the operation on the original tree.

    Proof sketch:
       At each step during a traversal, the digest for each node is known
       before the node's data is accessed. During a Replay, the digest is
       is recomputed and verified.

 ** Bounded Cost-of-Verification Claim **

    The tree is balanced such that the longest possible path from the root to
    a leaf is 2 log N. The worst-case bounds for all operations are given
    below:
          delete: 4 + 3 log N
          insert: 2 log N
          search: 2 log N

    TODO: I think these are wrong! How to construct the worst case?
"""

import math
import itertools

class RedBlack(object):
    def __init__(self, H=hash):
        """
        Args:
             H (optional): a collision-resistant hash function that
                           takes arguments of the form:
                  H(())
                  H((c, dL, k, dR))
        """
        self.H = H
        self.dO = self.digest(())

    def digest(self, D):
        if not D: return self.H(())
        (c, _, (k, dL, dR), _) = D
        return self.H((c, dL, k, dR))

    def record(self, D):
        return RecordTraversal(self.H, D)

    def replay(self, d0, VO):
        return ReplayTraversal(self.H, d0, VO)

    def search(self, q, D):
        T = self.record(D)
        return T.search(q)

    def insert(self, q, D, v=''):
        T = self.record(D)
        return T.reconstruct(T.insert(q, v))

    def delete(self, q, D):
        T = self.record(D)
        return T.reconstruct(T.delete(q))


class Traversal(object):
    def __init__(self, H, d0):
        self.H = H
        self.cache = {}
        self.dO = H(())
        self.d0 = d0

        R,B,a,b,c,d,x,y,z = 'RBabcdxyz'
        self.bL1 = (B,(R,(R,a,x,b),y,c),z,d), (R,(B,a,x,b),y,(B,c,z,d))
        self.bL2 = (B,(R,a,x,(R,b,y,c)),z,d), (R,(B,a,x,b),y,(B,c,z,d))
        self.bR1 = (B,a,x,(R,(R,b,y,c),z,d)), (R,(B,a,x,b),y,(B,c,z,d))
        self.bR2 = (B,a,x,(R,b,y,(R,c,z,d))), (R,(B,a,x,b),y,(B,c,z,d))

    def balanceL(self, c, dL, k, dR):
        d = self.store(c, dL, k, dR)
        return self.match(self.bL1, d) or self.match(self.bL2, d) or d

    def balanceR(self, c, dL, k, dR):
        d = self.store(c, dL, k, dR)
        return self.match(self.bR1, d) or self.match(self.bR2, d) or d

    def unbalancedL(self, c, dL, k, dR):
        get = self.get
        store = self.store
        balanceL = self.balanceL
        red = lambda (_,dL,x,dR): ('R',dL,x,dR)
        (_c, _dL, _k, _dR) = get(dL)
        if _c == 'B': return balanceL('B',store('R',_dL,_k,_dR),k,dR), c=='B'
        _R = get(_dR)
        assert c == 'B' and _c == 'R' and _R[0] == 'B'
        return store('B',_dL,_k,balanceL('B',store(*red(_R)),k,dR)), False

    def unbalancedR(self, c, dL, k, dR):
        get = self.get<commit_msg>Added note about missing optimization<commit_after>"""
<NAME> <<EMAIL>>
May 2012

This RedBlack tree is an Authenticated Set [1], based on a balanced
binary search tree. The tree is strictly balanced, so that all usual
operations can be performed in O(log N) worst-case time. The tree is augmented
with secure hashes for each node, forming a Merkle tree. This allows each 
operation to be 'replayed' by a Verifier using only O(log N) data. Only O(1) of
'trusted' state (the Merkle tree root hash) must be maintained by the Verifier.

Additionally, this tree supports selection of an element by its rank, which is
especially useful in choosing elements at random for a Proof-of-Throughput.

This implementation uses a combination of Okasaki style balancing for 
insert [2] and Kazu Yamamato's version of delete [3,4,5].


[1] Persistent Authenticated Dictionaries and Their Applications
    Agnostopolous, Goodrich, and Tamassia.
    http://cs.brown.edu/people/aris/pubs/pad.pdf

[2] Purely Functional Data Structures
    <NAME>
    http://www.eecs.usma.edu/webs/people/okasaki/jfp99.ps

[3] Missing method: How to delete from Okasaki's red-black trees
    <NAME>
    http://matt.might.net/articles/red-black-delete/

[4] Efficient Verified Red-Black Trees
    <NAME>
    http://www.cs.princeton.edu/~appel/papers/redblack.pdf

[5] Purely Functional Left-Leaning Red-Black Trees
    <NAME>
    http://www.mew.org/~kazu/proj/red-black-tree/


Type definitions and common notations:
======================================

RedBlack():
    A RedBlack tree that can be augmented with a 'digest' field, which is
    assumed to contain at least a collision-resistant hash function. The
    digests for the subtrees are stored along with each node. The digests
    are recomputed as necessary during insert and delete in order to maintain
    consistency.

 ** Note that RedBlack objects simply define functions, the actual data 
    structure D is just a tuple, as described below

D:
    A Node in the tree, especially the root. Of the form:
        (Color, Left, (Element, LeftDigest, RightDigest), Right) = D

    - Typically abbreviated
        (c, L, (k, dL, dR), R) = D

    - c in ('R', 'B'): red and black labels for balancing
        L, R: the children, also Nodes,
        dL, dR: digests of the children
        k: each non-leaf's value is equal to the largest leaf value in the left
           sub-tree

    - () represents the empty tree.
    - dO == digest(()) is the empty-digest

    - The following operations are defined as you'd expect:

        D = insert(q, D)   # unless q is already in the set
        D = delete(q, D)   # unless the set does not contain q
        v = search(q, D)   # Returns the smallest element >= q, unless q is the
                           # largest element in the tree

VO:
    Each of the tree operations is defined in terms of a stateful 'Traversal'
    object, which runs in one of two modes:

    Record: 
        The data for every node visited during subsequent operations on T
        is appended to a Verification Object (VO).

        T = record(D)
        d0 = T.insert(q)
        VO = T.VO

    Replay: 
        A VO created from a recording can be replayed, simulating the
        operation on the full tree.

        T = replay(d0, VO)
        d0 = T.insert(q)

 ** Security Claim **

    If an operation on a Replay traversal returns a value, then it is the same
    value that would be returned by the operation on the original tree.

    Proof sketch:
       At each step during a traversal, the digest for each node is known
       before the node's data is accessed. During a Replay, the digest is
       is recomputed and verified.

 ** Bounded Cost-of-Verification Claim **

    The tree is balanced such that the longest possible path from the root to
    a leaf is 2 log N. The worst-case bounds for all operations are given
    below:
          delete: 4 + 3 log N
          insert: 2 log N
          search: 2 log N

    TODO: I think these are wrong! How to construct the worst case?
"""

import math
import itertools

class RedBlack(object):
    def __init__(self, H=hash):
        """
        Args:
             H (optional): a collision-resistant hash function that
                           takes arguments of the form:
                  H(())
                  H((c, dL, k, dR))
        """
        self.H = H
        self.dO = self.digest(())

    def digest(self, D):
        if not D: return self.H(())
        (c, _, (k, dL, dR), _) = D
        return self.H((c, dL, k, dR))

    def record(self, D):
        return RecordTraversal(self.H, D)

    def replay(self, d0, VO):
        return ReplayTraversal(self.H, d0, VO)

    def search(self, q, D):
        T = self.record(D)
        return T.search(q)

    def insert(self, q, D, v=''):
        T = self.record(D)
        return T.reconstruct(T.insert(q, v))

    def delete(self, q, D):
        T = self.record(D)
        return T.reconstruct(T.delete(q))


class Traversal(object):
    def __init__(self, H, d0):
        self.H = H
        self.cache = {}
        self.dO = H(())
        self.d0 = d0

        # TODO: each of the balance operations sometimes produces more 
        # 'proof' than is necessary. For example, if bL2 is a match,
        # then a 'negative proof' for bL1 is unnecessary. Is there a way
        # to resolve this using the same coroutine setup I have?
        R,B,a,b,c,d,x,y,z = 'RBabcdxyz'
        self.bL1 = (B,(R,(R,a,x,b),y,c),z,d), (R,(B,a,x,b),y,(B,c,z,d))
        self.bL2 = (B,(R,a,x,(R,b,y,c)),z,d), (R,(B,a,x,b),y,(B,c,z,d))
        self.bR1 = (B,a,x,(R,(R,b,y,c),z,d)), (R,(B,a,x,b),y,(B,c,z,d))
        self.bR2 = (B,a,x,(R,b,y,(R,c,z,d))), (R,(B,a,x,b),y,(B,c,z,d))

    def balanceL(self, c, dL, k, dR):
        d = self.store(c, dL, k, dR)
        return self.match(self.bL1, d) or self.match(self.bL2, d) or d

    def balanceR(self, c, dL, k, dR):
        d = self.store(c, dL, k, dR)
        return self.match(self.bR1, d) or self.match(self.bR2, d) or d

    def unbalancedL(self, c, dL, k, dR):
        get = self.get
        store = self.store
        balanceL = self.balanceL
        red = lambda (_,dL,x,dR): ('R',dL,x,dR)
        (_c, _dL, _k, _dR) = get(dL)
        if _c == 'B': return balanceL('B',store('R',_dL,_k,_dR),k,dR), c=='B'
        _R = get(_dR)
        assert c == 'B' and _c == 'R' and _R[0] == 'B'
        return store('B',_dL,_k,balanceL('B',store(*red(_R)),k,dR)), False

    def unbalancedR(self, c, dL, k, dR):
        get = self.get
{'fraction_non_alphanumeric': 0.12182900093955527, 'fraction_numerical': 0.006263701847792045, 'mean_word_length': 2.480381471389646, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 19, 'https://': 0, 'lorem ipsum': 0, 'www.': 6, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4278797', 'n_tokens_mistral': 4402, 'n_tokens_neox': 4179, 'n_words': 1549}