RSA Accumulators for Plasma Cash history reduction

Apparently you need to hash committed values to primes. We can also use predefined sequence of primes as a mapping, maybe that will be cheaper for execution in the EVM.

Definitely the latter. Just use the sequence of primes starting from the beginning: 2, 3, 5, 7, 11, 13, 17, 19… This way a batched proof of inclusion or exclusion only requires ~2-4 bytes per coin included, and not >=32.

1 Like

Please correct me if I’m wrong, but wouldn’t proof be (b, z, r)? In the Weselowski scheme x = 2^\tau and is publicly known, so the verifier computes r \leftarrow x \mod B, while in your scheme x is only known to the prover.

To prove that a value is v not part of an accumulator A, we need only prove that we know r such that 0 < r < v where A * g^r is a known power of g^v using the algorithm above.

Could you please elaborate this part a little more? How do we find r? Why does the proof hold?

2 Likes

Please correct me if I’m wrong, but wouldn’t proof be (b,z,r)? In the Weselowski scheme x=2τ and is publicly known, so the verifier computes r←xmodB, while in your scheme x is only known to the prover.

Ah yes, I think you’re right.

Could you please elaborate this part a little more? How do we find r? Why does the proof hold?

Suppose I prove that A * g^3 is a power of g^{10}. Then, I know that DLOG_g(A) equals 7 mod 10, and so it is NOT a multiple of 10. Replace 3 with r and 10 with v.

It seems this proof would have to be verified on-chain. Do you have a ballpark for the cost of the full operation? I guess it needs logarithmic exponentiations with the size of the exponent + modulo the large RSA prime (?) Don’t have a strong intuition for the gas cost of that.

Do you have a ballpark for the cost of the full operation?

The check is b^B * h^r = z. B is a 256-bit value, as is r as r < B. b and h are both RSA-modulus-sized values. So it’s two calls to MODEXP with 256-bit exponents, and two calls with a one-bit exponent plus a manually implemented adder (this is using the formula ab = \frac{(a+b)^2 - (a-b)^2}{4}).

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)

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).

2 Likes

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=gqtp1e1p2e2… where q≠pi for all i. The coin validity proof consists of a proof that qt+1 is not part of A and 1 RSA inclusion proof and merkle inclusion proof per transaction of the coin (as before).

What’s the goal here? To reduce the size of the history proof by a further ~50%? If so it does seem like that does it.

gmaxwell’s posts on this thread about RSA accumulators are worth a read, imho.

https://bitcointalk.org/index.php?topic=1064860.0

1 Like

Given that the accumulator is ever-increasing, wouldn’t we very quickly run into problems with integer overflow when representing these values (both on-chain and off-chain)?

1 Like

The multiplication is modulo some N for which we don’t know the factorization.

1 Like

How do you pick N with uknown factorization without a trusted dealer? None of the methods mentioned in Bünz’s talk seem reasonable. Is there a well established way to do that?

You can do either a secure multi party computation, or pick an RSA number such as RSA-2048.

I wrote a blogpost about accumulators and the proof of exponentiation schemes here by the way:
https://medium.com/@gakonst/deep-dive-on-rsa-accumulators-230bc84144d9

5 Likes

Note that the verifier needs to additionally check that A’ accumulates from A, ie that the product of the newly accumulated elements {x1x2 … xn} is the discrete log of A’ base A.

The proof has to be the NI-PoKE2 from Stanford’s paper, and not just the b^B * h^r = z check.

This check should be done for every published accumulator value to make sure the operator is only doing additions. See my comment on this post:Let's assign prime numbers to transactions instead of coins

If this is done, I think the b^B * h^r = z check is sufficient.

In @gakonst 's deep-dive, he cautions against using @vbuterin 's non-membership due to the lack of a formal proof. I just wanted to chime in for those not convinced by Vitalik’s argument above, with a direct constructive reduction from Vitalik’s NMP to the LLX NMP.

Suppose we’re trying to prove that a prime x is not committed to in A, and we are able to produce q,r where 0<r<x and (g^x)^q=Ag^r as in Vitalik’s scheme. First of all we can replace q\gets q-1 and r\gets x-r, so that we instead have (g^x)^q\cdot g^r=A.

Since x is prime, we know \gcd(x,xq+r)=1, since otherwise x|(xq+r)\implies x|r, but 0<r<x by assumption, contradiction. Thus by running the Euclidean algorithm on x,xq+r, we can find a,b such that ax+b(xq+r)=1. But g^{xq+r}=A by assumption, so g^{ax}A^b=g^1, which exactly means that (g^a,b) is a valid LLX proof.

EDIT/P.S.: For batched NMPs of x_1,...,x_n, it is not enough to simply make sure 0<r<\prod x_i. You further need to verify that \gcd(r,\prod x_i)=1. If x is in the accumulator, then for any arbitrary m you can produce a batch NMP for x,m that’s valid except for the fact that x|r.

5 Likes

As @gakonst explains in his deep dive, the value B should be prime and is calculated via a hash to prime function. Is there an efficient way to do a hash to prime function on chain? Or is there an efficient method to verify that a given B is calculated correctly?

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…

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?