使用两级merkle tree,解决文件存储的证明问题

加密先看默克尔树:

使用两级merkle tree,解决文件存储的证明问题

1.0的设计方法:

假设区块链调度器,随机指定挑战d5数据块。在之前的做法是,让被挑战者生把d5数据,和其祖先路径哈希值返回给挑战者,供验证。
在有限的时间内(1min)挑战者先计算 d5的数据+d5在整个文件中的块数。即sha256(d5[0~64kb-1] + 12)得出哈希值,对比路径信息是否一致,一致则说明底层数据正确。
再层层计算到root节点,是否与调度器提供的整个文件的哈希值一致,一致则说明是这个文件确实是被矿工存储了。因为1min之内,矿工在极短时间内是不可能通过哈希值反推出一串符合要求数据的。
1.0的代码已经实现,测试符合设计要求。
验证数据时,需要把底层64kb字节,和每一层64byte(两片叶子,每个叶子是32byte的哈希值),例如1G文件的验证需要16层路径,总共64k + 16 * 64,加上标识信息,65~66k,可以验证一个1G文件。对应,网络传输需要66K的io量。
1.0在设计之初,是解决有没有的问题,效率问题并没有并列放在第一位。因推出2.0方案。

2.0的设计方法:

2.0目标是讲64kb的块数据,减小到32byte。 怎么减小? 利用分层思想。把二叉树底层的数据块当层顶层文件去设计,动态生成(在内存中)一颗默克尔树。块大小为<=32byte(总的默克尔树比文件都大,
也就是说没有了只存储哈希值的动力,应该可以完美解决存储证明问题,因为这样设计,只有老老实实存储了文件是最科学的,其它的任何途径,都将得不偿失。堵死了通过暴力破解用哈希生成数据、
堵死了只记录存储哈希值不存文件的路)
特点:
两层默克尔树;第一颗树是64kb为单位的大树,存在于磁盘中。第二层是大树底层为文件,每次调用时在内存生成的;小树 + 大树持久化到地盘所需空间 >= 文件原本的空间大小。

小树的块大小是32byte,底层默克尔树叶片数量为2048个
由于小树是以大树的一块数据(64Kb)为根,所以层级是固定的13级。 2^13 * 32byte/叶片 = 64kb

2.0方案,1G文件的验证信息:

最底层32byte文件原始数据
2(左右叶子) * 32byte(叶子哈希) * 13层/片叶子
2(左右叶子) * 32byte(叶子哈希) * 16层/片叶子

总工需要1856 byte,也就是挑战1个1G的文件,一次需要用2k的数据即可,假设一个1G文件,被随机挑战6次。12kb即可完成挑战。
一个原始文件的任意32byte,竟然需要作弊者用 32byte + N(N是大树小数的公共部分)作弊,谁会这么傻!!!

3.0方案:加大巡检力度:

挑战分为:

  • 全文挑战
  • 块挑战
  • 随机挑战

全文挑战:用于存储文件后,和合同将要解约之前,两次整个文件的验证。
块挑战:即方案1,周期性挑战(例如每周,或每个月挑战一次)
随机挑战:即方案2,每一天挑战一次,例如1T的磁盘,需要12k * 1024。12M的数据可挑战一块1T的硬盘。

4.0的方案:

3.0我还是不满意,万一有疯子,就是不想赚钱只想破坏这个模式怎么办? 就像911飞机撞击五角大楼一样。
在真实的世界中,没有100%的方案,总会有意想不到的事情发生……,任何算法都是顶不住这种疯子的。
分析一下疯子的成本:他需要很多个超级计算机集群。可以在1Min之内动态反推出所有的数据,然后用网络传输,
为了破坏也学是一个readme.txt这样的文件……,在目前的计算机能力中,2^256反射出一个,目前不存在这样的计算能力。

上一篇:【区块链整理】四、区块链数据结构


下一篇:Merkle Tree - 默克尔树