ECC Node.js

前情

上篇《基于 ECC 的私钥转为公钥的过程》讲到求椭圆曲线上的点时,用的是基于 Python 的 SAGE。为了方便 Node.js 程序员理解和实现完整流程代码,本篇用 Node.js 库实现椭圆曲线点的计算。

用 Node.js 求椭圆曲线的点

库的选型考虑 eosjs 用的 ecurveelliptic

1. ecurve

1
2
3
4
5
6
7
8
const ecurve = require('ecurve')
const BigInteger = require('bigi')

const k1 = ecurve.getCurveByName('secp256k1')
const pk = BigInteger.fromHex('d2653ff7cbb2d8ff129ac27ef5781ce68b2558c41a74af1f2ddca635cbeef07d')
const pub = k1.G.multiply(pk)
pub.affineX.toHex()
pub.affineY.isEven()

得到 x 值为 c0ded2bc1f1305fb0faac5e6c03ee3a1924234985427b6167ca569d13df435cf,y 为偶数,和 SAGE 计算结果一样。

2. elliptic

流程基本一样,所以这里给出完整转换代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#!/usr/bin/env node

/**
* @author UMU618 <umu618@hotmail.com>
* @copyright MEET.ONE 2019
* @description Use block-always-using-brace npm-coding-style.
*/

'use strict'

const bsc = require('bs58check')
const ripemd160 = require('ripemd160')
const bs = require('bs58')
const elliptic = require('elliptic')
const BN = require('bn.js')

function encodePublicKey(payload) {
const checksum = new ripemd160().update(payload).digest()

return bs.encode(Buffer.concat([
payload,
checksum.slice(0, 4)
]))
}

function privateKeyToPublicKey(privateKey) {
const buf = bsc.decode(privateKey)
if (0x80 !== buf[0]) {
throw new Error('Not a private key.')
}
const k1 = elliptic.curves.secp256k1
const pvt = new BN(buf.slice(1), 'be')
const pub = k1.g.mul(pvt)
const y = pub.getY().isEven() ? 2 : 3
return 'EOS' + encodePublicKey(Buffer.from([y].concat(pub.getX().toArray())))
}

const privateKey = '5KQwrPbwdL6PhXujxW37FSSQZ1JiwsST4cqQzDeyXtP79zkvFD3'
const publicKey = privateKeyToPublicKey(privateKey)

console.log(privateKey)
console.log(publicKey)

3. 对比

elliptic 比较好用,比较快。

代码

https://github.com/UMU618/secp256k1-tools

基于 ECC 的私钥转为公钥的过程

基本知识

ECC 体系中,私钥是一个大型随机数,而公钥则是私钥乘以椭圆曲线上的基点后对应的点。

meet-one/private-to-public 是 MEET.ONE 开发的私钥转公钥工具。

EOS 支持的 EC 有两种:secp256k1(以下简称 k1)、secp256r1,下面以 k1 为例,结合 Node.js 和 Python 代码介绍转换过程。

涉及算法

  • BASE58:编解码私钥、公钥。
  • SHA-256:校验私钥,本文忽略此步。
  • ECC, secp256k1:计算公钥。
  • RIPEMD-160:校验公钥。

转换过程

1. 解码私钥

假设私钥为:5KQwrPbwdL6PhXujxW37FSSQZ1JiwsST4cqQzDeyXtP79zkvFD3,这是 base58 编码,用 bs58 库解码:

1
2
3
const bs = require('bs58')

bs.decode('5KQwrPbwdL6PhXujxW37FSSQZ1JiwsST4cqQzDeyXtP79zkvFD3')

得到 <Buffer 80 d2 65 3f f7 cb b2 d8 ff 12 9a c2 7e f5 78 1c e6 8b 25 58 c4 1a 74 af 1f 2d dc a6 35 cb ee f0 7d aa 08 64 4a>,其中第 1 个字节 0x80 是类型,末尾的 4 字节是校验码。

这里我们不关心校验码,也可以直接用 bs58check 解码:

1
2
3
const bsc = require('bs58check')

bsc.decode('5KQwrPbwdL6PhXujxW37FSSQZ1JiwsST4cqQzDeyXtP79zkvFD3')

得到 <Buffer 80 d2 65 3f f7 cb b2 d8 ff 12 9a c2 7e f5 78 1c e6 8b 25 58 c4 1a 74 af 1f 2d dc a6 35 cb ee f0 7d>,去掉首字节后为:

65 3f f7 cb b2 d8 ff 12 9a c2 7e f5 78 1c e6 8b 25 58 c4 1a 74 af 1f 2d dc a6 35 cb ee f0 7d```
1

这是 256bit 整数的 Big endian 字节流表示,转为 16 进制整形为 `0xd2653ff7cbb2d8ff129ac27ef5781ce68b2558c41a74af1f2ddca635cbeef07d`,记为 `pk`。

## 2. 构造椭圆曲线,求公钥的坐标

根据 [SECG](http://secg.org/) 规定的 k1 的参数,我们用基于 Python 的 [SAGE](https://sagecell.sagemath.org/) 构造 k1 对应的椭圆曲线,然后计算 `pk * G`:

```python
a = 0
b = 7
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
Gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
E = EllipticCurve (GF(p), [a, b])
pk = 0xd2653ff7cbb2d8ff129ac27ef5781ce68b2558c41a74af1f2ddca635cbeef07d
G = E(Gx, Gy)
pk * G

结果为:(87237761414843254130560834629777710286905276524352264071298714336416392033743 : 108016191455113306196371645921919775466659772908675410052799661524790827329728 : 1)

注:这里的 (x : y : z) 是射影坐标,一般采用笛卡尔坐标系表示,为 (x/z, y/z)。

3. 编码公钥

取 x 值:87237761414843254130560834629777710286905276524352264071298714336416392033743

16 进制为:0xc0ded2bc1f1305fb0faac5e6c03ee3a1924234985427b6167ca569d13df435cf

Big endian 字节流表示为:[0xc0, 0xde, 0xd2, 0xbc, 0x1f, 0x13, 0x05, 0xfb, 0x0f, 0xaa, 0xc5, 0xe6, 0xc0, 0x3e, 0xe3, 0xa1, 0x92, 0x42, 0x34, 0x98, 0x54, 0x27, 0xb6, 0x16, 0x7c, 0xa5, 0x69, 0xd1, 0x3d, 0xf4, 0x35, 0xcf]

由于 y 值是偶数,所以添加一个前缀 2,得到:[2, 0xc0, 0xde, 0xd2, 0xbc, 0x1f, 0x13, 0x05, 0xfb, 0x0f, 0xaa, 0xc5, 0xe6, 0xc0, 0x3e, 0xe3, 0xa1, 0x92, 0x42, 0x34, 0x98, 0x54, 0x27, 0xb6, 0x16, 0x7c, 0xa5, 0x69, 0xd1, 0x3d, 0xf4, 0x35, 0xcf]

注:若 y 为奇数,则前缀为 3。

注:为什么这么规定?只用 x 值和 y 值的奇偶性表示一个点,这叫公钥的压缩格式。因为只要有 x,就可以通过 k1 的椭圆曲线方程式 $y^2 = x^3 + 7 \mod p$ 求出 y,但此时 y 会有两个解,又由于 p 是一个大质数,必定为奇数,故两个 y 解的和 mod p 一定等于 0,即一奇一偶,所以用 x 和 y 的奇偶性标志即可代表这个点。

接着求校验码:

1
2
3
const ripemd160 = require('ripemd160')

new ripemd160().update(Buffer.from([2, 0xc0, 0xde, 0xd2, 0xbc, 0x1f, 0x13, 0x05, 0xfb, 0x0f, 0xaa, 0xc5, 0xe6, 0xc0, 0x3e, 0xe3, 0xa1, 0x92, 0x42, 0x34, 0x98, 0x54, 0x27, 0xb6, 0x16, 0x7c, 0xa5, 0x69, 0xd1, 0x3d, 0xf4, 0x35, 0xcf])).digest()

得到:<Buffer eb 05 f9 d2 c6 dd 62 f7 f2 a0 f7 61 ea 1d 8c 0b 84 4a 3b 52>,取前 4 字节,添加到末尾,得到:[2, 0xc0, 0xde, 0xd2, 0xbc, 0x1f, 0x13, 0x05, 0xfb, 0x0f, 0xaa, 0xc5, 0xe6, 0xc0, 0x3e, 0xe3, 0xa1, 0x92, 0x42, 0x34, 0x98, 0x54, 0x27, 0xb6, 0x16, 0x7c, 0xa5, 0x69, 0xd1, 0x3d, 0xf4, 0x35, 0xcf, 0xeb, 0x05, 0xf9, 0xd2]

然后,base58 编码:

1
2
3
const bs = require('bs58')

bs.encode(Buffer.from([2, 0xc0, 0xde, 0xd2, 0xbc, 0x1f, 0x13, 0x05, 0xfb, 0x0f, 0xaa, 0xc5, 0xe6, 0xc0, 0x3e, 0xe3, 0xa1, 0x92, 0x42, 0x34, 0x98, 0x54, 0x27, 0xb6, 0x16, 0x7c, 0xa5, 0x69, 0xd1, 0x3d, 0xf4, 0x35, 0xcf, 0xeb, 0x05, 0xf9, 0xd2]))

得到:6MRyAjQq8ud7hVNYcfnVPJqcVpscN5So8BhtHuGYqET5GDW5CV,加上前缀 EOS,即为公钥。

优化思维【4】Bash for 循环

常规教材

Bash 循环有三种写法。

1. 类 C 语言语法

1
2
3
4
5

for ((i = 1; i <= 10000000; ++i))
do
echo $i
done

2. for in 语法

1
2
3
4
for i in {1..10000000}
do
echo $i
done

3. 使用外部命令 seq

1
2
3
4
for i in `seq 1 10000000`
do
echo $i
done

分析

这三种方法中,性能最好的是第一种,最差的是第三种。

方法 1 是语言层面的循环语法,循环会立刻开始,而后两种,作为对比,并不会立刻开始!

方法 2 中的 {1..10000000} 会产生一个 1 到 10000000 的序列,然后再开始循环。

方法 3 中的 seq 1 10000000 是调用 seq 产生一个 1 到 10000000 的序列,然后再开始循环。涉及到外部进程调用和管道传递,所以比方法 2 更慢。

总结

  • 方法 1 写起来最麻烦,性能却是最好的。“做一件事,有很多种方式”,有时候不是好事,有对比,就有伤害……优化往往是和人性作对!

  • 语言原生的方法一般比调用外部命令好。

优化思维【3】消除没必要步骤

故事

四月底给 EOSIO / eos 提了一个优化 MongoDB 插件性能的 PR,被连续感谢好几个 Release

分析

原先的流程:fc::variant -> JSON string -> BSON,实现起来很简单,因为 JSON 是很常见的,fc::variant 和 BSON 都有到 JSON 的转化,所以实现代码很简单,一行两个函数。

但数据大时,性能问题就暴露了,这个过程先把 fc::variant 对象序列化为 JSON 字符串,然后反序列化到 BSON 对象。两步都是 CPU 密集型操作,由于 nodeos 及其插件暂时对多核支持不好,导致单核跑爆。

两个过程都要用递归实现,调用栈可能很深。调用函数可能有入栈出栈的消耗,有一种优化思路正是用 inline 减少函数的频繁调用

回归到本质,fc::variant 和 BSON 都是对象,应该直接转化才对。只是实现起来就不是一行能搞定的。先挑简单的方式实现,后期再优化,这是一种挺常规的做法。

SQLite Node.js

选型

mapbox / sqlite3: Asynchronous, non-blocking SQLite3 bindings for Node.js

安装:

1
yarn add sqlite3

常见操作

创建数据库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
const path = require('path')
const sqlite = require('sqlite3')

const dbPath = path.join(__dirname, 'test.db')
const db = new sqlite.Database(dbPath)

const sqls = [`CREATE TABLE test(
id CHAR(64) NOT NULL PRIMARY KEY CHECK(LENGTH(id) == 64),
timeStamp INTEGER NOT NULL,
state INTEGER NOT NULL DEFAULT 0)`

, 'CREATE INDEX index_id ON txs(id)'
, 'CREATE INDEX index_timeStamp ON txs(timeStamp)'
, 'CREATE INDEX index_state ON txs(state)'
]

db.serialize(() => {
for (let sql of sqls) {
db.run(sql, (err) => {
if (err) {
console.error(err)
} else {
console.log('SQL executed.')
}
})
}
})

db.close()

插入数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const items = [
{ hash: 'D141925E39814FB5256615A1A94EC82B7043D983F68423D8C149A2AE360B623C'
, ts: 1563273661316, state: 0 }
, { hash: '2E9F26F5D0A73AE5DAFC8A1C22264725972AA997A22522A906D8CD7E225096ED'
, ts: 1563273661317, state: 1 }
, { hash: '0FF5F5F5E96664939D07D94975342D71F824747EFECE1D24FDDBB3B29DD91DCB'
, ts: 1563273661318, state: 0 }
]

db.serialize(() => {
const stmt = db.prepare("INSERT INTO test VALUES (?, ?, ?)")
for (const item of items) {
stmt.run(item.hash, item.ts, item.state, (err) => {
if (err) {
console.error(err)
} else {
console.log('INSERT', item.hash)
}
})
}
stmt.finalize()
})

查询

1
2
3
4
5
6
7
8
9
10
11
db.serialize(() => {
db.each("SELECT * FROM test WHERE state=0", (err, row) => {
if (err) {
console.error('SELECT state=0 error:', err)
} else {
// do something here
}
}, (err, count) => {
// do something here
})
})

更新

1
2
3
4
5
6
7
db.run("UPDATE test SET state=1 WHERE state=0", (err) => {
if (err) {
console.error('UPDATE txs error:', err)
} else {
console.log('UPDATE state to 1')
}
})

参考

http://www.sqlitetutorial.net/sqlite-nodejs/

pm2 运维经验

安装

比较多的文章推荐用 npm 安装,但 UMU 更推荐 yarn。

理由Visual Studio Code 脑残粉跟随 Microsoft/vscode 使用 yarn。

参考 yarn 安装,其中 Ubuntu 下命令为:

1
2
3
4
curl -sS https://dl.yarnpkg.com/debian/pubkey.gpg | sudo apt-key add -
echo "deb https://dl.yarnpkg.com/debian/ stable main" | sudo tee /etc/apt/sources.list.d/yarn.list

sudo apt-get update && sudo apt-get install --no-install-recommends yarn

使用 yarn 安装 pm2:

1
yarn global add pm2

运行

不熟悉 yarn 的话,装完一头雾水,装到哪了?用以下命令显示:

1
yarn global bin

结果参考:

  • macOS:/usr/local/bin
  • Ubuntu:/home/ubuntu/.yarn/bin

启动脚本的命令为:

1
`yarn global bin`/pm2 start my-program.js

安全建议

root 身份能不用则不用。

鸡兔同笼问题的程序解法

定义

“鸡兔同笼问题”是我国古算书《孙子算经》中著名的数学问题,其内容是:

今有雉(鸡)兔同笼,上有三十五头,下有九十四足。问雉兔各几何。

数学描述

设鸡有 x 只,兔有 y 只,则:

1
2
x + y = 35
2x + 4y = 94

解这个方程组得 x = 23, y = 12

用矩阵表示:

1
2
[1, 1]  *  [x]  =  [35]
[2, 4] [y] [94]

Python 代码

1
2
3
4
5
6
>>> import numpy as np
>>> a = np.mat([[1, 1], [2, 4]])
>>> b = np.mat([[35], [94]])
>>> a.I * b
matrix([[23.],
[12.]])

再来一题三元版本:

有蜘蛛,蜻蜓,蝉三种动物共 18 只,共有腿 118 条,翅膀 20 对,三种动物各几只?

蜘蛛 8 条腿;蜻蜓 6 条腿, 2 对翅膀;蝉 6 条腿,1 对翅膀。

1
2
3
[1, 1, 1]     [x]     [18]
[8, 6, 6] * [y] = [118]
[0, 2, 1] [z] [20]

代码:

1
2
3
4
5
6
7
>>> import numpy as np
>>> a = np.mat([[1, 1, 1], [8, 6, 6], [0, 2, 1]])
>>> b = np.mat([[18], [118], [20]])
>>> a.I * b
matrix([[5.],
[7.],
[6.]])

优化思维【2】有符号和无符号的本质区别

做题

以下代码打印什么?

1
2
3
4
5
6
7
auto count = sizeof (int);
if (count > -1) {
std::cout << "> -1";
}
else {
std::cout << "<= -1";
}

答案是:<= -1,因为 sizeof (int) 是无符号的,把 auto 改为 int 则结果是 > -1

本质论

当我们声明 unsigned/signed int count 时,unsigned/signed 是变量 count 的使用属性,int 是其容量属性。

所谓使用属性,就是当它存在寄存器或内存时,不管是 unsigned 还是 signed 本质是一样的,但对它进行访问时,就区别对待。

比如对 count 进行加法,unsigned 时用的是 ADD 指令,signed 时用的是 ADC 指令,其余减乘除也都类似地使用不同指令。

再来一个问题:把一个变量保存到文件里,再读出来,怎么知道它是有符号还是无符号?

答案是:如果你不在序列化时考虑符号,则反序列化时,无法知道原来的符号,把它赋值给什么类型的变量它就变成什么类型。

这也是 JSON 文本转对象后,要自己选择数据类型的原因,因为 JSON 文本没表示符号的语法。

结论

优化思路:理解本质,就能了解限制和优化方向。

云游戏开发指南【1】

实用参考

  1. 云游戏的架构设计和技术实现

    https://blog.csdn.net/RA681t58CJxsgCkJ31/article/details/79226317

  2. GamingAnywhere

    http://www.gaminganywhere.org

  3. OBS Studio

    https://github.com/obsproject/obs-studio

服务器架构

  • NVIDIA Grid 显卡

  • Windows 8 - 10,最好别用 7。

  • Sandbox 方案

一份授权 Windows 系统大约可以运行 40~50 个游戏实例。

音频

  • 服务器上设置 48000Hz 采样率;

  • 编码器采用 Opus,48000Hz,128kpbs

    1. 音频编码的延迟:需要一个 frame 才能编码,而等待一个 frame 需要时间。比如,48000Hz 的 samplerate 编码到 1024 samples/frame 的 AAC,一个 frame 需要的采集时间是 1000 * 1024 / 48000 = 21.3ms,这个只是采集的理论时间,应用程序的采集间隔还可能增大这个采集延迟,然后还有编码、传输、解码、播放延迟。

      Opus 的 frame size 默认是 960,相比 1024 的 AAC 理论上可以减少一点点延迟,1000 * 960 / 48000 = 20ms。

      Opus 的 frame size 还可以更小,比如 120,但不建议使用,因为 Windows 一次采集 480 samples,frame_size = 120 时,一次采集包含 4 frames,所以延迟和 frame_size = 480 其实是一样的。另外,live555 最小发送单位是 packet,而不是 frame,并且实现上 packet 要等待 960 samples 时长。

      128kpbs 的 Opus 音质几乎已经顶天了,人耳很难分辨,比 mp3 好太多了,网络上流行的高音质 mp3 都是 320kpbs 的。

    2. Opus 是开源并免费的,AAC 好的编解码器都是收费的。

流传输协议

  • RTSP

  • live555

    http://www.live555.com/

    UMU 之前用 live555 2017.07.18 版本时,发现它对 Opus 支持不好,需要改进,当前版本未测。

优化思维【1】字符串去空格

In place 版本

传入的字符串将被改变。

为方便复用,一般会实现 ltrim 和 rtrim 两个函数,然后 trim 函数调用这两者实现。

  • ltrim:从 str 头部开始找到非空格字符,偏移量记为 offset,将 str 左移(move)offset 个字符。

  • rtrim:从 str 尾部向头部找到非空格字符,偏移量记为 offset,将 str 截断为 offset。

一个想当然的实现:

1
2
3
4
trim(str) {
ltrim(str)
rtrim(str)
}

假设 str 是 x 个空格 + y 个非空格 + z 个空格,则以上代码需要把 y + z 个字符向左移动 x 个位置。

更好的实现是:

1
2
3
4
trim(string& str) {
rtrim(str)
ltrim(str)
}

由于先截断,剩 x + y,再去左移,只需要把 y 个字符左移 x 个位置。

优化思路:尽量减少复制,调整顺序也是优化手段。

Copy 版本

传入的字符串不会被改变,返回一个新的字符串。

一个复用前面代码的实现:

1
2
3
4
5
6
string trim_copy(string str) {
// str is a copy
rtrim(str)
ltrim(str)
return str
}

这个版本需要复制 x + y + z 个字符,ltrim 和 rtrim 里面都有找偏移量的代码可以复用,直接找到 y 个非空格字符是起点和终点,复制这 y 个字符就好了。

1
2
3
4
5
6
string trim_copy(const string& str) {
// str is a copy
l = lfind(str)
r = rfind(str)
return str[l, r]
}

优化思路:尽量减少复制。

move

strlen、strcpy、memmove 这类函数,都有一个优化思路:机器字长对齐,一次处理一个机器字。对于长字符串,效果显著。

优化思路:针对硬件特征调整策略。