门限 ECDSA——更安全、更私密的多重签名

 Keep 开发者 Piotr Dyraga 在 2018 年旧金山区块链周上关于门限 ECDSA 的演讲

2018年10月9日,在旧金山区块链周的 Epicenter 会议上,Keep 的 Piotr Dyraga 就门限椭圆曲线数字签名算法(t- ECDSA)进行了演讲。   

去年夏天,Piotr 和他的代码合作伙伴 Jakub Nowakowski 为Keep实现了一个原型门限 ECDSA 协议(并在比特币测试网上创建了一笔门限 ECDSA 签名的交易!),Piotr 上台展示了该技术解锁的一些可能性,以及有关其如何在底层运作的一些技术细节。

门限 ECDSA——更安全、更私密的多重签名

首先,我们将讨论多重签名(multi-signatures)——它们是什么,它们在比特币中的运作方式,以及它们在以太坊中的运作方式。然后,我们将讨论门限签名(threshold signatures)及其与多重签名相比的优缺点。最后——事情会变得有些疯狂——我们将探讨一些密码学的东西,并讨论门限 ECDSA 协议——类似于 Keep 中的实现方式。  

门限 ECDSA——更安全、更私密的多重签名

在继续进行之前,请允许我告诉你一些有关 Keep 的信息,因为这将有助于更好地理解为什么我们开始有关门限签名的工作。如果仅用一句话来描述 Keep,我会说Keep是公链的隐私层。 

在过去的几年中,公链为我们带来了令人难以置信的透明性和可审计性(auditability),以及抗审查和不可篡改的记录。但是,竞争利益可以轻松访问发布到区块链的任何智能合约。结果,当公司考虑在区块链上构建应用时,隐私是出现的主要问题之一。Keep 是公链和隐私之间的桥梁,允许合约利用区块链技术的全部功能而不会损害安全性。我们也可以说,Keep 是一种私人计算机,能够存储和处理甚至隐藏在自身之外的数据。  

门限 ECDSA——更安全、更私密的多重签名

让我们从多重签名开始。“多重签名”通常是指需要多把密钥来签署交易,并且通常被用于划分责任。

门限 ECDSA——更安全、更私密的多重签名

1-2 多重签名的一个很好的例子,是夫妻的小额现金联名账户,其中任何一方的签名都足以执行交易。

门限 ECDSA——更安全、更私密的多重签名

2-2 多重签名的一个例子,是夫妻双方的储蓄帐户,需要双方同意才能执行交易。

门限 ECDSA——更安全、更私密的多重签名

2-3 多重签名的一个例子,是父母对孩子的储蓄帐户。孩子可以在至少一位父母的同意下花钱,如果父母双方都同意,钱可以完全从孩子那里拿走。

门限 ECDSA——更安全、更私密的多重签名

在比特币中,多重签名通过创建一个多重签名地址来运作,并且在创建多重签名地址时,我们指定与该地址关联的密钥以及签署交易需要多少把密钥。然后,经过一段时间,我们创建了一个交易,有人用密钥对其进行签名,就是这样!在此案例中,我们创建了具有三把关联密钥的多重签名地址,并且至少需要两把密钥才能提供签名。

这确实很酷,但也有一些限制。

门限 ECDSA——更安全、更私密的多重签名

首先,使用哪把密钥来履行交易的信息是公开的。对于某些企业来说,这可能是一种优点,但是对于其他一些需要更大匿名性的企业来说,则可能是一种缺点。另外,在可以使用多少把密钥上也有一些限制。一旦创建了多重签名地址,安全策略就固定下来了。因此,你不能在一段时间之后改变主意,说:“好吧,现在我要使用 2-3 的策略,而不是 5-6 的策略”,它需要创建一个有着新安全政策的新多重签名地址,并把所有资金转移过去。

它在以太坊中的运作方式有些不同,因为这里没有像多重签名这样的东西。总有一个地址来签署一笔交易并花费 gas。但是,有一些多重签名钱包,它们基本上是智能合约,能够存储代币并且要求发起的交易需要接受某些要求,包括特定的签名配置。

门限 ECDSA——更安全、更私密的多重签名

最著名的几个钱包是 BitGo 钱包、Gnosis 钱包和 Parity 钱包。而且,尽管它们是智能合约(所以它们显然要比比特币交易具有更大的灵活性),它们也更难以实现。而且,一旦发生错误,错误的成本也确实很高。我想这里的每个人都听说过 Parity 被黑的故事。    

那么,有没有更好的方法?我认为答案是“是”。那就是门限签名。

门限 ECDSA——更安全、更私密的多重签名

多重签名机制依赖于拥有单独而唯一的密钥的各方,他们用这些密钥来对一笔交易签名,并且,签名者一个接一个地提供其签名。在(上方)这张图片中,我们在左侧有一组签名者。每个签名者都有自己的密钥,他们用它来签署一笔交易。当验证者 Bob(在右侧)想要验证交易时,他需要分别检查每个签名。

门限 ECDSA——更安全、更私密的多重签名

对于门限签名,情况有所不同,因为我们只有一把公钥,一把密钥和一个签名。在上图中,左侧有一组签名者。每个签名者都有相同的公钥和私钥的一个唯一部分。签名者使用一种特殊的通信协议进行协作,该协议不会为了生成签名而暴露密钥,并且只会生成一个签名。现在,验证者只需检查一个签名即可确定交易是否正确。

门限 ECDSA——更安全、更私密的多重签名

那么,什么门限签名可以给我们带来什么呢?首先,我们避免了基于合约的多重签名。使用门限签名,我们可以让多方签署以太坊交易,而无需将我们的代币锁定在智能合约钱包中。我认为这对以太坊来说是一个巨大的胜利。其次,门限签名在链上是无法区分的。

门限 ECDSA——更安全、更私密的多重签名

这是我们在比特币测试网络上执行的具有 20 个签名者的门限交易示例。你会注意到,这笔交易与只有一个签名者的标准比特币交易之间没有区别。这提供了更大的匿名性,因为有关哪些部分被用于签署交易(即谁签署了交易)的信息不会被公开泄漏。

同样,就验证而言,门限签名比多重签名交易便宜。多重签名需要为每个签名者创建一个新的签名,并且成本随着签名者数量的增加而增加。对于门限签名,只有一个签名,因此在验证方面成本是固定的。

门限签名还提供了更好的灵活性。首先,签名者的数量不限。其次,可以在一段时间后修改安全策略。它是一种单点故障算法,但是你仍然可以改变主意,说:“好吧,我要 3-6 而不是 7-10。” 

门限 ECDSA——更安全、更私密的多重签名

但是总会有陷阱存在。第一个陷阱是,尽管门限签名并不是什么新鲜事物,但大多数人仍不熟悉它们。这意味着要花一些时间来接受这项技术。而且,工具还不存在。对于多重签名,我们有一堆工具,比如有良好 UI 支持的硬件钱包。在门限签名这里没有这些东西,至少现在还没有。另一个问题是签名者需要保持在线。对于多重签名,你可以提供你的签名,然后下线去度假,同时,其他人过来提供另一个签名,交易就会被接受。对于门限签名,签名者需要合作(至少达到最低数量)才能产生签名。 

门限 ECDSA——更安全、更私密的多重签名

我希望这一切对你来说都令人兴奋!现在是时候讨论它实际上如何运作了。但首先,我们需要回顾一些模型和定义。它们是“加法同态加密(additively homomorphic encryption)”,“门限加密(threshold encryption)”和“承诺方案(commitment scheme)”。

门限 ECDSA——更安全、更私密的多重签名

首先,是加法同态加密。同态加法加密有一个很好的功能,可以对密文进行运算。加法同态加密方案的一个示例是 Pailier,对于该方案,存在一个可有效计算的运算“加”,因此加法运算(在幻灯片上带有 e 分指数)可将两个密文加在一起。

因此,如果我们有两个值 a 和 b。我们可以首先加密这两个值,然后用这一特殊运算将这两个密文加在一起。或者,我们可以首先有这两个值,然后将它们加在一起,然后对结果进行加密。当我们解密时,在两种情况下我们将获得完全相同的值。   

门限 ECDSA——更安全、更私密的多重签名

接下来是(t,n)门限加密。解释它的最简单方法,是说我们有 n 个参与者;每个人都有相同的公钥,但每个人也都有私钥的独特部分。因此,在这张幻灯片上,我们有 secret_share 1,secret_share 2,secret_share 3 … secret_share n 和签名者——如果你有一条用公钥加密的消息,则签名者必须使用一种特殊通信协议进行合作,这种协议不会为了解密而暴露密钥。

门限 ECDSA——更安全、更私密的多重签名

例如,假设 Alice 和 Caroline 正在玩掷硬币游戏。Alice 选择硬币的一面,评估对其选择的承诺,并将承诺发送给 Caroline 。现在, Caroline 将硬币扔向空中,说出结果会是什么。接下来,Alice 发送一个特殊的值,称为解除承诺密钥(decommitment key),它使得 Caroline 可以评估承诺并查看 Alice 最初选的值是否真的如她现在所说。 

解除承诺密钥可以验证承诺,但它还有一个很棒的功能,即允许定义无条件的隐藏方案。因此,无论 Caroline 做什么,无论她具有多么高的算力,如果没有解除承诺密钥,她都无法猜测 Alice 承诺的值。她不能仅凭承诺就做到这一点。

门限 ECDSA——更安全、更私密的多重签名

现在该讨论协议了。我们的实现基于纽约城市学院和普林斯顿大学的 Rosario Gennaro、Steven Goldfeder 和 Arvind Narayanan 的工作,他们描述了门限最佳 DSA/ECDSA 签名及其在比特币钱包安全中的应用(https://link.springer.com/chapter/10.1007/978-3-319-39555-5_9)。我们对该协议做了一些小的修改,但是现在没有时间讨论它。并且,协议由两个部分组成:密钥生成协议和签名协议。我们将首先讨论密钥生成。     

我们现在就要讨论密码学了。假设我们有 n 位签名者,每位签名者都用加法同态门限加密方案进行了初始化,并且这种情况发生在设置阶段:  

门限 ECDSA——更安全、更私密的多重签名

现在,我们将跳过它是怎样完成的,并在最后回过头来进行简要的讨论。

这可能会造成混淆,因为我们有两种类型的密钥。一种是门限加法同态加密方案密钥(threshold additively homomorphic encryption scheme key),这些密钥在设置阶段已初始化,另一种是我们用于签名的 门限-ECDSA 密钥(t-ECDSA key)。这第二种密钥就是我们现在要生成的。对于加法同态门限加密方案,我们仅假设它是在设置阶段完成的。   

在第一步里,每位参与者选择一个随机整数 x,它将被用于该参与者的私钥部分: 

门限 ECDSA——更安全、更私密的多重签名

x 不能大于 q 。q 是椭圆曲线的基数,因此它是椭圆曲线有的点数。在所有的幻灯片里,q 都代表椭圆曲线的基数。每个参与者将 y 计算为 g 的 x 次幂。这是一种椭圆曲线运算,基本上,我们将曲线的生成点乘以 x 。这是你经常在组里用到的一种表示法,但是由于椭圆曲线是一个组,因此我们也可以在这里使用它。            

然后,每个参与者计算对此值的承诺,并在第 2 轮中,将该承诺发布给组里的所有参与者:

门限 ECDSA——更安全、更私密的多重签名

接下来,在第三步中,每个参与者都揭示加密形式的 x,在幻灯片上为 α :    

门限 ECDSA——更安全、更私密的多重签名

加密是通过我们在设置阶段初始化的加法同态加密方案完成的。此外,每个参与者都揭示公钥部分、解除授权密钥,以及表明所有这些值合在一起正确的零知识证明。这不仅可以验证承诺,还可以让所有参与者查看他们刚刚一起展示的所有部分是否正确。

这样,零知识证明说的是,存在一个数字 x ,于是曲线的生成点的 x 次方等于 y ,并且 y 是公开的,因为它刚刚被揭示,并且如果我们解密刚刚发布的值 α ——这是加密的密钥——我们将获得该数字 x 。          

当然,这是一个零知识证明,所以我们不可能猜出 x 是多少,但我们在这里说的是,它位于(-q³, q³)的区间内,由于 q 是椭圆曲线的基数,这个范围确实很大。     

在第四步中,所有签名者都使用加法同态门限方案的加法运算来生成最终的 t-ECDSA 密钥,因此可以将 x 的所有加密部分相加:   

门限 ECDSA——更安全、更私密的多重签名

作为结果,我们得到了加密形式的密钥,y 的所有显露出来的公共部分可以被相加,并且,作为结果,我们得到了公钥。这里的加法运算只是椭圆曲线点的加法,因此很简单。  

门限 ECDSA——更安全、更私密的多重签名

第二部分是签名——让我们看一下签名算法。

门限 ECDSA——更安全、更私密的多重签名

我们有了 α,它是所有签名者之间共享的加密形式的 t-ECDSA 私钥,而且我们有了 y ,它是 t-ECDSA 公钥;它只是椭圆曲线上的一个点。   

在第一轮中,各方都挑一个随机整数 ρ :

门限 ECDSA——更安全、更私密的多重签名

使用加法同态门限加密方案对该值进行加密: 

门限 ECDSA——更安全、更私密的多重签名

并将 ECDSA 密钥(幻灯片上的α)乘以该随机值: 

门限 ECDSA——更安全、更私密的多重签名

我们能这样做,因为有了加法同态加密方案的加法运算,我们也可以进行乘法。每个签名者都发布对这些值的承诺,并在第二轮中揭示所有这些值以及零知识证明,指出它们是正确的:

门限 ECDSA——更安全、更私密的多重签名

在本演示中,我们跳过了零知识证明的构造。

因此,在第二回合之后,参与者使用同态加密方案定义的加法运算,将揭示出的各个部分合并在一起。

门限 ECDSA——更安全、更私密的多重签名

第 3 轮和第 4 轮使用相同的承诺-揭示模式:

门限 ECDSA——更安全、更私密的多重签名

在右侧,我们具有到目前为止评估的所有参数,并且所有参与者都具有相同的值。  

在第三轮中,每一方挑选一个随机整数 kᵢ: 

门限 ECDSA——更安全、更私密的多重签名

和随机整数 cᵢ: 

门限 ECDSA——更安全、更私密的多重签名

q 始终代表椭圆曲线的基数,也就是椭圆曲线上的点数。 

各方把 rᵢ 计算为 g 的 k 次方——我们基本上用它来乘以曲线生成点:    

门限 ECDSA——更安全、更私密的多重签名

各方计算参数 w ,它是 k 乘以 ρ 加上 c 乘以 q            

门限 ECDSA——更安全、更私密的多重签名

q 一直是椭圆曲线的基数,由于我们使用加法同态门限加密,因此我们可以对其进行计算。 

最后,各方承诺所有这些参数,并在第 4 轮中揭示生成的参数,以及说明它们在一起正确的零知识证明:

门限 ECDSA——更安全、更私密的多重签名

现在,我们跳过零知识证明。

有了所有小组成员的所有参数之后,我们可以将它们加在一起,就像在第 2 轮之后一样。我们把所有 k 部分,所有 c 部分,所有 w 部分相加。更重要的是,我们把参数 r 评估为所有 rᵢ 部分的总和,我们使用了一种特殊的哈希函数:     

门限 ECDSA——更安全、更私密的多重签名

实际上,这是我们从标准 ECDSA 协议中知道的函数:它是x 点坐标模除(modulo,译注:一个数除以另一个数的余数)椭圆曲线的阶数;这是来自标准 ECDSA 协议的内容。  

在第 4 轮之后,右侧的所有参数将由组里的所有签名者共享。现在我们需要玩一些离散数学的把戏来产生一个签名。使用到目前为止我们评估过的所有这些参数,由于我们运算的是加密的数据,因此签名也会是加密的。但这是我们将在最后的第 6 轮中处理的事情。 

门限 ECDSA——更安全、更私密的多重签名

我们要做的第一件事是执行门限解密机制,以便使所有参与者都解密参数 w 并把该值赋给 η:   

门限 ECDSA——更安全、更私密的多重签名

接下来,我们计算一个叫 Ψ 的参数,它是 η 的模 q 乘法逆元,并且 q 一直是椭圆曲线的基数:

门限 ECDSA——更安全、更私密的多重签名

然后,有了 m,即我们正在签名的消息的哈希值(或这笔交易的哈希值),我们开始使用以下公式评估签名: 

门限 ECDSA——更安全、更私密的多重签名

c 是我们刚刚评估过的值,而 u ,r 和 v 是所有签名者在前几轮中共同评估的参数。   

因此,由于 u 是一个加密的 ρ ,并且 v 是一个加密的 ρ 乘以 ECDSA 密钥,因此我们可以执行以下转换:   

门限 ECDSA——更安全、更私密的多重签名

如果我们把 Ψ 替换为它所代表的值,我们会得到下面的公式:  

门限 ECDSA——更安全、更私密的多重签名

最后,如果消掉 ρ ,我们得到: 

门限 ECDSA——更安全、更私密的多重签名

我想你们大多数人都知道该方程的含义——这是标准 ECDSA 签名的方程,其中 k 是加密安全的随机整数,m (译注:原文此处写成了 n,应该是笔误)是消息哈希,x 是我们的 ECDSA 密钥,而 r 是曲线生成点的 k 次方(译注:原文此处多写了一个模 q,应该是笔误)。因此,这是一个标准 ECDSA 协议的方程。

所有这些方程都是在密文上完成的,因此最后我们的签名也被加密了:

门限 ECDSA——更安全、更私密的多重签名

我们需要处理它,这是在第 6 轮中完成的,在这一轮里所有参与者都执行门限解密机制以了解 s 的值。解密值 s 和在第4轮中评估的参数 r 共同构成签名:     

门限 ECDSA——更安全、更私密的多重签名

我知道第一次见到它显然不容易理解。我的意图不是要让你对协议有一个全面的了解,而是要通过所有步骤了解你如何在后台进行工作。

门限 ECDSA——更安全、更私密的多重签名

因此,有两个注意事项。

实际上,这是关于被问到的问题的——签名协议的单点故障是不可接受的。在密钥生成这里是容易的,因为我们可以检测到一方是否有行为不当。我们有零知识证明和承诺。如果一方在密钥生成协议期间行为不当,我们可以删除结果,然后将行为不当的一方替换为其他人,然后重启协议。在签名这里就不那么容易了,因为即使一方行为不当,我们也应该能够产生签名。只要我们有 t 加 1,其中 t 是诚实的门限参与者——这是我们在生成加法同态门限加密方案时设置的参数——我们仍然可以生成一个签名。因此,我们需要一些最低限度的诚实参与者,然后就一切都好了。    

另一个重要的注意事项是这些密钥是如何生成的。我们这里通常有两种可能的方法——有一个受信任的经办人设置,其中一方会生成那些密钥并将其交付给组中的所有其他参与者,而受信任的经办人应该忘记所有这些密钥,擦除内存。第二种可能性是我们执行某种无经办人协议,以便由所有组员一起执行密钥。还有明天史蒂夫可能还会提出第三种方法(http://stevengoldfeder.com/papers/GG18.pdf)。这两篇论文(编者注:https://link.springer.com/chapter/10.1007/978-3-642-17955-6_4和https://link.springer.com/article/10.1007/s10207-010-0119-9)显示了该设置的可能算法。     

那么,它真的有效吗?是的,我们已经签名了许多以太坊和比特币交易。但重要的是要了解该解决方案确实是通用的,因此我们可以在此处使用任何椭圆曲线。

门限 ECDSA——更安全、更私密的多重签名

因此,不管你是一个钱包公司或提供机构托管解决方案,还是你只是想保护自己的个人钱包,你都可以受益于 t-ECDSA,尤其是在不支持多重签名的链上。因此,例如,作为一个加密货币交易所,你可以把以太坊密钥存储在多个服务器上,甚至可以将某些部分存储在线下,因此这应该降低了遭受攻击的可能性。  

关键词: 门限  多重签名  ECDSA  

该内容来自于互联网公开内容,非区块链原创内容,如若转载,请注明出处:https://qkljsw.com/archives/28304

联系我们

aliyinhang@gmail.com