core@mtv.ac
MultiVAC Foundation
2018年5月，版本0.1
摘要 MultiVAC是为大规模去中心化应用设计的下一代高性能公链，通过可信分片技术为区块链系统赋予了可持续无限扩展的能力。MultiVAC首次提出了基于可验证随机函数选择分片节点的可信度概率模型，并将该模型运用到区块链交易、计算、存储等关键环节中，使得任务目标可以在部分节点参与的情况下达到极高的可靠性。MultiVAC将网络中的交易根据经典UTXO账户模型分片，通过可信度概率模型选择矿工记账，将公链性能提升到企业级商用水平。作为区块链领域中首个提供弹性计算模型的公链，MultiVAC创造性地提出了可验证计算任务的PoIE共识、专为区块链设计的BISC指令集、具备通用计算能力的MVM虚拟机等技术，使得开发者能够自主权衡分布式应用中的一致性，可用性和分区容忍性要求，为应用层复杂业务逻辑提供完备支持，从而更便捷地构筑多元化的公链生态体系。
关键词 区块链；分片；可信；概率模型；弹性
区块链是分布式数据存储、点对点传输、共识机制、加密算法等计算机技术的新型应用模式，是一种全球化、去中心化的技术网络。安全性、可扩展性、去中心化构成一个不可能三角。以Bitcoin[1]、Ethereum[11]为代表的公链完全不具备扩展性，全网计算能力等同于单个矿工计算能力，全网总处理能力与节点规模不相关甚至负相关（更大的通讯成本）。以EOS[13]为代表的公链尝试用超级节点解决性能瓶颈，却放弃了去中心化。以Zilliqa[16]、Dfinity[19]为代表的分片方案放弃了一定的安全性，以Plasma[28]为代表状态通道（State Channel）技术则使用了技术结合现实的手段来处理安全性问题。
目前大量研发投入到提高每秒交易数量的技术方案上。最新公链将每秒交易量提升到数千水平（e.g. EOS[13]，Seele[18]在实验环境下达到1000-3000 tps, tps = transactions per second）。但是这一交易处理速度依然受到共识制约，主要瓶颈在于单一矿工的硬件处理能力。本质上，很多公链没有实质性地突破“区块链是一个账本”的认知。
同时，网络扩张的速度和规模也不尽如人意：截止2018年5月13日12:00 Noon (UTC时间)，问世近10年的Bitcoin的全节点仅有10424个[7]，Ethereum的全节点仅有14383个[8]。账本庞大及挖矿困难，建立一个全节点本身并不具备足够收益，导致普通用户不愿意建立全节点。
MultiVAC认为区块链能否真正商用化的关键在于区块链能否提供通用计算能力，以及全网交易和合约处理性能是否能够可扩展、可增长与可适应。
据此，MultiVAC提出可信分片计算模型，旨在去中心化网络的不可信节点之间，建立一种计算上的分工与可信关系，使得全球节点可以汇总交易能力，构建成算力可以无限扩张的基础公链网络。
同时，MultiVAC将交易处理与智能合约进行独立分片设计，构建了一个具有极强支持性和弹性的区块链底层平台。DApp可实现通用计算层面上的业务逻辑，并可根据自我需要灵活选择由多大规模的节点来进行计算和达成共识。
为此，MultiVAC要解决的核心问题是：
1.如何在全网中选取若干个节点组成可信分片
2.如何通过可信分片处理网络交易并记录账本
3.如何验证节点是否诚实可信地完成了计算任务
其中问题1决定了MultiVAC如何在交易和合约层面进行分片，问题2决定了MultiVAC如何在交易分片内达成出块共识，问题3决定了MultiVAC如何将弹性计算分片应用到智能合约。
MultiVAC利用VRF构建可靠概率模型，解决了在交易和合约中如何安全、高效、随机选取分片节点的问题；采用UTXO账本分片和共识族达成片内共识，实现交易可信分片构建；设计BISC区块链专用指令集和MVM通用计算虚拟机运行智能合约，通过PoIE共识机制验证计算任务，为DApp业务逻辑处理提供了基于可信分片的弹性执行环境。
共识算法的本质是在分布式网络中如何选取一个或多个节点成为记账人。MultiVAC中关于交易处理和合约计算的分片方案都以VRF（Verifiable Random Function，可验证随机函数[3]）为基础。VRF是一种共识框架，也是数学工具。
理想状态下，区块链系统中每一个诚实节点都应该有权力参与整个网络的记账工作。共识机制创新本质需要兼顾节点选择的公平性和系统运行的效率。Bitcoin及Ethereum的PoW算法机制，保证记账节点的选取充分随机，且只有掌控超过全网51%算力才能破坏规则。PoW具备数学优雅性，充分体现去中心化的公平性，不过存在巨大的资源浪费。而以石墨烯技术为代表的DPoS算法倾向于提高系统吞吐量而牺牲节点选取随机性，并舍弃了普通节点的参与机会，牺牲数学的优雅性和去中心化的公平性换取效率优势。其他共识算法如PBFT算法[2]（O(n2)的复杂度）及其各类改良版本、RAFT算法[21]等，受限于较高的交互成本等原因，难以大规模应用于公链系统。
MultiVAC认为，Bitcoin、Ethereum的节点选择机制具有良好的随机性，并赋予所有节点平等记账权力，这是区块链系统存在和发展的基石。Ethereum还专门针对ASIC专业矿机设计ETHash，将记账权力从中心化矿场归还给普通节点。但必须承认，PoW节点选择带来巨大资源消耗，哈希计算本身不能创造实际价值。
理想的共识算法应该兼顾随机性和效率。随机性（去中心化）是区块链存在的核心意义，而现实是现有公链性能拓展决定了区块链的未来。VRF是解决这一矛盾的最佳突破方向。一个良好的VRF，应该具有以下特点：
1.VRF可验证随机数发生器，为分布式系统提供数学上严谨的随机性。
2. VRF具有不可预测、不可控制性，从数学上保证安全性。
3. VRF可以是非交互式的，传播成本低、效率高。
目前，采用VRF进行选择的区块链共识方案有Algorand[4]，Dfinity中使用的BLS算法[5]，以及Cardano中的Ouroboros Praos算法[6]。
从这一数学基础出发，完全可以将Bitcoin或Ethereum看作是庞大的现代互联网中的一个分片，而这个分片的可信度仅和Bitcoin或者Ethereum的参与节点个数相关，而和整个互联网有多大并无太大关系。故，我们有以下两个论断：
论断1：区块链系统是现实世界的一个分片。
论断2：分片内部共识的可信度主要与片内的节点个数相关。
这里的区块链可以是Bitcoin或者Ethereum，也可以是任意区块链网络，其分片强度与参与节点个数有关，参与节点越多，可信度越高。如Bitcoin全节点为10424个[7]，Ethereum全节点个数为14383个[8]。相比区块链网络而言，现实世界（即现实的N）几乎是无穷大的，现实的人、实体、设备均可以视作为一个独立的节点。而当N充分大的时候，分片的可信度只与片内的节点个数相关。而区块链系统可以视为现实世界的一个分片。
基于VRF和可信度概率模型，我们可以将全网构建成为多个分片，每一笔交易可以委派给某一个特定分片来执行。但如何设计合适的交易处理机制，以实现多个分片之间的协同交互，是一件非常有挑战性的事情。交易分片方案需要综合考虑账本如何管理、在分片内部达成的共识是否足够安全、以及跨多个分片之间的交易如何执行等问题。
现有技术方案，如Elastico[15]，Zilliqa[16]使用了统一的账本数据，虽然实现了分片处理交易，但数据之间的同步成本依然存在，本质上没有解决数据分片问题。OmniLedge[17]设计了名为Atomix的拜占庭分片原子提交协议（Byzantine Shard Atomic Commit (Atomix) protocol），实现对每一个交易的原子处理，但这一协议逻辑比较复杂，工程实现难度较大。
MultiVAC设计分片UTXO机制来解决这一问题。网络将交易根据账户分配到不同分片，同一个账户的所有支出交易在同一个分片中执行。在UTXO交易模型之下，每一个UTXO交易的输入都是一笔或多笔已确认交易，而输出不需要与交易接收方进行数据交互，如图2所示。所以当一个账户始终在同一个片内被处理时，保证了UTXO交易只对分片内数据进行写操作，对分片外账本数据均为只读操作，避免了跨片的复杂数据逻辑。此方法逻辑简单、清晰，执行效率高，易于工程实现。
账本分片的潜在问题是作恶者如果需要篡改某笔交易或想要实现双重支付，则不需要攻击全网，只需要对特定的分片实施攻击，或联合该分片的矿工实现作恶。解决的方案有两种途径，一种是动态调整用户所归属的分片，另一种是动态调整所属分片的矿工。两种方法都可以使作恶者的难度提升至攻击全网的难度，MultiVAC选择第二种方案。同时，MultiVAC在分片内共识选用PBFT、异步BFT或BA⋆等不会（或极低概率）产生分叉的算法，且一旦作恶产生错误的区块必定会留下密码学痕迹。而Bitcoin中的PoW算法并不适用于片内共识，因为分片的算力弱于全网算力，攻击者在分片内更容易占据多数算力，在分片内产生分叉。
以上，MultiVAC使用VRF构建概率模型，对账户交易和矿工节点分片，采用UTXO模型和共识族达成片内共识，完成可信分片构建。可信分片在保证安全性和去中心化的基础上，对公链性能拓展意义重大，使得区块链平台吞吐量可随节点和分片的增长而无限扩展。
对于公链上的交易来说，MultiVAC单个分片内的共识强度将足以达到极高可靠性要求，这一可靠性需要至少数百量级的单片节点数。但对于表达通用业务逻辑的DApp和智能合约而言，如果每一行代码都需要在数百上千节点上重复运行，显然过于浪费。那么，是否有办法在不可信任的去中心化网络中，通过更少或者可选有限的节点数，完成合约层面的可靠计算，并保证过程与结果的可信度呢？MultiVAC将在VRF选取分片的基础上，通过BISC指令集、MVM虚拟机、PoIE共识为DApp构建在智能合约层面上的弹性可信计算分片模型。
虚拟机为分布式节点执行智能合约提供了良好的沙盒环境。但对要具有通用计算能力和无限扩展能力的公链来说，指令集的设计也至关重要。目前主流的指令集和虚拟机设计方案比较简易，无法支撑起复杂业务逻辑与应用。
MultiVAC将建立适用于区块链系统的专属指令集BISC（Blockchain Instruction Set Computer），并基于这一指令集系统设计具备通用计算能力的虚拟机MVM（MultiVAC Virtual Machine）。
长远来看，区块链虚拟机可以直接是一台专业的硬件计算机，具有更高的计算效能，未来还具有落地成为硬件CPU的能力。区块链指令集应该是一种高效、成熟的指令集，通过支持复杂通用计算来支撑复杂上层应用。
MultiVAC基于长远愿景设计指令集和虚拟机：
1. 支持通用计算能力。简单的虚拟机和字节码，如Ethereum的虚拟机EVM[12]，难以支撑复杂应用逻辑。面向未来的智能合约和DApp要求虚拟机除了图灵完备之外，还要求指令集能支持更复杂的计算逻辑。
2. 支持高级语言，具有良好的编译生态。MultiVAC是开源技术生态，支持大量高级语言并提供完善的编译生态，可支持既有程序的平滑迁移，对开发者全面友好。
3. 具有高效可行的硬件架构。现有区块链系统在将虚拟机的字节码进行解释或编译执行时，会严重损失底层硬件性能。MVM将基于成熟的开源CPU指令集进行二次设计和升级，具有进一步发展成为硬件计算机的能力，使得计算机能够天然成为MultiVAC矿机节点，同时还具备桌面计算机或移动设备所需要的通用计算能力，实现矿机和计算机的无缝切换。
5.2 BISC指令集
MultiVAC将在现代最出色的开源精简指令集RISC-V指令集基础上，升级开发区块链专用指令集BISC（Blockchain Instruction Set Computer）。
BISC是一套灵活、定制化的指令集架构。它基于成熟的开源RISC-V社区[22]，有大量成熟的指令架构体系，也有良好的开源编译生态。同时，MultiVAC对它进行区块链定制化，包括加入256位指令的处理，以及为公链运行加入哈希与签名指令。BISC的开发也将遵循开源共享原则。
BISC指令集支持一套精简而完善的指令序列。如表1所示。最后一列列举了BISC指令集包含的指令内容。BISC包含了多个指令包，其中RV表示这是由RISC-V定义的标准指令扩展包，BRV开头的是BISC新定义的扩展包。RV或BRV后跟的数字表示数据位宽，最后的字母表示扩展包的功能。其中I指令包是RISC-V的基础包，MAFD 4种指令包是RISC-V定义的标准扩展包，IMAFD 5种指令构成的集合统称为标准通用指令集（G指令）。G指令，尤其RV32G和RV64G是RISC-V社区目前重点支持和实现的基础指令集。而L和B两种指令是RISC-V定义的额外扩展包，H指令包和X指令是BISC指令集中全新定义的。
BISC指令集架构支持基于LLVM的C语言编译架构，GDB调试工具，glibc标准库等。LLVM（Low Level Virtual Machine，底层语言虚拟机）本质是编译器框架，目的是对任意编程语言，利用该基础框架，构建一个包括编译时、链接时、执行时等的语言执行器。以RISC-V为后端的LLVM编译框架将会支持Java、Go等高级语言。其架构如图3所示。
MVM（MultiVAC Virtual Machine）是为支持弹性计算模型而设计的区块链专用虚拟机，能够为图灵完备的高级语言所编写的智能合约提供高效率、可验证的执行环境，具备静态编译指令优化、运行时态指令检查、指令执行过程校验、存储空间分配调度等能力。
在分布式系统中，为了避免恶意代码对网络平台的循环攻击，以及缺陷代码对计算资源的持续占用，执行智能合约的沙盒环境应该具备解决图灵停机问题的能力。MVM采用类似Ethereum中gas计费的机制来解决此问题，对合约需要执行的BISC指令进行统计并计算费用，当成功完成计算任务或者费用已消耗完毕时，合约程序停止。
基于针对BISC指令集的gas计费机制，计算任务中的每一步都会被精确量化，这将会引导智能合约向高性价比方向演化，即在实现计算目标不变的前提下，尽可能的减少计算步骤、精简指令序列，为此MVM设计了针对性的优化与建议引擎，能够通过测试环境预执行来提示开发者计算任务的指令集规模和单条指令单价成本，以及通过编译环境为开发者提供代码优化建议。
除了可以在有限的时间内可以结束运行，在弹性计算模型中执行的智能合约还需要经过诚实性工作验证，MVM通过嵌入PoIE共识来完成此任务，因此，计算、计费、验证将融入到每段指令的执行过程中同时进行，其中需要说明的是，计费和验证过程虽然消耗计算资源，但是服务能力中必要的保障机制，与执行任务所设定的gas额度无关。当指令序列在足够充裕的gas费用保证下顺利完成，并且验证通过之后，节点将通过共识将计算结果打包发布并获得gas奖励。
为了更便捷的进行指令操作，MVM提供了面向BISC更友好的内存模型，该模型能够将计算机物理资源进行隔离，并且为合约执行提供灵活的运行时支持，内置了栈空间和堆空间。其中栈空间提供足够的调用深度，支持多种数据结构类型，并可提供批量出入栈操作，而堆空间提供自由分配的能力，支持随机寻址，同时提供监测机制对已释放资源进行回收，整体为通用计算提供基本存储保障。
MVM可以运行在所有网络节点中，提供计算服务的节点会将其通过网络接收到的计算任务纳入以指令集单价为索引的优先队列中，集中调度和执行计算任务，并交付计算结果。
6. PoIE共识
现有分片技术如Ethereum分片方案[20]、Zilliqa[16]、Elastico[15]等，对每个分片内部的节点数量有较大的要求，至少也应该是数百至数千的水平。考虑一个区块链上的分布式应用DApp，它的代码就是公链上的一个或多个合约，如果DApp的每一行代码都需要在数百上千个节点上重复运行，这个成本显然是过于高昂了。
那么，在区块链这种不可信任的节点网络之中，有没有办法可以只让少数几个节点执行代码，就可以进行计算任务的验证，还能保证计算过程及结果的可靠性？
MIT和Tel Aviv大学提出的zk-SNARKs[14]，可在无需泄露数据本身的情况下，通过证明某些数据运算的零知识证明（ZKPs, Zero Knowledge Proofs）来验证一个程序的执行。Zk-SNARKs创造了简洁的非互动式零知识证明，将交易或合约（本质上都是计算任务）看做一个逻辑回路，通过将计算编码成回路，并生成一个证明声明提供给验证者，以一种非交互式的方法来验证某个计算任务确实被执行了。
基于此可设计一种分片内部共识算法，好处是分片内节点数量非常少也可以达成较大强度的共识，并且分片外部未参与实际计算的节点也可以利用简洁方法验证计算的执行过程。这是一个非常重要的特性，即：不需要执行计算任务（如合约）本身，就可以用数学的手段去验证它。
MultiVAC提出了一种全新的计算共识算法，称为PoIE（Proof of Instruction Execution），指令集执行共识。PoIE基于物理现实而设计，不同于zk-SNARKs这样的纯数学算法。设计理论是：作恶者需要花更高的物理代价去作弊；即使作弊，作恶者获得的是经济利益，但不能更改计算结果的正确性。那么，从成本上说，作恶者更愿意诚实地执行计算任务。
PoIE的物理现实是：将一个程序看成是要执行的一串指令序列，现代计算机处理这串指令的成本远低于存储成本。事实上，现代CPU处理速度等同于CPU Cache，远大于内存读写速度。这是因为CPU是由晶体管构成，而内存则是电容材质，所以计算性能远大于存储性能。虽然CPU中的缓存Cache可以达到与CPU相同的处理速度，但即使在高端消费CPU中（如Intel Core i7系列），Cache也仅有8-12MB，并且其成本（晶体管数量）占到整个CPU的1/4至1/3。
世界上很多技术是具有美妙的共通点的。Ethereum的挖矿机制与PoIE的物理基础，在设计思想上有相似之处。为了抵御ASIC矿机，规避出现Bitcoin专业化矿机挖矿中心化，Ethereum设计ETHash[12]：矿工在PoW挖矿过程中不仅需要进行简单的哈希计算，还需要频繁、随机地读取大量的内存数据。内存读取瓶颈限制了专业ASIC矿机，避免了挖矿变成一种高度专业和中心化的工作，实现了良好的去中心化。PoIE也是利用了现代计算机的计算和存储结构的物理差异来避免作恶。
PoIE是一个嵌入到虚拟机层面的指令集共识。设计理念是将程序的执行过程看成是一串指令的执行序列，PoIE将验证这一指令序列是否真的被正确执行了。作用是在不可完全信任的网络中，验证一个计算任务是否被诚实执行，并根据执行情况给予相应的经济激励。
6.3 弹性分片计算
一个健壮而具有扩展性的公链网络，应该在计算、存储、传输三个维度上都具有良好的扩展性、安全性和去中心化。此外，还应有完善的经济体系激励更多节点加入网络，以提供计算、存储、传输服务，建立完整而具有成长性的公链基础设施。但要实现上述理想的网络平台还面临着很多学术和工程上的困难。
在存储层面，IPFS[23]设计了完整的去中心化分布式存储系统，提供了可寻址、版本化、点对点的文件系统。一些知名的公链系统已经使用了IPFS作为底层存储，如EOS。IPFS使用了filecoin[24]作为存储激励机制，其他的区块链存储方案还有Storj[25]，MaidSafe[27]，Siacoin[26]等。
与IPFS基于Hash的存储与检索方案略有不同，MultiVAC首次提出了基于Merkle Root的存储结构。这样的结构的好处是不仅仅可以基于Merkle Root值进行检索或数据获取，还支持较小的数据片段的检索和获取，以及针对片段的网络校验，包括存在性校验和真实性校验。MultiVAC中同时支持基于Hash与基于Merkle Root的数据存取与检索。此外，MultiVAC还加入了VRF分片存储机制，建立分布式去中心化存储系统。类似于Bitcoin轻节点，MultiVAC的节点只存储区块的摘要信息，真正的交易信息及合约相关输入输出都存储在分布式存储之中。值得注意的是，在MultiVAC中，数据的存储仅作为系统的底层服务被使用，存储者不能对数据进行任何修改操作。关于数据的所有产生、修改、删除、确认、共识等行为均由上层逻辑达成，底层存储服务仅保管确定性的数据并向上层提供存取功能。在MultiVAC中，节点提供计算与存储服务都会获得相应的激励。
最后，区块链网络还需要考虑数据传输的问题。如果使用分片存储账本，那么必然面临的问题是账本的存储压力被转化成了数据通讯的压力。不过IPFS已经证明了分布式的存储也带来了分布式网络传输，可以缓解中心化节点的带宽压力。
若一个节点在出块时需要处理 t 个交易：如果全网存储账本的话，则面临O(t)的磁盘IO成本，
O(t)的网络账本同步成本；如果是分片存储账本，那么就没有磁盘IO成本，同样是O(t)的网络账本同步成本，另外还需要O(t)的交易验证带来的网络通讯成本。由于交易验证可能是一个碎片化的网络通讯，所以工程实现上成本会高于本地磁盘IO。但本质上，账本分片不会增加网络传输的理论复杂度。
在传输的激励机制层面，学术界和工业界都没有一个有效的解决方案，目前仍然是一个开放的问题。即使在IPFS和filecoin的方案之中，一个存储节点可以通过PoRep和PoST两个共识来获得存储的奖励。但在网络上其他节点需要使用这个数据的时候，由于带宽成本等原因，存储节点完全可以拒绝向请求方传输数据。此外，数据传输是高频次的，每一次访问都产生对应的奖励交易也是不可能实现的，因为交易又会带来数据传输的成本，进而产生了无限递归。一个良好的传输激励机制需要综合考虑带宽、延迟、数据总传输量、请求频次等问题，这些困难也使得它目前仍然是一个等待解决的问题。不过由于传输不会脱离计算或存储而独立存在，所以传输的激励体制并不是必须的。
MultiVAC综合考虑区块链中的计算、存储、传输问题，并设计了计算与存储的激励机制，是首个实现了在计算、存储、传输三个维度可扩展的公链。
MultiVAC设计了一种通过VRF选择节点进行分片，以概率模型保证可信度的高性能公链，该架构为其上运行的智能合约提供了可以自由定义和取舍安全性、去中心化和可扩展性的弹性可信计算分片模型。MultiVAC网络的处理能力能够伴随节点数量和计算能力的扩张而持续增加；在业务支持方面，基于BISC指令集、MVM虚拟机、PoIE共识的分布式计算平台能够为公链上的去中心化应用提供无限扩张的资源供给。
（MultiVAC名称来源于科幻作家阿西莫夫《最后的问题》[29]中的超级计算机的名称。这台超级计算机，从现在我们熟知的晶体管结构，自我进化到与所有人类灵魂融为一体的超时空结构，最终在整个宇宙热寂湮灭之时，完成了终极问题“如何逆转宇宙的熵增”的计算和再现。）
[1]. Satoshi Nakamoto, Bitcoin: A Peer-to-Peer Electronic Cash System, October 31, 2008
[7]. Global Bitcoin Nodes Distribution, website: https://bitnodes.earn.com/
[8]. Ether Nodes Network Number, website: https://www.ethernodes.org/network/1
[12].Dr Gavin Wood, Ethereum: A Secure Decentrailised Generalised Trasactioin Ledger.
[13].The Block.One. EOS.IO Technical White Paper. March 2018.
[16]. The Zilliqa Team, The ZILLIQA Technical Whitepaper, 2017.
[18]. The Seele Team. Seele Tech Whitepaper: Innovate New Era of Value Internet. 2018.
[20].Vitalik Buterin. Ethereum 2.0 Mauve Paper. 2016.
[22]. [Andrew Waterman, Krste Asanovie, The RISC-V Instruction Set Manual, May 7, 2017.
[23]. Juan Benet. IPFS - Content Addressed, Versioned, P2P File System. 2014.
[24]. The Filecoin Team. Filecoin: A Cryptocurrency Operated File Storage Network. July 2014.
[26]. David Vorick and Luke Champine. Sia: Simple Decentralized Storage. Nov 2014.
[28]. Joseph Poon and Vitalik Buterin. Plasma: Scalable Autonomous Smart Contracts. August 2017.
[29]. Isaac Asimov. The Last Question. Science Fiction Quarterly. Nov 1956
MultiVAC官网：mtv.ac
