为何说通过LDE可以“放大错误”？

[0xxEric]

为何说LDE（或说RScode）可以放大错误（不知道这样描述是否准确？可能没有get到核心意思）
如下图，我们在自然数（方便演示）上，做个LDE。
在小域上，错误的Value只错了一个点，导致在大域上的值完全不同。（这里大域中，与小域中的插值点完全错开）

那么，问题是：
（1）放大错误，应该怎么理解呢？是说，有一个正确的值来做对比吗？
（2）从FRI的流程来看，只能直观的看到，折半算其degree是否小于某个值。并没有和哪个正确的东西做对比？

可能我用语不是很准确，请海涵一下

[0xxEric]

假设如上示例，在小域上，在x=1时，错误的f(x)值为2。导致在大域上的插值点完全不同。

[doutv]

仅关注 RS Code

RS Code 的目标是：发送方将一段 message 可靠地传输给接收方。
如果直接传输 message，因为传输过程中可能会发生错误，使 message 中的某些数发生改变。
所以发送方用 RS Code 将 message encode 得到 codeword，传输 codeword，即使 codeword 中某些数改变了，接收方也可以在 decode 过程中发现错误甚至纠正错误，得到正确的 message

在你的例子中，message = [1, 0, 0]，将 message 作为多项式的系数，degree = 2 的单变量多项式 $f(x)=1x^2 + 0x + 0 = x^2$
encoding: codeword = [f(-1), f(1), ..., f(10), f(11)] = [1, 1, 4, 9, 16, 25,36, 49, 64, 81, 100, 121]
decoding: 我不清楚具体的过程，由于任意3个数都可以恢复 $f(x)$，如果 codeword 中错误的数比较少，接收方可以还原 $f(x)=x^2$

上述的步骤似乎没有解答你的问题 “RS Code 可以放大错误”，我尝试用另一个角度来解释

目标：检查两个 degree = 3 的多项式是否相等
$$f(x) =^? q(x)$$
条件：我们不知道 f(x) q(x) 的表达式，只有他们在几个点上的取值
方法：随机选一个点，看看它俩取值是否一样，如果一样，就认为它俩相等
在小域 D 上，用以上方法检查，只有 1/4 的概率能成功发现它俩不相等
在大域 F 上，成功的概率上升到了 9/12 = 3/4
在更大的域上取值更容易发现错误了 -> “RS Code 可以放大错误”

原因：如果 $f(x) \neq q(x)$, degree = 3，它俩最多有 3 个点相等
联想起了一个公式但我忘记出处了 $error = \frac{degree}{domain size} = \frac{D}{|F|} $
小域 D： $error = \frac{3}{4} $
大域 F： $error = \frac{3}{12} = \frac{1}{4}$

[readygo67]

关于RCS 放大错误，可以参考 https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf chapter2.3


在di er第二张图理解起来更加容易，对于（2,1,1）这个消息，如果恶意的prover 将其修改为(2,1,0) ,经过RS 编码后，不同的概率从1/3 变成了9/11。 即除了最开始的(2,1)相同外，其他的码字都是不同的。
这里的结论仅仅是在扩展原来的定义域时成立，如果我们在计算是使用陪集，可以放的更大。

[nishuzumi]

个人理解

1. 如果攻击者构建的多项式就需要保证能依然满足大部分的点都和原多项式相同，这个难度是非常高的，一般构建出来的多项式次数会高于原来的多项式（如你发的图所示）
2. 如果攻击者恰好找到一个多项式，刚好在小域内，并且可以拟合大部分点值，当把这个域扩大后，原来的多项式必然无法满足，并且寻找这样的多项式难度非常大，因此可以增强安全性
3. 值的比较不是FRI负责的部分

如果有错误希望大佬指出