首页>财经 > 正文
全球观焦点:Half-Aggregation of BIP 340 Signatures
来源: 鸵鸟区块链要闻 发布于:2022-07-09 05:45:44

来源:blockstream


(资料图片仅供参考)

作者:Jonas Nick

We are excited to share the current progress on our research into the aggregation of signatures based on curvesecp256k1: There is now an earlydraft Bitcoin Improvement Proposal (BIP) for non-interactive half-aggregation of BIP 340 Schnorr signatures. This proposal has a variety of potential applications in the Bitcoin ecosystem. Moreover, to the best of our knowledge, this would be the first BIP with a formal specification, which is a mathematically precise description of the scheme. The formal specification can be used to prevent multiple classes of security issues and potentially help future formal software verification efforts.

Half-Aggregation

About five years ago, signature half-aggregation wasfirst mentioned on the Bitcoin mailing list. It allows aggregating multiple Schnorr signatures into a single signature that is about half as long as the sum of the individual signatures. Importantly, this scheme is non-interactive, which means that a set of signatures can be half-aggregated by a third party without any involvement from the signers. This scheme has been discussed on and off over the years in the Bitcoin space but only recently received attention from the academic community.Chalkias, Garillot, Kondi and Nikolaenkoas well asChen and Zhaoprove security under sensible assumptions, which inspired us to start writing a specification. If you want to learn more about half-aggregation, have a look at the"cross-input signature aggregation" repositoryorthis presentation and pair-programming session.

Bitcoiners have already come up with various potential applications for half-aggregation. For example, half-aggregation can reduce the bandwidth requirement of off-chain networks that gossip BIP-340 signatures. On the other hand, half-aggregation applied to the Bitcoin consensus protocol could cut down on the size of transactions in multiple ways:

Bitcoin script opcodes requiring multiple signatures could take a single half-aggregate signature instead.

Transactions could have a single half-aggregate signature instead of one signature per input.

Since half-aggregation is non-interactive, block producers could aggregate transaction signatures into a single half-aggregate signature per block.

Note that some of these ideas have complex trade-offs (which are collectedhere). Our draft specification only covers the cryptographic scheme and does not prescribe a particular application. While it may be useful to some off-chain protocols immediately, we intend the half-aggregation specification to aid future discussions around consensus changes.

To avoid confusion, we would also like to mention a different signature aggregation approach that provides much larger space savings. We call itfull aggregationbecause the size of the aggregate signature is equal to a regular Schnorr signature. However, due to its complexity, full aggregation is not always preferable to half aggregation. In particular, similar to theMuSig2 multi-signature scheme, full aggregation is an interactive protocol with at least two rounds and requires securely keeping signing state. Also, it (probably) does not permit deterministic signing without adding relatively massive complications to the scheme (similar toMuSig-DNfor example). Therefore, we believe that even for protocols that already require interaction, the simplicity of half-aggregation may beat the efficiency of full aggregation.Our specification of half aggregation differs from the scheme initially discussed on the mailing list by the added capability forincrementalaggregation, which we found inChen and Zhao"s work. Incremental aggregation allows us to aggregate additional signatures into an existing half-aggregate signature. Surprisingly, this is a straightforward generalization of regular half-aggregation and does not add significant complexity to the specification.

Formal Specification

The half-aggregation BIP draft is similar in scope toBIP 340("BIP Schnorr") since both specify a cryptographic scheme without particular applications. BIP 340"s specification consists of two parts, the actual specification in pseudocode and a reference implementation in python. This situation is not ideal. This situation is not ideal, primarily because the meaning of the pseudocode is not specified. The readers rely on their intuition to determine what the pseudocode is doing; this judgment may differ from reader to reader. The python reference implementation can help in case the pseudocode is unclear. Many programmers are familiar with python, and it comes with an extensivelanguage reference. However, the reference manual describes the meaning of individual operations in natural language, which again leaves room for interpretation.In contrast, the half-aggregation BIP draft has aformalspecification. Each operation of the specification has a precisely defined meaning (semantics), which implies that the overall behavior of the scheme is unambiguous. Such precision is a nice feature, but on its own may not be worth the effort. Most importantly for us, the rigorous definition of the scheme paves the way forcomputer-aided formal proofs.

With software tools known as proof assistants, it is possible to prove that the formal specification has certain properties, like the absence of out-of-bound array access or integer overflow. Moreover, one can formally provecompletenessof the specification, i.e., applying the aggregation algorithm to valid BIP 340 signatures always yields a valid half-aggregate signature. In principle, it is also possible to prove the security of the specified scheme using proof assistants. In the case of half-aggregation, this would be a relevant and ambitious research project.Proving theorems about specifications is especially valuable because the behavior of specifications is often not identical to the abstract mathematical scheme they are based on. In fact, the security properties of the abstract scheme may not survive translation to a specification, leading to critical vulnerabilities. This problem can be circumvented if the proofs apply directly to the specification.A formal specification is also a necessary prerequisite to doformal verification, which is the process of proving that the behavior of an implementation matches that of the specification. This allows for writing a highly optimized implementation and then formally verifying it against a specification. If the specification is correct, then the implementation is also correct, and proofs about the specification carry over.

Implementations that are supposed to undergo formal verification are generally not written in common programming languages. Instead, implementers use languages likeVerifiable CorF*and its ecosystem.The formal specification language we use for half-aggregation ishacspec. One of its most compelling features is that it isembeddedin rust: hacspec specifications are also valid rust code. So one can build, run, manage dependencies and test the specification like any other rust project. Thus, the specification can also serve as a reference implementation and remove the need to add extra python code as in BIP 340. A downside is that readers of the BIP may not be as familiar with rust as with python. Additionally, hacspec code does not necessarily look like idiomatic rust and misses some primitives and rust standard library components. To help readers of the half-aggregation BIP draft, we also included informal pseudocode, which is similar in syntax and semantics to BIP 340"s pseudocode. For the kind of theorem proving and software verification mentioned above, the hacspec typechecker program can translate hacspec code into specialized languages like Coq, F*, and EasyCrypt, which are starting points for proof engineering.

Conclusion

Half-aggregation of BIP 340 signatures has potential applications in various scenarios. We hope our half-aggregation BIP draft can serve as a valuable foundation for further exploration. We invite you to reviewthe draftand provide feedback. What do you think about the absence of a python reference implementation and adding a formal specification written in hacspec? Besides being a fun experiment, we believe this is a promising direction that has the potential to advance the robustness of the Bitcoinecosystem significantly.

关键词: significantly

猜你喜欢

  • 天天即时看!景区开启人从众模式,何必人挤人,买台哈趣K1在家纳凉观影不好吗!
  • 天天新消息丨兄弟MFC-J3940DW打印机评测:彩色A3 细致成像
  • b站视频怎么保存在手机本地?b站一个硬币up主能得多少钱?
  • 全球快资讯丨京东居家携全链路业务亮相深圳家具展 覆盖供应链、服务、设计三大板块
  • 西方文明的发源地在哪?西方文明的三大支柱是什么?
  • 全球今热点:自动上下水成扫地机器人功能标配,云鲸打造上门服务新标杆
  • 世界热头条丨COLMO构建全屋智能新图景,“墅智专家”让智控更高端
  • 暴雨的降水量是多少毫米?降水量是怎么计算的?
  • 世界信息:一加 Ace Pro 至高配备 16GB 超大内存,打造行业流畅新体验
  • 当前热点-未来新冠疫苗或是鼻腔喷雾甚至一张贴片?福奇希望疫苗更多创新
  • 今日关注:iPhone二季度在印度出货120万部 本地产iPhone接近100万部
  • 【焦点热闻】东方甄选户外直播画风变了:俞敏洪吃桃子 董宇辉聊诗词
  • 每日焦点!助力乡村振兴,润初妍10周年携近千名经销商走进宏村
  • 《暗黑破坏神2重制版》遭俄罗斯黑客团队破解 联网模式将不再支持MOD
  • 联动狂魔《糖豆人》携手《WWE》 将于7月28日推出限时售卖皮肤
  • 官方发布《间谍过家家》第二部分先导预告 预计将于10月开播
  • 2022年国产游戏销量排行榜公布 《暖雪》获得上半年最畅销新游
  • 《雷神4》曝光海量原始概念设计图 电影全球票房创全系列新高
  • 今天是日本西瓜姐 《炼金工房》发布官图邀请你和莱莎一起吃瓜
  • 从此网络直播间使用BGM需付费!试行付酬标准现已出炉