大家好。我有一个算法问题想与大家探讨。服务器S需要对n个节点进行认证，S有一个批量认证的函数F(x)，F(x)的输入是x个节点的签名，如果x个节点的签名都验证通过，那么F(x)输出True，否则输出False。我们假设F(x)的时间复杂度是O(1)。任务是服务器S要找出所有的恶意节点。当n个节点中，恶意节点的数量为1，如何调用F(x)？ n个节点中恶意节点的数量对问题1中的算法有没有关系？假设F(x)的时间复杂度是O(n)，此时要找出所有恶意节点的算法复杂度是什么？除去批量认证算法，还有别的新方法吗？问题1中，用二分法最多调用log 2n次F(x)。问题2中，最差情况下所有的节点都是恶意时，二分法的效率降低太多了，比逐个认证还要慢。假设F(a)表示输入节点1依次到节点a共a个节点，那么当F(a+1) = False, F(a) = True时，就可以找出节点a+1是恶意节点，这种情况下，不管恶意节点的数量是多少，总共会调用n次F(x)。

使用批量认证对恶意节点的识别

alienx

大家好。我有一个算法问题想与大家探讨。

服务器S需要对n个节点进行认证，S有一个批量认证的函数F(x)，F(x)的输入是x个节点的签名，如果x个节点的签名都验证通过，那么F(x)输出True，否则输出False。我们假设F(x)的时间复杂度是O(1)。

任务是服务器S要找出所有的恶意节点。

当n个节点中，恶意节点的数量为1，如何调用F(x)？
n个节点中恶意节点的数量对问题1中的算法有没有关系？
假设F(x)的时间复杂度是O(n)，此时要找出所有恶意节点的算法复杂度是什么？
除去批量认证算法，还有别的新方法吗？

问题1中，用二分法最多调用log 2n次F(x)。问题2中，最差情况下所有的节点都是恶意时，二分法的效率降低太多了，比逐个认证还要慢。假设F(a)表示输入节点1依次到节点a共a个节点，那么当F(a+1) = False, F(a) = True时，就可以找出节点a+1是恶意节点，这种情况下，不管恶意节点的数量是多少，总共会调用n次F(x)。

Bintou

想了一个中午，感觉怪怪的。既然是“算法问题”，那么输入数据的分布应该限定。比如：考虑排序，可以假设数据本身就很随机，或者假定数据包括了一定的结构性，这样直接导致快排选pivot的方法不同。同样，n中找1或者n中找n，非要归类到一个算法中去考虑吗？n中找1的情况，二分法是不是已经是最优了？还有什么可抱怨的呢？如果是n中找n，有O(n)的算法也是最优了吧？也没什么可抱怨。现在最大的问题是你非要把它们扭在一起搞一个无可抱怨的算法，我看不出有必要，也没看出有这种可能。

至于“除去批量认证算法，还有别的新方法吗？“（所谓”批量认证“应该是”聚合签名/验签“技术吧？），批量认证或者聚合签名就不是为此设计的，如果n个节点中有f(n)个节点是恶意节点，f是以n为输入满足某种分别的函数，在特定情况下，最简单的验证签名也许就是好的。

alienx

Bintou 嗯嗯，上面的问题提的不好。当输入的数据分布限定时，例如n个节点中找1个或者是n个，都有对应最优的方法。

批量认证其实就是聚合签名/验签技术。批量认证能够实现对一批节点产生的聚合签名进行验证，但是当聚合签名没有通过时，无法找出具体的恶意节点。按照老师的分析，看来这个解决思路是不妥当的。