主页 > 苹果版imtoken钱包怎么下载 > 比特币源码分析比特币源码阅读笔记[基础]
比特币源码分析比特币源码阅读笔记[基础]
正好坐火车出差,趁着这段时间学习了一波比特币源码。 比特币源代码主要语言为C++,测试代码主要语言为Python。
1. 区块链数据结构与数字签名算法 1. 数据结构 Merkle 树
区块链,顾名思义,是由区块按照一定的规则组成的链条。 什么是区块,我们可以使用命令行工具bitcoin-cli或者区块链浏览器(以及其他网站)来浏览区块详情,例如:
{
"size": 43560,
"version": 2,
"previousblockhash": "00000000000000027e7ba6fe7bad39faf3b5a83daed765f05f7d1b71a1632249",
"merkleroot": "5e049f4030e0ab2debb92378f53c0a6e09548aea083f3ab25e1d94ea1155e29d",
"time": 1388185038,
"difficulty": 1180923195.25802612,
"nonce": 4215469401,
"tx": ["257e7497fb8bc68421eb2c7b699dbab234831600e7352f0d9e6522c7cf3f6c77", # [...many more transactions omitted...] "05cfd38f6ae6aa83674cc99e4d75a1458c165b7ab84725eda41d018a09176634"
]}
区块包含的信息分为几个部分: 1. 元信息,如版本、时间、大小等。 2. 挖矿信息,如只使用一次的随机数、难度系数。 交易数据 4. 交易摘要,以及 .
比特币使用 Merkle 树进行交易聚合。 Merkle树的基础是哈希函数和非对称数字签名,而比特币选择的哈希函数是两层SHA256。 交易本身并不存储在 Merkle 树中,它保存着交易的哈希值。 例如交易A的哈希值计算过程为HA= SHA256(SHA256(A))
,两笔交易A和B的哈希值计算过程为H(A,B)=SHA256(SHA256(HA+HB)))。交易数据成对计算,最终形成哈希二叉树,如图下图
这两个字段代表了整条链的交易摘要的哈希值,表示区块在链中的位置;
下图是一个链的例子:
至此,我们已经知道比特币区块链的底层数据结构是Merkle树。 Merkle 树是哈希指针形式的二叉树。 每个节点都包含其子节点的哈希值。 一旦子节点的结构或内容发生变化,该节点的哈希值将不可避免地发生变化。 因此,两棵Merkle树的顶层是,如果节点的hash值相同,我们就认为两棵Merkle树完全一样。
Merkle树计算核心函数,见/merkle.cpp
/* This implements a constant-space merkle root/path calculator, limited to 2^32 leaves. */static void MerkleComputation(const std::vector& leaves, uint256* proot, bool* pmutated, uint32_t branchpos, std::vector* pbranch) { if (pbranch) pbranch->clear(); if (leaves.size() == 0) { if (pmutated) *pmutated = false; if (proot) *proot = uint256(); return;
} bool mutated = false; // count is the number of leaves processed so far.
uint32_t count = 0; // inner is an array of eagerly computed subtree hashes, indexed by tree
// level (0 being the leaves).
// For example, when count is 25 (11001 in binary), inner[4] is the hash of
// the first 16 leaves, inner[3] of the next 8 leaves, and inner[0] equal to
// the last leaf. The other inner entries are undefined.
uint256 inner[32]; // Which position in inner is a hash that depends on the matching leaf.
int matchlevel = -1; // First process all leaves into 'inner' values.
while (count
uint256 h = leaves[count]; bool matchh = count == branchpos;
count++; int level; // For each of the lower bits in count that are 0, do 1 step. Each
// corresponds to an inner value that existed before processing the
// current leaf, and each needs a hash to combine it.
for (level = 0; !(count & (((uint32_t)1) << level)); level++) { if (pbranch) { if (matchh) {
pbranch->push_back(inner[level]);
} else if (matchlevel == level) {
pbranch->push_back(h);
matchh = true;
}
}
mutated |= (inner[level] == h);
CHash256().Write(inner[level].begin(), 32).Write(h.begin(), 32).Finalize(h.begin());
} // Store the resulting hash at inner position level.
inner[level] = h; if (matchh) {
matchlevel = level;
}
} // Do a final 'sweep' over the rightmost branch of the tree to process
// odd levels, and reduce everything to a single top value.
// Level is the level (counted from the bottom) up to which we've sweeped.
int level = 0; // As long as bit number level in count is zero, skip it. It means there
// is nothing left at this level.
while (!(count & (((uint32_t)1) << level))) {
level++;
}
uint256 h = inner[level]; bool matchh = matchlevel == level; while (count != (((uint32_t)1) << level)) { // If we reach this point, h is an inner value that is not the top.
// We combine it with itself (Bitcoin's special rule for odd levels in
// the tree) to produce a higher level one.
if (pbranch && matchh) {
pbranch->push_back(h);
}
CHash256().Write(h.begin(), 32).Write(h.begin(), 32).Finalize(h.begin()); // Increment count to the value it would have if two entries at this
// level had existed.
count += (((uint32_t)1) << level);
level++; // And propagate the result upwards accordingly.
while (!(count & (((uint32_t)1) << level))) { if (pbranch) { if (matchh) {
pbranch->push_back(inner[level]);
} else if (matchlevel == level) {
pbranch->push_back(h);
matchh = true;
}
}
CHash256().Write(inner[level].begin(), 32).Write(h.begin(), 32).Finalize(h.begin());
level++;
}
} // Return result.
if (pmutated) *pmutated = mutated; if (proot) *proot = h;
}
2. 数字签名算法椭圆曲线算法 2.1 椭圆曲线算法与公钥和私钥
在日常工作中,我们每天都会登录服务器,对公私钥体系非常熟悉。 公钥和私钥不是新技术。 我们可以使用ssh-keygen命令生成一对公钥和私钥; 当我们有私钥时,我们可以使用 ssh-keygen -y -f 生成配对的公钥,但是有公钥不能生成配对的私钥。 这背后的原理就是椭圆曲线数字签名算法(Curve Digital,简称ECDSA)。 比特币使用椭圆曲线生成密钥对,其中公钥作为交易接收方的地址对外传输。
在平面直角坐标系下比特币源码分析,椭圆曲线的形状如下图所示。 在比特币源代码中,椭圆曲线定义在 src/ 目录中。 比特币选择的椭圆曲线方程为y2mod p = (x3+ 7) mod p,其中p是一个非常大的素数,p = 2256- 232- 29- 28- 27- 26- 24- 1。
给定私钥 k,如何从椭圆曲线生成公钥 K? 公式为K=k*G。 其中,比特币源码分析,G代表一个变换,从点k=(x,y)生成k1=(x1,y1),首先求k点的切线,切线与椭圆的交点曲线...
下图以几何形式显示了变换 G。
2.2 SHA-256
哈希函数在比特币中被广泛使用,包括:比特币地址、交易脚本地址、挖矿工作量证明。 在比特币系统中,使用公钥生成比特币地址的算法是SHA256 sum。
从公钥生成比特币地址的整体流程如下图所示
给定公钥K,先进行SHA256哈希比特币源码分析,再对SHA256结果进行哈希,得到的值A为比特币地址,即A = (SHA256(K))。 A 值进一步压缩,我们得到比特币地址,如下所示。 比特币选择的压缩算法是 .
SHA-256计算过程比特币源码分析,如下图
我们来看看比特币源码中SHA256哈希的实现
散列函数类定义如下。 主体是状态 s,它由八个 32 位无符号整数组成。 缓冲区buf用于批量读取和计算数据。
/** A hasher class for SHA-256. */class CSHA256
{private:
uint32_t s[8]; unsigned char buf[64];
uint64_t bytes;public: static const size_t OUTPUT_SIZE = 32;
CSHA256();
CSHA256& Write(const unsigned char* data, size_t len); void Finalize(unsigned char hash[OUTPUT_SIZE]);
CSHA256& Reset();
};
SHA256的主要代码每64个字节读取一次数据,写入buff,处理得到s的值。
CSHA256& CSHA256::Write(const unsigned char* data, size_t len)
{ const unsigned char* end = data + len;
size_t bufsize = bytes % 64; if (bufsize && bufsize + len >= 64) { // Fill the buffer, and process it.
memcpy(buf + bufsize, data, 64 - bufsize);
bytes += 64 - bufsize;
data += 64 - bufsize;
Transform(s, buf, 1);
bufsize = 0;
} if (end - data >= 64) {
size_t blocks = (end - data) / 64;
Transform(s, data, blocks);
data += 64 * blocks;
bytes += 64 * blocks;
} if (end > data) { // Fill the buffer with what remains.
memcpy(buf + bufsize, data, end - data);
bytes += end - data;
} return *this;
}
这里定义了一些基本的操作,Ch, Maj, Sigma0, Sigma1, sigma0, sigma1,很简单,不用赘述。
uint32_t inline Ch(uint32_t x, uint32_t y, uint32_t z) { return z ^ (x & (y ^ z)); }
uint32_t inline Maj(uint32_t x, uint32_t y, uint32_t z) { return (x & y) | (z & (x | y)); }
uint32_t inline Sigma0(uint32_t x) { return (x >> 2 | x << 30) ^ (x >> 13 | x << 19) ^ (x >> 22 | x << 10); }
uint32_t inline Sigma1(uint32_t x) { return (x >> 6 | x << 26) ^ (x >> 11 | x << 21) ^ (x >> 25 | x << 7); }
uint32_t inline sigma0(uint32_t x) { return (x >> 7 | x << 25) ^ (x >> 18 | x << 14) ^ (x >> 3); }
uint32_t inline sigma1(uint32_t x) { return (x >> 17 | x << 15) ^ (x >> 19 | x << 13) ^ (x >> 10); }
初始化八个 32 位无符号整数作为初始状态。
/** Initialize SHA-256 state. */void inline Initialize(uint32_t* s)
{
s[0] = 0x6a09e667ul;
s[1] = 0xbb67ae85ul;
s[2] = 0x3c6ef372ul;
s[3] = 0xa54ff53aul;
s[4] = 0x510e527ful;
s[5] = 0x9b05688cul;
s[6] = 0x1f83d9abul;
s[7] = 0x5be0cd19ul;
}
/** One round of SHA-256. */void inline Round(uint32_t a, uint32_t b, uint32_t c, uint32_t& d, uint32_t e, uint32_t f, uint32_t g, uint32_t& h, uint32_t k, uint32_t w)
{
uint32_t t1 = h + Sigma1(e) + Ch(e, f, g) + k + w;
uint32_t t2 = Sigma0(a) + Maj(a, b, c);
d += t1;
h = t1 + t2;
}
SHA256每一轮的计算过程如上图所示,也很直观,无需赘述。
以下函数内容较多。 函数输入一个64字节的chunk和状态s,每次从chunk中读取4个字节,根据当前状态s进行16轮计算; 完成后进行三轮16轮; 最后,将 8 个无符号整数加到上述 64 轮的结果中,更新状态 s。 经过上面的计算,我们得到了数据块的SHA256哈希值。
数据读写代码,见/src/crypto/common.h
/** Perform a number of SHA-256 transformations, processing 64-byte chunks. */void Transform(uint32_t* s, const unsigned char* chunk, size_t blocks)
{ while (blocks--) {
uint32_t a = s[0], b = s[1], c = s[2], d = s[3], e = s[4], f = s[5], g = s[6], h = s[7];
uint32_t w0, w1, w2, w3, w4, w5, w6, w7, w8, w9, w10, w11, w12, w13, w14, w15; // 步骤一:
Round(a, b, c, d, e, f, g, h, 0x428a2f98, w0 = ReadBE32(chunk + 0));
Round(h, a, b, c, d, e, f, g, 0x71374491, w1 = ReadBE32(chunk + 4)); // 中间省略...
Round(c, d, e, f, g, h, a, b, 0x9bdc06a7, w14 = ReadBE32(chunk + 56));
Round(b, c, d, e, f, g, h, a, 0xc19bf174, w15 = ReadBE32(chunk + 60)); // 步骤二:
Round(a, b, c, d, e, f, g, h, 0xe49b69c1, w0 += sigma1(w14) + w9 + sigma0(w1));
Round(h, a, b, c, d, e, f, g, 0xefbe4786, w1 += sigma1(w15) + w10 + sigma0(w2)); // 中间省略
Round(c, d, e, f, g, h, a, b, 0x06ca6351, w14 += sigma1(w12) + w7 + sigma0(w15));
Round(b, c, d, e, f, g, h, a, 0x14292967, w15 += sigma1(w13) + w8 + sigma0(w0)); // 步骤三:
Round(a, b, c, d, e, f, g, h, 0x27b70a85, w0 += sigma1(w14) + w9 + sigma0(w1));
Round(h, a, b, c, d, e, f, g, 0x2e1b2138, w1 += sigma1(w15) + w10 + sigma0(w2)); // 中间省略
Round(c, d, e, f, g, h, a, b, 0xf40e3585, w14 += sigma1(w12) + w7 + sigma0(w15));
Round(b, c, d, e, f, g, h, a, 0x106aa070, w15 += sigma1(w13) + w8 + sigma0(w0)); // 步骤四:
Round(a, b, c, d, e, f, g, h, 0x19a4c116, w0 += sigma1(w14) + w9 + sigma0(w1));
Round(h, a, b, c, d, e, f, g, 0x1e376c08, w1 += sigma1(w15) + w10 + sigma0(w2)); // 中间省略
Round(c, d, e, f, g, h, a, b, 0xbef9a3f7, w14 + sigma1(w12) + w7 + sigma0(w15));
Round(b, c, d, e, f, g, h, a, 0xc67178f2, w15 + sigma1(w13) + w8 + sigma0(w0));
s[0] += a;
s[1] += b;
s[2] += c;
s[3] += d;
s[4] += e;
s[5] += f;
s[6] += g;
s[7] += h;
chunk += 64;
}
}
挖矿网Ethos中文网是一款简单易用的挖矿系统,为挖矿行业提供教程软件和矿机评测及交易信息,对比计算各种数字货币在挖矿网的挖矿收益,以及矿网挖矿工具介绍,矿场最新动态等。
矿业网络,版权所有丨如未注明,均为原创丨本站采用BY-NC-SA协议授权
转载请注明原文链接:比特币源码解析比特币源码阅读笔记【基础】