PIL中缺少约束 导致恶意SMT存在性证明
存储状态机使用SMT(稀疏默克尔树)并与存储ROM一起实现可证明的CRUD操作。
为了证明SMT中(键,值)的包含关系,状态机将键表示为位字符串。它使用键的LSB(最低有效位)从根向叶子遍历树:位的0/1值对应于左/右边缘遍历。
01010101010101010 - value
由于树是稀疏的,叶级别不一定等于键位长度,这意味着一旦将叶子插入到树中,剩余部分的键(rkey)被编码到叶子值中。
包含检查算法由两部分组成(参考链接:https://wiki.polygon.technology/docs/zkEVM/zkProver/basic-smt-ops):
检查根 - 通过从叶子到根节点爬升并使用兄弟哈希进行通用Merkel Tree根检查来完成。
检查键:
I. 为了检查键,状态机在每个下一个路径位之前添加到剩余密钥(rkey),例如 rkey||b1||b0 (对于叶级别=2)。
II. 在操作结束时,在Storage ROM中可以通过LATCH_GET命令识别出iLatchGet设置为1。
III. 主SM中使用排列约束确保zkEVM ROM传递的key与步骤(I)构造的key匹配。