Short RSA exclusion proofs for Plasma Prime

[snjax]

@vbuterin

Computing the coin-specific values b_1 and b_2 would still require raising g^{a_i} to the power of floor(\frac{y}{B_1}) and floor(\frac{\prod a_i}{B_2}), which would be expensive if there are many a_i values

@vbuterin

Here, the proofs would need to be aligned across coins, so I suppose you would make them every day or something similar; this could increase the raw amount of data that needs to be maintained by the nodes.

If we split the proof to 36-primes chunks it will use only twice the amount of disk space. But it is much simpler to generate proofs for accumulator with 36 primes than with millions.

So, coin-aligned proofs seems to be useful. The arbitary “coin” contains (log N)^2 primes. For N=2^{50} it is 2500. The overhead to store separate proofs for each coin is lesser than 1%.

It is not expensive to compute b_1 and b_2 for 2500 \{a_i\} set offchain.

If we do not spend coins every day, we do not need in proof for the coins. If we are accepting the coin, we request the history of the coin.

The defragmentation of the history is an open problem for us now. I am planning to model it and find the balance between aligning by coins or by transfers and splits.