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:
- A sequence of proofs (Miller-Rabin certificates) that h(x), h(x)+1, ..., \ldots, H(x)-1 are not primes
- 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…
5 Likes
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
2 Likes
I was of the understanding that an exclusion proof could be done without the set, but after looking at the Parity stateless blockchain implementation (https://github.com/paritytech/stateless-blockchain) I am left a little confused. The product of the members of the set is used in these proofs. This product it seems would be huge if many elements are accumulated.
I came across Vitalik’s non-membership proof which seemingly does not use the set. I understand how this proof equates to LLX, but as @gluk64 mentions, how is it is possible to find r and its cofactor?