免责声明:凤梨财经作为开放的信息发布平台,所提供的所有内容与凤梨财经观点和立场无关,且不构成任何投资理财建议。投资有风险,入市需谨慎。

比特币核心数据结构

2019-08-08 阅读量 241
摘要:比特币核心数据结构
         

我们学习计算机时曾经有这么一个定义:程序=数据结构+算法,对于一个区块链,我认为从技术方面看与程序的定义类似,核心一个是共识算法,一个是核心数据结构,这两点直接决定了这条区块链工作运行原理。比特币的共识算法,在这一篇《哈希函数与比特币共识算法PoW》中已经讲述了其原理,这一篇主要讲述比特币核心数据结构这一部分。主要包括如下内容:

  • Blockchain(区块链)

  • Block(区块)

  • Block Header(区块头部)

  • Merkle Tree(默克尔树)

  • Transaction(交易)

Blockchain

区块链很难用一个什么定义来描述,如果一定要描述的话,借用以太坊黄皮书中的解释:区块链就是一个具有共享状态的密码性安全交易的单机(cryptographically secure transactional singleton machine with shared-state)。这里按数据结构的层面来描述区块链,就是用哈希指针将一些列区块串联起来形成的一条数据链。在比特币区块链中,是有区块这个概念的,现在部分区块链中已经没有区块这个概念了,感兴趣的可以关注一下DAG。

Block

上面讲到区块链是由一个个区块构成的,哪区块是怎么定义的?由区块头部和交易两部分构成:

  • 区块头部: a data structure containing the block's metadata

  • 交易列表: an array (vector in rust) of transactions

C++版本实现定义:

class CBlock : public CBlockHeader
{
public:
// network and disk
std::vectorvtx;

//...省略部分代码...
}

Rust版本实现定义,可以看到基本都是一样的:

#[derive(Debug, PartialEq, Clone, Serializable, Deserializable)]
pub struct Block {
pub block_essay-header: BlockHeader, // 区块头部
pub transactions: Vec, // 交易列表
}

BlockHeader

区块头部定义如下:

c++版本实现定义:

/** Nodes collect new transactions into a block, hash them into a hash tree,
* and scan through nonce values to make the block's hash satisfy proof-of-work
* requirements. When they solve the proof-of-work, they broadcast the block
* to everyone and the block is added to the block chain. The first transaction
* in the block is a special one that creates a new coin owned by the creator
* of the block.
*/

class CBlockHeader
{

public:
// essay-header
int32_t nVersion; // 版本号,指定验证规则(indicates which set of block validation rules to follow)
uint256 hashPrevBlock; // 前一区块哈希(实际计算时取得是前一区块头哈希)(a reference to the parent/previous block in the blockchain)
uint256 hashMerkleRoot; // 默克尔根哈希(a hash (root hash) of the merkle tree data structure containing a block's transactions)
uint32_t nTime; // 时戳(seconds from Unix Epoch)
uint32_t nBits; // 区块难度(aka the difficulty target for this block)
uint32_t nNonce; // 工作量证明nonce(value used in proof-of-work)

// ...部分代码省略...
}

Rust实现版本定义,可以看到基本都是一样的:

#[derive(PartialEq, Clone, Serializable, Deserializable)]
pub struct BlockHeader {
pub version: u32, // 版本号,指定验证规则
pub previous_essay-header_hash: H256, // 前一区块哈希
pub merkle_root_hash: H256, // 默克尔根哈希
pub time: u32, // 时戳
pub bits: Compact, // 区块难度
pub nonce: u32, // 工作量证明nonce
}

Merkle Tree

上面区块头部的hashMerkleRoot字段就是默克尔树根哈希值,默克尔树可以说是区块中最重要的一个数据结构,不仅仅提供了整个区块所有交易的完整性验证,。

Rust版本Merkle tree代码实现如下:

/// Calculates the root of the merkle tree
/// https://en.bitcoin.it/wiki/Protocol_documentation#Merkle_Trees
pub fn merkle_root<T: AsRef<H256> + Sync>(hashes: &[T]) -> H256{
// 递归结束条件
if hashes.len() == 1 {
return hashes[0].as_ref().clone();
}
// 哈希成对,为下一步计算做准备
let mut row = Vec::with_capacity(hashes.len() / 2);
let mut i = 0;
while i + 1 < hashes.len() {
row.push((&hashes[i], &hashes[i + 1]));
i += 2
}

// duplicate the last element if len is not even
if hashes.len() % 2 == 1 {
let last = &hashes[hashes.len() - 1];
row.push((last, last)); //如果元素是奇数个数,将最后一个元素复制一份,自己与自己配对
}

// 一层一层的递归计算,一直到只有最后一个根哈希值
let res: Vec<_>;
// Only compute in parallel if there is enough work to benefit it
if row.len() > 250 {
res = row.par_iter().map(|x| merkle_node_hash(&x.0, &x.1)).collect();
} else {
res = row.iter().map(|x| merkle_node_hash(&x.0, &x.1)).collect();
}
merkle_root(&res)
// 这里不用担心递归的深度,其一,比特币区块大小有限,限制了交易数量;其二,是因为Merkle tree是类似二叉树的结构,递归计算次数为log(n),即使n非常大,递归次数也很小。
}

/// Calculate merkle tree node hash
pub fn merkle_node_hash<T>(left: T, right: T) -> H256 where T: AsRef<H256> {
dhash256(&*concat(left, right)) //双SHA-256哈希运算
}

#[inline]
fn concat<T>(a: T, b: T) -> H512 where T: AsRef<H256> { //将2个哈希值并在一起
let mut result = H512::default();
result[0..32].copy_from_slice(&**a.as_ref());
result[32..64].copy_from_slice(&**b.as_ref());
result
}

Transaction

Rust实现版本定义如下:

pub struct Transaction {
pub version: i32, //协议版本,明确这笔交易参照的规则协议
pub inputs: Vec, //输入列表
pub outputs: Vec, //输出列表
pub lock_time: u32, //锁定时间
}

可以看到,交易中最重要的是输入列表和输出列表,说明这次比特币转账时比特币的来源和转账去向。

Rust版本实现输入列表定义:

pub struct TransactionInput {
pub previous_output: OutPoint, //上一笔交易输出
pub script_sig: Bytes, //解锁脚本
pub sequence: u32, //序列号
pub script_witness: Vec, //见证脚本
}

/** An outpoint - a combination of a transaction hash and an index n into its vout */
pub struct OutPoint {
pub hash: H256, //交易ID
pub index: u32, //输出索引,表明是交易中的第几个输出
}

上面这个OutPoint定义如何没有理解的话,可参考下图进行理解:

Rust版本实现输出列表定义:

pub struct TransactionOutput {
pub value: u64, //输出金额
pub script_pubkey: Bytes, //锁定脚本,对于一个比特币交易来说,交易本身是不用关心输出的地址,交易只需要关心锁定脚本,当使用的时候能使用正确的解锁脚本即可动用比特币。
}



声明:本文观点仅代表作者本人,不代表凤梨财经赞同或证实其观点描述。如若侵权,请联系我们删除文章。

凤梨小秘书(微信号:fenglicaijing)