互联网中存在大量的边缘存储设备，MEMO通过对这种闲置资源的整合搭建了一个可扩展的分散式云存储协议，使存储资源有限的用户可将数据存储在边缘存储节点上。但是在这样一个公开的低可信环境中，边缘存储节点可靠性较低，他们可能会作出篡改、删除数据等恶意行为，因此需要对存储节点进行有效监督，以验证他们是否正确地持有存储数据。

考虑到部署环境为公有区块链，故引入第三方进行数据持有性证明的挑战和验证工作。在MEMO的组织架构中，设计了User、Provider、Keeper三个角色，其中User是存储消费者，Provider是存储空间提供者，Keeper是协调管理者。这三个角色中，Keeper充当着第三方审计角色，会定期对Providers发起挑战并验证他们是否完好存储数据。

一、可验证随机函数

即使引入了第三方审计角色，在低可信的分散式环境中仍然面临着预存攻击和合谋攻击的可能。预存攻击是数据存储方可以在不存储完整数据的情况下响应挑战并通过的可能，合谋攻击是指在公开验证的环境中，用于审计的服务器和用于存储的服务器之间还存在双方合谋以非法通过证明的可能。

为了抵御这两项攻击，使数据存储更加安全可靠，MEMO采用可公开验证随机函数算法（VRF）来保证验证的不可预测性和公开验证性。

1.不可预测性：指随机数算法产生的每个输出均应统计独立于其他输出，使得攻击者无法通过已得到的随机数推算出其他随机结果，即任何恶意节点无论以何种途径，都无法根据个人意志控制随机过程的输出。

2.可公开验证性：指可使任何有兴趣的参与方都能得到授权，并通过某种方式进行验证以下事实是否成立，即需要验随机过程所产生的结果是真正随机的、而非受某一方操控形成。

该算法由证明者发布的公钥来对函数进行承诺，公钥与函数相绑定，这意味着验证者一定能用它对函数的可靠性进行验证，具体来说，可验证随机函数拥有多项式时间算法G(函数参数生成器）、F(函数计算器）和V(函数验证器）等3个算法。

二、验证原理

每一次验证，由Keeper生成VRF密钥对，并在保存VRF私钥至本地的同时，将VRF公钥发送给对应的数据存储方Provider，这意味着Provider利用VRF公钥对函数的可靠性进行验证。同样的，之后VRF计算生成的随机数和响应证据会被一起发送给Provider，用于之后的验证过程。换言之，Keeper作为计算方掌握私有信息，Provider作为验证方掌握公开信息，从而使得Keeper的随机过程具有可验证性。

在确保了随机阶段的可验证性之后，还需要对随机过程做到公开验证。可以看到，合谋攻击的本质在于随机数相关的过程隐秘性过强，其产生过程并不透明，这使得产生随机数的可靠性难以得到验证。可验证随机函数利用一种类似于公钥加密方式的承诺方案，其中的证明者通过私钥和黑盒模式的函数保障不可预测性，验证者则利用公钥和完全公开的函数输出保障可验证性，从而达成了两种必备性质的有效结合。

图：验证证明中各角色的交互流程  

三、验证流程

1.数据预处理

在上传数据前，User首先会对数据进行预处理。User根据参数计算生成公开信息和私有信息，公开信息发送至Keeper存储，私有信息保存在用户本地；并且，User需要对将要存储到Provider的外包数据进行签名，生成相对应的标签信息，之后用户把外包数据和标签信息进行组合并发送给Provider。

User对将要存储到数据存储方的外包数据切分成数据片，同时按照递增的整数给数据命名索引，然后根据数据片和索引生成标签进行签名，之后用户把外包数据和标签信息进行组合并发送给Providers。

图：用户对数据块进行计算产生标签的过程

2.生成挑战信息

Keeper接收User的公开信息即相当于接受了该User的挑战委托，因此选择一种会发生变化、且变化不可预测的信息作为后续计算的输入。Keeper生成属于自己的可验证随机函数的密钥对，并将挑战信息发送给Providers，这个挑战信息就是Keeper根据可验证随机函数生成的公钥。

3.生成数据持有性证明

收到挑战信息后，Provider首先对其进行验证，若验证通过，则生成对应的数据持有性证据并发回Keeper。

4.验证证明

最后由Keeper根据存储的用户的公开信息，对收到的数据持有性证据依次进行两步验证，当且仅当两步验证的结果均为通过时，可表明Provider正确且完整地存储了外包数据。

小结：

MEMO引入第三方审计Keeper对数据持有性进行公开验证，能够有效分担数据所有方Provider的计算压力和在线压力。通过引入新的变量和计算环节使得数据存储方Provider必须正确而完整地存储数据才能实现利益最大化，选用合适的随机函数以使第三方审计和数据存储方Provider在维持正常运转的环境中有较大概率无法顺利地进行合谋攻击，有效提高了方案安全性。整个过程只需要负担较低的计算压力和常量级的信息存储开销即可使第三方审计在未接触原始存储数据的情况下对数据持有性进行公开审计，高效性与隐私性也都能得到切实保证。

了解更多MEFS相关内容，欢迎关注：

l 官网：http://memolabs.org

l 公众号：MEMO分散式存储

l Twitter：Memo Labs

l Medium：Memo Labs

l Telegram：http://t.me/memolabsio