3.1 把比较画成电路：百万富翁比较电路
3.1 把比较画成电路：百万富翁比较电路
本节摘要：比较两个 n 位数，等价于从高位到低位找第一个不同的比特——谁在那一刻是 1 谁更大。本节用 4 位小例子把这句话变成具体的门电路，数出门数，并解释"电路化"为什么是混淆电路路线的第一性要求。
核心概念
明文世界里一句话就能说完的事（if a 大于 b），在 MPC 里必须先回答：这个函数是哪张布尔电路？ 因为混淆电路加密的对象是门，不是高级语句。比较运算的电路化有个经典构造：从最高位开始逐位扫描，维护一个"目前是否已经分出胜负"的信号 l；每读入一对比特 (ai, bi)，若 l 尚未置位且 ai 不等于 bi，则胜负就此确定（ai 为 1 则 a 大）。
写成逻辑门：设 li 是处理完第 i 位后的"已分出"信号，则 l(i) = l(i-1) OR (EQ(i-1) AND ai XOR bi)，其中 EQ 表示此前各位全部相等。实现上更常用的等价形式是每个比较单元含一扇与门加一扇异或门，n 位比较共用一个 n 单元的链，总门数约 3n 扇——32 位整数约百扇门，对混淆电路来说小到可以忽略，真正的大户是 AES 这类函数（约 6800 扇与门，3.4 节会引用这个数）。
图：4 位比较电路的逐位结构
为什么必须先电路化
混淆电路加密的原子单位是"一扇门的真值表"，这意味着函数必须预先编译成电路。这对开发者是个真实的思维转换：习惯写 if 的人要在 MPC 世界里改写习惯——分支要展开（两个分支都算然后按条件选），循环要静态展开（迭代次数编译期定死），除法、开方这类运算要么查表要么用多项式逼近。第 6 章讲工程化时还会回到这些"电路纪律"，它们决定了 MPC 项目的开发成本。
电路表示还有一层安全含义：泄露量与电路结构绑定。协议只保护输入值，不保护函数本身——参与方都知道大家在算"比较"还是"求和"。如果连函数都要保密（比如保护评分模型的结构），需要额外的技术（如对电路再做一层零知识封装），那是进阶话题。
定位与延伸
比较电路是百万富翁问题的"执行体"，也是很多上层应用的原材料：隐私求交后的阈值筛选、联合风控的分档判定、拍卖中的二价机制，底层都是比较电路的不同组合。下一节把这个电路整个加密掉，看看混淆四步如何让它在密文世界跑起来。
本节要点：比较 = 从高位找首个不同比特；每单元一与一异或、约 2n 扇门；MPC 开发从"写代码"变为"画电路"，控制流必须静态展开。
电路化的真实成本：三个改造案例
"画电路"不是机械翻译，是一门口袋里的优化手艺。三个来自实战的改造案例帮你建立手感。
案例一：if 分支的展开。 想表达"若余额大于阈值则走规则甲否则走规则乙"，电路里两条规则都要算——先分别算出两个结果，再用阈值比较的结果当开关做选择。代价是"两条规则的计算量都付"，明文工程师习惯的"短路求值"在电路世界里不存在。这个代价在规则数量大时会爆炸，解决办法是把规则集压缩、合并同类条件，或在协议外做预筛。
案例二：循环的静态展开。 明文里"对每个元素循环检查"翻译成电路就是把循环体复制 n 份——循环次数必须编译期定死。动态长度的列表要么定上限补齐，要么分批处理。这也解释了为什么 MPC 任务的第一步永远是"把数据形状定死"。
案例三：查表的重写。 AES 的 S 盒若按 256 项真值表逐项比对实现，一个 S 盒就要上千扇门；重写成位运算等价式后压到几十扇。成熟电路库的全部价值就在这类手艺里——自研电路前先找现成库，是 MPC 项目省预算的第一原则。
三个案例合起来给出一句话方法论：明文代码决定"算什么"，电路写法决定"算多贵"，后者才是 MPC 工程师的日常主战场。回到百万富翁问题本身：比较电路恰好是"天生适合电路"的形态——分支少、深度浅、门少，这也是它常被选作入门案例与生产构件的双重原因。
比较电路的三个变体与选用场景
同一句"比较两个数大小"，在不同业务语境下要的是不同的电路变体，选错变体等于白付计算量。变体一：全序比较——本节的构造，输出"谁大谁小或相等"三态，适合拍卖、排序类需求。变体二：阈值判断——只输出"是否大于等于阈值"一个比特，电路砍掉一半，联合风控的"评分是否过线"用这个，泄露面也最小。变体三：相差值比较——输出差的符号加粗略量级，营销场景"预算是否显著高于对方"用这个，量级粒度本身就是设计出来的泄露边界。
三个变体的差异再次呼应 1.2 节的原则：输出的形状决定泄露的形状。业务方要"精确知道大多少"的时候，值得多问一句"这个精度是决策必需还是习惯使然"——把全序比较降级成阈值判断，往往既省电路又省泄露，双赢的优化在本节就能落地。
比较电路还有一层教学价值：它是理解"混淆对象"的最佳教具。混淆电路加密的是门与线，不是数字——这个反直觉的点在加法、乘法这类算术电路上不如在比较电路上直观，因为比较的逻辑结构（从高位找不同）肉眼可见，每一扇门在保护什么都清清楚楚。下一节把这张电路整个加密，建议你边读边对照本节的图，亲手把"哪根线的哪个标签对应哪个比特"在草稿上标一遍——混淆电路的一切神秘感，都会在你标完之后消失。
动手作业：自己画一张 3 位比较电路
理解比较电路最可靠的方式是亲手画一张缩水版。取 3 位输入 a 等于 a2 a1 a0、b 等于 b2 b1 b0，按"从高位找首个不同比特"的构造逐位画出单元链：每个单元一扇异或门（判该位是否相同）、一扇与门（判"此前未分出且本位不同"）。画完做三件事：数一数总门数并对照 3n 量级；代入 a 等于 101、b 等于 011 在图上标出信号传播路径；再把 b 改成 100（只有最高位相同）重新标一遍，观察胜负信号在第二位就置位后，低位的与门如何被压制。三遍标注做完，"电路在算什么"这个问题就永久归你所有了。
这张 3 位小电路还有一个隐藏用途：它就是第 7 章拍卖场景与金融阈值判断的生产雏形——生产电路不过是你这张图的位宽放大版加输出封装。从教学例到生产件之间隔的不是新原理，只是参数与工程纪律。
最后补一个便于记忆的数字锚点：比较是最便宜的有语义运算之一——n 位比较约 3n 扇门、深度约 2n，32 位整数不到百扇门；同样的位宽做一次长乘法则要一个数量级以上的门数。所以当你为某个业务电路估算成本拿不定主意时，用它相当于几次比较来报数，是同行业里都能秒懂的语言。这张电路的问题链身份就此完成闭环：它是第 1 章那道题的化身，也是第 3 章一切加密动作的对象——下一节，我们把它整个装进保险箱。