Kelvin

Merkle树工具包和后端。

Merkle树和区块链

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

编写处理Merkle树的程序时，当前的做法是采用一种底层数据结构（例如，智能合约平台的一个常见选择是 Patricia或基数树）。

大多数实现都使用键值数据库后端（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中，每个正在修改的数据结构都是基于&t;mut引用的保证而已经是transient的。这意味着，我们得到了两全其美的效果！

磁盘持久性

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

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

让我们再次看看前面的例子，为什么根节点的子节点不能指向某种磁盘表示？并且按需加载和缓存？这正是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。不同节点类型之间的区别隐藏在处理类型后面，作为库的用户，你只需要关心 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
}

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

使用示例

以下是一个示例，说明构建一个可以持久化为 Merkle 树的程序状态所需的所有内容。（来自 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(())
}

待完成的工作

这是一个测试版发布，我们不保证 API 的稳定性。一些功能尚未实现，但已设计。

垃圾回收

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

lib.rs:

在 kelvin 上实现的 Radix trie