YODA: Enabling computationally intensive contracts on blockchains with Byzantine and Selfish nodes

• Sourav Das, Vinay Joseph Ribeiro and Abhijeet Anand
• Network and Distributed Systems Security (NDSS) Symposium 2019

Introduction

传统公开链的结构并不适合用于大批量的计算场景（比如深度学习和零知识证明）。主要有如下几个原因：

1. 每一个合约的执行需要缴纳手续费。计算量大意味着昂贵的手续费。
2. 每个验证计算需要花费大量的时间，节点可能会选择跳过验证，以快速开始下一个区块的计算，导致安全性下降

有两种一直的改进方法，但都有缺点：

1. 将重度计算过程分散成多步骤，发在多个区块中
2. 离线的执行智能合约

文章实现了一种离线 CIC 的执行策略，能在公开链上实现有效的重度计算协约的执行。方案允许低于 50% 的节点是拜占庭的，剩下的节点都是 quesi-honest 的。

Threat Model

考虑两种节点:

• Byzantine Node 受到恶意节点控制，可能会随意添加、删除数据，可能会不正确的执行协议
• Quesi-Honest node 基本可信的节点。如实完成协议。但是如果有可能的话，就引入已有的计算量，以减轻自己的计算负担。

方案选取了一部分 Execution Set 的节点集合，由这些节点来进行 CIC 计算。Yoda 使用一种叫做 MultI-Round Adaptive Consensus using Likelihood Estimation (MIRACLE) 的共识机制来保证计算的可靠性。

We achieve this by making the digest dependent on a set of pseudo-randomly chosen intermediate states of a CIC execution.

MIRACLE

归结为一个优化问题：

如何能在给定恶意节点比例 f 和 ES 集合规模的条件下，使得某一个结果正确的可能性大于 
1−𝛽 ( 𝛽 误差率).此外要求尽可能少的轮数就能够达成共识。 

这个问题归结为一个 n 重的并行的假设检验问题。即同时判断第i个解是不是正确的解。如果是，则停止这个过程，并返回结果。

在这个共识机制中，需要进行多轮计算。每一轮计算一个 likelihood （由当前的恶意节点的数量估计 f 和其他信息计算），只有 likelihood 到达某一个门限时候，才采纳计算结果；否则进行下一轮。这个共识机制要求所有 quesi-honest 节点能够如实计算正确结果，这需要其他机制来保证（Randomness Inserted Contract Execution ）

RICE: RANDOMNESS INSERTED CONTRACT EXECUTION

为了防止 quesi-node 直接使用前一轮的结果来提交，以减轻自己的工作量。使用 RICE 协议来解决个问题。

这个方案使得每一次不计算完整的合约，而是随机生成两个随机数 ti 和 tj 表示开始和结束的指令。每次执行都返回部分的状态和成功执行的最后指令偏移。当执行了最后一次指令后才返回结果和一个 seed。

安全性证明

作者对上面两个算法进行了安全性证明。然后有对整个实现进行了安全性证明。略过

实现和评估

作者最后在8个物理节点的主机上搭建了网络并进行了评估。主要是所需轮数、时间、gas消耗、可扩展性等方面。

目前的不足在于其大量节点的通信开销以及重的合约意味着大量状态从存储开销。此外网络的交易处理能力依然不足。