Merge lp:~jderose/filestore/protocols into lp:filestore

[Jason Gerard DeRose]

This puts the infrastructure in place for selecting between multiple protocols based on ID length, but so far it causes no external API change and the version zero protocol is used by default. Also, not all code paths have been updated to be protocol aware... I did just enough to prove the overall approach is viable. As this is already a rather large merge, I think it's better to finish the API updates is another merge (and probably further refine some things).

Details:

 * Moves filestore.py to filestore/__init__.py, turning filestore into a proper Python package now that it spans multiple modules

 * Adds new filestore/protocols.py module with a uniform API that all protocol versions use. This makes it much easier to experiment with new protocols, and allows both the current (interim) v0 protocol and the (proposed) v1 protocol to exist side by side

 * Changes the proposed v1 protocol from 240 to 280 bits so we can do a nice migration, fully test our length-based protocol identification

 * Adds new filestore/misc.py module with some utility functions for generating standard test vectors for a protocol version... before we officially commit to the v1 protocol, it would be nice to have at least one independent "clean-room" implementation based on just a description of the protocol, verified with our test vectors, and in a language other than Python (my vote is Java because of Android)

 * Adds v0 and v1 test vectors in test-vectors.json data file

 * Moves the TempFileStore class into the misc.py module, which normally isn't imported, which allows us to reduce Dmedia's memory usage a bit (because filestore doesn't need to import `shutil` and `tempfile`)

 * Removes the hash_leaf2(), hash_root2() functions as their tests, as they are now replaced by an implementation of the same using the new Protocol class

 * Updates Hasher, hash_fp(), FileStore.verify(), check_root_hash(), and a few other misc functions to be protocol version aware... this isn't a complete porting yet, just enough to confirm that the Protocol API is viable

 * A bit of unit test refactoring and cleanup

[Jason Gerard DeRose (jderose)]

Oh, and for further details, see this bug:

https://bugs.launchpad.net/filestore/+bug/1094801

[James Raymond (jamesmr)]

review: Approve

[James Raymond (jamesmr)]

Long read, but looks okay to me!

review: Approve

=== modified file 'MANIFEST.in'
--- MANIFEST.in	2011-08-19 20:51:05 +0000
+++ MANIFEST.in	2012-12-31 04:35:24 +0000
@@ -1,2 +1,2 @@
-include COPYING test_filestore.py
+include COPYING
 include doc/*

=== modified file 'benchmark-protocol.py'
--- benchmark-protocol.py	2012-12-02 00:16:59 +0000
+++ benchmark-protocol.py	2012-12-31 04:35:24 +0000
@@ -3,30 +3,47 @@
 import timeit
 
 setup = """
-import os
 from base64 import b32encode, b64encode
 
-from filestore import DIGEST_BYTES, hash_root, hash_root2
-
-digest = os.urandom(DIGEST_BYTES)
+from filestore import check_id, B32ALPHABET
+from filestore.protocols import Protocol, OldProtocol, MiB
+
+digest = b'N' * 30
+_id = 'GTUK6VPCITPAUSG3FLVNYK7IXEPXWDKGQ4T2X4IUOYXDE232'
+
+new = Protocol(8 * MiB, 240)
+old = OldProtocol(8 * MiB, 240)
+
+leaf_index = 17
+leaf_data = b'S' * 1776
+
 file_size = 31415
-leaf_hashes = b'L' * DIGEST_BYTES
+leaf_hashes = b'D' * 30
 """
 
-N = 50 * 1000
+N = 100 * 1000
 
 def run(statement):
     t = timeit.Timer(statement, setup)
     elapsed = t.timeit(N)
-    print('{:.0f}/s: {}'.format(N / elapsed, statement))
+    rate = int(N / elapsed)
+    print('{:>10,}: {}'.format(rate, statement))
+
+
+print('Executions per second:')
 
 run('b32encode(digest)')
-run("b32encode(digest).decode('utf-8')")
-run("b32encode(digest).decode('ascii')")
 
 run('b64encode(digest)')
 run("b64encode(digest).decode('utf-8')")
 run("b64encode(digest).decode('ascii')")
 
-run('hash_root(file_size, leaf_hashes)')
-run('hash_root2(file_size, leaf_hashes)')
+run('check_id(_id)')
+run('set(_id).issubset(B32ALPHABET)')
+run('B32ALPHABET.issuperset(_id)')
+
+run("old._hash_leaf(leaf_index, leaf_data, b'')")
+run("new._hash_leaf(leaf_index, leaf_data, b'')")
+
+run('old._hash_root(file_size, leaf_hashes)')
+run('new._hash_root(file_size, leaf_hashes)')

=== added directory 'filestore'
=== renamed file 'filestore.py' => 'filestore/__init__.py'
--- filestore.py	2012-12-19 08:54:54 +0000
+++ filestore/__init__.py	2012-12-31 04:35:24 +0000
@@ -28,7 +28,7 @@
 
 The best way to experiment is to use a `TempFileStore`.  For example:
 
->>> from filestore import TempFileStore
+>>> from filestore.misc import TempFileStore
 >>> fs = TempFileStore()
 >>> tmp_fp = fs.allocate_tmp()
 >>> tmp_fp.write(b'Hello, Bruce Schneier!')
@@ -75,8 +75,6 @@
 import os
 from os import path
 import io
-import tempfile
-import shutil
 import stat
 from base64 import b32encode, b64encode
 import hashlib
@@ -87,6 +85,8 @@
 
 from skein import skein512
 
+from .protocols import VERSION0, VERSION1
+
 try:
     from _filestore import fallocate, posix_fadvise, fastread
 except ImportError:
@@ -114,6 +114,9 @@
 DIGEST_BYTES = DIGEST_BITS // 8
 DIGEST_B32LEN = DIGEST_BITS // 5
 
+ALLOWED_B32LEN = (48, 56)
+PROTOCOL = VERSION0
+
 # Handy constants for file layout:
 DOTNAME = '.dmedia'
 B32ALPHABET = frozenset('234567ABCDEFGHIJKLMNOPQRSTUVWXYZ')
@@ -259,124 +262,15 @@
     :param leaf_hashes: a ``bytes`` instance that is the concatenated leaf
         hashes produced by `hash_leaf()`
     """
-    if not isinstance(file_size, int):
-        raise TypeError(
-            TYPE_ERROR.format('file_size', int, type(file_size), file_size)
-        )
-    if file_size < 1:
-        raise ValueError(
-            'file_size: must be >= 1; got {!r}'.format(file_size)
-        )
-    if not isinstance(leaf_hashes, bytes):
-        raise TypeError(TYPE_ERROR.format(
-                'leaf_hashes', bytes, type(leaf_hashes), leaf_hashes
-            )
-        )
-    if len(leaf_hashes) == 0:
-        raise ValueError('leaf_hashes cannot be empty')
-    if len(leaf_hashes) % DIGEST_BYTES != 0:
-        raise ValueError('len(leaf_hashes) is {}, not multiple of {}'.format(
-                len(leaf_hashes), DIGEST_BYTES)
-        )
-    n = len(leaf_hashes) // DIGEST_BYTES
-    low = (n - 1) * LEAF_SIZE + 1
-    high = n * LEAF_SIZE
-    if not (low <= file_size <= high):
-        raise ValueError(
-            'Need {} <= file_size <= {}; got {}'.format(low, high, file_size)
-        )
-    skein = skein512(hash_file_size(file_size),
-        digest_bits=DIGEST_BITS,
-        pers=PERS_ROOT,
-    )
-    skein.update(leaf_hashes)
-    return b32encode(skein.digest()).decode('utf-8')
-
-
-def hash_leaf2(leaf_index, leaf_data, challenge=b''):
-    """
-    Return the leaf-hash of the leaf at (zero) index *leaf_index*.
-
-    For example:    
-
-    >>> b32encode(hash_leaf2(3, b'XYZ'))
-    b'4GIMNJIAKM5NK3I26QWZFENZRM66CZB2VQK4YSXGH3KWBZCQ'
-
-    :param leaf_index: an ``int`` >= 0
-    :param leaf_data: a ``bytes`` instance with contents of this leaf
-    :param challenge: a ``bytes`` instance containing a random nonce to be used
-        in a proof-of-storage
-    """
-    if not isinstance(leaf_index, int):
-        raise TypeError(
-            TYPE_ERROR.format('leaf_index', int, type(leaf_index), leaf_index)
-        )
-    if leaf_index < 0:
-        raise ValueError(
-            'leaf_index: must be >= 0; got {!r}'.format(leaf_index)
-        )
-    if not isinstance(leaf_data, bytes):
-        raise TypeError(
-            TYPE_ERROR.format('leaf_data', bytes, type(leaf_data), leaf_data)
-        )
-    if not (1 <= len(leaf_data) <= LEAF_SIZE):
-        raise ValueError('Need 1 <= len(leaf_data) <= {}; got {}'.format(
-                LEAF_SIZE, len(leaf_data)
-            )
-        )
-    return skein512(leaf_data,
-        digest_bits=DIGEST_BITS,
-        pers=PERS_LEAF,
-        key=str(leaf_index).encode('utf-8'),
-        nonce=challenge,
-    ).digest()
-
-
-def hash_root2(file_size, leaf_hashes):
-    """
-    Return the root-hash for a file *file_size* bytes with *leaf_hashes*.
-
-    For example:
-
-    >>> hash_root2(31415, b'NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN')
-    '7M6RPEWAIMYTKIISSB3K4ORAX2ONZ6R3B4XAZWQURMGD2IW4'
-
-    :param file_size: an ``int`` >= 1
-    :param leaf_hashes: a ``bytes`` instance that is the concatenated leaf
-        hashes produced by `hash_leaf2()`
-    """
-    if not isinstance(file_size, int):
-        raise TypeError(
-            TYPE_ERROR.format('file_size', int, type(file_size), file_size)
-        )
-    if file_size < 1:
-        raise ValueError(
-            'file_size: must be >= 1; got {!r}'.format(file_size)
-        )
-    if not isinstance(leaf_hashes, bytes):
-        raise TypeError(TYPE_ERROR.format(
-                'leaf_hashes', bytes, type(leaf_hashes), leaf_hashes
-            )
-        )
-    if len(leaf_hashes) == 0:
-        raise ValueError('leaf_hashes cannot be empty')
-    if len(leaf_hashes) % DIGEST_BYTES != 0:
-        raise ValueError('len(leaf_hashes) is {}, not multiple of {}'.format(
-                len(leaf_hashes), DIGEST_BYTES)
-        )
-    n = len(leaf_hashes) // DIGEST_BYTES
-    low = (n - 1) * LEAF_SIZE + 1
-    high = n * LEAF_SIZE
-    if not (low <= file_size <= high):
-        raise ValueError(
-            'Need {} <= file_size <= {}; got {}'.format(low, high, file_size)
-        )
-    skein = skein512(leaf_hashes,
-        digest_bits=DIGEST_BITS,
-        pers=PERS_ROOT,
-        key=str(file_size).encode('utf-8'),
-    )
-    return b32encode(skein.digest()).decode('utf-8')
+    return VERSION0.hash_root(file_size, leaf_hashes)
+
+
+def get_protocol(_id):
+    check_id(_id)
+    if len(_id) == 48:
+        return VERSION0
+    assert len(_id) == 56
+    return VERSION1
 
 
 class Hasher(object):
@@ -384,9 +278,10 @@
     A helper to keep track of state as you hash leaf after leaf.
     """
 
-    __slots__ = ('file_size', 'leaf_index', 'array', 'closed')
+    __slots__ = ('protocol', 'file_size', 'leaf_index', 'array', 'closed')
 
-    def __init__(self):
+    def __init__(self, protocol=PROTOCOL):
+        self.protocol = protocol
         self.file_size = 0
         self.leaf_index = 0
         self.array = bytearray()
@@ -401,9 +296,9 @@
             raise Exception('Expected leaf.index {}, got {}'.format(
                     self.leaf_index, leaf.index)
             )
-        if len(leaf.data) < LEAF_SIZE:
+        if len(leaf.data) < self.protocol.leaf_size:
             self.closed = True
-        leaf_hash = hash_leaf(leaf.index, leaf.data)
+        leaf_hash = self.protocol.hash_leaf(leaf.index, leaf.data)
         self.array.extend(leaf_hash)
         self.file_size += len(leaf.data)
         self.leaf_index += 1
@@ -413,7 +308,7 @@
         self.closed = True
         leaf_hashes = bytes(self.array)
         return ContentHash(
-            hash_root(self.file_size, leaf_hashes),
+            self.protocol.hash_root(self.file_size, leaf_hashes),
             self.file_size,
             leaf_hashes
         )
@@ -535,12 +430,12 @@
     """
     if not isinstance(_id, str):
         raise TypeError(TYPE_ERROR.format('_id', str, type(_id), _id))
-    if not (len(_id) == DIGEST_B32LEN and set(_id).issubset(B32ALPHABET)):
+    if not (len(_id) in  ALLOWED_B32LEN and set(_id).issubset(B32ALPHABET)):
         raise IDError(_id)
     return _id
 
 
-def check_leaf_hashes(leaf_hashes):
+def check_leaf_hashes(leaf_hashes, protocol=PROTOCOL):
     """
     Verify that *leaf_hashes* is a ``bytes`` instance of correct length.
 
@@ -562,7 +457,7 @@
                 'leaf_hashes', bytes, type(leaf_hashes), leaf_hashes
             )
         )
-    if len(leaf_hashes) == 0 or len(leaf_hashes) % DIGEST_BYTES != 0:
+    if len(leaf_hashes) == 0 or len(leaf_hashes) % protocol.digest_bytes != 0:
         raise LeafHashesError(leaf_hashes)
     return leaf_hashes
 
@@ -590,11 +485,12 @@
     22
 
     """
-    computed = hash_root(file_size, leaf_hashes)
+    protocol = get_protocol(_id)
+    computed = protocol.hash_root(file_size, leaf_hashes)
     if _id != computed:
         raise RootHashError(_id, file_size, leaf_hashes, computed)
     if unpack:
-        leaf_hashes = tuple(iter_leaf_hashes(leaf_hashes))
+        leaf_hashes = tuple(iter_leaf_hashes(leaf_hashes, protocol))
     return ContentHash(_id, file_size, leaf_hashes)
 
 
@@ -628,7 +524,7 @@
 #################################################
 # Utility functions for working with leaf_hashes:
 
-def enumerate_leaf_hashes(leaf_hashes):
+def enumerate_leaf_hashes(leaf_hashes, protocol=PROTOCOL):
     """
     Enumerate *leaf_hashes*.
 
@@ -640,12 +536,13 @@
     [(0, b'AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA'), (1, b'BBBBBBBBBBBBBBBBBBBBBBBBBBBBBB')]
 
     """
-    check_leaf_hashes(leaf_hashes)
-    for i in range(len(leaf_hashes) // DIGEST_BYTES):
-        yield (i, leaf_hashes[i*DIGEST_BYTES : (i+1)*DIGEST_BYTES])
-
-
-def iter_leaf_hashes(leaf_hashes):
+    check_leaf_hashes(leaf_hashes, protocol)
+    digest_bytes = protocol.digest_bytes
+    for i in range(len(leaf_hashes) // digest_bytes):
+        yield (i, leaf_hashes[i*digest_bytes : (i+1)*digest_bytes])
+
+
+def iter_leaf_hashes(leaf_hashes, protocol=PROTOCOL):
     """
     Iterate through *leaf_hashes*.
 
@@ -657,12 +554,13 @@
     [b'AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA', b'BBBBBBBBBBBBBBBBBBBBBBBBBBBBBB']
 
     """
-    check_leaf_hashes(leaf_hashes)
-    for i in range(len(leaf_hashes) // DIGEST_BYTES):
-        yield leaf_hashes[i*DIGEST_BYTES : (i+1)*DIGEST_BYTES]
-
-
-def get_leaf_hash(leaf_hashes, i):
+    check_leaf_hashes(leaf_hashes, protocol)
+    digest_bytes = protocol.digest_bytes
+    for i in range(len(leaf_hashes) // digest_bytes):
+        yield leaf_hashes[i*digest_bytes : (i+1)*digest_bytes]
+
+
+def get_leaf_hash(leaf_hashes, i, protocol=PROTOCOL):
     """
     Return a slice containing the i-th leaf_hash from *leaf_hashes*.
 
@@ -677,7 +575,8 @@
     b''
 
     """
-    return leaf_hashes[i*DIGEST_BYTES : (i+1)*DIGEST_BYTES]
+    digest_bytes = protocol.digest_bytes
+    return leaf_hashes[i*digest_bytes : (i+1)*digest_bytes]
 
 
 def missing_leaves(fp, leaf_hashes):
@@ -950,7 +849,7 @@
     thread.join()  # Make sure batch_reader() terminates
 
 
-def hash_fp(src_fp, dst_fp=None):
+def hash_fp(src_fp, dst_fp=None, protocol=PROTOCOL):
     """
     Compute content hash of open file *src_fp*, optionally writing *dst_fp*.
 
@@ -963,7 +862,7 @@
     :param src_fp: A file opened in mode "rb" or "r+b"
     :param dst_fp: An optional file opened in mode "wd"
     """
-    hasher = Hasher()
+    hasher = Hasher(protocol)
     for leaf in reader_iter(src_fp):
         hasher.hash_leaf(leaf)
         if dst_fp:
@@ -1093,7 +992,7 @@
             subdir = path.join(self.basedir, 'files', prefix)
             for name in sorted(os.listdir(subdir)):
                 _id = prefix + name
-                if len(_id) != DIGEST_B32LEN:
+                if len(_id) not in ALLOWED_B32LEN:
                     continue
                 if not set(_id).issubset(B32ALPHABET):
                     continue
@@ -1296,7 +1195,7 @@
             a ContentHash namedtuple
         """
         src_fp = self.open(_id)
-        c = hash_fp(src_fp)
+        c = hash_fp(src_fp, protocol=get_protocol(_id))
         if c.id != _id:
             raise self.move_to_corrupt(src_fp, _id, bad_id=c.id)
         if return_fp:
@@ -1688,38 +1587,3 @@
             except CorruptFile as e:
                 yield e
 
-
-class TempFileStore(FileStore):
-    """
-    A throw-away `FileStore` for experimenting and testing.
-
-    When you create a `TempFileStore` instance, a random, temporary
-    `FileStore.parentdir` is created for you.  For example:
-
-    >>> fs = TempFileStore()
-
-    Then when the `TempFileStore` instance is garbage collected, this
-    directory is automatically deleted (along with any files contained
-    therein).
-
-    As with a `FileStore`, you can provide the `FileStore.id` and
-    `FileStore.copies` attributes.  The `FileStore` itself ignores these
-    values, but they are convenient for high-level software like Dmedia.
-
-    For example:
-
-    >>> fs = TempFileStore('hello', 3)
-    >>> fs.id
-    'hello'
-    >>> fs.copies
-    3
-
-    """
-    def __init__(self, _id=None, copies=0):
-        parentdir = tempfile.mkdtemp(prefix='TempFileStore.')
-        super().__init__(parentdir, _id, copies)
-        assert self.parentdir is parentdir
-
-    def __del__(self):
-        if path.isdir(self.parentdir):
-            shutil.rmtree(self.parentdir)

=== added directory 'filestore/data'
=== added file 'filestore/data/test-vectors.json'
--- filestore/data/test-vectors.json	1970-01-01 00:00:00 +0000
+++ filestore/data/test-vectors.json	2012-12-31 04:35:24 +0000
@@ -0,0 +1,50 @@
+{
+    "48": {
+        "leaf_hashes": {
+            "A": [
+                "FrZmE1OIglZp4N1Rl9HD6MuAQXDGqx57KgsPyXLL",
+                "DaIG8amV8Jl6u8Qa2uiKWQhmgV2r5IxlTg3Tt70l"
+            ],
+            "B": [
+                "atOnHDzrEkWhr7pFMIkfrPfNcNGbd+CN/c7aTVu5",
+                "AsAN/81Fu8tHrfJxoj4+qVKPgFqv3pFEkxoNGCRt"
+            ],
+            "C": [
+                "zD0aCp/ozlcPJDNX70E0ZvgN0B3czawr6zxpyVJl",
+                "YLJzcaFfa2UKCARHePkHbvgFoGf7q4Bns2jXdCgc"
+            ]
+        },
+        "root_hashes": {
+            "A": "O4NQ4LFNI2UCMKOSWWGPRZXSNEPW2M6OOTBFM3AHTBK35D67",
+            "B": "NW6IMGBAU4NTZDQRHGIZA7VYV5CBZ5TUXADHZE43N4GDZGKK",
+            "C": "TRXCE6PVSJTHQX7H4KV7A7F5DKCMSETLMNANNCJIVT624WLU",
+            "CA": "QSUCTH4LJU3B7QG7IJ3FC7HNE4TXDPZVQEJ36B4A45ATTXDM",
+            "CB": "3FWPZ6RBPXGBSTFBNPK5IOCO7DUMSKR5YTWJ3HM2KI4AEF2O",
+            "CC": "CX2K52LIUTT6SSMFHR7NUI6YIJLO3SGKLSRIL6IDY4BP7HUZ"
+        }
+    },
+    "56": {
+        "leaf_hashes": {
+            "A": [
+                "vnqPKTOknItURAuVQi5gHml2ncDDv/apR7CRbZ8Gw57L9S0=",
+                "mQX/95lrNeZNnsQKj02VnNXIqgRjwGnqLoZoF9EHkmmhjjs="
+            ],
+            "B": [
+                "f776qpuQhQO1EWR1nrUCIxD9+sIqTcBb2AgJ6iOK8Gq8bIg=",
+                "ygruy07GH5BRvrwtO2TCGCdxGjpOG/ogF+8sytiTYihTfsw="
+            ],
+            "C": [
+                "jbRklQZ8C9suPd0Ar/5vO2JVMoHEQ62ksuG1EsYtPbzr8FE=",
+                "uGq34DS/oD0NT0zxWl562rYAUBbqeRZDvNtg0YDujBPzBGQ="
+            ]
+        },
+        "root_hashes": {
+            "A": "FWV6OJYI36C5NN5DC4GS2IGWZXFCZCGJGHK35YV62LKAG7D2Z4LO4Z2S",
+            "B": "OB756PX5V32JMKJAFKIAJ4AFSFPA2WLNIK32ELNO4FJLJPEEEN6DCAAJ",
+            "C": "QSOHXCDH64IQBOG2NM67XEC6MLZKKPGBTISWWRPMCFCJ2EKMA2SMLY46",
+            "CA": "BQ5UTB33ML2VDTCTLVXK6N4VSMGGKKKDYKG24B6DOAFJB6NRSGMB5BNO",
+            "CB": "ER3LDDZ2LHMTDLOPE5XA5GEEZ6OE45VFIFLY42GEMV4TSZ2B7GJJXAIX",
+            "CC": "R6RN5KL7UBNJWR5SK5YPUKIGAOWWFMYYOVESU5DPT34X5MEK75PXXYIX"
+        }
+    }
+}
\ No newline at end of file

=== added file 'filestore/misc.py'
--- filestore/misc.py	1970-01-01 00:00:00 +0000
+++ filestore/misc.py	2012-12-31 04:35:24 +0000
@@ -0,0 +1,124 @@
+# filestore: Dmedia hashing protocol and file layout
+# Copyright (C) 2012 Novacut Inc
+#
+# This file is part of `filestore`.
+#
+# `filestore` is free software: you can redistribute it and/or modify it under
+# the terms of the GNU Affero General Public License as published by the Free
+# Software Foundation, either version 3 of the License, or (at your option) any
+# later version.
+#
+# `filestore` is distributed in the hope that it will be useful, but WITHOUT ANY
+# WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
+# A PARTICULAR PURPOSE.  See the GNU Affero General Public License for more
+# details.
+#
+# You should have received a copy of the GNU Affero General Public License along
+# with `filestore`.  If not, see <http://www.gnu.org/licenses/>.
+#
+# Authors:
+#   Jason Gerard DeRose <[e-mail]>
+
+"""
+Helper functions for creating a utilizing protocol test vectors.
+"""
+
+from os import path
+import json
+from base64 import b64encode, b64decode
+import tempfile
+import shutil
+
+from . import FileStore
+
+
+TEST_VECTORS = path.join(
+    path.dirname(path.abspath(__file__)), 'data', 'test-vectors.json'
+)
+assert path.isfile(TEST_VECTORS)
+
+
+def encode(value):
+    return b64encode(value).decode('utf-8')
+
+
+def decode(value):
+    return b64decode(value.encode('utf-8'))
+
+
+def load_test_vectors():
+    return json.load(open(TEST_VECTORS, 'r'))
+
+
+def build_test_leaves(leaf_size):
+    return {
+        'A': b'A',
+        'B': b'B' * (leaf_size - 1),
+        'C': b'C' * leaf_size,
+    }
+
+
+def build_test_vectors(protocol):
+    leaves = build_test_leaves(protocol.leaf_size)
+
+    def hash_root(letters):
+        leaf_hashes = b''
+        file_size = 0
+        for (i, L) in enumerate(letters):
+            data = leaves[L]
+            leaf_hashes += protocol.hash_leaf(i, data)
+            file_size += len(data)
+        return protocol.hash_root(file_size, leaf_hashes)
+
+    vectors = {
+        'leaf_hashes': {},
+        'root_hashes': {},
+    }
+
+    for (key, data) in leaves.items():
+        vectors['leaf_hashes'][key] = [
+            encode(protocol.hash_leaf(i, data)) for i in range(2)
+        ]
+
+    for L in leaves:
+        for key in (L, 'C' + L):
+            vectors['root_hashes'][key] = hash_root(key)
+
+    return vectors
+
+
+class TempFileStore(FileStore):
+    """
+    A throw-away `FileStore` for experimenting and testing.
+
+    When you create a `TempFileStore` instance, a random, temporary
+    `FileStore.parentdir` is created for you.  For example:
+
+    >>> fs = TempFileStore()
+
+    Then when the `TempFileStore` instance is garbage collected, this
+    directory is automatically deleted (along with any files contained
+    therein).
+
+    As with a `FileStore`, you can provide the `FileStore.id` and
+    `FileStore.copies` attributes.  The `FileStore` itself ignores these
+    values, but they are convenient for high-level software like Dmedia.
+
+    For example:
+
+    >>> fs = TempFileStore('hello', 3)
+    >>> fs.id
+    'hello'
+    >>> fs.copies
+    3
+
+    """
+    def __init__(self, _id=None, copies=0):
+        parentdir = tempfile.mkdtemp(prefix='TempFileStore.')
+        super().__init__(parentdir, _id, copies)
+        assert self.parentdir is parentdir
+
+    def __del__(self):
+        if path.isdir(self.parentdir):
+            shutil.rmtree(self.parentdir)
+

=== added file 'filestore/protocols.py'
--- filestore/protocols.py	1970-01-01 00:00:00 +0000
+++ filestore/protocols.py	2012-12-31 04:35:24 +0000
@@ -0,0 +1,386 @@
+# filestore: Dmedia hashing protocol and file layout
+# Copyright (C) 2012 Novacut Inc
+#
+# This file is part of `filestore`.
+#
+# `filestore` is free software: you can redistribute it and/or modify it under
+# the terms of the GNU Affero General Public License as published by the Free
+# Software Foundation, either version 3 of the License, or (at your option) any
+# later version.
+#
+# `filestore` is distributed in the hope that it will be useful, but WITHOUT ANY
+# WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
+# A PARTICULAR PURPOSE.  See the GNU Affero General Public License for more
+# details.
+#
+# You should have received a copy of the GNU Affero General Public License along
+# with `filestore`.  If not, see <http://www.gnu.org/licenses/>.
+#
+# Authors:
+#   Jason Gerard DeRose <[e-mail]>
+
+"""
+Generic API for the Dmedia Hashing Protocol, both current and future versions.
+
+Dmedia is a very loosely coupled distributed object store, and in order for it
+to achieve its goals, two key constraints were needed:
+
+    1. File in Dmedia are read-only (you can't modify an existing file, you can
+       only insert an entire new file)
+
+    2. Files can only be addressed by their content-hash
+
+We feel the properties we get are well-worth these limitations, but assigning
+global file IDs based on their content hash is not without peril.  For some
+background on the challenges and limitations of content-based addressing, see
+this excellent paper by Valerie Aurora:
+
+    http://valerieaurora.org/monkey.html
+
+Our take-away from the above paper is that:
+
+    * We should assume the hashing protocol will have a limited useful
+      lifetime, perhaps not longer than 10 years or so
+
+    * We should today have in place exact plans for how a new version of the
+      hashing protocol will be introduced and how multiple versions of the
+      protocol can coexist side-by-side during a long transition period
+
+In short, our migration strategy is to use the digest length as a way to select
+the appropriate protocol version.  For example, say the version 1 hashing
+protocol has a 280-bit digest.  And then in a decade from now when a new
+protocol is needed, the new protocol will have a different digest length, say
+320-bit.
+
+This allows files hashed under different versions of the protocol to be stored
+together in a FileStore.  At any given time there will be one or more valid
+digest lengths, each one selecting a specific protocol version.  So if you
+wanted to verify every file in a FileStore, you would iterate through them one
+by one, select the protocol version based on the ID length, and then see if the
+hash you compute matches the ID.
+
+So that our reference implementation is well architected for the inevitable,
+we're going to make all relevant code paths select the protocol version based
+on the ID length, even when there is only one protocol available.
+
+We want to practice now, rather than later.  This will force us to work within
+this constraint, and will mean we develop design patterns that are prepared for
+the future.
+
+We might also do a full practice migration from the current protocol in use
+(which we're calling version zero), to the proposed version one protocol.
+
+Although we've never made any official commitment to the version zero protocol,
+it's been around long enough that we really need at least migration
+functionality, if not to support it alongside the version one protocol.
+Despite not being production ready, some people have built fairly large Dmedia
+libraries already.
+
+For reference, the version zero protocol has been unchanged since November 2011:
+
+    https://launchpad.net/filestore/trunk/11.09
+
+In hind sight, we should have used a smaller digest size than expected for the
+version zero protocol, and then planned to do a practice protocol change by at
+least upping the digest size, even if no other changes were made.
+
+In our opinion, a 240-bit digest size is probably the best choice for the
+version one protocol, but unfortunately we can't use that if we want to put
+Dmedia through a realistic migration scenario.  And the valuable lessons we'd
+learn from such a practice scenario probably outweigh the downside not having
+what we currently feel is the ideal digest size.
+
+But even if multiple protocols are only supported in the context of unit tests,
+we still feel this is a very import architecture to embrace now.
+"""
+
+from base64 import b32encode
+
+from skein import skein512
+
+
+# Skein personalization strings used in the Dmedia Hashing Protocol:
+PERS_LEAF = b'20110430 [e-mail] dmedia/leaf'
+PERS_ROOT = b'20110430 [e-mail] dmedia/root'
+
+# Additional Skein personalization strings used only in the old protocol:
+PERS_LEAF_INDEX = b'20110430 [e-mail] dmedia/leaf-index'
+PERS_FILE_SIZE = b'20110430 [e-mail] dmedia/file-size'
+
+# Provide very clear TypeError messages:
+TYPE_ERROR = '{}: need a {!r}; got a {!r}: {!r}'
+
+# Handy:
+MiB = 1024 ** 2
+
+
+class Protocol:
+    """
+    Standard API for current and future versions of the Dmedia Hashing Protocol.
+
+    This class provides a standard API that abstracts away the details of a
+    particular hashing protocol and allows multiple protocol versions to be
+    supported simultaneously.
+
+    The API consists of two methods:
+
+        `Protocol.hash_leaf(leaf_index, leaf_data, challange=b'')`
+
+        `Protocol.hash_root(file_size, leaf_hashes)`
+
+    And four attributes:
+
+        `Protocol.leaf_size`
+
+        `Protocol.digest_bits`
+
+        `Protocol.digest_bytes`
+
+        `Protocol.digest_b32len`
+
+    To make it easy to experiment with different *leaf_size* and *digest_bits*
+    (while still using the standard hashing functions), you can simply create
+    a `Protocol` instance like this:
+
+    >>> experimental = Protocol(16 * MiB, 360)
+
+    The `digest_bytes` and `digest_b32len` will be derived from the provided
+    *digest_bits*:
+
+    >>> experimental.digest_bytes
+    45
+    >>> experimental.digest_b32len
+    72
+
+    In order to implement a protocol that uses different underlying hash
+    functions, you'll need to subclass `Protocol` and override the two
+    low-level hashing methods:
+
+        `Protocol._hash_leaf(leaf_index, leaf_data, challange)`
+
+        `Protocol._hash_root(file_size, leaf_hashes)` 
+    """
+
+    def __init__(self, leaf_size, digest_bits):
+        """
+        Initialize a new `Protocol` instance.
+
+        :param leaf_size: an ``int`` which is some multiple of MiB and >= MiB
+        :param digest_bits: an ``int`` which is some multiple of 40 and >= 200
+        """
+        if not isinstance(leaf_size, int):
+            raise TypeError(
+                TYPE_ERROR.format('leaf_size', int, type(leaf_size), leaf_size)
+            )
+        if leaf_size < MiB:
+            raise ValueError(
+                'leaf_size: must be >= MiB; got {!r}'.format(leaf_size)
+            )
+        if leaf_size % MiB != 0:
+            raise ValueError(
+                'leaf_size: must be multiple of MiB; got {!r}'.format(leaf_size)
+            )
+        if not isinstance(digest_bits, int):
+            raise TypeError(
+                TYPE_ERROR.format(
+                    'digest_bits', int, type(digest_bits), digest_bits
+                )
+            )
+        if digest_bits < 200:
+            raise ValueError(
+                'digest_bits: must be >= 200; got {!r}'.format(digest_bits)
+            )
+        if digest_bits % 40 != 0:
+            raise ValueError(
+                'digest_bits: must be multiple of 40; got {!r}'.format(
+                    digest_bits
+                )
+            )
+        self.leaf_size = leaf_size
+        self.digest_bits = digest_bits
+        self.digest_bytes = digest_bits // 8
+        self.digest_b32len = digest_bits // 5
+
+    def hash_leaf(self, leaf_index, leaf_data, challenge=b''):
+        """
+        Hash the leaf at (zero) index *leaf_index* containing *leaf_data*.
+
+        For example:
+
+        >>> p = Protocol(MiB, 200)
+        >>> b32encode(p.hash_leaf(0, b'The Leaf Data'))
+        b'EFBXKNNDAMRFIIPTIL2DYZ36YYQDAX54AAOYA7WG'
+
+        The optional *challenge* keyword argument should be a random nonce used
+        to make a remote cloud storage service prove that they actually have
+        the complete, exact file stored.  For example:
+
+        >>> b32encode(p.hash_leaf(0, b'The Leaf Data', b'Random Nonce'))
+        b'LBAECE4GW3UFXREWAFBMBGV2O4GISUTJ3ALZXGJW'
+
+        :param leaf_index: an ``int`` >= 0
+        :param leaf_data: a ``bytes`` instance with leaf content
+        :param challenge: a ``bytes`` instance containing a random nonce to be
+            used in a proof-of-storage challenge; default is ``b''``
+        """
+        if not isinstance(leaf_index, int):
+            raise TypeError(
+                TYPE_ERROR.format(
+                    'leaf_index', int, type(leaf_index), leaf_index
+                )
+            )
+        if leaf_index < 0:
+            raise ValueError(
+                'leaf_index: must be >= 0; got {!r}'.format(leaf_index)
+            )
+        if not isinstance(leaf_data, bytes):
+            raise TypeError(
+                TYPE_ERROR.format(
+                    'leaf_data', bytes, type(leaf_data), leaf_data
+                )
+            )
+        if not (1 <= len(leaf_data) <= self.leaf_size):
+            raise ValueError('Need 1 <= len(leaf_data) <= {}; got {}'.format(
+                    self.leaf_size, len(leaf_data)
+                )
+            )
+        digest = self._hash_leaf(leaf_index, leaf_data, challenge)
+        assert len(digest) == self.digest_bytes
+        return digest
+
+    def hash_root(self, file_size, leaf_hashes):
+        """
+        Return the root-hash for a file *file_size* bytes with *leaf_hashes*.
+
+        For example:
+
+        >>> p = Protocol(MiB, 200)
+        >>> p.hash_root(1776, b'DDDDDDDDDDDDDDDDDDDDDDDDD')
+        'SJGXSO43OF5424G6HAEG55X2SFCZRW7L7LG42UKN'
+
+        :param file_size: an ``int`` >= 1
+        :param leaf_hashes: a ``bytes`` instance containing the concatenated
+            leaf-hashes produced by `Protocol.hash_leaf()`.
+        """
+        if not isinstance(file_size, int):
+            raise TypeError(
+                TYPE_ERROR.format('file_size', int, type(file_size), file_size)
+            )
+        if file_size < 1:
+            raise ValueError(
+                'file_size: must be >= 1; got {!r}'.format(file_size)
+            )
+        if not isinstance(leaf_hashes, bytes):
+            raise TypeError(TYPE_ERROR.format(
+                    'leaf_hashes', bytes, type(leaf_hashes), leaf_hashes
+                )
+            )
+        if len(leaf_hashes) == 0:
+            raise ValueError('leaf_hashes cannot be empty')
+        if len(leaf_hashes) % self.digest_bytes != 0:
+            raise ValueError(
+                'len(leaf_hashes) is {}, not multiple of {}'.format(
+                    len(leaf_hashes), self.digest_bytes
+                )
+            )
+        n = len(leaf_hashes) // self.digest_bytes
+        low = (n - 1) * self.leaf_size + 1
+        high = n * self.leaf_size
+        if not (low <= file_size <= high):
+            raise ValueError(
+                'Need {} <= file_size <= {}; got {}'.format(
+                    low, high, file_size
+                )
+            )
+        digest = self._hash_root(file_size, leaf_hashes)
+        assert len(digest) == self.digest_bytes
+        b32digest = b32encode(digest).decode('utf-8')
+        assert len(b32digest) == self.digest_b32len
+        return b32digest
+
+    def _hash_leaf(self, leaf_index, leaf_data, challenge):
+        """
+        Protocol version 1 leaf-hashing implementation.
+
+        Subclasses can override this to use different hash functions,
+        configurations, etc.
+        """
+        assert leaf_index >= 0
+        assert 1 <= len(leaf_data) <= self.leaf_size
+        return skein512(leaf_data,
+            digest_bits=self.digest_bits,
+            pers=PERS_LEAF,
+            key=str(leaf_index).encode('utf-8'),
+            nonce=challenge,
+        ).digest()
+
+    def _hash_root(self, file_size, leaf_hashes):
+        """
+        Protocol version 1 root-hashing implementation.
+
+        Subclasses can override this to use different hash functions,
+        configurations, etc.
+        """
+        assert file_size >= 1
+        assert len(leaf_hashes) > 0
+        assert len(leaf_hashes) % self.digest_bytes == 0
+        return skein512(leaf_hashes,
+            digest_bits=self.digest_bits,
+            pers=PERS_ROOT,
+            key=str(file_size).encode('utf-8'),
+        ).digest()
+
+
+VERSION1 = Protocol(8 * MiB, 280)
+
+
+class OldProtocol(Protocol):
+    """
+    The unofficial version zero protocol.
+
+    Although no formal support commitments were ever made for this version zero
+    protocol, it has been used enough in the wild that we should really
+    continue to support it and provide a nice migration to the version one
+    protocol.
+    """
+
+    def _hash_leaf_index(self, leaf_index):
+        assert leaf_index >= 0
+        return skein512(str(leaf_index).encode('utf-8'),
+            digest_bits=self.digest_bits,
+            pers=PERS_LEAF_INDEX,
+        ).digest()
+
+    def _hash_leaf(self, leaf_index, leaf_data, challenge):
+        assert leaf_index >= 0
+        assert 1 <= len(leaf_data) <= self.leaf_size
+        skein = skein512(self._hash_leaf_index(leaf_index),
+            digest_bits=self.digest_bits,
+            pers=PERS_LEAF,
+            nonce=challenge,
+        )
+        skein.update(leaf_data)
+        return skein.digest()
+
+    def _hash_file_size(self, file_size):
+        assert file_size >= 1
+        return skein512(str(file_size).encode('utf-8'),
+            digest_bits=self.digest_bits,
+            pers=PERS_FILE_SIZE,
+        ).digest()
+
+    def _hash_root(self, file_size, leaf_hashes):
+        assert file_size >= 1
+        assert len(leaf_hashes) > 0
+        assert len(leaf_hashes) % self.digest_bytes == 0
+        skein = skein512(self._hash_file_size(file_size),
+            digest_bits=self.digest_bits,
+            pers=PERS_ROOT,
+        )
+        skein.update(leaf_hashes)
+        return skein.digest()
+
+
+VERSION0 = OldProtocol(8 * MiB, 240)
+
+PROTOCOLS = (VERSION0, VERSION1)

=== added directory 'filestore/tests'
=== renamed file 'test_filestore.py' => 'filestore/tests/__init__.py'
--- test_filestore.py	2012-12-11 12:48:03 +0000
+++ filestore/tests/__init__.py	2012-12-31 04:35:24 +0000
@@ -36,6 +36,8 @@
 
 from skein import skein512
 
+from filestore.protocols import PROTOCOLS, VERSION0, VERSION1
+from filestore import misc
 import filestore
 
 
@@ -595,242 +597,6 @@
         )
         self.assertEqual(len(accum), count)
 
-    def test_hash_leaf2(self):
-        # Test with wrong leaf_index type:
-        with self.assertRaises(TypeError) as cm:
-            filestore.hash_leaf2(0.0, None)
-        self.assertEqual(
-            str(cm.exception),
-            TYPE_ERROR.format('leaf_index', int, float, 0.0)
-        )
-        with self.assertRaises(TypeError) as cm:
-            filestore.hash_leaf2(1.5, None)
-        self.assertEqual(
-            str(cm.exception),
-            TYPE_ERROR.format('leaf_index', int, float, 1.5)
-        )
-
-        # Test with wrong leaf_index value
-        with self.assertRaises(ValueError) as cm:
-            filestore.hash_leaf2(-1, None)
-        self.assertEqual(
-            str(cm.exception),
-            'leaf_index: must be >= 0; got -1'
-        )
-        with self.assertRaises(ValueError) as cm:
-            filestore.hash_leaf2(-17, None)
-        self.assertEqual(
-            str(cm.exception),
-            'leaf_index: must be >= 0; got -17'
-        )
-
-        # Test with wrong leaf_data type
-        leaf_data = 'a' * 31415
-        with self.assertRaises(TypeError) as cm:
-            filestore.hash_leaf2(2, leaf_data)
-        self.assertEqual(
-            str(cm.exception),
-            TYPE_ERROR.format('leaf_data', bytes, str, leaf_data)
-        )
-
-        # Test with wrong leaf_data length
-        toosmall = b''
-        with self.assertRaises(ValueError) as cm:
-            filestore.hash_leaf2(2, toosmall)
-        self.assertEqual(
-            str(cm.exception),
-            'Need 1 <= len(leaf_data) <= 8388608; got 0'
-        )
-        toobig = b'a' * 8388609
-        with self.assertRaises(ValueError) as cm:
-            filestore.hash_leaf2(2, toobig)
-        self.assertEqual(
-            str(cm.exception),
-            'Need 1 <= len(leaf_data) <= 8388608; got 8388609'
-        )
-
-        # Test with good values:
-        leaf_data = b'D'
-        digest = filestore.hash_leaf2(0, leaf_data)
-        self.assertEqual(
-            digest,
-            skein512(leaf_data,
-                digest_bits=filestore.DIGEST_BITS,
-                pers=filestore.PERS_LEAF,
-                key=b'0',
-            ).digest()
-        )
-        leaf_data = b'D' * filestore.LEAF_SIZE
-        digest = filestore.hash_leaf2(0, leaf_data)
-        self.assertEqual(
-            digest,
-            skein512(leaf_data,
-                digest_bits=filestore.DIGEST_BITS,
-                pers=filestore.PERS_LEAF,
-                key=b'0',
-            ).digest()
-        )
-
-        # Test with challenge:
-        challenge = os.urandom(16)
-        leaf_data = b'D'
-        digest = filestore.hash_leaf2(0, leaf_data, challenge)
-        self.assertEqual(
-            digest,
-            skein512(leaf_data,
-                digest_bits=filestore.DIGEST_BITS,
-                pers=filestore.PERS_LEAF,
-                key=b'0',
-                nonce=challenge,
-            ).digest()
-        )
-        leaf_data = b'D' * filestore.LEAF_SIZE
-        digest = filestore.hash_leaf2(0, leaf_data, challenge)
-        self.assertEqual(
-            digest,
-            skein512(leaf_data,
-                digest_bits=filestore.DIGEST_BITS,
-                pers=filestore.PERS_LEAF,
-                key=b'0',
-                nonce=challenge,
-            ).digest()
-        )
-
-        # A 25k value sanity check on our crytographic claim that the
-        # leaf_index is tied to the leaf_hash:
-        count = 25 * 1000
-        leaf_data = os.urandom(16)
-        accum = set(
-            filestore.hash_leaf2(i, leaf_data)
-            for i in range(count)
-        )
-        self.assertEqual(len(accum), count)
-
-        # A 25k random value sanity check on our crytographic claim that the
-        # leaf_data is tied to the leaf_hash:
-        accum = set(
-            filestore.hash_leaf2(21, os.urandom(16))
-            for i in range(count)
-        )
-        self.assertEqual(len(accum), count)
-
-        # A 25k random value sanity check on our crytographic claim that the
-        # challenge is tied to the leaf_hash:
-        accum = set(
-            filestore.hash_leaf2(21, leaf_data, os.urandom(16))
-            for i in range(count)
-        )
-        self.assertEqual(len(accum), count)
-
-    def test_hash_root2(self):
-        # Test with wrong file_size type:
-        with self.assertRaises(TypeError) as cm:
-            filestore.hash_root2(1.0, None)
-        self.assertEqual(
-            str(cm.exception),
-            TYPE_ERROR.format('file_size', int, float, 1.0)
-        )
-        with self.assertRaises(TypeError) as cm:
-            filestore.hash_root2(1.5, None)
-        self.assertEqual(
-            str(cm.exception),
-            TYPE_ERROR.format('file_size', int, float, 1.5)
-        )
-
-        # Test with bad file_size value
-        with self.assertRaises(ValueError) as cm:
-            filestore.hash_root2(0, None)
-        self.assertEqual(
-            str(cm.exception),
-            'file_size: must be >= 1; got 0'
-        )
-        with self.assertRaises(ValueError) as cm:
-            filestore.hash_root2(-1, None)
-        self.assertEqual(
-            str(cm.exception),
-            'file_size: must be >= 1; got -1'
-        )
-
-        # Test with wrong leaf_hashes type:
-        leaf_hashes = 'A' * 30
-        with self.assertRaises(TypeError) as cm:
-            filestore.hash_root2(17, leaf_hashes)
-        self.assertEqual(
-            str(cm.exception),
-            TYPE_ERROR.format('leaf_hashes', bytes, str, leaf_hashes)
-        )
-
-        # Test with empty leaf_hashes
-        with self.assertRaises(ValueError) as cm:
-            filestore.hash_root2(17, b'')
-        self.assertEqual(str(cm.exception), 'leaf_hashes cannot be empty')
-
-        # Test when len(leaf_hashes) is not a multiple of DIGEST_BYTES
-        with self.assertRaises(ValueError) as cm:
-            filestore.hash_root2(17, b'A' * 45)
-        self.assertEqual(
-            str(cm.exception),
-            'len(leaf_hashes) is 45, not multiple of 30'
-        )
-
-        # Test low and high bounds
-        with self.assertRaises(ValueError) as cm:
-            filestore.hash_root2(
-                filestore.LEAF_SIZE + 1,
-                b'a' * filestore.DIGEST_BYTES
-            )
-        self.assertEqual(
-            str(cm.exception),
-            'Need 1 <= file_size <= 8388608; got 8388609'
-        )
-        with self.assertRaises(ValueError) as cm:
-            filestore.hash_root2(
-                filestore.LEAF_SIZE,
-                b'ab' * filestore.DIGEST_BYTES
-            )
-        self.assertEqual(
-            str(cm.exception),
-            'Need 8388609 <= file_size <= 16777216; got 8388608'
-        )
-        with self.assertRaises(ValueError) as cm:
-            filestore.hash_root2(
-                2 * filestore.LEAF_SIZE + 1,
-                b'ab' * filestore.DIGEST_BYTES
-            )
-        self.assertEqual(
-            str(cm.exception),
-            'Need 8388609 <= file_size <= 16777216; got 16777217'
-        )
-
-        # Test with good file_size and leaf_hashes
-        leaf_hashes = b'D' * filestore.DIGEST_BYTES
-        self.assertEqual(
-            filestore.hash_root2(1, leaf_hashes),
-            'AGXSQ2KPM7IZTYFHGPOHPN5TKJV6A2S54RPH7GRZONKNOJLS'
-        )
-        self.assertEqual(
-            filestore.hash_root2(filestore.LEAF_SIZE, leaf_hashes),
-            'QSCEN5L4DVJBKNNLC34B7YQAQAHY43FNKWVD2ULQHRG3SUQ5'
-        )
-
-        # A 25k value sanity check on our crytographic claim that the
-        # file_size is tied to the root_hash:
-        count = 25 * 1000
-        leaf_hashes = os.urandom(filestore.DIGEST_BYTES)
-        accum = set(
-            filestore.hash_root2(size, leaf_hashes)
-            for size in range(1, count + 1)
-        )
-        self.assertEqual(len(accum), count)
-
-        # A 25k random value sanity check on our crytographic claim that the
-        # leaf_hashes are tied to the root_hash:
-        accum = set(
-            filestore.hash_root2(314159, os.urandom(filestore.DIGEST_BYTES))
-            for i in range(count)
-        )
-        self.assertEqual(len(accum), count)
-
     def test_check_leaf_hashes(self):
         # Test with wrong type:
         leaf_hashes = 'a' * 60
@@ -853,16 +619,44 @@
             filestore.check_leaf_hashes(leaf_hashes)
         self.assertIs(cm.exception.leaf_hashes, leaf_hashes)
 
-        # Test with good values
-        good = b'a' * 60
-        self.assertIs(filestore.check_leaf_hashes(good), good)
-
-        array = bytearray()
-        for x in range(256):
-            array.extend(x for i in range(30))
-        big = bytes(array)
-        self.assertEqual(len(big), 30 * 256)
-        self.assertIs(filestore.check_leaf_hashes(big), big)
+        # Test with good values:
+        good30 = os.urandom(30)
+        self.assertIs(filestore.check_leaf_hashes(good30), good30)
+        self.assertIs(
+            filestore.check_leaf_hashes(good30, protocol=VERSION0),
+            good30
+        )
+        good35 = os.urandom(35)
+        self.assertIs(
+            filestore.check_leaf_hashes(good35, protocol=VERSION1),
+            good35
+        )
+
+        # Test with wrong protocol version:
+        with self.assertRaises(filestore.LeafHashesError) as cm:
+            filestore.check_leaf_hashes(good30, protocol=VERSION1)
+        self.assertIs(cm.exception.leaf_hashes, good30)
+        with self.assertRaises(filestore.LeafHashesError) as cm:
+            filestore.check_leaf_hashes(good35, protocol=VERSION0)
+        self.assertIs(cm.exception.leaf_hashes, good35)
+
+        # Future proofing:
+        for protocol in PROTOCOLS:
+            good = os.urandom(protocol.digest_bytes)
+            self.assertIs(filestore.check_leaf_hashes(good, protocol), good)
+
+            good = os.urandom(18 * protocol.digest_bytes)
+            self.assertIs(filestore.check_leaf_hashes(good, protocol), good)
+
+            bad = os.urandom(protocol.digest_bytes + 1)
+            with self.assertRaises(filestore.LeafHashesError) as cm:
+                filestore.check_leaf_hashes(bad, protocol)
+            self.assertIs(cm.exception.leaf_hashes, bad)
+
+            bad = os.urandom(18 * protocol.digest_bytes - 1)
+            with self.assertRaises(filestore.LeafHashesError) as cm:
+                filestore.check_leaf_hashes(bad, protocol)
+            self.assertIs(cm.exception.leaf_hashes, bad)
 
     def test_check_root_hash(self):
         f = filestore.check_root_hash
@@ -893,6 +687,62 @@
             'OYESBWEZ4Y2AGSLMNZB4ZF75A2VG7NXVB4R25SSMRGXLN4CR'
         )
 
+    def test_check_root_hash2(self):
+        for protocol in PROTOCOLS:
+            file_size = protocol.leaf_size + 1
+            leaf0_hash = os.urandom(protocol.digest_bytes)
+            leaf1_hash = os.urandom(protocol.digest_bytes)
+            leaf_hashes = leaf0_hash + leaf1_hash
+            _id = protocol.hash_root(file_size, leaf_hashes)
+
+            # Everything is correct:
+            ch = filestore.check_root_hash(_id, file_size, leaf_hashes)
+            self.assertIsInstance(ch, filestore.ContentHash)
+            self.assertEqual(ch.id, _id)
+            self.assertEqual(ch.file_size, file_size)
+            self.assertEqual(ch.leaf_hashes, leaf_hashes)
+            self.assertEqual(ch, (_id, file_size, leaf_hashes))
+
+            # Everything is correct, unpack=True
+            ch = filestore.check_root_hash(_id, file_size, leaf_hashes,
+                unpack=True
+            )
+            self.assertIsInstance(ch, filestore.ContentHash)
+            self.assertEqual(ch.id, _id)
+            self.assertEqual(ch.file_size, file_size)
+            self.assertEqual(ch.leaf_hashes, (leaf0_hash, leaf1_hash))
+            self.assertEqual(ch, (_id, file_size, (leaf0_hash, leaf1_hash)))
+
+            # Wrong ID:
+            bad_id = random_id(protocol.digest_bytes)
+            with self.assertRaises(filestore.RootHashError) as cm:
+                filestore.check_root_hash(bad_id, file_size, leaf_hashes)
+            self.assertEqual(cm.exception.id, bad_id)
+            self.assertEqual(cm.exception.file_size, file_size)
+            self.assertEqual(cm.exception.leaf_hashes, leaf_hashes)
+            self.assertEqual(cm.exception.bad_id, _id)
+
+            # Wrong file_size:
+            with self.assertRaises(filestore.RootHashError) as cm:
+                filestore.check_root_hash(_id, file_size + 1, leaf_hashes)
+            self.assertEqual(cm.exception.id, _id)
+            self.assertEqual(cm.exception.file_size, file_size + 1)
+            self.assertEqual(cm.exception.leaf_hashes, leaf_hashes)
+            self.assertEqual(cm.exception.bad_id,
+                protocol.hash_root(file_size + 1, leaf_hashes)
+            )
+
+            # Wrong leaf_hashes
+            bad_leaf_hashes = leaf0_hash + os.urandom(protocol.digest_bytes)
+            with self.assertRaises(filestore.RootHashError) as cm:
+                filestore.check_root_hash(_id, file_size, bad_leaf_hashes)
+            self.assertEqual(cm.exception.id, _id)
+            self.assertEqual(cm.exception.file_size, file_size)
+            self.assertEqual(cm.exception.leaf_hashes, bad_leaf_hashes)
+            self.assertEqual(cm.exception.bad_id,
+                protocol.hash_root(file_size, bad_leaf_hashes)
+            )
+
     def test_enumerate_leaf_hashes(self):
         f = filestore.enumerate_leaf_hashes
         self.assertEqual(
@@ -1011,28 +861,39 @@
 
     def test_check_id(self):
         # Test with wrong type
+        bad = random_id(30).encode('utf-8')
         with self.assertRaises(TypeError) as cm:
-            filestore.check_id(42)
+            filestore.check_id(bad)
         self.assertEqual(
             str(cm.exception),
-            TYPE_ERROR.format('_id', str, int, 42)
+            TYPE_ERROR.format('_id', str, bytes, bad)
         )
 
-        # Test with invalid base32 encoding:
-        bad = 'NWBNVXVK5DQGIOW7MYR4K3KA5K22W7N'
-        with self.assertRaises(filestore.IDError) as cm:
-            filestore.check_id(bad)
-        self.assertIs(cm.exception.id, bad)
-
         # Test with wrong length:
-        bad = 'NWBNVXVK5DQGIOW7MYR4K3KA'
-        with self.assertRaises(filestore.IDError) as cm:
-            filestore.check_id(bad)
-        self.assertIs(cm.exception.id, bad)
-
-        # Test with a good chash:
-        good = 'DHS36R6HGG52TQRB6BN7N66EWOPU4H67WISD3J6TWNCXXAZT'
-        self.assertIs(filestore.check_id(good), good)
+        for i in range(321):
+            value = 'N' * i
+            if len(value) in (48, 56):
+                self.assertIs(filestore.check_id(value), value)
+                continue
+            with self.assertRaises(filestore.IDError) as cm:
+                filestore.check_id(value)
+            self.assertIs(cm.exception.id, value)
+
+        # Test with 48 and 56 character:
+        id48 = random_id(30)
+        self.assertIs(filestore.check_id(id48), id48)
+        id56 = random_id(35)
+        self.assertIs(filestore.check_id(id56), id56)
+
+        # Test case sensitivity:
+        bad48 = id48.lower()
+        with self.assertRaises(filestore.IDError) as cm:
+            filestore.check_id(bad48)
+        self.assertIs(cm.exception.id, bad48)
+        bad56 = id56.lower()
+        with self.assertRaises(filestore.IDError) as cm:
+            filestore.check_id(bad56)
+        self.assertIs(cm.exception.id, bad56)
 
     def test_iter_files(self):
         """
@@ -1486,6 +1347,31 @@
         src_fp = open(dst, 'rb')
         self.assertEqual(filestore.hash_fp(src_fp), ch)
 
+    def test_hash_fp2(self):
+        obj = misc.load_test_vectors()
+        for proto in PROTOCOLS:
+            tmp = TempDir()
+            leaves = misc.build_test_leaves(proto.leaf_size)
+            vectors = obj[str(proto.digest_b32len)]
+            for (key, value) in vectors['root_hashes'].items():
+                name = tmp.join(key)
+                assert not path.exists(name)
+                fp = open(name, 'wb')
+                for L in key:
+                    fp.write(leaves[L])
+                fp.close()
+                fp = open(name, 'rb')
+                ch = filestore.hash_fp(fp, protocol=proto)
+                self.assertIsInstance(ch, filestore.ContentHash)
+                self.assertEqual(ch.id, value)
+                self.assertEqual(ch.file_size, path.getsize(name))
+                self.assertEqual(ch.leaf_hashes,
+                    b''.join(
+                        misc.decode(vectors['leaf_hashes'][L][i])
+                        for (i, L) in enumerate(key)
+                    )
+                )
+
     def test_ensuredir(self):
         f = filestore.ensuredir
         tmp = TempDir()
@@ -1747,7 +1633,7 @@
             os.chmod(f, stat.S_IRUSR | stat.S_IRGRP | stat.S_IROTH)
             self.assertEqual(path.getsize(f), 7)
         self.assertEqual(list(fs), [])
-        long = tuple(random_id(35) for i in range(50))
+        long = tuple(random_id(40) for i in range(50))
         for _id in long:
             f = fs.join('files', _id[:2], _id[2:])
             assert not path.exists(f)
@@ -1788,10 +1674,26 @@
             assert path.isdir(fs.path(_id))
         self.assertEqual(list(fs), [])
 
-        # Now add valid files in
+        # Now add valid files in (48 character IDs)
         stats = []
         for i in range(2000):
-            _id = random_id()
+            _id = random_id(30)
+            size = i + 1
+            f = fs.path(_id)
+            assert not path.exists(f)
+            open(f, 'wb').write(b'N' * size)
+            os.chmod(f, stat.S_IRUSR | stat.S_IRGRP | stat.S_IROTH)
+            self.assertEqual(path.getsize(f), size)
+            st = filestore.Stat(_id, f, size, path.getmtime(f))
+            self.assertEqual(fs.stat(_id), st)
+            stats.append(st)
+        self.assertNotEqual(list(fs), stats)  # Sorting!
+        stats.sort(key=lambda s: s.id)
+        self.assertEqual(list(fs), stats)
+
+        # Add more valid files in (56 character IDs)
+        for i in range(1000):
+            _id = random_id(35)
             size = i + 1
             f = fs.path(_id)
             assert not path.exists(f)
@@ -2186,6 +2088,31 @@
         self.assertFalse(path.exists(canonical))
         self.assertTrue(path.isfile(corrupt))
 
+    def test_verify2(self):
+        tmp = TempDir()
+        fs = filestore.FileStore(tmp.dir)
+        obj = misc.load_test_vectors()
+        for proto in PROTOCOLS:
+            leaves = misc.build_test_leaves(proto.leaf_size)
+            vectors = obj[str(proto.digest_b32len)]
+            for (key, value) in vectors['root_hashes'].items():
+                name = fs.path(value)
+                assert not path.exists(name)
+                fp = open(name, 'wb')
+                for L in key:
+                    fp.write(leaves[L])
+                fp.close()
+                ch = fs.verify(value)
+                self.assertIsInstance(ch, filestore.ContentHash)
+                self.assertEqual(ch.id, value)
+                self.assertEqual(ch.file_size, path.getsize(name))
+                self.assertEqual(ch.leaf_hashes,
+                    b''.join(
+                        misc.decode(vectors['leaf_hashes'][L][i])
+                        for (i, L) in enumerate(key)
+                    )
+                )
+
     def test_verify_iter(self):
         tmp = TempDir()
         fs = filestore.FileStore(tmp.dir)
@@ -2933,31 +2860,3 @@
         fs2.verify(ID)
         fs.verify(ID)
 
-
-class TestTempFileStore(TestCase):
-    def test_init(self):
-        fs = filestore.TempFileStore()
-        self.assertIsInstance(fs, filestore.FileStore)
-        self.assertTrue(fs.parentdir.startswith('/tmp/TempFileStore.'))
-        self.assertIsNone(fs.id)
-        self.assertEqual(fs.copies, 0)
-
-        fs = filestore.TempFileStore('foobar', 2)
-        self.assertIsInstance(fs, filestore.FileStore)
-        self.assertTrue(fs.parentdir.startswith('/tmp/TempFileStore.'))
-        self.assertEqual(fs.id, 'foobar')
-        self.assertEqual(fs.copies, 2)
-
-        fs = filestore.TempFileStore(_id='hooray', copies=3)
-        self.assertIsInstance(fs, filestore.FileStore)
-        self.assertTrue(fs.parentdir.startswith('/tmp/TempFileStore.'))
-        self.assertEqual(fs.id, 'hooray')
-        self.assertEqual(fs.copies, 3)
-
-    def test_del(self):
-        fs = filestore.TempFileStore()
-        parentdir = fs.parentdir
-        self.assertTrue(path.isdir(parentdir))
-        fs = None
-        self.assertFalse(path.exists(parentdir))
-

=== added file 'filestore/tests/test_misc.py'
--- filestore/tests/test_misc.py	1970-01-01 00:00:00 +0000
+++ filestore/tests/test_misc.py	2012-12-31 04:35:24 +0000
@@ -0,0 +1,150 @@
+# filestore: dmedia hashing protocol and file layout
+# Copyright (C) 2012 Novacut Inc
+#
+# This file is part of `filestore`.
+#
+# `filestore` is free software: you can redistribute it and/or modify it under
+# the terms of the GNU Affero General Public License as published by the Free
+# Software Foundation, either version 3 of the License, or (at your option) any
+# later version.
+#
+# `filestore` is distributed in the hope that it will be useful, but WITHOUT ANY
+# WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
+# A PARTICULAR PURPOSE.  See the GNU Affero General Public License for more
+# details.
+#
+# You should have received a copy of the GNU Affero General Public License along
+# with `filestore`.  If not, see <http://www.gnu.org/licenses/>.
+#
+# Authors:
+#   Jason Gerard DeRose <[e-mail]>
+
+"""
+Unit tests for `filestore.misc` module.
+"""
+
+from unittest import TestCase
+import os
+from os import path
+import json
+from base64 import b64encode
+
+import filestore
+from filestore.protocols import MiB, Protocol, VERSION0, VERSION1
+from filestore import misc
+
+
+class TestFunctions(TestCase):
+    def test_encode(self):
+        data = os.urandom(30)
+        self.assertEqual(
+            misc.encode(data),
+            b64encode(data).decode('utf-8')
+        )
+        data = os.urandom(35)
+        self.assertEqual(
+            misc.encode(data),
+            b64encode(data).decode('utf-8')
+        )
+
+    def test_load_test_vectors(self):
+        pkg = path.dirname(path.abspath(filestore.__file__))
+        self.assertTrue(path.isdir(pkg))
+        self.assertEqual(
+            misc.TEST_VECTORS,
+            path.join(pkg, 'data', 'test-vectors.json')
+        )
+        self.assertTrue(path.isfile(misc.TEST_VECTORS))
+        self.assertEqual(
+            misc.load_test_vectors(),
+            json.loads(open(misc.TEST_VECTORS, 'r').read())
+        )
+
+    def test_build_test_leaves(self):
+        obj = misc.build_test_leaves(MiB)
+        self.assertEqual(obj,
+            {
+                'A': b'A',
+                'B': b'B' * (MiB - 1),
+                'C': b'C' * MiB,
+            }
+        )
+        self.assertEqual(len(obj['A']), 1)
+        self.assertEqual(len(obj['B']), MiB - 1)
+        self.assertEqual(len(obj['C']), MiB)
+
+        obj = misc.build_test_leaves(2 * MiB)
+        self.assertEqual(obj,
+            {
+                'A': b'A',
+                'B': b'B' * (2 * MiB - 1),
+                'C': b'C' * (2 * MiB),
+            }
+        )
+        self.assertEqual(len(obj['A']), 1)
+        self.assertEqual(len(obj['B']), 2 * MiB - 1)
+        self.assertEqual(len(obj['C']), 2 * MiB)
+
+    def test_build_test_vectors(self):
+        proto = Protocol(MiB, 200)
+        leaves = misc.build_test_leaves(proto.leaf_size)
+        A0 = proto.hash_leaf(0, leaves['A'])
+        A1 = proto.hash_leaf(1, leaves['A'])
+        B0 = proto.hash_leaf(0, leaves['B'])
+        B1 = proto.hash_leaf(1, leaves['B'])
+        C0 = proto.hash_leaf(0, leaves['C'])
+        C1 = proto.hash_leaf(1, leaves['C'])
+        self.assertEqual(
+            misc.build_test_vectors(proto),
+            {
+                'leaf_hashes': {
+                    'A': [misc.encode(A0), misc.encode(A1)],
+                    'B': [misc.encode(B0), misc.encode(B1)],
+                    'C': [misc.encode(C0), misc.encode(C1)],
+                },
+                'root_hashes': {
+                    'A': proto.hash_root(1, A0),
+                    'B': proto.hash_root(MiB - 1, B0),
+                    'C': proto.hash_root(MiB, C0),
+                    'CA': proto.hash_root(MiB + 1, C0 + A1),
+                    'CB': proto.hash_root(2 * MiB - 1, C0 + B1),
+                    'CC': proto.hash_root(2 * MiB, C0 + C1),
+                }
+            }
+        )
+
+        self.assertEqual(
+            misc.load_test_vectors(),
+            {
+                '48': misc.build_test_vectors(VERSION0),
+                '56': misc.build_test_vectors(VERSION1),
+            }
+        )
+
+
+class TestTempFileStore(TestCase):
+    def test_init(self):
+        fs = misc.TempFileStore()
+        self.assertIsInstance(fs, filestore.FileStore)
+        self.assertTrue(fs.parentdir.startswith('/tmp/TempFileStore.'))
+        self.assertIsNone(fs.id)
+        self.assertEqual(fs.copies, 0)
+
+        fs = misc.TempFileStore('foobar', 2)
+        self.assertIsInstance(fs, filestore.FileStore)
+        self.assertTrue(fs.parentdir.startswith('/tmp/TempFileStore.'))
+        self.assertEqual(fs.id, 'foobar')
+        self.assertEqual(fs.copies, 2)
+
+        fs = misc.TempFileStore(_id='hooray', copies=3)
+        self.assertIsInstance(fs, filestore.FileStore)
+        self.assertTrue(fs.parentdir.startswith('/tmp/TempFileStore.'))
+        self.assertEqual(fs.id, 'hooray')
+        self.assertEqual(fs.copies, 3)
+
+    def test_del(self):
+        fs = misc.TempFileStore()
+        parentdir = fs.parentdir
+        self.assertTrue(path.isdir(parentdir))
+        fs = None
+        self.assertFalse(path.exists(parentdir))

=== added file 'filestore/tests/test_protocols.py'
--- filestore/tests/test_protocols.py	1970-01-01 00:00:00 +0000
+++ filestore/tests/test_protocols.py	2012-12-31 04:35:24 +0000
@@ -0,0 +1,1223 @@
+# filestore: dmedia hashing protocol and file layout
+# Copyright (C) 2012 Novacut Inc
+#
+# This file is part of `filestore`.
+#
+# `filestore` is free software: you can redistribute it and/or modify it under
+# the terms of the GNU Affero General Public License as published by the Free
+# Software Foundation, either version 3 of the License, or (at your option) any
+# later version.
+#
+# `filestore` is distributed in the hope that it will be useful, but WITHOUT ANY
+# WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
+# A PARTICULAR PURPOSE.  See the GNU Affero General Public License for more
+# details.
+#
+# You should have received a copy of the GNU Affero General Public License along
+# with `filestore`.  If not, see <http://www.gnu.org/licenses/>.
+#
+# Authors:
+#   Jason Gerard DeRose <[e-mail]>
+
+"""
+Unit tests for `filestore.protocols` module.
+"""
+
+from unittest import TestCase
+import os
+from base64 import b32encode, b32decode
+
+from skein import skein512
+
+from filestore.misc import decode
+from filestore import protocols
+
+
+MiB = 1024 * 1024
+EightMiB = 8 * MiB
+COUNT = 50 * 1000
+TYPE_ERROR = '{}: need a {!r}; got a {!r}: {!r}'
+
+A = b'A'
+B = b'B' * (EightMiB - 1)
+C = b'C' * EightMiB
+
+
+class ProtocolTestCase(TestCase):
+    def check_hash_leaf(self, proto):
+
+        # Test with wrong leaf_index type:
+        with self.assertRaises(TypeError) as cm:
+            proto.hash_leaf(0.0, None)
+        self.assertEqual(
+            str(cm.exception),
+            TYPE_ERROR.format('leaf_index', int, float, 0.0)
+        )
+        with self.assertRaises(TypeError) as cm:
+            proto.hash_leaf(1.5, None)
+        self.assertEqual(
+            str(cm.exception),
+            TYPE_ERROR.format('leaf_index', int, float, 1.5)
+        )
+
+        # Test with wrong leaf_index value
+        with self.assertRaises(ValueError) as cm:
+            proto.hash_leaf(-1, None)
+        self.assertEqual(
+            str(cm.exception),
+            'leaf_index: must be >= 0; got -1'
+        )
+        with self.assertRaises(ValueError) as cm:
+            proto.hash_leaf(-17, None)
+        self.assertEqual(
+            str(cm.exception),
+            'leaf_index: must be >= 0; got -17'
+        )
+
+        # Test with wrong leaf_data type
+        leaf_data = 'a' * 31415
+        with self.assertRaises(TypeError) as cm:
+            proto.hash_leaf(2, leaf_data)
+        self.assertEqual(
+            str(cm.exception),
+            TYPE_ERROR.format('leaf_data', bytes, str, leaf_data)
+        )
+
+        # Test with wrong leaf_data length
+        toosmall = b''
+        with self.assertRaises(ValueError) as cm:
+            proto.hash_leaf(2, toosmall)
+        self.assertEqual(
+            str(cm.exception),
+            'Need 1 <= len(leaf_data) <= {}; got 0'.format(proto.leaf_size)
+        )
+        toobig = b'a' * (proto.leaf_size + 1)
+        with self.assertRaises(ValueError) as cm:
+            proto.hash_leaf(2, toobig)
+        self.assertEqual(
+            str(cm.exception),
+            'Need 1 <= len(leaf_data) <= {}; got {}'.format(
+                proto.leaf_size, proto.leaf_size + 1
+            )
+        )
+
+        # Smallest possible leaf, index=0
+        accum = set()
+        leaf_data = b'D'
+        digest = proto.hash_leaf(0, leaf_data)
+        accum.add(digest)
+        self.assertEqual(proto._hash_leaf(0, leaf_data, b''), digest)
+
+        # Smallest possible leaf, index=1
+        digest = proto.hash_leaf(1, leaf_data)
+        self.assertNotIn(digest, accum)
+        accum.add(digest)
+        self.assertEqual(proto._hash_leaf(1, leaf_data, b''), digest)
+
+        # Largest possible leaf, index=0
+        leaf_data = b'D' * proto.leaf_size
+        digest = proto.hash_leaf(0, leaf_data)
+        self.assertNotIn(digest, accum)
+        accum.add(digest)
+        self.assertEqual(proto._hash_leaf(0, leaf_data, b''), digest)
+
+        # Largest possible leaf, index=1
+        digest = proto.hash_leaf(1, leaf_data)
+        self.assertNotIn(digest, accum)
+        accum.add(digest)
+        self.assertEqual(proto._hash_leaf(1, leaf_data, b''), digest)
+
+        # Test with challenge, smallest leaf, index=0:
+        challenge = os.urandom(16)
+        leaf_data = b'D'
+        digest = proto.hash_leaf(0, leaf_data, challenge)
+        self.assertNotIn(digest, accum)
+        accum.add(digest)
+        self.assertEqual(proto._hash_leaf(0, leaf_data, challenge), digest)
+
+        # Test with challenge, smallest leaf, index=1:
+        digest = proto.hash_leaf(1, leaf_data, challenge)
+        self.assertNotIn(digest, accum)
+        accum.add(digest)
+        self.assertEqual(proto._hash_leaf(1, leaf_data, challenge), digest)
+
+        # Test with challenge, largest leaf, index=0:
+        leaf_data = b'D' * proto.leaf_size
+        digest = proto.hash_leaf(0, leaf_data, challenge)
+        self.assertNotIn(digest, accum)
+        accum.add(digest)
+        self.assertEqual(proto._hash_leaf(0, leaf_data, challenge), digest)
+
+        # Test with challenge, largest leaf, index=1:
+        digest = proto.hash_leaf(1, leaf_data, challenge)
+        self.assertNotIn(digest, accum)
+        accum.add(digest)
+        self.assertEqual(proto._hash_leaf(1, leaf_data, challenge), digest)
+
+        # Make sure we didn't goof
+        self.assertEqual(len(accum), 8)
+
+    def check_hash_root(self, proto):
+        # Test with wrong file_size type:
+        with self.assertRaises(TypeError) as cm:
+            proto.hash_root(1.0, None)
+        self.assertEqual(
+            str(cm.exception),
+            TYPE_ERROR.format('file_size', int, float, 1.0)
+        )
+        with self.assertRaises(TypeError) as cm:
+            proto.hash_root(1.5, None)
+        self.assertEqual(
+            str(cm.exception),
+            TYPE_ERROR.format('file_size', int, float, 1.5)
+        )
+
+        # Test with bad file_size value
+        with self.assertRaises(ValueError) as cm:
+            proto.hash_root(0, None)
+        self.assertEqual(
+            str(cm.exception),
+            'file_size: must be >= 1; got 0'
+        )
+        with self.assertRaises(ValueError) as cm:
+            proto.hash_root(-1, None)
+        self.assertEqual(
+            str(cm.exception),
+            'file_size: must be >= 1; got -1'
+        )
+
+        # Test with wrong leaf_hashes type:
+        leaf_hashes = 'A' * proto.digest_bytes
+        with self.assertRaises(TypeError) as cm:
+            proto.hash_root(17, leaf_hashes)
+        self.assertEqual(
+            str(cm.exception),
+            TYPE_ERROR.format('leaf_hashes', bytes, str, leaf_hashes)
+        )
+
+        # Test with empty leaf_hashes
+        with self.assertRaises(ValueError) as cm:
+            proto.hash_root(17, b'')
+        self.assertEqual(str(cm.exception), 'leaf_hashes cannot be empty')
+
+        # Test when len(leaf_hashes) is not a multiple of Protocol.digest_bytes
+        with self.assertRaises(ValueError) as cm:
+            proto.hash_root(17, b'A' * (proto.digest_bytes + 1))
+        self.assertEqual(
+            str(cm.exception),
+            'len(leaf_hashes) is {}, not multiple of {}'.format(
+                proto.digest_bytes + 1, proto.digest_bytes
+            )
+        )
+
+        # Test low and high bounds
+        with self.assertRaises(ValueError) as cm:
+            proto.hash_root(proto.leaf_size + 1, b'a' * proto.digest_bytes)
+        self.assertEqual(
+            str(cm.exception),
+            'Need 1 <= file_size <= {}; got {}'.format(
+                proto.leaf_size, proto.leaf_size + 1
+            )
+        )
+        with self.assertRaises(ValueError) as cm:
+            proto.hash_root(proto.leaf_size, b'ab' * proto.digest_bytes)
+        self.assertEqual(
+            str(cm.exception),
+            'Need {} <= file_size <= {}; got {}'.format(
+                proto.leaf_size + 1,
+                2 * proto.leaf_size,
+                proto.leaf_size
+            )
+        )
+        with self.assertRaises(ValueError) as cm:
+            proto.hash_root(
+                2 * proto.leaf_size + 1,
+                b'ab' * proto.digest_bytes
+            )
+        self.assertEqual(
+            str(cm.exception),
+            'Need {} <= file_size <= {}; got {}'.format(
+                proto.leaf_size + 1,
+                2 * proto.leaf_size,
+                2 * proto.leaf_size + 1
+            )
+        )
+
+        # Test with good file_size and leaf_hashes
+        accum = set()
+        leaf_hashes = b'D' * proto.digest_bytes
+        _id = proto.hash_root(1, leaf_hashes)
+        self.assertNotIn(_id, accum)
+        accum.add(_id)
+        self.assertEqual(
+            proto._hash_root(1, leaf_hashes),
+            b32decode(_id.encode('utf-8'))
+        )
+
+        _id = proto.hash_root(2, leaf_hashes)
+        self.assertNotIn(_id, accum)
+        accum.add(_id)
+        self.assertEqual(
+            proto._hash_root(2, leaf_hashes),
+            b32decode(_id.encode('utf-8'))
+        )
+
+        leaf_hashes = b'AB' * proto.digest_bytes
+        _id = proto.hash_root(proto.leaf_size + 1, leaf_hashes)
+        self.assertNotIn(_id, accum)
+        accum.add(_id)
+        self.assertEqual(
+            proto._hash_root(proto.leaf_size + 1, leaf_hashes),
+            b32decode(_id.encode('utf-8'))
+        )
+
+        _id = proto.hash_root(proto.leaf_size + 2, leaf_hashes)
+        self.assertNotIn(_id, accum)
+        accum.add(_id)
+        self.assertEqual(
+            proto._hash_root(proto.leaf_size + 2, leaf_hashes),
+            b32decode(_id.encode('utf-8'))
+        )
+
+        # Make sure we didn't goof
+        self.assertEqual(len(accum), 4)
+
+    def sanity_check_hash_leaf(self, proto):
+        """
+        Random value sanity check on Protocol._hash_leaf().
+        """
+
+        # Sanity check on our crytographic claim that the
+        # leaf-hash is tied to the leaf-index:
+        leaf_data = os.urandom(16)
+        accum = set(
+            proto._hash_leaf(i, leaf_data, b'')
+            for i in range(COUNT)
+        )
+        self.assertEqual(len(accum), COUNT)
+
+        # Sanity check on our crytographic claim that the
+        # leaf-hash is tied to the leaf-data:
+        accum = set(
+            proto._hash_leaf(21, os.urandom(16), b'')
+            for i in range(COUNT)
+        )
+        self.assertEqual(len(accum), COUNT)
+
+        # Sanity check on our crytographic claim that the
+        # leaf-hash is tied to the challenge:
+        accum = set(
+            proto._hash_leaf(21, leaf_data, os.urandom(16))
+            for i in range(COUNT)
+        )
+        self.assertEqual(len(accum), COUNT)
+
+    def sanity_check_hash_root(self, proto):
+        """
+        Random value sanity check on Protocol._hash_root().
+        """
+
+        # Sanity check on our crytographic claim that the
+        # root-hash is tied to the file-size:
+        leaf_hashes = os.urandom(proto.digest_bytes)
+        accum = set(
+            proto._hash_root(size, leaf_hashes)
+            for size in range(1, COUNT + 1)
+        )
+        self.assertEqual(len(accum), COUNT)
+
+        # Sanity check on our crytographic claim that the
+        # root-hash is tied to the leaf-hashes:
+        accum = set(
+            proto._hash_root(314159, os.urandom(proto.digest_bytes))
+            for i in range(COUNT)
+        )
+        self.assertEqual(len(accum), COUNT)
+
+
+class TestProtocol(ProtocolTestCase):
+    def test_init(self):
+        # Wrong `leaf_size` type:
+        with self.assertRaises(TypeError) as cm:
+            protocols.Protocol(1.0 * MiB, 200)
+        self.assertEqual(
+            str(cm.exception),
+            TYPE_ERROR.format('leaf_size', int, float, 1.0 * MiB)
+        )
+
+        # leaf_size < MiB:
+        with self.assertRaises(ValueError) as cm:
+            protocols.Protocol(MiB - 1, 200)
+        self.assertEqual(
+            str(cm.exception),
+            'leaf_size: must be >= MiB; got {!r}'.format(MiB - 1)
+        )
+
+        # leaf_size % MiB != 0:
+        with self.assertRaises(ValueError) as cm:
+            protocols.Protocol(MiB * 3 // 2, 200)
+        self.assertEqual(
+            str(cm.exception),
+            'leaf_size: must be multiple of MiB; got {!r}'.format(MiB * 3 // 2)
+        )
+
+        # Wrong `digest_bits` type:
+        with self.assertRaises(TypeError) as cm:
+            protocols.Protocol(MiB, 200.0)
+        self.assertEqual(
+            str(cm.exception),
+            TYPE_ERROR.format('digest_bits', int, float, 200.0)
+        )
+
+        # digest_bits < 200:
+        with self.assertRaises(ValueError) as cm:
+            protocols.Protocol(MiB, 159)
+        self.assertEqual(
+            str(cm.exception),
+            'digest_bits: must be >= 200; got 159'
+        )
+
+        # digest_bits % 40 != 0:
+        with self.assertRaises(ValueError) as cm:
+            protocols.Protocol(MiB, 220)
+        self.assertEqual(
+            str(cm.exception),
+            'digest_bits: must be multiple of 40; got 220'
+        )
+
+        # Test with the good minimum values:
+        proto = protocols.Protocol(MiB, 200)
+        self.assertEqual(proto.leaf_size, MiB)
+        self.assertEqual(proto.digest_bits, 200)
+        self.assertEqual(proto.digest_bytes, 25)
+        self.assertEqual(proto.digest_b32len, 40)
+
+        # Test with the actual v0 protocol values:
+        proto = protocols.Protocol(8 * MiB, 240)
+        self.assertEqual(proto.leaf_size, 8 * MiB)
+        self.assertEqual(proto.digest_bits, 240)
+        self.assertEqual(proto.digest_bytes, 30)
+        self.assertEqual(proto.digest_b32len, 48)
+
+        # Test with the actual v1 protocol values:
+        proto = protocols.Protocol(8 * MiB, 280)
+        self.assertEqual(proto.leaf_size, 8 * MiB)
+        self.assertEqual(proto.digest_bits, 280)
+        self.assertEqual(proto.digest_bytes, 35)
+        self.assertEqual(proto.digest_b32len, 56)
+
+    def test_hash_leaf(self):
+        proto = protocols.Protocol(MiB, 200)
+        self.check_hash_leaf(proto)
+        self.sanity_check_hash_leaf(proto)
+
+        # Smallest possible leaf, index=0
+        accum = set()
+        leaf_data = b'D'
+        digest = proto.hash_leaf(0, leaf_data)
+        accum.add(digest)
+        self.assertEqual(
+            digest,
+            skein512(leaf_data,
+                digest_bits=200,
+                pers=protocols.PERS_LEAF,
+                key=b'0',
+            ).digest()
+        )
+        self.assertEqual(proto._hash_leaf(0, leaf_data, b''), digest)
+
+        # Smallest possible leaf, index=1
+        digest = proto.hash_leaf(1, leaf_data)
+        self.assertNotIn(digest, accum)
+        accum.add(digest)
+        self.assertEqual(
+            digest,
+            skein512(leaf_data,
+                digest_bits=200,
+                pers=protocols.PERS_LEAF,
+                key=b'1',
+            ).digest()
+        )
+        self.assertEqual(proto._hash_leaf(1, leaf_data, b''), digest)
+
+        # Largest possible leaf, index=0
+        leaf_data = b'D' * MiB
+        digest = proto.hash_leaf(0, leaf_data)
+        self.assertNotIn(digest, accum)
+        accum.add(digest)
+        self.assertEqual(
+            digest,
+            skein512(leaf_data,
+                digest_bits=200,
+                pers=protocols.PERS_LEAF,
+                key=b'0',
+            ).digest()
+        )
+        self.assertEqual(proto._hash_leaf(0, leaf_data, b''), digest)
+
+        # Largest possible leaf, index=1
+        digest = proto.hash_leaf(1, leaf_data)
+        self.assertNotIn(digest, accum)
+        accum.add(digest)
+        self.assertEqual(
+            digest,
+            skein512(leaf_data,
+                digest_bits=200,
+                pers=protocols.PERS_LEAF,
+                key=b'1',
+            ).digest()
+        )
+        self.assertEqual(proto._hash_leaf(1, leaf_data, b''), digest)
+
+        # Test with challenge, smallest leaf, index=0:
+        challenge = os.urandom(16)
+        leaf_data = b'D'
+        digest = proto.hash_leaf(0, leaf_data, challenge)
+        self.assertNotIn(digest, accum)
+        accum.add(digest)
+        self.assertEqual(
+            digest,
+            skein512(leaf_data,
+                digest_bits=200,
+                pers=protocols.PERS_LEAF,
+                key=b'0',
+                nonce=challenge,
+            ).digest()
+        )
+        self.assertEqual(proto._hash_leaf(0, leaf_data, challenge), digest)
+
+        # Test with challenge, smallest leaf, index=1:
+        digest = proto.hash_leaf(1, leaf_data, challenge)
+        self.assertNotIn(digest, accum)
+        accum.add(digest)
+        self.assertEqual(
+            digest,
+            skein512(leaf_data,
+                digest_bits=200,
+                pers=protocols.PERS_LEAF,
+                key=b'1',
+                nonce=challenge,
+            ).digest()
+        )
+        self.assertEqual(proto._hash_leaf(1, leaf_data, challenge), digest)
+
+        # Test with challenge, largest leaf, index=0:
+        leaf_data = b'D' * MiB
+        digest = proto.hash_leaf(0, leaf_data, challenge)
+        self.assertNotIn(digest, accum)
+        accum.add(digest)
+        self.assertEqual(
+            digest,
+            skein512(leaf_data,
+                digest_bits=200,
+                pers=protocols.PERS_LEAF,
+                key=b'0',
+                nonce=challenge,
+            ).digest()
+        )
+        self.assertEqual(proto._hash_leaf(0, leaf_data, challenge), digest)
+
+        # Test with challenge, largest leaf, index=1:
+        digest = proto.hash_leaf(1, leaf_data, challenge)
+        self.assertNotIn(digest, accum)
+        accum.add(digest)
+        self.assertEqual(
+            digest,
+            skein512(leaf_data,
+                digest_bits=200,
+                pers=protocols.PERS_LEAF,
+                key=b'1',
+                nonce=challenge,
+            ).digest()
+        )
+        self.assertEqual(proto._hash_leaf(1, leaf_data, challenge), digest)
+
+        # Make sure we didn't goof
+        self.assertEqual(len(accum), 8)
+
+    def test_hash_root(self):
+        proto = protocols.Protocol(MiB, 200)
+        self.check_hash_root(proto)
+        self.sanity_check_hash_root(proto)
+
+        accum = set()
+
+        # Smallest file-size possible for one leaf:
+        leaf_hashes = b'D' * 25
+        digest = proto._hash_root(1, leaf_hashes)
+        self.assertNotIn(digest, accum)
+        accum.add(digest)
+        self.assertEqual(
+            digest,
+            skein512(leaf_hashes,
+                digest_bits=200,
+                pers=protocols.PERS_ROOT,
+                key=b'1',
+            ).digest()
+        )
+        self.assertEqual(
+            proto.hash_root(1, leaf_hashes),
+            b32encode(digest).decode('utf-8')
+        )
+
+        # Largest file-size possible for one leaf:
+        digest = proto._hash_root(MiB, leaf_hashes)
+        self.assertNotIn(digest, accum)
+        accum.add(digest)
+        self.assertEqual(
+            digest,
+            skein512(leaf_hashes,
+                digest_bits=200,
+                pers=protocols.PERS_ROOT,
+                key=b'1048576',
+            ).digest()
+        )
+        self.assertEqual(
+            proto.hash_root(MiB, leaf_hashes),
+            b32encode(digest).decode('utf-8')
+        )
+
+        # Smallest file-size possible for two leaves:
+        leaf_hashes = b'D' * 50
+        digest = proto._hash_root(MiB + 1, leaf_hashes)
+        self.assertNotIn(digest, accum)
+        accum.add(digest)
+        self.assertEqual(
+            digest,
+            skein512(leaf_hashes,
+                digest_bits=200,
+                pers=protocols.PERS_ROOT,
+                key=b'1048577',
+            ).digest()
+        )
+        self.assertEqual(
+            proto.hash_root(MiB + 1, leaf_hashes),
+            b32encode(digest).decode('utf-8')
+        )
+
+        # Largest file-size possible for two leaves:
+        digest = proto._hash_root(2 * MiB, leaf_hashes)
+        self.assertNotIn(digest, accum)
+        accum.add(digest)
+        self.assertEqual(
+            digest,
+            skein512(leaf_hashes,
+                digest_bits=200,
+                pers=protocols.PERS_ROOT,
+                key=b'2097152',
+            ).digest()
+        )
+        self.assertEqual(
+            proto.hash_root(2 * MiB, leaf_hashes),
+            b32encode(digest).decode('utf-8')
+        )
+
+        # Make sure we didn't goof
+        self.assertEqual(len(accum), 4)
+
+
+class TestVersionOne(ProtocolTestCase):
+
+    def test_hash_leaf(self):
+        proto = protocols.VERSION1
+
+        self.check_hash_leaf(proto)
+        self.sanity_check_hash_leaf(proto)
+
+        # A0
+        digest = proto._hash_leaf(0, A, b'')
+        self.assertEqual(digest, 
+            decode('vnqPKTOknItURAuVQi5gHml2ncDDv/apR7CRbZ8Gw57L9S0=')
+        )
+        self.assertEqual(
+            digest,
+            skein512(A,
+                digest_bits=280,
+                pers=protocols.PERS_LEAF,
+                key=b'0',
+            ).digest()
+        )
+        self.assertEqual(proto.hash_leaf(0, A), digest)
+
+        # A1
+        digest = proto._hash_leaf(1, A, b'')
+        self.assertEqual(digest, 
+            decode('mQX/95lrNeZNnsQKj02VnNXIqgRjwGnqLoZoF9EHkmmhjjs=')
+        )
+        self.assertEqual(
+            digest,
+            skein512(A,
+                digest_bits=280,
+                pers=protocols.PERS_LEAF,
+                key=b'1',
+            ).digest()
+        )
+        self.assertEqual(proto.hash_leaf(1, A), digest)
+
+        # B0
+        digest = proto._hash_leaf(0, B, b'')
+        self.assertEqual(digest, 
+            decode('f776qpuQhQO1EWR1nrUCIxD9+sIqTcBb2AgJ6iOK8Gq8bIg=')
+        )
+        self.assertEqual(
+            digest,
+            skein512(B,
+                digest_bits=280,
+                pers=protocols.PERS_LEAF,
+                key=b'0',
+            ).digest()
+        )
+        self.assertEqual(proto.hash_leaf(0, B), digest)
+
+        # B1
+        digest = proto._hash_leaf(1, B, b'')
+        self.assertEqual(digest, 
+            decode('ygruy07GH5BRvrwtO2TCGCdxGjpOG/ogF+8sytiTYihTfsw=')
+        )
+        self.assertEqual(
+            digest,
+            skein512(B,
+                digest_bits=280,
+                pers=protocols.PERS_LEAF,
+                key=b'1',
+            ).digest()
+        )
+        self.assertEqual(proto.hash_leaf(1, B), digest)
+
+        # C0
+        digest = proto._hash_leaf(0, C, b'')
+        self.assertEqual(digest, 
+            decode('jbRklQZ8C9suPd0Ar/5vO2JVMoHEQ62ksuG1EsYtPbzr8FE=')
+        )
+        self.assertEqual(
+            digest,
+            skein512(C,
+                digest_bits=280,
+                pers=protocols.PERS_LEAF,
+                key=b'0',
+            ).digest()
+        )
+        self.assertEqual(proto.hash_leaf(0, C), digest)
+
+        # C1
+        digest = proto._hash_leaf(1, C, b'')
+        self.assertEqual(digest, 
+            decode('uGq34DS/oD0NT0zxWl562rYAUBbqeRZDvNtg0YDujBPzBGQ=')
+        )
+        self.assertEqual(
+            digest,
+            skein512(C,
+                digest_bits=280,
+                pers=protocols.PERS_LEAF,
+                key=b'1',
+            ).digest()
+        )
+        self.assertEqual(proto.hash_leaf(1, C), digest)
+
+    def test_hash_root(self):
+        proto = protocols.VERSION1
+
+        self.check_hash_root(proto)
+        self.sanity_check_hash_root(proto)
+
+        A0 = decode('vnqPKTOknItURAuVQi5gHml2ncDDv/apR7CRbZ8Gw57L9S0=')
+        A1 = decode('mQX/95lrNeZNnsQKj02VnNXIqgRjwGnqLoZoF9EHkmmhjjs=')
+        B0 = decode('f776qpuQhQO1EWR1nrUCIxD9+sIqTcBb2AgJ6iOK8Gq8bIg=')
+        B1 = decode('ygruy07GH5BRvrwtO2TCGCdxGjpOG/ogF+8sytiTYihTfsw=')
+        C0 = decode('jbRklQZ8C9suPd0Ar/5vO2JVMoHEQ62ksuG1EsYtPbzr8FE=')
+        C1 = decode('uGq34DS/oD0NT0zxWl562rYAUBbqeRZDvNtg0YDujBPzBGQ=')
+
+        # A
+        digest = proto._hash_root(1, A0)
+        self.assertEqual(
+            b32encode(digest).decode('utf-8'),
+            'FWV6OJYI36C5NN5DC4GS2IGWZXFCZCGJGHK35YV62LKAG7D2Z4LO4Z2S'
+        )
+        self.assertEqual(
+            digest,
+            skein512(A0,
+                digest_bits=280,
+                pers=protocols.PERS_ROOT,
+                key=b'1',
+            ).digest()
+        )
+        self.assertEqual(
+            proto.hash_root(1, A0),
+            b32encode(digest).decode('utf-8')
+        )
+
+        # B
+        digest = proto._hash_root(8388607, B0)
+        self.assertEqual(
+            b32encode(digest).decode('utf-8'),
+            'OB756PX5V32JMKJAFKIAJ4AFSFPA2WLNIK32ELNO4FJLJPEEEN6DCAAJ'
+        )
+        self.assertEqual(
+            digest,
+            skein512(B0,
+                digest_bits=280,
+                pers=protocols.PERS_ROOT,
+                key=b'8388607',
+            ).digest()
+        )
+        self.assertEqual(
+            proto.hash_root(8388607, B0),
+            b32encode(digest).decode('utf-8')
+        )
+
+        # C
+        digest = proto._hash_root(8388608, C0)
+        self.assertEqual(
+            b32encode(digest).decode('utf-8'),
+            'QSOHXCDH64IQBOG2NM67XEC6MLZKKPGBTISWWRPMCFCJ2EKMA2SMLY46'
+        )
+        self.assertEqual(
+            digest,
+            skein512(C0,
+                digest_bits=280,
+                pers=protocols.PERS_ROOT,
+                key=b'8388608',
+            ).digest()
+        )
+        self.assertEqual(
+            proto.hash_root(8388608, C0),
+            b32encode(digest).decode('utf-8')
+        )
+
+        # CA
+        digest = proto._hash_root(8388609, C0 + A1)
+        self.assertEqual(
+            b32encode(digest).decode('utf-8'),
+            'BQ5UTB33ML2VDTCTLVXK6N4VSMGGKKKDYKG24B6DOAFJB6NRSGMB5BNO'
+        )
+        self.assertEqual(
+            digest,
+            skein512(C0 + A1,
+                digest_bits=280,
+                pers=protocols.PERS_ROOT,
+                key=b'8388609',
+            ).digest()
+        )
+        self.assertEqual(
+            proto.hash_root(8388609, C0 + A1),
+            b32encode(digest).decode('utf-8')
+        )
+
+        # CB
+        digest = proto._hash_root(16777215, C0 + B1)
+        self.assertEqual(
+            b32encode(digest).decode('utf-8'),
+            'ER3LDDZ2LHMTDLOPE5XA5GEEZ6OE45VFIFLY42GEMV4TSZ2B7GJJXAIX'
+        )
+        self.assertEqual(
+            digest,
+            skein512(C0 + B1,
+                digest_bits=280,
+                pers=protocols.PERS_ROOT,
+                key=b'16777215',
+            ).digest()
+        )
+        self.assertEqual(
+            proto.hash_root(16777215, C0 + B1),
+            b32encode(digest).decode('utf-8')
+        )
+
+        # CC
+        digest = proto._hash_root(16777216, C0 + C1)
+        self.assertEqual(
+            b32encode(digest).decode('utf-8'),
+            'R6RN5KL7UBNJWR5SK5YPUKIGAOWWFMYYOVESU5DPT34X5MEK75PXXYIX'
+        )
+        self.assertEqual(
+            digest,
+            skein512(C0 + C1,
+                digest_bits=280,
+                pers=protocols.PERS_ROOT,
+                key=b'16777216',
+            ).digest()
+        )
+        self.assertEqual(
+            proto.hash_root(16777216, C0 + C1),
+            b32encode(digest).decode('utf-8')
+        )
+
+
+class TestOldProtocol(TestCase):
+    def test_hash_leaf_index(self):
+        proto = protocols.OldProtocol(MiB, 200)
+        accum = set()
+        key = proto._hash_leaf_index(0)
+        accum.add(key)
+        self.assertEqual(key,
+            skein512(b'0',
+                digest_bits=200,
+                pers=protocols.PERS_LEAF_INDEX,
+            ).digest()
+        )
+
+        key = proto._hash_leaf_index(17)
+        self.assertNotIn(key, accum)
+        accum.add(key)
+        self.assertEqual(key,
+            skein512(b'17',
+                digest_bits=200,
+                pers=protocols.PERS_LEAF_INDEX,
+            ).digest()
+        )
+        self.assertEqual(len(accum), 2)
+
+        count = 25 * 1000
+        accum = set(
+            proto._hash_leaf_index(i) for i in range(count)
+        )
+        self.assertEqual(len(accum), count)
+
+        #############################################
+        # Again, this time with different digest_bits
+        proto = protocols.OldProtocol(MiB, 240)
+        accum = set()
+        key = proto._hash_leaf_index(0)
+        accum.add(key)
+        self.assertEqual(key,
+            skein512(b'0',
+                digest_bits=240,
+                pers=protocols.PERS_LEAF_INDEX,
+            ).digest()
+        )
+
+        key = proto._hash_leaf_index(17)
+        self.assertNotIn(key, accum)
+        accum.add(key)
+        self.assertEqual(key,
+            skein512(b'17',
+                digest_bits=240,
+                pers=protocols.PERS_LEAF_INDEX,
+            ).digest()
+        )
+        self.assertEqual(len(accum), 2)
+
+        count = 25 * 1000
+        accum = set(
+            proto._hash_leaf_index(i) for i in range(count)
+        )
+        self.assertEqual(len(accum), count)
+
+    def test_hash_leaf(self):
+        challenge = b'secret foo bar'
+        proto = protocols.OldProtocol(MiB, 200)
+        key0 = proto._hash_leaf_index(0)
+        key17 = proto._hash_leaf_index(17)
+
+        accum = set()
+
+        # Min leaf size, index=0
+        leaf_data = b'D'
+        digest = proto._hash_leaf(0, leaf_data, b'')
+        self.assertNotIn(digest, accum)
+        accum.add(digest)
+        self.assertEqual(digest,
+            skein512(key0 + leaf_data,
+                digest_bits=200,
+                pers=protocols.PERS_LEAF,
+            ).digest()
+        )
+
+        # Min leaf size, index=17
+        digest = proto._hash_leaf(17, leaf_data, b'')
+        self.assertNotIn(digest, accum)
+        accum.add(digest)
+        self.assertEqual(digest,
+            skein512(key17 + leaf_data,
+                digest_bits=200,
+                pers=protocols.PERS_LEAF,
+            ).digest()
+        )
+
+        # With challenge, min leaf size, index=0
+        digest = proto._hash_leaf(0, leaf_data, challenge)
+        self.assertNotIn(digest, accum)
+        accum.add(digest)
+        self.assertEqual(digest,
+            skein512(key0 + leaf_data,
+                digest_bits=200,
+                pers=protocols.PERS_LEAF,
+                nonce=challenge,
+            ).digest()
+        )
+
+        # With challenge, min leaf size, index=17
+        digest = proto._hash_leaf(17, leaf_data, challenge)
+        self.assertNotIn(digest, accum)
+        accum.add(digest)
+        self.assertEqual(digest,
+            skein512(key17 + leaf_data,
+                digest_bits=200,
+                pers=protocols.PERS_LEAF,
+                nonce=challenge,
+            ).digest()
+        )
+
+        # Max leaf size, index=0
+        leaf_data = b'D' * MiB
+        digest = proto._hash_leaf(0, leaf_data, b'')
+        self.assertNotIn(digest, accum)
+        accum.add(digest)
+        self.assertEqual(digest,
+            skein512(key0 + leaf_data,
+                digest_bits=200,
+                pers=protocols.PERS_LEAF,
+            ).digest()
+        )
+
+        # Max leaf size, index=17
+        digest = proto._hash_leaf(17, leaf_data, b'')
+        self.assertNotIn(digest, accum)
+        accum.add(digest)
+        self.assertEqual(digest,
+            skein512(key17 + leaf_data,
+                digest_bits=200,
+                pers=protocols.PERS_LEAF,
+            ).digest()
+        )
+
+        # With challenge, max leaf size, index=0
+        digest = proto._hash_leaf(0, leaf_data, challenge)
+        self.assertNotIn(digest, accum)
+        accum.add(digest)
+        self.assertEqual(digest,
+            skein512(key0 + leaf_data,
+                digest_bits=200,
+                pers=protocols.PERS_LEAF,
+                nonce=challenge,
+            ).digest()
+        )
+
+        # With challenge, max leaf size, index=17
+        digest = proto._hash_leaf(17, leaf_data, challenge)
+        self.assertNotIn(digest, accum)
+        accum.add(digest)
+        self.assertEqual(digest,
+            skein512(key17 + leaf_data,
+                digest_bits=200,
+                pers=protocols.PERS_LEAF,
+                nonce=challenge,
+            ).digest()
+        )
+
+        # Make sure we didn't goof:
+        self.assertEqual(len(accum), 8)
+
+        # A 25k value sanity check on our crytographic claim that the
+        # leaf-hash is tied to the leaf-index:
+        count = 25 * 1000
+        leaf_data = os.urandom(32)
+        accum = set(
+            proto._hash_leaf(i, leaf_data, b'')
+            for i in range(count)
+        )
+        self.assertEqual(len(accum), count)
+
+        # A 25k random value sanity check on our crytographic claim that the
+        # leaf-hash is tied to the leaf-data:
+        accum = set(
+            proto._hash_leaf(21, os.urandom(32), b'')
+            for i in range(count)
+        )
+        self.assertEqual(len(accum), count)
+
+        # A 25k random value sanity check on our crytographic claim that the
+        # leaf-hash is tied to the challenge:
+        accum = set(
+            proto._hash_leaf(21, leaf_data, os.urandom(16))
+            for i in range(count)
+        )
+        self.assertEqual(len(accum), count)
+
+    def test_hash_file_size(self):
+        proto = protocols.OldProtocol(MiB, 200)
+        accum = set()
+
+        key = proto._hash_file_size(1)
+        self.assertNotIn(key, accum)
+        accum.add(key)
+        self.assertEqual(key,
+            skein512(b'1',
+                digest_bits=200,
+                pers=protocols.PERS_FILE_SIZE,
+            ).digest()
+        )
+
+        key = proto._hash_file_size(18)
+        self.assertNotIn(key, accum)
+        accum.add(key)
+        self.assertEqual(key,
+            skein512(b'18',
+                digest_bits=200,
+                pers=protocols.PERS_FILE_SIZE,
+            ).digest()
+        )
+        self.assertEqual(len(accum), 2)
+
+        count = 25 * 1000
+        accum = set(
+            proto._hash_file_size(size) for
+            size in range(1, count + 1)
+        )
+        self.assertEqual(len(accum), count)
+
+        #############################################
+        # Again, this time with different digest_bits
+        proto = protocols.OldProtocol(MiB, 240)
+        accum = set()
+
+        key = proto._hash_file_size(1)
+        self.assertNotIn(key, accum)
+        accum.add(key)
+        self.assertEqual(key,
+            skein512(b'1',
+                digest_bits=240,
+                pers=protocols.PERS_FILE_SIZE,
+            ).digest()
+        )
+
+        key = proto._hash_file_size(18)
+        self.assertNotIn(key, accum)
+        accum.add(key)
+        self.assertEqual(key,
+            skein512(b'18',
+                digest_bits=240,
+                pers=protocols.PERS_FILE_SIZE,
+            ).digest()
+        )
+        self.assertEqual(len(accum), 2)
+
+        count = 25 * 1000
+        accum = set(
+            proto._hash_file_size(size) for
+            size in range(1, count + 1)
+        )
+        self.assertEqual(len(accum), count)
+
+    def test_hash_root(self):
+        proto = protocols.OldProtocol(MiB, 200)
+        key1 = proto._hash_file_size(1)
+        key18 = proto._hash_file_size(18)
+        keyM = proto._hash_file_size(MiB)
+        keyM1 = proto._hash_file_size(MiB + 1)
+        keyM18 = proto._hash_file_size(MiB + 18)
+        key2M = proto._hash_file_size(2 * MiB)
+
+        accum = set()
+
+        # One leaf, file_size=1
+        leaf_hashes = b'D' * 25
+        digest = proto._hash_root(1, leaf_hashes)
+        self.assertNotIn(digest, accum)
+        accum.add(digest)
+        self.assertEqual(digest,
+            skein512(key1 + leaf_hashes,
+                digest_bits=200,
+                pers=protocols.PERS_ROOT,
+            ).digest()
+        )
+        self.assertEqual(
+            proto.hash_root(1, leaf_hashes),
+            b32encode(digest).decode('utf-8')
+        )
+
+        # One leaf, file_size=18
+        digest = proto._hash_root(18, leaf_hashes)
+        self.assertNotIn(digest, accum)
+        accum.add(digest)
+        self.assertEqual(digest,
+            skein512(key18 + leaf_hashes,
+                digest_bits=200,
+                pers=protocols.PERS_ROOT,
+            ).digest()
+        )
+        self.assertEqual(
+            proto.hash_root(18, leaf_hashes),
+            b32encode(digest).decode('utf-8')
+        )
+
+        # One leaf, file_size=MiB
+        digest = proto._hash_root(MiB, leaf_hashes)
+        self.assertNotIn(digest, accum)
+        accum.add(digest)
+        self.assertEqual(digest,
+            skein512(keyM + leaf_hashes,
+                digest_bits=200,
+                pers=protocols.PERS_ROOT,
+            ).digest()
+        )
+        self.assertEqual(
+            proto.hash_root(MiB, leaf_hashes),
+            b32encode(digest).decode('utf-8')
+        )
+
+        # Two leaves, file_size=(MiB + 1)
+        leaf_hashes = b'D' * 50
+        digest = proto._hash_root(MiB + 1, leaf_hashes)
+        self.assertNotIn(digest, accum)
+        accum.add(digest)
+        self.assertEqual(digest,
+            skein512(keyM1 + leaf_hashes,
+                digest_bits=200,
+                pers=protocols.PERS_ROOT,
+            ).digest()
+        )
+        self.assertEqual(
+            proto.hash_root(MiB + 1, leaf_hashes),
+            b32encode(digest).decode('utf-8')
+        )
+
+        # Two leaves, file_size=(MiB + 18)
+        digest = proto._hash_root(MiB + 18, leaf_hashes)
+        self.assertNotIn(digest, accum)
+        accum.add(digest)
+        self.assertEqual(digest,
+            skein512(keyM18 + leaf_hashes,
+                digest_bits=200,
+                pers=protocols.PERS_ROOT,
+            ).digest()
+        )
+        self.assertEqual(
+            proto.hash_root(MiB + 18, leaf_hashes),
+            b32encode(digest).decode('utf-8')
+        )
+
+        # Two leaves, file_size=(2 * MiB)
+        digest = proto._hash_root(2 * MiB, leaf_hashes)
+        self.assertNotIn(digest, accum)
+        accum.add(digest)
+        self.assertEqual(digest,
+            skein512(key2M + leaf_hashes,
+                digest_bits=200,
+                pers=protocols.PERS_ROOT,
+            ).digest()
+        )
+        self.assertEqual(
+            proto.hash_root(2 * MiB, leaf_hashes),
+            b32encode(digest).decode('utf-8')
+        )
+
+        # Make sure we didn't goof:
+        self.assertEqual(len(accum), 6)
+
+        # A 25k value sanity check on our crytographic claim that the
+        # root-hash is tied to the file-size:
+        count = 25 * 1000
+        leaf_hashes = b'D' * 25
+        accum = set(
+            proto._hash_root(size, leaf_hashes)
+            for size in range(1, count + 1)
+        )
+        self.assertEqual(len(accum), count)
+
+        # A 25k random value sanity check on our crytographic claim that the
+        # root-hash is tied to the leaf-hashes:
+        accum = set(
+            proto._hash_root(21, os.urandom(25))
+            for i in range(count)
+        )
+        self.assertEqual(len(accum), count)

=== modified file 'setup.py'
--- setup.py	2012-11-01 06:15:22 +0000
+++ setup.py	2012-12-31 04:35:24 +0000
@@ -49,7 +49,14 @@
         pass
 
     def run(self):
-        pynames = ['filestore', 'test_filestore']
+        pynames = [
+            'filestore',
+            'filestore.protocols',
+            'filestore.misc',
+            'filestore.tests',
+            'filestore.tests.test_protocols',
+            'filestore.tests.test_misc'
+        ]
 
         # Add unit-tests:
         loader = TestLoader()
@@ -77,7 +84,8 @@
     author='Jason Gerard DeRose',
     author_email='[e-mail]',
     license='AGPLv3+',
-    py_modules=['filestore'],
+    packages=['filestore', 'filestore.tests'],
+    package_data={'filestore': ['data/test-vectors.json']},
     scripts=['dmediasum'],
     cmdclass={'test': Test},
     ext_modules=[_filestore],