Comunion 是一个去中心化的(DAO) 组织协作网络，提供面向数字时代的全新商业基础设施和价值转化机制，致力于让劳动价值 像 资本一样自由流通、交易和积累。
本系列内容包含：基本概念及原理、密码学、共识算法、钱包及节点原理、挖矿原理及实现。
本篇专门讲解哈希碰撞原理，这对于哈希算法的理解是非常重要的。如果把这个理解透了，那么哈希算法里面的很多特点，包括区块链当中为什么使用哈希算法，那么基本上就完全通透了。
定义
摘要函数（哈希函数），其实是一个安全性定义。



抗原像碰撞
什么是原像？函数有定义域，有词语，有对应关系。那么类比到这里，原像是指定义域里面的一些未知数。
引用哈希算法应用中挖矿的例子来说，X是定义域，里面的部分就是原像，Y就是一个值域。
我们来看其定义，几乎所有消息摘要，都难以用ppn算法计算出一个原像。
这句话的意思是，假如确定了一个对应关系，或者确定了一个哈希函数，这时对定义域里面某一个元素，比如X1，进行哈希之后，产生了一个哈希值，比如Y1。
假设这个时候产生了Y1，但是并没有告诉任何人。那么这里就有一个问题：这个Y1的原像是谁呢？
这是很难找出来的，也就是提供一个像：Y1，很难找出其对应的原像：X1，这也就是抗原像碰撞的意思。
抗第二原像碰撞
通过字面意思来解释是，存在两个原像，这两个原像是很难找到碰撞的。
给定一个摘要函数h，消息m1，任何ppn算法都难以计算出一个m2使得m1≠m2并且h（m1）=h（m2）。
意思是，给定一个哈希函数，通过任何ppn算法，很难找出一个m2，但这个m2和m1不相同，然后使得原像m2和m1，里面的像也相同，这是很难做到的。
抗碰撞
给定一个摘要函数，任意ppn算法，难以找到m1，m2，使得h（m1）=h（m2）。
意思是，给定一个哈希函数，使用任意ppn算法，难以找到两个消息（原像），使得它们的像相同。
强抗碰撞的意思是，给定一个哈希函数，从定义域（原像）里面随便找两个数，并且这两个数的像是相同的，这样的数是很难找到的。
抗第二原像碰撞和抗碰撞之间的区别是：
抗第二原像碰撞是抗碰撞里面的一个特殊问题。抗碰撞的条件更加强一些，因为是任意取的两个原像，想得到的像是相同的。而抗第二原像碰撞是给定了一个固定的原像，让再找一个原像，使得这两个原像里面的像相同。所以说抗第二原像碰撞是弱抗碰撞。
在区块链中，如果一个哈希函数满足上述三个安全性定义，即：抗原相碰撞、抗第二原像碰撞、抗碰撞，那么这个函数就可以使用，比如SHA-256就满足这三点。
应用
通过安全性定义，其实我们能发现一个特点：这种函数能进行一个数据的完整性认证。
为什么这么说呢？
举个例子，特工A发了一段消息，内容是：使用任意函数H。并用SHA-256对这段话进行哈希，假设其哈希值全部是0，那么就产生了256个0。
特工A把这段消息发给特工B，特工B收到之后，也对其内容“使用任意函数H”进行哈希，假如产生的值是256个0的话，那么就说明这个消息在传播的过程当中没有被篡改。
发送方将完整的传输传输给了接收方，完成了发送方的目的，同时接受方也可以对数据的完整性进行验证。
这里有的朋友就有疑问了，那么对于消息：使用任意函数X，经过哈希之后，会不会也产生256个0呢？
我可以负责的告诉你，如果对消息进行哈希使用的函数，满足上述三个安全性定义的话，那么是不会产生这种情况的。所以，在进行区块链开发选用函数的时候，可以不必须用SHA-256，但是一定要满足这三个安全条件。
其实讲到这里，有很多朋友会产生一个问题：假如我采用的是SHA-256算法，其原像是任意的字符串，像是固定的，那么这个像的空间有多大呢？
答案是：2的256次方的像，也就是总共可以容纳这么多像。

安全级别
还有一个问题是：一个任意多的原像和一个固定空间大的像，那么肯定会通过一定的概率找到两个原像一样的像，也就是产生了碰撞，那么这个碰撞的概率是多大呢？
这个问题很好理解，像是固定的，但是原线有很多，在一个固定的空间内肯定会有碰撞的概率，就比如之前讲过的粒子对撞机一样的原理。
很多朋友都会对这个问题困扰很久。
其实在密码学里面专门有个悖论来解释这个问题，我们一起来用“生日悖论”来解释一下这个问题。
生日悖论
上述的成功概率与下述的问题相关。
问题：要使得教室里的学生中有两个人的生日相同的概率大于0.5（也就是50%），那么教室里至少需要有多少学生？
从直观上来看，可能至少需要2/365≈183个人才行。但是大家仔细分析一下，回顾一下之前学过的概率论的一些知识，会发现这个问题其实并不容易回答。
我们另外一个角度，从反面来解决这个问题，可能会更好一点。
这个问题的反面事件可以理解为：教室里的学生，任意两个人的生日，不相同的概率大于50%。
如果我们能把反面事件的概率求出来，那么用1减去求得概率就是原题目的答案。
所以这个问题我们转换成：求这个教室里面任意两个人的生日，不相同的概率大于50%的人数。
那么到底有多少个人不相同，概率才大于50%呢？
我们做两个假设：
假设1，每个学生的生日在某个特定一天的概率是1/365；
假设2，n个学生的生日都互不相同的概率大于50%。
这里就转换成了求n是什么。
我们首先来来分析一下，n 个人里面，2个人生日不相同的概率是多大？也就是从教室里面任意选出2个人，那他们生日不相同的概率是多少？
答案是：364/365。
也就是把两个人标记为A和B，A的生日是365天中的某一天，那么B的生日和A不同，就有364种可能。
我们继续，如果3个人不相同的概率是多大呢？那么就是：364/365 * 363/365 。
……
那么n个人不相同的概率应该是：363/365 * 364/365 * ……*（365-n+1）/365
这个时候呢，n个人生日不相同的概率，我们已经求出来了。如果要求这个概率大于50%，则可以写成：pro[363/365 * 364/365 * ……*（365-n+1）/365] >
0.5，这就是反面事件的解。
那正面事件就可以写成：1-{ pro[363/365

364/365 * ……*（365-n+1）/365] > 0.5} > 0.5

算式列出来之后，对n求解，得出n≥23，也就是说，只要不少于23个人，就至少有两人生日相同的概率大于50%。



这看起来很不可思议，但通过计算却是：一个 30 人的班级中，存在两人生日相同的概率为 70%；对于 60 人的班级中，这种概率要大于 99%。
从引起逻辑矛盾的角度来说，生日悖论并不是一种“悖论”。但这个数学事实十分反直觉，故称之为一个悖论。
通过这个问题，我们回来看哈希函数的碰撞问题：假如使用的哈希函数是SHA-256，那么它的安全级别是多少呢？
或者说，假如使用的哈希函数是SHA-256，任意找两个原像，要使这两个原像产生碰撞的概率大于50%，需要做多少次计算呢？
通过生日悖论，我们可以理解到，SHA-256的安全级别不是2256（2的256次方），而是：2（256/2），也就是2的256/2次方。
引申一下，其实在密码学里面，对哈希函数有一个专门的安全性界定，它是跟哈希函数的尾缀有关系的，所以假如使用的是SHA-n，那么其安全级别就是：2^（n/2）。

布隆过滤器的简介

什么是布隆过滤器？

布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。


为什么会出现布隆过滤器？

在日常生活中，包括在设计计算机软件时，我们经常判断一个元素是否在一个集合中。比如：要检查一个单词是否拼写正确（即是否在已知的字典中）；判断一个嫌疑人的名字是否已经在嫌疑名单中；在网络爬虫中，一个网站是否被访问过等等。最直接的方法就是将集合中全部的元素存在计算机中，遇到一个新元素，将它和集合中的元素直接对比。计算机中的集合是用哈希表存储。优点是：快速准确，缺点是：费存储空间。为了提高效率我们可以采用hash表，并且将集合中的元素都映射到bitmap中的一个位上，这样的话就会节省空间和查找的时间。但是由于哈希冲突的原因，我们有可能会产生误判，即不同的元素经过散列函数之后可能产生同一个地址。

布隆过滤器有哪些应用？ 

1、Google著名的分布式数据库Bigtable使用布隆过滤器来查找不存在的行或列，以减少磁盘查找IO的次数。 

2、Squid网页代理缓存服务在cache digests 。 

3、Venti文档存储系统也采用布隆过滤器来检测先前存储的数据。 

4、SPIN模型检测器使用布隆过滤器在大规模验证问题时跟踪可达状态空间。 

5、Google Chrome浏览器使用布隆过滤器加速安全浏览服务。 

6、在很多Key-Value系统也使用了布隆过滤器加快查询过程。如：Hbase、Accumulo、Leveldb。

简单的实现布隆过滤器



BitSet.h
#pragma once

#include <vector>

class BitSet
{
public:
    BitSet(size_t range)//构造函数
    {
        _a.resize((range >> 5) + 1, 0);
    }

    void Set(size_t num)
    {
        size_t index = num >> 5;//在哪个数中
        size_t pos = num % 32;//在哪个比特位中

        _a[index] |= (1 << pos);//将num对应的位置1
    }

    void ReSet(size_t num)
    {
        size_t index = num >> 5;
        size_t pos = num % 32;

        _a[index] &= ~(1 << pos);//将num对应的位置0
    }

    bool Test(size_t num)
    {
        size_t index = num >> 5;
        size_t pos = num % 32;

        return _a[index] & (1 << pos);//如果存在，对应的位是1，&1为1，否则相反
    }

protected:
    vector<int> _a;
};

BloomFilter.h
#pragma once

template <typename K>
struct _Func1
{
    size_t BKDRHash(const char *str)
    {
        register size_t hash = 0;
        while (size_t ch = (size_t)*str++)
        {
            hash = hash * 131 + ch;   // 也可以乘以31、131、1313、13131、131313..           
        }
        return hash;
    }
    size_t operator()(const string& key)
    {
        return BKDRHash(key.c_str());
    }
};

template <typename K>
struct _Func2
{
    size_t SDBMHash(const char *str)
    {
        register size_t hash = 0;
        while (size_t ch = (size_t)*str++)
        {
            hash = 65599 * hash + ch;
            //hash = (size_t)ch + (hash << 6) + (hash << 16) - hash;  
        }
        return hash;
    }
    size_t operator()(const string& key)
    {
        return SDBMHash(key.c_str());
    }
};

template <typename K>
struct _Func3
{
    size_t RSHash(const char *str)
    {
        register size_t hash = 0;
        size_t magic = 63689;
        while (size_t ch = (size_t)*str++)
        {
            hash = hash * magic + ch;
            magic *= 378551;
        }
        return hash;
    }

    size_t operator()(const string& key)
    {
        return RSHash(key.c_str());
    }
};

template <typename K>
struct _Func4
{
    size_t APHash(const char *str)
    {
        register size_t hash = 0;
        size_t ch;
        for (long i = 0; ch = (size_t)*str++; i++)
        {
            if ((i & 1) == 0)
            {
                hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
            }
            else
            {
                hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
            }
        }
        return hash;
    }
    size_t operator()(const string& key)
    {
        return APHash(key.c_str());
    }
};

template <typename K>
struct _Func5
{
    size_t JSHash(const char *str)
    {
        if (!*str)        // 这是由本人添加，以保证空字符串返回哈希值0  
            return 0;
        register size_t hash = 1315423911;
        while (size_t ch = (size_t)*str++)
        {
            hash ^= ((hash << 5) + ch + (hash >> 2));
        }
        return hash;
    }
    size_t operator()(const string& key)
    {
        return JSHash(key.c_str());
    }
};

template <typename K = string
    , typename Func1 = _Func1<K>
    , typename Func2 = _Func2<K>
    , typename Func3 = _Func3<K>
    , typename Func4 = _Func4<K>
    , typename Func5 = _Func5<K >>
class BloomFilter
{
public:
    BloomFilter(const size_t range)
        :_s1(range)
        , _size(range)
    {}

    void Set(const K& key)
    {
        size_t index1 = Func1()(key.c_str()) % _size;
        size_t index2 = Func2()(key.c_str()) % _size;
        size_t index3 = Func3()(key.c_str()) % _size;
        size_t index4 = Func4()(key.c_str()) % _size;
        size_t index5 = Func5()(key.c_str()) % _size;

        _s1.Set(index1);
        _s1.Set(index2);
        _s1.Set(index3);
        _s1.Set(index4);
        _s1.Set(index5);
    }

    bool Test(const K& key)
    {
        size_t index1 = Func1()(key.c_str()) % _size;
        _s1.Test(index1);
        if (_s1.Test(index1) == 0)
            return false;

        size_t index2 = Func2()(key.c_str()) % _size;
        _s1.Test(index2);
        if (_s1.Test(index2) == 0)
            return false;

        size_t index3 = Func3()(key.c_str()) % _size;
        _s1.Test(index3);
        if (_s1.Test(index3) == 0)
            return false;

        size_t index4 = Func4()(key.c_str()) % _size;
        _s1.Test(index4);
        if (_s1.Test(index4) == 0)
            return false;

        size_t index5 = Func1()(key.c_str()) % _size;
        _s1.Test(index5);
        if (_s1.Test(index5) == 0)
            return false;
        return true;
    }
protected:
    BitSet _s1;
    size_t _size;
};

void TestBloomFilter()
{
    BloomFilter<> bf1(1000);
    bf1.Set("sort");
    bf1.Set("man");
    bf1.Set("left");
    bf1.Set("123");
    bf1.Set("真的");
    bf1.Set("https://hao.360.cn/?a1006");
    bf1.Set("https://hao.360.cn/?a10061");
    bf1.Set("https://hao.360.cn/?a10062");
    bf1.Set("https://hao.360.cn/?a10063");
    bf1.Set("https://hao.360.cn/?a10064");

    cout << "Is True?:" << bf1.Test("sort") << endl;
    cout << "Is True?:" << bf1.Test("123") << endl;
    cout << "Is True?:" << bf1.Test("left1") << endl;
    cout << "Is True?:" << bf1.Test("真的") << endl;
    cout << "Is True?:" << bf1.Test("假的") << endl;
    cout << "Is True?:" << bf1.Test("https://hao.360.cn/?a1006") << endl;
    cout << "Is True?:" << bf1.Test("https://hao.360.cn/?a10064") << endl;
    cout << "Is True?:" << bf1.Test("https://hao.360.cn/?a10067") << endl;
}

Test.cpp
#include <iostream>
#include <string>
#include <cassert>
#include <cstdlib>

using namespace std;

#include "BitSet.h"
#include "BloomFilter.h"

int main()
{
    TestBloomFilter();
    return 0;
}

        对于《数据结构和算法》这本书，首先需要了解一下，什么是数据结构呢？简言之，数据结构就是对计算机内存中（或磁盘中）的数据的一种安排。包括数组、链表、栈、二叉树、哈希表等等。


        构造函数在每个对象创建时，都会被自动调用，名称总是与类名相同。
        一个类中的数据字段经常被设置为私有的（private double balance;），而方法经常是公有的（public），这样可以保护数据，使之不会被其他类的方法所修改。所有外界实体要想访问一个类中的数据，必须使用那个类自己的方法。
继承与多态
        继承是指由基类扩展或派生形成一个新类。这个扩展类拥有基类的所有属性，并加上了几种其他属性。例如，秘书类可能是从一个更加一般化的雇员类派生而来，它也许会包括一个雇员类所缺少的字段：打字速度。
        在Java中，继承又被称为子类化，基类被称为父类，扩展类被称为子类。
        多态指的是以相同的办法处理来自不同类的对象。为了使多态能够正常运行，这些不同的类必须从一个基类中派生出来。实际上，多态经常指的是通过一种方法的调用，而实质是对不同的类的对象执行不同的方法。

       字符型char： 注意：当程序用户输入一个字符时，他有可能输入一个或输入多于一个（错误）的字符，因此最安全的读入一个字符的做法是，先读入一个字符串，在通过charAt()方法摘取它的第一个字符：
public static char getChar() throws IOException {
  String s = getString();
  return s.charAt(0);
}
        String类的charAt方法返回一个String类对象中某个特定位置的字符，在上述例子中，是第一个字符，号码是0。
        数值型int：读入数字则需要将得到的String类对象，使用getInt()方法将其转换成int型并返回。
public static int getInt() throws IOException{
  String s = getString();
  return Integer.parseInt(s);
}
        Integer类的parseInt方法将字符串转化成int型，在代码开头需要包括语句  import java.lang.Integer;
        浮点数型double：示例代码
public double getDouble() throws IOException{
    String s = getString();
    Double aDub = Double.valueOf(s);
    return aDub.doubleValue();
}
        字符串首先转换成一个Double型的对象，它是double类型的封装类。然后Double类的doubleValue方法将这个对象转化成double型。

SHA-2 (安全散列算法2)，其中包括SHA-256，是一个非常流行的散列算法。本文，我们将通过一个实例来尽可能地把这个算法简单的介绍一下。

SHA-2以他的安全性著称，（不像SHA-1那样容易破解），并且它的速度很快。在未生成密钥的情况下，比如挖掘比特币，像SHA-2这种快速的hash算法是非常有优势的。

什么是一个哈希函数？

假如你想比较详细的立即通用的哈希函数，可以参考这里。本文就不详细介绍了，不过我们还是要回顾一下哈希函数的三个重要的作用：

确定性的加扰数据。
	
接收任何长度的输入，但是输入的长度是固定的。
	
操作不可逆，也就是说不能从输出推出输入。
 

SHA-2 VS SHA-256

SHA-2是一个算法，他是一个通用的产生hash数据的想法。SHA-256就是假如一些额外的常量，用来定义SHA-2算法的行为。一个比较常见的常量就是输出的长度。比如256或者512，用这个来设置他们输出的比特大小。

下面让我们来一步一步看一个关于SHA-256的例子。

 

SHA-256 “Hello World”

第一步 - 预处理

把“hello world”转变为二进制：


 在后面加上一个1


 

填充0，使得它是512的整数倍减去64比特，我们这里选择了448比特


在最后加入64比特，这个64比特用来表示之前输入的二进制的长度，用大端来表示。我们这里是88，所以二进制就是“1011000”


 

这样我们就有了我们的输入，他总是可以被512整除的。

 

第二步 -- 初始化哈希值 （h）

现在我们来创建8个哈希值，他们是硬编码，代表前8个素数的平方根的小数部分的前32位： 2,3,5,7,11,13,17,19

 



 

 

第三步 -- 初始化一个舍入常数 （k）

和第二步类似，我们要创建一个常数 （关于这些常数更多信息以及什么时候使用他们可以参见这里）。这篇文章中，我们用到了64个。每个值（0-63）是前64个素数（2-311）的立方根小数部分的前32位。



 

第四步 -- 块循环

下面这些步骤每512比特（一块）循环一次。在我们的例子中，因为“hello world”比较短，我们只有一个块。在循环的每一个迭代中，我们都需要对哈希值得h0-h7进行突变，从而产生最终的输出。

 

第五步 -- 创建消息时间表 （w）

 把上面第一步中的输入数据拷贝到一个新的数组中，每一个元素是一个32比特的word：（我们例子中512就是16个元素）


然后增加48个word初始化为0，这样我们就有一个数组w[0…63]


使用下面的算法来修改我们后面假如的全0的元素：

对w[16…63]中的每一个i:

S0 = (w[i-15]向右旋转7） xor （w[0-15] 向右旋转 18） xor （w[i-15] 右移3）
	
S0 = (w[i-2]向右旋转17） xor （w[0-2] 向右旋转 19） xor （w[i-2] 右移10）
	
w[i] = w[i-16] + s0 + w[i-7] + s1
我们下面以w[16]为例来详细说明一下：



这样，我们的w中就有64个words了：

 



 

第六步 -- 压缩

初始化变量a,b,c,d,e,f,g,h让他们的值分别等于我们前面设置的哈希值 h0, h1, h2, h3, h4,h5, h6, h7。

运行下面的压缩循环。这个压缩循环需要突变a .. h的值，如下所示：

i从0到63：

S1 = (e 向右旋转6） xor （e 向右旋转 11） xor （e 向右旋转 25）
	
ch = (e and f) xor ((not e) and g)
emp1 = h + S1 + ch + k[i] + w[i]
	
S0 = (a 向右旋转2) xor (a 向右旋转13) xor (a 向右旋转22)
	
maj = (a and b) xor (a and c) xor (b and c)
	
temp2 := S0 + maj
	
h = g
	
g = f
	
e = d + temp1
	
d = c
	
c = b
	
b = a
	
a = temp1 + temp2
 

我们来过一下第一个迭代，所有的加法都对2^32取模



 



 



 

这个计算过程要继续做63次，始终改变a-h的值，我们不一一计算了，不过我们最终会有这样的结果：



 

第七步 -- 修改最终的值

在压缩循环之后，在每一个块循环内，我们通过加上相应的变量来改变哈希值 a-h。同样的，没有给加法最后都对2^23取模。



 

第八步 -- 级联最终的哈希值

最后一步，把他们连起来：



 

好了，这样我们就经历了SHA-256的每一步了。

 

伪代码

假如你想得到上面所有步骤的伪代码，我们从维基百科得到如下：



 



 



更多原创，敬请关注微信公众号，每日更新业界最新资讯：



欢迎关注个人小站：https://donggeitnote.com/2020/07/15/sha-2-how-to-work/