ZEROCOIN Breakdown..

[spartacusrex]

Hello Friends! It's good to have the forum back..  

Now - to business.

I am trying to get my head around the ZEROCOIN protocol. It's mathematical workings.. Not how it is integrated with bitcoin, this I get.

I can see that the accumulator works on the principal that

f(x,y)n = (x^y) mod n

Is a quasi-commutative hash function.

eg

For any n

f(f(f(4,5),6),7) = f(f(f(4,7),5),6) = Accumulated-Value = AV

This is great, and I understand that you can then prove that your number was used in the construction by summing all the other numbers and leaving your number till last..

So that IF 6 was the number that you added in the previous example..

f(f(f(4,5),6),7) = AV

we can show that if

f(f(4,7),5) = DELTA

then

f(DELTA, 6) = AV

Thus showing that 6 was indeed used to construct AV in the first place.. Since as a HASH function calculating DELTA afterwards is very hard.. (Almost Impossible..)

Obviously MUCH BIGGER numbers are used in practice..

As you can see though, you need to show your value of 6, to prove your membership.. How to do this without giving that away is the zero proof bit.

What I need to know is how the ZERO PROOF bit at the end works. I have read the papers OVER and OVER and all though I am sure my maths CAN handle it, the notation it is described in is just a bit beyond what I can understand.. :-p

I can see that the number you add is the HASH of some concatenated values.. but what, where, how and why still eludes me..

Can some one explain in SIMPLE terms what the number you would add to the accumulator would need to be, how it is constructed, and how you would show with ZERO KNOWLEDGE that your number was part of the accumulated value ?

I hope this makes sense..

[adam3us]

Can some one explain in SIMPLE terms what the number you would add to the accumulator would need to be, how it is constructed, and how you would show with ZERO KNOWLEDGE that your number was part of the accumulated value ?

I hope this makes sense..

Try this explanation:
accumulators and ref to outline: https://bitcointalk.org/index.php?topic=175156.45 (sounds like you got this one)
the ZKP that a=c^w without revealing c & w: https://bitcointalk.org/index.php?topic=175156.msg2378622#msg2378622 and more detail https://bitcointalk.org/index.php?topic=175156.msg2381470#msg2381470

Adam

[spartacusrex]

Thanks Adam.

That's almost EXACTLY what I was looking for.. ;-p

BUT - If I may espouse my ignorance a little further.. and continuing on my one-line one-equation policy..

I can now see that the number you choose to add to the accumulator, call it ZC is created like so :

We have a HASH function H(s,r) = g^s * h^r  where g and h are two generators in the shnorr group of size q.. (get to that later)

^ is modular exponent
* is modular multiplication..

ZC = H(s,r)

Where s is the coin serial number, and r is a random number. ZC has to be prime, and you alter the random number until it is.

Now the accumulator adds all the ZC's produced by people to represent their coins.. the final value is AV.

Then to prove your membership you need only show that you know

AV = w^c BUT without publishing w and c..

You DO publish s?, which you used in your creation of the ZC, but not the random number r..

SO - we have w,c,r are unknown AND s,AV  are known as well as all the ZC's published earlier.

I hope that's right.

...A==w^(g^s*h^r) and they were able to find a somewhat large way to prove that without revealing c,w,r. Its large because it involves multiple cut-and-choose rounds as each round is only 50:50 convincing that what the prover claims is true.  After 80 rounds its security is 1/2^80 which is quite good.

This bit.. Can you show what you mean by the cut and choose rounds ?

What would the first few rounds look like.. ?

Can it be shown using my earlier post example with small numbers of f(f(4,5),7),6.. etc ?

As in

f(DELTA,6) = AV

if '6' was constructed with H(s,r) , this would need to be proved without publishing DELTA or 6.. ?

Thanks again for explaining so thoroughly.