sumfolder1 0.0.2

sumfolder1 is a utility for use within the archival and digital preservation community to generate checksums for file system directories, and to generate an overall "collection" checksum for a given set of files.

• Why?
  • Archival questions
  • Structural questions
  • Forensics questions
• How?
  • Reference set
  • Reference implementation
  • Merkle trees
  • Terminology
  • New folder attributes
  • Sensitivity
• DROID
  • DROID in Siegfried
  • DROID as an inspiration
  • Writing about sumfolder1
• Installation
• Usage
  • Demo output
  • Use with a DROID csv
  • Outputting the reference CSV
• License

Why?

Conventionally, checksums exist for files, they do not exist for directories. They have no payload that can be summed together to calculate a digest/checksum.

If it were possible to create checksums for folders or a global checksum for a collection of objects, it would become possible to ask the following:

Archival questions

• What is the collection checksum for a given set of files and folders?
• What is the checksum for a given folder?
• Given a collection of objects online, am I looking at an authentic listing?
• Have I downloaded a collection in its entirety?

Structural questions

• Is file/folder hash(x) included in the collection set?
• Is file/folder hash(y) (non-existent) part of the entire set?
• Is file hash(x) part of folder(y) where the collection has arbitrary depth?
• Where are duplicate checksums located within a collection?

Forensics questions

• Has a digital object been removed from the collection?
• Did the collection contain at least one empty directory?

How?

Given a set of file paths and existing checksums it is possible to compute a checksum for a folder by creating a checksum of the given checksums.

Given checksum 1) 7c1f9f9a4d0ce9a72ee63f37a1b7f694 and checksum 2) aececec0bc3f515039aec9e60c413cd3 an MD5 can be computed as: 82f9e9a4305714fffdd7932783980cbc.

We can see this illustrated for a small collection as follows:

📁 folder_1 82f9e9a4305714fffdd7932783980cbc
    📄 checksum_1 7c1f9f9a4d0ce9a72ee63f37a1b7f694
    📄 checksum_2 aececec0bc3f515039aec9e60c413cd3

If we follow this approach through an entire directory structure we can create checksums for all sub-directories and for the collection as a whole.

Reference set

A reference set is provided with this repository: reference set.

We can iterate through the directory tree to create sets of directory checksums and a collection checksum: 52b94608dc70813aa88dae01176dc73b.

The reference set then looks as follows:

📁 collection 93778c524035d5d3e429a2fe43b7700a
   📄 file_0001 14118ff9ad0344decb37960809b2f17a
   📄 file_0000 8cfda2609b880a553759cd6200823f3b
   📄 file_0002 a4501ee1a5c711ea9db78a800a24e830
   📁 sub_dir_1 82301616d7e24f474dbe21de93af0a34
      📄 file_empty d41d8cd98f00b204e9800998ecf8427e
      📄 file_0003 dc7f828c5fe622925181d06edada350f
      📄 file_0004 e3d90a4bf14a9b355f0e69ba08df522d
      📁 sub_1_dir_1 1c7ba27edf1356d097a3f568032430c2
         📄 file_0005 637a3fb7da1ab61d10e96336d9758416
   📁 sub_dir_2 1ccb49edc4e873f1a8affd4bad5e9b90
   📁 sub_dir_3 2a60541cede91a36e9dc5bab7a97dd6e
      📁 sub_3_empty_1 db9d848b4f83ff3cb3faa4df0a59e3e1
         📁 sub_3_empty_2 1ccb49edc4e873f1a8affd4bad5e9b90
   📁 sub_dir_4 272d45767d534335163f220c1d40e559
      📄 file_0006 2b43227486ec8744cd5d4c955d269743
      📄 file_0007 c5a1973a70e08bf1eee13b8090f790ad
      📄 file_0008 fdffe4dd2d39c7d9986dbf5c6ec5ad39
   📁 sub_dir_5 d818d29b75f89a9b5d8d1c5a4c70dbbb
      📁 sub_5_dir_1 82f9e9a4305714fffdd7932783980cbc
         📄 file_0009 7c1f9f9a4d0ce9a72ee63f37a1b7f694
         📄 file_0010 aececec0bc3f515039aec9e60c413cd3
   📁 sub_dir_6 74be16979710d4c4e7c6647856088456
      📄 file_empty d41d8cd98f00b204e9800998ecf8427e

Reference implementation

The reference implementation for sumfolder1 does the following:

From the lowest sub-directory in the tree:

1. Check for sub-directories and add the checksums for these to a hash digest in alphabetical order by checksum.
2. For files in the directory add these to the hash digest in alphabetical order by checksum.
3. Create a digest for the list of checksums.

Repeat, processing each folder backwards up to the top level.

NB. If a folder is completely empty it is assigned a constant value chosen in the code: 2600_EMPTY_DIRECTORY. This evaluates to an MD5 value of 1ccb49edc4e873f1a8affd4bad5e9b90.

Merkle trees

The concept I have used here is based on Merkle trees and a loose understanding of techniques used in the block-chain and in the source control system GitHub.

A good video summary of Merkle trees can be found on YouTube:

• Gaurav Sen on Merkle Trees

And a Python tutorial I found useful in starting this work:

• Dan Nolan on Merkle Trees

The technique required for a directory tree is a little more convoluted than that of a Merkle tree which uses binary nodes and evaluates checksums from left to right. I believe the implementation used for sumfolder1 is more closely aligned to that of a "Radix Tree" or "Patricia Tree", however, this is to be explored more.

NB. A merkle tree can be used in its context for performance; sumfolder1 does not yet have a performance use-case.

Terminology

The reference implementation introduces some terminology that helps with understanding the approach:

• Active-tree: the side of a directory tree that we're querying about a given hash.
• Non-active-tree: the tree at root node (Rn+1) that do not contain the digital object that we're querying.
• Root-node (Rn): the name of the top-level node, i.e. collection folder. This is either artificially created for a set of directories all at the same level, or exists as a function of the given collection set.

New folder attributes

Folder objects need to be given additional attributes to enable the algorithm to work.

• Folder-depth, so directories can be grouped and distinguished from one-another by level in the hierarchy.
• Hash, the goal of this tool is to enable a hash to be calculated for an entire collection.

Sensitivity

I am trying to make this code as portable as possible, i.e. while it works with DROID-style reports today, it might also work with other checksum-based outputs tomorrow. Additionally, to be able to compare folder structures, this utility may also work with DROID-style reports later on in a transfer workflow; at which point, folders and files may have been renamed, but their content remains consistent.

To calculate a single folder checksum we currently do the following:

• If there are folders in the directory, order their hashes alphabetically and add to a list.
• File checksums are then ordered alphabetically and added to the end of the list.
• The checksums are then summed together to create a new folder-level checksum.

DROID

sumfolder1 uses the DROID format identification report to generate folder level checksums.

DROID can be found at The National Archives UK website:

• DROID @ The National Archives

DROID in Siegfried

sumfolder1 can also be used with DROID compatible reports created by Siegfried using a command such as follows:

sf --hash=md5 --droid <collection_folder>

DROID as an inspiration

File format reports provide a means of statically analyzing collections of digital objects. A DROID report satisfies the pre-conditions required to create reliable folder- and collection-level checksums for digital collections:

• A collection is static, i.e. unlikely to change.
• Digital objects within the collection have checksums.

NB: A collection need not be static to be analyzed but it is not the primary use-case of this utility.

More information about the different uses for a file-format identification report can be found in my paper in the Code4Lib journal.

• Fractal in detail: What information is in a file format identification report?

Writing about sumfolder1

I wrote a blog describing the utility on the OPF website.

• What is the checksum of a directory?

Installation

sumfolder1 is available on pypi and can be installed as follows:

pip install -U sumfolder1

Usage

sumfolder1 has the following usage instructions:

usage: sumfolder1.py [-h] [--csv CSV] [--demo] [--ref] [-v]

Calculate checksums for folders in a collection of objects using a DROID format
identification report

options:
  -h, --help          show this help message and exit
  --csv CSV           Single DROID CSV to read.
  --demo              Run demo queries and output a tree to demo.txt
  --ref, --reference  Write reference set to stdout.
  -v, --version       Return version information.

Demo output

sumfolder1's demo output can be invoked as follows:

python sumfolder1 --demo

JSON will be output to stdout describing a handful of queries generated using the reference collection.

An visualization of the collection tree will be output (for demo purposes) to stderr.

Use with a DROID csv

Given a DROID csv the tool can be invoked as follows:

python sumfolder1 --csv <droid_csv_file>

Outputting the reference CSV

A reference CSV can be output to stdout. Ideally it is piped to some other file using a command such as follows:

python sumfolder1 --ref > <output_file>

License

This work is license using: GNU GENERAL PUBLIC LICENSE Version 3.