论文主要提出了一种针对共识机制PoS的多重签名算法Pixel。

1、介绍

所有基于PoS的区块链以及允许的区块链均具有通用结构，其中节点运行共识子协议，以就要添加到分类账的下一个区块达成共识。这样的共识协议通常要求节点检查阻止提议并通过对可接受提议进行数字签名来表达其同意。当一个节点从特定块上的其他节点看到足够多的签名时，会将其附加到其分类帐视图中。

由于共识协议通常涉及成千上万的节点，为了达成共识而共同努力，因此签名方案的效率至关重要。此外，为了使局外人能够有效地验证链的有效性，签名应紧凑以进行传输，并应快速进行验证。已发现多重签名对于此任务特别有用，因为它们使许多签名者可以在公共消息上创建紧凑而有效的可验证签名。

补充知识：多重签名
是一种数字签名。在数字签名应用中，有时需要多个用户对同一个文件进行签名和认证。比如，一个公司发布的声明中涉及财务部、开发部、销售部、售后服务部等部门，需要得到这些部门签名认可，那么，就需要这些部门对这个声明文件进行签名。能够实现多个用户对同一文件进行签名的数字签名方案称作多重数字签名方案。
多重签名是数字签名的升级，它让区块链相关技术应用到各行各业成为可能。在实际的操作过程中，一个多重签名地址可以关联n个私钥，在需要转账等操作时，只要其中的m个私钥签名就可以把资金转移了，其中m要小于等于n，也就是说m/n小于1，可以是2/3, 3/5等等，是要在建立这个多重签名地址的时候确定好的。

本文提出了Pixel签名方案，这是一种基于配对的前向安全多签名方案，可用于基于PoS的区块链，可大幅节省带宽和存储要求。为了支持总共T个时间段和一个大小为N的委员会，多重签名仅包含两个组元素，并且验证仅需要三对配对，一个乘幂和N -1个乘法。像素签名几乎与BLS多重签名一样有效，而且还满足前向安全性。此外，就像在BLS多签名中一样，任何人都可以非交互地将单个签名聚合到一个多签名中。

有益效果：
为了验证Pixel的设计，将Pixel的Rust实施的性能与以前的基于树的前向安全解决方案进行了比较。展示了如何将Pixel集成到任何PoS区块链中。接下来，在Algorand区块链上评估Pixel，表明它在存储，带宽和块验证时间方面产生了显着的节省。我们的实验结果表明，Pixel作为独立的原语并在区块链中使用是有效的。例如，与一组128位安全级别的N = 1500个基于树的前向安全签名（对于T = 232）相比，可以认证整个集合的单个Pixel签名要小2667倍，并且可以被验证快40倍。像素签名将1500次事务的Algorand块的大小减少了约35％，并将块验证时间减少了约38％。

对比传统BLS多重签名方案最大的区别是BLS并不具备前向安全性。

对比基于树的前向安全签名，基于树的前向安全签名可满足安全性，但是其构造的签名太大，验证速度有待提升。本文设计减小了签名大小、降低了验证时间。

补充知识：前向安全性
是密码学中通讯协议的安全属性，指的是长期使用的主密钥泄漏不会导致过去的会话密钥泄漏。前向安全能够保护过去进行的通讯不受密码或密钥在未来暴露的威胁。如果系统具有前向安全性，就可以保证在主密钥泄露时历史通讯的安全，即使系统遭到主动攻击也是如此。

2、技术概述

构建基于分层身份的加密（HIBE）的前向安全签名，并增加了在同一消息上安全地聚合签名以及生成没有可信集的公共参数的能力。以实现：
1、生成与更新密钥
2、防止恶意密钥攻击的安全性
3、无效的信任设置

对于常见的后攻击有两种变体：
1、短程变体：对手试图在共识协议达成之前破坏委员会成员。解决：通过假设攻击延迟长于共识子协议的运行时间来应对短距离攻击。
2、远程变体：通过分叉选择规则解决。
前向安全签名为这两种攻击提供了一种干净的解决方案，而无需分叉选择规则或有关对手和客户的其他假设。（说明前向安全签名的优势）。

应用于许可的区块链共识协议（例如PBFT）也是许多许可链（例如Hyperledger）的核心，在这些区块链中，只有经过批准的方可以加入网络。我们的签名方案可以类似地应用于此设置，以实现前向保密性，减少通信带宽并生成紧凑的块证书。

3、前向安全签名

定义

传统Bellare-Miner 模型，消息空间M的前向安全签名方案FS由以下算法组成：
1、Setup
pp ←Setup(T), pp为各方都同意的公共参数，Setup(T)表示在T时间段内对于固定参数的分布设置。

2、Key generation
(pk,sk1) ←Kg
签名者在输入的最大时间段T上运行密钥生成算法，以为第一时间段生成公共验证密钥pk和初始秘密签名密钥sk1。

3、Key update
skt+1←Upd(skt) 签名者使用密钥更新算法将时间段t的秘密密钥skt更新为下一个周期的skt + 1。该方案还可以为任何t0> t提供“快速转发”更新算法skt0←$ Upd0（skt，t0），该算法比重复应用Upd更有效。

4、Signing
σ ←Sign(skt,M),在输入当前签名密钥skt消息m∈M时，签名者使用此算法来计算签名σ。

5、Verification
b ← Vf(pk,t,M,σ)任何人都可以通过运行验证算法来验证消息M在公共密钥pk下的时间段t内的签名M的签名，该算法返回1表示签名有效，否则返回0。

改进

1、依靠非对称双线性组来提高效率，我们的签名位于G2×G1中而不是G2 ^2中。这样，就足以给出公共参数到G1中（然后我们可以使用散列曲线实例化而无需信任设置），而不必生成“一致的”公共参数（hi，h0 i）=（gxi 1，gxi 2）∈G1× G2。

2、密钥生成算法，公钥pk更小，参数设置提升安全性。

4、前向多签名

除了第3节中的前向安全签名方案的算法外，密钥验证模型中的前向安全多重签名方案FMS还具有密钥生成，该密钥生成另外输出了公钥的证明π。
新增Key aggregation密钥汇总、Signature aggregation签名汇总、Aggregate verification汇总验证。满足前向安全的多重签名功能的前提下也证明了其正确性和安全性。

5、基于PoS的区块链中的Pixel

1、PoS在后继损坏中得到保护
后继损坏：后验证的节点对之前的共识验证状态进行攻击破坏。
在许多用户在同一条消息上传播许多签名（例如交易块）的情况下，可以将Pixel应用于所有这些区块链中，以防止遭受后继攻击并潜在地减少带宽，存储和计算成本。

2、Pixel整合
为了对区块B进行投票，子协议的每个成员使用具有当前区块编号的Pixel签署B。当我们看到N个委员会成员在同一块B上签名的集合时，就达成了共识，其中N是某个固定阈值。最后，我们将这N个签名聚合为单个多重签名Σ，而对（B，Σ）构成所谓的区块证书，并将区块B附加到区块链上。

3、注册公共密钥
希望参与共识的每个用户都需要注册一个参与签名密钥。用户首先采样Pixel密钥对并生成相应的PoP。然后，用户发出特殊交易（在她的消费密钥下签名），注册新的参与密钥。交易包括PoP。选择在第r轮达成协议的PoS验证者，检查（a）特殊交易的有效性和（b）PoP的有效性。如果两项检查均通过，则使用新的参与密钥更新用户的帐户。从这一点来看，如果选中，则用户将使用Pixel登录块。
即不断更换自己的参与密钥，实现前向安全性。

4、传播和聚集签名
各个委员会的签名将通过网络传播，直到在同一块B上看到N个委员会成员的签名为止。请注意，Pixel支持非交互式和增量聚合：前者意味着签名可以在广播后由任何一方聚合，而无需与原始签名者，而后者意味着我们可以将新签名添加到多重签名中以获得新的多重签名。实际上，这意味着传播的节点可以对任意数量的委员会签名执行中间聚合并传播结果，直到形成块证书为止。或者，节点可以在将块写入磁盘之前聚合所有签名。也就是说，在收到足够的区块证明票后，节点可以将N个委员会成员的签名聚集到一个多重签名中，然后将区块和证书写入磁盘。

5、密钥更新
在区块链中使用Pixel时，时间对应于共识协议中的区块编号或子步骤。将时间与区块编号相关联时，意味着所有符合条件的委员会成员都应在每次形成新区块并更新轮回编号时更新其Pixel密钥。

6、实验评估

在Algorand 项目上进行实验评估，与Algorand项目自带的防止后腐败攻击的解决方案BM-Ed25519以及BLS多签名解决方案做对比。

存储空间上：

签名集所占存储空间对比 区块链长期存储对比

节省带宽：
Algorand使用基于中继的传播模型，其中用户的节点连接到中继网络（具有更多资源的节点）。如果在传播过程中没有聚合，则中继和常规节点的带宽像素节省来自较小的签名大小。每个中继可以服务数十个或数百个节点，这取决于它提供的资源。

在达成共识以达成交易块的过程中，传播一组4500个签名的总带宽

节省验证时间

验证时间减少