关于区块存储

因为有区块浏览器这样的东西存在, 所以区块链的存取结构应当能够方便的从头遍历到尾, 同时也要能够从尾遍历到头.  => 双向链表

当收到其它节点传来的新区块时, 需要知道此区块的前一区块是否存在 (存在就 ok; 不存在的话可能本节点区块数据太旧, 触发从其他节点同步, 也可能是接收到的区块作假. 总之这种情况下不要接受区块, 如果确实是自己区块太旧, 从其他节点同步数据的过程也会将刚刚自己没有接受的块同步过来的, 不必担心块丢了.)   =>  平衡二叉树 (avl 或者红黑树)

当用区块哈希而不是区块高度 (高度不唯一, 做不了) 来作为区块标识以后, 便不适合用平衡二叉树了, 因为平衡二叉树存区块的话, 要求 key 能够方便的比较大小, 然而区块的哈希并不是方便比较大小的类型. 这种情况下更适合用哈希表存区块.

但是前面也说了, 我们仍然要求区块的存储是按照高度有序的, 因为区块浏览器, 新加入的节点都需要能够从最旧区块同步到最新的区块.

那么问题来了, 现在我们既想要能够根据区块哈希块查找到区块, 又想能够根据区块高度快速遍历区块, 然而不幸的是, stl 里的容器们要么是只适合查找, 要么只适合排序, 没有同时满足两个的, 所以搁以前我们八成会用两个数据结构同时存区块来达到目的, 比如 std::unordered_map 和 std::map, 但这样增删都要同时改两个地方, 很不方便, 还多占空间.

现在不同了, boost 提供了一种 multi index 结构, 能够满足我们多维度对数据查询的需求 (暂不考虑持久化). 关于 multi index 这里介绍的很好, https://theboostcpplibraries.com/boost.multiindex

为什么需要区块哈希

区块是需要唯一标识的, 因为很多节点在同时生产区块, 仅靠区块高度是无法区分开它们的, 两个不同节点生产的区块可能位于同一高度, 这时候应当选用哪个区块, 就需要根据区块的唯一标识确定了.

区块的唯一标识可以用 sha256 哈希来计算.

关于 genesis time

我最初实现的代码中, genesistime 是在程序启动的时候被赋值的, 这是为了测试方便, 生产环境下这种方式不好. 一般来讲, 公链应当是好些个节点约定好一个未来的时间, 写死在代码里 (或者写在共同约定的配置里), 然后启动节点, 程序中会有逻辑判断是否到达了设定的时间, 一旦到达, 就开始出块.

这个 genesis time 可以直接作为创世区块的时间戳, 比特币就是这样的.

关于消息同步

消息同步是 p2p 网络中的重要问题. 早期的 p2p 网络是真正的 “各个节点都平等”, 也就是我们所说的非结构 p2p 网络, 那个时候消息同步的典型的方法就是洪泛算法, 然而洪泛算法的问题也是众所周知的 — 网络风暴. 后来的 p2p 网络趋于向结构化发展, 比如 DHT, 归根结底就是掺杂了 “中心” 在里面, 以 “中心” 解决消息同步问题.

我希望实现一个非结构化的 p2p 网络, 真正实现各节点平等 (比特币就是如此). 有关非结构化 p2p 网络的消息同步已经做过了很多努力:

  • ttl
  • 邻居表

TODO: 贴中内外相关论文

关于最长链准则的几种情况

假设有 a, b, c 三个见证人轮流出块, 他们在出块的过程中可能会碰到如下的一些窘境.

首先是最简单的情况:

a, b, c 第一轮出块很完美, 第二轮开始 a 基于 c 出块, 依然正常. 但是 b 可能恰好 c 和 a 的块他都没收到, 也可能是它自己确实是坏人, 总之这第二轮它的块指向了自己在第一轮出的块. 接下来 c 出块时 (假设 c 正常收到了所有消息), 他看到的就是图上这番景象. 那么它出块应当基于 a 区块还是 b 区块呢? 根据最长链准则, 显然它应当基于 a 区块出.

这里我们讨论一个细节, 就是 c 怎么判断它看到的 a 和 b 谁的高度比较高. 分别从 a, b 往前推到头来计数肯定是很慢的, 所以在我们的实现中高度信息也会写到区块中. 那么问题又来了, 如果高度写到区块里, 那 b 在第二轮出块的时候把自己的块高度写的比较大不就行了吗? 当然是不行的, 在我们的实现中, 见证人收到每个块是都会验证前一个块在不在, 以及验证前一个块的高度是不是只比收到的块小 1, 如果不是的话, 块会被拒绝.

上面说的是最基本的情况, 下面是一个相对复杂一点的情况, 就是当轮到某个节点出块时, 它发现当前有两个块高度一样, 它不知道自己的块应该指向这两个块中的哪个.

这个情况的产生可能是由于 c 没有收到 b 的区块, 于是在 c 出块时 c 看到的只有 a 区块, 于是就继续在 a 后面出, 而 a 是成功收到了 b 和 c 的区块的. 于是再到 a 出块时, a 就会看到 b, c 高度都是 2, 并且都指向自己第一次出的块.

这个窘境怎么解呢? 我们规定, 但出现两个长度相同的链时, 见证人应当基于较早 (可以比较两个块的时间戳, 或者比较两个块出块人在见证人列表中的先后次序) 接收到的块出块. 这里显然 b 是较早接收到的块, 于是 a 这次出块应当基于 b 区块出.