锐客网

  1. 首页 > 睿知 > it技术 > >

Python定义素数函数 python定义函数输出素数( 六 )

IT技术起随


那么，我们的论证如下 。证明者想要证明P(1) == input和P(last_step) == output 。如果我们将I(x)作为插值，那么就是穿越(1, input)和(last_step, output)亮点的线，于是P(x) – I(x)就会在这亮点上等于零 。因此，它会证明P(x) – I(x)是P(x) – I(x)的乘积，并且我们通过提高商数来证明这点 。
紫色：计算轨迹多项式 (P)。绿色：插值 (I)（注意插值是如何构造的，其在 x = 1 处等于输入（应该是计算轨迹的第一步），在 x=g^(steps-1) 处等于输出（应该是计算轨迹的最后一步） 。红色：P-I 。黄色：在x = 1和 x=g^(steps-1)（即 Z2）处等于 0 的最小多项式 。粉红色：(P – I) / Z2 。
【Python定义素数函数 python定义函数输出素数】现在，我们来看看将P，D和B的默克尔根部组合在一起 。
现在，我们需要证明P，D和B其实都是多项式，并且是最大的正确阶数 。但是FRI证明是很大且昂贵的，而且我们不想有三个FRI证明，所以，我们计算 P，D 和 B 的伪随机线性组合，并且基于它来进行FRI证明：
# Compute their Merkle roots mtree = merkelize([pval.to_bytes(32, 'big') + dval.to_bytes(32, 'big') + bval.to_bytes(32, 'big') for pval, dval, bval in zip(p_evaluations, d_evaluations, b_evaluations)]) print('Computed hash root')
除非所有这三个多项式有正确的低阶，不然几乎不可能有随机选择的线性组合，所以这很足够 。
我们想要证明D的阶数小于2 * steps，而且P 和 B 的次数小于steps，所以我们其实使用了随机的P, P * xsteps, B, Bsteps 和 D的随机组合，并且可以看出这部分组合是小于2 * steps 。
现在 ， 我们来检查下所有的多项式组合 。我们先获得很多随机的索引，然后在这些索引上为默克尔树枝提供多项式：
k1 = int.from_bytes(blake(mtree[1] + b'\x01'), 'big') k2 = int.from_bytes(blake(mtree[1] + b'\x02'), 'big') k3 = int.from_bytes(blake(mtree[1] + b'\x03'), 'big') k4 = int.from_bytes(blake(mtree[1] + b'\x04'), 'big') # Compute the linear combination. We don't even bother calculating it # in coefficient form; we just compute the evaluations root_of_unity_to_the_steps = f.exp(root_of_unity, steps) powers = [1] for i in range(1, precision): powers.append(powers[-1] * root_of_unity_to_the_steps % modulus) l_evaluations = [(d_evaluations[i] + p_evaluations[i] * k1 + p_evaluations[i] * k2 * powers[i] + b_evaluations[i] * k3 + b_evaluations[i] * powers[i] * k4) % modulus for i in range(precision)]
get_pseudorandom_indices函数会回复[0…precision-1]范围中的随机索引，而且exclude_multiples_of参数并不会给出特定参数倍数的值 。这就保证了 ， 我们不会沿着原始计算轨迹进行采样，否则就会获得错误的答案 。
证明是由一组默克尔根、经过抽查的分支以及随机线性组合的低次证明组成：
# Do some spot checks of the Merkle tree at pseudo-random coordinates, excluding # multiples of `extension_factor` branches = [] samples = spot_check_security_factor positions = get_pseudorandom_indices(l_mtree[1], precision, samples, exclude_multiples_of=extension_factor) for pos in positions: branches.append(mk_branch(mtree, pos)) branches.append(mk_branch(mtree, (pos + skips) % precision)) branches.append(mk_branch(l_mtree, pos)) print('Computed %d spot checks' % samples)
整个证明最长的部分是默克尔树分支，还有FRI证明，这是有更多分支来组成的 。这是验证者的实质结果：
o = [mtree[1], l_mtree[1], branches, prove_low_degree(l_evaluations, root_of_unity, steps * 2, modulus, exclude_multiples_of=extension_factor)]
在每个位置，证明者需要提供一个默克尔证明 ， 从而让验证者能够检查这个默克尔证明，并且检查C(P(x), P(g1*x), K(x)) = Z(x) * D(x)以及B(x) * Z2(x) + I(x) = P(x)（提醒：对于不在初始计算轨道上的x ， Z(x)不会是零，所以C(P(x), P(g1*x), K(x)也不会是零) 。验证者也会检查线性组合是正确的，然后调用 。

推荐阅读


上一篇：狗狗跑步拍摄用什么，狗狗跑步机制作图

下一篇：html5存储方式csdn，html5的web存储对象