Kelvin

一个默克尔树工具包和后端。

默克尔树和区块链

默克尔树使开发者能够以非常高效的方式将加密哈希函数应用于状态的庞大表示。正因为这一重要特性，默克尔树被广泛应用于各种去中心化应用中，在这些应用中，只有当网络节点能够确信整个系统的确切状态时，才能正确地实现独立实体的协调。在基于区块链的基础设施中，大型状态表示的例子包括未花费的交易输出、链历史、账户状态和智能合约存储。

在编写处理默克尔树的程序时，目前的做法是满足于一个底层数据结构（例如，智能合约平台的一个流行选择是 Patricia 或 Radix 树）。

大多数实现都使用了键值数据库后端（RocksDB、LevelDB），这些后端针对可变数据的存储进行了优化（即可能被更新或删除的数据），因此，为了允许跟踪缓存失效和高效更新，它们需要承担相当大的开销。这种额外的逻辑在区块链用例中纯粹是多余的复杂性，因为区块链的本质是只读存储不可变数据。

另一个问题是，大多数这些树实现与数据库后端的紧密耦合。这种做法的缺点是使这些实现变得不灵活，并且依赖于特定的数据库逻辑来进行回滚和事务处理。因此，改变和/或实现替代数据结构不可避免地会导致复杂性和努力和代码的重复，因为每个新的树结构都需要自己的数据库集成层。理想情况下，在事务失败的情况下，你应该能够简单地丢弃失败状态，并从之前的状态继续，开销非常低。

为了解决这些问题，并允许更快的数据结构建模和迭代，我们引入了 Kelvin！

动机

Kelvin 是一个库，旨在结合不可变数据结构、磁盘持久性和内容寻址树（即默克尔树）的优点。

在 DUSK 网络中，Kelvin 已经成为建模真正区块链优化数据结构不可或缺的工具，这些数据结构遍布许多需要状态表示的核心网络组件，从交易模型到智能合约引擎。Kelvin 允许我们避免为每次迭代分别实现存储和写时复制的繁琐工作。

数据结构逻辑与数据库后端的结构、使用的哈希函数甚至元数据注释是分离的。每个都可以单独优化和调整。

让我们首先了解这三个主题的背景知识，稍后再介绍它们是如何结合在一起的。

不可变数据结构

假设我们有一个这样的映射

{ a: 0, b: 1, c: 2, d: 3, e: 4 }

这可以用以下不可变数据结构来表示

现在，假设我们将映射中的 e 设置为 42，结果不可变结构可能看起来像这样

树的左侧节点实际上是我们的旧映射，它没有改变！右侧红色根节点是改变 e 后的新映射。如你所见，两个映射在指向没有改变的 b 和 c 所在的黄色节点方面具有相同的结构。

这就是如何高效地保留旧映射的副本，你只需为实际改变的树的部分支付存储和更新成本。

Clojure VS Rust

Clojure 在推广不可变数据结构概念方面发挥了重要作用，Clojure 的所有集合（映射/列表/集合）默认都是不可变的。尽管在大多数常见情况下性能足够好，但语言还支持所谓的 transient 数据结构。论点是，只要在修改期间没有其他线程能看到结构，就可以使用更高效的非复制方法。如果你熟悉 Rust，这可能会让你想起一些东西。

在 Rust 中，每个正在修改的数据结构已经是 transient 的，这是基于 &mut 引用的保证。这意味着，我们得到了两者的最佳结合！

磁盘持久化

在程序中保存状态最常见的方式是通过文件系统，通常用于日志和配置文件，或者某种类型的数据库。

但如果我们将我们漂亮的树直接保存到磁盘上会如何？如果你的程序状态可以表示为映射和集合的集合，为什么我们不能直接以它们现有的格式将它们写入磁盘呢？

让我们再次看看之前的例子，为什么根节点的子节点不能指向某种类型的磁盘表示？并在需要时加载和缓存？这正是 kelvin 的工作方式。

let mut state = ProgramState::new();

state.do_things_that_modify_state();

// Let's set up a store
let dir = tempdir().unwrap();
let store = Store::<Blake2b>::new(&dir.path());

// A snapshot is a hash and a reference to a Store
let snapshot = store.persist(&mut state).unwrap();

let mut restored = store.restore(&snapshot).unwrap();
// restored can now be used as a normal `ProgramState`

ProgramState 本身可以是不同映射的组合，稍后我们会详细讨论。

内容可寻址性

内容可寻址性是指使用加密哈希来引用字节流。在这种情况下，我们的 ProgramState 的序列化表示。这意味着，你用来查找数据的“键”就是该数据的表示。这有多个好处。

首先，你可以免费获得完整性检查，如果你通过其加密哈希查找已更改或损坏的数据，你会立即注意到。你还获得了去重。例如，如果你的状态包含多个等效映射，就像上面例子中的共享子树一样，它只会在磁盘上存储一次。

Merkle 树

Merkle 树正是这样，根节点只是其叶子节点和/或子树的哈希值的哈希。而且，正如 Merkle 树通常那样，kelvin 维护的结构也适用于构建 Merkle Proofs

自底向上的视图

那么，这是如何实现的，你需要如何调整你的程序状态以使用这个库？

内容特征

这个库的主要特征是 Content 特征。它简单地定义了如何将特定类型转换为/从字节转换。

我们未使用 serde，因为我们希望对类型施加额外的限制，例如要求类型能够实现 Clone、Eq 等功能。同时，我们还要确保哈希值映射总是 1-1。

/// The main trait for content-adressable types, MUST assure a 1-1 mapping between
/// values of the type and hash digests.
pub trait Content<H: ByteHash>
where
    Self: Sized + Clone + 'static + PartialEq + Eq,
{
    /// Write the type to a `Sink`
    fn persist(&mut self, sink: &mut Sink<H>) -> io::Result<()>;
    /// Restore the type from a `Source`
    fn restore(source: &mut Source<H>) -> io::Result<Self>;
}

就是这样！只需为您的状态实现此类型，您就可以创建状态的快照了！

复合特质

复合特质是为了创建自己的数据结构。目前 kelvin 只提供了哈希数组映射 trie，这是 Clojure 用于其映射的相同数据结构，但库的设计旨在尽可能简化您自己的结构实现。

/// A trait for tree-like structures containing leaves
pub trait Compound<H>: Content<H> + Default
where
    H: ByteHash,
{
    /// The leaf type of the compound structure
    type Leaf: Content<H>;

    /// Returns handles to the children of the node
    fn children(&self) -> &[Handle<Self, H>];

    /// Returns mutable handles to the children of the node
    fn children_mut(&mut self) -> &mut [Handle<Self, H>];
}

实现 Compound 特质使您能够访问 kelvin 的迭代器和搜索功能。您需要自己实现的是 insert 和 remove 功能。目前 get、get_mut 等也需要手动实现，但这一点可能会改变。其余部分由库处理。

处理类型

处理类型是树结构实现的核心。

pub struct Handle<C, H>(HandleInner<C, H>);

enum HandleInner<C, H>
where
    C: Compound<H> [...]
{
    Leaf(C::Leaf),
    Node(Box<C>),
    SharedNode(Arc<C>), // not yet implemented
    Persisted(Snapshot<C, H>),
    None,
}

每个处理类型可以是叶子节点、boxed 节点、共享节点、快照或 None。不同节点类型之间的区别隐藏在 Handle 类型后面，作为库的用户，您只需要关注 Leaf、Node 和 None 的情况。

搜索

要搜索树，您使用 Method 特质，当在树中递归查找分支时，由库调用。

/// Trait for searching through tree structured data
pub trait Method: Clone {
    /// Select among the handles of the node
    fn select<C, H>(&mut self, handles: &[Handle<C, H>]) -> Option<usize>
    where
        C: Compound<H>,
        H: ByteHash;
}

最简单的例子是找到树中的第一个非空节点。

impl Method for First {
    fn select<C, H>(&mut self, handles: &[Handle<C, H>])
		  -> Option<usize> [...]
    {
        for (i, h) in handles.iter().enumerate() {
            match h.handle_type() {
                HandleType::Leaf | HandleType::Node
								  => return Some(i),
                HandleType::None => (),
            }
        }
        None
    }
}

这是在迭代树叶子时使用的默认方法。

对于在简单的 HAMT 实现中找到正确的键槽，这是一个例子（实际的实现更优化）

fn calculate_slot(h: u64, depth: u64) -> usize {
    let result = hash(depth + h);
    (result % N_BUCKETS as u64) as usize
}

impl Method for HAMTSearch {
    fn select<C, H>(&mut self, _: &[Handle<C, H>]) -> Option<usize>
    {
        let slot = calculate_slot(self.hash, self.depth);
        self.depth += 1;
        Some(slot)
    }
}

关联树注释

可用于搜索的树元数据，例如

基数，用于有效地找到集合的第 n 个元素

校验和，用于在集合之间进行常数时间的相等性检查

最小/最大值，用于优先队列功能

这是基数注释的示例

#[derive(PartialEq, Eq, Clone)]
pub struct Cardinality<T>(T);

impl<T> Associative for Cardinality<T>
where
    T: Counter,
{
    fn op(&mut self, b: &Self) {
        self.0 += b.0;
    }
}

impl<Anything, U> From<&Anything> for Cardinality<U>
where
    U: Counter,
{
    fn from(_: &Anything) -> Self {
        Cardinality(U::one())
    }
}

From<&Anything> 的实现意味着，任何叶子都将被计算为 1，并且随着子树注释的计算，使用简单的加法。

annotation! {
    pub struct BTreeAnnotation<K, U> {
        key: MaxKey<K>,
        count: Cardinality<U>,
    }
    where
        K: MaxKeyType,
        U: Counter
}

use std::io;

use kelvin::{Blake2b, ByteHash, Content, Map, Root, Sink, Source};
use kelvin_btree::BTree;

#[derive(Clone)]
struct State<H: ByteHash> {
    map_a: BTree<String, String, H>,
    map_b: BTree<u64, u64, H>,
    counter: u64,
}

// The initial root state
impl<H: ByteHash> Default for State<H> {
    fn default() -> Self {
        // Set up a default kv for map_a:
        let mut map_a = BTree::new();
        map_a
            .insert("Hello".into(), "World".into())
            .expect("in memory");
        State {
            map_a,
            map_b: BTree::default(),
            counter: 0,
        }
    }
}

impl<H: ByteHash> Content<H> for State<H> {
    fn persist(&mut self, sink: &mut Sink<H>) -> io::Result<()> {
        self.map_a.persist(sink)?;
        self.map_b.persist(sink)?;
        self.counter.persist(sink)
    }

    fn restore(source: &mut Source<H>) -> io::Result<Self> {
        Ok(State {
            map_a: BTree::restore(source)?,
            map_b: BTree::restore(source)?,
            counter: u64::restore(source)?,
        })
    }
}

fn main() -> io::Result<()> {
    let mut root = Root::<_, Blake2b>::new("/tmp/kelvin-example")?;

    let mut state: State<_> = root.restore()?;

    match state.map_a.get(&"Foo".to_owned())? {
        Some(path) => println!("Foo is {}", *path),
        None => println!("Foo is `None`"),
    }

    println!("Counter is {}", state.counter);

    state.counter += 1;
    state.map_a.insert(
        "Foo".into(),
        format!("Bar {}", state.counter * state.counter),
    )?;

    root.set_root(&mut state)?;

    Ok(())
}