一种化链为点的存储验证系统及应用zym11的博客-

摘要：在一种点对点的电子现金系统中，提出了简化的支付验证方式（Simplified Payment Verification），即用户不需要运行全节点，只需要同步区块头数据，就能通过Merkle Tree对某次支付进行验证。也即验证某个交易是否包含在链的区块中，并经过了多少个确认，但是缺少轻节点对交易数据进行验证的方式。本文提出一种化链为点的存储验证系统，能够实现轻节点各自存储部分交易数据，并且轻节点各自验证部分交易数据后，即可等价为验证了整个交易数据。而且是集存储、验证和检索为一体的系统结构，能够提供轻节点对任意部分数据的检索和验证，并且对“点”的验证完成后，即可等价为验证了整个“链”。

一．简介

首先回顾Bitcoin的一些技术细节。Bitcoin的区块数据主要由区块体数据和区块头数据组成。区块体数据是一定时间片段内由矿工打包的交易数据的集合，区块头数据则包含其对应区块体的交易数据生成的Merkle Tree的根哈希值，可以通过Merkle Tree的根哈希值和认证路径验证某个交易数据是否包含在该区块的交易数据的集合中。区块头数据还包含前一个区块头数据的哈希值，进而形成反（前）向连接的链式结构，本文称为区块（头）链。

交易数据则使用UTXO模型。在Bitcoin的UTXO模型中，一笔交易包含一个或多个输入和一个或多个输出。每个输入是一个对前向的未花费交易输出的引用，以及对应的解锁脚本。当对前向的未花费交易输出引用解锁后，就不能够再次引用解锁，也即不能够双花。而每个输出包含相应的token数额和锁定脚本，锁定脚本需对应的解锁脚本才能够解锁，也即创建了一个新的未花费交易输出。Bitcoin使用交易的哈希值作为交易ID（txid），引用则是txid+输出索引号（index）。但在Bitcoin中，txid并不完全是全局唯一的。在Bitcoin的BIP30中，如果之前交易的output（txid+index）都已经被花费过，则可以包含相同txid的交易，只需要utxoset中不存在相同txid的交易。

本文假设一个类Bitcoin系统，并根据UTXO模型，引用一个或多个未花费交易输出变为已花费，并且创建一个或多个新的未花费交易输出，并且不断循环的向后延伸，假设引用的txid(+index)是严格的全局唯一的，根据其连接的方式，则会形成一个DAG（Directed Acyclic Graph）有向无环图的链式结构，因为后一个交易引用的是前一个交易的txid+index，所以也是反（前）向连接的，本文称为UTXO链。

可以看出如果引用的txid(+index)不是全局唯一的，就不能够形成链了，而是构成了环。正是因为交易数据能够形成一条UTXO链，所以才能使用本文提出的一种由链转化为点的存储和验证系统。

二．链转化为点

Bitcoin系统使用的是Gossip网络协议，也叫Epidemic Protocol （流行病协议），是一种非结构化的对等网络协议。

本文所描述的类Bitcoin系统，矿工等全节点同样使用Gossip网络协议，但轻客户端节点则使用DHT（Distributed Hash Table）分布式哈希表，是一种结构化的对等网络，具体可以使用S/Kademlia网络协议。DHT能够在不需要服务器的情况下，使每个节点负责一小范围的路由，并负责存储一小部分数据，从而实现整个DHT网络的寻址和存储。也即根据索引的key将对应的value分散存储在网络的节点中，可以使用索引的key在网络中快速检索对应的value。但本文中的key-value与通常的DHT不同，允许有多个value具有相同的key值，并且规定了相同key的不同value存储与检索的方式，也即本文介绍的连接存储（或称为结对存储）方式。

首先从最简单的单一输入输出的链开始，比如非同质化的token形成的一条反向连接的UTXO链，后一个交易引用了前一个交易的txid。假设第一个交易A1的txid为Hash(00A1)；第二个交易所引用的值为Hash(00A1)，第二个交易A2的txid为Hash(00A2)；第三个交易所引用的值为Hash(00A2)，第三个交易A3的txid为Hash(00A3)；以此类推。对应的连接信息是txid，并且根据连接的相关信息可分为输入数据和输出数据。比如这里A1与A2可以分别看作一个是输入、另一个是输出，并且相关的连接信息Hash(00A1)是A1的输出地址，同样Hash(00A1)是A2的输入地址。将Hash(00A1)作为key，可以归纳为key对应的是输出地址，则为连接存储的输入数据；key对应的是输入地址，则为连接存储的输出数据。所以存储Hash(00A1)的节点，会将A1存储为输入数据，A2存储为输出数据；存储Hash(00A2)的节点，会将A2存储为输入数据，A3存储为输出数据。如果链在一直增长，假设当前的最后一个数据为An，所以存储Hash(00An)的节点，只会存储输入数据An，而输出数据为空；当链新增加A[n+1]时，该节点才会包含输出数据A[n+1]；而存储Hash(00A[n+1] )的节点，也只会存储输入数据A[n+1]，输出数据则为空。第一个交易的输入引用使用特殊的0000值，由于0000是A1的输入地址，所以存储0000的节点，只会存储输出数据A1，而输入数据为空。但由于0000是特殊的起始地址，也即能标识为起始连接存储，所以起始连接存储可以使用一个特殊的0000数据（或空数据）作为输入。

如果节点只有输出数据而没有输入数据（除特殊的起始连接存储外），则该链的连接错误；如果节点只有输入数据而没有输出数据，则该输入数据必定会在上一个节点中连接存储且为输出数据。连接存储是指节点存储一个或多个输入数据和对应的一个或多个输出数据，并且该节点能验证输入、输出数据是否正确；也可以没有输出数据，表示输入数据的连接未被引用或未花费。

如果是类Bitcoin的同质化token形成的反向连接的UTXO链，则是可以有多个输入和多个输出的DAG链。此时的连接信息为txid+index。同样使用txid作为key，也即key可以是连接的全部或部分信息。假设交易Tc，输入引用为Ta[1]和Tb[2]，有两个输出Tc[1]和Tc[2]，其中Ta和Tb是两个输出交易；交易数据Td，其中的输入引用为Tc[1]；交易数据Te，其中的输入引用为Tc[2]；括号内的数字为index。所以存储txid(Ta)的节点，会存储Ta作为输入数据，以及Ta作为输入引用的输出数据Tc；存储txid(Tb)的节点，会存储Tb作为输入数据，以及Tb作为输入引用的输出数据Tc；存储txid(Tc)的节点，会存储输入数据Tc，以及输出数据Td和Te。这里的两个输出数据Td和Te的输入分别是Tc[1]和Tc[2]，所以根据txid+index，连接存储根据连接信息是一一对应的。如果输入引用的txid是各不相同的，则连接存储不会有多个输入数据，但可能会有多个输出数据；如果输入引用的txid有相同情况，比如Ta等于Tb，则连接存储会有多个输入数据（txid相同但index不同，可看作为是独立数据），并且连接存储根据连接信息是一一对应的。

当节点形成连接存储时，会验证输入、输出数据是否正确，包括验证解锁签名是否正确，输入数据的连接是否未被引用或未花费（有无双花），如果包含token，还需验证输出数据的交易数额是否正确。比如存储txid(Ta)的节点，需要验证Ta[1]+Tb[2]是否等于Tc[1]+Tc[2]；同样存储txid(Tb)的节点，也需要验证Ta[1]+Tb[2]是否等于Tc[1]+Tc[2]。由于类Bitcoin的交易中，输入只是引用，并不包含实际的数额，所以验证输出数据的交易数额，其中输入数额的部分就可以来自输入数据的输出数额。所以存储txid(Ta)的节点，会存储Tb作为附加验证数据完成验证；存储txid(Tb)的节点，同样会存储Ta作为附加验证数据完成验证；而存储txid(Tc)的节点，并不需要附加验证数据即可完成Tc[1]+Tc[2]是否等于Td+Te的数额验证。上述验证还包括相应解锁脚本的签名验证以及未双花验证。

其它节点查询相应的key时，连接存储的节点会返回相关的输入数据和输出数据，以及附加验证数据。查询节点也可以对返回的数据进行验证，验证方式与存储的节点相同。比如返回的数据只有输入地址包含key，则表示只有输出数据，而没有输入数据，链的连接错误；如果只有输入数据，而没有输出数据，则表示该地址未被引用或未花费。并且能在只有单向连接的链上，具有双向检索的能力。比如检索txid(Ta)，就能获取连接存储的Ta和Tc，以及附加验证数据Tb，可以对数据进行验证；然后再对txid(Tc)进行检索，获取下一个连接存储的Tc、Td和Te，所以具备正（后）向检索的能力。

上述通过连接存储使DHT的轻客户端节点可以验证链的连接是否正确，但无法验证链的长度是否正确，也即如果缺少链的最后几个数据，通过连接存储是无法验证的。可以在区块头中添加当前所有的累计交易数据量，以及矿工随机生成的一个公钥数据P，并且矿工所打包的交易数据集合根据其生成的Merkle Tree对应的位置进行排序，对每个交易数据添加全局的累计递增序号并用公钥P的私钥进行签名。假设每个轻客户端节点正确同步了区块（头）链，则可以根据当前区块头里的累计交易数据量和前一个区块头里的累计交易数据量得到当前区块对应的交易数据集合的起始序号和结束序号，以及集合的数量。所以对应Merkle Tree的叶子节点数量和交易数据所在的序号（即位置）都是已知的，则交易数据所对应的认证路径的高度和方向都是固定且已知的（其中方向是指路径的左右方向）。所以也表示交易数据是有序的，不能用不同的认证路径以及高度和方向来替代，加强了数据的安全性。根据每个交易数据里的序号，可以快速查找到该交易数据所在的区块，然后可以根据区块头里的公钥P验证序号，再结合区块头里的累计交易数据量得到认证路径的高度和方向，使用Merkle Tree验证该交易数据是否包含在该区块的交易数据的集合中。所以上述连接存储的数据以及附加验证数据都需要包含认证路径，可以根据序号快速找到所在的区块，然后使用Merkle Tree验证是否为链上的数据。

交易数据里的序号可以通过类似地址方式进行扩展(如补0)，并通过特定的前缀明确区别，作为编号地址，比如序号为1的交易数据可以用F0001作为编号地址。使用编号地址作为key，对应的交易数据作为value，并包括对应的Merkle Tree认证路径，存储在DHT的轻客户端节点中。每个轻客户端节点正确同步了区块（头）链后，则可以根据区块头里的累计交易数据量得到该区块的所有交易数据的编号地址，然后节点可以根据每个编号地址查询自己的网络标识是否匹配该key，如果该key应该由自己存储，则可以从轻客户端的DHT网络中或全节点的Gossip网络中获取该key对应的value数据进行存储。然后对交易数据里的输入引用地址的key进行查询和验证。根据上文可知，输入地址的key对应的是连接存储的输出数据，编号地址的存储节点可以对key进行查询同时附加value数据，连接存储的节点可以对输出数据进行验证，也可以获取附加验证数据，并将相关联的数据返回给查询节点进行验证。编号地址的存储节点还可以对输出地址的key进行查询同时附加value数据，连接存储的节点会存储为输入数据。上述所有的key关联的value数据都包含Merkle Tree认证路径，可以验证是否为链上的数据。

可以看出本系统全节点Gossip网络与轻客户端节点DHT网络在检索上的不同。全节点网络能检索编号地址，返回对应的交易数据和认证路径；而轻节点的DHT网络，除了能检索编号地址外，还能检索连接存储的key，返回对应的输入数据、输出数据、附加验证数据和认证路径，反映的是交易数据DAG链上的一个连接。

通过连接存储和编号地址的方式就能验证链的连接和完整性是否正确，但上述都是存储的相关节点才会验证的。可以通过客户端随机选取的验证方式，增加系统的安全性。每个轻客户端节点正确同步了区块（头）链后，可以从已知的编号地址中随机选取部分编号地址，查询相应编号地址的key，得到相关的value交易数据；再从交易数据的输入地址的key，查询和验证连接存储的正确性。而每个节点都是独立随机选取交易数据进行验证，所以并不会知晓某个交易数据被哪些节点选择验证，也就能避免某个数据只被特定节点验证。

再分析特殊的起始连接存储，该存储的是发行交易，也就是Bitcoin中的Coinbase交易。Coinbase交易中的输入引用地址txid都是0，index为固定的FFFFFFFF，所以存储该key的节点，会存储所有的Coinbase交易为输出数据，这样并不方便检索和验证，txid+index也不符合一一对应的特性。可以根据Coinbase交易所在区块的高度进行编号，并通过特定的前缀明确区别，作为发行地址。通过发行地址作为起始连接存储的key，则会将发行交易分散存储在不同的节点上，客户端可以通过区块头的高度得到发行地址，并对该地址进行检索。Bitcoin的Coinbase交易奖励是包含出块奖励和交易手续费两部分，所以起始连接存储需要Coinbase交易所在区块的所有交易手续费才能够验证，如果需要区块里所有的交易数据，则会使验证变得比较困难。这里有两种方法，第一种是每个交易都使用固定的手续费，起始连接存储的节点根据区块头里的累计交易数据量就能得到该区块所包含的手续费；第二种是矿工在打包的交易数据添加累计递增序号的同时，为每个交易添加当前区块所包含的累计手续费，也即除Coinbase交易外，每个交易的累计手续费为前一个序号交易的累计手续费加上本交易的手续费，这样起始连接存储的节点只需要获取本区块的最后一个编号地址的交易数据，该交易数据的累计手续费即为本区块所包含的手续费。但该方式需要每个编号地址的存储节点（除起始连接存储外），获取上一个编号地址的交易数据，然后验证本编号地址的交易数据的累计手续费是否正确。该验证方式类似连接存储，上一个编号地址的交易数据为输入，本编号地址的交易数据为输出。最后起始连接存储的节点就能够比较容易的验证Coinbase交易的奖励数额是否正确。所以发行交易也是可以符合连接存储规则的，比如其中输入的是区块里最后一个编号地址的交易数据的累计手续费。

每个轻客户端节点正确同步区块（头）链后，因为区块头的一致性可以映射每个区块的交易数据的一致性，从而映射系统状态的一致性，所以每个节点的系统状态都是一致的。再通过上述的连接存储验证链的连接是否正确，以及通过编号地址验证链的完整性，就能使每个节点存储部分账本数据和认证路径，并验证相关数据是否正确，就能等价为验证全部账本数据的正确性，本文称为等价验证。这样就将链式结构转化为节点存储和验证的方式。

系统还提供了数据的检索功能，能够根据区块（头）链检索编号地址，以及连接信息的key检索连接存储的交易数据并返回给客户端进行验证。所以还可以使用客户端独立随机选取验证的方式，增加系统的安全性。并且当多个客户端，共同完成检索和对“点”进行验证后，即可等价为共同对整个“链”完成了验证。

三．链生成时的应用

上述的应用是在链生成之后，由客户端节点对区块（头）链进行同步并存储和验证区块里所有的交易数据，使用连接存储验证链的连接是否正确，使用编号地址验证链的完整性。链生成时也可以使用连接存储验证链的连接是否正确。

一般共识算法能处理的数据量都有一定上限，所以需要继续扩大能处理的数据量，一般都是使用分片分组的方式，每组处理各自的数据，分片之间需要跨分片交易。本文也使用分组的方式，比如使用一致性哈希算法将交易数据分散到m个共识组中，一致性哈希算法也是一种DHT的算法实现。使用交易数据的哈希值也即txid作为key，根据上述UTXO形成DAG链，则每个txid都是唯一的，所以每个共识组中都不允许有相同key的交易。该key同时也是交易数据的输出地址，根据上述连接存储，该交易数据被存储为连接存储的输入数据，并且一个交易数据只会在一个对应的共识组中存储为输入数据。这里与客户端不同，生产链时并不需要验证链的完整性，只需要验证UTXO链的连接是否正确。假设交易Tc，输入引用为Ta[1]和Tb[2]，有两个输出Tc[1]和Tc[2]。此时存储txid(Tc)的共识组会根据交易Tc的输入引用Ta[1]和Tb[2]，对存储txid(Ta)和txid(Tb)的共识组发起查询并附加Tc数据，此时Tc尚未上链。存储txid(Ta)的共识组会验证Ta是否已上链，并且对应的Ta[1]是否未被引用，如果已被引用，则返回错误，然后验证Tc中Ta[1]的解锁脚本是否正确，否则返回错误，然后标识Ta[1]被引用，并返回Ta[1]的输出数额；同样存储txid(Tb)的共识组会验证Tb是否已上链，并且对应的Tb[2]是否未被引用，如果已被引用，则返回错误，然后验证Tc中Tb[2]的解锁脚本是否正确，否则返回错误，然后标识Tb[2]被引用，并返回Tb[2]的输出数额；存储txid(Tc)的共识组会根据返回的Ta[1]和Tb[2]验证Tc的输入数额是否等于输出数额，验证成功后会将Tc共识上链。最后由每个共识组共识上链的数据组成区块中的交易数据集合。存储Ta和Tb的共识组会验证Tc是否已上链，如果已上链，则会连接存储Tc为输出数据，否则会去除被引用的标识。

这里描述了一个简单的根据一致性哈希算法将交易数据分散到多个共识组中进行存储、验证，然后上链。与现有的分片方式不同的是，本文的共识组并不会拥有自己的子链，而是共同组成了一条UTXO链，所以不需要跨分片交易，并且每个共识组只需要存储、验证和共识各自的数据即可，共识组之间也只需要有限的查询和验证。通过连接存储验证UTXO链的连接是否正确，从而能够生成正确的UTXO链。并且根据一致性哈希算法，还可以灵活的调整共识组的数量，能更好的适应变化的场景。

四．其它

上述DHT网络的客户端节点提供了存储、验证和检索的系统，但也可以有不参与提供存储和检索的客户端节点。矿工一般有挖矿奖励作为激励，系统可以提供减免手续费作为奖励激励客户端参与提供存储和检索，以提高系统的分布式能力和安全性。

类Bitcoin产生新的区块后，并不是立即可信的，一般需要经过几个确认才能达到可信的状态，中间可能会发生分叉等。DHT网络的客户端节点同步新的区块头后，可以不立即对区块数据进行存储和验证，而是经过几个确认，再对确认后的区块数据进行存储和验证，并且一般的SPV验证也需要经过几个确认才能有效。

五．功能和优点

1. 能够将一条类Bitcoin的链（需要具有UTXO链），通过由链转化为点的方式，将其映射到客户端的DHT网络中。每个节点各自存储部分账本数据，并且节点各自验证部分账本数据后，即可等价为验证了整个账本数据。
2. 客户端的DHT网络提供对任意部分数据的检索和验证，可以使用客户端独立随机选取验证的方式，增加系统的安全性。所有的客户端同步一致的区块（头）链，所以具有全局状态一致性。多个客户端并行完成对“点”的验证，即可等价为验证了整个“链”。
3. 生成链时也可以使用连接存储验证链的连接是否正确，由链转化为点并将其分散到多个共识组中，以处理海量的数据，并能灵活的调整共识组的数量。
4. 通过连接存储使只有单向连接的链，具有双向检索的能力。比如可以通过txid查询该交易的输出是否为被引用或未花费，如果已花费，也将返回引用的交易，以提供验证。
5. 编号地址使每个交易数据有序，并且对应的Merkle Tree认证路径的高度和方向都是固定且已知的，加强了数据的安全性。

六．总结

在类Bitcoin中可以有两条链。一条是现有的区块（头）链；另一条是交易数据组成的UTXO链，并且是DAG的链式结构。区块（头）链可以反映一致的状态，并且可以使用Merkle Tree验证是否为链上数据，并验证其是否被篡改。而UTXO链可以通过连接存储由链转化为点的方式，将UTXO链转化为节点存储和验证，无论是在生产链时，还是客户端同步链数据，都能存储和验证处理海量的数据，以验证链的连接是否正确，包括是否引用正确的未花费交易输出、有无双花、交易数额是否正确等。再结合编号地址对链的完整性进行验证，以及独立随机选取验证的方式加强安全性，就能将一条类Bitcoin的链通过等价验证的方式，在结构化对等网络的分布式节点中存储和验证该链是否正确，从而达到验证整个账本数据是否正确的目的。

参考

1. S. Nakamoto, “Bitcoin: A Peer-to-Peer Electronic Cash System”. https://bitcoin.org/bitcoin.pdf，2008.

注：文本中的相关技术已申请PCT专利，未经许可不得使用。