Log(coins)-sized proofs of inclusion and exclusion for RSA accumulators

[ldct]

@vbuterin

To implement this in practice, the most efficient path seems to be to run a one-time “setup” computation (no trust required; anyone can independently check it) that runs through all values of get_prime(i)get_prime(i) for 0≤i<2400 \le i < 2^{40}) and finds all values that are not prime that do pass Fermat’s test (eg. Carmichael numbers ), and creates a file containing them. The implementation of get_prime used inside of the contract would use the Fermat test followed by checking non-membership in the file of “spooky numbers” created by the setup as its primality test.

It seems to me that if we are willing to impose on users the cost of a deterministic “setup” phase that explicitly enumerates ~ 2^{40} primes, one alternative would be for the plasma contract to hard-code a merkle root of a depth-40 tree containing the first 2^{40} primes, and any transaction that requires a hash-to-prime must provide witnesses into this tree.