VCBB开发日志

Posted by szh on 2019-07-27

由于一些奇奇怪怪的原因,ToyBC 的开发鸽到开学(小饼干)

2019.7.27

VCBB 本体已经写了三天了,Master 端基本要写好了,但是发现耦合比较严重不容易测试,但是有些细节确实要先写出来才能考虑到,可能在测试前要重构一部分。
今天写了 Tracker 部分,文件传输部分三个写完了两个,分别是 Transport,Tracker,还剩一个要和合约打交道的 Download
Master 和 Slave 本来应该用 RPC 交互,但是因为底层的 peerList 实现还不清楚,自己搞了个奇奇怪怪的玩意出来,现在的实现是这样的:每个 Job 或者 Tracker 或者 Transportation 的 Session 按自己的 ID 向 peerList 申请一个 Instance 用作统一的出入口,三种不同的 Session 按方法名向 Instance 注册各自的 chan,收发对应的信息的时候按方法前缀确定对应的 Channel,格式大概是"ID/MethodName/Param",不过信息类型都是统一的[]byte,具体格式由各自方法 Unmarshal 出来,对于每个 Job 生成一个随机的 JobID,这一个 Job 执行结束后会有后续的答案分发的过程,对应的 ID 是 JobID 加上前缀,这样使得下一轮的 Slave 可以方便地下载到数据。以后能跑起来了再看看怎么搞可以上 grpc 罢。还有一件很重要的事情是数据提供者的数据是按数据的 hash 进行索引的而不是 partition 的 ID,partition 的 ID 仅仅在解释执行的时候起到数据的链接作用,在不同节点间的数据传输时不起作用
今天写了 Scheduler 的启动和监控
今天发现了一个严重的问题,如果把答案不做处理直接发到合约上的话会导致作弊行为,暂时想到的解决方法是 Master 对每个 Job 生成一个随机数,对于每个请求 Metadata 的参与者,Maste 利用随机数和参与者的地址生成一对密钥,参与者使用密钥加密答案后上传至合约,以后确实要注意以下合约是公开的这个问题
仔细考虑了一下决定答案的验证方式只支持多数表决,这样就可以在 Terminate 的时候委托合约进行确认,从而杜绝 Master 作弊的情况发生,之前也考虑过别的验证方式,但其实讲道理正确的答案肯定是大多数节点得到的答案(不考虑浮点数精度问题),但是下载合约还是没有一个有效的办法保证在合约结束的时候合约发起者有出格的行为,想不出一个可靠的办法证明一个下载确确实实正确地完成或者是失败

在写的时候有一些地方有别的想法但是现在暂时没功夫实现,在这里列一下:

  • 加入了流程控制边使得调度器可以只负责用朴素的算法执行计算图,对计算图的优化可以交给专门的优化器执行,由优化器添加控制边或合并计算节点来进行专门的优化操作。
  • 调度器的容错机制暂时没写,按照之前的设计,在某个计算节点超时失败之后,可以按照执行的结果进行检查并重启部分计算节点,这也是现在 JobID 和 NodeID 不一致的原因,JobID 在每个 Job 初始化时生成,一个 Node 可能由于计算失败生成很多次 Job,如果每次都用一个就会导致”RPC”冲突

2019.7.28

今天写了下 Slave 端的代码,改了以下 peerList 的部分让他支持全局的 RPC 和对某个 session 的 RPC
在 Slave 端应用了一个比较基础的调度策略:在满负荷时,如果收到一个新的计算请求,可以选择一个最没有希望的停止,没有希望体现在参与人数的一半已经明显超出受奖励人数
今天又想到一个很重要的事情,在合约中,计算出正确答案的后几名需要支付一定量的罚金,其总和与前几名相等,这样使得伪造多重身份作弊的行为无法获利,由于合约执行状态得到确认的滞后性,在一定时间范围内 Slave 无法通过观察合约状态判断自己提交正确答案后的奖罚情况,从而无法采取优化策略
然后在这里分析一下共有哪些途径来控制对上层的 SybilAttack:

  • 合法节点要求账户中必须有一定数量的余额
  • 合法的节点需要有合法的 nonce 值
  • 消息传递需要合法的 nonce 值
  • 只有在从 Master 节点处获取到公钥后,Slave 上传至合约的答案才有意义
  • 上传答案需要押金
  • 计算任务的 partition 中随机掺杂有事先已知答案的部分,在这部分的答案不一致时,Master 会排除上一轮的作弊节点并重启计算任务
  • 合约保证利用多个身份进行作弊不会获利

2019.8.6

之前因为一些事情鸽了一星期,期间重新整理了一下思路,在这里都列一下。

  • 整个框架包括 Master 端,Slave 端、peerList 和 VCFS。

    • Master 端只负责按静态计算图发布计算任务并监控 Slave 的执行情况,客户端或计算图优化器或其他调度器通过 RPC 与 Master 交互
    • Slave 端只负责接受计算任务,解决数据依赖问题并将其交付给执行引擎,不负责计算机底层资源调度及任务实际执行,执行引擎与 Slave 端通过 RPC 交互
    • peerList 负责在节点间建立有效连接,维护信任度
    • VCFS 提供文件服务
  • 计算合约运行原理:

    • master 在发布任务时创建一个 job 对应的计算合约,所有参与者需将得到答案的 hash 上传至合约,运行结束时由合约选择支持者过半的答案作为确定的答案,选择“最早”得出正确答案的几位参与者给予奖励
    • 为防止 slave 作弊,采取以下策略:
      • 参与者提交答案时需持有 master 对参与者账户及 jobid 的有效签名
      • 参与者提交答案时需提交一定数额押金,答案错误者扣除押金
      • 参与者提交的答案经过特定算法混淆,防止跟风
      • 参与者只能提交一次答案
      • 得出正确答案的前几名参与者的赏金由后几名参与者支付
    • 为防止 master 作弊(不终止合约或恶意终止合约),采取以下策略
      • master 在创建合约时需要上传押金,通常数额远大于 slave 需要上传的
      • 合约发现不存在答案超出一半,扣除 master 所有押金
    • 混淆算法(暂定):对于一个 job,master 随机生成一个 32 位的 key,并寻找一个 64 位的素数 p,对于每一名参与者,master 计算出 w=hash(concat(key,addr))并取前 20 位交给参与者,参与者计算 x=(ans**w)%p 上传至合约。在合约结束时,master 提供 key,p 以及 ans 模 p 的乘法逆元,合约即可还原出 ans。
  • 计算合约的 specification

    • 状态:preparing running terminated aborted ruined
      • preparing:合约成功创建但没到规定的生效时间
      • running:合约在生效时间之后,创建者调用 terminate()方法之前,接受提交答案
      • terminated合约在 terminate()时满足以下条件即达到 terminated 状态:
        • 出现某个 ans,其提交者数量大于 participant 总数量的一半
        • 提交该 ans 的参与者数量大于等于设置给予奖励的参与者数量的一半
      • aborted合约在 terminate()时满足以下条件即达到 aborted 状态:
        • 出现某个 ans,其提交者数量大于 participant 总数量的一半
        • 提交该 ans 的参与者数量小于设置给予奖励的参与者数量的一半
      • ruined合约在 terminate()时满足以下条件即达到 ruined 状态:
        • 不存在任何一个 ans,其提交者数量大于 participant 总数量的一半
    • constructor(uint256 st,uint8 numParticipants,string memory id,uint256[maxParticipantCount] memory distribute)payable public
    • 参数:
      • st:合约启动时间
      • numParticipants:受奖励参与者的数量,大于零,小于等于 maxParticipantCount
      • id:合约对应的 job 的 id
      • distribute:奖金分布,有效元素均为正整数且小于minimumParticipantFund,下标从 0 开始且连续,有效元素数量与 numParticipants 相等
    • 发起合约时的 value 需大于等于minimumMasterFund
    • commit(string memory answer)public payable

      • 参数:
        • answer:participant 提交的答案
        • v,r,s,sign:participant 持有的 master 对 participant 的 address 和 jobid 的签名,要求验证通过
      • 合约处于running状态
      • 提交时间大于等于st规定的时间
      • 调用者不是 master
      • participant 不在黑名单中
      • participant 第一次提交
      • 调用合约的 value 大于等于minimumParticipantFund
    • terminate(uint32 key, uint64 p) public

      • 合约处于running状态
      • 调用者为 master
    • 黑名单:

      • master 调用commit()
      • participant 调用commit()超过一次
      • participant 调用terminate()
      • master 在preparing状态下调用terminate()

2019.8.8

这两天主要是 peerList 和重新写的 fileSystem

peerList 主要分 global 和 session,global 指全局的消息处理,session 指某个会话的消息处理,二者都可以注册一系列回调函数,都可以调用指定的 peer 的 global 或 session 的 method,相比之下 global 多了一个 broadCast 方法,用于群发到别的 peer 的 global 消息。global 和 session 都有 reply 方法,区别在 global 的 reply 调用的是发来的 peer 的 session 的某个 method,session 是调用发来的 peer 的相同 session 的某个 method
举个栗子,A 要与 B 发起一个 Session,A 首先应该建立一个 Session 并向 peer_list 获取一个 instance,然后用这个 instance 向 B 的 global 发一个消息,B 在接到这个消息以后调用特定的 method 创建一个相同 id 的 session,然后使用 session 的 reply 向 A 的 session 发消息,这样子就建立了一个 session
这个解决方案还是显得很蹩脚,之后可能参考一些 http 的框架重新改一下

然后重写了一下 fileSystem,在这个版本里,一个 file 是一对 K-V,Key 是 V 的 hash。有一组 kvStore 的接口负责实际内容的存储,fileSystem 负责维护这些文件的存储位置,并与其他 peer 同步或购买某些文件。

  • tracker:无 session,应付其他节点对某个文件位置的查询,回复它已知的拥有该文件的全部节点
  • sync:无 session,A 主动向 B 请求同步某些文件,B 在查询本地文件后向 A 回复希望同步的文件,之后 A 向 B 发送所需文件,在这些交互中,只使用全局的数据结构来维护某些文件已知 peer 的状态,而不建立一个 session 来维护某组文件同步任务的状态,具体来说,A 向 B 请求同步后,设置 B 为 waiting 状态,而后 A 接到一个 B 的下载请求,检查 B 为 waiting 后,向 B 发送文件,设置 B 为 possess 状态,而 B 在向 A 索要数据时,设置 A 为 sending 状态,B 接到一个来自 A 的文件,检查 A 为 sending 状态,将其存入本地数据库,并将 A 设置为 possess 状态
  • purchase:有 session,对一组数据的购买需要建立一个对应的合约并监控其运行状态,所以是有状态的,需要使用 session。A 向 B 购买一份数据时,A 上传一个合约,并建立一个 session,向 B 发送带有合约的请求,将 B 设置为 sending 状态,B 调用合约函数并将 receipt 与数据一同发送给 A 的 session,A 收到一个来自 B 的文件发现为 sending 状态,接受,并更新合约状态。
  • 以上所有状态都是对每个文件分别维护的
  • 某步骤出现问题后状态的设置需要进一步考虑

2019.8.14

有关数据的组织形式以及在 scheduler 中 node 间的传递方式

  • 预处理器对代码进行预处理,将 partition 划分为 job 并为所有输入输出变量生成唯一的 id
  • 划分为 job 后,预处理器为每个 job 生成 node,每个 node 中包含有以下信息

    • inputMap map[string] *struct{x,y int} 将变量 id 映射为 input 中的一个位置
    • input [][]string 该 job 所需所有的数据的 key,executer 会对其顺序读取
    • output [][]string 将 job 输出中 ans 的位置映射为变量 id
    • dependencies map[string]*dependency,一个 dependency 对应本 node 所需的一个 job,将 nodeid 映射为 node,包括以下字段

      • dependencyMeta *JobMeta 指向一个 job 运行结束的信息
      • ids []string 记录在这个 job 中所需要的变量的 id
        预处理器为 node 填入 inputMap,output 和 dependencies
  • scheduler 为所有入度为 0 的 node 生成 job 并执行

  • job 向 slave 发送 metadata,其中包含 input(直接从 node 中获取)和 filePart,filePart 的生成方式为:遍历 dependencies,从 jobmeta 的 participants 中获得 peer,将 keys 经 inputMap 映射后在 input 中查找出真正的 key
  • slave 接受 metadata 后,先由 vcfs 按 filePart 下载到数据,然后将 input 发送至 executer 顺序执行,结束后获取顺序排列的 ans 上传至合约
  • master 监控合约,获取到 ans,并统计,在 job 运行结束后,生成 jobMeta,包括:
    • participants []address
    • output [][]string
  • scheduler 得知 job 运行结束,更新 job 对应的 node 的所有出边指向的 node,遍历 job 的 output,按其遍历索引从 node 的 output 获取变量 id,由 id 和出 node 的 inputMap 获取 input 的位置并将 key 填入出边 node 的 input 中,并将 jobMeta 按 nodeid 填入出 node 的 dependencies 中

2019.9.1

现在已经可以跑测试了,之前又整理了一份比较清晰的文档
接下来要开始细化和重构,今天和昨天大概考虑了一下通信模块
通信部分有三块:Peer 数据库,PeerList 和 DHT,数据从 socket 传过来之后先经过 DHT 层,之后是 PeerList,之后到应用层,数据发送顺序相反
Peer 数据库存有后面二者需要的信息,包括:

  • 节点 id
  • 节点 RSA 公钥和 DH 密钥
  • 节点的出入 nonce 值
  • 节点的 UDP 地址和端口

PeerList 维护节点信誉值,信誉值过低的节点会被拉黑,消息不被接受,DHT 给 PL 一个[]byte,由 PL UnMarshal 成 Message Info 之后分发到 Session 和 Method 中
DHT 按 id 的异或距离维护所有可以直接联系的节点,DHT 之间通过构建在 UDP 上的一个自定义的通信协议(VCCP)联系。DHT 支持以下方法,这些方法由 VCCP 中的固定字段标识,在 DHT 层被处理,传递到 PL 层的只是其中的数据字段

  • Ping A 向 B 发送消息以确认 B 在线,B 收到后需要立即回复 Pong,DHT 为其中的每个节点设置时间间隔,到达固定的时间间隔后如果有从 A 向 B 发送的消息,DHT 会在其中附加 ping,在节点加入网络时,也会向其他节点发送不带消息的 ping
  • Pong Ping 的回复
  • Repeat A 向 B 发送请求,请求 B 向 C 发送一个由 A 签名的 ping 消息,此方法用于 NAT 穿透,B 作为中继器
  • Search A 向 B 请求获得与某个 id 的异或距离最近的一批节点的 id

DHT 对消息进行过滤,检查 VCCP 中的以下内容:

  • CheckSum
  • Nonce
  • Signature
  • 对于一个数据库中没有的 id,DHT 会随机抛弃或检查消息的来源是否已注册
  • 对于一个非 ping 消息,DHT 检查 id 之前是否 ping 过

DHT 维护“可直接联系”的节点的策略如下:

  • 一开始接入网络时,DHT 逐个 ping 数据库中保存的节点,把 pong 的节点插入 k 桶中(先到先进)
  • 在收到消息时,会把节点的通信时间更新,剔除掉 k 桶中标记为无效的节点
  • 之后在发送其他信息时,对于发往长时间未联系节点的信息,会附加一条 ping,在时限内收不到 pong 的被标记为无效

节点入网或重启时会按以下方法接入网络

  • 向数据库中的所有节点发送 ping
  • 在时限内收到 pong 的节点尝试加入 DHT
  • 超时未收到 pong 的节点利用 DHT 发起节点查找,找到可以与其直接联系的节点(DHT 中存在)作为中继发送中继 ping

VCCP 是 DHT 间的通信协议,包括以下字段:

  • FromID 20B | FromIP 4B | FromPort 4B 源节点信息 28B
  • ToID | ToIP | ToPort 目的节点信息 28B
  • Nonce 4B
  • length1 4B 从一开始到 DHTData 的字节数
  • length2 4B 整个的字节数
  • Signature 20B 对消息的 hash 的签名,Checksum 除外
  • Checksum 2B 对消息的校验和
  • Ping | Pong | Repeat | Search 方法的标志位,填充为 1B
  • DHTData 调用 DHT 方法的数据,Ping 和 Pong 方法不带数据 0B,Repeat 和 Search 方法分别带有中继节点的 ID 和需要查询的 ID 20B
  • Data 发往 PeerList 的数据,长度不定

所有数据在传输时被紧密压缩为[]byte,除 Data 外,其余部分长度为 91 或 111B