RSA Accumulators for Plasma Cash history reduction


Forgive me if this seems like a stupid question, but where/how are the results of MODEXP stored, in order to be used later? Doesn’t the EVM only support 256-bit integers natively?


@denett: not sure how practical it would be, but you could define the prime hash as
H(x) = \min\{n : n \mbox{ is prime and }n\geq h(x)\}
where h(x) is an ordinary hash function.
Then the operator could post a proof of correctness of H(x) as:

  1. A sequence of proofs (Miller-Rabin certificates) that h(x), h(x)+1, ..., \ldots, H(x)-1 are not primes
  2. proof (Atkin–Goldwasser–Kilian–Morain certificate) that H(x) is a prime.

The issue might be the verification time of the Atkin–Goldwasser–Kilian–Morain certificate…


You can break a 2048 bit number into 8 256 bit ones, or a bytes array and do bignumber arithmetic in a smart contract. E.g