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: