比原链研究院 | 一种弱同步网络假设下的门限签名系统

本贴最后更新于 1629 天前,其中的信息可能已经时移世异

近几年门限密码学在区块链系统里开始逐渐被应用,分为门限加密和门限签名,一般见于随机预言机、防审查、减少通信复杂度(HotStuff)、共识网络中防拜占庭(HoneyBadgerBFT 中用于 BA 环节的 common coin)以及作为分布式伪随机数生成器(coin tossing)的重要原语,其优越的资产协同防盗特性也慢慢被新兴数字资产托管机制所重视,今天我们主要讨论公钥密码学(PKC)里的门限签名机制。一种理想的门限签名系统是可以在异步的网络环境里做到容错容灾不可伪造(non-forgeability),并且拥有极度可靠安全的消息传输通道,签名份额的生成和验证是完全非交互式的,在初始密钥阶段具备可以防止拜占庭行为的异步分布式密钥生成(DKG)机制。

与基础签名机制类似,门限签名机制(Threshold Signature Schemes)也分为两部分:

门限密钥生成(Thresh-Key-Gen):基于安全参数构造一种分布式密钥生成协议 DKG,协议运行输出一个共同的公钥 pk 和分属不同参与方各自所有的私钥份额 ski,聚集起满足阈值数量的私钥份额可以构建出真正的私钥 sk。

门限签名(Thresh-Sig):基于分布式通信网络,各参与方通过自己的私钥份额 ski 完成对消息 m 的分布式协作签署并输出最终的可验证签名 Sig(sk, m),这个签名跟单独用 sk 私钥签出的一模一样,可以用所基于的基础签名机制里的验证函数进行本地验证,无需走通信交互验证

但是大多数情况下会通过使用一个可信的中心节点(dealer)来实现私钥份额的生成和分发。沙米尔秘密分享(Shamir Secret Sharing)是最简单的依赖中心 dealer 节点的门限密钥生成方法,基本原理是拉格朗日插值,在 (t, n) 门限构造中,dealer 会选择一个 (t-1) 次方的随机多项式 f,令 f(0)=s,s 即为要分享的秘密值,然后向每个节点分发该多项式曲线上的点 si=f(i) 作为各自的秘密份额值,简单来讲,三个点确定一个二次方程曲线(Lagrange interpolation formula)。为了解决中心作恶问题,人们又不断探索了基于承诺(commitment)的可验证秘密分享(VSS、PVSS),以及应用于异步网络的 VSS(Cobalt BFT 在区块链系统里也尝试了结合 PoW 准入机制的 AVSS)。有许多优秀成熟的 commitment scheme 可以借鉴应用,简单来讲承诺(commitment)算法 [C(M), D(M)]=Com(pk, M, r) 中 pk 是与承诺机制有关的公钥,M 是要承诺的原始值,r 是一个随机骰子,算法输出的 C 便是 commitment,D 则是需要秘密保管的 decommitment 值,在正式公开 M 之前先公开 M 的承诺 C,即先对自己要公布的消息做个上帝担保,约束自己无法更换 M,而对于 M 的受众或者接收者,它们可以通过之前公布的承诺和验证算法进行验证唯一性。这里我们主要关注非交互式的 VSS 实现。

此外,在过往的研究里,签名(Sig)的生成和验证大多是交互式的,并且依赖一个同步通信网络和广播通道(broadcast channel),节点们在某种设定下接收到特定消息后便同时启动签名协议,并严格遵循超时机制。而在互联网环境和区块链网络里,对网络假设的限定是有限的,所以门限系统要成功运作除了需要构造真正的 DKG 协议和非交互式签名机制外,还需要具备商用级的网络系统以及被验证过的成熟代码实现。这里我们(Bytom)尝试提出并构建一种弱同步网络假设下的门限签名分布式系统,主要对网络模型、DKG 构建、签名机制进行一些创新结合和应用,探索在实际网络环境里最小可实用的门限签名系统原型。

门限系统是一种(t, k, n)型 fault-tolerance 系统,t 代表网络最大容错,k 代表最小门限值,n 是节点数,一般设定 k>=t+1,但这种对网络分区(network partition)是无能为力的,所以在一个异步拜占庭网络里我们依然选用经典设定 k=n-t & t<n/3 去达成系统里的一个大多数共识。

门限网络或者通信模型是实现可实用门限系统需要认真考量的一个关键点。像 HoneyBadgerBFT 所构建的接近异步通信网络在现实案例中是少见的,一般会增加消息复杂度和通信轮次,异步网络模型主要依赖所接收到的消息类型和数量进行判断,因为时间因子(time-based)并不能区分谁是慢节点谁是恶意节点。但在这里我们更倾向采用高效的弱同步网络假设,即消息延迟和时钟偏移有上限(实际可接受)但未知,延迟的渐进是合理的,保障 liveness(safety 可以采用妥协的方法处理);能够对 crash、network failure、byzantine 等不同情况尽量做到分开处理,比如设置规定时间内可容忍的 crash 阈值,对于诚实节点发生 crash 后能够从一个规定的状态恢复等;并且假设网络故障总能被修复、遭受的 DoS 攻击总会停止;最后在构建通信通路上可以借助 PKI 和外部 CA 构建 TLS 链接,以及借助经典的 RBC 协议(reliable broadcast channel)。

DKG 是门限签名最为核心的环节也是第一阶段,负责完成门限密钥的生成和分发。VSS 是 DKG 的重要组成部分。上面提到 VSS 的基本原理是承诺机制,一般基于 Pedersen commitment,构造形如 C=mG+nH 的承诺(这里我们省去了一些对椭圆曲线群运算特征定义和假设,可以简单理解为椭圆曲线计算),其中 m 来自密钥构造多项式 f(x) 系数,而 n 来自 dealer 另外构造的一个随机多项式 h(x) 的系数,承诺集合 {Ci, 0<i<t} 是一种公开可获取的系数“证据”,用于证明 dealer 只承认一个合法的密钥多项式。各个参与方在获得 dealer 分发给自己的密钥份额 f(i) 和秘密值份额 h(i) 后,计算 f(i)G+h(i)H,如果与对应的承诺值(多项式计算)相等,则认为合法,如果不一致,则认为 dealer 出现作恶行为,开始向网络提交自己的抗议 complaint,其他人可以进行验证,如果发现事实如此,则立即停止协议,如果其他人验证后发现该 complaint 不合法,则发起 complaint 的节点会被标记不可信。VSS 过程简单来讲包括中心初始化密钥分发、构建承诺和重建密钥三部分内容,整个网络交互存在两轮(synchronous)全网广播(all-to-all)达成一致,最终将密钥份额和承诺传递给每个参与节点,这里我们会定义三种消息类型用于标记多轮消息序列并携带足够的信息用于计算门限密钥。

真正的 DKG 是需要去掉 VSS 里的那个中心,在分布式协作下生成秘密,避免单点泄漏风险,其原理也很简单,相当于 n 个节点同时各自选择秘密值并运行自己的 VSS,每个节点收集来自其他节点的秘密份额完成组装,组装后的结果便是真正私钥的份额,而各个合法节点各自分发的秘密值聚合起来便是最终的构造私钥,最后在进行承诺验证。这似乎很像一个 Multi-valued Validated Byzantine Agreement (MVBA) protocol (一种被广泛研究的可以对多种提案高效率达成共识的一致性协议算法,存在多个变种,比如异步公共子集 Common Subset)。

不过我们尽量避免这种复杂的实现,一般通过选举出 Leader 节点,统一协调处理这些 VSS 的完成情况和最终共识,定义序列,当大多数节点(n-t)完成各自的 VSS 阶段并被其他所有诚实节点所确认后,Leader 将这些已完成的 VSS 信息进行收集并重组提案,再经过两轮全网广播后,每个节点便会确定下各自最终的秘密份额,因此保障 liveness 对于我们的系统是十分关键的。如果 DKG 协议里任何一方出现恶意行为,协议都会立即停止,即 DKG 需要确保所有参与方的诚实行为。至此,一把公共的门限公钥和分属不同参与方的门限私钥份额便构造完毕。

签名阶段简单来讲是基于上面得到的密钥份额各自完成签署自己的签名份额,最后再完成统一组装,得到最终门限签名。Thresh-Sig 阶段的具体实现与所基于的数字签名算法有很大关系,例如 Schnorr 算法在计算签名 s 值时所依赖的秘密值 k 在常数项,s=k-z(H(K||M)),所以可以简单的将秘密值份额相组。而 ECDSA 中秘密值 k 是非线性的,即 s=(H(M)+zr)/k(其中 r 也是由 k 经过指数运算得来),存在两个秘密值(k 和 z)的乘运算,所以各个节点不能仅通过拥有 k 秘密值份额来完成最终签名值的组装,需要对公式进行变形,重新定义组合秘密值 kz,并分布式完成 kz 的秘密份额计算以及分发,甚至需要借助安全多方计算(在不泄漏各自 k 和 z 份额的前提下,完成 kz 的结果计算并输出 kz 的秘密份额给相应参与方)、同态加密机制以及零知识证明(range proof),因此多方的 ECDSA 门限签名在实现和效率上会比较复杂,现阶段以可实用的 2-2 方案研究居多。

不论是采用 ECDSA 还是 Schnorr 算法,最核心的问题依然是基于 DKG 和多方计算的原理去生成和分发签名算法中需要的秘密值,每个参与方基于各自的密钥份额和秘密值份额完成自己的签名过程,最后通过整体的交互组装获得最终的合法签名。同样的,如果无法达到足够门限阈值数量的合法签名方,签名协议也会立即停止。根据不同的应用场景需求,我们需要认真研究用于实现门限签名机制的底层签名算法,比如 ECDSA、EdDSA、Schnorr、BLS 等,不同的签名算法对应的门限机制实现复杂度和效率是不同的。

此外,一个完整的门限系统可能会有成员变更的需求,原有的密钥份额随之需要新一轮变更,最直观的做法是引入周期的概念,通过同步网络和共识协议发起新一轮密钥生成,产生新的主公钥和私钥份额,用超时机制防止阻塞。成员变更和 DKG 是一种比较精细(或脆弱)的系统,任何一个成员 fail 或者 fault 都会引发状况外。在实现上我们用状态机复制原理构建门限(DKG)节点,基于消息输入更换自身状态(例如 node_remove,leader_change,group_update)。

门限密码学随着结合应用场景的需求研究增多,不断完善自身成熟度,尤其是随着高度可靠的代码实现增多,随着复杂网络环境里的系统架构成熟,有希望在价值网络里扮演“门神”的重大作用,同时会促进对零知识证明、同态加密技术的进一步场景化应用,是当下区块链新技术领域为数不多值得深入研究和实战的研究方向。现代密码学与价值网络相辅相成,前者给予后者“上帝保障”,后者给予前者“伟大战场”。

比原链研究院 刘秋杉

  • 区块链

    区块链是分布式数据存储、点对点传输、共识机制、加密算法等计算机技术的新型应用模式。所谓共识机制是区块链系统中实现不同节点之间建立信任、获取权益的数学算法 。

    91 引用 • 751 回帖 • 5 关注

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...
bytom
一种多样性比特资产的区块链交互协议 杭州

推荐标签 标签

  • CentOS

    CentOS(Community Enterprise Operating System)是 Linux 发行版之一,它是来自于 Red Hat Enterprise Linux 依照开放源代码规定释出的源代码所编译而成。由于出自同样的源代码,因此有些要求高度稳定的服务器以 CentOS 替代商业版的 Red Hat Enterprise Linux 使用。两者的不同在于 CentOS 并不包含封闭源代码软件。

    238 引用 • 224 回帖
  • DNSPod

    DNSPod 建立于 2006 年 3 月份,是一款免费智能 DNS 产品。 DNSPod 可以为同时有电信、网通、教育网服务器的网站提供智能的解析,让电信用户访问电信的服务器,网通的用户访问网通的服务器,教育网的用户访问教育网的服务器,达到互联互通的效果。

    6 引用 • 26 回帖 • 518 关注
  • Firefox

    Mozilla Firefox 中文俗称“火狐”(正式缩写为 Fx 或 fx,非正式缩写为 FF),是一个开源的网页浏览器,使用 Gecko 排版引擎,支持多种操作系统,如 Windows、OSX 及 Linux 等。

    7 引用 • 30 回帖 • 457 关注
  • 书籍

    宋真宗赵恒曾经说过:“书中自有黄金屋,书中自有颜如玉。”

    76 引用 • 390 回帖 • 1 关注
  • Hibernate

    Hibernate 是一个开放源代码的对象关系映射框架,它对 JDBC 进行了非常轻量级的对象封装,使得 Java 程序员可以随心所欲的使用对象编程思维来操纵数据库。

    39 引用 • 103 回帖 • 676 关注
  • Vditor

    Vditor 是一款浏览器端的 Markdown 编辑器,支持所见即所得、即时渲染(类似 Typora)和分屏预览模式。它使用 TypeScript 实现,支持原生 JavaScript、Vue、React 和 Angular。

    308 引用 • 1658 回帖 • 1 关注
  • 大疆创新

    深圳市大疆创新科技有限公司(DJI-Innovations,简称 DJI),成立于 2006 年,是全球领先的无人飞行器控制系统及无人机解决方案的研发和生产商,客户遍布全球 100 多个国家。通过持续的创新,大疆致力于为无人机工业、行业用户以及专业航拍应用提供性能最强、体验最佳的革命性智能飞控产品和解决方案。

    2 引用 • 14 回帖 • 2 关注
  • 快应用

    快应用 是基于手机硬件平台的新型应用形态;标准是由主流手机厂商组成的快应用联盟联合制定;快应用标准的诞生将在研发接口、能力接入、开发者服务等层面建设标准平台;以平台化的生态模式对个人开发者和企业开发者全品类开放。

    15 引用 • 127 回帖
  • Markdown

    Markdown 是一种轻量级标记语言,用户可使用纯文本编辑器来排版文档,最终通过 Markdown 引擎将文档转换为所需格式(比如 HTML、PDF 等)。

    163 引用 • 1446 回帖
  • Ruby

    Ruby 是一种开源的面向对象程序设计的服务器端脚本语言,在 20 世纪 90 年代中期由日本的松本行弘(まつもとゆきひろ/Yukihiro Matsumoto)设计并开发。在 Ruby 社区,松本也被称为马茨(Matz)。

    7 引用 • 31 回帖 • 166 关注
  • Kubernetes

    Kubernetes 是 Google 开源的一个容器编排引擎,它支持自动化部署、大规模可伸缩、应用容器化管理。

    108 引用 • 54 回帖
  • Google

    Google(Google Inc.,NASDAQ:GOOG)是一家美国上市公司(公有股份公司),于 1998 年 9 月 7 日以私有股份公司的形式创立,设计并管理一个互联网搜索引擎。Google 公司的总部称作“Googleplex”,它位于加利福尼亚山景城。Google 目前被公认为是全球规模最大的搜索引擎,它提供了简单易用的免费服务。不作恶(Don't be evil)是谷歌公司的一项非正式的公司口号。

    49 引用 • 192 回帖
  • 微软

    微软是一家美国跨国科技公司,也是世界 PC 软件开发的先导,由比尔·盖茨与保罗·艾伦创办于 1975 年,公司总部设立在华盛顿州的雷德蒙德(Redmond,邻近西雅图)。以研发、制造、授权和提供广泛的电脑软件服务业务为主。

    8 引用 • 44 回帖
  • 服务

    提供一个服务绝不仅仅是简单的把硬件和软件累加在一起,它包括了服务的可靠性、服务的标准化、以及对服务的监控、维护、技术支持等。

    41 引用 • 24 回帖
  • Wide

    Wide 是一款基于 Web 的 Go 语言 IDE。通过浏览器就可以进行 Go 开发,并有代码自动完成、查看表达式、编译反馈、Lint、实时结果输出等功能。

    欢迎访问我们运维的实例: https://wide.b3log.org

    30 引用 • 218 回帖 • 594 关注
  • VirtualBox

    VirtualBox 是一款开源虚拟机软件,最早由德国 Innotek 公司开发,由 Sun Microsystems 公司出品的软件,使用 Qt 编写,在 Sun 被 Oracle 收购后正式更名成 Oracle VM VirtualBox。

    10 引用 • 2 回帖 • 1 关注
  • Shell

    Shell 脚本与 Windows/Dos 下的批处理相似,也就是用各类命令预先放入到一个文件中,方便一次性执行的一个程序文件,主要是方便管理员进行设置或者管理用的。但是它比 Windows 下的批处理更强大,比用其他编程程序编辑的程序效率更高,因为它使用了 Linux/Unix 下的命令。

    122 引用 • 73 回帖 • 2 关注
  • 设计模式

    设计模式(Design pattern)代表了最佳的实践,通常被有经验的面向对象的软件开发人员所采用。设计模式是软件开发人员在软件开发过程中面临的一般问题的解决方案。这些解决方案是众多软件开发人员经过相当长的一段时间的试验和错误总结出来的。

    198 引用 • 120 回帖
  • OpenShift

    红帽提供的 PaaS 云,支持多种编程语言,为开发人员提供了更为灵活的框架、存储选择。

    14 引用 • 20 回帖 • 596 关注
  • IPFS

    IPFS(InterPlanetary File System,星际文件系统)是永久的、去中心化保存和共享文件的方法,这是一种内容可寻址、版本化、点对点超媒体的分布式协议。请浏览 IPFS 入门笔记了解更多细节。

    20 引用 • 245 回帖 • 232 关注
  • 国际化

    i18n(其来源是英文单词 internationalization 的首末字符 i 和 n,18 为中间的字符数)是“国际化”的简称。对程序来说,国际化是指在不修改代码的情况下,能根据不同语言及地区显示相应的界面。

    7 引用 • 26 回帖 • 1 关注
  • 友情链接

    确认过眼神后的灵魂连接,站在链在!

    24 引用 • 373 回帖 • 7 关注
  • Sphinx

    Sphinx 是一个基于 SQL 的全文检索引擎,可以结合 MySQL、PostgreSQL 做全文搜索,它可以提供比数据库本身更专业的搜索功能,使得应用程序更容易实现专业化的全文检索。

    1 引用 • 171 关注
  • Unity

    Unity 是由 Unity Technologies 开发的一个让开发者可以轻松创建诸如 2D、3D 多平台的综合型游戏开发工具,是一个全面整合的专业游戏引擎。

    25 引用 • 7 回帖 • 249 关注
  • 招聘

    哪里都缺人,哪里都不缺人。

    189 引用 • 1056 回帖
  • Scala

    Scala 是一门多范式的编程语言,集成面向对象编程和函数式编程的各种特性。

    13 引用 • 11 回帖 • 101 关注
  • Vue.js

    Vue.js(读音 /vju ː/,类似于 view)是一个构建数据驱动的 Web 界面库。Vue.js 的目标是通过尽可能简单的 API 实现响应的数据绑定和组合的视图组件。

    261 引用 • 662 回帖 • 2 关注