Verifiable Data Structures

In June 2013, after seeing repeated breaches of internet trust due to flaws in the SSL certificate system, Google engineers published RFC6962, a draft internet standard known as Certificate Transparency that describes a standard for publicly verifiable append-only, logs that are used to vastly improve trust in the Certificate Authority ecosystem that underpins the security of the modern web.

In November 2015, the Google team responsible for Certificate Transparency published a paper (which the founder of Continusec co-authored) describing how the data structures used successfully in Certificate Transparency could be applied more generally to other applications.

The Verifiable Data Structures provided in this open-source project are an implementation of the verifiable logs and maps described in that paper.

What are Verifiable Logs?

A log is a list of records that is appended to over time, but not modified.

A Verifiable Log is a log that can prove the above properties. That is, a log that can prove that it is append-only, and that the entries are not tampered with.

Any organization that is responsible for the issuance of records benefits from verifiable logs. Whether those records are digital certificates, binary software artifacts that you ship, university degrees, access records, insurance policies or parking tickets, by requiring the records be verifiably logged in order to be considered valid, an organization can decrease the number of improperly issued records, since such issuance will be logged in tamper-proof systems, discouraging insider fraud as transparency leads to accountability.

What are Verifiable Maps?

A map is a store of key/value pairs, where the value for a key can change over time.

A Verifiable Map is a map that has the property that when returning the value for any key, the map can include an audit proof that proves the value returned is same as returned for any others that ask the same question, and that all mutations to that map are captured in a Verifiable Log that cannot be tampered with.

Many organizations are responsible for maintaining a registry that maps keys to values, where the values change over time. For example a bank will maintain a balance amount for each account number. A land registry will maintain ownership information for a specific parcel of property. A Certificate Authority will maintain state as to whether a certificate has been revoked or not. An organization may maintain a list of which public keys are in effect per user.

Known alternative implementations

Trillian, maintained by Google, is another implementation of the concepts within the Verifiable Data Structures paper.