概念

Merkle Tree 又称 Hash Tree，实现一般为二叉树，当然也可以用多叉树实现，本质是一样的，WiKi 上也有相关介绍，点击这里传送。

树的叶子节点处存放数据的哈希值，其他的非叶子节点通过子节点进行构造，按照下方公式：

$$node_i = hash(node_{2i+1} || node_{2i+2})$$

其中，节点 $i$ 是节点 $2i+1$ 和 $2i+2$ 的父结点，$||$ 表示串接，或者简单的说拼接，比如 $a = 0001_2, b = 1100_2$ 则
$$c = a || b = 00011100_2$$

HORS(Hash to Obtain Random Subset)属于 FTS, 其生成的公私钥对，可以多次用来签名消息，但是每一次签名之后，系统的安全性会降低，签名能够被伪造的概率上升。论文可见 Better than BiBa: Short One-time Signatures with Fast Signing and Verifying。

下面以三元组 $(GEN, SIG, VER)$ 对 HORS 签名系统进行介绍。

密钥生成($GEN$)

$$(pk, sk) \leftarrow GEN(1^k)$$

首先，我们需要确定参数 $k$ 和 $t = 2^\tau$，哈希函数输出的摘要长度为 $n = k \times \log_2t = k \times \tau$ bits。

1979 年 Ralph C. Merkle 提出了 Winternitz-OTS，其中运用了哈希链(hash chain)的结构，论文见 A Certified Digital Signature ，更加详细的算法描述见 Hash-based Digital Signature Schemes，该算法产生的一对密钥也只能签名一条消息。

下面按照 $(GEN, SIG, VER)$ 三元组描述该算法。

密钥生成($GEN$)

$$(pk, sk) \leftarrow GEN(1^k)$$

首先，我们需要确定 $w$ 参数该参数决定哈希私钥多少次构造公钥，此外还需确定哈希之后摘要的长度 $n$ ，或者可以认为是采用的哈希函数族。

Lamport 是第一个 OTS(One Time Signature) 算法，由 Leslie Lamport 于 1979 年提出，论文可见 Constructing Digital Signatures from One Way Function ，一对密钥只能签名一次，不能重复使用。

下面按照 $(GEN, SIG, VER)$ 三元组描述该算法。

密钥生成($GEN$)

$$(pk, sk) \leftarrow GEN(1^k)$$

首先我们需要确定安全参数 $k$，不过实际操作中我们一般只需要确定输出的摘要长度 $n$。

通过随机数生成器(PRG, Pseudo Random Generator)，生成 $n$ 对随机数，每一对包含两个随机数，每一个随机数 $n$ bits，总共 $2\times n\times n$ bits，此为私钥。

对每一个随机数进行哈希，生成 $2\times n$ 个摘要，每一个 $n$ bits，也是 $2 \times n \times n$ bits，此为公钥。

形式化表示为：

$$sk = (sk_{0,0}, sk_{0,1}, \dotsm, sk_{n-1, 0}, sk_{n-1, 1}) \\ pk = (pk_{0,0}, pk_{0,1}, \dotsm, pk_{n-1, 0}, pk_{n-1, 1})$$

定义

任意的签名算法都可以用一个三元组表示: ($GEN, SIG, VER$)，可以说是组成签名系统的三个算法。

• $GEN$: 密钥生成算法
• $SIG$: 消息签名算法
• $VER$: 消息校验算法

定义一个接口表示：

1
2
3
4
5
6
7
8

type Signature interface {
	// GenerateKey generates secret key and public key
	GenerateKey() (sk []byte, pk []byte)
	// Sign computes signature of message using secret key
	Sign(message []byte, sk []byte) []byte
	// Verify check if the signature is valid
	Verify(message []byte, pk []byte, signature []byte) bool
}

下面详细说说这三个算法。