作者:AdamISZ

来源:https://github.com/AdamISZ/AdaptorSecurityDoc/tree/main

作者注:本文为关于适配器签名安全性的一个简短笔记。当前处于 “草稿” 及 “未审核” 状态。

草稿意味着它还不是最终版本,可能发生变更。

未审核意味着还没有谁认定本文中的任何描述是正确的。

概述

在本文中,我们给出了 Schnorr 签名语境下的 “签名适配器(signature adaptor)” 的定义(该术语最早由 Poelstra 提出 [1] ),(具体来说,是公钥前缀版本由 BIP340 [4] 标准化的 Schnorr 签名)。我们会从一个 “玩具” 定义开始,为单一公钥 $P$ 指定。

(回顾关于这个问题的更早的工作)之后,我们会正式声明这种构造的安全性特性。

然后,我们会解释,为什么这样一种 “签名适配器” 可能合并到一种 3 轮次的 MuSig [2] 协议中(:下文使用的 “MuSig” 全部都指的是 这篇 论文中的构造;再说清楚一点,不是 MuSig2 [3] ),从而可以用一个聚合公钥($P _ {agg}$)签名。我们还会解释,它的安全性属性跟前面的案例有什么关系。

然后,我们会处理在一个 MuSig 签名会话中 并行地 使用多个签名适配器的情形。具体来说,我们处理的可能是最重要的情形:同一个 (因此是私密的)适配器点并行地用在多个不同的签名会话中。我们发现,这种构造的安全性可以通过一种化约法(reduction argument)来证明,但也要加上一些重要的说明。在未来,这个领域可能需要进一步的工作。

最后一部分分析比较实用,因为它适用于需要签名适配器的最为著名的构造,即 “基于适配器签名的 CoinSwap” [14] [15] 、匿名的多跳锁定 [16] ,以及更奇异的版本,比如 “多方 S6”[6] 。

记号

虽然我们默认使用椭圆曲线 secp256k1(见下一段),下文的论述对任何其它能使离散对数问题难解的素数阶循环群(group of prime order)应该也成立。

我们使用 $\mathbb{H}$ 来表示由 BIP340 [4] 指定的哈希函数,用于哈希消息(当然,用来做其他事也是可以的)。我们使用 $\mathbb{H} _ c$ 来表示用于承诺到曲线点的哈希函数,用在这里讨论的未修正和修正过的 MuSig 版本中。

在我们提到要创建 nonce 值的时候,一定说的是 “随机选出”,也即,没有用于表示 “确定性随机” 的记号。其安全性和不安全性已经在 BIP340 和 MuSig2 BIP [5] (以及其它地方)有详细讨论。

此外,我们总是使用 $R$ 来表示签名中的 nonce 点,而其对应的标量值会写成 k (还会加上适量的上下标)。

关于签名适配器的早期工作

在提出我们的基础定义(从而为安全性论证打下基础)之前,值得先看看其他人是怎么看待签名适配器的安全性的。

据我们所知,正式处理签名适配器的安全性的工作可追溯到 Fournier [13] 和 Aumayr 等人 [9] 。先看后者,在 “敌手可访问一种常规的签名断言机以及一个适配器签名断言机” 的假设下,可以定义出 “EUF-CMA 安全性”(译者注:“EUF-CMA” 意味着 “选择明文攻击下的实质不可伪造性”)。该论文的定义 1 声称,在这个敌手可以得到需要伪造的消息的一个签名适配器的时候,无法伪造完整签名。我们认为,这个定义有点太弱了,因为更有意义的是考虑这样一个场景:敌手可以获得对 一条 消息的 多个 签名适配器,以伪造完整的签名。作为对该模型的批评,这是否成立,是可以辩论的,但是,这一点却正是本文剩余部分讨论的核心。

待完成:包含对更新的 Wei Dai 论文的索引。

同样的安全模型也被用在关于 “支付通道” 的论文 [12] 中。许多这样的论文都需要一种通用的构造,而非专属于 Schnorr 签名的构造,尤其是因为他们考虑了使用 ECDSA 而非 Schnorr 作为例子展示签名适配器的可能性 —— 但 ECDSA 显然在密码学上更加复杂。

也与此相关的是,从 [9] 开始,有一种说法是签名适配器本身(被叫作 “预签名”)也是不可伪造的。但是,这种说法假设了一个细微的差别,在我们的附录 D 里面得到了正式的证明:敌手无法伪造 给定 的一个 “陈述” $T$(在我们这个案例中就是一个曲线点,或者一个公钥)的适配器签名。但这没有涉及敌手使用一个随机的、非预先选定的 $T$ 伪造适配器签名的能力;而且,实际上,这种能力是下面的论证的核心。(此外,也很难说这超越了实用性协议的范围,因为随机选出 $T$ 值的情况是很常见的)。

Fournier 在 [13] 提出了一个密切相关的论点,直接引用如下:EUF-CMA [VES] 并不涉及签名加密手段的不可伪造性。实际上,即使敌手无需签名密钥就可以制作有效的 VES 密文,那也是完全具备这种特性的。当然,不能允许敌手有能力伪造某一个加密密钥的 VES 密文,否能,他们就可以伪造他们已经知道解密密钥的加密签名,然后解密它(从而打破安全性)… 。实际上,该论文在其后续的第三章含蓄地指出,也许存在一些协议,签名适配器会由多方合作协议中的其他人来创建。在 Fournier 的模型中,他将签名适配器当作 “一次性的可验证加密签名(VES)”,而 “一次性” 当然指的是签名适配器的这种属性:一旦揭晓明文,加上早已知道的密文,就会揭晓(加密)私钥(在 Schnorr 签名的语境下,就是一个离散对数,也即对应于 $T$ 的 $t$)。虽然其模型与 [9] 不同,但大体上,其安全性论证是相似的。

在 Erwig 等人所作的《两方适配器签名》[10] 中,[9] 的模型得到了延伸,考虑了相同的模型如何应用到从一个 ID 协议中派生的任意签名方案中。因此,它作出了富有启发的注释:根据定义,这样的签名适配器在唯一签名方案(unique signature scheme)(比如 BLS [11] )中是不可能实现的(Fournier 在其论文中也简要提到了这一点)。这篇论文也正式地将模型延伸到多方签名的语境,跟本文的关注点一样,但使用了一种 KOSK(“私钥知识”)模型,与前面提到的 MuSig 和 MuSig2 不同。

BIP340 Schnorr 签名的单公钥签名适配器

给定 BIP340 对公钥 $P$、消息 $m$、私钥(在这里记作 $x$)和签名 $(R, σ)$ 的定义,我们定义一种 “签名适配器” 创建算法 AdaptorCreate,它取一个标量 $t ∈ Z _ N$ 以及前述定义的一个公钥 $P$、一条消息 $m$ 以及一个签名 $(R, σ)$ 作为输入,输出一个 “签名适配器”,它是一个数组 $ (R, σ’ , T)$ 。

$T$ 有时候会被称为 “适配器点”,对应的 $t$ 则是 “适配器秘密”。

创造签名适配器的算法是先计算:

$$T := tG$$

$$σ’ := σ - t$$

然后返回 $ (R, σ’ , T)$ 。在这个返回的数组中包含 $R$ 的尴尬之处直接关系到为什么这个过程是 “无用的”,我们后文会说明。

然后,我们定义一种算法 AdaptorVerify ,它取一个签名适配器 $ (R, σ’ , T)$ 为输入,然后计算:

$$σ’G ?= R - T + \mathbb{H}(R||P||m)P$$

然后返回真或假。

如果上述定义看起来是错的,请注意:

读者可能更熟悉 “签名适配器” 的等式定义:$\sigma’ = k + \mathbb{H}(R+T||P||m)x$ 为点 $T$ 的适配器。这里给出的减法版本是等价的,但稍为容易分析,因为由 $T$ 构成的 “调整因子” 现在仅仅出现在哈希函数 之外。再看一个等价的版本:重新定义 $R’ = R + T$ ,因此 $R = R’ - T$ ,因此 $\sigma’ = R’ - T + \mathbb{H}(R||P||m)P$ 。

这个等式可以用下面这个任务来说明:假设你想要为你的私钥 $x$ 和消息 $m$ 创建一个适配器签名,适配器点为 $T$,且你不知道 $T$ 背后的离散对数。在 “另一种” 形式化版本 $\sigma’ = k + \mathbb{H}(R+T||P||m)x$ 中,你可以直接做这样的计算,因为它只需要 $T$ ,并不需要 $t$ 。而在这种新的形式中,你必须先随机选出一个 $k _ 2$ 然后定义 $k _ 2 = k - t$,从而让 $R = R _ 2 + T$ ,然后才能计算 $\sigma’ = k _ 2 + \mathbb{H}(R||P||m)x$ ,然后返回 $(R, \sigma’, t)$ 作为你的适配器。因此,当一个对手通过发布 $\sigma = \sigma’ + t$ 揭晓一个签名时,你可以通过减法得出此前未知的 $t$。

论点 1

上面定义的单公钥签名适配器是诚实验证者零知识的。

首先,我们定义出创建签名适配器的另一种算法,我们称为 AdaptorForge

  1. 选出随机数 $k \in Z _ N$
  2. 令 $R := kG$
  3. 随机选出 $\sigma’ \in Z _ N$
  4. 令 $T := R + \mathbb{H}(R||P||m)P - \sigma’G$

因此,一个敌手可以制作出一个签名适配器 $(R, \sigma’, t)$ ,显然可以通过 AdaptorVerify ,无论你选出的 $R, \sigma’$ 是什么数值都可以(甚至无需一对真实的 $(R, \sigma’)$ 先存在,这当然意味着伪造更加容易)。不过,请注意,敌手无法为选定的签名适配器找出秘密 $t$ ,除非他能抽取椭圆曲线上的离散对数(证明:假设相反情形,敌手 能够 找出 $t$ ,那么这暗示着他能从公钥 $P$ 中抽取出私钥 $x$,又因为 $x = \frac{t + \sigma’ -k}{\mathbb{H}(R||P||m)}$ ,而敌手拥有所有的 RHS。因此这个敌手在不需要跟断言机互动的情形下抽取了 $P$ 的离散对数)。

AdaptorCreate 的执行当成一种跟挑战者 $C$ 的互动,它会以随机数值回复对 $\mathbb{H}$ 的调用(正是合格的 “诚实验证者”,因为我们默认假设该挑战者所返回的数值是真正随机的):

  • 发送 $R, P, m$ 给 $C$
  • 从 $C$ 处获得 $\mathbb{H}(R||P||m)$
  • 输出 $T, \sigma’, R$

我们可以将相同的逻辑应用在 Schnorr 身份验证协议中,如 Boneh 和 Shoup [7] 中的定理 19.4 一样:如果敌手可以使用 AdaptorForge 伪造副本,且其统计分布跟我们从使用 AdaptorCreate 的诚实应用中看到的没有区别,那么我们就拥有 “诚实验证者零知识(HVZK)” 安全性。

AdaptorForge 可以作为 HVZK 定义中的 “模拟器($Sim$)”,只需传入公钥(不是私钥),它就可以随机选出 $\sigma’$,然后定义 $T$(也是完全随机的,假定有一种理想的哈希函数)。在使用 AdaptorCreate 的时候,$t$ 是由(知晓私钥的)创建者选出的,然后 $\sigma’$ 是使用 $\sigma - t$ 计算出来的,而 $\sigma$ 是常规的 Schnorr 签名,而且,我们同样假设有一种理想的哈希函数,其输出是均匀随机的。在两种情况下,因为挑战数值(建模为随机数断言机(RO)的输出)是随机的,而且独立于输入 $R, P, m$,所以输出值 $(T, \sigma’)$ 的分布也将是均匀随机的。

注意,AdaptorForge 不是什么 “新发现” 或者令人惊讶的结果,它是这样的 “签名适配器” 的众所周知的固有属性,只是它对这个概念的发展至关重要。而且,如前面所指出的,[9] 并没有提到这一点。

我们已经观察到两件事:签名适配器不会泄露关于私钥(在这里是 $x$)的信息,以及,签名适配器很容易伪造,即,它本身不是电子签名。(当然,请注意,前者并不 意味着 后者;真正的电子签名方案就是反例)。

因此,我们的论点是,在创建适配器的场景下,不需要对底层签名方案(在这里是 BIP340 Schnorr 签名)不为造型的更复杂的论证;根据零知识的定义,敌手没有从任何数量的适配器中得到任何额外的信息,所以没有改变(底层签名方案的特性)。

为什么单公钥签名的适配器是无用的

我们说上述算法是 “无用的”,因为它没有提供以下任何一种特性:

  • 一种创建强制机制的办法,可以保证公布对一条预先定义的消息的签名将揭晓一个秘密值
  • 一种若没有本算法就无法实现的嵌入秘密数据的新办法

在第一点上,我们观察到,Schnorr 签名并非 唯一的;意思是,你只需使用另一个 nonce 值 $R$ ,就可以为相同的语境 $P, m$ 创建另一个签名。因此,AdaptorCreate 的输出 $(R, \sigma’, t)$ 将不允许强制揭晓 $t$ ,只要你还可以创建新的签名,例如,使用另一个 $R$ 来许可一笔比特币交易(也即 “预先定义的消息”)。这就是为什么本文剩余的部分都是关于 MuSig 场景的,其中,在签名以合作方式完成之前,$R$ 可以是固定的(以聚合的形式)。

(注意,Dryja 的 “谨慎日志合约”[8] 也应用了类似的推理,“固定了” $R$,只不过出于不同的目的:为了防止通过签名两条相互矛盾的消息来含糊其词。)

在第二点上,显然将秘密数据隐藏在公开数据中是容易的事,只要秘密的发送者和接受者可以提前分享一些私钥;例子如一次性密码本(one-time pad)。这不是要贬低公开的随机性对隐写术的有用性(而且,比如说,在比特币区块链上,占最大比例的数据就是以签名和公钥形式体现的公开随机性);只是想说,适配器签名不是为此而生的算法;简单的减法或 XOR(异或运算)也有相同的效果。

多方(MuSig)场景的定义

我们将从定义开始:

  • 签名语境 $c$ 将由一组由 $n$ 个参与者 $p$(记为一组有序列表 $p _ 1, …, p _ n$)构成的合作团体,以及一条待签名的消息 $m$ 组成。
  • 算法 KeySetup,取一组来自参与者 $p$ 的公钥 $\prod _ i$ ,然后为每一个成员输出一个公钥 $P _ i$ 。这个算法是由 MuSig 论文定义的。注意,我们将使用记号 $x _ i$ 来表示 $P _ i$ 的私钥(因此,这是起始公钥 $\prod _ i$ 的私钥的非线性版本)。$P _ {agg}$ 定义为 $\sum _ iP _ i$ 。
  • 算法 Sign1Check,由每个成员 $p _ i$ 各自运行,取来自其他每一个成员(即 $p _ j, j \not= i$)的哈希值 $h _ j$ 为输入,然后在且仅在从其他成员处收到的数值是预先一致同意的哈希函数 $H _ c$ 的有效输出时返回 “真”。
  • 算法 Sign2Check,由每个成员 $p _ i$ 各自运行,取来自其他每一个成员(即 $p _ j, j \not= i$)的公钥 $R _ j$ 以及 $R _ i$ 为输入,然后,在 $\mathbb{H} _ c(R _ j) \not= h _ j$ 时输出 “拒绝”;而在所有的哈希值都匹配的时候输出 $R _ {agg} = \sum _ {k=1}^{n} R _ k$ 。注意,每一个 $R _ k$ 背后都有一个对应的私钥 $k _ k$ 。
  • 算法 AdaptorCreateM,可以由任何成员 $p _ i$ 运行,取 KeySetup 的输出 $P _ {agg}$、Sign2Check 的输出 $R _ {agg}$ 作为输入,然后输出一个适配器:$(T _ i, \sigma’ _ i)$ 。注意,这个元组不再包含 $R$(跟单公钥适配器不同)。

请注意,Sign1CheckSign2Check 是分别在 MuSig 算法(本身要求三轮交互)的第一轮和第二轮中运行的;MuSig 论文给出了完整的描述。

此外,根据定义,AdaptorCreateM 只能在成功完成前面三个算法后运行。

现在,我们定义三种独立的验证算法:

  • $\mathbb{V} _ s$ 取一个元组 $(\sigma, R, P, m)$ 为输入,然后输出 “真” 或 “假”。这就是 Schnorr 签名验证算法(为求精确,我们可以指明是 BIP340 验证算法)。注意,在上文的 “签名语境” 中是没有定义这一部分的,因为签名语境不知道作为该算法输入的公钥 $P$ 的构成。仅供参考,这个算法是这样的:$\sigma G ?= R + \mathbb{H}(R||P||m)P$ 。
  • $\mathbb{V} _ p$ 取 $(c, \sigma _ j, j, R _ j, R _ {agg}, P _ {agg})$ 为输入,其中 $P _ {agg}, R _ {agg}$ 分别是来自 KeySetupSign2Check 的输出。它在且仅在 $\sigma _ jG = R _ j + \mathbb{H}(R _ {agg}||P _ {agg}||m)P _ j$ 时返回 “真”(注意,$m$ 是包含在 $c$ 中的),否则返回 “假”。
  • $\mathbb{V} _ a$ 取 $(c, j, (T _ j, \sigma’ _ j), R _ j, R _ {agg}, P _ j, P _ {agg})$ 为输入,其中$(P _ {agg}, P _ j), R _ {agg}$ 分别是来自 KeySetupSign2Check 的输出。它在且仅在 $\sigma’ _ jG = R _ j - T _ j + \mathbb{H}(R _ {agg}||P _ {agg}||m)P _ j$ 时返回 “真”(注意,$m$ 是包含在 $c$ 中的),否则返回 “假”。

这两种看起来复杂的 Schnorr 验证算法 $\mathbb{V} _ p, V _ a$ 具有很长的输入元组,但可以通过要求算法 KeySetupSign1CheckSign2Check 必须提前运行且成功完成来简化(因为,显然这是下面的安全性论点所需要的)。然后定义就会变成:

  • $\mathbb{V} _ p$ 会取 $(\sigma _ j, j)$ 为输入,输出 接受/拒绝。
  • $\mathbb{V} _ a$ 会取 $((T _ j, \sigma’ _ j), j)$ 为输入,输出 接受/拒绝。

安全性

论点 2

选择上述定义的必然结果是:

*假设第一类算法 (KeySetup, Sign1Check 以及 Sign2Check) 已经运行且成功完成。进一步假设一个参与者 $p _ j$ 已经运行了算法 AdaptorCreateM,创建了一个签名适配器 $(T _ j, \sigma’ _ j)$ 且该适配器能够通过 $\mathbb{V} _ a$ 。那么,$\sigma’ _ j \leftrightarrow T _ j$ 之间必然有准确的一对一映射,也就是说,没有另一个 $T^{\ast} $ 使得 $(T^{\ast}, \sigma’ _ j)$ 能够通过 $\mathbb{V} _ a$ 。因此,这种绑定是完美的,而不仅仅是计算上的。*

这可以从下列描述中看出来:$R _ {agg}, P _ {agg}, R _ j, m$ 和 $P _ j$ 都是在 Sign2Check 结束时定义好的。因此,在等式 $\sigma’ _ j = k _ j - t _ j + \mathbb{H}(R _ {agg}||P _ {agg}||m)x _ j$ 中,除了 $\sigma’ _ j$ 和 $t _ j$ ,所有项都是固定的。(在域 $Z _ N$ 中)选了一个,就将决定另一个。

这个属性当然是极为关键的:如果我们的目标是创建一种能够强制揭晓一个秘密值的算法,我们就需要保证恶意的适配器创建者不能含糊其词、“揭晓” 另一个秘密值。

关于 “完美” 绑定,还有一个提醒:在固定语境 $(c, R _ {agg}, P _ {agg}, m, \sigma’ _ j)$ 下无法伪造另一个适配器的意义上,该论点为真。真正实用的安全性限制来自 MuSig 本身,也即,敌手在没有诚实参与者同意的情况下伪造多签名的能力(或无能为力)。

论点 3

就像 AdaptorCreate 一样,HVZK 属性在 AdaptorCreateM 上也成立。

这里我们定义了一种算法 AdaptorForgeM

  • 假设敌手为 $c$ 中的 $j$,而且 KeySetup, Sign1Check 以及 Sign2Check 都已经运行且成功完成。
  • 敌手随机选出 $\sigma’ _ j \in Z _ N$ 。
  • 然后计算 $\mathbb{H}(R _ {agg}||P _ {agg}||m)P _ j - \sigma’ _ j = Q$
  • 然后计算 $T _ j = Q + R _ j$
  • 返回 $(T _ j, \sigma’ _ j)$

可以检查到,$(T _ j, \sigma’ _ j)$ 能够通过 $\mathbb{V} _ a$ ,虽然这个元组的创建者不知道 $T _ j$ 的离散对数,也不知道 $P _ j$ 的离散对数。

因此,签名适配器的 “可伪造性” 在多参与者聚合签名、聚合 nonce 的语境下与单公钥语境下是一样的,对其诚实验证者零知识的论证也是一样的。只需观察到 AdaptorForgeMAdaptorCreateM 的统计分布是一样的。

“伪造” AdaptorForge(M) 的源头

这一节尝试满足读者的头脑,分析为什么适配器会有前面提到的属性。

基本的 Schnorr 签名的涉及依赖于这样一个事实:Fiat-Shamir 启发法的应用 在开始挑战之前固定了对话副本中的所有元素。这防止了敌手在不知道秘密值的情况下反求解(back-solving)$\sum$-协议中的响应元素。这对适配器也适用,因此:

在应用到论点 1 时,如果承诺的数值是 $R$ ,那么我们并没有承诺用在适配器中的实际 nonce 值 $k - t$ ,而只是该值的一个偏移量 $k$,差值是未定义的数值 $t$,因此,我们可以任意的 $\sigma’$ 反求解 $T$ 的数值。

在应用到论点 3 时,承诺的数值是 $R _ {agg}$,而 nonce 值 $R _ j$ 在 Sign1Check 这一步中就承诺了,所以这些值都是固定的了,但我们没有承诺实际上的 nonce 秘密值 $k _ j - t _ j$ ,因为 $T _ j$ 是来自 $R _ j$ 的偏移量,可以在这些事件后反解出来。通过 哈希成语境 来固定 $R$ 并没有移除可伪造性,因为伪造的可能性躲在 nonce 偏移量 $k - t$ 中。

存在适配器时碎片签名的不可伪造性

在这一节中,我们将详细讨论,在超过一个签名会话中使用适配器会不会影响 MuSig 中定义的碎片签名(实际上也将影响完整签名)的不可伪造性。

作为前奏,我们需要概述 MuSig18 [10] 签名协议的步骤:对一条消息 $m$ ,一组 $N$ 个参与者,编号为 $i = 1 … N$ ,插入位于合适点上的适配器:

  1. KeySetup:每一位参与者都宣布碎片公钥 $\prod _ i$ ,所有参与者对 $P _ {agg} = \sum \mathbb{H}(L, \prod _ i)\prod _ i$ 达成共识,其中 $L$ 是对公钥 $\prod _ 1…\prod _ N$ 的序列化。提醒,在本文中,$P _ i$ 指的是 $H(L, \prod _ i)\prod _ i$ 。
  2. Sign1Check:分享 nonce 承诺,每一位参与者都发送 $\mathbb{H}(R _ i)$ 给其他所有人。
  3. Sign2Check:分享 nonce 值 $R _ i$ ,然后验证其他人的 nonce 承诺。计算 $R _ {agg} = \sum R _ i$ 。
  4. (不是MuSig 的一部分,但,这就是要分享适配器的地方;见 AdaptorCreateM)。包括排序在内的细节,将在下文的特定情况下讨论。
  5. Round 3:分享碎片签名 $\sigma _ i = k _ i + \mathbb{H}(R _ {agg}||R _ {agg}||m)x _ i$ (见上一章对 $x _ i$ 的定义)。准确来说,$\sum \sigma _ i$ 就是聚合公钥 $P _ {agg}$ 对消息 $m$ 的一个有效 Schnorr 签名。

我们将在下列情况下提供作为参考的有序列表:

基本情形:在一次会话中其中一方使用一个适配器

考虑这样一种情形:编号为 $j$ 的参与者在一个签名会话中提供了一个适配器 $\sigma’ _ j$ 。在这种情形下,我们提出进一步的论点:

论点 4

*假设前面 3 步已经运行且成功完成。进一步假设一个参与者 $p _ j$ 运行了算法 AdaptotCreateM,产生了 $(\sigma’ _ j, T _ j)$ 。其对应的碎片签名 $\sigma _ j$ 在这些步骤之后是无法伪造被对手($i \not= j$)的任何子集伪造的,除非他们能解决椭圆曲线上的离散对数问题。*

证据:我们展示一种标准的化约法:控制了所有参与者 $p _ i$($i \not= j$)、可以计算出 $\sigma _ j$ 的一个敌手 $\mathbb{A}$ ,可以抽取出任意的离散对数。

我们将敌手 $\mathbb{A}$ 封装起来,并取一个点 $Q$ 作为挑战值,并准备用 $\mathbb{A}$ 抽取出 $Q$ 背后的离散对数。我们运行上面的 1 ~ 3 步,然后使用伪造程序计算一个适配器,就跟论点 1 中的 AdaptorForge 一样,只不过有一处重要的修改;我们不假设我们已经知道了 nonce 秘密值 $k$:

  1. 挑战者给我们一个点 $Q$ 。我们令 $R _ j := Q$ (注意,我们还不知道它的离散对数)
  2. 我们,作为参与者 $p _ j$ ,以及作为所有其他参与者的 $\mathbb{A}$ ,遵循上述步骤 1 ~ 3,如常产生一个 $P _ {agg}$ 和 $R _ {agg}$ 。
  3. 我们 伪造 一个适配器(见论点 1):首先,随机选出 $\sigma’ _ j$ ,然后计算 $T _ j = \mathbb{H}(R _ {agg}||P _ {agg}||m)P _ j - \sigma’ _ jG$ 。将元组 $(\sigma’ _ j, T _ j)$ 发送给 $\mathbb{A}$,后者可以用 $\mathbb{V} _ a$ 来验证。
  4. $A$ 以不可忽视的概率返回编号 $j$ 的一个有效的碎片签名 $\sigma _ j$ 。
  5. 我们可以计算 $k _ j = \sigma _ j - \mathbb{H}(P _ {agg}||R _ {agg}||m)x _ j$ ,作为 $Q$ 的离散对数,返回给挑战者。

注意这个程序的不寻常一面:虽然我们的角色是 “诚实的” 参与者 $p _ j$ ,按要求遵循了协议的所有步骤,我们一开始也 不知道 $R _ j$ 的离散对数,所以也无法真的制作出属于 $j$ 的碎片签名。但是,敌手 $\mathbb{A}$ 可以 为我们制作出来的事实,产生了所需要的 ECDLP(椭圆曲线离散对数难题)化约效果。

同样要指出的是,这个论证的结构比起为 MuSig 展示一种化约到 ECDLP 或 OMDL 的方法,要简单得多;原因在于,我们并不尝试证明签名方案本身的健全性;(对 MuSig 来说)这样的证明已经存在。这里我们只尝试证明,对 诚实参与者($p _ j$)来说,假设其已经知道私钥 $x _ j$ ,则添加适配器不会引起外部伪造的风险了;而且,让 论证 变得非常简单的,正是上文中详细讨论过的可伪造性。

第二种情形:多个适配器,一个签名会话

也许这是一种不实用的场景,但的确有可能发生:参与者 $p _ j$ 在同一个签名会话的第 4 步中超过 1 个对应于适配器点 $T _ q, q \in 1…m$ 的适配器。注意一个代数上的细微差别:在这样一种场景中,不仅碎片签名 $\sigma _ j$ 的曝光会同时揭晓对应所有对应的秘密值 $t _ q$ ,即使一个秘密值(比如 $t _ 1$)揭晓,也会导致其它所有秘密值 $t _ q$ 以及碎片签名 $\sigma _ j$ 揭晓。这本质上 “只有一个秘密值”。我们依然介绍这种情形,因为可以想象其重要性。

在这种情形中,来自前面章节的论证或多或少是一样的。我们生成 $m$ 个随机数值 $\sigma’ _ {j, q}$ ,然后为每一个使用相同的伪造程序,同时,像上一节一样,将 $R _ j$ 设为由挑战者给出的 $Q$(请记得,这里也只有一个 $R _ j$)。如果 $A$ 能成功制作碎片签名($\sigma _ j$),那就能揭晓挑战值 $Q$ 背后的离散对数。

注意:因为在根据论点 1 给出的伪造程序计算数值 $T _ q$ 时使用了哈希函数 $H$,这种论证进队适配器点 $T$ 具有随机分布时才成立。

第三种情形:一个适配器点,多个签名会话

这是 “同时给出多个适配器” 的一个显然更有趣的应用:假设 Alice 希望为 $m$ 个 不同 的签名语境提供同一个点 $T _ A$ 上的适配器,这些语境是她跟 $N$ 个不同的对手 Bob、Carol 等人建立的。实际上,适配器最基础的应用就是基于适配器的 CoinSwap [14] ,正是这种情形的两方特例。

这第三种情形不能用第一种情形那样的碎片签名伪造程序证明是安全的。原因在于,我们的算法 AdaptorForgeM 在应用时只能生成一个不可预测的数值 $T$ ;如果我们要在多个签名会话中使用 相同的 $T$ ,就不能直接使用它。

为了让化约能够进行,我们需要给论证增加两个 约束/假设。首先,我们依赖于 “随机数断言机模型(ROM)”,以允许我们在特定时间点修补哈希函数的输出,再交给敌手。其次,对时间序列有个限制:不同签名会话中的 Sign1CheckSign2Check 不能并行执行。

最后要指出的是:这样一来,化约中的 “密合性(tightness)” 必然减少,原理上是因为有多种伪造可能性,即,原理上是 $m$ 的一个线性因子。

因此,我们定义 $A _ 2$ 为:(1)它扮演 $m$ 个签名会话中编号为 $2…N$ 的所有对手;(2)它被给予 KeySetup, Sign1Check 以及 Sign2Check 的有效输出。注意,如前所述,这些步骤都完成了,但 $m$ 个签名会话中的每一个都是按顺序完成的,不是 并行完成的。(3)然后,它得到 $\sigma’ _ {1, 1},\sigma’ _ {1, 2},…\sigma’ _ {1, m}$ 其中 $\sigma’ _ {x, y}$ 是编号为 $x$ 的参与者在第 $y$ 个会话中的签名适配器。(4)$\mathbb{A} _ 2$ 的任务是以不可忽视的概率,在 至少一个签名会话中输出伪造的有效碎片签名 $\sigma _ {1, q}$ 。

现在,我们基于比 “论点 4” 更复杂的游戏,将签名伪造化约成 ECDLP。

  1. 挑战者给我们一个点 $Q$ 。我们令 $R _ {1, 1} := Q$ 。
  2. 在 $m$ 个签名会话(编号为 $q$ )中,MuSig 的所有参与者都可以运行 KeySetup ,从而对 $P _ {agg, q}$ 达成一致。
  3. 然后,我们作为 $p _ 1$ ,跟 $\mathbb{A} _ 2$(作为其他参与者)一起,仅在第一个签名语境中,运行 Sign1CheckSign2Check ,从而产生 $R _ {agg, 1}$ 。
  4. 现在,我们如 “论点 4” 一样,为 签名语境 1 伪造一个签名适配器:首先,随机选出 $\sigma’ _ {1, 1}$ 。然后计算 $T _ 1 = R _ {1, 1} + \mathbb{H}(R _ {agg, 1}||P _ {agg, 1}||m _ 1)P _ {1,1} - \sigma’ _ {1, 1}G$ 。这时候,(在签名会话间)共享的 $T _ 1$ 就决定好了。
  5. 下一步,对于所有剩余的签名会话 $q \in 2…m$ ,我们做这些:(1)随机选出 $\sigma’ _ {1, q}$ 。(2)为 $\mathbb{H}(R _ {agg, q}||P _ {agg, q}||m _ 1)$ 选出一个随机的数值 $H$ (注意,这时候我们还不知道 $R _ {agg, q}$ )。(3)计算 $R _ {1, q} = T _ 1 + \sigma’ _ {1, q}G + H P _ {1, q}$ 。
  6. 现在,我们为 $q \not= 1$ 的语境提供准备好的 $R _ {1, q}$ 并运行 Sign1CheckSign2Check 。注意,这些步骤 不需要 查询哈希函数 $\mathbb{H}$,只需要提供用来作为承诺的 $\mathbb{H} _ c$ 。在这个点上,我们拥有了 $R _ {agg, q}$ ,所以我们可以放置后门,令 $\mathbb{H}(R _ {agg, q}||P _ {agg, q}||m _ q) :=H$ 。
  7. 为编号为 $2…m$ 的所有语境完成上面的两步之后,我们有了一组签名适配器 $(\sigma’ _ {1, 2}, T _ 1), … , (\sigma’ _ {1, m}, T _ 1)$ ,都交给 $\mathbb{A} _ 2$ 。
  8. 对 $\mathbb{A} _ 2$ 来说,所有这些适配器都可以通过 $\mathbb{V} _ a$ 验证,因为,很容易检查出来,因为我们的随机数断言机有后门。
  9. $\mathbb{A} _ 2$ 以不可忽略的概率(定义为 $p$),为至少一个签名会话 $q \in 1…m$ 返回一个有效的碎片签名 $\sigma _ {1, q}$ 。
  10. 以概率 $\frac{p}{m}$ ,$\mathbb{A} _ 2$ 为第一个签名会话返回有效的碎片签名。这时候,我们就可以计算 $k _ {1, 1} = \sigma _ {1, 1} - \mathbb{H}(P _ {agg,1}||R _ {agg,1}||m)x _ {1,1}$ ,从而我们可以返回 $Q$ 的离散对数。

按顺序提供一些解释:

  • 上面的第 10 步有一个未言明的假设:我假定敌手 $\mathbb{A} _ 2$ 为每个签名语境成功伪造碎片签名的概率是相同的。这个假设背后的直觉是,呈现给 $\mathbb{A} _ 2$ 的 信息(相比于常规的 MuSig 签名会话),是一次性给出的:一组签名适配器。不过,这并不严格,所以也许这个论证还可以收紧一点。
  • 不管怎么说,化约密合性的损失并不 恰好 是因子 $m$ :随机数断言机的后面引入了另一个因子(由于碰撞的可能性),虽然我们认为这是微不足道的,而且不重要。
  • 这里并没有论证并行运行所有会话的 Sign1CheckSign2Check 就是 不安全的 ;关于这一点,我们没有意见。但我们这里的化约法要求在所有其它会话之前运行一个会话。

第四种情形:多方在多个签名会话中使用自己的适配器

在一个(一组)签名会话中,每一方都需要一种安全性:他们 自己 的碎片签名无法被其他参与者的任何子集伪造。我们认为,上面的论证已经能解决这个问题。如果(敌意的)对手制作了自己的签名适配器,这只会给诚实参与者提供额外的信息,因此不构成额外的安全风险。这个命题假设了我们会让 “论调 4” 所展示的事件 1 ~ 5 保持相同顺序。

参考文献

  1. “Adaptor signatures”, Poelstra, 2017 https://download.wpsoftware.net/bitcoin/wizardry/mw-slides/2017-03-mit-bitcoin-expo/slides.pdf
  2. MuSig (3-round), Maxwell, Poelstra, Seurin, Wuille
    https://eprint.iacr.org/2018/068
  3. MuSig2, Nick, Ruffing, Seurin 2021
    https://eprint.iacr.org/2020/1261
  4. Bitcoin Improvement Proposal 340 (Schnorr signatures)
    https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki
  5. Bitcoin Improvement Proposal 327 (MuSig2 protocol)
    https://github.com/bitcoin/bips/blob/master/bip-0327.mediawiki
  6. Multiparty S6 (blog; how to do a multiparty adaptor-based swap).
    https://reyify.com/blog/multiparty-s6
  7. Boneh and Shoup’s Graduate Course in Cryptography (contains a lot of useful fundamentals on security proofs)
    https://toc.cryptobook.us/
  8. Discreet Log Contracts, Dryja
    https://adiabat.github.io/dlc.pdf
  9. Generalized Channels from Limited Blockchain Scripts and Adaptor Signatures, Aumayr et al
    https://eprint.iacr.org/2020/476
  10. Two-Party Adaptor Signatures From Identity Schemes, Erwig, Faust, Hostakova, Maitra, Riahi
    https://eprint.iacr.org/2021/150
  11. Short signatures from the Weil pairing, Boneh, Lynn, Shacham 2001
    https://www.iacr.org/archive/asiacrypt2001/22480516.pdf
  12. Anonymous Atomic Locks for scalability in Payment Channel Hubs, Tairi, Moreno-Sanchez, Maffei 2019
    https://eprint.iacr.org/2019/589
  13. One-Time Verifiably Encrypted Signatures, Fournier 2019
    https://eprint.iacr.org/2019/589
  14. Scriptless script based atomic swaps, Blockstream Research
    https://github.com/BlockstreamResearch/scriptless-scripts/blob/master/md/atomic-swap.md
  15. Adaptor signatures, summary by Bitcoin OpTech
    https://bitcoinops.org/en/topics/adaptor-signatures/
  16. Anonymous Multi-Hop Locks
    https://eprint.iacr.org/2018/472