RSA Accumulators for Plasma Cash history reduction


#21

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?


#22

@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…


#23

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 https://github.com/zcoinofficial/solidity-BigNumber/blob/5355ea7c6e942f613855c509ebd0d98afbe39ec7/contracts/BigNumber.sol#L667