超酷算法:喷泉码

在前面我提到选择每个编码块都需要的源码块的数量,即度分布,是很重要的,它确实重要。理想情况下,我们需要生成一些只包含一个源码块的编码块,然后可以开始译码了,大多数编码块依赖很少的其他编码块。这种理想的分布是存在的,叫做理想孤波分布。

不幸的是,理想孤波分布在实际情况中并没有这么理想,正如随机变量使得有些源码块不被任何编码块包含,或者当所有知道的块用完之后译码停止了。理想孤波分布的一个变形,叫做稳健孤波分布,在这方面进行了改进,用非常少的源码块生成更多的码块,也通过合并所有的或几乎所有的源码块生成一些码块,来帮助破译最后一些源码块。

简而言之,这就是喷泉码的,更确切的说是LT码的,工作原理。LT码是已知的喷泉码中效率最低的,但是最易解释的。如果你想进一步学习,我强烈推荐读这篇关于喷泉码的技术论文,也可以读Raptor码,Raptor码只比LT码增加了一点复杂度,但是在传输开销和计算上都显著的提高了它们的效率。

在我们总结之前有一个进一步的思考问题。对于系统来说喷泉码可能看起来很理想,比如说比特流,它允许种子生成和散布几乎无限制数量的码块,或多或少的消除了稀疏种子流“最后一块”的问题,而且确保两个随机选择的并行端几乎总有有用信息相互交换。但是它面临一个重大的问题:验证从并行端接收到的数据将会很难。

像比特流这样的协议使用安全散列函数,比如说SHA1,和一个可信任中心(最初的上传者),向所有的并行端发送一个权威散列表。每个并行然后可以验证他们下载的散列块的文件包,并且和权威散列进行对比。但是对于喷泉码,这个是很难的。根本没有方法在编码块上计算SHA1散列,更不要说单独块上的散列。我们不能相信我们的并行端计算的结果,因为它们可以对我们撒谎。我们可以等到我们得到全部文件,然后从无效码块列表出发,尝试推断什么样的编码块是无效的,但这是困难的也是不可靠的,而且信息来的时候可能已经为时已晚。一个可供选择的方法是让最初发布者公布一个公共密钥,并且标注所有的生成块。然后我们就可以验证编码块了,但代价是:现在只有最初发布者可以生成有效的编码块了,并且我们失去了最初使用喷泉码的很多好处。似乎我们被困住了。

还有另一种选择,而且已经证明是一个非常聪明的方案,叫做同态哈希,尽管它有自己的注意事项和缺点。我们将会在下一版的超酷算法中讨论。