Silk Road forums

Same here. I also doubt it's the server itself. At first I thought along the lines of a SYN flood, where the server is still able to build circuits but too many are left half open for it to manage. Since I don't think that's possible (or effective) over tor--and as kmf said you don't get the "server out of resources" message--it likely is an attack on the only nodes the attackers can reasonably find: the entry nodes.

On the other hand, I can still build circuits to the SR server, at least as of this post. HTTP connections still close immediately though. It's almost like the old ICMP/TCP RST attacks from back in the day, although I don't see how that would work here. lol

Not likely a DoS of the entry guards. Unless strict entry guards are used, the hidden service will switch to a new entry guard temporarily while one of its previously selected ones is down. The attacker would need to DoS a lot of entry guards simultaneously to prevent access to a hidden service. They would probably be able to brute force deanonymize it with mass entry guard DoS + timing attack before they could block access to it in this way. It looks very much like itnroduction node DoS.

The behavior that you describe sounds like what I was seeing on the forums when they suffered down time, and is indicative of a crashed Apache. However, I am personally incapable of establishing a circuit to the marketplace.

A quick way for SR staff to confirm that this is the problem, is to create a new .onion address pointing to the same port as the original one. This will use a different set of introduction nodes, and as the address will not be made public, the attacker will not DDoS those introduction nodes. If they can access the site with this new .onion address, then it is definitely the introduction nodes being DDoSed. Keep in mind sometimes it takes a little bit to access a newly created / launched hidden service though.

Somebody with access to the SR server should type in the command top and see if the CPU is at 100%, or if the memory is exhausted. In either case they should see which process is using all the CPU or Memory.

The entire time the forum was down I had no trouble establishing an open circuit to dkn255hz262ypmii.onion. I even closed the open circuits I established a few times and rinsed and repeated, and never had any trouble establishing an open circuit. The problem was that streams through the circuit were going from connecting to closing almost immediately, without ever opening. That is indicative of Tor on the hidden service redirecting traffic to a port that has nothing listening on it. Do an experiment, configure a hidden service yourself but don't run anything on the port that you have it redirect traffic to. Now connect to the hidden service. You will see the same exact behavior, the circuit is established without problems, but the streams through the circuit quickly go from connecting to closed. I am pretty much absolutely certain that the actual forum server did not experience any down time, and I am equally certain that the introduction nodes behaved correctly and were not DDoSed. Tor on the remote server (dkn255hz262ypmii.onion) was running and operating perfectly for the entire duration of the down time (that I witnessed anyway, which was quite a while but probably not from the very start). The problem was that it was redirecting traffic to a port that had nothing listening on it, or something malfunctioning listening on it. This means that the problem was with Apache (and very likely it had crashed). Towards the end of the down time Apache started working correctly, because the streams were going from connecting to open to closed, and a 500 error was returned on valid pages and 404 on invalid pages. This suggests to me that the problem at this point was with PHP, but it could have been an Apache problem as well. It looked like Apache kept crashing and coming back up, because it would go from rarely loading with a 500 internal server error, to forming a circuit to the remote instance of Tor, but with streams through it going from connecting to closed. 

I am positive that the server hosting this forum did not go down nor was it overwhelmed with bandwidth. I am also 100% positive that the introduction nodes were not DDoSed. I am less sure, but still quite confident, in saying that the down time was caused by Apache crashing.

I don't know about any particular vulnerability in regards to Silk Road. I will say that I have seen some less than ideal configuration though, for example having detailed error messages enabled in a production site. At the end of the day the security of a site like SR is not of utmost importance for customers, they must handle their security themselves and not rely on an non compromised server. The primary things that present real problems are things like DoS attacks , and of course the risk to DPR and vendors that hackers could steal the escrow. Although this is only ideally, as we all know that most users here do not encrypt their addresses with GPG, etc, and thus they needlessly make it so that they do indeed rely on the security of the server hosting the site.

As far as the DoS of SR goes, I cannot say much without knowing specifics of the attack. I don't go to the SR marketplace ever, but I did notice a few things when the forums were said to be being DDoSed. The first thing I noticed is that Tor was indeed building a circuit to the instance of Tor running on the server hosting this forum. It was just immediately closing streams through it. This means that the introduction nodes were not being DDoSed, it also means that the server was not being overwhelmed with bandwidth. If the introduction nodes were inaccessible, I would not have been able to successfully build a circuit that communicated with the instance of Tor running on the server. This also means that the server itself was clearly running and had sufficient bandwidth available, otherwise it would not have a running instance of Tor capable of establishing a connection. It seems to me that the problem is with the actual web server, Apache I believe. The connection to the instance of Tor running on the SR forum server was working fine for the entire time, however after establishing the circuit the streams through it were immediately closed by the remote host. This is what we would expect to see if Tor was running and configured to redirect incoming traffic to a port that had nothing listening on it, or had something malfunctioning listening on it.

Another thing I noticed is that intermittently Apache began working again, and the circuit built to the instance of Tor on the forum server was useful for maintaining open streams. During the brief periods in which this happened the server returned 500 errors when attempting to access legitimate pages, but when attempting to access pages such as  http://dkn255hz262ypmii.onion/made_up_not_real.php it was returning 404 errors as normal. I see that now attempting to load false .php pages is returning a 'No input file specified' error , and attempting to load any .html page loads the forum index, so apparently they changed something since the forums went down. It didn't take long before the intermittent 500 error messages were replaced with a maintenance message, and the forum came up shortly after that.

My impression of the down time for the forum was that their instance of Apache kept crashing and being brought back up. Definitely the server itself remained reachable the entire time, and connections to their hidden service were also flawless the entire time, it is just that Tor was apparently redirecting the traffic to a port that had nothing listening on it. That said, it doesn't rule out a DoS attack. Perhaps the attacker exploited a remote flaw in Apache, or somewhere in the configuration, and kept remotely crashing the web server. But it does pretty definitely rule out a bandwidth flooding DDoS, and also rules out a DDoS on the introduction nodes, and a DoS of the box itself.

The first step of determining what went wrong is finding why there was a 500 error being returned. I cannot do this without access to Apache error logs from the server. Searching shows that 500 errors are pretty ambiguous and can refer to a wide variety of different things. Maybe it was caused by a PHP misconfiguration or crash, and that is why fake .php pages were returning 404 errors but real ones were returning 500 errors. The real root of the problem is probably figuring out why Apache was crashing  / PHP was throwing a fit or crashing.

edit: to the above poster, bitcoin is not mostly anonymous, in fact it is entirely non anonymous and totally public record.


I think it is going to be hard to really understand Zerocoin at a low level if you can't figure out what the set of formulas in appendix B means. It explains their zero knowledge proof of knowledge algorithm. I tried to paste it here, but it cannot be displayed correctly. Needless to say, it looks like it is pretty advanced.

[edit: removed formulas because pasting them fucked up all formatting and some characters cannot be displayed]

One of the reasons why it is hard to figure out what is going on in this paper is because it is actually discussing at least three different things: a system to prevent double spending, a system to allow for anonymous spending and a way to integrate all of this with the current Bitcoin network. Also they are describing the systems that they use briefly, to really have a good chance of understanding this you should also read the cited papers , for example there is an entire paper dedicated to the accumulator and blind witness technique that they are using, but they summarize it in a few paragraphs.

So, the user generates a zerocoin (C) which is a commitment to the coin serial number (S). C is unlocked with a random number (R) into S. At the risk of being repetitive, I will repost the example of such a mechanism that I showed previously:

The Commitment (coin)      C    = fc4b5fd6816f75a7c81fc8eaa9499d6a299bd803397166e8c4cf9280b801d62c
The Random Number         R    = 0283da60063abfb3a87f1aed845d17fe2d9ba8c780b478dc4ae048f5ee97a6d5
The coin serial number      S    = efdf88c3315309fa0d4245389d79e035cd761813b85a954f2b924f81ee6bb248

because SHA256(C || R) == S

Now the user needs to add the value C to a public accumulator. As I mentioned before, accumulators are constructs such as bloom filters, they are for checking for set membership of an object. It is probably even correct to consider a list of items as an accumulator, which can be checked to see if it contains element A with the algorithm (A == A1) OR (A == A2) OR ... OR (A == An). This OR based example is actually about the worst possible performing accumulator possible, but I just am trying to show that all an accumulator is , is something that can be queried with some data (a witness, the object itself in the previous example) to determine if the queried for item is present. 

Now one of the most tricky things to wrap your head around is how the Zerocoin accumulator is queried for element C, and this is really the heart of Zerocoin. Now in the OR based example I just now wrote about, the verifier is given the actual item to check for its presence in the accumulator. In a bloom filter, they are given the item itself as well in some cases, or in others just the items hash. Regardless, the point is that in both of these examples the verifier can determine which element the client is checking for the presence of , if the verifier knows all the items that have been accumulated. The Zerocoin scheme allows for the client to prove to the verifier that it knows an element in the accumulator, without the verifier being able to determine anything about which of the elements in the accumulator the client is proving that it knows about. Put another way, the Zerocoin accumulator scheme allows the client to prove to the verifier that it has a Zerocoin in the accumulator, without revealing which of the Zerocoins it is (this mechanism is where the anonymity comes from). Even more impressively, it allows the client to prove that the element (C) which is present in the accumulator (ie: the Zerocoin the client has in the accumulator), opens up to serial number S (something that would only be known by the person who created the element C in the first place), without the verifier being able to determine which of the C's in the accumulator open up to S, and without the verifier learning the secret number R (this mechanism protects from double spending, and keeps the person who put the Zerocoin into the accumulator in charge of it)!

The anonymity of Zerocoin is derived from the fact that the verifier cannot determine which element C the client proves knowledge of (ie: the client can prove that it has a Zerocoin in the accumulator without revealing which of the Zerocoins it is). So Alice adds an element C to the accumulator (ie: Alice gets a Zerocoin). Of course, she also needs to be charged some bitcoins to add the element to the accumulator (ie: She needs to buy the Zerocoin from the Bitcoin network with Bitcoins), and I believe this is where the full Bitcoin integration request comes from. They want the current Bitcoin network to be modified so that Alice can essentially return X Bitcoins to the entire network, so that they are not under the control of anybody anymore, and in return for doing this Alice can add an element C worth that value of Bitcoins to the accumulator, which they also want to be run distributed over the Bitcoin network. After sending X Bitcoins back to the network and then adding element C to the accumulator, Alice can use the Zerocoin proof of knowledge formula to create what I will call a blinded witness (and what the paper calls a zero knowledge signature of knowledge). The blinded witness is the information that allows Alice to prove to the verifier that she knows of an element C in the accumulator (ie: it lets her prove that she has a Zerocoin in the accumulator), and to prove that the element C opens up to the never before used serial number S (ie: it lets her prove that she has not spent the Zerocoin before). I actually would prefer calling the  (Blinded Witness, Serial Number) pair a Zerocoin, rather than the value C in the accumulator. However, in order to not go against the terminology defined in the paper, I will instead call the (Blinded Witness, Serial Number) pair a "Bitcoin Redemption Slip", or BRS for brevity. Alice could very well send her BRS to Bob, who she is doing business with. However, it makes a bit more sense for Alice to merely use her BRS to have coins sent to Bobs Bitcoin address. There are actually a lot of different ways in which it can be used. Assume that Alice actually does send her BRS to Bob.

Now after Bob obtains the BRS from Alice, he can send it to the Bitcoin network, where the blinded witness is used with the Zerocoin zero knowledge system to prove that:

A. Bob put a value C (aka: Zerocoin) into the accumulator (or, in this case, Bob was sent a BRS by somebody who did)
and
B. Bob knows a unique value S which C opens up to (which means that the BRS has never been used before)

Thanks to the cryptographic properties of the Zerocoin accumulator and zero knowledge proof of knowledge scheme (blinded witness) , the verifier cannot link Bob to any specific C in the accumulator, despite being able to tell that Bob (or somebody who did business with Bob) put a C into the accumulator. This means that the verifier cannot link Bob to Alice. Now that Bob has proven he has a Zerocoin in the accumulator, the Bitcoin network releases a Bitcoin to whatever Bitcoin address Bob tells it to, and it takes the released Bitcoin from the no mans land that Alice put them into, in order to put a C of equivalent value into the accumulator and get a BRS in the first place. Additionally, the network keeps track of serial number S, so that nobody can ever redeem the associated BRS for a Bitcoin again (ie: nobody can double spend).

Now a passive adversary who observes the blockchain can determine that Alice put some Bitcoins into no mans land, and that Bob took some Bitcoins out of no mans land, but that is all of the information that they can get. If enough people are using the Zerocoin system, and the C values are standardized denominations, then the sheer volume of traffic will prevent traffic analysis from being carried out to link Bob and Alice. Additionally, because of the Zerocoin accumulator and ZKPOK properties, even the Bitcoin network / verifier itself cannot link Alice to Bob.


If Alice redeems the BRS herself, in order to send Bitcoins to Bobs Bitcoin Address, rather than sending Bob the BRS for him to exchange for bitcoins himself, Alice will still learn one of Bobs bitcoin addresses. Since Bob doesn't trust Alice, he will be smart to then spend this Bitcoin on yet another BRS , and then redeem his new BRS for Bitcoins sent to another Bitcoin address that Alice is unaware of. By Bob taking this final step, Alice and Bob will not only be protected from being linked together by any third parties, but additionally Alice will be prevented from determining the Bitcoin address that Bob cashes out from.

edit: Well I finished reading the entire paper, and a lot of it is above my head. Regardless, I will share the thoughts and limited insights I have obtained from the paper. Chances are if I read it several dozen more times, in addition to the cited papers included in it, that I can come to a pretty good understanding of it. I have decoded and come to understand complex technical papers such as this in the past, but only with great effort and much time.

So I am reading through the Zerocoin spec after having skimmed it. I can tell you right now that a lot of the cryptography goes over my head, but I am familiar with a lot of the terms used, if not the details of the math behind them. I will post my thoughts in this message, which I am constructing as I read through the paper, in the hopes that I can shed some (likely limited) light on the details of zerocoin.

The first thing I will do is clarify some of the technical terminology that I see.

One thing I see is 'commitment'. An example of commitment in a cryptographic sense would be if you and I play a game of heads or tails. I flip the coin. First I take the string heads-ewijfifjw89hj83429f89342fuejgueju and hash it with sha256 to get the following hash value:

500ec7db996ec36ef30bb7b2881cd6c99f3347e3785edb3bce5cfb3a78977b6a

Now I send you that value, and in doing so I have committed to heads. I ask you to select heads or tails. After you make your selection, I show you the string that I used to generate the hash value, and you hash it to confirm if I have been honest. If I cannot show you a string starting with the correct answer that SHA256 hashes to what I showed you before you selected heads or tails, then you know I am cheating. So by sending you the hash value I did, I have cryptographically committed to heads.


Another terminology I see is zero knowledge proof of knowledge. These schemes are generally used for identity authentication, in a way that is more secure than passwords. With traditional password authentication, I register with a server and give the server my password, it hashes the password and stores it associated with my name. With zero knowledge proof of knowledge, I send the server a zero knowledge public key. The server can use the public key to craft challenge questions that can only be consistently correctly answered by someone with the corresponding private key, but the answers are easy to verify as true or false. The server then sends me a bunch of challenge questions crafted from the public key, I derive answers with the private key and send them to the server, and the server verifies that all of the answers are correct. It is called a zero knowledge proof of knowledge because unlike with passwords, where the server gets knowledge of my password in order for me to prove that I know the password, the server does NOT get knowledge of my private key to determine that I have my private key. A naive and insecure implementation, but one which is easy to explain, would be if I send the server my public RSA key, and to authenticate with the server it generates a random timestamped string, sends it to me, has me sign it with my RSA private key, and then verifies that the signature is valid after I send it back the signed timestamped string.

Another technical term I see is cryptographic accumulator. I have read about accumulators a little bit in the past, but I never really fully wrapped my head around them. I believe that bloom filters qualify as accumulators though, and I understand how bloom filters work. Bloom filters are used to check for the presence of an object in constant time, while taking up little storage space. Essentially a blank bloom filter consists of a ton of zero bits at various positions from 0 to whatever. When you add an item to a bloom filter, you hash it and use the hash to derive a series of numbers. The derived numbers then correlate with positions in the bloom filter, and you set all of the positions to 1 to add the item. When you check for the presence of the item, you hash it and derive bit positions as before, but now you check that all of the bit positions are set to 1. This is much faster than keeping a list of hashes of seen objects and going through the entire list looking for a match. If you have a database of ten thousand item hashes, you may need to search through all ten thousand of them before determining if the item has been seen before or not. With a bloom filter, you always only need to hash the item and check the bit values at each of the positions in the filter, so the time to check for the presence of the item is constant time and doesn't grow with the number of items added (although the accuracy of the bloom filter drops with the number of items added, and increases with the bit size of the filter). 


Anyway, on to the paper.

One thing I note is that they are indeed making a new type of coin, so to speak. However, their goal is for its value to be inherently tied to the value of Bitcoin, and for it to piggy back on top of the current Bitcoin network. Whereas in the past blind mixes have been used to achieve what they are trying to achieve, the primary challenge they claim to have addressed is creating a blind mix that doesn't have a central authority for minting blind tokens. They claim to address this by letting any user mint their own blind token, but the challenge then is to make it so users can only mint valid blind tokens if they spend an equivalent amount of Bitcoins.

ntuition behind our construction. To understand the intuition
behind Zerocoin, consider the following “pencil and paper”
protocol example. Imagine that all users share access to
a physical bulletin board. To mint a zerocoin of fixed
denomination $1, a user Alice first generates a random coin
serial number S, then commits to S using a secure digital
commitment scheme. The resulting commitment is a coin,
denoted C, which can only be opened by a random number
r to reveal the serial number S. Alice pins C to the public
bulletin board, along with $1 of physical currency. All users
will accept C provided it is correctly structured and carries
the correct sum of currency.
To redeem her coin C, Alice first scans the bulletin board
to obtain the set of valid commitments (C1 , . . . , CN ) that
have thus far been posted by all users in the system. She next
produces a non-interactive zero-knowledge proof π for the
following two statements: (1) she knows a C ∈ (C1 , . . . , CN )
and (2) she knows a hidden value r such that the commitment
C opens to S. In full view of the others, Alice, using a
disguise to hide her identity,1 posts a “spend” transaction
containing (S, π). The remaining users verify the proof π
and check that S has not previously appeared in any other
spend transaction. If these conditions are met, the users allow

In this case we need a secret number R that unlocks the commitment C to obtain S.

The Zerocoin                     C    = fc4b5fd6816f75a7c81fc8eaa9499d6a299bd803397166e8c4cf9280b801d62c
The Random Number    R    = 0283da60063abfb3a87f1aed845d17fe2d9ba8c780b478dc4ae048f5ee97a6d5
The coin serial number S    = efdf88c3315309fa0d4245389d79e035cd761813b85a954f2b924f81ee6bb248

because sha256sum(C concatenated with R) == efdf88c3315309fa0d4245389d79e035cd761813b85a954f2b924f81ee6bb248 == S

We also need a zero knowledge proof π , demonstrating that she has the secret random number R, and that she knows a published C that is unlocked by R into S. I will need to keep reading to see how they achieve this, the basic sketch up on page 2 is interesting but it says the what without saying the how. Maybe they cannot even use the hashing commitment that I use in the above example, I will need to see...

Of course, even when integrated with the Bitcoin block
chain, the protocol above has another practical challenge.
Specifically, it is difficult to efficiently prove that a commit-
ment C is in the set (C1 , . . . , CN ). The naive solution is to
prove the disjunction (C = C1 ) ∨ (C = C2 ) ∨ . . . ∨ (C =
CN ). Unfortunately such “OR proofs” have size O(N ),
which renders them impractical for all but small values of
N.

The complicated seeming naive solution they posted simply means going through the entire list of commitments and seeing if there is a match, because bitwise OR gets stuck on 1 which is true. 1 is true, 0 is false.

(a = = b) OR (a == c)

is the same as saying 0 OR 0 which evaluates to 0.

(a == a) OR (a == b) OR (a == c)

evaluates to 1 OR 0 OR 0 which evaluates to 1 because anything OR 1 is 1.

This is a computationally expensive operation to carry out for large sets of N, because they would exhaustively search the entire list of commitments. One of the contributions they claim to have made is an accumulator that solves this problem.

Our second contribution is to solve this problem, producing
a new construction with proofs that do not grow linearly as
N increases. Rather than specifying an expensive OR proof,
we employ a “public” one-way accumulator to reduce the
size of this proof. One-way accumulators [10, 11, 12, 13, 14],
first proposed by Benaloh and de Mare [10], allow parties to
combine many elements into a constant-sized data structure,
while efficiently proving that one specific value is contained
within the set. In our construction, the Bitcoin network com-
putes an accumulator A over the commitments (C1 , . . . , CN ),
along with the appropriate membership witnesses for each
item in the set. The spender need only prove knowledge of
one such witness. In practice, this can reduce the cost of the
spender’s proof to O(log N ) or even constant size.

Although I don't know what their accumulator (A) is like, I am currently conceptualizing it as a bloom filter because that is the only sort of accumulator I know the technical details of. So rather than doing an exhaustive search for the Zerocoin C, they are creating something like a bloom filter and adding each of the values of C to it, I think that the hash value of C is a witness (what is used to determine the presence of C in the filter), however I am not totally clear on this terminology (despite seeing it in papers on cryptographic accumulators that I have skimmed yet failed to fully comprehend).

Our application requires specific properties from the
accumulator. With no trusted parties, the accumulator and
its associated witnesses must be publicly computable and
verifiable (though we are willing to relax this requirement
to include a single, trusted setup phase in which parameters
are generated). Moreover, the accumulator must bind even
the computing party to the values in the set. Lastly, the
accumulator must support an efficient non-interactive witness-
indistinguishable or zero-knowledge proof of set membership.
Fortunately such accumulators do exist. In our concrete
proposal of Section IV we use a construction based on the
Strong RSA accumulator of Camenisch and Lysyanskaya [12],
which is in turn based on an accumulator of Baric and
Pfitzmann [11] and Benaloh and de Mare [10].

Okay, bloom filters to the extent that I understand them are out. They meet the requirement of being publicly computable and verifiable, but I don't know of a way to query them with a zero knowledge proof. I assume this means that it must be possible for a user to prove knowledge of a member in the set without revealing the specific member in the set that they have knowledge of to the verifier. With a bloom filter you would need to reveal the value C, or the witness computed from it, to the verifier, in order for them to determine the presence of C in the filter.

One illustration of this is the existence of
laundries that (for a fee) will mix together different users’
funds in the hopes that shuffling makes them difficult to
trace [2, 6, 7]. Because such systems require the users to trust
the laundry to both (a) not record how the mixing is done
and (b) give the users back the money they put in to the pot,
use of these systems involves a fair amount of risk.

Although the current bitcoin "laundry" (mixing) services require the user to trust a and b, there are centralized blind mixing schemes that do not require the user to trust a. b is the problem that remained for blind mixing systems, and hopefully this is the issue that Zerocoin will have solved.

Additionally, they
describe an efficient zero-knowledge proof of knowledge that
a committed value is in an accumulator. We convert this into
a non-interactive proof using the Fiat-Shamir transform and
refer to the resulting proof using the following notation:

NIZKPoK{(v, ω) : AccVerify((N, u), A, v, ω) = 1}.

So essentially they are using a zero knowledge proof of knowledge to determine if something exists in the accumulator. This would be like a verifier determining if an element is in a bloom filter without being given the element they are checking for. I don't understand most of the math they have demonstrated up to this point, but I can understand the "what" and the "why" or their writings so far, just not the "how". Although it is not accurate, I am going to continue conceptualizing this as a bloom filter that can be queried with a blinded witness to determine the presence of an element. A non-interactive proof simply means that there does not need to be back and forth between the verifier and the client (ie: instead of the server generating a random timestamped string and sending it to the client to sign, the client simply signs anything with their key and sends it to the server to verify the signature of. Both of these examples are horrible authentication systems, but I just use them to try to demonstrate the difference between an interactive and a non-interactive zero knowledge proof of knowledge).

We now describe the algorithms:
λ
• Setup(1 ) → params. On input a security parameter,
run AccumSetup(1λ ) to obtain the values (N, u). Next
generate primes p, q such that p = 2w q + 1 for w ≥ 1.
Select random generators g, h such that G = g =
h and G is a subgroup of Z∗ . Output params =
q
(N, u, p, q, g, h).
∗
• Mint(params) → (c, skc). Select S, r ← Zq and
S r
compute c ← g h mod p such that {c prime | c ∈
[A , B ]}.11 Set skc = (S, r) and output (c, skc).
• Spend(params, c, skc, R, C) → (π, S). If c ∈ C
/
output ⊥. Compute A ← Accumulate((N, u), C) and
ω ← GenWitness((N, u), c, C). Output (π, S) where π
comprises the following signature of knowledge:12
π = ZKSoK[R]{(c, w, r) :
AccVerify((N, u), A, c, w) = 1 ∧ c = g S hr }
•
Verify(params, π, S, R, C) → {0, 1}. Given a proof π,
a serial number S, and a set of coins C, first compute
A ← Accumulate((N, u), C). Next verify that π is the
aforementioned signature of knowledge on R using the
known public values. If the proof verifies successfully,
output 1, otherwise output 0.

Sorry but I can not immediately make sense of this math. I am sure if I spent some time on it I could wrap my head around it much better, but I am not skilled enough to read this and immediately decode what is going on. I can see they are using RSA though .

We now consider the security of our construction.
Theorem 4.1: If the zero-knowledge signature of knowl-
edge is computationally zero-knowledge in the random oracle
model, then Π = (Setup, Mint, Spend, Verify) satisfies the
Anonymity property.
We provide a proof sketch for Theorem 4.1 in Appendix A.
Intuitively, the security of our construction stems from the fact
that the coin commitment C is a perfectly-hiding commitment
and the signature proof π is at least computationally zero-
knowledge. These two facts ensure that the adversary has at
most negligible advantage in guessing which coin was spent.

So the summary is that they have created a decentralized blind mix using zero knowledge proof of knowledge combined with a special cryptographic accumulator.

While the construction of the previous section gives an
overview of our approach, we have yet to describe how our
techniques integrate with Bitcoin. In this section we address
the specific challenges that come up when we combine a
decentralized e-cash scheme with the Bitcoin protocol.
The general overview of our approach is straightfor-
ward. To mint a zerocoin c of denomination d, Alice runs
Mint(params) → (c, skc) and stores skc securely.13 She
then embeds c in the output of a Bitcoin transaction that
spends d + fees classical bitcoins. Once a mint transaction
has been accepted into the block chain, c is included in the
global accumulator A, and the currency cannot be accessed
except through a Zerocoin spend, i.e., it is essentially placed
into escrow.

Whew hopefully away from the "Makes my head hurt" section of the paper now. As you can see from the above paragraph, Zerocoin is a separate currency system, but the value of a Zerocoin is inherently tied to the value of a Bitcoin, and it piggy backs on the network. In order to get a Zerocoin, Alice must spend a Bitcoin, apparently the Bitcoin does not go to anybodies actual wallet but rather is associated with the Zerocoin C that Alice has minted.

So in summary I do not fully understand the "how" of what is happening here, but I do have a pretty decent grasp on the "why" and the "what". Zerocoin is a decentralized blind mixing scheme that they propose be integrated with Bitcoin, although it can also run separately of it. It is the first decentralized blind mix in the literature, and is bleeding edge if it lives up to its claims (I certainly am not capable of verifying its security). It is based off of a special sort of cryptographic accumulator that is compatible with blinded witnesses, zero knowledge proofs of knowledge for computing blinded witnesses and cryptographic commitment schemes. It is a separate currency from Bitcoin, but they propose that it be merged into the Bitcoin network in such a way that the value of a Zerocoin is inherently linked to the value of Bitcoin it can be redeemed for. They want to piggy back on top of the established Bitcoin network for many of the components required for their system. In essence, their goal is to cryptographically obfuscate the transaction history of Bitcoin, which is currently public knowledge. They claim to have addressed several issues, primarily they remove the need to trust a traditional laundering service from linking input and output coins, and more importantly they give the security assurances of blind mixing while removing the ability of a centralized authority (the blind mix) to steal the bitcoins sent through them.

I can say that I am actually very excited about Zerocoin and that I think it will be a massive improvement for Bitcoin. People who can read that paper once and understand it fully will need to verify that the math and logic are sound though.