Proof Of Space算法解析

1.Table格式会生成7个table,每个table包含2^K个entry,现在K取值20,所以每个table有1M个entry;每个entry的格式如下:pub(super)enumTable<constK:u8,constTABLE_NUMBER:u8>where

1. Table 格式

会生成7个table,每个table包含2^K个entry,现在K取值20,所以每个table有1M个entry;每个entry的格式如下:

pub(super) enum Table&lt;const K: u8, const TABLE_NUMBER: u8>
where
    EvaluatableUsize&lt;{ metadata_size_bytes(K, TABLE_NUMBER) }>: Sized,
{
    /// First table with contents of entries split into separate vectors for more efficient access
    First {
        /// Derived values computed from `x`
        ys: Vec&lt;Y>,
        /// X values
        xs: Vec&lt;X>,
    },
    /// Other tables
    Other {
        /// Derived values computed from previous table
        ys: Vec&lt;Y>,
        /// Left and right entry positions in a previous table encoded into bits
        positions: Vec&lt;[Position; 2]>,
        /// Metadata corresponding to each entry
        metadatas: Vec&lt;Metadata&lt;K, TABLE_NUMBER>>,
    },
}

Y,X是u32类型,Position也是u32类型,Metadata根据是第几个table而不同;7个table一共404M大小;

2. Table生成算法

Generate(k, seed) → pos_tables

table1的产生算法如下:

  1. 根据ChaCha算法和Seed通过ChaCha8(seed, 0)方法产生一个伪随机数发生器,从而产生2^K个X值;然后根据f1(X)算法产生对应的Y值;

table2产生的算法大体思路如下: 根据下面的f2算法得到Y值,其实就是hash值,选择的Xi和Xj需要满足M算法(算法比较复杂);Xi和Xj值上面一个的table1的X值,其中的i和j就是entry里面的Position; image.png

table3产生的算法大体思路如下: $f3​(l=(xi​,xj​),r=(xk​,xl​))=Hash(l∣∣r)$ if and only if $M(f2​(xi​,xj​),f2​(xk​,xl​))==True$ Xi,Xj,Xk,Xl的值是也来自于Table1,其实是通过Table2的两个Entry获取的Table1的4个X值;l,r值是Table2的索引,即position;

第4,第5,到第7个Table的算法和上面一样,每次entry.Y值都是根据上一个table的两个值计算得出;

可以简单的认为整个生成算法就是首先根据一个Seed产生1M(1048576个)数据量的伪随机值X,然后根据把X作为输入参数,根据f1算法生成同样数量的Y值,第一个Table就生成了; 然后后面每一个Table都要找到符合M算法要求的,上一个Table的,两个Entry。然后再根据f2,f3,f4,f5,f6,f7的算法计算当下Table的Entry数;

3. Proof of Space生成算法

Find_Proof(pos_table, challenge) → proof_of_space 找proof其实就是找64个table1的entry;

为了找到证据,我们必须查看表Table7是否有一个或多个条目entry.y值,其中前k位与challenge的前k位匹配(其实就是是否相等)。 最后一个表Table7中的每个满足的条目都指向表Table6中的 2 个条目。这两个条目将指向表Table5中的 2 个条目,依此类推,直到Table1。因此最后一个表中的条目将间接指向第一个表中的 64 个条目 。这 64 个entry.x串联起来就是空间证明,

4. Verify 算法

Is_Proof_Valid(space_k, seed, challenge, proof_of_space) → bool

为了验证空间证明,我们需要 4 个东西: proof_of_space中的 64 个 x 值、参数k 、种子和challenge_index 。该过程或多或少与表生成相同,即我们计算相同的函数,但不生成整个表,仅生成一个很小的子集。仅计算证明的 x 值的输出才能验证:

  1. 输出f1..f7满足每一步的匹配函数M,

  2. Table7的最终输出entry.y对应于challenge_index(判断是否相等) 。

总结

和filecoin一样,都是计算多个table(filecoin叫做layer),后面一个table的计算必须要依赖前一个table,从而保证了无法并行化计算;

计算慢,而验证快的逻辑和arweave一样,都是因为计算的时候是7个整表数据都需要计算出来,而验证则是只验证其中的一部分(重新计算其中的一部分)。

点赞 0
收藏 0
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
杜满想Elvin
杜满想Elvin
老程序员,区块链架构师