组内技术分享的内容, 目前网上相关资料很多, 但读起来都不太合自己的习惯, 于是自己整理并编写一篇简洁并便于 (自己) 理解和分享的文章.
因为之前对密码学没有专门研究, 自己的体会或理解会特别标注为 "个人理解", 请注意甄别, 如有必要可以自行查证.
阅读前需要树立一种观点: 大部分场景都是基于概率的大小而言的, 比如 SHA256 安全性, 区块链不可更改性等.
SHA-256 算法
简介
区块链的基础算法之一, 在其中用于区块 hash 计算方法.
是 SHA-2 下的一个算法标准, 而 SHA-2 全称安全散列算法 2, 即 Secure Hash Algorithm 2, 属于 SHA 算法之一, 是 SHA-1 的后继者, 一种密码散列函数算法标准, 由美国国家安全局研发, 由美国国家标准与技术研究院 (NIST) 在 2001 年发布. 其下一共分六个不同的算法标准: SHA-224,SHA-256,SHA-384,SHA-512,SHA-512/224,SHA-512/256.
个人理解: SHA-2 没有完整的安全证明, 可以认为是一种实践中产生的算法.
基本流程
将信息 m 补齐到长度对 512 取模为 448 得到 m'将信息 m'尾部添加一个用 64 位表示的长度得到 m"将信息 m" 按 512 位分割成 n 份, 循环处理 n 次, 最终获得一个 256 位的信息摘要 m''', 即为所需的摘要值.
理论基础
散列函数安全性
散列 (hash) 函数需要满足以下性质才是安全的:
1. 不能从散列结果得到原始信息, 也就是密码学中的原像问题.
2. 不能出现两个不同的原始信息, 但是 hash 结果一样, 即碰撞问题.
3. 最好由原信息的微小变动能让 hash 结果面目全非, 即雪崩效应.
个人理解
SHA-256 的压缩函数不能完全满足这些性质,"安全" 可以看做是破解的难度大小的相对值, 而非绝对值. 即, 不是绝对安全, 但是大概率安全.
对于第 1 条, SHA-256 做了充分混淆, 但是能不能找到原像? 有可能, 但是时间上不允许. 举例, 一个长度是 1 的字符串, 其 SHA-256 结果为 m. 那么遇到 m, 可以猜测原像有可能是 1."有可能" 的原因见第 2 条的理解.
对于第 2 条, 因为散列后的摘要长度是 2^256, 当有 2^256+1 个原始信息时, 一定有重复, 只是在这个尺度下碰撞几率很小.
第 3 条实际上强制性很弱, 需要大量的反例来证明. 我还没有看到相关的反例.
Merkle-Damgard 结构
SHA-256 的压缩函数满足 Merkle-Damgard 结构, 此时可以保证压缩函数在满足散列函数安全性的前提下, 在分组后做压缩时仍能保证. 关于 Merkle-Damgard 结构, 可以参考《密码学原理与实践》第四章及文末参考资料[2].
个人理解
上一小节可以看到 SHA-256 的压缩函数的安全是概率性的, 那么可以认为 SHA-256 分组处理时, 分组处理的安全概率≈原压缩函数的安全概率.
伪码
- // 所有变量均为无符号 32 位整型, 计算时以 2^32 为模
- // 1. 变量初始化
- // 1.1 初始化变量第一部分: 前 8 个质数 (2, 3, 5 ... 19) 的平方根的前 32 位
- h0 := 0x6a09e667
- h1 := 0xbb67ae85
- h2 := 0x3c6ef372
- h3 := 0xa54ff53a
- h4 := 0x510e527f
- h5 := 0x9b05688c
- h6 := 0x1f83d9ab
- h7 := 0x5be0cd19
- // 1.2 初始化变量第二部分: 前 64 个质数 (2, 3, ..., 311) 的立方根的前 32 位
- k[0..63] :=
- 0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
- 0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
- 0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
- 0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
- 0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
- 0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
- 0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
- 0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
- // 2. 预处理
- // 2.1 给原始消息 m 末尾增加 (接续) 一个二进制 1
- m0 = add1bit(m)
- // 2.2 给 m0 末尾增加连续 k 个 0, 直到其长度对 512 取模后余数为 448
- // k>= 0
- m1 = add0bitsWhenMod512Equals448(m0)
- // 2.3 给 m1 末尾增加 64bit 表示的 m1 的长度, 以大端表示
- m2 = addLengthBigEndian(m1)
- // 3. 将 m1 拆分成 l 个以 512bit 为长度的块
- sub_ms[l] = splitBy512bit(m1)
- // 3.1 子块处理
- for(sub_m : sub_ms ) {
- // 对每个 512bit 的子块, 进一步拆成 16 个 32bit 的子块
- w[0...15] = splitBy32bit(sub_m)
- for(i from 16 to 63) {
- // 计算 w[16]到 w[63]
- //rightrotate 循环右移 x 位, rightshift 右移 x 位高位补 0
- s0 := (w[i-15] rightrotate 7) xor (w[i-15] rightrotate 18) xor(w[i-15] rightshift 3)
- s1 := (w[i-2] rightrotate 17) xor (w[i-2] rightrotate 19) xor(w[i-2] rightshift 10)
- w[i] := w[i-16] + s0 + w[i-7] + s1
- }
- // 局部变量初始化
- a := h0
- b := h1
- c := h2
- d := h3
- e := h4
- f := h5
- g := h6
- h := h7
- // 子块内主循环
- for i from 0 to 63 {
- s0 := (a rightrotate 2) xor (a rightrotate 13) xor(a rightrotate 22)
- maj := (a and b) xor (a and c) xor(b and c)
- t2 := s0 + maj
- s1 := (e rightrotate 6) xor (e rightrotate 11) xor(e rightrotate 25)
- ch := (e and f) xor ((not e) and g)
- t1 := h + s1 + ch + k[i] + w[i]
- h := g
- g := f
- f := e
- e := d + t1
- d := c
- c := b
- b := a
- a := t1 + t2
- }
- // 子块结果更新到全局变量
- h0 := h0 + a
- h1 := h1 + b
- h2 := h2 + c
- h3 := h3 + d
- h4 := h4 + e
- h5 := h5 + f
- h6 := h6 + g
- h7 := h7 + h
- }
- // 3.2 最终的摘要结果计算, append 即位拼接
- digest = hash = h0 append h1 append h2 append h3 append h4 append h5 append h6 append h7
区块链原理
一句话定义
去中心的分布式数据库.
数据结构
伪码如下
- // 区块与前个区块相连.
- /**
- * 区块
- */
- class Block {
- /** 区块头 */
- BlockHead head;
- /** 区块体 */
- BlockBody body;
- }
- /**
- * 区块头
- */
- class BlockHead {
- /** 生成时间 */
- Date gmtGenerate;
- /** 本区块体的 hash 值 */
- String bodyHashCode;
- /** 上个区块的 hash 值 */
- String prevHashCode;
- /** 难度系数 */
- int difficulty;
- /** 随机数, 32 位 */
- int nonce;
- }
- /**
- * 区块体
- */
- class BlockBody {
- /** 数据 */
- byte[] data;
- }
区块的不可修改性
区块的 hash=SHA256(区块头), 区块头包含上一个区块 hash 及本区块体的 hash. 因此, 当前区块 (无论区块头和区块体) 或上一个区块发生变化, 都会导致区块的 hash 变化. 这个关系可以用公式表达为:
blockHash = SHA256(block.header) = SHA256(prevBlockHash + block.body + other)
因此, 修改一个区块会导致断链, 必须连锁地修改后续所有区块. 由于后面会提到计算 hash 很慢的原因, 几乎不可能, 除非拥有全网 51% 计算能力 -- 区块链因此得名.
*__个人理解__为什么是全网 51% 计算的能力? 即在全网中所有计算能力都在挖矿时, 修改的速度超过创建的速度. 假设当前全网只有 1% 的计算能力在挖矿, 那么你只要这 1% 的 51%-- 全网的 0.51% 足矣.
挖矿 -- 创建区块原理
为什么称为 "挖矿"?
所有节点都会创建新的区块. 为了保证节点同步, 区块添加的速度不能太快. 同步的速度由发明者中本聪设置为平均 10 分钟 1 次, 即 1 小时 6 个. 控制速度的方式是, 创建区块需要大量的计算才能获得当前块的 hash, 此后才能添加新的块. 这个海量计算过程类似于从大量的沙子中获取有用的一粒金子, 因此被比喻为 "挖矿". 但是 "金子" 并不完全是指这粒 "合适的 hash", 下文会提到.
难度系数与随机值
只有符合要求的 hash 才被区块链接受, 这个要求是: hash < 常量 targetMax / 当前区块 difficulty.
大部分计算的 hash 是不符合条件的. 为了使 hash 发生变化, 需要改动区块头. 为了让区块头产生变化, 中本聪在区块头增加了随机值 Nonce. 从 0 开始计算到 2^32 位找到 Nonce 具体值的过程, 就是挖矿的过程, 因此 Nonce 和对应的 hash 合起来才是金子, 而计算获得的 hash 只是需要做进一步确认金子的原石.
存在所有值都不是符合要求的 Nonce 的情况, 此时协议允许矿工改变区块体, 重新计算.
当然也存在符合条件的 hash 值有多个的情况, 为了降低这种情况的概率, 可以调节 difficulty 值.
创建时间平均化
根据当前的创建速度, 可以动态地更改 difficulty 的大小来调节, 确保近似平均 10 分钟 1 次. 随着运算能力提升, difficulty 会越来越大, 导致挖矿难度越来越高.
区块链的分叉
如果同时提交两个区块, 两者连接了同一个区块, 那么区块链采用哪一个?
新节点总是采用最长的区块链; 哪个分支先达到 6 个新区块("6 次确认"), 区块链就会采用那条链. 6 次确认只需要 1 个小时就会完成. 可见, 取决于哪条分支拥有更多的计算速度.
被丢弃的短链, 相关计算是完全没有价值的. 在比特币中是这样, 以太坊则会受到一定的补偿.
应用场景
8 年的持续运行证实了其可行性. 但是代价是: 10 分钟同步一次; 大量无意义计算. 因此使用场景有限:
不存在所有节点信任的管理中心
不要求实时写入
挖矿收益弥补本身成本
目前的应用: 比特币; 电子证书等.
附: 参考资料
SHA-2 定义及伪代码 https://zh.wikipedia.org/wiki/SHA-2
SHA256 算法的理论基础(含 SHA256 与 Merkle-Damgard 结构关系简单证明)
区块链入门教程 -- 阮一峰
posted on 2018-12-22 17:37 五岳 阅读(...) 评论(...) 编辑 收藏
来源: https://www.cnblogs.com/wuyuegb2312/p/10017990.html