在 Go 中实现 Merkle 树数据结构

Question

我目前正在尝试在 Go 中实现默克尔树数据结构。基本上，我的最终目标是存储一小组结构化数据（最大 10MB），并允许这个“数据库”与分布在网络上的其他节点轻松同步（请参阅相关资料）。我已经在 Node 中合理有效地实现了这一点，因为没有类型检查。这就是 Go 的问题所在，我想利用 Go 的编译时类型检查，尽管我也想拥有一个可以与任何提供的树一起使用的库。简而言之，我想使用结构体作为 merkle 节点，并且我想拥有一种Merkle.Update()嵌入到所有类型中的方法。我试图避免Update()为每个结构编写一个（尽管我知道这可能是唯一/最好的方法）。我的想法是使用嵌入式类型：//librarytype Merkle struct {    Initialised bool    Container interface{} //in example this references foo    Fields []reflect.Type    //... other merkle state}//Merkle methods... Update()... etc...//userlandtype Foo struct {    Merkle    A int    B bool    C string    D map[string]*Bazz    E []*Bar}type Bazz struct {    Merkle    S int    T int    U int}type Bar struct {    Merkle    X int    Y int    Z int}在这个例子中，Foo将是根，它将包含Bazzs 和Bars。这种关系可以通过反思类型来推断。问题是用法：foo := &Foo{    A: 42,    B: true,    C: "foo",    D: map[string]*Bazz{        "b1": &Bazz{},        "b2": &Bazz{},    },    E: []*Bar{        &Bar{},        &Bar{},        &Bar{},    },}merkle.Init(foo)foo.Hash //Initial hash => abc...foo.A = 35foo.E = append(foo.E, &Bar{})foo.Update()foo.Hash //Updated hash => def...我认为我们需要merkle.Init(foo)因为foo.Init()实际上会foo.Merkle.Init()并且无法反思foo. 未初始化的Bars 和Bazzs 可以被 parent 检测和初始化foo.Update()。一些反思是可以接受的，因为目前正确性比性能更重要。另一个问题是，当我们Update()是一个节点时，所有结构字段（子节点）也需要被Update()d（重新散列），因为我们不确定发生了什么变化。我们可以foo.SetInt("A", 35)实现自动更新，但我们会丢失编译时类型检查。这会被认为是惯用的 Go 语言吗？如果没有，如何改进？任何人都可以想出一种替代方法来将数据集存储在内存中（用于快速读取），并通过简洁的数据集比较（用于通过网络进行有效的增量传输）？编辑：还有一个元问题：问这类问题的最佳地点是 StackOverflow、Reddit 还是 go-nuts？最初发布在reddit 上，没有答案:(

Answer 1

一些目标看起来像：

• 散列任何东西——通过散列开箱即用的大量内容使其易于使用

• 缓存散列- 进行更新只是重新散列他们需要的内容

• 符合地道的习惯——与其他 Go 代码很好地融合

我认为你可以像内置的序列化工具那样粗略地攻击散列encoding/gob或encoding/json做任何事情，这是三管齐下的：如果类型实现它，则使用特殊方法（对于 JSON 而言MarshalJSON），对基本类型使用类型开关，并使用反射回退到令人讨厌的默认情况。这是一个 API 草图，它为哈希缓存提供了一个帮助程序，并允许类型实现Hash或不实现：

package merkle

type HashVal uint64

const MissingHash HashVal = 0

// Hasher provides a custom hash implementation for a type. Not

// everything needs to implement it, but doing so can speed

// updates.

type Hasher interface {

    Hash() HashVal

}

// HashCacher is the interface for items that cache a hash value.

// Normally implemented by embedding HashCache.

type HashCacher interface {

    CachedHash() *HashVal

}

// HashCache implements HashCacher; it's meant to be embedded in your

// structs to make updating hash trees more efficient.

type HashCache struct {

    h HashVal

}

// CachedHash implements HashCacher.

func (h *HashCache) CachedHash() *HashVal {

    return &h.h

}

// Hash returns something's hash, using a cached hash or Hash() method if

// available.

func Hash(i interface{}) HashVal {

    if hashCacher, ok := i.(HashCacher); ok {

        if cached := *hashCacher.CachedHash(); cached != MissingHash {

            return cached

        }

    }

    switch i := i.(type) {

    case Hasher:

        return i.Hash()

    case uint64:

        return HashVal(i * 8675309) // or, you know, use a real hash

    case []byte:

        // CRC the bytes, say

        return 0xdeadbeef

    default:

        return 0xdeadbeef

        // terrible slow recursive case using reflection

        // like: iterate fields using reflect, then hash each

    }

    // instead of panic()ing here, you could live a little

    // dangerously and declare that changes to unhashable

    // types don't invalidate the tree

    panic("unhashable type passed to Hash()")

}

// Item is a node in the Merkle tree, which must know how to find its

// parent Item (the root node should return nil) and should usually

// embed HashCache for efficient updates. To avoid using reflection,

// Items might benefit from being Hashers as well.

type Item interface {

    Parent() Item

    HashCacher

}

// Update updates the chain of items between i and the root, given the

// leaf node that may have been changed.

func Update(i Item) {

    for i != nil {

        cached := i.CachedHash()

        *cached = MissingHash // invalidate

        *cached = Hash(i)

        i = i.Parent()

    }

}