基于VRF的Poof-of-Capacity共识算法

最近在写一篇基于VRF的POC共识算法的论文,算法基本框架已经基本梳理清楚,但是证明部分很有很多内容要写,最近一直忙于项目没有时间动笔,故先将算法贴出来。 背景 共识算法是区块链技术研究的核心,PoW(Proof of Work)共识算法的可行性已在理论与实践上得到了验证,但PoW共识需要消耗大量的能源。为次,PoS(Proof of Stake)共识算法成为研究热点,但PoS共识算法在公有链上的应用仍然存在许多问题。MIT的团队提出了基于容量证明的共识算法Spacemint,虽然其在公有链上有较好的应用,但其性能与安全性都存在问题。为此,我们提出一种新的基于容量证明的共识算法。 算法描述 首先选定两个单向函数$f(x,x’),\ g(x, k), \ h(x’, k)$,hash函数$hash(x)$,时间间隔$s$, unique signature签名算法 $Sig(x, sk)$, 取前$n$位的函数 $right(x)$. 初始化:参与挖矿的矿工要对硬盘进行初始化,首先,矿工生成签名算法$Sig$的一组公私钥对($pk,sk)$,然后利用$pk$建立$f(x,x’) \to (x,x’)$的映射表,其中 $(x,x’)$ 满足 $g(x, pk) = h(x’, pk)$。 挖矿:每隔 $s$ 时间间隔,矿工可以尝试一次,即计算$$hash(sig((x,x’,time/s, c), sk)) < target$$若满足则出块,其中$(x,x’)$满足$$right(f(x,x’)) = right( c ), \ g(x, pk) = h(x’, pk)$$ 其中,c为前面某个块的proof的hash。 出块:矿工在打包的块中应包含该块的proof,proof为$(x,x’,pk, signature)$,并使用sk对整个block进行签名,当其它节点收到块时,节点依次验证$(x,x’), signature, hash(signature), block\ signature$是否有效,若均验证通过则接受该block。 分叉:分叉时选择难度最高的链,若均相同,则随机选择。

Read More

Authenticated Dynamic Dictionaries in Ethereum

1、Merkle Tree Merkle Tree 是利用Hash对内容的正确性进行快速鉴定的数据结构,其结构示意图如下: Merkle Tree 父节点包含所有子节点的Hash值; Merkle Tree 的Tree可以是任何形式的Tree,任何经典的tree构造算法都可以经过简单的修改应用到Merkle Tree上; Merkle Tree的Branch Node也可以存储数据,尽管大多数实现中只在Leaf Node上存储数据; Merkle Tree对单个数据的校验最多需要 $O(h)$ 时间,其中 $h$ 为树高,如果树足够平衡,则验证单个节点的复杂度为$O(\log(n))$. 在BitCoin中,Merkle Tree主要用来实现轻节点,轻节点只存Top Hash,当轻节点要验证一笔交易时(比如上图中的L4),则向存有全部数据的完全节点验证,完全节点将L4到root的路径上的所有node(1-1,1-0,1,0,Top Hash),轻节点对根据这条路径计算得到Top Hash,如果计算得到的Top Hash与本地的Top Hash相等,则轻节点就可以相信完全节点传过来的数据。 在Ethereum中,Merkle Tree除用来实现轻节点外,还用来实现增量存储。 2、MPT 为了能够支持高效的检索及动态的插入、删除、修改,Ethereum使用Trie来构建Merkle tree,Ethereum将其命名为Merkle Patricia Tree(MPT),其示意图如下: Ethereum使用的是一棵16叉Trie树,并进行了路径压缩。可以将其理解为一棵普通的Trie树,只不过指向子节点的指针变成了子节点的Hash。 2.1 Node类型 MPT有三种类型的节点,分别是:Leaf Node、Branch Node、Extension Node。Leaf Node 由一个Key域(nibbles,key的片段)及数据域组成;Branch Node 由分支域(16个指向下一个节点的指针,这里的指针可以理解为KV数据库中的Key)及数据域(如果存有数据,则此数据的Key是从根到达该Node所经过的所有nibbles)组成;Extension Node由Key域(Shared nibbles,这实际上是对路径进行压缩,否则路径的长度就是key的长度,在Node数量不多的情况下,树会非常的不平衡)及分支域(指向下一个Branch Node的指针)组成。 Parity中MPT定义如下: enum Node{ /// Empty node. Empty, /// A leaf node contains the end of a key and a value.

Read More

Reading List

Papers [1] The Sleepy Model of Consensus. [2] Beyond Hellman’s Time-Memory Trade-Offs with Applications to Proofs of Space [3] SpaceMint: A Cryptocurrency Based on Proofs of Space [4] Simple Proofs of Sequential Work [5] Algorand: The efficient and democratic ledger [6] Ouroboros: A provably secure proof-of-stake blockchain protocol [7] Chainspace: A Sharded Smart Contracts Platform [8] A secure sharding protocol for open blockchains [9] Analysis of the blockchain protocol in asynchronous networks

Read More