如何实现一个去中心化的 Dropbox 存储

lightning-li   |     |   1033 次阅读

本文翻译自 https://blog.ethereum.org/2014/08/16/secret-sharing-erasure-coding-guide-aspiring-dropbox-decentralizer/

在去中心化计算的应用中,有一个激动人心的应用,在过去的一年里引起了相当大的兴趣,那就是受激励的去中心化在线文件存储系统的概念。目前,如果你想你的文件或者数据安全地在云端备份,你有3种选择:(1). 上传它们到自己的服务器,(2). 使用一个中心化的应用,如 Google drive 或者 Dropbox,或者是 (3). 使用已经存在的去中心化的应用,如 Freenet。这些方法都有它们自己的缺点:第一种方法有着昂贵的建立和维护费用;第二种方法依赖于一个单可信任实体,并且常常涉及重大价格上涨;第三种方法速度慢,对每一位用户在空间容量方面有着很高的限制,因为它依赖于用户自愿奉献存储空间。受激励的文件存储协议有潜力成为第四种方法,通过无中心化地激励执行者 (存储用户数据的客户) 参与其中,提供高容量存储与高质量服务。

大量的平台,包括 StorjMaidsafe,某种程度上,PermacoinFilecoin,正在尝试处理这个问题,该问题在某种意义上看起来是简单的,所有的工具要么已经存在了,要么正在构建的过程中,我们所需要的就是实现而已。然而,该问题其中的一小部分尤其重要:我们如何合适地引进冗余性?冗余对于安全来说至关重要,尤其是在一个去中心化的网络中,业余爱好者与临时性用户占大部分,我们绝对不能依赖于单节点保持在线。我们可以简单地复制用户数据,让一些节点存储单独的拷贝,问题是:我们能做的更好吗?事实证明,我们当然可以。

Merkle Trees 与 Challenge-Response 协议

在我们进入最为重要的冗余性部分之前,我们首先讲解一些更容易的部分:我们如何创建一个至少激励一个实体保持文件的最为基本的系统?没有激励的系统中,问题将会变得更加容易,你上传文件,等待其它的用户来下载它,当你再次需要该文件的时候,通过文件的哈希来发出一个查询请求。如果我们想引进激励机制,问题某种程度上变得更加困难,但是在大事的计划中,依旧不是那么难。

在文件存储的上下文中,有两种实体你可以激励。第一种是你发出一个下载文件的请求时,实际向你发送文件的实体。这很容易可以做;最好的策略是一种类似于简单的 tit-for-tat 游戏,发送者发送 32 kb,你发送 0.0001 个币,然后发送者发送另一 32 kb,以此类推。注意在没有冗余以及大文件的情形下,这个策略是极易受到敲诈勒索攻击的。一个文件的 99.99% 对于你来说是毫无用处的,所以存储者有机会敲诈你,让你为文件的最后一部分付出高昂的费用。对该问题最聪明的解决办法是,让文件是自冗余的,使用一种特殊的编码来扩展该文件,如文件 11.11% 自冗余,那么该文件的任意 90% 都可以来恢复原文件的内容,并且对存储者隐藏该文件的自冗余百分比。然而,随后针对不同的目的,我们将讨论一个非常类似的算法。所以现在,接受该问题已被解决。

第二种我们可以激励的行为实体是长期存储该文件的实体。该问题有些困难,如何在不真正传输整个文件的情况下,证明你存储着该文件?幸运地是,有一个不是很难实现的解决方案,使用在加密经济中,被用来构建信誉的结构:Merkle trees。

haha

准确来说,某些情况下,Patricia Merkle 是更好的,尽管古老原始的 Merkle 树也能胜任。

基本的方法就是这个。首先,将文件分散为小块。或许每一块在 32 bytes 与 1024 bytes 之间,添加全 0 的块,直到块数量达到 n = 2 ^ k (添补的步骤是可以避免的,但是它使得算法编码和解释更加简单)。接下来,我们构建树。重命名 n 个块为 chunk[n]chunk[2n-1],并且使用以下规则重新构建块 1n-1chunk[i] = sha3([chunk[2*i], chunk[2*i+1]])。这使得你计算出块 n/2n-1,然后 n/4n/2 - 1,然后重复上述步骤直至得到一个 rootchunk[1]

Merkle

现在,注意如果你仅仅存储根节点,忘记 chunk[2]...chunk[2n-1],存储其它块的实体通过几百字节就能向你证明,他们拥有某个特定块。这个算法相对来说比较简单。首先,我们定义一个函数 partner(n),如果 n 是奇数,输出 n-1,如果 n 是偶数,输出 n+1 - 简单来说,就是给定一个块,找出和该块链接在一起产生父区块的块。然后,如果你想证明 chunk[k] (n <= k <= 2n - 1) 的所有权,提交 chunk[partner(k)]chunk[partner(k/2)] (除法在这里意味着向下取整,例如 11 / 2 = 5),chunk[partner(k/4)] 等等直到 chunk[1],与真正的 chunk[k] 一起。本质上,我们提供的是从块 k 到根节点的整个分支。验证者使用 chunk[k]chunk[partner(k)] 构建 chunk[k/2],使用刚生成的 chunk[k/2]chunk[partner(k/2)] 构建 chunk[k/4],直到验证者得到 chunk[1],该树的根节点,如果根节点与验证者自存的根节点匹配,那么该证据就是有效的,否则无效。

Merkle_verify

上图是块 10 的证据,包括 (1). chunk 10,(2). chunk 11 (11=partner(10)),4 (4 = partner(10/2)),3 (3 = partner(10/4))。验证过程从块 10 开始,使用它们的 partner 来产生父区块,直到产生根节点 chunk 1,看是否匹配验证者节点自存储的根节点。

注意证据隐式地包含了索引--在哈希之前有时你需要将 partner 加到左边,有的时候是右边,如果用来验证证据的索引是不同的,那么该证据将不再匹配。因此,如果我要求一个 chunk 422 的证据,你提供了一个即使有效的 chunk 587 的证据,我也会注意到出了错误。同样地,如果没有 Merkle Tree 的整个相关的部分,那么你没有任何办法提供一个有效证据;如果你试图传输伪造的数据,在某一点,哈希将不会匹配,导致最终的根节点会是不同的。

现在,让我们回顾一下这个协议。按照上述描述,我在文件之外构建了一棵 Merkle 树,然后上传给某个实体。然后,每 12 个小时,我找一个位于 [0, 2^k-1] 中的随机数,提交该随机数要求存储者提供证据。如果存储者回复了相应 Merkle tree 证据,然后我验证该证据,如果该证据是正确的,则发送 0.001 BTC (或者 ETH,或 storjcoin,或者任意使用的代币)。如果我没有接收到相应证据或者证据是无效的,那么我不会发送 BTC。如果存储者存储了整个文件,他们将会在所有的验证时间点成功,如果他们存储了文件的 50%,他们将会有 50% 的验证时间点是成功的,等等。如果我们想让它要么全部成功要么失败,那么我们可以简单地要求存储者提供 10 个连续的证据,这样存储者才可以得到奖励。存储者仍然可以就传输文件的 99% 进行敲诈勒索,但是我们可以利用我上面提到的冗余编码策略,在任何情况下文件的 90% 就足以恢复出原文件,这种策略将在下面描述。

这时你可能会关心的一点是隐私 - 如果你使用一个加密协议来让任意节点存储你的文件以获得奖励,难道那不意味着你的文件散落在互联网的各个角落,任何节点可以潜在地访问这些文件?幸运的是,该问题的答案是简单的:在发送文件之前,加密整个文件。从这一点上,我们假设所有的数据都是加密的,忽略掉隐私问题,因为目前的加密方法几乎完全解决了该问题 (几乎是因为,文件的大小,你访问文件的时间,依旧是公开的)。

深入到去中心化 (Looking to Dencentralize)

现在我们有一个使人们存储你的数据来获得奖励的协议;该算法甚至可以通过将其放入 Ethereum 合约中来实现无需信任 (trust-free),使用 block.prevhash 作为生成挑战 (注:挑战指向存储者索要某一特定块的 Merkle Tree 证据) 的随机数源。现在,让我们进行下一步:指出如何去中心化存储和增加冗余。去中心化的最简单方式是简单的复制:取而代之一个节点存储一份文件的拷贝,我们可以让五个节点分别都存储一份文件的拷贝。然而,如果我们简单地遵循上述提到的天真协议,我们会有一个问题:一个节点可以假装成五个节点,得到五倍的回报。一个快速解决该问题的办法是五次加密原文件,那么一个存储者将不能注意到五份文件其实是相同的,从而存储它们一次但是索要 5 倍奖励。

但是即使这样,我们依然有两个问题。第一个,没有任何办法验证文件的五份拷贝被五个分开的用户存储,如果你想让你的文件被去中心化的云来备份,你就会为去中心化的服务付款;如果所有的五个用户实际上是通过 Google 或者 Amazon 存储任何数据,这将会使得该协议没有多大实用性。这是一个非常困难的问题,尽管五次加密文件,假装你正在存储五个不同的文件,可以阻止参与者使用一份存储来获取五倍奖励,却不能阻止一个参与者使用五份存储来获取五倍奖励,并且从存储者的角度来看,经济规模甚至意味着这种情形是可取的。第二个,存在一种问题,你花费了巨大开销,尤其是,你从并没有获取到太多冗余性的存储者那里花费了不应该的冗余性支出 - 例如,如果一个单节点有 50% 的可能会离线 (非常合理的一个预估,如果我们正在讨论的是一个在个人硬盘剩余空间存储的文件网络),那么你有 6.25% 的可能会完全不能访问该文件 (译者注:这里指的可能是四个存储者的情况)。

针对第一个问题,有一种解决方案,尽管它是有缺陷的并且不清楚带来的好处是否值得这样去做。思想就是使用权益证明 (proof of stake)协议与*保管证明 (proof of custody) - 一种文件与私钥同时拥有的证明 *的结合。如果你想存储你的文件,想法是随机选择某个数量的某种货币的权益持有者,通过他们拥有的货币数量来赋予他们被选择的可能性权重。用 Ethereum 合约的方式来实现权益证明可能包括,让参与者存放 ether (以太币) 到合约中 (记住,这里存放 ether 是无需信任的,如果合约提供了一种赎回 ether 的方式),然后给每一个账户与他们存款成比例的可能性,接下来这些权益持有者将会有机会存储文件。然后,取而代之上面提到的简单 Merkle 树检测,保管证明协议会被使用。

保管证明协议有 non-outsourceable 的好处,也就是,如果不给服务器访问你的私钥,没有任何方法可以将文件放入服务器中。这意味着,至少在理论上,用户将不会倾向于在中心化的云计算系统中存储大量的文件。当然,协议完成这个是以验证需要更高花费为代价的。所以,留下一个开放的问题:我们是想要保管证明以及其带来的验证开销,还是以防万一而引进额外的冗余
所带来的存储开销?

M of N

不管保管证明是否是一个好主意,下一步是看看我们在冗余性方面能否比原生且幼稚的复制范例 (简单地将文件复制分发到各个节点) 做的更好。首先,我们分析一下原生的复制范例有多么好。假定每个节点有 50% 的可用时间,并且你愿意花费 4 倍开销。在这些情况下,失败的可能性有 0.5 ^ 4 = 0.0625 - 跟中心化服务提供的 4 个 9 (例如,99.99% 可用时间) 相比还是挺高的,一些中心化服务甚至提供 5 个 或 6 个 9 以上的可用时间,但是由于黑天鹅理论 (Talebian black swan considerations),任何超过 3 个 9 的承诺都可以被认为是废话;因为去中心化的网络不依赖于任何具体公司的存在或者行为或者是具体的软件包,去中心化系统实际可论证地可以合理提供 4 个 9 以上的承诺。如果我们假设参与去中心化网络的用户是类似专业的挖矿者,那么我们可以降低节点不可用时间的比例,如到 10%。在这种情况下,我们实际可以得到 1 - 0.1 ^ 4 = 0.9999 可用时间,但是理应假设更悲观的情况。

现在我们需要的是某种 M-of-N 协议,就像比特币中的多方签名 (multisig for Bitcoin) 。那么首先我们描述一下我们理想中的协议应该是怎样的,然后随后再考虑它是否是可行的。假定我们有一个大小为 1G 的文件,我们想"多方签名"它到 20-of-60 中。我们将文件分割为 60 块,每块大小为 50 MB (总共 3 GB),如此这 60 块中的任意 20 块足够重建原始文件。这是信息理论中最优情况;你不能从少于 1 G 字节的信息中恢复出 1 G 字节的信息,但是从 1 G 字节的信息中恢复出 1 G 字节的信息是完全可能的。如果我们有一种类似的协议,我们可以使用该协议将文件分割为 60 块,单独得加密这 60 块,使得它们看起来像独立的文件,然后单独地对这 60 块分别应用受激励的文件存储协议。

现在,有趣的部分来了:这样的一个协议确实存在。在文章的下一部分,我们将要描一点数学知识,被称作为"secret sharing" 或者"erasure coding"。这些名字使用的算法基本是相同的,除了一些实现细节。为了开始,我们回顾一个简单的定理:两点决定一条直线。

twopoints

尤其是,注意到,恰好有一条直线穿过其中任意两点,但是有无穷条直线穿过其中一点。由这个简单的定理,我们可以制定一个受限制的 2-of-n 版本:把文件的一半看作是坐标系中的一点 (x=1, y=文件一半的内容),把文件的另一半看作是坐标系中另一点 (x=2, y=文件另一半的内容),画出穿过两点的直线,并且取 x 轴为 3 与 4 的点,等等。这样,任意两块能被用来重建这条直线,从这条直线中获取 x=1, x=2 对应的 y 轴,从而恢复原文件。

数学上,有两种方法完成这个。第一种是相对简单的方法,包括一个线性方程的系统即可。假定我们想分割的文件内容是数字 "1321"。左半部分是 13,右半部分是 21,所以直线穿过 (1, 13), (2, 21) 两点。如果我们想知道斜率以及这条直线上 y 轴特点,我们可以解决该线性方程系统:

1 * a + b = 13
2 * a + b = 21

让第二个方程减去第一个方程,得到:

a = 8

将其带入第一个方程,得到:

b = 5

所以我们得到了等式,y = 8 * x + 5。我们可以生成新点:(3, 29)(4, 27),等等。从这些点中任意两点,我们都可以恢复原始的等式。

现在,让我们更进一步,生成 m-of-n 版本。事实证明,这是更复杂的,但是也不是那么难,我们知道两点决定一条直线。我们同时也知道三点决定一条抛物线。

threepoints

因此,对于 3-of-n,我们就可以将文件分割为 3 块,由 x = 1, 2, 3 三点组成抛物线,然后在该抛物线上取第四个点或更多的点作为附加块。如果我们想要 4-of-n,就要使用三次多项式。我们具体看一下后一种情况,我们仍然假设原始文件为 “1321”,但是我们使用 4-of-7 来将该文件分割。我们的四个点为 (1, 1)(2, 3)(3, 2)(4, 1)。所以我们有:

a * 1 ^ 3 + b * 1 ^ 2 + c * 1 + d = 1
a * 2 ^ 3 + b * 2 ^ 2 + c * 2 + d = 3
a * 3 ^ 3 + b * 3 ^ 2 + c * 3 + d = 2
a * 4 ^ 3 + b * 4 ^ 2 + c * 4 + d = 1

哦!让我们开始进行减法,我们将使用等式 2 减去等式 1,等式 3 减去等式 2,等式 4 减去等式 3,这样就可以将 4 个等式转换为 3 个等式,然后一次一次重复上述步骤。

a * 7 + b * 3 + c = 2
a * 19 + b * 5 + c = -1
a * 37 + b * 7 + c = -1
a * 12 + b * 2 = -3
a * 18 + b * 2 = 0
a * 6 = 3

所以 a = 1/2,现在我们逐步解开此方程,得到:

1/2 * 12 + b * 2 = -3

所以 b = -9/2,然后:

1/2 * 7 - 9/2 * 3 + c = 2

所以 c = 12,然后:

1/2 - 9/2 + 12 + d = 1

所以 a = 0.5b = -4.5c = 12d = -7。这是形象化的可爱多项式:

fourpoints

我创建了一个 Python 版实用工具来帮助你完成这些操作 (这个工具能做一些更高级的操作,但是我们随后深入它);你可以在这里下载它,如果你想快速解决上面提到的等式方程组,你可以:

> import share
> share.sys_solve([[1.0, 1.0, 1.0, 1.0, -1.0], [8.0, 4.0, 2.0, 1.0, -3.0], [27.0, 9.0, 3.0, 1.0, -2.0], [64.0, 16.0, 4.0, 1.0, -1.0]])
[0.5, -4.5, 12.0, -7.0]

注意把值设置为浮点数是必须的。如果你使用整数,Python 的整数除法会将所有的事情搞乱。

现在,我们介绍一种更容易的方式来完成它,拉格朗日插值法 (Lagrange interpolation)。这里思想是非常聪明的:我们提出一个三次多项式,它在 x = 1 处的值为 1,在 x = 2, 3, 4 处的值为 0,然后针对每一个其它的 x 坐标做相同的操作 (x = 2 处为 1x = 1, 3, 4 处为 0)。然后,我们做乘法,并将多项式方程加在一起;例如,为了匹配 (1, 3, 2, 1),我们简单地用 1 乘以多项式 (它的 y 轴为 (1, 0, 0, 0)),用 3 乘以多项式 (它的 y 轴为 (0, 1, 0, 0)),用 2 乘以多项式 (它的 y 轴为 (0, 0, 1, 0)),用 1 乘以多项式 (它的 y 轴为 (0, 0, 0, 1)),然后将这些多项式方程加在一起来得到目标多项式 (它的 y 轴为 (1, 3, 2, 1))。这个小技巧是有效的,因为四个点唯一决定一个三次多项式方程。这看起来不是那么简单,因为我们目前这种用点带入多项式方程的方法太笨拙了,但是幸运的是,对于它,我们有一个显示的构建方法:

CodeCogsEqn-19

x = 1 处,注意分子与分母是一样的,因此 y = 1。在 x = 2, 3, 4 处,分子中有一个为 0,因此 y = 0。这些多项式相乘并相加耗费二次方的时间 (例如,4 个等式需要 16 步),然而,我们原先的步骤耗费三次方的时间 (4 个等式需要 64 步),所以它是一个显著的提升,尤其是我们开始讨论数量大的分割时候,像 20-of-60。python 工具也同样支持该算法:

> import share
> share.lagrange_interp([1.0, 3.0, 2.0, 1.0], [1.0, 2.0, 3.0, 4.0])
[-7.0, 12.000000000000002, -4.5, 0.4999999999999999]

第一个参数是 y 坐标,第二个参数是 x 坐标。注意这里的相反顺序,python 模块里的代码将多项式中最低次数对应的系数放在首位,即由上面结果可得 0.5 * x ^ 3 - 4.5 * x ^ 2 + 12 * x - 7 = y。最后,让我们得到我们需要的附加值:

> share.eval_poly_at([-7.0, 12.0, -4.5, 0.5], 5)
3.0。
> share.eval_poly_at([-7.0, 12.0, -4.5, 0.5], 6)
11.0
> share.eval_poly_at([-7.0, 12.0, -4.5, 0.5], 7)
28.0

那么,这里我们立即能发现两个问题。首先,看起来计算机化的浮点数不是无限精确的;12 转变为 12.000000000000002。第二,当我们将 x 坐标变大时,块开始变得很大;在 x = 10 处,它变大为 163。这在某种程度上打破了你需要用相同大小的文件来恢复原始文件的承诺;如果我们丢失了 x = 1, 2, 3, 4,那么你需要 8 个数字来使原始文件恢复而不是 4 个数字。这些都是严重的问题,随后我们将使用一些数学上的高级知识来解决这些问题,但是目前我们先把这些问题放在一边。

即使有这些问题遗留,我们基本上已经取得了胜利,所以我们来计算一下我们的收获。如果我们使用 20-of-60 的分割,每一个节点有 50% 的时间在线,那么我们能使用组合数学 - 具体来说,二项式分布定理 - 来计算我们数据是完好的概率,首先,做好准备工作:

> def fac(n): return 1 if n==0 else n * fac(n-1)
> def choose(n,k): return fac(n) / fac(k) / fac(n-k)
> def prob(n,k,p): return choose(n,k) * p ** k * (1-p) ** (n-k)

最后一个函数计算 n 台服务器中恰好 k 台在线时数据完好的可能性大小,假设每台服务器在线的可能性为 p。现在,我们做:

> sum([prob(60, k, 0.5) for k in range(0, 20)])
0.0031088013296633353

仅仅 3 倍冗余我们就获得了 99.7% 的可用时间 - 比起简单的 3 倍复制带给我们的 87.5% 可用时间有了很大一步提升。如果我们将冗余度提升为 4 倍,那么我们就可以得到 6 个 9 的可用时间。这里我们就可以停下了,因为整个 Ethereum 或者整个 internet 完全宕掉的可能性比 0.0001% 高 (实际上,明天你很可能死去的概率)。哦!如果我们假设每台机器都有 90% 的可用时间,那么使用 1.5 倍冗余 20-0f-30协议,我们绝对会得到超过 12 个 9 的可用时间。信誉系统可被用来追踪每一个节点在线的频率。

处理错误 (Dealing with Errors)

我们将用该篇文章剩余部分讨论关于该模式的三种扩展。第一种是阅读上述描述过程中你可能忽略掉的问题,但是它是很重要的:如果一些节点尝试欺骗,会发生什么?上述算法能从任意 20 块恢复出原文件数据 (使用 20-of-60 协议)。但是如果其中的一个数据提供者是恶意的并且尝试提供伪造数据来使算法混乱该怎么办?攻击向量是相当吸引人的:

> share.lagrange_interp([1.0, 3.0, 2.0, 5.0], [1.0, 2.0, 3.0, 4.0])
[-11.0, 19.333333333333336, -8.5, 1.1666666666666665]

使用上述多项式的四个点,但是改变最后一个值为 5,会得到一个完全不同的结果。有两种方法可以处理这个问题。一种是很明显的方法,另一种是数学上聪明的方法。明显的方法是显而易见的:当分割一个文件的时候,保存每一个块的哈希,当接收到块的时候,将它的哈希与本地存储的哈希进行比较,如果不一致则丢弃掉。

聪明的方法在某种程度上是更聪明的;它包含一种令人生畏的数学方法,被称作伯利坎普-韦尔奇算法。思想是取而代之仅仅找到一个多项式,P,我们想象存在两个多项式,QE,使得 Q(x) = P(x) * E(x),尝试同时解决 QE,然后我们计算 P = Q / E。思想是如果这个等式保持正确,那么对于所有的 x,要么 P(x) = Q(x) / E(x),要么 E(x) = 0;因此,除了计算原始的多项式,我们神奇地隔离了错误是什么。这里我不会举一个例子,维基百科上已经有一个极好的示例,你能自己尝试:

> map(lambda x: share.eval_poly_at([-7.0, 12.0, -4.5, 0.5], x), [1, 2, 3, 4, 5, 6])
[1.0, 3.0, 2.0, 1.0, 3.0, 11.0]
> share.berlekamp_welch_attempt([1.0, 3.0, 18018.0, 1.0, 3.0, 11.0], [1, 2, 3, 4, 5, 6], 3)
[-7.0, 12.0, -4.5, 0.5]
> share.berlekamp_welch_attempt([1.0, 3.0, 2.0, 1.0, 3.0, 0.0], [1, 2, 3, 4, 5, 6], 3)
[-7.0, 12.0, -4.5, 0.5]

译者注:已知信道会错误传输 k 这个值,那么 P(x) 可以通过传输其上的 n + 2k 个点来纠正其中 k个错误,因此上述函数第一个参数中 6 个点中可以允许 1 个错误的点,并可以纠正它。

正如我提到的,这个数学小技巧对于文件存储来说,并不是真正需要的;上面提到的更简单的方法,即存储哈希值,并抛弃与之不匹配的块,可以工作的很好。但是却附带地对另一个应用非常有用:自治愈的比特币地址。比特币有一个 base58check 编码算法,可以被用来检测一个比特币地址被错误地拼写的情形,并且返回一个错误,这样你就不会偶然地发送数千美元到万劫不复的深渊。然后,使用我们了解到的,我们实际上能够做的更好,设计一种算法,不仅能检测错误的拼写,而且可以在我们不知道的情形下纠正这些错误。我们没有在以太坊中使用任何聪明的地址编码算法,因为我们更喜爱鼓励可选的基于注册名称的使用,但是如果一种地址编码算法模式确实需要,上述提到的也许会被使用。

有限域

现在,我们回到第二个问题:一旦我们的 x 坐标变大一点,相应的 y 坐标就开始迅速得变为无穷之大。为了解决这个问题,我们将要做的就是完全重新定义一套算术规则,正如我们知道的那样。具体点来说,我们重新定义我们的算术操作如下:

a + b := (a + b) % 11
a - b := (a - b) % 11
a * b := (a * b) % 11
a / b := (a * b ** 9) % 11

这里百分号的意思是取余,所以我们有 7 + 5 = 16 * 6 = 3 (并且它的推论,3 / 6 = 6),等等。我们现在只被允许处理数字 0、1、2、3、4、5、6、7、8、9、10。令人惊讶的事情是,即使我们这样做了,所有传统算术规则对于我们新的算术规则仍然是有效的;(a * b) * c = a * (b * c)(a + b) * c = (a * c) + (b * c),如果 b != 0a / b * b = a(a^2 - b^2) = (a + b) * (a - b),等等。因此,我们可以使用上面提到的抛物线方程,将其转变到我们的新系统中。即使抛物线曲线的直观感受被完全破坏了 - 我们现在处理的是抽象的数学对象,不是任何类似的平面上实际的点 - 因为我们的新代数是自统一的,公式仍然是有效的,那就是我们想要的。

> e = share.mkModuloClass(11)
> P = share.lagrange_interp(map(e, [1, 3, 2, 1]), map(e, [1, 2, 3, 4]))
> P
[4, 1, 1, 6]
> map(lambda x: share.eval_poly_at(map(e, P), e(x)), range(1, 9))
[1, 3, 2, 1, 3, 0, 6, 2]
> share.berlekamp_welch_attempt(map(e, [1, 9, 9, 1, 3, 0, 6, 2]), map(e, [1, 2, 3, 4, 5, 6, 7, 8]), 3)
[4, 1, 1, 6]

map(e, [v1, v2, v3]) 用来转变普通的整数到新域里的元素;该软件库包含了一种对 11 取余类的实现,该类提供了无缝的算术操作接口,所以我们能够互换它们,例如 print e(6) * e(6) 返回 3。你可以看到,所有的一切仍然工作 - 除了那个,因为我们对加减乘除操作进行了重新定义,因此所有的操作返回的整数都在 [0 ... 10] 范围内。我们从不需要担心浮点数精度问题或者是当 x 轴变大之后,相应 y 轴值变得无限大。

现在,现实中,这些相对简单的取余有限域并不是我们真正需要用在错误检测代码中的。更喜爱的通用构建方法被称作伽罗瓦域 (技术上,任何拥有有限个数元素的域都可以称之为伽罗瓦域,但是有时候这个术语被用来更具体地指向基于多项式的域,就正如我们将要描述的)。思想是,域中的元素现在是多项式,系数是整数域中的自身值对 2 取余 (例,a + b := (a + b) % 2,等等)。加法和减法就像正常的那样工作,但是乘法是它自身对某一个多项式取余,具体点来说,是 x^8 + x^4 + x^3 + x + 1。这个更为复杂的多层构建让我们拥有了一个恰好有 256 个元素的域。如果我们想一次性地在多个字节上应用,我们仅需要并行地应用该模式 (例,如果每一块是 1024 个字节,决定 10 个多项式,每一个对应一个字节,分开扩展它们,然后结合多项式在每一个 x 轴处的值来得到附加块)。

译者注:


本人认为如果每一个块对应 1024 个字节,应该使用 1024 个多项式,每一个多项式对应一个字节;举一个简单的例子来说,假设一个块对应 4 个字节,现在需要 4 个多项式,假设文件内容是 "abcdefghijkl",那分割该文件为 2 块,块 1 为 "abcd",块 2 为 "efgh",块 3 为 "ijkl"。那第一个多项式由 (1, a)(2, e)(3, i) 决定;第二个多项式由 (1, b)(2, f)(3, j) 决定,以此类推。

> P1 = share.lagrange_interp(map(share.Galois, [ord("a"), ord("e"), ord("i")]), map(share.Galois, [1, 2, 3]))
[109, 253, 241]
> P2 = share.lagrange_interp(map(share.Galois, [ord("b"), ord("f"), ord("j")]), map(share.Galois, [1, 2, 3]))
[110, 253, 241]
> P3 = share.lagrange_interp(map(share.Galois, [ord("c"), ord("g"), ord("k")]), map(share.Galois, [1, 2, 3]))
[111, 253, 241]
> P4 = share.lagrange_interp(map(share.Galois, [ord("d"), ord("h"), ord("l")]), map(share.Galois, [1, 2, 3]))
[96, 4, 0]

> map(lambda x : share.eval_poly_at(map(share.Galois,P1),share.Galois(x)), range(1, 7))
[97, 101, 105, 61, 49, 53]
> map(lambda x : share.eval_poly_at(map(share.Galois,P2),share.Galois(x)), range(1, 7))
[98, 102, 106, 62, 50, 54]
> map(lambda x : share.eval_poly_at(map(share.Galois,P3),share.Galois(x)), range(1, 7))
[99, 103, 107, 63, 51, 55]
> map(lambda x : share.eval_poly_at(map(share.Galois,P4),share.Galois(x)), range(1, 7))
[100, 104, 108, 112, 116, 120]

> share.berlekamp_welch_attempt(map(share.Galois,[97, 101, 105, 61, 4, 5]), map(share.Galois,[1, 2, 3, 4, 5, 6]), 2)
[109, 253, 241]

> map(chr, [97, 101, 105, 61, 49, 53])
['a', 'e', 'i', '=', '1', '5']
>map(chr, [98, 102, 106, 62, 50, 54])
['b', 'f', 'j', '>', '2', '6']
> map(chr, [99, 103, 107, 63, 51, 55])
['c', 'g', 'k', '?', '3', '7']
> map(chr, [100, 104, 108, 112, 116, 120])
['d', 'h', 'l', 'p', 't', 'x']

由上述运行代码看出,我们可以附加 3 个块,分别为 "=>?p"、"123t"、"567x",现在我们可以有 3-of-6 的协议,即得到上传的 6 块中的任意 3 块,我们都可以恢复出原内容,比如我们得到了块 1 "abcd"、块 4 "=>?p"、块 5 "123t":

> P1 = share.lagrange_interp(map(share.Galois,map(ord, ["a", "=", "1"])), map(share.Galois, [1,4,5]))
[109, 253, 241]
> P2 = share.lagrange_interp(map(share.Galois,map(ord, ["b", ">", "2"])), map(share.Galois, [1,4,5]))
[110, 253, 241]
...
> map(lambda x : share.eval_poly_at(map(share.Galois,P1),share.Galois(x)), range(1, 4))
[97, 101, 105]  -> ["a", "e", "i"]
...

由上述代码就可以复原出原来的文件内容为 "abcdefghijkl"。

但是知道它具体工作原理并不是很重要,这部分工作的要点是我们能够以这种方式重新定义 +-*/ 操作,并且他们仍然是自统一的,但是却可以使用和输出字节。

走向多维:自治愈立方体 (Going Multimensional: The Self-Healing Cube)

现在,我们使用有限域,并且我们能够处理错误,但是有一个问题依旧存在:当节点宕机的时候发生了什么?在任意时间点,你能依赖于有 50% 的存储你的文件的节点在线,但是你不能依赖的是相同的节点一直保持在线 - 最终,一小部分节点退出,然后另外一小部分节点退出,然后再另一小部分节点退出,直到最终没有足够多的原始节点保持在线。我们如何处理这种渐变的消耗?一种策略是,你监视奖励每一个独立存储文件的实例节点的智能合约,了解节点会停止接收该奖励的时间,然后重新上传该文件。然而,有一个问题:为了重新上传文件,你需要重新构建文件的全部,对于满足人们强烈视觉要求的高分辨率的电影是一种潜在性困难的任务;还有,理想状态下,我们是希望网络自己能够解决该问题,而不借助中心化的资源,甚至是文件的拥有者。

幸运地是,这样一种算法是存在的,我们所需要做的就是实现上面提到的错误检测码的一种巧妙的扩展。关键思想是,多项式的错误检测码是线性的,这是我们可信赖的事实。线性是数学术语,意味着对于乘法和加法来说有着良好的互操作性。例如,考虑:

> share.lagrange_interp([1.0, 3.0, 2.0, 1.0], [1.0, 2.0, 3.0, 4.0])
[-7.0, 12.000000000000002, -4.5, 0.4999999999999999]
> share.lagrange_interp([10.0, 5.0, 5.0, 10.0], [1.0, 2.0, 3.0, 4.0])
[20.0, -12.5, 2.5, 0.0]
> share.lagrange_interp([11.0, 8.0, 7.0, 11.0], [1.0, 2.0, 3.0, 4.0])
[13.0, -0.5, -2.0, 0.5000000000000002]
> share.lagrange_interp([22.0, 16.0, 14.0, 22.0], [1.0, 2.0, 3.0, 4.0])
[26.0, -1.0, -4.0, 1.0000000000000004]

可以观察到,第三行代码的输入是第一行代码与第二行代码输入之和,输出也是前两行输出之和。当我们加输入变为 2 倍过后,输出也变为了原先的 2 倍。那么,这样的好处是什么?好吧,这里是一个巧妙的小技巧。Erasure codeing 自身是一种线性的公式;它仅仅依赖于乘法和加法。因此,我们将应用 erasure coding 到其自身。那么,我们该如何去做?这里是一种可能的策略。

首先,我们使用我们的 4 数字文件,然后把它放入到一个 2X2 的网格中。

1  3
2  1

接下来,我们使用相同的多项式插值法和上面提到的扩展程序沿着 x 和 y 轴来扩展文件:

1  3  5  7
2  1  0  10
3  10
4  8

并且,我们应用相同的过程来得到剩下的 4 个值:

1  3  5  7
2  1  0  10
3  10 6  2
4  8  1  5

译者注,使用的方法如下:

In [77]: e = share.mkModuloClass(11)

In [78]: share.extend([1,3],2,e)
Out[78]: [1, 3, 5, 7]

In [79]: share.extend([2,1],2,e)
Out[79]: [2, 1, 0, 10]

In [80]: share.extend([1,2],2,e)
Out[80]: [1, 2, 3, 4]

In [81]: share.extend([3,1],2,e)
Out[81]: [3, 1, 10, 8]

In [82]: share.extend([5,0],2,e)
Out[82]: [5, 0, 6, 1]

In [83]: share.extend([7,10],2,e)
Out[83]: [7, 10, 2, 5]

其中 extend 函数的第一个参数代表要扩展的值列表,第二个参数代表需要生成多少数量的值附加在原列表上,第三个参数代表使用的有限域类型。


注意,我们计算最后 4 个值的时候,无论是从水平扩展还是纵向扩展都是没有关系的,因为 secret coding 是线性自交换的,所以无论从哪个方向扩展,得到的结果都是一样的。现在假设我们丢失了数字 6。那好,我们可以在纵向上修复该问题:

In [90]: share.repair([5,0,None,1],2,e)
Out[90]: [5, 0, 6, 1]

或者横向修复该问题:

In [94]: share.repair([3,10,None,2],2,e)
Out[94]: [3, 10, 6, 2]

其中,repair 函数的第一个参数代表要修复的列表,第二个参数代表多项式的次数,即两个点决定一个 2 次多项式,第三个参数代表有限域类型。

无论从哪一种方向修复,我们都得到了 6。这是一件令人惊奇的事情:多项式在 x 和 y 轴上工作地一样好。因此,如果我们从该网格中使用这 16 块,将它们分散到 16 个不同的节点上,当这些节点中的一个消失的时候,然后和消失的节点处于同一 x 轴或者 y 轴的节点就可以联合起来,重建被消失的节点所持有的数据,并且可以索要存储该数据应得的奖励。理想地,我们可以扩展该处理过程,从 2 维的平面到 3 维的立方体,或者 4 维的超立方体,甚至更高维 - 使用更多维的一个好处是使得重新构建变得更加容易,代价是一个比较低程度的冗余。因此,我们所拥有的是一种信息理论的等价物,听起来像是直接出自科幻小说:一个高度冗余,互连,多部件组成的自治愈立方体,它能快速检测错误,并且能够自己修复错误,即使在该立方体大部分区域损坏的情况。

borgcube

the cube can still function even if up to 78% of it were to be destroyed...

那么,让我们汇总一下。你拥有一个 10 GB 大小的文件,你想将其分散到网络中。首先,你加密该文件,然后你分割该文件为 125 块。你安排这些块组成一个 3 维的 5X5X5 的立方体,指出每一个轴的多项式,并且扩展每一个轴,到最后你可以得到一个 7X7X7 的立方体。你可以寻找乐意存储这些块的 343 个节点,并且只告诉每一个节点它属于那一轴的节点们的实体信息 (我们希望努力避免单个节点将整个线,方形或立方体聚集在一起并存储它并根据需要实时计算任何冗余块,从而索要存储全部块的奖励,实际上却没有提供任何的冗余性)。

为了下载整个文件,你会针对所有块发出一个请求,然后查看进来的哪一块拥有最高的带宽,你可以使用 pay-per-chunk 协议来为数据的发送付款;敲诈勒索将不再是一个问题,因为你拥有如此高的冗余度以至于没有人可以拥有垄断的权利从而拒绝向你提供文件。只要满足最小数量的块到达,你可以使用数学运算来解密该文件,并且在本地复原该文件。或许,如果编码是 per-byte,你甚至可以应用它到类似 Youtube 流式实现,一次恢复一个字节。

在某种意义上,在自愈和对这种伪造冗余的脆弱性之间存在不可避免的权衡:如果网络的部分节点联合在一起,恢复一个丢失的块来提供冗余性,那么网络中恶意的大量参与者就可以凭空恢复丢失的块提供给客户端,像客户端索要伪造冗余的费用。或许,一些模式包括在每一块之上增加另外一层加密,隐藏加密的密钥和在另一轴存储块的参与者的地址,仅在某些特定时间激励披露过程来形成一个最佳的平衡。

Secret Sharing

在文章的开始,我提到了 erasure coding 概念的另一名称,secret sharing。从该名字可以看出,这两者如何关联:如果你有一个分散数据到 9 个节点中,其中 5 个节点就可以恢复出原始文件,但是 4 个却不可以的算法,那么另外一个明显的使用情况是,使用相同的算法来存储私钥 - 分割你比特币钱包备份为 9 块,将其中一块给你的妈妈,一块给你的上司,一块给你的律师,将其中 3 块放入一个安全的保管箱里,等等。如果你忘记了你的密码,你可以分别向他们索要其中一部分,他们看起来不会互相串通。这是一个非常合理的办法,但是还需包括一个实现细节来使其正常工作。

这个问题是:即使 4-of-9 不能不能恢复出原始的密钥,4-of-9 仍然可以联合,并且可以得到关于密钥的大量信息 - 具体点来说,四个线性等式已经明了,第五个不清楚。这可以约减选择空间的维度到五分之一,所以代替需要搜索 2^256 次的私钥空间被约减到只需要搜索 2^51 次。如果你的私钥是 180 位,那么就约减到 2^36 - 对于一台普通电脑来说,是绰绰有余可以解决该复杂度的问题。我们处理该问题的解决方法是不是对私钥进行 erasure coding,而是对私钥再加上 4 被随机的冗余进行编码。更精确来说,让私钥是多项式中 0 次方的系数,随机找 4 个值成为接下来的四个系数,从该多项式中获取值。这使得制作每一块花费五倍的时间,但是却有即使 4-of-9 也需要有 2^180 或者 2^256 的搜索空间。

结论

那么我们来到了这里,这是对 erasure coding 能力的一个简介 - arguably the single most underhyped set of algorithms (except perhaps SCIP) in computer science or cryptography。这个思想相对于文件存储来说就相当于多签名对于智能合约来说,允许你最大程度地获得安全性和你能接受的文件冗余程度。它是一种解决文件可用性的一种有效方法,可以取代简单地分割与复制方法 (的确,如果你想应用 1-of-n 策略,实际上就是简单复制方法);它能够用来概括和处理冗余中的一些问题,就像加密用来概括和解决隐私性中的一些问题一样。

去中心化文件存储仍然是远未解决的问题;尽管核心技术的大部分,包括 Tahoe-LAFS 中的 erasure coding,已经被实现,但仍然有大量小的或者不是那么小的实现细节需要被解决来使系统实际可用。一个有效的信誉系统将会被需要用来测量节点的服务质量 (例如,一个高达 99% 可用时间的节点至少值 3 个 50% 可用时间的节点)。在某些方面,受激励的文件存储甚至依赖于实际的区块链扩展性;不得不每小时隐式地对 343 个与验证合约交互的交易费用买单这种方法将不会工作,直到交易费远远比现在的交易费要低,并且直到那时,需要一些更粗糙的妥协。但是再一次,几乎加密货币领域里的每一个问题依旧有很长的一段路要走。

 
4 人喜欢