2023-05-18

这是一个在线的网页游戏：Pebbling Game。可以看这个嵌入进来的网页：

为了直观展示 Pebbling Game 的游戏规则，经过几十次调整，GPT-4 完成了这个在线的游戏页面。

游戏的规则是：

1. 点击节点的圆圈，可以在节点中放入鹅卵石
2. 只有指向当前节点的所有节点，都已经放置了鹅卵石，当前节点才能够放置鹅卵石
3. 游戏目的是在节点 0 放置鹅卵石
4. 任何时间都能够从任意节点取走鹅卵石

如果直接点击节点 0，可以看到两个红色闪烁圆圈的提醒，意思是节点 1 和 2 都还没有放入鹅卵石，所以节点 0 不能放入鹅卵石。

节点 7 没有来源节点，所以可以直接放入鹅卵石。点击节点 7，能看到节点内出现了黑色的实心圆。此时如果想把鹅卵石放入节点 3，会提示因为节点 6 还空着，放入失败。节点 3 的来源节点是 6 和 7.

那么在这样的游戏规则下，问：最少需要多少颗鹅卵石？

如果鹅卵石足够多，这个图中一共有 10 个节点，手里有 10 个鹅卵石，就不需要取走鹅卵石的操作，直接按照顺序把节点填满就行。

如果鹅卵石有限，寻求鹅卵石数量最少的解法，这个图应该至少需要 5 个鹅卵石。

鹅卵石游戏的特点就是，总会存在一个最小值，如果鹅卵石的数量少于这个值，游戏将不能完成，因为最终的节点依赖于下层节点，而下层节点依次依赖于更下层的节点。如果中间节点的鹅卵石被取走，还需要从最下层开始重新放置。

鹅卵石游戏对于 Hard-to-pebble graphs 的数据结构具有启发意义，理解了游戏的规则，就理解了区块链如何证明磁盘空间的大小。

空间证明

Hard-to-pebble graphs 是一种结合了 Merkle 树的 DAG，特点就是需要一定数量的储存空间才能够完成最顶点的计算。就像是鹅卵石不够就无法完成游戏，储存空间不够就无法完成挑战。

由于图的多种多样，需要鹅卵石的数量没有通用的最优解，只能是针对某一种类型的图，去计算空间复杂度。

区块链场景的需求是既要占用空间大，又要验证速度快。Stack expender graph 的图结构在 Proof of Space 中使用比较广泛。在验证阶段，只需要按照 Merkle 树的特点，验证图中的某些节点，就可以确认图的完整性了，同时也能根据图的深度，推算出占用了多大的磁盘空间。

如果既要验证空间大小，又要验证空间占用的持续性，就在空间证明的基础上加上对时间的证明，比如 Chia 就用了 Delay Verifiable Function 的方式，先验一遍空间证明，等一段时间后，用 VDF 验证确实经过了足够多的时间，然后再验一遍空间证明，就达到了 Proof of Space-Time 的效果。