1.Table格式会生成7个table,每个table包含2^K个entry,现在K取值20,所以每个table有1M个entry;每个entry的格式如下:pub(super)enumTable<constK:u8,constTABLE_NUMBER:u8>where
会生成7个table,每个table包含2^K个entry,现在K取值20,所以每个table有1M个entry;每个entry的格式如下:
pub(super) enum Table<const K: u8, const TABLE_NUMBER: u8>
where
EvaluatableUsize<{ 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<Y>,
/// X values
xs: Vec<X>,
},
/// Other tables
Other {
/// Derived values computed from previous table
ys: Vec<Y>,
/// Left and right entry positions in a previous table encoded into bits
positions: Vec<[Position; 2]>,
/// Metadata corresponding to each entry
metadatas: Vec<Metadata<K, TABLE_NUMBER>>,
},
}
Y,X是u32类型,Position也是u32类型,Metadata根据是第几个table而不同;7个table一共404M大小;
Generate(k, seed) → pos_tables
table1的产生算法如下:
ChaCha8(seed, 0)
方法产生一个伪随机数发生器,从而产生2^K个X值;然后根据f1(X)算法产生对应的Y值;table2产生的算法大体思路如下: 根据下面的f2算法得到Y值,其实就是hash值,选择的Xi和Xj需要满足M算法(算法比较复杂);Xi和Xj值上面一个的table1的X值,其中的i和j就是entry里面的Position;
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数;
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
串联起来就是空间证明,
Is_Proof_Valid(space_k, seed, challenge, proof_of_space) → bool
为了验证空间证明,我们需要 4 个东西: proof_of_space中的 64 个 x
值、参数k
、种子和challenge_index
。该过程或多或少与表生成相同,即我们计算相同的函数,但不生成整个表,仅生成一个很小的子集。仅计算证明的 x
值的输出才能验证:
输出f1..f7
满足每一步的匹配函数M,
Table7
的最终输出entry.y
对应于challenge_index
(判断是否相等) 。
和filecoin一样,都是计算多个table(filecoin叫做layer),后面一个table的计算必须要依赖前一个table,从而保证了无法并行化计算;
计算慢,而验证快的逻辑和arweave一样,都是因为计算的时候是7个整表数据都需要计算出来,而验证则是只验证其中的一部分(重新计算其中的一部分)。
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!