【区块链技术】默克尔树和常见数字签名算法资料整理

一、默克尔树

默克尔树是一种树形的数据结构，一般形态是二叉树，具有树结构的所有特点。

默克尔树的叶子节点一般存储的是数据块，也可以是数据块的哈希值。

默克尔树的生成过程如下：

将一个大数据块拆分成更多小的数据块，然后对每个数据块进行哈希运算，得到所有数据块的哈希值之后，获得一个哈希列表。

接下来根据列表元素个数的奇偶特性重新再计算出哈希值，如果是偶数，则两两合并再计算哈希值，获得新的列表；

如果是奇数，则前面两两计算哈希值，最后一个单独计算哈希值。

重复上面的过程，最终得到一个哈希值，被称为根哈希。

默克尔树逐层记录哈希值的特点，使得它具有对数据修改敏感的特征。

它有一些比较典型的应用场景。

（1）快速比较大量数据。

叶子节点数据的细微改动，都会导致根节点发生变化，可以用根节点来判断数据是否发生修改。

（2）快速定位数据块的修改。

如果Data1的数据发生修改，那么就会影响H1、H4、Root。根据树的特性，从根节点到叶子节点，只需要通过O（logn）便定位到实际发生改变的数据块是Data1。

（3）零知识证明。

为了证明某个论断是否正确，通常我们需要将数据发送给验证者。默克尔树提供了一种方法，可以证明某方拥有某数据，而不需要将原始数据发给对方。

我们只需要将Data0、H1、H5、Root对外公布，任何拥有Data0的用户，经过计算可以获得同样的Root值，说明该公开用户拥有数据Data1、Data2、Data3。

二、 常见数字签名算法

数字签名中非对称加密算法主要依赖密码学领域的单向函数原理。

即正向操作非常简单，而逆向操作非常困难的函数。

密码学常用的三个单项函数原理为质数分解、离散对数和椭圆曲线问题。

质数分解（prime factorization）即数学中的整数分解，将一个整数分解成几个质数的乘积。

给出两个较大的质数，很快可以求得乘积。

但是给定它们的乘积，无法在一定时间内分解得到两个质数。

整数越大，做因数分解越困难，即满足单向函数条件。

当前流行的RSA算法就是采用质数分解原理。

当前较短的RSA私钥可通过枚举等强力方式破解，当前应用一般推荐2048甚至更高长度的私钥。

随着计算能力的飞速提升，特别是量子计算的发展，人们普遍认为RSA算法将在不久的将来被破解，所以推荐采用加密强度更高的椭圆曲线算法。

离散对数（Discrete logarithm）是一种基于同余运算和原根的一种对数运算。

在实数中对数的定义logba是指对于给定的a和b，有一个数x，使得bx=a。

相同地，在任何群G中可为所有整数k定义一个幂数为bk，而离散对数logba是指使得bk=a的整数k。

离散对数在一些特殊情况下可以快速计算。

然而，通常没有非常高效的方法来计算它们。

公钥密码学中几个重要算法的基础，是假设寻找离散对数的问题解，在仔细选择过的群中，并不存在有效率的求解算法。

Diffie-Hellman密钥交换算法是由上面提到的离散对数难题保证的。

椭圆曲线（Ellipse Curve）为一种代数曲线。

其实椭圆曲线并不是我们高中学习的椭圆形状，其名字的由来是因为椭圆曲线的描述方程，类似于计算一个椭圆周长的方程。

一条椭圆曲线是在射影平面上满足威尔斯特拉斯方程（Weierstrass）所有点的集合，一般形式为y2=x3+ax2+bx+c。

椭圆曲线包含两个重要特性：关于X轴水平对称；不垂直的直线穿过曲线最多三个点。

椭圆曲线在密码学中的应用正是依赖这两个特性。