RSA Accumulators for Plasma Cash history reduction

[ldct]

@vbuterin

To prove that a value v is part of an accumulator A, we can use a proof of knowledge of exponent scheme, proving that we know a value x such that (g^v)^x=A

Can we instead have g^x be the inclusion witness and have the verification be that (g^x)^v = A?

(the proof of knowledge of exponent scheme would still be needed to prove that the accumulator output in a block uses the previous block’s accumulator output as generator)

@vbuterin

This means that the history proof size for a coin goes down from one Merkle branch per Plasma block to two RSA accumulator proofs per transaction of that coin : one proof of membership for when the transaction takes place, and one proof of non-membership for the range where it does not.

I wonder if the the following scheme works instead: supposing a coin (whose id is q) has been spent t times, and the genesis block accumulator generator is g=3. Then the latest block accumulator value should be A = g^{q^t {p_1}^{e_1} {p_2}^{e_2} \ldots } where q \ne p_i for all i. The coin validity proof consists of a proof that q^{t+1} is not part of A and 1 RSA inclusion proof and merkle inclusion proof per transaction of the coin (as before).