DOCSEARCHbyAlgolia
Submit Docs

Trillian Documentation

repository·master·Indexed 25 days ago

https://github.com/google/trillian

A high-performance implementation of verifiable data structures, specifically Merkle trees, used to build append-only transparency logs for Certificate Transparency (CT) and other verifiable logging applications. Includes guides for deploying to Kubernetes on GCP with Cloud Spanner, AWS with RDS MySQL, and tools like treetex for Merkle tree visualization and the Claimant Model Render Tool for design evaluation.

Tokens
35.8K
Snippets
59
Records
196
Agent score
86%

What's inside Trillian

  1. Overview of Trillian

    master

    Trillian is an implementation of verifiable data structures, specifically a Merkle tree designed for scalability. It provides an append-only Log mode (a dense Merkle tree) and requires applications to provide their own personalities on top of the core functionality.

    Note: Trillian is currently in maintenance mode. For new log operators, it is recommended to use Tessera and Tiled APIs instead.

  2. Understand Verifiable Maps in Trillian

    master

    A Verifiable Map is a mapping from a set of keys to a corresponding set of values. Trillian implements this using Sparse Merkle Trees (found in the experimental/batchmap package).

    Key Capabilities:

    • Enumerate Entries: Clients can list all key/value pairs in the map.
    • Inclusion/Non-inclusion Proofs: Given a map checkpoint and an inclusion proof, clients can verify if a value exists for a key or if a key is explicitly not present in the map at a specific point in time.

    Note on Security: Unlike logs, maps do not have an inherent way to efficiently verify the append-only property, making them more susceptible to split-view attacks unless used in conjunction with a Verifiable Log-Derived Map.

  3. Understand Trillian's architecture and tree modes

    master

    Trillian is a gRPC-based service that manages Merkle trees using a separate storage layer (currently MySQL). It is multi-tenanted, meaning a single installation can manage multiple trees simultaneously, each identified by a unique TreeId.

    Trillian supports two primary modes of operation:

    1. Log mode: An append-only collection of items. This includes two sub-modes:
      • Normal Log mode: The Trillian service automatically assigns sequence numbers to new entries.
      • Pre-ordered Log mode: The unique sequence number for entries is provided externally.
    2. Other modes: (Implicitly non-log modes, though Log mode is the primary focus for transparency applications).

    Key property: Trillian provides cryptographic proofs of inclusion and consistency for all data items added to the service.

  4. Understand the Log Transparency Claimant Model

    master

    Log Transparency is a pattern used to ensure the discoverability of Claims. It is intended for ecosystems where a Claimant Model (like Certificate Transparency) is already established and you need to ensure that any claim relied upon by a Believer can eventually be discovered and verified by a Verifier without relying on the Believer to report it.

    Core Principle: Any claim believed by any honest Believer must be eventually verified by an honest Verifier. Logs act as a verifiable transport mechanism to achieve this.

  5. Understand Trillian extension points

    master
    Trillian provides several extension points designed to allow for customization by forks. At runtime, implementations for these extensions are acquired through the extension.Registry. This registry contains the comprehensive list of all supported extensions available in the project.

  6. Understand Verifiable Log-Derived Maps (VLDM)

    master

    A Verifiable Log-Derived Map (VLDM) is a map created from a verifiable log in a deterministic and verifiable manner. This structure combines the convenience of map lookups with the consistency guarantees of an underlying log.

    How it works:

    1. Derivation: The map consumes log entries in order. The signed map checkpoint incorporates a specific log checkpoint, attesting that the map includes all entries committed to by that log checkpoint.
    2. Verification: Any party can download and replay the entire log to verify the map's correct behavior over time.
    3. Split-view Protection: To prevent split-view attacks, all signed map checkpoints should be published to a separate verifiable log called a Map Checkpoint Log (MCL). This ensures map checkpoints are globally visible and verifiable.

    Use Case Example: A Certificate Transparency monitor can expose a VLDM that maps domain names (keys) to X.509 certificates (values), derived from a Certificate Transparency log operated by a different party.

  7. Understand Tree Node Storage concepts

    master

    Trillian's node-level storage provides an abstract tree model used to implement verifiable logs and maps. The storage model provides a versioned view of the tree where each transaction results in a new, monotonically increasing revision number.

    Key concepts include:

    • NodeIDs: Unique identifiers combining a tree path (used as a bitwise subtree prefix) and a revision number. Note that while logs and maps use the same NodeID objects, they are interpreted differently; mixing them in API calls will cause incorrect results.
    • Subtree Stratification: An optimization where the tree is stored as a collection of subtrees rather than raw nodes. This improves space efficiency (approx. 50% saving) and read performance for Merkle paths.
    • Consistency: Storage implementations must provide strongly consistent updates. Users must never see partial updates or inconsistent views, though they may see an earlier version of the tree if updates haven't propagated.

  8. PostgreSQL storage implementation overview

    master
    Trillian provides a PostgreSQL storage implementation designed for high-throughput Certificate Transparency logs. It is optimized for performance and reliability, specifically addressing concerns like database corruption due to disk space exhaustion and sequencing throughput limitations found in other implementations. It uses the pgx driver directly instead of the standard database/sql interface to leverage PostgreSQL-specific features like the COPY command.

  9. Understand the Commit-Log based Trillian storage design

    master

    The commit-log based storage design is an alternative to the standard MySQL/Spanner storage layers. It uses a distributed, immutable commit log (e.g., Apache Kafka) as the canonical source of truth for a Trillian Log's contents and sequence, while using independent, read-only databases (e.g., Apache HBase or RocksDB) to serve queries.

    Key Benefits:

    • Scalability: Provides flexibility in scaling Trillian deployments.
    • Recovery: Allows for easier recovery from corrupt or failed database deployments. Operators can delete a failed database instance and rebuild it from the commit log without interrupting service from other instances.
    • Consistency Decoupling: Ensures Trillian is not exclusively tied to strong globally consistent storage engines.

    Core Requirements:

    1. A durable, ordered, and immutable commit log.
    2. A local storage mechanism capable of supporting the Trillian {tree,log}_storage API operations.

  10. Understand Verifiable Logs in Trillian

    master

    A Verifiable Log is an append-only data structure where entries can be added but never removed or changed. Trillian implements this using Merkle trees (as described in RFC6962).

    Key Capabilities:

    • Enumerate Entries: Clients can list all entries held in the log.
    • Inclusion Proofs: Given a log checkpoint and an inclusion proof, clients can verify that a specific entry exists in the log.
    • Consistency Proofs: Given two checkpoints, clients can verify the append-only property of the log.
    • Split-view Attack Detection: By using consistency proofs and a gossip protocol for checkpoints, clients can detect if a log is presenting different views to different parties.

  11. Available Log Storage Implementations

    master

    Trillian provides several storage implementations for logs. The following are currently usable:

    • MySQL/MariaDB: Available in the mysql/ package. This implementation includes support for Maps.
    • Cloud Spanner: Available in the cloudspanner package.
    • PostgreSQL: Available in the postgresql/ package (currently in beta mode).

    Other implementations include:

    • CockroachDB (crdb/ package): In alpha mode; not recommended for production.
    • In-memory Storage (memory package): For testing purposes only; do not use in real applications.

  12. Understand Trillian's Transparent Logging design

    master

    Trillian generalizes Certificate Transparency to allow for the transparent, append-only logging of arbitrary data. When designing a Log using Trillian, you must define the purpose of the log (the ecosystem) and the specific nature of the leaf contents.

    Key design considerations include:

    • Ecosystem: Determine if you need to build auditors, monitors, or indexes around your log.
    • Leaf Contents: Define what constitutes a single entry (e.g., a certificate, a binary package, or a text blob).
    • Admission Control: Decide how to handle duplicates or invalid entries.
    • Inclusion Proofs vs. Promises: Understand the distinction between proving data is in the tree versus promising it will be.