VCBB设计文档

Posted by szh on 2019-08-24

目录

总体介绍

VCBB(Volunteer Computing Based on Blockchain) 是一个基于区块链的志愿计算框架,志愿计算技术希望充分利用公众的闲置计算资源为科学研究项目提供计算力。而 VCBB 借助区块链技术实现了对部分志愿者的金钱奖励,这有助于调动公众对参与志愿计算项目的积极性。VCBB 利用智能合约以及信誉系统较好的解决了在去信任环境下引入金钱奖励带来的恶意节点欺诈问题,利用冗余和密码学技术提高了计算结果的可靠程度,利用基于 DAG 的任务调度技术为大型的计算任务提供了容错和良好的并发性。同时,VCBB 为志愿计算程序开发者提供了统一的编程模型,这使得开发者能够专注于算法本身而不是网络通信或任务调度,开发者只需把源数据上传至数据库并利用客户端发布编写好的代码即可利用 VCBB 网络中的大量志愿者节点完成计算任务。VCBB 框架作为中间件,通过网络与系统外的其他组件连接,可以灵活地支持多样的奖励规则、计算任务优化和志愿者端任务调度策略

软件架构

节点角色

NodeCharacter
在网络中,节点可以有以下三种角色,一个节点可以同时拥有有多种角色:

  • Master 发布计算任务
  • Slave 接受计算任务并执行
  • Storage Provider 为 Master 和 Slave 提供数据存储服务,网络中每个节点都是一个 Storage Provider

在系统之外,还有提供区块链相关服务的全节点,在区块链系统上运行有节点状态合约,用于维护系统中所有节点的公开状态

基础服务

BasicArchitecture
根据节点角色不同,每个节点运行的软件架构有所不同,但所有节点都有共同的基础服务架构,基础服务由以下部分组成:

  • DHT 和 PeerList 提供网络通信服务
  • Blockchain Handler 与区块链进行交互
  • KV Store 进行实际键值对存储
  • File System 维护文件状态,进行文件同步和获取

Master 架构

MasterArchitecture
Master 节点需要对用户提交的计算任务进行解析和发布,并监控计算任务的执行状态。在基础服务的基础上,Master 节点具有以下部分:

  • Client 面向用户,将用户提交代码进行任务分解并转化为计算图,提交给 Server
  • Server 与 Client 使用 web Socket 或 http 进行通信,接受 Client 提交的计算图并发起计算任务,并将结果返回给 Client
  • Scheduler 实际根据计算图发起计算任务并对任务进行调度

在 Master 方面,有一部分模块对计算任务的提交和运行也起着重要作用,而这些模块根据用户偏好不同具有多样的实现方案,因此这些模块不被纳入软件范畴而是由用户自行决定:

  • Optimizer 将一般程序转化为 Master 接受的格式,并对计算图结构进行优化
  • Broker 根据市场情况决定计算任务对 Slave 的奖励策略

Slave 架构

SlaveArchitecture
Slave 节点需要接受 Master 发布的任务并执行。在基础服务的基础上,Slave 节点具有以下部分:

  • Scheduler 接受 Master 发布的任务,判断是否执行,并将任务交给 Executor 执行

根据 Slave 节点自身情况,Executor 有多种任务调度和执行策略,因此不属于本项目
与 Master 类似,Slave 也应有一 Broker 模块用于判断执行计算任务的成本和收益,同样这一模块也不属于本项目
Executor 和 Broker 与 Scheduler 利用 web socket 或 http 进行通信

节点状态合约

节点状态合约是运行在区块链上的单例合约,接入系统的节点需要调用合约支付押金并提供用于通信的 RSA 公钥进行注册,合约支持两类节点的注册:

  • 普通节点:具有较差的硬件配置和网络环境,不定时地进入或退出系统,支付较低的押金
  • 基础设施节点:具有较好的硬件配置和网络环境,能够长时间稳定地在系统中提供服务,支付较高的押金并需要提供自身 ip 和端口信息,此类节点可以为网络系统提供节点发现服务,也可以提供较为稳定的文件存储服务

合约公开地记录所有注册节点的账户地址和 RSA 公钥并维护其信誉信息,对于基础设施节点,合约还会公开其网络信息

网络系统

总体结构

VCBB 的节点由区块链账户作为唯一 id,所有节点建立在一个由 sKad 协议构建的 DHT 上,该 DHT 维护所有邻接节点的 ip 地址及端口等信息,提供节点查找、消息发送等服务。在 DHT 的基础上,每个节点维护一份 Peer 列表,其中包含该节点信任的其他节点 id 和信任度。应用层的消息经 Peer 列表处理后传递至 DHT 发送。节点间的消息除文件传输使用 TCP 协议之外,均使用 UDP 协议进行传输,在传输过程中,由于目的节点的公钥可以在节点状态合约上查询,节点间可以使用 RSA 算法进行加密通信

DHT

DHT 承担以下任务:

  • 节点查找:按节点 id 查找到确切节点的 ip 和端口
  • 消息路由:将消息发送至目标 id
  • 连接建立:在两个节点间建立一条用于文件传输的 TCP 连接

DHT 按照节点 id 维护了不同异或距离上其他节点的 ip 和端口信息,接受 PeerList 传递的消息并将其发送至目标节点
DHT 具体选用 sKad 协议,该协议在正常路由功能的基础上通过不相交路径路由和工作量证明等方式对 sybil attack 提供了一定的防御能力

PeerList

PeerList 承担以下任务:

  • 记录所有已知的可信节点 id
  • 维护列表中节点的信任度
  • 提供身份证明及验证
  • 在应用层和 DHT 层间传递消息,对应用层不同 session 的消息提供多路复用

PeerList 在应用层和 DHT 层之间传递消息,对于应用层的消息,PeerList 对其进行签名并传递至 DHT 发送,对于 DHT 的消息,PeerList 对签名进行验证并传递至应用层的特定 session。PeerList 利用信任度机制控制了应用层可以实际进行通信的节点范围。节点间由 PeerList 维护的邻接关系在 DHT 层上形成了第二层由信任度构成的拓扑结构

节点发现和接入

新加入的节点需要生成一对用于加密通信的 RSA 密钥并调用合约进行注册,此后可以向节点状态合约查询基础设施节点并向其请求同步 DHT 和 PeerList,此后即可按照正常 DHT 接入流程接入网络
暂时退出的节点在重新接入网络时需要向其 DHT 的邻居节点重新发送自身网络信息

离线消息(设计不明确)

利用节点状态合约,可以向暂时退出系统的节点发送离线消息

文件系统

总述

每个节点都有一个文件系统用于维护自身文件状态并与其他节点进行文件传输,文件系统建立于键-值数据库之上,承担以下任务:

  • 维护文件在本地和其他节点的分布信息
  • 响应其他节点对文件状态的查询
  • 主动向其他节点同步某一文件
  • 发起文件购买合约向其他节点购买文件

文件实际存储于数据库上,在文件系统中注册文件信息后才可以被节点识别,文件系统是数据库存储的入口之一,Master 的 Client 和 Slave 的 Executor 也可以读写数据库

文件

一个文件是存储于数据库上的一对键-值,其中键是值的 Hash。文件在存储后只能被删除而不能被修改。
一个文件有以下状态:

  • waiting 等待文件同步至本地
  • purchasing 等待文件购买至本地
  • possess 文件存储于本地
  • unkown 其他情况

文件系统也存储已知其他节点对文件的拥有情况,对于节点 A 文件系统中的某个文件 f,一个节点 B 有以下状态:

  • waiting B 等待 A 向 B 发送文件 f
  • sending A 等待 B 发送文件 f
  • possess B 拥有该文件 f,且 AB 之间无交流
  • unkown 其他情况

文件同步

节点 A 的文件系统可以根据需要主动请求节点 B 存储 A 的某一(批)文件 f,称为文件同步
在同步过程中,A 首先向 B 发送同步请求,并将 f 关于 B 的状态修改为 waiting,B 接到请求后判断可以接受同步,建立 f 的信息,并将关于 A 的状态置为 sending,之后向 A 发送 Accept。A 接到 Accept 信息后确认 B 状态后与 B 建立稳定传输,并向 B 发送 f。二者在确认文件正常传输后将 f 关于对方的状态修改为 possess,完成同步过程。在过程中二者对对方的状态和文件状态设置超时,在对方无响应超过超时后恢复文件状态
在完成同步后,B 需定期向 A 发送心跳信号并等待 A 对心跳的响应,在 A 无响应超时后不再发送心跳。信号中无需包括文件状态,而在 B 删除文件 f 时,B 需向 A 发送删除消息从而触发文件状态改变
A 监控 B 以及其他接受同步的节点的心跳,在超时后重置节点状态。若在 B 超时后重新 A 收到来自 B 的心跳信号,A 会重新向 B 发起同步请求

文件购买

节点 A 可以向节点 B 请求购买某一(批)文件 f
节点 A 首先提交一份购买文件的智能合约并上传押金,并将合约地址和文件购买请求发送给 B。B 检查请求后向合约上传押金,与 A 建立稳定传输,并向 A 发送 f。A 在收到 f 后调用合约奖励 B 并取回押金。同一份文件合约可以处理多个文件的交易,文件交易在合约上彼此独立。如果 B 在购买时限内未能向 A 传输正确的文件,A 调用合约扣除 B 的押金。在购买过程中,A 可能通过其他渠道获取到 f,此时 A 取消文件传输,调用合约返回双方押金。由于缺乏有效方式证明文件正确传输,在购买过程中,合约调用的主动权在 A 节点处,对于 A 的反常行为,需要通过信誉系统进行处理。

文件状态维护

在运行过程中,文件系统会定期中断服务进行状态维护,状态维护包括以下内容:

  • 发现未被正常处理的超时请求并恢复与之相关的文件和节点状态
  • 清理长时间无访问的文件

对于接受的文件同步请求,如果本地空间不足,同步请求会进入一个队列中,待同步请求文件大小到达一定限制时会触发状态维护,请求队列长度达到限制时会丢弃队首的请求

编程模型

总述

DAG
向 Master Server 输入的程序按照数据依赖关系形成一个 DAG,DAG 由以下两种节点构成:

  • 计算节点 表示一组使用相同代码进行计算的任务
  • 数据节点 表示一份数据,对应文件系统中一个文件,不可分割

DAG 从初始数据节点开始,一条有向边表示数据流向或计算先后关系,由数据节点指向计算节点即表示计算节点需要该数据,由计算节点指向数据节点表示计算节点输出数据,由数据节点指向数据节点表示人为规定的计算先后顺序
在编写程序时,数据节点仅由一组从 0 开始的编号表示,用户需要编写计算节点,并将输入输出映射至数据节点编号

在编程时一个计算节点可以理解为一个函数,按执行情况分为以下两类:

  • function 对数据执行一次计算,执行结束后资源被回收
  • iterator 对数据执行多轮计算,在每轮计算结束后被挂起,等待下一轮计算

计算节点的编写

ComputeNode
计算节点表示对一批数据执行同一个操作,一个计算节点包括许多 partition,每个 partition 接受对应的输入列表,对输入执行操作后将结果输出至输出列表
在编写一个计算节点时,需要提供以下信息:

  • partitionCount 该节点的 partition 数量
  • inputCount 单个 partition input 数量
  • outputCount 单个 partition output 数量
  • inputMapper(partitionId) returns dataId 按 partition 编号将数据节点编号映射至该 partition 的 input 数组中
  • outputMapper(partitionId) returns dataId 按 partition 编号将该 partition 的 output 列表的数据映射至数据节点
  • code 单个 partition 执行的操作代码

如果编写的是一个 iterator,mapper 还接受 epoch 参数,表示迭代的轮数

计算节点向计算图的转化

用户向 client 提交一个计算节点列表,以及一个用于描述计算节点执行先后关系的二元组(u,v)列表(表示在计算节点列表中位于 v 位置的节点执行时间晚于在 u 位置节点),client 会进行如下预处理:

  • 检查确认每个数据节点只有一条入边
  • 检查确认整个图为 DAG
  • 为每个数据节点编号生成唯一的 id
  • 为每个计算节点生成唯一的 id
  • 为每个计算节点生成输入输出映射表:
    • 从数据节点 id 映射至输入数据列表的位置
    • 从数据在输出列表中的位置映射至数据节点 id
  • 为所有计算节点计算入度和出度

计算协议

总述

计算协议描述了一个计算任务执行过程中 Master、Slave 和区块链三方的交互,包括以下部分:

  • Master 向区块链提交计算合约
  • Master 向 Slave 请求执行计算任务
  • Slave 获取执行计算任务所需信息
  • Slave 提交答案
  • 运行在区块链上的计算合约对参与双方的各种行为进行奖惩

计算协议本质上是 Master 向 Slave 支付一定费用雇佣其执行计算任务的过程
一个完整的计算任务被拆分成许多子任务,这些子任务根据数据的依赖关系和事先确定的先后顺序组成 DAG,调度器根据 DAG 发布任务。一个子任务的执行对应一个计算协议的运行
在计算协议中,同一个计算任务由多个 Slave 冗余执行,其有效答案指过半 Slave 得出的答案,计算协议应尽量保证有效答案等于正确答案
在 Master 与 Slave 在去信任的环境下达成计算协议时面临以下问题:

  • Master 在得到答案后不进行奖励
  • Master 在得出有效答案之前终止协议
  • Slave 提交错误答案
  • Slave 抄袭答案
  • 恶意对象借助多个 Slave 身份提交错误答案导致合约无法执行
  • 恶意对象借助多个 Slave 身份提交错误答案导致有效答案错误

计算协议中数据的传递

计算协议中数据的传递分为以下两种:

  • 键传递:只传递数据的 hash,在以下情况下发生:

    • Master 向 Slave 传输 metadata
    • Slave 向 Tracker 查询文件信息
    • Slave 向智能合约提交答案
    • 智能合约触发提交事件
  • 值传递:传递数据自身和其 hash,在以下情况下发生:

    • 初始计算任务开始前 Master 将初始计算任务所需数据发布至相邻节点
    • Slave 购买计算任务所需数据
    • Slave 在计算任务执行结束后向邻接节点同步数据
    • Master 在计算图执行结束后将最终答案购买回来
    • Master 在计算图执行过程中保存检查点时购买数据

Slave 向 Master 请求的 metadata 由许多 part 组成,每个 part 包括以下内容:

  • keys:该 part 中文件的 key
  • peers:拥有该 part 中文件的信息的节点 id

Slave 在得到 metadata 后,需要向 peers 请求获得文件的具体位置后才可实际进行数据购买

计算协议的执行流程

CalcProc
计算合约在执行时,Master,Slave 以及区块链三方进行一系列通信,具体过程如下:

  • Master 建立计算协议的 Session,执行以下操作:

    • 为本次计算合约的执行建立 Session,生成 Session id,并为 Session 随机生成一个密钥
    • 向区块链上传计算合约,包括 Session id,Master 方的押金和奖励分配方式
    • 将合约地址、软硬件要求和测试代码作为计算请求广播至 PeerList 中
  • Slave 接收到请求后进行以下检查:

    • 检查合约正确性
    • 检查软硬件符合要求,
    • 检查奖励和成本符合预期
    • 自身有足够资源运行计算任务

    若满足要求,Slave 向 Master 发送消息请求 metadata,否则不予回复

  • Master 接收到一个 Slave 对 metadata 的请求后执行以下操作:

    • 根据 Session 密钥和 Slave 的 id 计算出一个 hashKey
    • 将 Slave id,Session id 进行签名得出 sign
    • 将 hashKey、metadata 和 sign 发送给 Slave

    若 metadata 请求过多,Master 可随机选取一部分进行回复

  • Slave 接收到以上回复,执行以下操作:

    • 向 metadata 中记录的 Tracker 节点请求数据位置
    • 根据数据位置利用文件系统购买到计算所需数据
    • 执行计算任务,得出结果 K-V 数组
    • 将结果的 Key 逐个与 hashKey 相加,将处理过的 Key 和 Master 的签名调用计算合约上传,并支付一定数量的押金
  • Master 监听合约中的上传答案事件,执行以下操作:

    • 根据收到的答案和 Slave 对应的 hashKey 还原出答案
    • 统计收到答案的数量,并记录对应的 Slave id
    • 当收到答案数量超出期望数量并出现有效答案时,Master 调用合约进行结算
  • Master 监听合约中的惩罚事件,并更新 PeerList 中的信任度信息

计算合约

计算合约运行在区块链上,负责对协议双方的行为进行奖惩,支持以下操作:

  • 建立合约:Master 在开始一个计算协议时会建立一个计算合约,需要提供以下内容:

    • Session id
    • fund:Master 支付的押金
    • rewardDistribute:奖金分配方式
    • start:合约开始接受 commit 的时间

    需要满足以下条件才可以正常建立:

    • fund 大于等于合约规定的最低限制
    • rewardDistribute 数组长度大于零,且元素值为正整数
    • 随部署合约交易发送的 value 需等于押金和奖金之和
  • commit:Slave 在得出结果后将结果上传至合约,需要提供以下内容:

    • Signature:Master 对 Slave id 和 Session id 的签名
    • Answer:运行结果的 key 数组

    需要满足以下条件才可以正常提交:

    • 合约未被 terminate,否则会回滚
    • 提交时间大于等于 start 时间,否则会被 punish
    • 调用者不是 Master,否则会被 punish
    • 调用者此前未被 punish 过
    • 调用者此前未提交过,如果重复提交相同答案会回滚,提交不同答案会被 punish
    • 调用者提供的签名有效,否则会被 punish
    • 随调用交易发送的 value 大于等于合约规定的最低限制,否则会回滚

    在提交答案后,Slave 的 id 和答案会被插入到合约维护的队尾,合约会触发 commit 事件

  • terminate:Master 在确信可以得出有效答案后,调用 terminate 方法进行结算,调用时需要上传 Session 的密钥
    需要满足以下条件才可以正常结算:

    • 合约未被 terminate,否则会回滚
    • 调用者为 Master,否则会被 punish

    结算时,合约进行以下操作:

    • 根据 Session 密钥还原出每个 Slave 的答案并统计每个答案对应的 Slave 数量
    • 如果未得到有效答案,Master 会被 punish,其余参与者的押金被退回,合约终止
    • 得出有效答案后会触发 terminate 事件
    • 根据 Master 规定的奖金分配方式对得出有效答案的 Slave 分配奖金并退回押金
    • punish 得出其他答案的 Slave
    • 调用节点状态合约更新得出正确答案的 Slave

在合约方法调用过程中出现某些行为时调用者会被 punish,对于一个调用者,punish 只会进行一次,进行以下操作

  • 触发 punish 事件
  • 扣除违规者押金
  • 将违规者加入黑名单
  • 调用节点状态合约在区块链上更新违规者信誉值

合约在运行过程中会触发以下三种事件:

  • commit:Slave 提交一个有效答案后触发,事件包括 Slave 的 id 和上传的答案
  • terminate:合约正常结算并得到有效答案后触发,包括有效答案
  • punish:对某个违规者进行惩罚时触发,包括违规者 id

异常行为处理

在计算任务可以得出有效答案的情况下,异常行为可以被有效处理
Master 不主动终止合约就无法取回押金,促使其终止合约对 Slave 进行奖励
Master 在得出有效答案前终止协议会导致押金被没收,而所有 Slave 可以正常退回押金
Slave 提交无效答案时,其押金会在结束时被没收
由于每个 Slave 得出的答案在上传至区块链时都经过不同的密钥加密处理,Slave 在合约终止之前无法通过区块链得知别人的答案
每个 Slave 在上传答案时都需要提供 Master 的有效签名,使得 Master 可以对上传答案的 Slave 数量进行控制
对于恶意对象借助多个 Slave 身份提交相同错误答案,有以下策略:

Confound

  • 在输入数据中设置多个无效位置,该位置数据不影响答案
  • Master 对每个 Slave 随机生成一个控制字符串 c,随 Metadata 返回给 Slave
  • Slave 在执行计算任务前需要根据 c 替换每个 partition 数据中的某些位置,被替换到无效位置的 partition 不被影响,替换到有效位置的 partition 被屏蔽
  • Slave 对替换操作结束后的数据进行计算并提交答案
  • Master 监听提交事件,计算出 Slave 提交的未被屏蔽的答案并更新统计结果
  • 在合约的结算阶段,合约根据每个 Slave 的 c 计算出该 Slave 未被屏蔽的 partition,如果发现多个 Slave 对同一个被屏蔽的 partition 提交了相同答案,可判定这些 Slave 作弊

执行流程

多个子任务在调度器的调度下按 DAG 规定的顺序依次执行,其总体执行流程如下:

  • Master 的调度器找到初始入度为零的 DAG 节点,将其所需数据同步至部分邻接节点,发送第一批任务
  • Slave 与 Master 进行通信并获取到 metadata,之后 Slave 与 metadata 中的节点进行通信,获取到文件实际的存储位置并进行文件购买
  • 得出有效答案的 Slave 在计算合约结算之后将本次得出的答案同步至 Peer List 中的邻接节点(优先同步至本次计算任务的消息来源)
  • Master 在结算后将本轮得出有效答案的 Slave id 记入依赖本轮计算结果的计算任务的 metadata 中
  • 调度器重新计算计算节点的入度,找到入度为零的计算节点开启新一轮计算任务
  • Master 在执行完出度为零的计算节点后,用与 Slave 找到并购买数据相同的方式将最终结果购买回来,所有计算任务结束
  • 在某些计算节点结束后,Master 也可以选择回购结果数据以建立检查点

计算节点对应一个迭代器的调用时,部分简化流程如下:

  • Master 在第一轮发送迭代器任务时流程与上述流程相同
  • Master 在首轮迭代器任务执行结束后将得出有效计算结果的 Slave id 通知下一轮迭代器任务
  • 在之后迭代器任务开始时,Master 将直接向上一轮记录的 Slave id 发送附加有合约地址的 metadata

在计算任务执行过程中,可能出现某一计算节点执行失败,此时 Master 将进行以下检查:

  • 检查提交答案的 Slave 数量是否不足,若不足,向基础设施节点请求部分 PeerList 数据发送计算请求
  • 检查上一轮答案的存储情况,向 metadata 中记录的 tracker 节点查询数据分布情况,如果发现数据缺失,将按照计算图依赖关系向前检查直到遇到结果数据保存完好的计算节点或 Master 建立的检查点,从该处向后重启计算任务

信誉系统

信誉系统维护网络中各节点中的信誉值,包括以下两种:

  • 全局信誉值:由区块链上的节点状态合约维护,由计算合约调用节点状态合约对全局信誉值进行更新,表示所有节点公认的节点可信程度
  • 主观信誉值:由每个节点的 PeerList 维护,表示从节点自身的角度判断其他节点的可信程度,其更新条件如下:

    • 全局信誉值更新会导致主观信誉值随之更新
    • 消息无响应会导致信誉值下降
    • 文件购买的结果(是否得到正确文件/是否被奖励)会导致买卖双方信誉值更新
    • 节点间相互配合(正确转发计算请求/按约定进行文件同步)会导致双方信誉值更新

节点最初加入系统时主观信誉值等于全局信誉值
全局信誉值不足者会被节点状态合约没收押金并加入黑名单,每个节点会自动将主观信誉值过低的节点移出 PeerList