递归区块链 区块链重构规则

本篇文章给大家谈谈递归区块链，以及区块链重构规则对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

什么是数据结构？什么是算法？算法与程序有什么关系？

在计算机编程领域，数据结构与算法的应用是无处不在。比如图像视频处理、数据压缩、数据库、游戏开发、操作系统、编译器、搜索引擎、AR、VR、人工智能、区块链等领域，都是以数据结构与算法为基石。

数据结构与算法属于开发人员的基本内功，也能训练大脑的思考能力，掌握一次，终生受益。扎实的数据结构与算法功底，能让我们站在更高的角度去思考代码、写出性能更优的程序，能让我们更快速地学习上手各种新技术（比如人工智能、区块链等），也能让我们敲开更高级编程领域的大门。

数据结构与算法更是各大名企面试题中的常客，如果不想被行业抛弃、想进入更大的名企、在IT道路上走得更远，掌握数据结构与算法是非常有必要。

区块链不挖会断吗

你的这个问题，需要厘清两个概念：

什么是区块链？

区块链(Blockchain)是比特币的一个重要概念，它本质上是一个去中心化的数据库，同时作为比特币的底层技术。区块链是一串使用密码学方法相关联产生的数据块，每一个数据块中包含了一次比特币网络交易的信息，用于验证其信息的有效性(防伪)和生成下一个区块。

挖矿，挖的是区块链吗？

要理解“挖矿”，必须得先搞清楚区块链的结构。

区块：可以理解为一张空白纸。正如一张白纸不能无限大一样，区块也有大小限制，比特币最初的大小限制在1M字节，一个区块就是存在电脑上的一个文件。一个区块分为两部分，分别是“区块头”和“区块体”，其中区块头用来记录一些说明信息，而区块体是用来记录“交易”的列表。注意，是列表，真正的数据记录在客户端的数据库中。

区块头：区块头共有六个字段，分别是版本号、前一区块的哈希值、梅克尔根、预设的难度值、时间戳、要寻找的随机数。

（1）版本号：用于区分软件的升级换代。在一段时间内不变且相同。

（2）前一区块的哈希值。实际就是前一区块头的哈希值。成链就靠它了，10分钟的“挖矿”过程，所有“矿机”中这个值不变且相同。

（3）预设的难度值。10分钟内所有“矿机”中这个值不变且相同。

（4）梅克尔根。这也是一个哈希值，它是由列表中的每个交易两两递归生成的一个总哈希值。交易随时在到来，因此这个总哈希随时在变，而且因为网络延迟、交易优先级等诸多问题，每个结点记录的列表不一定相同。因此，梅克尔根是一个变化值且与其它节点不相同。

（5）时间戳。这也是一个变化值，几秒钟就会改变。

（6）要寻找的随机数。这个就是要获得挖矿奖励的核心要素，也就是“矿机”穷尽算力要寻找的那个随机数值。

挖矿过程就是对以上这六个字段进行一系列的转换、连接和哈希运算，并随着不断一个一个试要寻找的随机数，最后成功找到一个随机数满足条件：经过哈希运算后的值，比预设难度值的哈希值小，那么，就挖矿成功了，节点可以向邻近节点进行广播该区块，邻近节点收到该区块，对以上六个字段进行同样的运算，验证合规，再向其它结点转播，其它结点也用同样的算法进行验证，如果全网有51%的结点都验证成功，这个区块就算真正地“挖矿”成功了，每个结点都把这个区块加在上一个区块的后面，并把区块中与自己记录相同的列表删除，再次复生上述过程。

结论

区块链不挖会断吗？如果单指区块链，那肯定不存在断不断问题，如果是指挖矿，那么不挖的话，收益就会停止。

希望我的回答可以帮助到你~

什么是LRC？

纵向冗余校验（LRC，Longitudinal Redundancy Check）是通信中常用的一种校验形式。纵向冗余校验(LRC)是一种从纵向通道上的特定比特串产生校验比特的错误检测方法。在行列格式中（例如，在磁带中），LRC经常是与VRC一起使用，这样就会为每个字符校验码。

介绍

纵向冗余校验的异或校验和可以简单快速的计算出来，将一个数据块的所有数据字节递归，经过异或选通后即可产生异或校验和。

由于算法简单，可以快速简单地计算纵向冗余校验。然而，LRC并不很可靠，多个错误可能相互抵消，在一个数据块内字节顺序的互换根本识别不出来。因此LRC主要用于快速校验很小的数据块儿（如32B）。在射频识别系统中，由于标签的容量一般较小，每次交易的数据量也不大，所以这种算法还是比较适合的。

区块链的核心技术是什么？

区块链运作的7个核心技术介绍

2018-01-15

1.区块链的链接

顾名思义，区块链即由一个个区块组成的链。每个区块分为区块头和区块体（含交易数据）两个部分。区块头包括用来实现区块链接的前一区块的哈希（PrevHash）值（又称散列值）和用于计算挖矿难度的随机数（nonce）。前一区块的哈希值实际是上一个区块头部的哈希值，而计算随机数规则决定了哪个矿工可以获得记录区块的权力。

2.共识机制

区块链是伴随比特币诞生的，是比特币的基础技术架构。可以将区块链理解为一个基于互联网的去中心化记账系统。类似比特币这样的去中心化数字货币系统，要求在没有中心节点的情况下保证各个诚实节点记账的一致性，就需要区块链来完成。所以区块链技术的核心是在没有中心控制的情况下，在互相没有信任基础的个体之间就交易的合法性等达成共识的共识机制。

区块链的共识机制目前主要有4类：PoW、PoS、DPoS、分布式一致性算法。

3.解锁脚本

脚本是区块链上实现自动验证、自动执行合约的重要技术。每一笔交易的每一项输出严格意义上并不是指向一个地址，而是指向一个脚本。脚本类似一套规则，它约束着接收方怎样才能花掉这个输出上锁定的资产。

交易的合法性验证也依赖于脚本。目前它依赖于两类脚本：锁定脚本与解锁脚本。锁定脚本是在输出交易上加上的条件，通过一段脚本语言来实现，位于交易的输出。解锁脚本与锁定脚本相对应，只有满足锁定脚本要求的条件，才能花掉这个脚本上对应的资产，位于交易的输入。通过脚本语言可以表达很多灵活的条件。解释脚本是通过类似我们编程领域里的“虚拟机”，它分布式运行在区块链网络里的每一个节点。

4.交易规则

区块链交易就是构成区块的基本单位，也是区块链负责记录的实际有效内容。一个区块链交易可以是一次转账，也可以是智能合约的部署等其他事务。

就比特币而言，交易即指一次支付转账。其交易规则如下：

1）交易的输入和输出不能为空。

2）对交易的每个输入，如果其对应的UTXO输出能在当前交易池中找到，则拒绝该交易。因为当前交易池是未被记录在区块链中的交易，而交易的每个输入，应该来自确认的UTXO。如果在当前交易池中找到，那就是双花交易。

3）交易中的每个输入，其对应的输出必须是UTXO。

4）每个输入的解锁脚本（unlocking

）必须和相应输出的锁定脚本（locking

）共同验证交易的合规性。

5.交易优先级

区块链交易的优先级由区块链协议规则决定。对于比特币而言，交易被区块包含的优先次序由交易广播到网络上的时间和交易额的大小决定。随着交易广播到网络上的时间的增长，交易的链龄增加，交易的优先级就被提高，最终会被区块包含。对于以太坊而言，交易的优先级还与交易的发布者愿意支付的交易费用有关，发布者愿意支付的交易费用越高，交易被包含进区块的优先级就越高。

6.Merkle证明

Merkle证明的原始应用是比特币系统（Bitcoin），它是由中本聪（Satoshi

Nakamoto）在2009年描述并且创造的。比特币区块链使用了Merkle证明，为的是将交易存储在每一个区块中。使得交易不能被篡改，同时也容易验证交易是否包含在一个特定区块中。

7.RLP

RLP（Recursive

Length

Prefix，递归长度前缀编码）是Ethereum中对象序列化的一个主要编码方式，其目的是对任意嵌套的二进制数据的序列进行编码。

【深度知识】以太坊数据序列化RLP编码/解码原理

RLP(Recursive Length Prefix)，中文翻译过来叫递归长度前缀编码，它是以太坊序列化所采用的编码方式。RLP主要用于以太坊中数据的网络传输和持久化存储。

对象序列化方法有很多种，常见的像JSON编码，但是JSON有个明显的缺点：编码结果比较大。例如有如下的结构：

变量s序列化的结果是{"name":"icattlecoder","sex":"male"},字符串长度35，实际有效数据是icattlecoder 和male，共计16个字节，我们可以看到JSON的序列化时引入了太多的冗余信息。假设以太坊采用JSON来序列化，那么本来50GB的区块链可能现在就要100GB，当然实际没这么简单。

所以，以太坊需要设计一种结果更小的编码方法。

RLP编码的定义只处理两类数据：一类是字符串（例如字节数组），一类是列表。字符串指的是一串二进制数据，列表是一个嵌套递归的结构，里面可以包含字符串和列表，例如["cat",["puppy","cow"],"horse",[[]],"pig",[""],"sheep"]就是一个复杂的列表。其他类型的数据需要转成以上的两类，转换的规则不是RLP编码定义的，可以根据自己的规则转换，例如struct可以转成列表，int可以转成二进制（属于字符串一类），以太坊中整数都以大端形式存储。

从RLP编码的名字可以看出它的特点：一个是递归，被编码的数据是递归的结构，编码算法也是递归进行处理的；二是长度前缀，也就是RLP编码都带有一个前缀，这个前缀是跟被编码数据的长度相关的，从下面的编码规则中可以看出这一点。

对于值在[0, 127]之间的单个字节，其编码是其本身。

例1：a的编码是97。

如果byte数组长度l = 55，编码的结果是数组本身，再加上128+l作为前缀。

例2：空字符串编码是128，即128 = 128 + 0。

例3：abc编码结果是131 97 98 99，其中131=128+len("abc")，97 98 99依次是a b c。

如果数组长度大于55， 编码结果第一个是183加数组长度的编码的长度，然后是数组长度的本身的编码，最后是byte数组的编码。

请把上面的规则多读几篇，特别是数组长度的编码的长度。

例4：编码下面这段字符串：

The length of this sentence is more than 55 bytes, I know it because I pre-designed it

这段字符串共86个字节，而86的编码只需要一个字节，那就是它自己，因此，编码的结果如下：

184 86 84 104 101 32 108 101 110 103 116 104 32 111 102 32 116 104 105 115 32 115 101 110 116 101 110 99 101 32 105 115 32 109 111 114 101 32 116 104 97 110 32 53 53 32 98 121 116 101 115 44 32 73 32 107 110 111 119 32 105 116 32 98 101 99 97 117 115 101 32 73 32 112 114 101 45 100 101 115 105 103 110 101 100 32 105 116

其中前三个字节的计算方式如下：

184 = 183 + 1，因为数组长度86编码后仅占用一个字节。

86即数组长度86

84是T的编码

例5：编码一个重复1024次"a"的字符串，其结果为：185 4 0 97 97 97 97 97 97 ...。

1024按 big endian编码为0　0　4 0，省略掉前面的零，长度为2，因此185 = 183 + 2。

规则1~3定义了byte数组的编码方案，下面介绍列表的编码规则。在此之前，我们先定义列表长度是指子列表编码后的长度之和。

如果列表长度小于55，编码结果第一位是192加列表长度的编码的长度，然后依次连接各子列表的编码。

注意规则4本身是递归定义的。

例6：["abc", "def"]的编码结果是200 131 97 98 99 131 100 101 102。

其中abc的编码为131 97 98 99,def的编码为131 100 101 102。两个子字符串的编码后总长度是8，因此编码结果第一位计算得出：192 + 8 = 200。

如果列表长度超过55，编码结果第一位是247加列表长度的编码长度，然后是列表长度本身的编码，最后依次连接各子列表的编码。

规则5本身也是递归定义的，和规则3相似。

例7：

["The length of this sentence is more than 55 bytes, ", "I know it because I pre-designed it"]

的编码结果是:

248 88 179 84 104 101 32 108 101 110 103 116 104 32 111 102 32 116 104 105 115 32 115 101 110 116 101 110 99 101 32 105 115 32 109 111 114 101 32 116 104 97 110 32 53 53 32 98 121 116 101 115 44 32 163 73 32 107 110 111 119 32 105 116 32 98 101 99 97 117 115 101 32 73 32 112 114 101 45 100 101 115 105 103 110 101 100 32 105 116

其中前两个字节的计算方式如下：

248 = 247 +1

88 = 86 + 2，在规则3的示例中，长度为86，而在此例中，由于有两个子字符串，每个子字符串本身的长度的编码各占1字节，因此总共占2字节。

第3个字节179依据规则2得出179 = 128 + 51

第55个字节163同样依据规则2得出163 = 128 + 35

例8：最后我们再来看个稍复杂点的例子以加深理解递归长度前缀，

["abc",["The length of this sentence is more than 55 bytes, ", "I know it because I pre-designed it"]]

编码结果是：

248 94 131 97 98 99 248 88 179 84 104 101 32 108 101 110 103 116 104 32 111 102 32 116 104 105 115 32 115 101 110 116 101 110 99 101 32 105 115 32 109 111 114 101 32 116 104 97 110 32 53 53 32 98 121 116 101 115 44 32 163 73 32 107 110 111 119 32 105 116 32 98 101 99 97 117 115 101 32 73 32 112 114 101 45 100 101 115 105 103 110 101 100 32 105 116

列表第一项字符串abc根据规则2，编码结果为131 97 98 99,长度为4。

列表第二项也是一个列表项：

["The length of this sentence is more than 55 bytes, ", "I know it because I pre-designed it"]

根据规则5，结果为

248 88 179 84 104 101 32 108 101 110 103 116 104 32 111 102 32 116 104 105 115 32 115 101 110 116 101 110 99 101 32 105 115 32 109 111 114 101 32 116 104 97 110 32 53 53 32 98 121 116 101 115 44 32 163 73 32 107 110 111 119 32 105 116 32 98 101 99 97 117 115 101 32 73 32 112 114 101 45 100 101 115 105 103 110 101 100 32 105 116

长度为90，因此，整个列表的编码结果第二位是90 + 4 = 94, 占用1个字节，第一位247 + 1 = 248

以上5条就是RPL的全部编码规则。

各语言在具体实现RLP编码时，首先需要将对像映射成byte数组或列表两种形式。以go语言编码struct为例，会将其映射为列表，例如Student这个对象处理成列表["icattlecoder","male"]

如果编码map类型，可以采用以下列表形式：

[["",""],["",""],["",""]]

解码时，首先根据编码结果第一个字节f的大小，执行以下的规则判断：

1.　如果f∈ [0,128),　那么它是一个字节本身。

2.　如果f∈[128,184)，那么它是一个长度不超过55的byte数组，数组的长度为 l=f-128

3.　如果f∈[184,192)，那么它是一个长度超过55的数组，长度本身的编码长度ll=f-183,然后从第二个字节开始读取长度为ll的bytes，按照BigEndian编码成整数l，l即为数组的长度。

4.　如果f∈(192,247]，那么它是一个编码后总长度不超过55的列表，列表长度为l=f-192。递归使用规则1~4进行解码。

5.　如果f∈(247,256]，那么它是编码后长度大于55的列表，其长度本身的编码长度ll=f-247,然后从第二个字节读取长度为ll的bytes,按BigEndian编码成整数l，l即为子列表长度。然后递归根据解码规则进行解码。

以上解释了什么叫递归长度前缀编码，这个名字本身很好的解释了编码规则。

（1） 以太坊源码学习—RLP编码( )

（2）简单分析RLP编码原理

( )

STL内存管理详细分析

        STL中内存管理非常精妙，本文以SGI STL为例，分析其内存管理的设计思路，也是对侯捷老师的《STL源码剖析》中相关内容的总结。

        首先，从总体上看，STL空间配置器分为两级，针对大内存的申请，调用第一级空间配置器，对于小内存的申请，则调用第二级配置器。

        第一级空间配置器对外提供了allocate()，deallocate(),reallocate()三个函数供用户使用，同时，其内部定义了oom_allocate()和oom_reallocate()函数，用于处理内存不足的情况。

        deallocate()函数直接调用free函数释放内存，无须关心其他问题，重点在于内存不足情况下allocate()函数和reallocate()函数是如何应对的。

        allocate()函数首先调用malloc函数获取内存，在内存不足的情况下，该函数会返回空指针NULL，当malloc函数返回NULL时，则会调用oom_allocate()函数尝试释放一些内存并再次进行申请。

        这就是第一级空间配置器所提供的一种缓冲机制，第一级配置器中定义了一个函数指针，这个指针所指向的函数由用户所定义，因为只有用户知道哪些内存可以被释放来腾出空间，如果没有为该函数指针赋予相应的函数，则此时直接会抛出bad_alloc异常，若该函数指针被指定，则会不停调用该函数，直到申请到足够的内存，这里把它叫做内存不足处理函数，它的运行过程如图所示

        reallocate函数的内部运行过程和allocate函数的过程是相似的，只不过把malloc换成了realloc，oom_allocate换成了oom_reallocate，过程都是一样的。

        第二级内存配置器负责小内存的管理

        当申请大量的小内存时，一方面会把完整的内存区间划分的很破碎，当再次申请较大的内存时，可能会出现没有足够长的区间的情况，另一方面，大量的小区间也会使操作系统用来记录内存状态的数据结构很臃肿。

        第二级内存配置器所采取的策略是，在第一次申请小内存时，先申请一大块内存留作备用，以后再申请小内存时，直接从上次申请的那一大块内存中划去要求的部分，不再向系统申请。

        同样的，第二级空间配置器提供了标准接口allocate()、deallocate()、reallocate()三个接口，在介绍这三个接口之前，先介绍一下接下来会遇到的一些名词。

        1. 内存区块，有时也简称区块

        内存区块是指一块小内存，它的大小均为8的倍数，最大为128Bytes，即有8、16、24、32、40、48、56、64、72、80、88、96、114、122、128这几种，内存区块有自己的首地址，可以存储数据。在每个区块的前8个字节，存储下一个可用区块的地址，通过这种方式，可以形成一条区块链表

        2. freelist数组

        freelist数组是一个数组，内含16个元素，每一个元素是一个区块链表的首指针

        3. 内存池

        内存池是是一大块内存，它有三个参数：起始地址，终止地址以及大小，内存池的大小=终止地址 - 起始地址

        在初始状态下，内存池是空的，内存区块也是不存在的，freelist数组中保存的都是空指针。

        我们从这种状态下开始分析，该机制是如何运作的。

        当申请的内存大于128bytes时，直接转交第一级配置器进行内存申请。

        当申请的内存不大于128bytes时，假设申请n字节

        1. 计算（n + 7）/7，得到一个整数值i，这个i即为freelist的元素索引

        2. 访问freelist位于i的元素，此时该元素为NULL，不指向任何可用区块，这时将n向上调整为8的倍数，并调用refill函数

        3. refill函数的作用是给freelist重新填充内存区块，这些区块从内存池中获得，一次默认取20个，通过函数chunk_alloc获得

        chunk_alloc函数返回的是一块长度为nobjs*n的内存块，refill函数需要将这一整块连续内存分割为一个个内存区块，并构建链表的链接关系

        在内存充足的情况下，第一个内存块会被返回给用户使用，从第二块内存块开始构建链接关系，如图所示

        在内存不足的情况下，假如只分配到了一个区块，则该区块直接交给用户使用，freelist不进行更新

        如果不足20个，则仍将获得的内存构建链接关系。

        如果一个区块都没有获得，因为chunk_alloc函数内部调用了第一级配置器填充内存池，因此会按照第一级内存配置器的方式处理内存不足的情况。

        这里我们要关注几个参数

        1. 申请的内存总大小——size*nobjs，这里用total_bytes来表示

        2. 内存池剩余空间——用bytes_left表示

        如果total_bytes小于bytes_left，则直接划走total_bytes这么多内存，同时更新内存池的状态

        如果内存池的剩余空间不够申请的那么多区块，即size bytes_left total_bytes，即能够供应一部分区块，则计算最多能划多少块，并划走

        如果连一个区块都无法供应，这时候就要给内存池“加水”了

        在“加水”之前，首先要把内存池中剩下的水收集起来，别浪费了，加到freelist上去，具体的步骤是，根据剩下的内存的大小确定freelist的index，因为每个内存块都是8的倍数，划走时也按照8的倍数划分的，因此生下来的内存一定可以构成一个内存区块，找到合适的freelist位置后，将这个区块加到freelist上，这时，就可以开始“加水”了

        首先要确定“加多少水”，即为内存池填充的内存总量

        1. 加完“水”后，要满足这次的内存申请的量，即大于total_bytes

        2. 加完“水”后，内存池的大小应该比上一次的要大

        SGI STL选择的量是

        2 × total_bytes + heap_size 4

        heap_size是以往内存池的容量的累加和，这里把它作为一个附加变量来看待，要满足，随着“加水”次数变多，每次加水的量应该越来越大这个条件

        确定加多少水后，通过malloc函数获取内存

        如果获取成功，则更新内存池的状态，并递归调用chunk_malloc，因为内存池已经充足，下一次能够直接获取指定的内存

        如果没能获取那么多内存

        首先，遍历freelist，如果freelist里面有大小大于一个size的空闲区块，则将这个区块加入到内存池，并递归

        注意，这里的遍历并不是那种从freelist第一个开始逐个检查，而是以size为起点，确定freelist中相应的index，如果该index不含有空闲区块，则将size增加8字节，也就是检查下个freelist，直到后面的freelist都检查完，中途找到任何一个空闲区块，都会立即返回，不再遍历

如果遍历freelist也找不到足够的空闲区块，那么只能指望第一级配置器中由用户设置的内存不足处理函数能否解决，这里转交给第一级空间配置器，这时，要么第一级空间配置器顺利获得内存，这时会更新内存池，并递归，没能顺利获得内存，则会抛出异常。

        释放内存的过程相对简单，由第二级内存配置器分配的内存，在释放时并不交由free函数进行释放，也不放到内存池中，而是把内存加入到freelist链表中，以备下次使用，这个过程主要是简单的链表操作，不作详解。

        freelist中，每一个元素都是obj*，obj的结构如图所示

        这里为什么要采用这种结构？

        首先考虑它的功能，它是内存区块的链表结点，它需要记录当前区块的地址，以及下个区块的地址，每个地址都是8个字节的指针，用一个struct来表示，需要16字节，而使用union结构，只需要8个字节

        在每个内存区块的前8个字节处，是个obj对象，它存储着下一个内存区块的地址，当用free_list_link来解引用这个指针时，有效区间为这8个字节，client_data是一个长度为1的数组，只有一个元素，它就是内存区块的第一个字节，为这个字节定义一个变量，并对它取址，得到的就是当前区块的地址，这里采用数组的形式而不是直接定义一个char，目的是直接将client_data作为数组首地址返回，而不需要调用取址运算符，将该内存区块返回时，返回client_data，无须进行类型转换，直接在union中切换就行，状态的改变不会改变前8个字节的内容，但内存区块交出去后，前八个字节的内容丢失也不重要了，在将内存区块加入到freelist中时，会重新设置前8个字节的值，保证数据的有效性。

写到这里，本文关于递归区块链和区块链重构规则的介绍到此为止了，如果能碰巧解决你现在面临的问题，如果你还想更加了解这方面的信息，记得收藏关注本站。