2018-2019 前期任务(一):资料阅读&Python入门
资料原文地址:Dumbcoin – An educational python implementation of a bitcoin-like blockchain【本文详细解读了比特币的基础技术,实现了Python中类比特币区块链中的大部分概念。虽不是真正的区块链,但有助于对其技术的理解。】
————————CONTENTS————————
Requires# - pycryptodome (pycrypto for 3.6)# - numpy /scipy / matplotlib# - pandasimport hashlib #包含常见hash算法的标准库import random #生成随机数import string #字符串运算import json #文件格式处理import binascii #进制转换import numpy as np #数组操作import pandas as pd #此处用于创建数据框import pylab as pl #绘图import logging #日志输出%matplotlib inline #生成图像
hash函数和挖矿
这里展示了矿工挖矿的过程。此处方便起见,使用一轮SHA256哈希函数。在比特币中使用的是两轮SHA256算法。
该函数将任意长度的字符串转换为长度为64的十六进制固定长度字符串:
def sha256(message): return hashlib.sha256(message.encode('ascii')).hexdigest()
- digest()和hexdigest():
hashlib是涉及安全散列和消息摘要,提供多个不同的加密算法接口,如SHA1、SHA224、SHA256、SHA384、SHA512、MD5等。
其中,hash.digest()返回摘要,作为二进制数据字符串值;hash.hexdigest()返回摘要,作为十六进制数据字符串值。
如下代码:
import hashlibmd5 = hashlib.md5()md5.update("a".encode('utf-8'))print(u"digest返回的摘要:%s"% md5.digest())print(u"hexdigest返回的摘要:%s"% md5.hexdigest())
结果为:
digest返回的摘要:b'\x0c\xc1u\xb9\xc0\xf1\xb6\xa81\xc3\x99\xe2iw&a'hexdigest返回的摘要:0cc175b9c0f1b6a831c399e269772661
挖矿的过程可以描述为:给定一个任意字符串X,找到一个随机数nonce,使得hash(x + nonce)
产生一个以多个前导字符串开头的哈希值。
如下代码所示,我们将“挖掘”到一个nonce,使得消息“hello bitcoin”的哈希值与随机数nonce连接时,值至少含有两个前导字符:
message = 'hello bitcoin'for nonce in range(1000): digest = sha256(message + str(nonce)) if digest.startswith('11'): print('Found nonce = %d' % nonce) breakprint(sha256(message + str(nonce)))
运行结果为:
Found nonce = 32112c38d2fdb6ddaf32f371a390307ccc779cd92443b42c4b5c58fa548f63ed83
结果表示,当随机数为32时,能够产生以“11”开头的哈希值。
你规定的前导字符越多,就越难找到符合条件的nonce(平均而言)。在比特币中,这被称为挖矿的难度。比特币不需要前导字符,而是要求哈希值低于某个值,但思路与之类似。
因此,定义两个稍后会用到的函数,一个用来计算字符串的哈希值,另一个用来挖掘给定字符串的随机数nonce:
def dumb_hash(message): return sha256(message)def mine(message, difficulty=1): assert difficulty >= 1, "Difficulty of 0 is not possible" i = 0 prefix = '1' * difficulty while True: nonce = str(i) digest = dumb_hash(message + nonce) if digest.startswith(prefix): return nonce, i i += 1
输入字符串,将会返回一个随机数nonce,满足hash(string + nonce)
以规定难度的字符串开头。
根据这个,我们可以挖掘各种难度的随机数:
nonce, niters = mine('42', difficulty=1)print('Took %d iterations' % niters)nonce, niters = mine('42', difficulty=3)print('Took %d iterations' % niters)
运行结果为:
`Took 23 iterations Took 2272 iterations
由此可见,难度为3所需的迭代次数比难度为1要大得多。因此,难度控制了平均尝试次数
难度
对于每个难度级别为各种输入字符串挖掘一个符合条件的随机数(本例中使用50),并记录每个难度级别所需的平均迭代次数。
def random_string(length=10): return ''.join(random.choice(string.ascii_uppercase + string.digits) for _ in range(length))strings = [random_string() for i in range(50)]levels = range(1, 5)# An array of results with a row for each difficulty and a column for each test stringresults = pd.DataFrame(index=strings, columns=levels, dtype=np.int)results.fillna(value=0)#results = np.zeros((N_LEVELS, len(strings)), dtype=np.int)for level in levels: for s in strings: _, niters = mine(s, difficulty=level) results[level][s] = nitersresults.iloc[:5]
输出如下:
pl.figure(figsize=(10, 5))ax = pl.subplot(111)ax.set_title('Number of iterations to mine a nonce for various difficulty')results.plot.box(showfliers=False, ax=ax)ax.set_xlabel('Difficulty')ax.set_ylabel('Iterations')
钱包
在比特币中,钱包是公钥/私钥对,公钥用于接收交易,私钥用于消费。通过私钥签署交易,其他任何人使用我们的公钥验证签名。
在比特币中,钱包是一组多个公钥/私钥对,地址并不直接是公钥。这确保了隐私和安全性,但在这里,我们将使用单个秘钥并使用公钥作为地址。
import Cryptoimport Crypto.Randomfrom Crypto.Hash import SHAfrom Crypto.PublicKey import RSAfrom Crypto.Signature import PKCS1_v1_5class Wallet(object): def __init__(self): random_gen = Crypto.Random.new().read self._private_key = RSA.generate(1024, random_gen) self._public_key = self._private_key.publickey() self._signer = PKCS1_v1_5.new(self._private_key) @property def address(self): return binascii.hexlify(self._public_key.exportKey(format='DER')).decode('ascii') def sign(self, message): h = SHA.new(message.encode('utf8')) return binascii.hexlify(self._signer.sign(h)).decode('ascii')def verify_signature(wallet_address, message, signature): pubkey = RSA.importKey(binascii.unhexlify(wallet_address)) verifier = PKCS1_v1_5.new(pubkey) h = SHA.new(message.encode('utf8')) return verifier.verify(h, binascii.unhexlify(signature))functionality worksw1 = Wallet()signature = w1.sign('foobar')assert verify_signature(w1.address, 'foobar', signature)assert not verify_signature(w1.address, 'rogue message', signature)
交易
交易用来在钱包之间兑换货币,由以下内容组成:
- 一位消费者:对交易签名;花钱
- 许多输入:是其他交易的输出,收件人为消费者的钱包
- 许多输出:每个输出都指定了金额和收件人
交易还可以包含“交易费”,这是矿工将交易包括在一个区块中的激励。交易费是总投入金额和总输出金额之间的差值。
class TransactionInput(object): """ An input for a transaction. This points to an output of another transaction """ def __init__(self, transaction, output_index): self.transaction = transaction self.output_index = output_index assert 0 <= self.output_index < len(transaction.outputs) def to_dict(self): d = { 'transaction': self.transaction.hash(), 'output_index': self.output_index } return d @property def parent_output(self): return self.transaction.outputs[self.output_index]class TransactionOutput(object): """ An output for a transaction. This specifies an amount and a recipient (wallet) """ def __init__(self, recipient_address, amount): self.recipient = recipient_address self.amount = amount def to_dict(self): d = { 'recipient_address': self.recipient, 'amount': self.amount } return ddef compute_fee(inputs, outputs): """ Compute the transaction fee by computing the difference between total input and total output """ total_in = sum(i.transaction.outputs[i.output_index].amount for i in inputs) total_out = sum(o.amount for o in outputs) assert total_out <= total_in, "Invalid transaction with out(%f) > in(%f)" % (total_out, total_in) return total_in - total_outclass Transaction(object): def __init__(self, wallet, inputs, outputs): """ Create a transaction spending money from the provided wallet """ self.inputs = inputs self.outputs = outputs self.fee = compute_fee(inputs, outputs) self.signature = wallet.sign(json.dumps(self.to_dict(include_signature=False))) def to_dict(self, include_signature=True): d = { "inputs": list(map(TransactionInput.to_dict, self.inputs)), "outputs": list(map(TransactionOutput.to_dict, self.outputs)), "fee": self.fee } if include_signature: d["signature"] = self.signature return d def hash(self): return dumb_hash(json.dumps(self.to_dict()))class GenesisTransaction(Transaction): """ This is the first transaction which is a special transaction with no input and 25 bitcoins output """ def __init__(self, recipient_address, amount=25): self.inputs = [] self.outputs = [ TransactionOutput(recipient_address, amount) ] self.fee = 0 self.signature = 'genesis' def to_dict(self, include_signature=False): # TODO: Instead, should sign genesis transaction will well-known public key ? assert not include_signature, "Cannot include signature of genesis transaction" return super().to_dict(include_signature=False)
基于以上类,我们可以实现Alice和Bob之间的交易。
alice = Wallet()bob = Wallet()t1 = GenesisTransaction(alice.address)t2 = Transaction( alice, [TransactionInput(t1, 0)], [TransactionOutput(bob.address, 2.0), TransactionOutput(alice.address, 22.0)])assert np.abs(t2.fee - 1.0) < 1e-5
在比特币中,用户不会存储钱包中的金额;相反,将通过计算整条交易链条来计算拥有的钱数。下面的函数将实现这一点:
alice = Wallet()bob = Wallet()walter = Wallet()# This gives 25 coins to Alicet1 = GenesisTransaction(alice.address)# Of those 25, Alice will spend# Alice -- 5 --> Bob# -- 15 --> Alice# -- 5 --> Waltert2 = Transaction( alice, [TransactionInput(t1, 0)], [TransactionOutput(bob.address, 5.0), TransactionOutput(alice.address, 15.0), TransactionOutput(walter.address, 5.0)])# Walter -- 5 --> Bobt3 = Transaction( walter, [TransactionInput(t2, 2)], [TransactionOutput(bob.address, 5.0)])# Bob -- 8 --> Walter# -- 1 --> Bob# 1 feet4 = Transaction( bob, [TransactionInput(t2, 0), TransactionInput(t3, 0)], [TransactionOutput(walter.address, 8.0), TransactionOutput(bob.address, 1.0)])transactions = [t1, t2, t3, t4]
def compute_balance(wallet_address, transactions): """ Given an address and a list of transactions, computes the wallet balance of the address """ balance = 0 for t in transactions: # Subtract all the money that the address sent out for txin in t.inputs: if txin.parent_output.recipient == wallet_address: balance -= txin.parent_output.amount # Add all the money received by the address for txout in t.outputs: if txout.recipient == wallet_address: balance += txout.amount return balanceprint("Alice has %.02f dumbcoins" % compute_balance(alice.address, transactions))print("Bob has %.02f dumbcoins" % compute_balance(bob.address, transactions))print("Walter has %.02f dumbcoins" % compute_balance(walter.address, transactions))
运行结果为:
Alice has 15.00 dumbcoinsBob has 1.00 dumbcoinsWalter has 8.00 dumbcoins
除此之外,还需要验证交易是否有效,这意味着:
- 用户只能花自己的钱。这意味着检查所有输入是否由交易所有者拥有;
- 确保花费不会超过拥有的钱。这由上面的
compute_fee
函数检查。
def verify_transaction(transaction): """ Verify that the transaction is valid. We need to verify two things : - That all of the inputs of the transaction belong to the same wallet - That the transaction is signed by the owner of said wallet """ tx_message = json.dumps(transaction.to_dict(include_signature=False)) if isinstance(transaction, GenesisTransaction): # TODO: We should probably be more careful about validating genesis transactions return True # Verify input transactions for tx in transaction.inputs: if not verify_transaction(tx.transaction): logging.error("Invalid parent transaction") return False # Verify a single wallet owns all the inputs first_input_address = transaction.inputs[0].parent_output.recipient for txin in transaction.inputs[1:]: if txin.parent_output.recipient != first_input_address: logging.error( "Transaction inputs belong to multiple wallets (%s and %s)" % (txin.parent_output.recipient, first_input_address) ) return False if not verify_signature(first_input_address, tx_message, transaction.signature): logging.error("Invalid transaction signature, trying to spend someone else's money ?") return False # Call compute_fee here to trigger an assert if output sum is great than input sum. Without this, # a miner could put such an invalid transaction. compute_fee(transaction.inputs, transaction.outputs) return Truet1 = GenesisTransaction(alice.address)# This is an invalid transaction because bob is trying to spend alice's money# (alice was the recipient of the input - t1)t2 = Transaction( bob, [TransactionInput(t1, 0)], [TransactionOutput(walter.address, 10.0)])# This is valid, alice is spending her own moneyt3 = Transaction( alice, [TransactionInput(t1, 0)], [TransactionOutput(walter.address, 10.0)])
区块
现在我们有了:
- 定义钱包的方法(作为公私钥对)
- 在钱包之间创建交易的方法
- 验证交易的方法(通过检查签名是否匹配)
剩下的就是讲交易分组成块,并让矿工开采区块。挖矿包括两部分:
- 验证区块中的交易
- 查找一个nonce,使得区块的哈希值以0开头
此外,挖矿通过以下方式产生资金:区块中的第一个交易是GenesisTransaction,它为矿工选择的任何地址提供25个硬币。以同样的方式,矿工可以将费用从块中的交易重定向到他选择的任何地址。
BLOCK_INCENTIVE = 25 # The number of coins miners get for mining a blockDIFFICULTY = 2def compute_total_fee(transactions): """Return the total fee for the set of transactions""" return sum(t.fee for t in transactions)class Block(object): def __init__(self, transactions, ancestor, miner_address, skip_verif=False): """ Args: transactions: The list of transactions to include in the block ancestor: The previous block miner_address: The address of the miner's wallet. This is where the block incentive and the transactions fees will be deposited """ reward = compute_total_fee(transactions) + BLOCK_INCENTIVE self.transactions = [GenesisTransaction(miner_address, amount=reward)] + transactions self.ancestor = ancestor if not skip_verif: assert all(map(verify_transaction, transactions)) json_block = json.dumps(self.to_dict(include_hash=False)) self.nonce, _ = mine(json_block, DIFFICULTY) self.hash = dumb_hash(json_block + self.nonce) def fee(self): """Return transaction fee for this block""" return compute_total_fee(self.transactions) def to_dict(self, include_hash=True): d = { "transactions": list(map(Transaction.to_dict, self.transactions)), "previous_block": self.ancestor.hash, } if include_hash: d["nonce"] = self.nonce d["hash"] = self.hash return dclass GenesisBlock(Block): """ The genesis block is the first block in the chain. It is the only block with no ancestor """ def __init__(self, miner_address): super(GenesisBlock, self).__init__(transactions=[], ancestor=None, miner_address=miner_address) def to_dict(self, include_hash=True): d = { "transactions": [], "genesis_block": True, } if include_hash: d["nonce"] = self.nonce d["hash"] = self.hash return d
与验证交易信息的方式类似,我们还需要一种方法来验证区块:
def verify_block(block, genesis_block, used_outputs=None): """ Verifies that a block is valid : - Verifies the hash starts with the required amount of ones - Verifies that the same transaction output isn't used twice - Verifies all transactions are valid - Verifies the first transaction in the block is a genesis transaction with BLOCK_INCENTIVE + total_fee Args: block: The block to validate genesis_block: The genesis block (this needs to be shared by everybody. E.g. hardcoded somewhere) used_outputs: list of outputs used in transactions for all blocks above this one """ if used_outputs is None: used_outputs = set() # Verify hash prefix = '1' * DIFFICULTY if not block.hash.startswith(prefix): logging.error("Block hash (%s) doesn't start with prefix %s" % (block.hash, prefix)) return False if not all(map(verify_transaction, block.transactions)): return False # Verify that transactions in this block don't use already spent outputs # # Note that we could move this in verify_transaction, but this would require some passing the used_outputs # around more. So we do it here for simplicity for transaction in block.transactions: for i in transaction.inputs: if i.parent_output in used_outputs: logging.error("Transaction uses an already spent output : %s" % json.dumps(i.parent_output.to_dict())) return False used_outputs.add(i.parent_output) # Verify ancestors up to the genesis block if not (block.hash == genesis_block.hash): if not verify_block(block.ancestor, genesis_block, used_outputs): logging.error("Failed to validate ancestor block") return False # Verify the first transaction is the miner's reward tx0 = block.transactions[0] if not isinstance(tx0, GenesisTransaction): logging.error("Transaction 0 is not a GenesisTransaction") return False if not len(tx0.outputs) == 1: logging.error("Transactions 0 doesn't have exactly 1 output") return False reward = compute_total_fee(block.transactions[1:]) + BLOCK_INCENTIVE if not tx0.outputs[0].amount == reward: logging.error("Invalid amount in transaction 0 : %d, expected %d" % (tx0.outputs[0].amount, reward)) return False # Only the first transaction shall be a genesis for i, tx in enumerate(block.transactions): if i == 0: if not isinstance(tx, GenesisTransaction): logging.error("Non-genesis transaction at index 0") return False elif isinstance(tx, GenesisTransaction): logging.error("GenesisTransaction (hash=%s) at index %d != 0", tx.hash(), i) return False return True
alice = Wallet()bob = Wallet()walter = Wallet()genesis_block = GenesisBlock(miner_address=alice.address)print("genesis_block : " + genesis_block.hash + " with fee=" + str(genesis_block.fee()))t1 = genesis_block.transactions[0]t2 = Transaction( alice, [TransactionInput(t1, 0)], [TransactionOutput(bob.address, 5.0), TransactionOutput(alice.address, 15.0), TransactionOutput(walter.address, 5.0)])t3 = Transaction( walter, [TransactionInput(t2, 2)], [TransactionOutput(bob.address, 5.0)])t4 = Transaction( bob, [TransactionInput(t2, 0), TransactionInput(t3, 0)], [TransactionOutput(walter.address, 8.0), TransactionOutput(bob.address, 1.0)])block1 = Block([t2], ancestor=genesis_block, miner_address=walter.address)print("block1 : " + block1.hash + " with fee=" + str(block1.fee()))block2 = Block([t3, t4], ancestor=block1, miner_address=walter.address)print("block2 : " + block2.hash + " with fee=" + str(block2.fee()))
输出:
genesis_block : 1162dce8ffec3acf13ce61109f121922eee8cceeea4784aa9d90dc6ec0e0fa92 with fee=0block1 : 11af277c02c22a7e3c3a73102282ca5a0e01869b1d852527b6a842f0786ee8e3 with fee=0.0block2 : 119e461d393b793478c7c7cb9fa6feb54fca35865a398d017e541027a78a2e9a with fee=1.0
def collect_transactions(block, genesis_block): """Recursively collect transactions in `block` and all of its ancestors""" # Important : COPY block.transactions transactions = [] + block.transactions if block.hash != genesis_block.hash: transactions += collect_transactions(block.ancestor, genesis_block) return transactionstransactions = collect_transactions(block2, genesis_block)# Alice mined 25 (from the genesis block) and gave 5 to bob and 5 to walterprint("Alice has %.02f dumbcoins" % compute_balance(alice.address, transactions))# Bob received 5 from alice and 5 from walter, but then back 8 to walter with a transaction fee of 1print("Bob has %.02f dumbcoins" % compute_balance(bob.address, transactions))# Walter mined 2 blocks (2 * 25), received 8 from bob and go a transaction fee of 1 on block2print("Walter has %.02f dumbcoins" % compute_balance(walter.address, transactions))
输出:
Alice has 15.00 dumbcoinsBob has 1.00 dumbcoinsWalter has 59.00 dumbcoins
攻击
参考资料
- 廖雪峰官方网站-Python教程
- Python中hashlib模块
- python之binascii模块
- Python数据分析之numpy学习
- Python关于%matplotlib inline
- matplotlib绘图实例:pyplot、pylab模块及作图参数
- 【python笔记】使用matplotlib,pylab进行python绘图
- python3_matplotlib_figure()函数解析