VisualBasic实现DHT分布式哈希表网络中的Bencode

信息技术原理区块链技术相关算法理论
谢桂纲 -
7:08 PM
估计阅读时长: 7 分钟

https://github.com/xieguigang/sciBASIC

在分布式哈希表网络之中，Peer节点之间进行分布式数据传输都是使用的B编码。B编码格式与JSON编码格式较为相似，均以“键：值”形式存储，我们可以将B编码的字符串整个内容理解为一个经过特殊编码的字典，或者一个近似的JSON。B编码与JSON编码，这两种编码都仅包含有4种最基础的数据类型：字符串类型，数值类型，数组类型与对象字典类型。

字符串类型

string类型的编码格式为[length]:[string]，以字符串长度开头，以字符串内容结束。

bencode("hello")
# [1] "5:hello"

需要进行编码的字符串hello总共有5个字符，所以按照前面所提到的编码格式，我们将其字符数量放在字符串前面后就生成了编码输出5:hello。

''' <summary>
''' Generates the bencoded equivalent of the string.
''' </summary>
''' <param name="u">The StringBuilder to append to.</param>
''' <returns>The bencoded equivalent of the string.</returns>
Public Function ToBencodedString(u As StringBuilder) As StringBuilder Implements BElement.ToBencodedString
    If u Is Nothing Then
        u = New StringBuilder(Value.Length)
    Else
        u.Append(Value.Length)
    End If

    Return u.Append(":"c).Append(Value)
End Function

数值类型

这里的数值类型仅仅是指整型数，其他的浮点数都使用字符串来表示，对于integer类型，编码格式为i[int]e，以i开头，以e结尾。所以对于一个整型数12345，我们应用上面的规则可以很容易的就得到了编码输出：i12345e：

bencode(12345)
# [1] "i12345e"

这里给出了整数的B编码代码：

''' <summary>
''' Generates the bencoded equivalent of the integer.
''' </summary>
''' <returns>The bencoded equivalent of the integer.</returns>
Public Function ToBencodedString(u As StringBuilder) As StringBuilder Implements BElement.ToBencodedString
    If u Is Nothing Then
        u = New StringBuilder("i"c)
    Else
        u.Append("i"c)
    End If

    Return u.Append(Value.ToString()).Append("e"c)
End Function

数组类型

数组类型其实在这里更应该被称作为列表类型，因为对于这个集合类型而言，其编码是以字符l开头的，l即list。本类型的编码格式为l[object]e，以l开头，以e结尾。

bencode([1,2,3,4,5])
# [1] "li1ei2ei3ei4ei5ee"

从这里开始，编码的函数就开始有点复杂了。因为数组元素可能是数组，可能是对象，也可能是基本的字符串或者整数。但是因为数组其实是一个对象树来的，好在我们使用了一个BElement的抽象接口来描述我们的数据，所以我们只需要从最外层对数组元素进行递归遍历，添加编码字符串就可以了：

''' <summary>
''' Generates the bencoded equivalent of the list.
''' </summary>
''' <param name="u">The StringBuilder to append to.</param>
''' <returns>The bencoded equivalent of the list.</returns>
Public Function ToBencodedString(u As StringBuilder) As StringBuilder Implements BElement.ToBencodedString
    If u Is Nothing Then
        u = New StringBuilder("l"c)
    Else
        u.Append("l"c)
    End If

    For Each element In ToArray()
        element.ToBencodedString(u)
    Next

    Return u.Append("e"c)
End Function

对象字典类型

这里的对象字典，其实就是JSON之中的对象字典，在这个对象字典中数据是以键值对的形式进行保存。编码格式为d[Key-Value Pair]e，以d开头，以e结尾，字符d即dictionary。

list(
   name = "xieguigang",
   site = "stack.xieguigang.me",
   RMB  = 999999,
   city = ["GuiLin", "SuZhou"]
)
|> bencode

# [1] "d4:cityl6:GuiLin6:SuZhoue4:name10:xieguigang3:RMBi999999e4:site19:stack.xieguigang.mee"

字典的序列化与数组的序列化原理类似，都是对元素集合的序列化。只不过在这里只是多了一个Key字符串在元素值前面：

''' <summary>
''' Generates the bencoded equivalent of the dictionary.
''' </summary>
''' <param name="u">The StringBuilder to append to.</param>
''' <returns>The bencoded equivalent of the dictionary.</returns>
Public Function ToBencodedString(u As StringBuilder) As StringBuilder Implements BElement.ToBencodedString
    If u Is Nothing Then
        u = New StringBuilder("d"c)
    Else
        u.Append("d"c)
    End If

    For i = 0 To Count - 1
        Enumerable.ElementAt(Keys, i).ToBencodedString(u)
        Enumerable.ElementAt(Values, i).ToBencodedString(u)
    Next

    Return u.Append("e"c)
End Function

在这里需要注意的是，在B编码之中，对象字典中的键名是有从小到大排序顺序的。所以我们在对对象字典进行B编码序列化之后再进行反序列化，字典中的元素的顺序很有可能会变了。这一点是B编码与JSON编码相比最大的一处差异了（JSON格式最起码还可以保证元素的顺序不会发生改变）。

R#语言中的Bencode编码api

我在R#语言内部的字符串处理模块中，对R#脚本语言导出了两个与B编码相关的api函数：

  • bencode: 对任意类型的R#对象生成B编码字符串
  • bdecode: 从B编码字符串之中反序列化加载为任意数据类型的R#语言对象

使用这两个函数非常的简单：对于bencode函数，使用方法在上面的编码格式说明中已经展示过了，我在这里就不再重复展示了；对于bdecode函数，我将在下面的小结中进行使用方法展示，大家可以继续阅读下文。

Bencode解析实例

对于下面的一段所示B编码的字符串，

d8:announce41:http://bttracker.debian.org:6969/announce7:comment35:"Debian CD from cdimage.debian.org"13:creation datei1612616380e9:httpseedsl146:https://cdimage.debian.org/cdimage/release/edu//srv/cdbuilder.debian.org/dst/deb-cd/weekly-builds/amd64/iso-cd/debian-edu-10.8.0-amd64-netinst.iso146:https://cdimage.debian.org/cdimage/archive/edu//srv/cdbuilder.debian.org/dst/deb-cd/weekly-builds/amd64/iso-cd/debian-edu-10.8.0-amd64-netinst.isoe4:infod6:lengthi425721856e4:name35:debian-edu-10.8.0-amd64-netinst.iso12:piece lengthi262144e6:piecesi32480eee

再不了解B编码的情况下乍一看非常的复杂，但是假若我们按照上面的编码规则进行解析，就可以很容易的得到了里面的信息。冒号前面为数字的肯定是一个字符串，则我们可以按照长度截取字符串后插入一个回车来进行上面的字符串格式化。格式化后得到下面的内容结构信息：

d
    8:announce
        41:http://bttracker.debian.org:6969/announce
    7:comment
        35:"Debian CD from cdimage.debian.org"
    13:creation date
        i1612616380e
    9:httpseeds
        l
            146:https://cdimage.debian.org/cdimage/release/edu//srv/cdbuilder.debian.org/dst/deb-cd/weekly-builds/amd64/iso-cd/debian-edu-10.8.0-amd64-netinst.iso
            146:https://cdimage.debian.org/cdimage/archive/edu//srv/cdbuilder.debian.org/dst/deb-cd/weekly-builds/amd64/iso-cd/debian-edu-10.8.0-amd64-netinst.iso
        e
    4:info
    d
        6:length
            i425721856e
        4:name
            35:debian-edu-10.8.0-amd64-netinst.iso
        12:piece length
            i262144e
        6:pieces
            i32480e
    e
e

我们将上面的B编码结果字符串，使用R#脚本中的bdecode函数进行反序列化，看一下结果是不是上面描述的那样：

const bstr = 'd8:announce41:http://bttracker.debian.org:6969/announce7:comment35:"Debian CD from cdimage.debian.org"13:creation datei1612616380e9:httpseedsl146:https://cdimage.debian.org/cdimage/release/edu//srv/cdbuilder.debian.org/dst/deb-cd/weekly-builds/amd64/iso-cd/debian-edu-10.8.0-amd64-netinst.iso146:https://cdimage.debian.org/cdimage/archive/edu//srv/cdbuilder.debian.org/dst/deb-cd/weekly-builds/amd64/iso-cd/debian-edu-10.8.0-amd64-netinst.isoe4:infod6:lengthi425721856e4:name35:debian-edu-10.8.0-amd64-netinst.iso12:piece lengthi262144e6:piecesi32480eee';

print("Bencoded string:");
print(bstr);

cat("\n");

str(bdecode(bstr));

# List of 5
#  $ announce      : chr "http://bttracker.debian.org:6969/announce"
#  $ comment       : chr ""Debian CD from cdimage.debian.org""
#  $ creation date : int 1612616380
#  $ httpseeds     : chr [1:2] "https://cdimage.debian.org/cdimage/release/edu//srv/cdbuilder.d"| __truncated__
#  $ info          : List of 4
#  ..$ length       : int 425721856
#  ..$ name         : chr "debian-edu-10.8.0-amd64-netinst.iso"
#  ..$ piece length : int 262144
#  ..$ pieces       : int 32480

嗯嗯，得到的解析结果确实是和我们上面的手动解析的结果是一致的。

谢桂纲
Latest posts by 谢桂纲 (see all)

Attachments

Views: 1,092
打赏微海报分享
bencodeBitTorrentblockchainDHTR#vb

No responses yet

Leave a Reply

Your email address will not be published. Required fields are marked *

博客文章
December 2024
S M T W T F S
1234567
891011121314
15161718192021
22232425262728
293031  

  1. 在mysql之中，针对24小时内的数据按照半个小时进行一次统计数量： ```sql SELECT DATE_FORMAT(FROM_UNIXTIME(FLOOR(UNIX_TIMESTAMP(add_time) / 1800) * 1800), '%Y-%m-%d %H:%i') AS half_hour, COUNT(*) AS count FROM user_track.page_view WHERE add_time >=…

  2. 针对图对象进行向量化表示嵌入： 首先，通过node2vec方法，将node表示为向量 第二步，针对node向量矩阵，进行umap降维计算，对node进行排序，生成node排序序列 第三步，针对node排序序列进行SGT序列图嵌入，实现将网络图对象嵌入为一维向量