Reef：基于正则表达式匹配的ZKP

1. 引言

Sebastian Angel等人2023年论文《Reef: Fast Succinct Non-Interactive Zero-Knowledge Regex Proofs》，开源代码实现见：

• https://github.com/eniac/Reef（Rust）

Reef用于committed文档与正则表达式匹配或不匹配。可用于证明：

• 密码的强度
• 尽管进行了编辑但电子邮件的来源
• oblivious DNS查询的有效性
• DNA突变的存在。

Reef支持Perl兼容正则表达式语法，包括通配符、替换、范围、capture groups、Kleene-star、negations和查找。Reef引入了一种新类型的automata，即Skipping Alternating Finite Automata（SAFA），它在生成证明时跳过文档的无关部分，而不会破坏可靠性，并用lookup argument实例化SAFA。

经实验评估，Reef可为具有32M个字符的文档生成证明；这些证明很小，验证起来很便宜（不到一秒钟）。