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: