Tech 17 September 2018

Guest Contributor

比特币现金的Rabin签名

在本文中,我们将向您展示如何在比特币现金脚本中直接签署和验证任意消息,而无需引入新的操作码(例如提议的OP_CHECKDATASIG(也称作OP_DATASIGVERIFY))。通过利用Rabin签名的简单代数结构,我们可以对交易中的任何数据进行签署 – 即使数据来自比特币现金区块链之外。

Rabin 签名

Rabin数字签名(RDS)算法是迈克尔•拉宾(Michael Rabin)在1979年开发的数字签名方案中的一个相对不太为人们所了解的早期例子[1]。它的安全性依赖于一项关键观察,即计算模块化平方根与整数因子分解是同样困难的。基于这个原因,它有很多跟RSA相同的功能,但他们之间也有一些值得探索的有趣差异。

Rabin密码系统设置类似于RSA,通过识别具有相似量级的两个质数 和 来启动密钥生成。但是,与RSA不同,它还有另外一个要求,即  及 。该组合(p,q)一起形成具有相应公钥 的私钥。

为了对消息进行签名,需要识别一个 ,使得哈希值 是一个二次剩余模数 。换句话说,存在一个 使得:

.                                                       (1)

的组合就是 Rabin 签名。

通过找到右侧的平方根来伪造签名跟 的整数因子分解一样困难。另外,如果 和 已知,则根据孙子剩余定理:

and         .                          (2)

由于我们已经选定 且 ,可以使用Tonelli-Shanks算法的简化版本来计算:

.   (3)

要验证签名是否有效,需要检查(1)是否成立。其成立的条件为,当且仅当有一个整数 在 的范围内且:

.                                                       (4)

因子 可以安全地包含在签名中,因此可以公开的信息是 的组合。在这种情况下,要验证签名,需要检查(4)是否成立。这比验证(1)更容易实现。

Rabin签名方案有如下三种有趣的特点:

a)签名的生成从计算方面上讲是比较昂贵的,而签名的验证在计算上是比较便宜的。

b)签名的安全性仅依赖于整数因子分解的难度。因此,Rabin签名在存在性上是不可伪造的(与RSA不同)。

c)哈希函数 必须与公钥 具有相似的量级。

为确保128位安全级别,Rabin(或RSA)公钥 必须为3072位,明显大于椭圆曲线加密中类似密钥所需的256位。因此,哈希函数 的摘要和签名的 部分也必须是3072位的。

比特币现金的实现

验证方程(4)的简单代数结构有助于在比特币现金脚本中实现,该脚本仅允许某些基本的算术运算。计算上比较昂贵的签名本身的生成是在块外进行计算的。

其一项重要的应用是验证任意消息 的签名。此消息可能包含来自比特币现金区块链之外的数据。将其与现有操作码OP_CHECKSIG进行比较可以发现,现有操作码仅可验证已获得ECDSA签名的特定类型的消息(即交易哈希)。

可以考虑以下形式的赎回脚本:

OP_DUP OP_HASH160 < > OP_EQUALVERIFY OP_MUL OP_SWAP OP_2 OP_ROLL OP_CAT FUNC_HASH3072 OP_ADD OP_SWAP OP_DUP OP_MUL OP_EQUAL

其中, 是签署人的公钥。当且仅当它有下列输入时,才会被评估为成立:

< > < > < > < > < >

其中 是任意消息,而 是该消息的有效Rabin签名。或者,如果需要预定消息的签名,则可以在赎回脚本中包括< >。

直接实现上述赎回脚本存在两个障碍,但是这些都可以克服,而无需引入新的操作码。

i)比特币现金脚本没有具有3072位摘要的哈希函数,我们用FUNC_HASH3072将其表示为 一个占位符 。

ii)算术运算OP_MUL和OP_ADD限制在32位输入。这与Rabin签名方案中的3072位整数冲突。

为了解决(i)的问题,我们可以将一个256位的哈希摘要映射为3072位。例如,我们可以首先应用OP_HASH256,将结果拆分为12块,然后用OP_HASH256再次对每个块执行哈希计算,最后合并结果。

(ii)的一项解决方案是将每个整数分成32位的块,然后应用Karatsuba算法。另外可以通过在运行中直接验证等式两侧的每个块来提高效率。一旦数据被压缩成合适的形式,这个过程将带来主算法的96个循环,必须在比特币现金脚本中进行解压缩。请注意,该解决方案需要删除201个操作码的限制。

(ii)的另一种解决方案是提高比特币现金算术位长度以考虑更大的整数。在这种情况下,必须格外小心,以设计一个安全的解决方案。

结论

通过利用Rabin签名的属性,我们已经了解了如何进行任意消息的签署,以及如何在比特币现金脚本中直接验证签名而不引入新的操作码。所有计算上昂贵的操作(密钥生成、签名构造)都是在块外执行的。在脚本中执行的只有用来验证(4)成立的简单步骤。

该解决方案在存在性上难以伪造的特点,可以为比特币现金平台带来额外的功能,而无需牺牲网络的安全性,或改变核心协议本身。

我们将继续使用Rabin签名开发此解决方案,并将寻求与其他人合作开展此项工作。 nChain不打算为其在解决方案上的努力寻求专利保护;相反,nChain将发布在该领域的研究成果,供公众查阅和使用。

欧文•沃恩(Owen Vaughan)

参考文献

[1] Michael O. Rabin, “Digitalized signatures and public-key functions as intractable as factorization”, Technical Report 212, MIT Laboratory of Computer Science, Cambridge, 1979.

Read the full nChain article on Rabin signatures here.

Note: Tokens on the Bitcoin Core (SegWit) chain are referenced as BTC coins; tokens on the Bitcoin Cash ABC chain are referenced as BCH, BCH-ABC or BAB coins.

Bitcoin Satoshi Vision (BSV) is today the only Bitcoin project that follows the original Satoshi Nakamoto whitepaper, and that follows the original Satoshi protocol and design. BSV is the only public blockchain that maintains the original vision for Bitcoin and will massively scale to become the world’s new money and enterprise blockchain.

COMMENT

latest news

Bitcoin SV version 0.2.0 takes the next step towards unlimited scaling

Tech 27 minutes ago

Bitcoin SV version 0.2.0 takes the next step towards unlimited scaling

The Bitcoin SV node team has been true to its goal of massive scaling with huge upgrade on BSV client with version 0.2.0.

Read More
Is China banning Bitcoin mining?

Tech 2 hours ago

Is China banning Bitcoin mining?

The draft proposal from China’s economic planning commission, which labels bitcoin mining as an industry that needs to be “eliminated," sparks undesirable attention to the global mining industry.

Read More
Future block reward halvings spell doom for Bitcoin Core but bright future for Bitcoin SV

Tech 19 May 2019

Future block reward halvings spell doom for Bitcoin Core but bright future for Bitcoin SV

nChain’s chief scientist Dr. Craig Wright has performed some calculations about future economics for Bitcoin Core (BTC).

Read More
[data-clipboard-demo]
[data-clipboard-demo]
[data-clipboard-demo]
[data-clipboard-demo]
[data-clipboard-demo]
[data-clipboard-demo]
[data-clipboard-demo]
[data-clipboard-demo]