使用javascript实现Schnorr BIP签名算法

  • 时间:
  • 浏览:202
  • 来源:区块链技术网

前言

在本教程中,我们将看到我编写的Pieter Wuille提出的schnorr签名算法,使用Javascript进行一次编程试验。

背景

这是在椭圆曲线secp256k1上的标准64字节Schnorr签名方案使用JavaScript实现,以及它在Blockstream提出的MuSig多签名方案中的应用。

 

该代码是基于Pieter Wuille的初始提案,当时尚未分配比特币改进提案(BIP)编号。

 

musig实现基于secp256k1 zkp fork中的C实现。

 

当前版本通过了这里提供的所有测试向量。但并不能保证该算法在每种不同情况下都能得到正确的实现!

 

BIP和C参考实现仍在开发中,因此该实现的API也不稳定,并且可以在参考实现更改时进行更改。

如何安装

您可以从git存储库中复制https://github.com/guggero/bip-schnorr,也可以通过npm软件包安装,如下所示。

 

GIT:

 

$ git clone https://github.com/guggero/bip-schnorr

 

NPM:

 

$ npm install --save bip-schnorr

yarn:

 

$ yarn add bip-schnorr

我们还需要安装Big Integer依赖项。

 

Bigi:

 

$ npm install --save bigi

yarn:

 

$ yarn add bigi

如何使用

注意:所有参数都是BigInteger或Buffer类型(或是数组)。

签署和验证Schnorr签名

创建一个名为index.js的文件,如下所示。

const BigInteger = require("bigi");
const schnorr = require('bip-schnorr');
const convert = schnorr.convert;

// signing
const privateKey = BigInteger.fromHex('B7E151628AED2A6ABF7158809CF4F3

C762E7160F38B4DA56A784D9045190CFEF');
const message = Buffer.from('243F6A8885A308D313198A2E03707344A4093822

299F31D0082EFA98EC4E6C89''hex');
const createdSignature = schnorr.sign(privateKey, message);
console.log('The signature is: ' + createdSignature.toString('hex'));

// verifying
const publicKey = Buffer.from('02DFF1D77F2A671C5F36183726DB2341BE58F

EAE1DA2DECED843240F7B502BA659''hex');
const signatureToVerify = Buffer.from('2A298DACAE57395A15D0795DDBFD1

DCB564DA82B0F269BC70A74F8220429BA1D1E51A22CCEC35599B8F
266912281F8365FFC2D035A230434A1A64DC59F7013FD'
'hex');
try {
  schnorr.verify(publicKey, message, signatureToVerify);
  console.log('The signature is valid.');
catch (e) {
  console.error('The signature verification failed: ' + e);
}

// batch verifying
const publicKeys = [
  Buffer.from('02DFF1D77F2A671C5F36183726DB2341BE58FEAE
1DA2DECED843240F7B502BA659'
'hex'),
  Buffer.from('03FAC2114C2FBB091527EB7C64ECB11F8021CB45E8
E7809D3C0938E4B8C0E5F84B'
'hex'),
  Buffer.from('026D7F1D87AB3BBC8BC01F95D9AECE1E659D6E33C8
80F8EFA65FACF83E698BBBF7'
'hex'),
];
const messages = [
  Buffer.from('243F6A8885A308D313198A2E03707344A4093822299F
31D0082EFA98EC4E6C89'
'hex'),
  Buffer.from('5E2D58D8B3BCDF1ABADEC7829054F90DDA9805AAB56C7
7333024B9D0A508B75C'
'hex'),
  Buffer.from('B2F0CD8ECB23C1710903F872C31B0FD37E15224AF4577
22A87C5E0C7F50FFFB3'
'hex'),
];
const signatures = [
  Buffer.from('2A298DACAE57395A15D0795DDBFD1DCB564DA82B0F269B
C70A74F8220429BA1D1E51A22CCEC35599B8F266912281F8365FFC2D035A2
30434A1A64DC59F7013FD'
'hex'),
  Buffer.from('00DA9B08172A9B6F0466A2DEFD817F2D7AB437E0D253CB
5395A963866B3574BE00880371D01766935B92D2AB4CD5C8A2A5837EC57FE
D7660773A05F0DE142380'
'hex'),
  Buffer.from('68CA1CC46F291A385E7C255562068357F964532300BEADFF
B72DD93668C0C1CAC8D26132EB3200B86D66DE9C661A464C6B2293BB9A9F5B
966E53CA736C7E504F'
'hex'),
];
try {
  schnorr.batchVerify(publicKeys, messages, signatures);
  console.log('The signatures are valid.');
catch (e) {
  console.error('The signature verification failed: ' + e);
}

执行脚本应该有以下输出。

 

$ node ./index.js
The signature is2a298dacae57395a15d0795ddbfd1dcb564da82b0f269bc70

a74f8220429ba1d1e51a22ccec35599b8f266912281f8365ffc2d035a230434a1a6

4dc59f7013fd
The signature is valid.
The signatures are valid.

聚合密钥和验证

聚合签名(Schnorr密钥聚合,不是BIP的一部分,不能防止流氓密钥攻击!)

 

const BigInteger = require("bigi");
const schnorr = require('bip-schnorr');
const convert = schnorr.convert;

// aggregating signatures (naive Schnorr key aggregation, 
not part of BIP, not safe against rogue-key-attack!)
const privateKey1 = BigInteger.fromHex('B7E151628AED2A6ABF7158809CF

4F3C762E71
60F38B4DA56A784D9045190CFEF'
);
const privateKey2 = BigInteger.fromHex('C90FDAA22168C234C4C6628B80D

C1CD129024
E088A67CC74020BBEA63B14E5C7'
);
const message = Buffer.from('243F6A8885A308D313198A2E03707344A40938

22299F
31D0082EFA98EC4E6C89'
'hex');
const aggregatedSignature = schnorr.naiveKeyAggregation(

[privateKey1, privateKey2], message);

// verifying an aggregated signature
const publicKey1 = Buffer.from('02DFF1D77F2A671C5F36183726DB2341BE

58FEAE1DA2D
ECED843240F7B502BA659'
'hex');
const publicKey2 = Buffer.from('03FAC2114C2FBB091527EB7C64ECB11F80

21CB45E8E78
09D3C0938E4B8C0E5F84B'
'hex');
const sumOfPublicKeys = convert.pubKeyToPoint(publicKey1).add
(convert.pubKeyToPoint(publicKey2));
try {
  schnorr.verify(convert.pointToBuffer(sumOfPublicKeys), 
message, aggregatedSignature);
  console.log('The signature is valid.');
catch (e) {
  console.error('The signature verification failed: ' + e);
}

执行此脚本应该会有以下输出。

 

$ node ./index.js
The signature is valid.

非交互musig

const BigInteger = require("bigi");
const schnorr = require('bip-schnorr');
const convert = schnorr.convert;

// muSig non-interactive (not part of any BIP yet, see 

https://blockstream.com/2018/01/23/musig-key-aggregation-schnorr

-signatures/)
const privateKey1 = BigInteger.fromHex('B7E151628AED2A6ABF7158809CF4

F3C762E7160F38B4DA56A784D9045190CFEF');
const privateKey2 = BigInteger.fromHex('C90FDAA22168C234C4C6628B80DC

1CD129024E088A67CC74020BBEA63B14E5C7');
const message = Buffer.from('243F6A8885A308D313198A2E03707344A409382

2299F31D0082EFA98EC4E6C89''hex');
const aggregatedSignature = schnorr.muSig.nonInteractive(

[privateKey1, privateKey2], message);

// verifying an aggregated signature
const publicKey1 = Buffer.from('02DFF1D77F2A671C5F36183726DB2341BE58

FEAE1DA2DECED843240F7B502BA659''hex');
const publicKey2 = Buffer.from('03FAC2114C2FBB091527EB7C64ECB11F8021

CB45E8E7809D3C0938E4B8C0E5F84B''hex');
const X = schnorr.muSig.pubKeyCombine([publicKey1, publicKey2]);
try {
  schnorr.verify(X, message, aggregatedSignature);
  console.log('The signature is valid.');
catch (e) {
  console.error('The signature verification failed: ' + e);
}

执行此脚本应该会有以下输出。

 

$ node ./musig.js
The signature is valid.

musig

const BigInteger = require('bigi');
const randomBytes = require('random-bytes');
const randomBuffer = (len) => Buffer.from(randomBytes.sync(len));
const schnorr = require('bip-schnorr');
const convert = schnorr.convert;
const muSig = schnorr.muSig;

// data known to every participant
const publicData = {
  pubKeys: [
    Buffer.from('03846f34fdb2345f4bf932cb4b7d278fb3af24f44224fb52ae5

51781c3a3cad68a''hex'),
    Buffer.from('02cd836b1d42c51d80cef695a14502c21d2c3c644bc82f6a705

2eb29247cf61f4f''hex'),
    Buffer.from('03b8c1765111002f09ba35c468fab273798a9058d1f8a4e276f

45a1f1481dd0bdb''hex'),
  ],
  message: convert.hash(Buffer.from('muSig is awesome!''utf8')),
  pubKeyHash: null,
  pubKeyCombined: null,
  commitments: [],
  nonces: [],
  nonceCombined: null,
  partialSignatures: [],
  signature: null,
};

// data only known by the individual party, these values are never 

shared
// between the signers!
const signerPrivateData = [
  // signer 1
  {
    privateKey: BigInteger.fromHex('add2b25e2d356bec3770305391cbc80c

ab3a40057ad836bcb49ef3eed74a3fee'),
    session: null,
  },
  // signer 2
  {
    privateKey: BigInteger.fromHex('0a1645eef5a10e1f5011269abba9fd85

c4f0cc70820d6f102fb7137f2988ad78'),
    session: null,
  },
  // signer 3
  {
    privateKey: BigInteger.fromHex('2031e7fed15c770519707bb092a63372

15530e921ccea42030c15d86e8eaf0b8'),
    session: null,
  }
];

// -----------------------------------------------------------------------
// Step 1: Combine the public keys
// The public keys P_i are combined into the combined public key P.
// This can be done by every signer individually or by the initializing
// party and then be distributed to every participant.
// -----------------------------------------------------------------------
publicData.pubKeyHash = muSig.computeEll(publicData.pubKeys);
publicData.pubKeyCombined = muSig.pubKeyCombine(publicData.pubKeys, publicData.pubKeyHash);

// -----------------------------------------------------------------------
// Step 2: Create the private signing session
// Each signing party does this in private. The session ID *must* be
// unique for every call to sessionInitialize, otherwise it's trivial for
// an attacker to extract the secret key!
// -----------------------------------------------------------------------
signerPrivateData.forEach((data, idx) => {
  const sessionId = randomBuffer(32); // must never be reused between sessions!
  data.session = muSig.sessionInitialize(
    sessionId,
    data.privateKey,
    publicData.message,
    publicData.pubKeyCombined,
    publicData.pubKeyHash,
    idx
  );
});
const signerSession = signerPrivateData[0].session;

// -----------------------------------------------------------------------
// Step 3: Exchange commitments (communication round 1)
// The signers now exchange the commitments H(R_i). This is simulated here
// by copying the values from the private data to public data array.
// -----------------------------------------------------------------------
for (let i = 0; i < publicData.pubKeys.length; i++) {
  publicData.commitments[i] = signerPrivateData[i].session.commitment;
}

// -----------------------------------------------------------------------
// Step 4: Get nonces (communication round 2)
// Now that everybody has commited to the session, the nonces (R_i) can be
// exchanged. Again, this is simulated by copying.
// -----------------------------------------------------------------------
for (let i = 0; i < publicData.pubKeys.length; i++) {
  publicData.nonces[i] = signerPrivateData[i].session.nonce;
}

// -----------------------------------------------------------------------
// Step 5: Combine nonces
// The nonces can now be combined into R. Each participant should do this
// and keep track of whether the nonce was negated or not. This is needed
// for the later steps.
// -----------------------------------------------------------------------
publicData.nonceCombined = muSig.sessionNonceCombine(signerSession, publicData.nonces);
signerPrivateData.forEach(data => (data.session.nonceIsNegated = signerSession.nonceIsNegated));

// -----------------------------------------------------------------------
// Step 6: Generate partial signatures
// Every participant can now create their partial signature s_i over the
// given message.
// -----------------------------------------------------------------------
signerPrivateData.forEach(data => {
  data.session.partialSignature = muSig.partialSign(data.session, publicData.message, publicData.nonceCombined, publicData.pubKeyCombined);
});

// -----------------------------------------------------------------------
// Step 7: Exchange partial signatures (communication round 3)
// The partial signature of each signer is exchanged with the other
// participants. Simulated here by copying.
// -----------------------------------------------------------------------
for (let i = 0; i < publicData.pubKeys.length; i++) {
  publicData.partialSignatures[i] = signerPrivateData[i].session.partialSignature;
}

// -----------------------------------------------------------------------
// Step 8: Verify individual partial signatures
// Every participant should verify the partial signatures received by the
// other participants.
// -----------------------------------------------------------------------
for (let i = 0; i < publicData.pubKeys.length; i++) {
  muSig.partialSigVerify(
    signerSession,
    publicData.partialSignatures[i],
    publicData.nonceCombined,
    i,
    publicData.pubKeys[i],
    publicData.nonces[i]
  );
}

// -----------------------------------------------------------------------
// Step 9: Combine partial signatures
// Finally, the partial signatures can be combined into the full signature
// (s, R) that can be verified against combined public key P.
// -----------------------------------------------------------------------
publicData.signature = muSig.partialSigCombine(publicData.nonceCombined, publicData.partialSignatures);

// -----------------------------------------------------------------------
// Step 10: Verify signature
// The resulting signature can now be verified as a normal Schnorr
// signature (s, R) over the message m and public key P.
// -----------------------------------------------------------------------
schnorr.verify(publicData.pubKeyCombined, publicData.message, publicData.signature);

API

schnorr.sign(privateKey:BigInteger,message:Buffer):Buffer

使用私钥对32字节消息进行签名,返回64字节签名。

schnorr.verify(pubKey:Buffer,message:Buffer,signature:Buffer):void

验证针对公钥的32字节消息的64字节签名。 验证失败时会引发错误。

schnorr.batchVerify(pubKeys:Buffer [],消息:Buffer [],签名:Buffer []):void

验证64字节签名列表作为批处理操作。 验证失败时会引发错误。

schnorr.naiveKeyAggregation(privateKeys:BigInteger [],message:Buffer):Buffer

将同一消息上不同私钥的多个签名聚合为单个64字节签名。

这种方案不安全,容易发生所谓的流氓密钥攻击。

 

防止该攻击的muSig方案。

 

schnorr.muSig.nonInteractive(privateKeys:BigInteger [],message:Buffer):Buffer

使用可防止恶意密钥攻击的方案,将同一消息上不同私钥的多个签名聚合为单个64字节签名。

 

这种非交互式方案需要知道参与多签名创建的所有私钥。使用MuSig交互式方案,该方案需要多个步骤来创建签名,其中各方不共享其私钥

schnorr.muSig.computeEll(pubKeys:Buffer []):Buffer

生成ell,它是参与muSig会话的所有公钥的哈希值。

schnorr.muSig.pubKeyCombine(pubKeys:Buffer [],pubKeyHash:Buffer):Buffer

通过在将每个公钥P_i加到一起之前将MuSig系数应用于每个公钥P_i来创建特殊的流氓密钥组合公钥P.

schnorr.muSig.sessionInitialize(sessionId:Buffer,privateKey:BigInteger,message:Buffer,pubKeyCombined:Buffer,ell:Buffer,idx:number):Session

创建签名会话。每个参与者必须创建一个会话,除了承诺和后来的nonce之外,不得共享会话的内容。

会话ID对于sessionInitialize的每次调用都是唯一的。否则,攻击者提取密钥是微不足道的!

schnorr.muSig.sessionNonceCombine(session:Session,nonces:Buffer []):Buffer

将多个随机数R_i组合成组合的随机数R.

schnorr.muSig.partialSign(session:Session,message:Buffer,nonceCombined:Buffer,pubKeyCombined:Buffer):BigInteger

为参与者创建部分签名s_i。

schnorr.muSig.partialSigVerify(session:session,partialSig:BigInteger,nonceCombined:Buffer,idx:number,pubKey:Buffer,nonce:Buffer):void

验证参与者的公钥P_i的部分签名s_i。

验证失败时会引发错误。

schnorr.muSig.partialSigCombine(nonceCombined:Buffer,partialSigs:BigInteger []):Buffer

将多个部分签名组合成可以验证的Schnorr签名(s,R)

组合公钥P.

性能

代码尚未针对性能进行优化。

在具有节点v10.15.0的linux / amd64上运行的Intel Core i7-6500U上获得了以下结果:

$ node test/schnorr.benchmark.js
Sign (batch size: 1) x 29.81 ops/sec ±2.23% (53 runs sampled) 
35344 us/op 28 sig/s
Sign (batch size: 2) x 15.28 ops/sec ±1.99% (42 runs sampled) 
67103 us/op 30 sig/s
Sign (batch size: 4) x 7.51 ops/sec ±1.98% (23 runs sampled) 
134388 us/op 30 sig/s
Sign (batch size: 8) x 3.83 ops/sec ±2.27% (14 runs sampled) 
260547 us/op 31 sig/s
Sign (batch size: 16) x 1.92 ops/sec ±0.99% (9 runs sampled) 
525121 us/op 30 sig/s
Sign (batch size: 32) x 0.96 ops/sec ±2.78% (7 runs sampled) 
1044533 us/op 31 sig/s
Sign (batch size: 64) x 0.48 ops/sec ±1.51% (6 runs sampled) 
2072564 us/op 31 sig/s
Verify (batch size: 1) x 29.96 ops/sec ±0.77% (53 runs sampled) 
34513 us/op 29 sig/s
Verify (batch size: 2) x 15.30 ops/sec ±0.70% (42 runs sampled) 
67126 us/op 30 sig/s
Verify (batch size: 4) x 7.64 ops/sec ±1.03% (23 runs sampled) 
132236 us/op 30 sig/s
Verify (batch size: 8) x 3.85 ops/sec ±1.02% (14 runs sampled) 
261091 us/op 31 sig/s
Verify (batch size: 16) x 1.93 ops/sec ±0.53% (9 runs sampled) 
519554 us/op 31 sig/s
Verify (batch size: 32) x 0.97 ops/sec ±0.64% (7 runs sampled) 
1033222 us/op 31 sig/s
Verify (batch size: 64) x 0.48 ops/sec ±0.69% (6 runs sampled) 
2079248 us/op 31 sig/s
Batch Verify (batch size: 1) x 30.55 ops/sec ±0.93% (54 runs sampled)
33736 us/op 30 sig/s
Batch Verify (batch size: 2) x 12.35 ops/sec ±0.88% (35 runs sampled)
82398 us/op 24 sig/s
Batch Verify (batch size: 4) x 5.64 ops/sec ±1.25% (18 runs sampled) 
178555 us/op 22 sig/s
Batch Verify (batch size: 8) x 2.71 ops/sec ±0.83% (11 runs sampled) 
370195 us/op 22 sig/s
Batch Verify (batch size: 16) x 1.32 ops/sec ±0.72% (8 runs sampled) 
760835 us/op 21 sig/s
Batch Verify (batch size: 32) x 0.66 ops/sec ±0.52% (6 runs sampled) 
1523772 us/op 21 sig/s
Batch Verify (batch size: 64) x 0.33 ops/sec ±0.41% (5 runs sampled) 
3061443 us/op 21 sig/s
Aggregate Signatures naive (batch size: 1) x 31.36 ops/sec ±0.76
(55 runs sampled) 33094 us/op 30 sig/s
Aggregate Signatures naive (batch size: 2) x 15.49 ops/sec ±0.83
(42 runs sampled) 66253 us/op 30 sig/s
Aggregate Signatures naive (batch size: 4) x 7.80 ops/sec ±1.06
(24 runs sampled) 128978 us/op 31 sig/s
Aggregate Signatures naive (batch size: 8) x 3.97 ops/sec ±0.22
(14 runs sampled) 254682 us/op 31 sig/s
Aggregate Signatures naive (batch size: 16) x 1.95 ops/sec ±0.78
(9 runs sampled) 515667 us/op 31 sig/s
Aggregate Signatures naive (batch size: 32) x 0.98 ops/sec ±0.53
(7 runs sampled) 1023110 us/op 31 sig/s
Aggregate Signatures naive (batch size: 64) x 0.49 ops/sec ±0.60
(6 runs sampled) 2038238 us/op 31 sig/s
Aggregate Signatures MuSig non-interactive (batch size: 1) x 19.99 
ops/sec ±1.07% (37 runs sampled) 51157 us/op 20 sig/s
Aggregate Signatures MuSig non-interactive (batch size: 2) x 9.91 
ops/sec ±1.68% (29 runs sampled) 102176 us/op 20 sig/s
Aggregate Signatures MuSig non-interactive (batch size: 4) x 4.99 
ops/sec ±1.23% (17 runs sampled) 201754 us/op 20 sig/s
Aggregate Signatures MuSig non-interactive (batch size: 8) x 2.51 
ops/sec ±0.75% (11 runs sampled) 400945 us/op 20 sig/s
Aggregate Signatures MuSig non-interactive (batch size: 16) x 1.26 
ops/sec ±0.72% (8 runs sampled) 792623 us/op 20 sig/s
Aggregate Signatures MuSig non-interactive (batch size: 32) x 0.62 
ops/sec ±2.60% (6 runs sampled) 1618385 us/op 20 sig/s
Aggregate Signatures MuSig non-interactive (batch size: 64) x 0.32 
ops/sec ±0.71% (5 runs sampled) 3171948 us/op 20 sig/s
Done in 422.45s.

猜你喜欢

区块链红利吃饱后,这个巨头又想"征服"元宇宙?

据12月26日消息,百度与英伟达(NVIDIA)已达成协议,双方合作共建AI元宇宙。另外,在今日举行的百度AI开发者大会上,英伟达全球副总裁暨亚太区总裁 Raymond Teh将受邀出席,并发表主题演讲。

2021-12-27

2021年,区块链股权融资发生了怎么样的演变

过去一年,区块链行业融资井喷,在科技领域中独树一帜,A16z、红杉、老虎基金等等这些顶级机构在 2021 年的区块链行业肆意驰骋,在 DeFi、NFT、Metaverse 等领域扶持了一众创业项目。

2021-12-23

两个元宇宙的世界观,以及和区块链的关系

“元宇宙”这个名词音好听但义很难传达准确,想要更准确地理解义,取名为平行宇宙、竞争宇宙、山寨宇宙,更好。对应的,我们现在肉身所处的宇宙,我们称之为“肉身宇宙”。

2021-12-22

Alien Worlds(外星世界)区块链打金挖矿指南

Alien Worlds(外星世界)是一款4月就开始的游戏,10月27日又上线了全新的任务(Missions)游戏模式; 在WAX用户量排名中Alien Worlds(外星世界)一直排在前三,说明现在存量工作室还有很多;

2021-12-17

DeHorizon(地平线)区块链打金教程

今天我们就解析在一款社交主题游戏 — DeHorizon

2021-12-17