Blazing Fast PSI (CCS '22) Reproduction

本仓库是对论文 Blazing Fast PSI from Improved OKVS and Subfield VOLE 的复现，作为武汉大学本科毕业设计项目。

当前状态

• 已完成 volepsi2 中的 OKVS、clustering 优化 OKVS、半诚实 PSI fast instantiation 以及本地 Web UI 演示。
• volepsi2 已支持独立构建：优先使用已安装的 libOTe，找不到时回退到仓库内 vendored thirdparty 依赖。
• 已补充本地结构化 benchmark 结果，见 EVALUATION.md。
• 最终展示形态是本地 Web UI；除内置 synthetic demo 外，也支持粘贴或导入自定义数据集并在后端完成预处理。

已实现范围

volepsi2 当前覆盖的内容：

1. 论文 Figure 1 对应的 OKVS Encode / Decode。
2. clustering 优化 OKVS，支持按 bin 编码与多线程解码。
3. 论文 Figure 4 的半诚实 PSI fast instantiation，其中 B = F = GF(2^128)。
4. 通过 libOTe 的 silent VOLE 后端在本地两方执行中生成 VOLE 相关随机量。
5. 本地 Web UI，可展示协议阶段、耗时、网络流量和交集样本，并支持自定义数据集输入、去重和基础预处理。

当前未实现或未作为最终成果交付的内容：

• 论文中的 low-communication subfield-VOLE 变体。
• DOKVS / circuit PSI / malicious PSI。
• 与论文 Table 2 在相同硬件、相同网络环境下的一比一绝对数值复现。

仓库结构

• paper.md: 论文文本，作为复现参照。
• volepsi2/: 当前毕业设计的主实现、测试、benchmark 和 Web UI。
• EVALUATION.md: 已记录的 benchmark 命令、结果，以及与上游 volepsi 历史基线的比较。

从零开始的可复现构建

以下命令从仓库根目录执行。

1. 配置并构建 volepsi2

volepsi2 会先尝试 find_package(libOTe)。如果你已经安装了 libOTe，可通过 CMAKE_PREFIX_PATH 或 libOTe_DIR 指向它；如果没有，CMake 会自动回退到仓库内 vendored 的 thirdparty/libOTe、thirdparty/coproto、thirdparty/macoro 和 thirdparty/function2。

如果 vendored 依赖不在默认位置，可用 -DVOLEPSI2_THIRDPARTY_DIR=/path/to/thirdparty 指向替代目录。

如果你想强制始终使用 vendored 路径：

cmake -S volepsi2 -B volepsi2/build -DVOLEPSI2_USE_VENDORED_LIBOTE=ON

如果你要在当前机器上重新开启更激进的本地 CPU 调优，可以额外传入：

cmake -S volepsi2 -B volepsi2/build -DVOLEPSI2_USE_NATIVE_ARCH=ON

默认关闭 -march=native，这样把仓库拿到另一台答辩机器上时更容易直接重建。

当前 GF(2^128) 与行哈希 fast path 使用 x86 AES / PCLMUL 指令，VOLEPSI2_ENABLE_X86_CRYPTO_FLAGS 默认开启并自动添加 -maes -mpclmul。只有在工具链已经提供等价编译选项，或准备移植这条 fast path 时，才应关闭该选项。

如果你想显式使用外部已安装的 libOTe：

cmake -S volepsi2 -B volepsi2/build \
  -DCMAKE_PREFIX_PATH=/path/to/libote/prefix

然后编译：

cmake --build volepsi2/build --target core_test psi_test volepsi2_bench volepsi2_demo volepsi2_cli

说明：vendored 路径当前仍需要系统可发现的 libsodium 开发文件。

2. 运行回归测试

ctest --test-dir volepsi2/build --output-on-failure

当前测试分成两层：

• core_test: 内部后端回归，集中检查 GF(2^128)、OKVS 和 clustering 优化 OKVS。
• psi_test: 与 demo 协议路径一致的端到端 PSI 回归。

如果答辩前还想再做一层随机化压力验证，可运行：

./volepsi2/build/volepsi2_bench stress -t 20 -nt 4 -bs 2048

该模式会在 n = 2^10、2^12、2^14 上重复检查 OKVS round-trip 和 PSI correctness，已记录结果见 EVALUATION.md。

3. 启动最终展示用的 Web UI

./volepsi2/build/volepsi2_demo --port 8090

浏览器打开 http://127.0.0.1:8090。

Web UI 展示内容

Web UI 会展示：

• synthetic demo 的接收方/发送方规模、线程数、聚类阈值等输入参数。
• 直接粘贴或导入接收方与发送方数据集，并在后端进行分隔、去重和空白过滤。
• Hash Mapping、OKVS Encoding、VOLE Generation、Correction Transfer、Intersection Calculation 五个协议阶段。
• 每个阶段的耗时与网络流量。
• 最终交集规模、交集样本、发送方/接收方样本。
• 当前是否启用 clustering 优化 OKVS、是否启用真实 silent VOLE。

Demo 服务端当前限制 synthetic 或上传后的单侧集合规模不超过 2^20，请求体不超过 64 MiB；自定义数据集会先写入 15 分钟有效的一次性本地 session，再进入 SSE 执行流程。

这部分是最终答辩时最直接的演示界面。

本地结构化评测结论

完整命令和结果见 EVALUATION.md。这里给出摘要：

• volepsi2 已经具备可重复运行的 OKVS / PSI benchmark，不再只是“以后再测”。
• 在 n = 2^12 的本地测试中，clustering 优化 OKVS 在 4 线程下将 OKVS 总时间从 36.558 ms 降到 29.898 ms，说明 clustering 在当前实现中已经产生可观收益。
• 在 n = 2^10、2^12、2^14 的本地 PSI 测试中，volepsi2 的绝对运行时间仍明显慢于历史记录中的上游 volepsi 基线，因此本项目当前的定位是“功能性复现 + 可展示实现”，而不是“性能追平上游”。
• 论文在 n = 2^20 下报告了更强的多线程收益；本仓库当前 README 中记录的是本地机器上的小规模结构化评测，目的是给答辩和复现提供可重复证据，而不是冒充论文原始实验环境。

与论文的差异和限制

• 当前实现复现的是 Figure 4 的 fast instantiation，不是 low-communication subfield-VOLE 版本。
• Web UI 里的通信统计来自本地 socket 与 coproto::LocalAsyncSocket，适合展示协议阶段，但不等于真实跨机网络环境。
• volepsi2 的代码优先级是可读性、模块清晰度和前端可展示性，因此没有像上游 volepsi 那样做同等程度的内核级性能优化。
• 这意味着当前仓库适合作为本科毕业设计成果展示和论文复现讲解，但不应把它表述成“已经在性能上等价于上游参考实现”。

推荐阅读顺序

1. 看 volepsi2/README.md 了解实现和运行方式。
2. 看 EVALUATION.md 了解本地 benchmark 命令和结果。
3. 启动 volepsi2_demo，直接从 Web UI 演示协议流程。
4. 需要算法细节时，再回到 paper.md 对照 Figure 1 和 Figure 4。