由一篇比较两个大文件内容相等的算法文章引出的一些思考

[AlexiaChen]

前言

该篇文章介绍了用Reed-Solomon编码的思想来比较两个大文件的内容。原文请戳这里： https://hackmd.io/@Kurt-Pan/SJ6Y0DZLq# 主要是想说明一个确定性比较算法的下界。我们暂时不讨论这么技术的问题。我们重点关注下Reed-Solomon编码这个思想来解决这个问题所带来的一些思考。因为这个问题，跟我之前做Shamir secret sharing的密码学算法很像，都是根据多项式来编码一些数据，然后通过拉格朗日插值来进行恢复原始数据

正文

首先定义两个文件内容，文件A的内容记为向量a = (a1,a2,a3,..., a_n), 文件B的内容记为向量b = (b1,b2,b3,... b_n)。这些向量的元素你可以看成就是文件里面的字符了。Alice拥有文件A， Bob拥有文件B。按照朴素传统的确定性算法思想，要比较两个大文件内容就是Alice 把整个文件A发送给Bob， Bob执行算法验证 a_i 是否等于 b_i 逐个字符比较。但是，我们前面说了，这个文件是大文件了。Alice的文件发送给Bob这个动作，数据传输量太大了，通信复杂度很高。由于文章说了，如果有没有更好的确定性算法比这个朴素算法还好的，那么就没有，因为这个朴素算法就是下界。有没有可能可以突破下界，争取更好的复杂度，答案是放宽条件，用非确定性算法，允许有概率出错。这样就可以突破下界了。

原文它是设计了一种reed-solomon指纹识别协议，思想借用了RS编码。算法是把待编码的字符向量映射到一个有限域Fp下的多项式。向量字符值就是多项式的系数向量，以前我提到过的，系数向量就可以确定唯一的一个多项式。在这里，向量的大小n也就是多项式的degree了。

原始的RS编码: 把待编码的message定义为 x = (x1,x2,x3, ... , x_k ) x ∈ F

多项式: p(a) = x1*a^0 + x2*a^1 + ... + x_k * a^(k -1) a ∈ F

定义一个指纹hash函数:

F_p为素域， r ∈ F_p。 定义 Hash函数 H_r(x) = H_r(x1, x2, x3, ... , x_n) = x1*r^1 + x2*r^2 + x3* r3 + ... + x_n*r^n

具体协议:

• Alice 随机选择一个 r， r ∈ F_p， 并计算 v = H_r(a) 。
• Alice发送(v, r)
• Bob检查 v = H_r(b) 的真假。如果是真，那么 a = b 以很高的概率为真 , 如果是假，那么 a != b

你会看到这里的r在每一轮选择多项式上的一个点。而我们的RS编码，一段消息x的码字 C(x) 实际要选择n个点：

在Shamir Secret Sharing中，n 比 k大， 是 n >= 2*k + 1 ， 对于degree 为 k - 1的多项式 ，那么知道其中任意k个点，那么都可以通过这k个点，把多项式插出来。所以RS编码中的网络上大多数找到的方案，都需要在编码的后面补足一个冗余的多项式，就是为了防止数据错乱，带有恢复校验的功能，不然RS编码就不叫纠错码(ECC, error-correct code)了。如果要了解详情，请看这里 https://crypto.stackexchange.com/questions/1760/rs-erasure-coding-and-shamirs-secret-sharing， 本质上threshold主要都是为了纠错(error-correction)。

[songtianyi]

固定 step 取字符比较

[songtianyi]

固定 step 会有安全性问题，容易被伪造

[AlexiaChen]

固定 step 取字符比较

哈哈，主要是想写reed solomon编码。这个编码在无线通信和卫星信号传输上都有用。这个文件比较只是采用了部分思想解决的问题。

[songtianyi]

固定 step 取字符比较

哈哈，主要是想写reed solomon编码。这个编码在无线通信和卫星信号传输上都有用。这个文件比较只是采用了部分思想解决的问题。

这种编码属于很底层了吧，是我宁愿看下压缩/安全方面的编码 偏应用层的

[AlexiaChen]

不底层，就是一种纠错码。压缩我以前只知道一个huffman，其实这个对普通文本压缩率蛮不错的，通用的压缩一般是根据重复串建模，需要点概率论的意思。你以前是搞特定数据的压缩还是通用数据的压缩啊？