2018年4月16日星期一

# 阅读 go-ethereum 源码 - 5

dagger.go (Dagger工作量证明 )

Ethash 是 Ethereum 的PoW(工作量证明)算法。 该算法需要大量的数据集合,该集合被称为DAG. Ethash 算法由Dagger-Hashimoto 算法改进而得,Dagger Hashimoto是Ethereum 1.0 挖矿算法的推荐规范 。 
Dagger Hashimoto 基于已经存在的关键算法:Hashimoto 和 Dagger。 
在go-ethereum 提交记录 9f133a92d0853102863b77dd7c884d1462cf73a4 中,第一次提交了dagger的实现。 
commit 9f133a92d0853102863b77dd7c884d1462cf73a4 (HEAD)
Author: obscuren <geffobscura@gmail.com>
Date:   Wed Jan 8 23:41:03 2014 +0100

    First dagger impl

Dagger 工作量证明

Dagger的文档可以在 https://github.com/ethereum/wiki/blob/master/Dagger.md查看。
Dagger,由Vitalik Buterin提供的一种算法(January 2014),Dagger命名来自于“directed acyclic graph”(DAG),DAG(有向无环图)是dagger算法的数学结构。 该算法的主要实现内存困难的计算(memory-hard computation ),但内存容易的验证(memory-easy validation)。 简单来说计算需要大量的内存,而验证则只需要少量的内存。 
核心原则是每个随机数只需要大数据树中的一小部分,对于挖矿程序来说,重新计算每个随机数的子树是禁止的 ,所以矿工节点需要因此需要存储树 。但对于单一随机数的验证来说则没有问题。 Dagger本意是替代现有的内存困难算法,如Scrypt,该算法计是内存困难的,但当增加到真正的安全级别时,也很难验证。 
然而,Dagger 算法被Sergio Lerner证明存在缺陷(可以共享内存,并 导致可硬件加速,无法抵抗ASIC)。随后Ethereum POW逐步演化为 Dagger -> Dagger-Hashimoto -> Ethash 。

算法定义


D(data,xn,0) = sha3(data)
D(data,xn,n) =
    with v = sha3(data + xn + n)
         L = 2 if n < 2^21 else 11 if n < 2^22 else 3
         a[k] = floor(v/n^k) mod n for 0 <= k < 2
         a[k] = floor(v/n^k) mod 2^22 for 2 <= k < L
    sha3(v ++ D(data,xn,a[0]) ++ D(data,xn,a[1]) ++ ... ++ D(data,xn,a[L-1]))
  • Dagger 创建了一个有向非循环图(DAG),总计有2**32 -1 = 8388607 个节点。
  • 每个节点依赖于前面的3-15个随机的节点
  • 如果找到 2**22 至 2**23 见的一个节点的hash值 小于 2**256/diff ,则得到了工作量证明。 (diff 为难度值)

代码


type Dagger struct {
    hash *big.Int
    xn   *big.Int
}

func (dag *Dagger) Search(diff *big.Int) *big.Int 

func (dag *Dagger) Node(L uint64, i uint64) *big.Int

func (dag *Dagger) Eval(N *big.Int) *big.Int
  • Search 方法为寻找到制定难度 (diff)的 随机值
  • Eval 方法即为算法定义中的函数D 
  • Node 方法为计算DAG中的节点数据 
本地提交代码无法运行,所以我们使用测试通过的提交ba385ccdf15f8379c54d65061c3d62353baffc2b

git checkout ba385ccdf15f8379c54d65061c3d62353baffc2b
运行测试:
go test -bench=BenchmarkDaggerSearch
输出:goos: darwin goarch: amd64 pkg: go-ethereum BenchmarkDaggerSearch-4 1 1714457872 ns/op PASS ok go-ethereum 1.896s
发现使用该算法,难度2**36 时,每次查找时间约为1.8秒。
Share:

2018年4月10日星期二

阅读 go-ethereum 源码 - 4

Trie.go (Merkle-patricia-tree )

Merkle Patricia Tree(简称MPT树,实际上是一种trie前缀树)是以太坊中的一种加密认证的数据结构,可以用来存储所有的(key,value)对。
以太坊区块链中的区块由标题,交易列表和叔区块列表组成。区块头中包含交易的根哈希,它用于验证交易列表。在区块头部包括了交易的hash树根,用来校验交易的列表。在p2p网络上传输的交易是一个简单的列表,它们被组装成一个叫做trie树的特殊数据结构,来计算根hash。值得注意的是,除了校验区块外,这个数据结构并不是必须的,一旦区块被验证正确,那么它在技术上是可以忽略的。但是,这意味着交易列表在本地以trie树的形式存储,发送给客户端的时候序列化成列表。客户端接收到交易列表后重新构建交易列表trie树来验证根hash。RLP(Recursive length prefix encoding,递归长度前缀编码),用来对trie树种所有的条目进行编码。对RLP的介绍和源码实现阅读可参考阅读 go-ethereum 源码 - 2 
Merkle Patricia Tree的Wiki可在https://github.com/ethereum/wiki/wiki/Patricia-Tree查看。
go-ethereum源码中对MPT数的处理时在文件 **trie.go **中。 进入go-ethereum 源码查看trie.go .
git checkout 9f133a92d0853102863b77dd7c884d1462cf73a4

或通过如下方式在线浏览:

https://github.com/ethereum/go-ethereum/blob/9f133a92d0853102863b77dd7c884d1462cf73a4/trie.go
注意:
在MPT的wiki中制定,树的Merkle部分是一个节点的确定性加密的hash。 该hash 为 rlp编码的value值的sha3. 
The "Merkle" part of the radix trie arises in the fact that a deterministic cryptographic hash of a node is used as the pointer to the node (for every lookup in the key/value DB key == sha3(rlp(value)), rather than some 32-bit or 64-bit memory location as might happen in a more traditional trie implemented in C. 
但在go-ethereum的早期代码中,该hash实现为sha256。所以源码中间的计算结果会不同于wiki。在后续的实现中,go-ethereum 将会改为sha3 。
// Wrapper around the regular db "Put" which generates a key and value
func (t *Trie) Put(node interface{}) []byte {
    enc := Encode(node)     //RLP 编码
    sha := Sha256Bin(enc)   //sha256

    t.db.Put([]byte(sha), enc)

    return sha
}

HP编码

在以太坊(ethereum)中,使用了一种特殊的十六进制前缀(hex-prefix, HP)编码,所以在字母表中就有16个字符。这其中的一个字符为一个nibble。
我们用'\x01\x01\x02'做为key,'hello'作为值存入到trie树中。trie树将将创建一个新的叶节点。并将[hash, rlp(node)]存储在数据库中。 
" \x01\x01\x02" hp编码为20010102 。 k编码中后6位为010102,开头两位20为HP编码前缀。第一位2是字符串的标志位,用二进制的表示为0b10. 
  • 二进制最后一位表示key的长度是否为偶数(0,1,0,1,0,2),设为0
  • 二进制第一位表示是否终止(终止为1)
0b00 + 0b10 = 0b10 = byte(2)
HP编码后需要为偶数,所以2后再补充一字节 0 ,最终变为[2,0,0,1,0,1,0,2]
相关编码解码的实现在源码 encoding.go 中。 
相关例子说明:
> [ 1, 2, 3, 4, 5, ...]
'11 23 45'  //非终止,奇数。 补充1字节前缀  0b01=1
> [ 0, 1, 2, 3, 4, 5, ...]
'00 01 23 45' //非终止,偶数。 补充2字节前缀  0b00,00 
> [ 0, f, 1, c, b, 8, 10]
'20 0f 1c b8' //终止,奇数。 补充1字节前缀  0b10=2
> [ f, 1, c, b, 8, 10]
'20 f1 cb 8a' //终止,偶数。 补充2字节前缀  0b10=2, 0 

MPT中存储内容结构展示

编写一个简单的展示树结构的代码:

func printNode(root string, n []byte, trie *Trie, intent int) {

    tip := ""
    for i := 0; i < intent; i++ {
        tip += " "
    }
    fmt.Printf(tip+"node hash: %s \n", hex.EncodeToString([]byte(root)))
    // Decode it
    currentNode := DecodeNode(n)

    if len(currentNode) == 0 {
        fmt.Printf(tip+"node valu: %v \n", currentNode)

    } else if len(currentNode) == 2 {
        // Decode the key
        k := CompactDecode(currentNode[0])
        v := currentNode[1]

        length := len(k)
        if length == 0 || k[length-1] == 16 {
            //终止
            fmt.Printf(tip+"node valu: %v %v\n", k, v)
        } else {
            //非终止,v = next node hash
            fmt.Printf(tip+"node valu: %v %s\n", k, hex.EncodeToString([]byte(v)))
            n, err := trie.db.Get([]byte(v))

            if nil == err {
                printNode(v, n, trie, intent+1)
            }

        }

    } else if len(currentNode) == 17 {

        fmt.Printf(tip + "node swch:")
        printSwitchNode(currentNode, trie, intent)
    }

}

func printSwitchNode(slice []string, trie *Trie, intent int) {
    fmt.Printf("[")
    for i, val := range slice {
        //fmt.Printf("%q", val)

        if i != len(slice)-1 {
            fmt.Printf("%s", hex.EncodeToString([]byte(val)))
            fmt.Printf(",")
        } else {
            fmt.Printf("%v", val)
        }
    }
    fmt.Printf("]\n")

    for i, val := range slice {
        //fmt.Printf("%q", val)
        if i != len(slice)-1 {
            if val != "" {
                //下个节点hash
                n, err := trie.db.Get([]byte(val))

                if nil == err {
                    printNode(val, n, trie, intent+1)
                }
            }
        }
    }
}
trie.go的单元测试代码写在trie_test.go 中,我们加入一个新的测试用例。
编写一个测试用例:
func TestTrieUpdate2(t *testing.T) {

    db, err := NewMemDatabase()
    trie := NewTrie(db, "")

    if err != nil {
        t.Error("Error starting db")
    }

    //树中加入<64 6f> ‘do' : 'verb'
    trie.Update("do", "verb")
    n, _ := trie.db.Get([]byte(trie.root))
    printNode(trie.root, n, trie, 0)

}
执行测试: go test -run TestTrieUpdate2 输出为:
node hash: 40974ec0af4f0e1d466b3e0c6eb8e8c6cb99aa2a349c23b268a5cf65b6221782 
node valu: [6 4 6 15 16] verb
树中再次加入:trie.Update("dog", "puppy")
输出:
node hash: f7ea383e3a2acd742393382c3d5836cf7379b45dbfbc35cd7076001d3bdf51b7 
node valu: [6 4 6 15] 80b3283481f857ad774e1d932cad83a9b1433de221ec468a63cae62eda2a7217
 node hash: 80b3283481f857ad774e1d932cad83a9b1433de221ec468a63cae62eda2a7217 
 node swch:[,,,,,,9aa7cda514c3d6a2b65947dd8fa85f244d037f4572bd22984057a3e345597955,,,,,,,,,,verb]
  node hash: 9aa7cda514c3d6a2b65947dd8fa85f244d037f4572bd22984057a3e345597955 
  node valu: [7 16] puppy
加入: trie.Update("doge", "coin")
输出:
node hash: ca34cb14ee0fb6b039e2c26189442b7dd2f2c1cd575cc896ee49e77108e9e6eb 
node valu: [6 4 6 15] 2a937541cb3a17823d0a2f7adf9d8b355a5240ef99046e0d3485076320b41d7a
 node hash: 2a937541cb3a17823d0a2f7adf9d8b355a5240ef99046e0d3485076320b41d7a 
 node swch:[,,,,,,552cf872957cc9cbf82a53e5b89f37f867685d28105acebba60a03ac7f321147,,,,,,,,,,verb]
  node hash: 552cf872957cc9cbf82a53e5b89f37f867685d28105acebba60a03ac7f321147 
  node valu: [7] da821f38c5d331e760a88ae3a14a42c70618463d4509ff0822ad7014e7b388f0
   node hash: da821f38c5d331e760a88ae3a14a42c70618463d4509ff0822ad7014e7b388f0 
   node swch:[,,,,,,31ffd3d3e73ef63a36f6aaf751e53d8171605db7e13b15cf8525df259739d389,,,,,,,,,,puppy]
    node hash: 31ffd3d3e73ef63a36f6aaf751e53d8171605db7e13b15cf8525df259739d389 
    node valu: [5 16] coin
加入: trie.Update("horse", "stallion")
输出:
node hash: 6529010d2a2f633bfe03e7a3a3503e5a5bccd1ca49989ac0fb195fd022c6cc93 
node valu: [6] 81a164dfe985a4a6f330883c8c713ca48f06976779a0f9fcf43cfe2f2d8872a5
 node hash: 81a164dfe985a4a6f330883c8c713ca48f06976779a0f9fcf43cfe2f2d8872a5 
 node swch:[,,,,7e627874d222eb965ce0bfd13ef518392bc1c39020afb48a5024f1693449e6ad,,,,94c7c69112a354b2beba2f82c4e53f18aface66280be4ea1dd3f778a7917a373,,,,,,,,]
  node hash: 7e627874d222eb965ce0bfd13ef518392bc1c39020afb48a5024f1693449e6ad 
  node valu: [6 15] 2a937541cb3a17823d0a2f7adf9d8b355a5240ef99046e0d3485076320b41d7a
   node hash: 2a937541cb3a17823d0a2f7adf9d8b355a5240ef99046e0d3485076320b41d7a 
   node swch:[,,,,,,552cf872957cc9cbf82a53e5b89f37f867685d28105acebba60a03ac7f321147,,,,,,,,,,verb]
    node hash: 552cf872957cc9cbf82a53e5b89f37f867685d28105acebba60a03ac7f321147 
    node valu: [7] da821f38c5d331e760a88ae3a14a42c70618463d4509ff0822ad7014e7b388f0
     node hash: da821f38c5d331e760a88ae3a14a42c70618463d4509ff0822ad7014e7b388f0 
     node swch:[,,,,,,31ffd3d3e73ef63a36f6aaf751e53d8171605db7e13b15cf8525df259739d389,,,,,,,,,,puppy]
      node hash: 31ffd3d3e73ef63a36f6aaf751e53d8171605db7e13b15cf8525df259739d389 
      node valu: [5 16] coin
  node hash: 94c7c69112a354b2beba2f82c4e53f18aface66280be4ea1dd3f778a7917a373 
  node valu: [6 15 7 2 7 3 6 5 16] stallion
简化显示为:
node hash: hash1 
node valu: [6] hash2
 node hash: hash2 
 node swch:[,,,,hash3,,,,hash4,,,,,,,,]
  node hash: hash3 
  node valu: [6 15] hash5
   node hash: hash5 
   node swch:[,,,,,,hash6,,,,,,,,,,verb]
    node hash: hash6 
    node valu: [7] hash7
     node hash: hash7 
     node swch:[,,,,,,hash8,,,,,,,,,,puppy]
      node hash: hash8 
      node valu: [5 16] coin
  node hash: hash4 
  node valu: [6 15 7 2 7 3 6 5 16] stallion
  
var hashNum int64 = 0
var hashMap = make(map[string]string)

func clearSimpleHash() {
    hashNum = 0
    hashMap = make(map[string]string)
}
func simpleHash(hash string) string {
    if h, ok := hashMap[hash]; ok {
        return h
    }
    hashNum += 1
    nhash := "hash" + strconv.FormatInt(hashNum, 10)
    hashMap[hash] = nhash
    return nhash
}
Share:

2018年3月30日星期五

阅读 go-ethereum 源码 - 3


从初始代码提交到commit ad048e9f445ff96b7bfd75c104ab923e1e06754b,go-ethereum的结构&功能变化不大。主要变化有:
  • 将rlp编解码移动到 rlp.go文件中
  • 完善 transaction、block的rlp编解码
到了commit a926686445929d091c2d9e019b017600168e9e47,源码中出现了较大的功能加入。
Added sample server, genesis block, and database interface
但是本次提交出现,无法编译通过。错误为:
./database.go:65: cannot use k (type []int) as type string in function argument
所以迁出下一次提交 并逐一分析源码、功能。
git checkout f17930eb4661721cd0e1b92765448c589441907b

或在线浏览:

https://github.com/ethereum/go-ethereum/tree/f17930eb4661721cd0e1b92765448c589441907b

新增功能代码

server.go
实现客户端运行的主要框架。
  1. for循环实现始终运行
  2. db 实现数据的本地操作
  3. peers ,能够获取到其他客户端的连接。存储客户端列表。
type Server struct {
  // Channel for shutting down the server
  shutdownChan chan bool
  // DB interface
  db          *LDBDatabase
  // Peers (NYI)
  peers       *list.List
}
database.go
使用google的leveldb本地存储数据,这次提交中方法未完全实现。主要的功能就是CRUD,数据的增删查改。
trie.go
根据名称应该是数据结构前缀树或字典树的实现,主要功能也未实现。 
encoding.go
该文件并不是新提交的,主要功能是实现十六进制数的紧凑编码。并添加可选的是否终止的符号。 
Compact encoding of hex sequence with optional terminator
了解一下其实现。

CompactEncode 紧凑编码

传统的十六进制字符串的编码,一般是将十六进制字符串转为二进制数组。比如'0f1248'将会转换为[15,18,73]3字节的二进制数组。 但这通常会导致一个问题,如将[15,18,73]解码为十六进制字符串时,应该解码为’0f1248‘ 还是 'f1248'。该方法无法确定是否需要前面的0.
第二个问题,在Ethereum的数据结构Merkle Patricia tree中,需要十六进制字符串可以带一个可选的是否终止符号(常量 16),该终止标志仅出现一次,且在字符串最后。
为了同时解决如上两个问题,ethereum设计了CompactEncode编码。其实现的核心算法为:
将十六进制字符串当做字节数组。 根据数组的长度,在数组前增加1字节或2字节的前缀。 然后将连续两个字节的数值合并为一个字节(即:第一个字节作为前4bit,第二个字节当做后4bit。因数组中最大值为0xf,所以不会产生越界)。

前缀的个数

如果数组为基数,则添加1字节前缀。如果为偶数,则添加2字节(第2字节为0)。

前缀的内容

前缀主要用来表示两个内容:
  • 该字符串是否终止
  • 该字符串长度是否为奇数
该实现基于位操作:1byte =8bit(0000 0000)。最后一个bit表示是否奇数(0为偶数、1为奇数)。倒数第二个自己表示是否终止。
oddlen := len(hexSlice) % 2
flags := 2 * terminator + oddlen

编码实现

将连续两个字节的数值合并为一个字节(即:第一个字节作为前4bit,第二个字节当做后4bit) ``` var buff bytes.Buffer for i := 0; i < len(hexSlice); i+=2 { buff.WriteByte(byte(16 * hexSlice[i] + hexSlice[i+1])) }
return buff.String() ```

实例

如 [ 1, 2, 3, 4, 5 ]
长度为基数,无终止标志(16)。所以增加前缀一个字节。
该字节内容为: flags = 2 * 0 + 1 = 1 
数组变为:[1,1,2,3,4,5] 。
编码[1*16+1,2*16+3,4*16+5] = [17,35,69]=[0x11,0x23,0x45]
[ 0, 1, 2, 3, 4, 5 ]
长度偶数,无终止标志。 需要增加两个字节,
则: flags= 2 * 0 + 0 = 0
数组变为:[0,0 , 0, 1, 2, 3, 4, 5 ]
编码:[0*16+0, 0*16+1,2*16+3,4*16+5] = [0,1,35,69] = [0x00,0x01,0x23,0x45]
[ 0, 15, 1, 12, 11, 8, 16 ]
编码为: '\x20\x0f\x1c\xb8'
[ 15, 1, 12, 11, 8, 16 ]
编码为: '\x3f\x1c\xb8'

解码则为编码的反过程

略过

总结

本次主要分析了 CompactEncode 的实现。 database、trie、server因无具体实现。则等待稍后分析。

Share:

2018年3月26日星期一

阅读 go-ethereum 源码 - 2


RLP(递归长度前缀)的目的是编码任意嵌套的二进制数据数组,RLP是以太坊中用于序列化对象的主要编码方法。 RLP的唯一目的是编码结构; 对于编码的数据的具体类型(例如字符串,浮点数)则留给高阶协议自己负责处理。(简单来说编码的二进制数据,代表的是字符串、浮点数还是其他类型。由使用该编码的高级协议定义);RLP编码的整数必须以大端二进制形式(big endian)表示,且不包含前导零(整数值零等于空字节数组)。 反序列化正整数时如发现前缀有零的必须视为无效。 字符串长度的整数表示也必须以这种方式进行编码,其他部分的整数同样如此。 更多信息可以在Ethereum黄皮书 附录B中找到。
如果有人希望使用RLP对字典进行编码,有两个建议
  1. 按照字典顺序使用[[k1,v1],[k2,v2]...]进行编码
  2. 或者使用更高级别的Patricia Tree编码

定义(编码)

RLP编码功能需要一个项(item)。 一个项(item)定义如下:
  • 一个字符串(即字节数组)是一个item
  • 项目列表(a list of item )也是一个项item
例如,空字符串是一个item,包含单词“cat”的字符串也是item,包含任意数量字符串的列表以及更复杂的数据结构也是item,如["cat",["puppy","cow"],"horse",[[]],"pig",[""],"sheep"] 。 请注意,在本文其余部分的上下文中,“string”将用作“一定数量的二进制数据字节数”的同义词; 没有使用特殊的编码,也没有关于字符串内容的知识。
在Python2 和 Golang 中,string都被定义为二进制数组,数据的保存全为二进制。如需要展示为特定格式的编码字符时,需要指定编解码格式。
RLP编码定义如下:
  • 对于其值在[0x00, 0x7f]范围内的单个字节,该字节是其自己的RLP编码。
  • 如果一个字符串的长度为0-55字节,则RLP编码由一个值为0x80的单个字节加上 该字符串后面的字符串长度组成。 第一个字节的范围是[0x80, 0xb7]([0x80,0x80+55=0xb7]) 。
  • 如果一个字符串长度超过55个字节,则RLP编码由一个值为0xb7的单个字节加上以二进制形式表示的字符串长度的字节长度,接着是字符串长度,后跟字符串。 例如,长度为1024的字符串将被编码为\xb9\x04\x00后跟该字符串。 第一个字节的范围是[0xb8, 0xbf] 。(1024如何被编码查看下方代码)
  • 如果编码的为列表(list/array),其长度为0-55字节(列表保存的是,所有被RLP编码的二进制数据),则RLP编码由单个字节组成,其值为0xc0加上列表的长度,然后连接项目的RLP编码。 第一个字节的范围是0xc0, 0xf7 
  • 如果列表的总长度超过55个字节,则RLP编码由一个值为0xf7的单个字节加上以二进制形式表示的有效长度的字节长度,接着是RLP编码的列表。 第一个字节的范围是[0xf8, 0xff](表示后面最多跟随8字节表示长度的内容),列表的长度最多为2**64次方 。
python代码如下:
def rlp_encode(input):
    if isinstance(input,str):
        if len(input) == 1 and ord(input) < 0x80: return input
        else: return encode_length(len(input), 0x80) + input
    elif isinstance(input,list):
        output = ''
        for item in input: output += rlp_encode(item)
        return encode_length(len(output), 0xc0) + output

def encode_length(L,offset):
    if L < 56:
         return chr(L + offset)
    elif L < 256**8:
         BL = to_binary(L)
         return chr(len(BL) + offset + 55) + BL
    else:
         raise Exception("input too long")

def to_binary(x):
    if x == 0:
        return ''
    else: 
        return to_binary(int(x / 256)) + chr(x % 256)
Golang 代码如下:
在commit 5db3335dce766bd679c54ea44f6df08a7ff74762 初始提交中,rlp的编码代码在serialization.go文件中。其代码暂未支持整数编码。观察代码RLP的实现与如今的RLP规范定义的不大一致。所以我们选取后续的提交。 
在commit d7eca7bcc12e940f0aa80d45e6e802ba68143b5c 中,rlp编解码基本实现完整。以下代码来自 d7eca7bcc12e940f0aa80d45e6e802ba68143b5c rlp.go中。 
可通过:
https://github.com/ethereum/go-ethereum/blob/d7eca7bcc12e940f0aa80d45e6e802ba68143b5c/ethutil/rlp.go 在线查看

或者在go-ethereum源码目录中,迁出到指定提交
git checkout d7eca7bcc12e940f0aa80d45e6e802ba68143b5c


func Encode(object interface{}) []byte {
    var buff bytes.Buffer

    if object != nil {
        switch t := object.(type) {
        case *Value:
            buff.Write(Encode(t.Raw()))
        // Code dup :-/
        case int:
            buff.Write(Encode(big.NewInt(int64(t))))
        case uint:
            buff.Write(Encode(big.NewInt(int64(t))))
        case int8:
            buff.Write(Encode(big.NewInt(int64(t))))
        case int16:
            buff.Write(Encode(big.NewInt(int64(t))))
        case int32:
            buff.Write(Encode(big.NewInt(int64(t))))
        case int64:
            buff.Write(Encode(big.NewInt(t)))
        case uint16:
            buff.Write(Encode(big.NewInt(int64(t))))
        case uint32:
            buff.Write(Encode(big.NewInt(int64(t))))
        case uint64:
            buff.Write(Encode(big.NewInt(int64(t))))
        case byte:
            buff.Write(Encode(big.NewInt(int64(t))))
        case *big.Int:
            buff.Write(Encode(t.Bytes()))
        case []byte:
            if len(t) == 1 && t[0] <= 0x7f {
                buff.Write(t)
            } else if len(t) < 56 {
                buff.WriteByte(byte(len(t) + 0x80))
                buff.Write(t)
            } else {
                b := big.NewInt(int64(len(t)))
                buff.WriteByte(byte(len(b.Bytes()) + 0xb7))
                buff.Write(b.Bytes())
                buff.Write(t)
            }
        case string:
            buff.Write(Encode([]byte(t)))
        case []interface{}:
            // Inline function for writing the slice header
            WriteSliceHeader := func(length int) {
                if length < 56 {
                    buff.WriteByte(byte(length + 0xc0))
                } else {
                    b := big.NewInt(int64(length))
                    buff.WriteByte(byte(len(b.Bytes()) + 0xf7))
                    buff.Write(b.Bytes())
                }
            }

            var b bytes.Buffer
            for _, val := range t {
                b.Write(Encode(val))
            }
            WriteSliceHeader(len(b.Bytes()))
            buff.Write(b.Bytes())
        }
    } else {
        // Empty list for nil
        buff.WriteByte(0xc0)
    }

    return buff.Bytes()
}

例子

  • 字符串 "dog" 编码:
case string:
        buff.Write(Encode([]byte(t)))

case []byte:
        if len(t) == 1 && t[0] <= 0x7f {
            buff.Write(t)
        } else if len(t) < 56 {
            buff.WriteByte(byte(len(t) + 0x80))
            buff.Write(t)
        } else {
            b := big.NewInt(int64(len(t)))
            buff.WriteByte(byte(len(b.Bytes()) + 0xb7))
            buff.Write(b.Bytes())

len("dog")==3 < 56,
前缀 = byte(3+0x80) = 0x83
跟随字符串"dog" ,最终为[0x83,'d','o','g'] = [0x83,0x64,0x6f,0x67]               
  • 列表 [ "cat", "dog" ] 
    [ 0xc8, 0x83, 'c', 'a', 't', 0x83, 'd', 'o', 'g' ]
  • 关注int整数的保存 。
    case *big.Int:
        buff.Write(Encode(t.Bytes()))   
    Bytes方法返回的正式是大端序的byte切片 (returns the absolute value of x as a big-endian byte slice.)

RLP 解码

根据RLP编码的规则和过程,RLP解码的输入应视为二进制数据的数组,过程如下:
  1. 根据输入数据的第一个字节(即前缀),并解码数据类型、实际数据的长度和偏移量;
  2. 根据数据的类型和偏移,相应解码数据;
继续解码其余的输入;
其中,解码数据类型和偏移的规则如下:
  1. 如果第一个字节(即前缀)的范围是[0x00,0x7f],则该数据是一个字符串,且内容为该字节本身;
  2. 如果第一个字节的范围是[0x80,0xb7],那么数据是一个字符串,长度等于第一个字节减去0x80,字符串跟在第一个字节后面;
  3. 如果第一个字节的范围是[0xb8,0xbf],那么数据是一个字符串,第一个字节减去0xb7等于表示长度的字节数(跟在第一字节后),取得长度字节后得到实际字符串长度,字符串紧跟其后;
  4. 如果第一字节的范围是[0xc0,0xf7],则数据是列表,第一字节减去0xc0后得到列表的长度;
  5. 如果第一个字节的范围是[0xf8,0xff],那么该数据就是一个列表,第一个字节减去0xf7等于表示长度的字节数,根据长度字节数取得列表长度。列表紧跟其后;
Golang 代码如下:
// TODO Use a bytes.Buffer instead of a raw byte slice.
// Cleaner code, and use draining instead of seeking the next bytes to read
func Decode(data []byte, pos uint64) (interface{}, uint64) {
    var slice []interface{}
    char := int(data[pos])
    switch {
    case char <= 0x7f:
        return data[pos], pos + 1

    case char <= 0xb7:
        b := uint64(data[pos]) - 0x80

        return data[pos+1 : pos+1+b], pos + 1 + b

    case char <= 0xbf:
        b := uint64(data[pos]) - 0xb7

        b2 := ReadVarint(bytes.NewReader(data[pos+1 : pos+1+b]))

        return data[pos+1+b : pos+1+b+b2], pos + 1 + b + b2

    case char <= 0xf7:
        b := uint64(data[pos]) - 0xc0
        prevPos := pos
        pos++
        for i := uint64(0); i < b; {
            var obj interface{}

            // Get the next item in the data list and append it
            obj, prevPos = Decode(data, pos)
            slice = append(slice, obj)

            // Increment i by the amount bytes read in the previous
            // read
            i += (prevPos - pos)
            pos = prevPos
        }
        return slice, pos

    case char <= 0xff:
        l := uint64(data[pos]) - 0xf7
        b := ReadVarint(bytes.NewReader(data[pos+1 : pos+1+l]))

        pos = pos + l + 1

        prevPos := b
        for i := uint64(0); i < uint64(b); {
            var obj interface{}

            obj, prevPos = Decode(data, pos)
            slice = append(slice, obj)

            i += (prevPos - pos)
            pos = prevPos
        }
        return slice, pos

    default:
        panic(fmt.Sprintf("byte not supported: %q", char))
    }

    return slice, 0
}
Share:

阅读 go-ethereum 源码 - 1

如何理解系统的设计?最好的方法当然是:
Read The Fucking Source Code

Go Ethereum 是什么

以太坊从项目早起,就有不同操作系统下的多客户端实现。这些客户端可以互相验证以太坊的协议正确性。go-ethereum 是以太坊协议的go语言实现的客户端。
截止2016年9月,go-ethereum(go语言实现) 和 Parity(Rust语言实现) 是领先的实现方案。 
以太坊的协议标准在其黄皮书中定义。 
go-ethereum 由 Jeffrey Wilcke 领导开发,项目启动与2013年,开发语言为Go。go-ethereum在2015年7月30日成功发布,标志着创世区块和以太坊平台的发布。 
Jeff Wilcke 为以太坊的创始人之一,并是以太坊的三位董事之一。

源码下载

从github网站下载源码:
git clone https://github.com/ethereum/go-ethereum.git
查看提交记录:
cd go-ethereum/

git log --reverse

commit 5db3335dce766bd679c54ea44f6df08a7ff74762
Author: obscuren <obscuren@obscura.com>
Date:   Thu Dec 26 12:45:52 2013 +0100

    Initial commit

commit f77424d3fe89d6ece9bc5d24f784c648306d611a
Author: obscuren <obscuren@obscura.com>
Date:   Thu Dec 26 12:46:02 2013 +0100

    Initial commit

commit f201547731aca98ae24a62b816a9957927481a2f
Author: obscuren <obscuren@obscura.com>
Date:   Thu Dec 26 12:47:06 2013 +0100

    added git ignore

commit fe5577f59e0b5b254013263675e7a0989e7cd82a
Author: obscuren <obscuren@obscura.com>
Date:   Thu Dec 26 13:29:45 2013 +0100

    Added readme
看到初始提交记录为: 5db3335dce766bd679c54ea44f6df08a7ff74762
切换源码到初始提交:
git checkout 5db3335dce766bd679c54ea44f6df08a7ff74762

Note: checking out '5db3335dce766bd679c54ea44f6df08a7ff74762'.

You are in 'detached HEAD' state. You can look around, make experimental
changes and commit them, and you can discard any commits you make in this
state without impacting any branches by performing another checkout.

If you want to create a new branch to retain commits you create, you may
do so (now or later) by using -b with the checkout command again. Example:

  git checkout -b <new-branch-name>

HEAD is now at 5db3335dc... Initial commit

阅读第一次提交的源码

第一次提交时间2013/12/26 (东一区), 记录如下:
git log 5db3335dce766bd679c54ea44f6df08a7ff74762
commit 5db3335dce766bd679c54ea44f6df08a7ff74762

Author: obscuren <obscuren@obscura.com>
Date:   Thu Dec 26 12:45:52 2013 +0100

    Initial commit
文件如下 
文件名说明
big.go大数字操作
transaction.go交易(tx)的struct
block.go区块链中的块(block)结构
block_manager.go块管理
parsing.go将代码语句编码
serialization.go序列化,实现rlp编码
ethereum.go程序main函数入口

编译&运行

cd go-ethereum     #进入目录
go build            #编译
./go-ethereum       #执行

#输出如下:

init Ethereum VM
stack size = 256

# processing Tx (8fee28c5311d91212d92cbf14548e9e96ab39a)
# fee = 0.000000, ops = 12, sender = 1234567890, value = 20

# processing Tx (3ab78afb9e495acc6eabd8982730dbb679db2f)
# fee = 0.000000, ops = 2, sender = 1234567890, value = 20
0   67 [10 6 0 0 0 0]
0   67 [10 6 0 0 0 0]
# finished processing Tx

2   66 [10 10 0 0 0 0]
3   67 [255 7 0 0 0 0]
4   81 [20 255 0 0 0 0]
... JMP 7 ...
7   66 [30 31 0 0 0 0]
8   67 [255 22 0 0 0 0]
9   81 [31 255 0 0 0 0]
... JMP 22 ...
# finished processing Tx

rlp encoded Tx "\x01\x00\x010\x00\n1234567890\x00\x010\x00\x0220\x00\x010\x01\x00\x06395843\x00\x06657986\x00\t335612448\x00\x06524099\x00\b16716881\x00\x010\x00\b13114947\x00\a2039362\x00\a1507139\x00\b16719697\x00\a1048387\x00\x0565360"
执行过程中偶尔会报错误:
fatal error: concurrent map writes
是因为go语言版本 处理并发读写的变动有关。 暂时忽略这个问题。 或者修改 ethereum.go 的28行,设置blck []*Transaction数组中仅传一个对象。 

big.go

以太坊中操作的数字,取值范围较大。基本类型的int、int64、float等无法存储。所以需要golang的  "math/big" 包进行大精度数字处理。big.go中封装了两个快捷函数,实现
  • 字符串转big.Int Big(num string) *big.Int 
  • int类型数字的指数操作 BigPow(a,b int) *big.Int。

transaction.go

定义了区块中交易的数据结构。 结构如下:
 type Transaction struct {
  sender      string
  recipient   uint32
  value       uint32
  fee         uint32
  data        []string
  memory      []int
  signature   string

  addr        string
}
 
源码中亦注释了结构体成员的意义、字节大小等
/* 
Transaction   Contract       Size
-------------------------------------------
sender        sender       20 bytes
recipient     0x0          20 bytes
value         endowment     4 bytes (uint32)
fee           fee           4 bytes (uint32)
d_size        o_size        4 bytes (uint32)
data          ops           *
signature     signature    64 bytes
*/
同时定义了处理交易过程中的收费内容:
var StepFee   *big.Int = new(big.Int)
var TxFee     *big.Int = new(big.Int)
var MemFee    *big.Int = new(big.Int)
var DataFee   *big.Int = new(big.Int)
var CryptoFee *big.Int = new(big.Int)
var ExtroFee  *big.Int = new(big.Int)

var Period1Reward *big.Int = new(big.Int)
var Period2Reward *big.Int = new(big.Int)
var Period3Reward *big.Int = new(big.Int)
var Period4Reward *big.Int = new(big.Int)
以太坊中的矿工处理交易,是需要收取一定费用的。根据如上的一些定义可以粗略看出几种收费类型: 计算步骤、交易费、内存使用费、数据费等等。 可以对比比特币区块链的收费,其主要根据交易数据的大小来判断费用。

block.go

定义的区块的数据结构 ,区块由交易所组成
type Block struct {
  transactions []*Transaction
}

block_mananger.go

区块处理的逻辑。 
type BlockManager struct {
  vm *Vm
}

func (bm *BlockManager) ProcessBlock(block *Block) error
func (bm *BlockManager) ProcessTransaction(tx *Transaction, lockChan chan bool)
block的处理逻辑就是循环处理block下transaction的过程。 对transaction的处理,调用虚拟机 vm *Vm 对象来处理。 

serialization.go

用于处理以太坊中的RLP编码。 下一篇专门分析RLP编码

parsing.go

将类似于汇编语言的操作: "SET 10 6" "LD 10 10"
指令转换为6字节的Big Int
Big int equation = op + x * 256 + y * 256**2 + z * 256**3 + a * 256**4 + b * 256**5 + c * 256**6 。 
上面第一行代码解析后内容为:
十六进制表示:
0x 00 00 00 06 0A 43
转为string后:
395843

反向的十进制表示:

67 10 6 0 0 0 0

vm.go

处理区块链交易的最核心代码。Transaction对象的data,保存的是代码经过parsing.go 转换后的string数组。
"SET 10 6" => 395843(big.Int)=>"395843" (string)
vm处理RunTransaction的简单步骤为:
  1. 用map模拟stack栈 vm.stack = make(map[string]string)
  2. 为交易分配一段内存,map模拟。vm.memory[tx.addr] = make(map[string]string)
  3. 将编码后的内容还原为语句。
  4. 获得语句中的操作码、参数。并执行相关操作
67 10 6 0 0 0 0
代码的内容如下:

定义数组索引
x := 0; y := 1; z := 2; //a := 3; b := 4; c := 5

67 = 0x43 代表代码操作码
10 6 0 0 0 0 代表参数 args = [10,6,0,0,0,0]
操作码含义

    oSET        int = 0x43
代码的操作方式为:
case oSET:
// Set the (numeric) value at Iy to Rx
vm.stack[args[ x ]] = args[ y ]
所有语句处理完毕后,完成交易操作
Share: