Crate merkle_tree_bulletin_board

Merkle tree based bulletin board

This is a library for a public bulletin board, allowing one to publish a series of messages, and occasional root hashes. It can then provide a proof that each element published before the root hash is referenced by the root hash. This is done via Merkle Trees.

It is a method of being open, specifically of allowing external people to verify the bulletin board. After entries are added, the board publishes a public root (256 bit hash). Different people can confirm that they are told the same hash to check that they are looking at the same bulletin board and are not getting shown different data. Anyone can find a proof that their data of interest is in the board; also anyone can retrieve the entire contents of the board and do whatever is wanted with it.

As an example application, imagine a public election (this is of no use for an election with private votes, which is of course often very important). Everyone submits their vote to a central “of course we are totally trustworthy” authority (CA). The CA then publishes a root hash, which everyone can telephone their friends to check is the same. Also, everyone can easily check that their vote is recorded correctly (in time logarithmic in the number of entries, that is, quickly). Also, anyone can check the total list of votes (in time proportional to the number of votes) and see that the announced tally is correct. This means that even people who do not trust the CA can still trust the result, because it is verifiable.

The basic idea is that the bulletin board keeps track of a collection of items that it commits to. These items are built up into a tree, where each node is labeled by a SHA256 hash. The root is periodically published publicly. Anyone can then check that the root hash proves any particular committed element is referenced to by asking for the section of the tree containing the path from said element to the root. Each committed element is a leaf node whose label is the hash of the element and a timestamp. Each non-root, non-leaf node has two children; it is labeled by the hash of its children. The root is a hash of its children and a timestamp. The path is a proof of inclusion as it would require inverting SHA256 to make a fraudulent path, and this is currently considered computationally infeasible.

The system allows censorship of individual leaves. This is obviously generally undesirable and to some extent undermines some of the point of a committed bulletin board. However, most if not all countries have censorship laws that require operators of bulletin boards to do censorship, regardless of whether or not you agree with such laws. The system is designed to have the following properties in the presence of censorship:

• Censorship does not invalidate any published root.
• Censorship, even post a published root, does not invalidate or even affect any proof chain other than the particular leaf being censored.
• Even the leaf being censored can still be verified should you happen to know what had been present before the censorship.
• It is impossible to hide the fact that a censorship post published root has occurred.
• If you do not use the censorship feature, then the overhead of having it present is negligible.

Censorship is accomplished by simply not providing the censored text; the leaf and its associated hash value (and timestamp) are still present. The hash value cannot be modified post published root, as that would invalidate the parent branch. The timestamp cannot however be verified unless you happen to know the uncensored text.

Modules

• backend_flatfile
  A backend for the database based on csv files.
• backend_journal
  A journalling backend for the database based on csv files.
• backend_memory
• deduce_journal
• growing_forest
  Build Merkle trees, incrementally.
• hash
  Define the hash algorithm and result used in this board. This is all boilerplate.
• hash_history
• verifier
  Rust verifier of the Merkle tree. Really you should write your own rather than trusting me… but consider this as documentation and testing.

Structs

• BulletinBoard
  This is the main API to the bulletin board library. This represents an entire bulletin board. You provide a backend of type BulletinBoardBackend (typically an indexed database), and it provides a suitable API.
• DatabaseTransaction
  Adding one element to a set to be committed may result in a variety of elements being produced. A database may have the ability to do transactions, in which case this can be made safer by committing all the modifications needed by a single API call so that the database doesn’t have dangling elements.

Enums

• BulletinBoardError
  Possible things that could go wrong during a Bulletin Board operation.

Traits

• BulletinBoardBackend
  The data from the bulletin board needs to be stored somewhere. Typically this will be a database, but for generality anything implementing this trait can be used.