简介
Trillian 是 Google 对 Verifiable Data Structures 白皮书中描述的算法的一个实现，它也是 Certificate Transparency 的扩展和通用性实现。
Trillian 实现了一个梅克尔树（Merkle Tree），这个树中保存的内容来自于存储层的数据，并且这棵树的扩展性非常好。Trillian 在这颗树的基础上提供了两种操作模式：
- Log 模式 (append-only)
这个模式跟原始的 Certificate Transparency logs 类似。在这个模式下，梅克尔书从左子树开始填充，最后会形成一颗 dense 树。 - Map 模式 (key/value pairs)
在这个模式下，允许透明地存储任意的 Key:Value 对。Key 的哈希值被用来表示一颗很深的梅克尔书的叶节点，这种情况下就会形成一颗 sparse 树。
注：Trillian Map 是一个无序 map，不允许遍历 key）
Trillian 设计特点
1） Trillian 通过 grpc 来提供服务，通过 get/set 接口来获取存储在数据库（比如 MySQL）中的相应的 Merkle tree 数据，确保 Tree 的保密特性。
2） Trillian 实现了多租户，单个 Trillian 的安装可以同时支持多个 Merkle tree 的存在，通过它们的 TreeID 来区分。
Personality 特征
Trillian 服务需要配合实现其他代码来适应透明的存储，这个就叫 Personality。
Personality 的主要目的是实现一个“准入标准”：只有符合特定类型要求的数据才可以加入到 store。比如，对于一个 certificate transparency log 来说，只有是有效的 certificate 才会被接受。
personality 也可以对进入的数据进行标准化，这样，可以避免数据的无效重复。
注意：personality 需要使用自己单独的数据库来保存数据，与 Trillian 独立开来。尤其，在 personality 不完全信任 Trillian 的时候，它需要把 Trillian 签名过的东西存起来以便检测问题，因此，这种情况下，personality 实际上扮演的是 monitor 的作用。
Map 模式
Triilian 运行在 Map 模式下的时候，可以认为是提供了一个 key:value store，但是提供了一个数据加密透明性的安全保障。
提供的服务就是 get/set，比如 GetLeaves，SetLeaves，GetSignedMapRoot 等。
只有一个接口会修改数据库的数据，就是 SetLeaves，这个请求可以包含一批更新，一旦所有的更新完成，这个 Map 就会有一个新的版本 revision，这个版本会有一个新的 tree head
Log 模式
当运行在 Log 模式的时候，Trillian 提供了类似 Certificate Transparency logs （RFC 6962）所提供的服务。包括：
- GetLastestSignedLogRoot
- GetLeavesByHash 和 GetLeavesByIndex
- QueueLeaves
- GetInclusionProof，GetInclusionProofByHash， GetConsistencyProof
在 Log 模式下，Trillian 增加了一个额外的 Signer 模块，这个组件会会周期性的处理 pending queued items，把逐个把它们加到 Merkle tree 上，最终生成一个 signed tree head 作为结果。
用例
1. CT Log， Certificate Transparency Log
Trillian Log Mode 最明显的应用就是 CT Log（RFC 6962），要实现它，CT Log personality 需要包含所有跟 certificate 相关的处理，比如，确定某个 item 可以被包含进一个 tree root 之前，它需要确实是一个 valide certificate。
2. 可验证的 Log-Derived Map
Verifiable log derived map，VLDM，又叫 Log-Backed Map。要实现它，一个 VLDM personality 需要监控任何时候对 log 增加一条记录，同时，在 map 中也写入相应的 key:value pair。
然后，VLDM 的 client 可以验证，在 Map 中出现的 entries 同时可以被任何人通过检查 Log 来验证操作的正确性，然后反过来允许 Client 更加信任由 Map 返回的 key:value parit。
一个 VLDM 具体的例子是，监控一个 certificate transparency log，同时根据 log 中的域名信息和 certificate 的对应来建立一个 map。
