2018年9月2日星期日

Mac OS 安装PlantUML ,配合VSCode

软件要求: 
Java : 是运行PlantUML的必需条件, 请在您的环境中安装Java 
graphviz-dot: 可选的, 但是建议安装 (如果想绘制 除 时序图和活动图以外的图, 就需要安装 Graphviz 软件)

Java

https://www.java.com/en/download/ 下载安装JRE。 
查看安装结果:
命令行输入:java -version

java version "1.8.0_181"
Java(TM) SE Runtime Environment (build 1.8.0_181-b13)
Java HotSpot(TM) 64-Bit Server VM (build 25.181-b13, mixed mode)

安装graphviz

从https://www.graphviz.org/download/下载适合您当前操作系统的graphviz软件包, 安装或者解压到指定的目录.
使用Homebrew 安装
brew install graphviz

VSCode 安装plantuml

快捷键 Shift + Command + X,打开插件窗口(Extensioin),输入plantuml搜索。 搜索结果中点击‘PlantUML' 安装。 
PLantUML 支持的格式有: *.wsd, *.pu, *.puml, *.plantuml, *.iuml

编辑文件

新建文件测试一下:sequence.wsd
输入以下内容:
@startuml
Alice -> Bob: Authentication Request
Bob --> Alice: Authentication Response

Alice -> Bob: Another authentication Request
Alice <-- Bob: another authentication Response
@enduml

生成图表:

右键选择 Preview Current Diagram 或快捷键 ALT+D 预览生成的UML图。 

导出图表

右键选择 Export Current Diagram ,选择文件格式。 确定,等待图片生成。
下方 Output窗口会显示处理结果。 

资源

PlantUML官网 http://plantuml.com/
Share:

安装 python3.6

Mac OS

DMG 安装

brew

https://stackoverflow.com/questions/51125013/how-can-i-install-a-previous-version-of-python-3-in-macos-using-homebrew
brew install python3 #安装最新版本python3 == python3.7.0

brew install https://raw.githubusercontent.com/Homebrew/homebrew-core/f2a764ef944b1080be64bd88dca9a1d80130c558/Formula/python.rb # python3.6.5 


python3 -V

pip (可省略,brew自动安装)

$ curl -O https://bootstrap.pypa.io/get-pip.py
$ sudo python3 get-pip.py

pip3 --version  (pip -V)

venv


python3 -m venv ENV36
source ENV36/bin/activate

Centos 7

Step1 add the repository

sudo yum install -y https://centos7.iuscommunity.org/ius-release.rpm

sudo yum update

Download and install Python & Pip3


sudo yum install -y python36u python36u-libs python36u-devel python36u-pip


python3.6 -V

创建venv (python 3 内置)


python3 -m venv ENV36
source ENV36/bin/activate
Share:

2018年4月28日星期六

阅读 go-ethereum 源码 - 6

本次看下 go-ethereum 网络的雏形。 代码仍然停留在
commit ba385ccdf15f8379c54d65061c3d62353baffc2b (HEAD)
Author: obscuren <geffobscura@gmail.com>
Date:   Fri Jan 10 10:59:57 2014 +0100

    sudo not udo

server.go

type Server struct {
  // Channel for shutting down the server
  shutdownChan chan bool
  // DB interface
  db          *LDBDatabase
  // Block manager for processing new blocks and managing the block chain
  blockManager *BlockManager
  // Peers (NYI)
  peers       *list.List
}
Server 结构定义了go-ethereum启动后网络的基本功能。 

启动本地网络绑定

func (s *Server) Start() {
  // For now this function just blocks the main thread
  ln, err := net.Listen("tcp", ":12345")
  if err != nil {
    log.Fatal(err)
  }

  go func() {
    for {
      conn, err := ln.Accept()
      if err != nil {
        log.Println(err)
        continue
      }

      go s.AddPeer(conn)
    }
  }()
}
该方法调用 net 模块,在tcp 12345 端口进行绑定,并等待其他网络连接。 当网络连接到达后,将该连接封装到 Peer 结构内,并保存到列表内。 
添加连接节点
func (s *Server) AddPeer(conn net.Conn)

关闭网络连接

func (s *Server) Stop() {
  // Close the database
  defer s.db.Close()

  // Loop thru the peers and close them (if we had them)
  for e := s.peers.Front(); e != nil; e = e.Next() {
    if peer, ok := e.Value.(*Peer); ok {
      peer.Stop()
    }
  }

  s.shutdownChan <- true
}
逐一停止列表内的节点,并关闭本地数据库。 

广播

func (s *Server) Broadcast(msgType string, data []byte)
向所有连接发送消息。

主动连接到其他节点

func (s *Server) ConnectToPeer(addr string) error

peer.go

peer.go 封装了 Peer 结构。 主要实现具体网络节点连接之间的消息发送/收取操作。
type Peer struct {
  // Server interface
  server      *Server
  // Net connection
  conn        net.Conn
  // Output queue which is used to communicate and handle messages
  outputQueue chan OutMsg
  // Quit channel
  quit        chan bool
}

启动

Peer 创建后就会启动。 
func (p *Peer) Start() {
  // Run the outbound handler in a new goroutine
  go p.HandleOutbound()
  // Run the inbound handler in a new goroutine
  go p.HandleInbound()
}
同时启动协程 分别处理发送(p.HandleOutbound)和 接收(p.HandleInbound)。 两协程循环处理,直至收到退出信号。 

发送消息

func (p *Peer) WriteMessage(msg OutMsg) {
  // Encode the type and the (RLP encoded) data for sending over the wire
  encoded := Encode([]interface{}{ msg.msgType, msg.data })
  // Write to the connection
  _, err := p.conn.Write(encoded)
  if err != nil {
    log.Println(err)
    p.Stop()
  }
}
首先将需要发送的消息,进行RLP编码,然后调用net 库向连接写入数据。

接收消息

func ReadMessage(conn net.Conn) (*InMsg, error) {
  buff := make([]byte, 4069)

  // Wait for a message from this peer
  n, err := conn.Read(buff)
  if err != nil {
    return nil, err
  } else if n == 0 {
    return nil, errors.New("Empty message received")
  }

  // Read the header (MAX n)
  // XXX The data specification is made up. This will change once more details have been released on the specification of the format
  decoder := NewRlpDecoder(buff[:n])
  t := decoder.Get(0).AsString()
  // If the msgdata contains no data we throw an error and disconnect the peer
  if t == "" {
    return nil, errors.New("Data contained no data type")
  }

  return &InMsg{msgType: t, data: decoder.Get(1).AsBytes()}, nil
}
消息到达后,读取,并RLP解码。并交由其他功能模块处理。 

测试运行

cd go-ethereum 
go build 
./go-ethereum 
输出:

2018/04/28 16:09:27 Starting Ethereum
2018/04/28 16:09:27 Connected to peer :: [::1]:12345
2018/04/28 16:09:27 Peer connected :: [::1]:57114
在 ethereum.go main()入口函数中,如不传入任何参数。 Server则主要做如下工作:
//创建Server
server, err := NewServer()
//注册终止信号
RegisterInterupts(server)
//启动Server
server.Start()

//同时启动一个连接,连向刚才的服务端口12345
err = server.ConnectToPeer("localhost:12345")
Share:

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: