2021年618京享红包 - 618大促主会场
九阳 Joyoung电磁炉 电陶炉 2200W大功率 家用火锅套装 旋转控温 红外光波加热 H22-x3 赠烤盘
凯迪仕电子锁618狂欢购
有健康 更热爱
美丽雅品牌会员周

区块链-公有链 原

终遇你 1年前   阅读数 70 0

前言

       这是我在华南农业大学读研期间抽空整理出来的有关区块链-公有链知识点笔记,仅进行一个简单的技术科普,不涉及零知识证明(NIZK、zk-SNARKs),想要真正了解零知识证明,推荐读研深造。

UTXO

       什么是UTXO?即Unspent Transaction Output。区块链为了实现数据可溯源,会在链中详细记录每一笔Transaction(TX),它长下面这个样子,详细地记录了多少数量的资源从哪里流向哪里

       例如在制酒供应链,Alice向Bob供应了2瓶酒。之后Bob为了向Christal供应1瓶酒,首先他需要在链中找到这笔TX_1,并证明这笔TX_1的有效性,然后生成TX_2记录Bob向Christal供应了1瓶酒,生成TX_3记录Bob向自己供应了1瓶酒,最后在账本链中销毁TX_1。

Merkle树

       怎样保证所有TX记录没有被篡改过呢?用Merkle树来校验;怎样证明某一笔TX的有效性呢?用Merkle树来校验。举一个例子,在下图中为了证明L2的有效性,我们将图中圈绿色的节点发送给校验方。

       那么默克尔树怎样动态增加节点,原理如下图,为了插入橘黄色点,我们从左到右依次记录紫色点,然后更新紫色点路径上的父节点,这样就不会破坏原本的树结构。

       我这里贴出1份自己写的python代码,1个node就是1条数据库记录,思路借鉴于https://github.com/jvsteiner/merkletree

#!/usr/bin/python3
#coding=utf-8
#author: Qingwen Guo, South China Agricultural University

from hashlib import *
from math import log


# 全局定义Hash函数的形式
def hash_function(string):
    string = string.encode('utf-8')
    return sha256(string).hexdigest()


# 默克尔树中的节点
class Node:
    __slots__ = ['lchild', 'rchild', 'parent', 'sibling', 'side', 'value']

    def __init__(self, string):
        self.value = hash_function(string)
        self.lchild = None
        self.rchild = None
        self.parent = None
        self.sibling = None
        self.side = None

    def __repr__(self):
        return self.value


class MerkleTree:
    __slots__ = ['leaves', 'root']

    def __init__(self, strings=[]):
        self.leaves = [Node(string) for string in strings]
        self.root = None

    def build(self):
        if (not self.leaves) or (len(self.leaves) == 0):
            return False
        layer = self.leaves[::]
        while len(layer) != 1:
            layer = self._build(layer)
        self.root = layer[0]
        return True

    def _build(self, layer):
        res, temp = [], None
        if len(layer) % 2 != 0:
            temp = layer.pop(-1)
        for i in range(0, len(layer), 2):
            string = str(layer[i].value) + str(layer[i+1].value)
            node = Node(string)
            node.lchild, node.rchild = layer[i], layer[i+1]
            layer[i].parent, layer[i+1].parent = (node, ) * 2
            layer[i].sibling, layer[i].side, layer[i+1].sibling, layer[i+1].side = layer[i+1], 'L', layer[i], 'R'
            res.append(node)
        if temp:
            res.append(temp)
        return res

    def _get_add_path(self):
        res = []
        node = self.root
        rest_leaves = len(self.leaves)
        if rest_leaves != 0:
            while True:
                rest_leaves = rest_leaves - 2 ** int(log(rest_leaves, 2))
                if rest_leaves == 0:
                    break
                res.append(node.lchild)
                node = node.rchild
        # 若是空树,则不添加任何节点进路径
        if node:
            res.append(node)
        return res

    def add(self, string):
        node = Node(string)
        path = self._get_add_path()
        # 若列表path不存在节点,则直接以node为根节点
        if len(path) == 0:
            self.root = node
        # 若列表path仅有根节点
        elif len(path) == 1:
            p = path.pop(-1)
            string = str(p.value) + str(node.value)
            self.root = Node(string)
            self.root.lchild, self.root.rchild = p, node
            p.parent, node.parent = (self.root, ) * 2
            p.sibling, p.side, node.sibling, node.side = node, 'L', p, 'R'
        else:
            if path[-1].sibling == path[-2]:
                p = path.pop(-1)
                string = str(p.value) + str(node.value)
                new_node = Node(string)
                new_node.lchild, new_node.rchild = p, node
                p.parent, node.parent = (new_node, ) * 2
                p.sibling, p.side, node.sibling, node.side = node, 'L', p, 'R'
                node = new_node
            while len(path) != 0:
                p = path.pop(-1)
                string = str(p.value) + str(node.value)
                p.parent.value = hash_function(string)
                p.parent.rchild = node
                node.parent = p.parent
                p.sibling, p.side, node.sibling, node.side = node, 'L', p, 'R'
                node = node.parent
        self.leaves.append(node)

    def get_chain(self, i):
        res = []
        if 0 <= i and i <= len(self.leaves):
            node = self.leaves[i]
            while node != self.root:
                res.append((node.sibling.value, node.sibling.side))
                node = node.parent
        return res

    def check_chain(self, chain, string):
        res = hash_function(string)
        for v in chain:
            if v[1] == 'L':
                res = hash_function(v[0] + res)
            elif v[1] == 'R':
                res = hash_function(res + v[0])
            else:
                return False
        return res == self.root.value

    def clear(self):
        self.root = None
        for leaf in self.leaves:
            leaf.parent, leaf.sibling, leaf.side, leaf.value = (None, ) * 4


letters = "abcdefghijklmnopqrstuvwxyz"


for i in range(1, len(letters)+1):
    tree = MerkleTree([c for c in letters[:i]])
    tree.build()
    test1 = tree.root.value
    
    tree = MerkleTree()
    for c in letters[:i]:
        tree.add(c)
    test2 = tree.root.value

    if test1 != test2:
        print("Build Error!")


for i in range(1, len(letters)+1):
    tree1 = MerkleTree([c for c in letters[:i]])
    tree1.build()

    tree2 = MerkleTree([c for c in letters[:i]])
    tree2.build()

    for j in range(0, i):
        chain = tree1.get_chain(j)

        if not tree2.check_chain(chain, letters[j]):
            print("Chain Error!")

双花交易

       怎样防止一笔TX被多次使用,这需要每个记账节点维护一个UTXO交易池,记录哪些TX仍然有效。

工作量证明PoW

       为什么需要挖矿算法?这篇文章给出了一个很好的例子,本篇我重新塑造一个业务场景以更好地说明其作用。在制酒供应链中,若Bob提供给Christal的酒掺水了,监管部门对Bob进行问责时,Bob有可能重新伪造1条足够长的链并谎称这酒不是来自他,抵赖说其他人的账本链遭到了黑客篡改。幸运的是,挖矿算法能够有效针对这种无赖行为,因为Bob即使向重新造一条新链,凭他的算力怎么也赶不上最长链,而大家仅仅只承认最长链的有效性。

私有链与联盟链

       尽管公有链的挖矿算法很有用,但到了私有链和联盟链就显得很累赘了,因为实操起来很慢,又极度浪费资源。为了解决该问题,我们需要找到一种更好的办法。什么办法?想一想,与Hash算法相对应的算法是什么?没错,就是数字签名(Digital Signature)

       网络中每个记账节点以自签名证书的方式公布自己的(PkSk),节点记账时用自己的Sk 签名,资源流动时大家用相应的Pk 进行有效性校验。由于Bob没有下一个记账权节点的Sk,也就卡住无法造成更长的账本链了。当然,这仅仅只是工程上的一个小技巧,如果想要了解以太坊(Ethereum Blockchain)的零知识证明(NIZK、zk-SNARKs)技术,则推荐读研深造。

后记

       最后用清华大学老校歌里的一句“器识为先,文艺其从;立德立言,无问西东”结束。

Reference

A Python implementation of the Merkle/Hash Tree Algorithm

POW和POS机制究竟是什么?


注意:本文归作者所有,未经作者允许,不得转载

全部评论: 0

    我有话说: