【FHE 同态加密】我们如何实现同态加密推理七自举 Bootstrapping——一个不提高精度、只刷新模数链的加油站关键词同态加密 FHE 自举 Bootstrapping 模数链刷新 coeff_to_slot slot_to_coeff EvalMod 大模型密文推理导读自举Bootstrapping在同态加密里常被误解成纠错或提精度。本篇用实测数字说明它其实只是一个加油站把被乘法吃掉的模数链还给同态加密推理引擎精度几乎不动。内容包含七段流水线、sin 折叠EvalMod以及 80% 时间花在哪两段域变换上。项目仓库Gitee 主仓https://gitee.com/pei-xiaoguang/kestrel-llmGitHub 镜像https://github.com/m13253246268-ship-it/kestrel-llm相关文档术语与数据口径 性能与基准 构建与复现 快速上手 架构总览0. 一句话结论自举bootstrapping不提高精度它只做一件事把被乘法吃掉的模数链还给你。实测证据很干净——同一层的结果自举前后与明文参考的误差几乎不动| 对象 | 链长 |max|err|||—|—|—||u0lay0产出 |np16|1.2712e-03||u0r112boot0刷新后 |np112|1.2706e-03|链长从 16 回到 112误差从1.2712e-03变成1.2706e-03。如果你把自举理解成纠错或提精度那这个数字会让你困惑把它理解成加油就通了——油加满了车并没有变快。1. 为什么必须自举CKKS 的每一次乘法都要rescale而rescale会切掉一个素数本系列第 5 篇。链长是单向消耗的。一跳的实际数字阶段链长输入112lay消费后16boot刷新后11216 这个数字意味着还能再算十几步乘法——对于一个 28 层的模型这远远不够。自举就是那个周期性的补给站。2. 七段流水线实测顺序驱动t23_chain.c的[boot profile]打印把整条自举摊开了字段顺序就是执行顺序modraise → coeff_to_slot → rotate_k → conj_extract → sin_fold_re / sin_fold_im → restore_merge → slot_to_coeff#段做什么对应函数1modraise用 Garner 扩展把链抬回满链ckks_modraise()2coeff_to_slot系数域 → 槽位域coeff_to_slot()3rotate_kGalois 旋转ckks_rotate_k()4conj_extract共轭提取分出实部/虚部—5sin_fold_re/_im对实部、虚部分别做sin折叠sin_fold()6restore_merge还原并合并—7slot_to_coeff槽位域 → 系数域slot_to_coeff()图 7-1 怎么读左列是域——modraise在系数域上做coeff_to_slot与slot_to_coeff是两次跨域搬运中间四段都在槽位域上逐点操作右侧条形按实测耗时成比例两根红框的条形coeff_to_slotslot_to_coeff合起来就是那 80%。图中只画了正文 §4 给出的三个量其余四段合计 ≈31 s未逐段展开。矢量版figs/fig07_bootstrap_pipeline.svgGraphviz 源码figs/fig07_bootstrap_pipeline.dot这个顺序本身就是答案自举的本质是把消息从槽位域搬到系数域做一次取模modular reduction再搬回槽位域。难点全在搬上。3. 为什么要搬EvalMod 与 sin 折叠在槽位域里一个槽位装的是一个近似的实数scale 2^60定标。你想对它做取模q这种操作直接做不了——因为取模是在系数域上才有意义的整数操作。于是标准做法是modraise把模数从当前的短链用 Garner 扩展抬回满链。这一步把模数空间还给消息coeff_to_slot把消息从槽位域变回系数域此时那个需要取模的量变成了系数的整数倍sin_fold用sin的周期性sin(πx)型的倍角/折叠结构来逼近那个取模函数。因为取模在数学上可以写成锯齿波而锯齿波可以用sin的倍角多项式逼近slot_to_coeff/restore_merge搬回去。rotate_k与conj_extract的存在是因为实部/虚部要分开处理——复数的实虚部在系数域里纠缠在一起需要用 Galois 自同构与共轭把它们分离出来各自折叠再合并回去。3.1 为什么是把私钥稀疏度降到 8一个不显然的取舍头注释原文降 hw 控制 bootstrapping 折叠混叠混叠I ~ hw/2 4sin 逼近多项式 9 次原型无安全可接受。hw是私钥的非零系数个数这代被设成8CKKS_KEY_HW。它不是随手取的私钥越稀疏sin折叠时产生的**混叠aliasing**越小约hw/2 4于是只需要9 次多项式就能逼近到位。换句话说为了自举的数值可行性我们主动牺牲了密码学参数hw越小越不安全。作者在注释里明确标注了原型无安全可接受——这个取舍如果我们不写出来读者会以为hw8是某种安全选择。4. 自举的代价80% 的时间花在搬boot0的实测分段字段名与上文七段一一对应段耗时占比coeff_to_slot1688 s~39%slot_to_coeff1716 s~40%sin_fold实部虚部~850 s~20%modraise/rotate_k/conj_extract/restore_merge其余余下total4285.03 s100%两个域变换加起来约 3400 s占 80%。这个结果直接否掉了我们的第一版优化直觉——“去优化多项式乘法”。乘法NTT确实是最热的内核但在这条链上时间不在卷积里在域变换里coeff_to_slot与slot_to_coeff每段都要做大量的 Galois 旋转和 key-switch本系列第 6 篇那对3×2个密钥就是在这里被反复使用的。顺带对比同一轮的lay0是1920 s而boot0是4285 s。一层 1.8 小时里有约 1.2 小时花在自举上。5. 一个工程细节懒初始化的并发陷阱代码里留了一条修复记录t23_chain.c附近tab_prepare(n); /* M1c 修复coeff_to_slot/slot_to_coeff 的 omp 区并发首次触发 ... */含义是某些预计算表原来是在并行区里首次访问时懒初始化的。多线程同时第一次进入就会并发触发初始化——这是经典的隐蔽竞态。修法是在进并行区之前显式tab_prepare。这类 bug 的特点是单线程永远不出现多线程偶发。它跟本系列第 13 篇位级可复现性是同一类问题的两个面。6. 安全边界务请读完本文所述参数为机制验证级n2048、112/2100 素数链 远低于 HE 参数标准的 128-bit 水平不得用于保护真实数据。 本文主张的是自举流水线的结构与实测账本。 本文不主张安全强度、性能优越性。特别提醒§3.1 的hw8是为数值可行性做的妥协不是安全选择。请勿把本文任何参数当成可用的密码学配置。7. 这一篇的未解问题coeff_to_slot/slot_to_coeff为什么这么贵我们没有逐段归因。是旋转次数多是 key-switch 的密钥太大导致缓存不友好还是 NTT 调用次数过多目前只有总量没有分解。这是本项目最值得做的一块性能分析也是收益最大的一块。hw8与精度之间的关系没有量化。我们知道hw小→混叠小→多项式次数低但hw从 8 提到 16 会坏多少、慢多少没有测。自举的链长余量没有探边。t23boot编到 2100 素数实际用到多少、还能压到多低我们没有做最小可用链长的扫描。而链长直接决定内存与耗时。sin_fold的精度贡献与误差来源没有分离。我们只知道整链误差不知道折叠这一步贡献了多少。下一篇我们回到模型侧SiLU 的密文化——两条拟合路径以及那个只有 8 字节、却能让你算出错误答案的开关文件。