Kelvin

一个Merkle树工具包和后端。

Merkle树和区块链

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

在编写处理Merkle树的程序时，当前的实践是满足于一个底层数据结构（例如，智能合约平台的一个流行选择是 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 中，每个被修改的数据结构已经都是临时的，这是基于 &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 的序列化表示。这意味着，你用于查找数据的“键”是数据的表示。这具有多个好处。

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

梅克尔树

梅克尔树就是这样，根节点只是其叶子及其/或子树的哈希值。而且，像往常一样，kelvin维护的结构也适用于梅克尔证明的构建。

自下而上的视图

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

内容特性

这个库背后的主要特性是 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 的情况。

搜索

要搜索树，你使用方法特性，该方法由库在递归查找树中的分支时调用。

/// 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! 宏。以下是 BTree 实现的示例

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

当使用此注释类型定义数据结构时，它将自动传播到根。

使用示例

以下是需要构建一个可以作为梅克尔树持久化的程序状态的示例。 （从 examples/simple 中获取）

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(())
}

待完成事项

这是一个 beta 版本，我们不对 API 的稳定性做出任何保证。一些功能尚未实现，但已设计。

垃圾收集

在 kelvin 中，垃圾回收将包括一个基于代数的复制收集器，给定一个根节点，从这个节点可到达的所有内容都将被复制到新的后端，而旧的将被释放。使用多代使得平均速度更快。