ZCoin’s new anonymous payment system, Lelantus

This is a summary of Lelantus, the anonymous payment system coming up as a replacement of Zcoin’s current protocol Zerocoin. Lelantus hides transaction amounts and participants without a trusted setup and relies on simpler cryptographic primitives compared to something like Zcash. It also removed the need for spending or creating fixed denomination coins present in the current Zerocoin protocol and the need for RSA accumulators corresponding to each denomination.

The basic idea in Lelantus is similar to Monero (and some others) where the spender while spending a coin hides “his” coin among a set of coins (not necessarily “owned” by him) and proves to the ledger (blockchain) that he “owns” a coin in this set and the coin has not been spent yet. This set of coins is called the anonymity set for that particular spend. The reason why Lelantus sounds more attractive that Monero is that the anonymity set can be much bigger (10s of thousands) without incurring any significant performance cost as the table from their paper shows (Benchmarks on Intel Core i7 4th Gen).

Primitives

Most of the cryptographic primitives Lelantus relies on are fairly common and well understood, but the 2 most important techniques it relies on are relatively newer. They are One-out-of-Many Proofs for proving ownership of a coin and Bulletproofs for proving that the coin being created does not have a negative value or a large enough value to cause an overflow. However both of these techniques are modified and the paper contains security proof for these modifications and i am unable to understand whether those are correct ;).

1. 
   

   Commitments. Pedersen commitments are of the form gᵐ.hʳ where m is the message being committed to and r is the randomness chosen by the committer. g and h are publicly known generators. (m, r) are called the opening of the commitment. Coins in Lelantus are Pedersen commitments due to the homorphically additive nature of Pedersen commitments, meaning if you have 2 commitments C1 = gᵐ.hʳ and C2 = gⁿ.hˢ to m and n, multiplying the 2 commitments together gives you C1 * C2 = gᵐ⁺ⁿhʳ⁺ˢ, a commitment to m+n.Sometimes randomness r is also called the blinding factor of the commitment. Lelantus uses double blinded commitments meaning that in a commitment to m, there are 2 blinding factors r1 and r2 like gᵐhʳ¹jʳ².

2. One-out-of-Many Proofs. This technique is used to prove that given n commitments, the prover knows an opening of one of the commitments and that commitment commits to 0 without revealing which one. Hence given n commitments, C1, C2, …Cn, the prover proves that he knows that one of these commitments Ci open to (0, r), i.e Ci = g⁰.hʳ without revealing i. The prover does not need to know the opening to any other commitment than Ci. The proof size for “One-out-of-Many Proofs” is not linear in n but logarithimic in n. It was introduced by Jens Groth et.al in this paper and later made more efficient by J. Bootle et.al in this paper. Since Lelantus’s coins are double blinded commitments, a modified version of this technique is used where the prover proves that one of the commitments, Ci = g⁰hʳ¹jʳ² without revealing i.
3. Bulletproofs. This technique lets a prover prove that a committed value lies in a range, also called a range proof. Hence, a prover can prove that in commitment C1 = gᵐ.hʳ, 0≤m<2ⁿ for some n. Previous range proof techniques require a proof size, proving time and verification time proportional to n but with Bulletproofs, these fall down to lg(n). Again Lelantus modifies it to work with commitments of form gᵐhʳ¹jʳ².

4. 
   

   The ledger. In Zcoin’s old protocol Zerocoin, each coin was a commitment that was added to an RSA accumulator (a constant size set), in Lelantus every few blocks, a new set is created which contains commitments to the coins created in those blocks; each of these sets can be referenced with a unique id. Lets call each such set as a “coin set”. I did not find this improvement published anywhere but learned this from Aram Jivanyan, the author of Lelantus.The ledger will have a “transparent” currency meaning any transaction involving it will reveal amounts and participants. The currency supporting anonymous and confidential transactions is called “shielded” and such transactions as “shielded” transactions.

Coins and transactions

Unlike Zerocoin where coins have fixed denominations 1, 10, 25, 50, 100, Lelantus allows arbitrary value in a coin. Each coin hasi) a value Vii) a spending private key q and corresponding public key Q. The private key q is used to sign a transaction where the coin is spent and the ledger verifies the signature with public key Q.iii) a unique serial number S derived from Q by hashing, S = Hash(Q). The serial number is revealed when a coin is spent. The ledger records the serial number in a set and it only allows a spend if it has not seen the serial number before, hence S prevents double spend.iv) a random number R.The coin is represented by the commitment C = gˢh1ⱽh2ᴿ, g, h1 and h2 being 3 publicly known generators.

Lelantus has three kinds of transactions

1. Mint.

This transaction generates a new coin with a certain value. Assume that the Lelantus was deployed Bitcoin like ledger and someone owned V satoshis. If he wanted to convert his “transparent” V satoshis to a “shielded” coin that he can later use anonymously, he wouldi) Generate a spending private key q and public key Q and serial number S = Hash(Q)ii) Generate a random value R.iii) Generate the coin commitment C = gˢh1ⱽh2ᴿ.

He can now use the mint transaction to publish C to the ledger with a proof of ownership of V satoshis where the ledger will consume the V satoshis and add C to a “coin set”. But here he could cheat by creating the commitment with a value greater than V, say C = gˢh1ⱽ⁺¹⁰h2ᴿ rather than C = gˢh1ⱽh2ᴿ. To prevent this, the Mint transaction also contains a Schnorr proof of the relation C/h1ⱽ = gˢh2ᴿ which the ledger will verify as it already knows C and V. Note that the ledger only learns C and V but not S or R.

2. Spend.

This transaction does the opposite of Mint as it consumes 1 or more “shielded” coins (commitments) and gives back the “transparent” currency (satoshis) of equal value to the spender of the coins. During Spend, the spender reveals the serial numbers of the coin being spent as well as the total value of the coins being spent however which coins (commitments) are being spent is never known. The ledger will allow the spend only if a coin with the same serial number has not been spent before. Spend utilizes the homomorphic additive property of Pedersen commitments and One-out-of-Many Proofs to prove that there exist coins with the serial numbers that the spender is revealing and the spender knows V and R for such coins. To ensure spender is not spending already spent coins, the ledger ensures it has not seen the serial numbers before. An additional Schnorr proof is needed to ensure that the spent coin value is the same as the “transparent” currency value generated.

To spend a coin C = gˢh1ⱽh2ᴿ with value V, the spenderi) Chooses an anonymity set to hide his commitment in. The spender downloads these commitments from one or more “coin set”(s) from the ledger and then assembles a list L of n commitments C1, C2, C3, … Cn with some Ci being equal to C.L = [C1, C2,…..Ci,…Cn]= [gˢ¹h1ⱽ¹h2ᴿ¹, gˢ²h1ⱽ²h2ᴿ²,…. gˢh1ⱽh2ᴿ, …. gˢⁿh1ⱽⁿh2ᴿⁿ].The transaction will contain reference(s) to the “coin set”(s) used so that the ledger can create the same list L.ii) Creates a commitment D = gˢh1⁰h2⁰ and multiplies each element of L with D. L now becomes[gˢ¹⁻ˢh1ⱽ¹h2ᴿ¹, gˢ²⁻ˢh1ⱽ²h2ᴿ²,….. gˢ⁻ˢh1ⱽh2ᴿ,….gˢⁿ⁻ˢh1ⱽⁿh2ᴿⁿ]=[gˢ¹⁻ˢh1ⱽ¹h2ᴿ¹, gˢ²⁻ˢh1ⱽ²h2ᴿ²,….. g⁰h1ⱽh2ᴿ,….gˢⁿ⁻ˢh1ⱽⁿh2ᴿⁿ]iii) Uses One-out-of-Many Proofs with above list L to create a proof P that one of the commitments in L opens to 0 and he knows which one and the opening for it.iv) Creates a Schnorr proof that the “transparent” value generated is equal to V.v) Finally he signs the transaction with coin’s spending key q and reveals the public key Q.

The ledger willi) verify the signature with Q andii) recreate the list L with the references to the “coin set”(s) present in the transaction.iii) Will use the public key Q to create S and then create the same D as the spender did.iv) Modifies L as the spender did to get the sameL = [gˢ¹⁻ˢh1ⱽ¹h2ᴿ¹, gˢ²⁻ˢh1ⱽ²h2ᴿ²,….. g⁰h1ⱽh2ᴿ,….gˢⁿ⁻ˢh1ⱽⁿh2ᴿⁿ]iv) Uses One-out-of-Many Proofs to verify the proof P.v) Verifies the Schnorr proof to ensure correct V.

3. JoinSplit.

JoinSplit transaction can be considered a combination of Mint and Spend transactions as they can spend old coins and create new coins and optionally create some “transparent” value Vₜ. A JoinSplit transaction spending N old coins and creating M new coins should prove thati) He knows S, V and R for each of these N coins and none of them have been spent before. This is achieved by the same method as the used in the Spend transaction with the difference that the value V is not revealed for any coin.ii) All new coins M have a positive value and are not big enough to cause overflows. This is done with Bulletproofs.iii) The sum of value of all N old coins = (sum of value of all M new coins + any “transparent” value Vₜ). This is done with a Schnorr proof.

The verifier will now verify the N signatures and N One-out-of-Many Proofs like Spend transaction, M Bulletproofs and a Schnorr proof to ensure that the prover did not create money out of nothing. Note that the verifier only learns that the sum of the value of old coins equals the sum of the value of new coins but not the individual value of any old or new coin.

The spender should aim to use more than one such “coin set”s (created far apart in time) in a Spend or JoinSplit to avoid timing based correlation.

Anonymous payment transfer

Until now, the transactions described do not show how one party can pay another. This is achieved by the sender creating a coin such that only the recipient knows the spending private key corresponding to that coin. To spend a coin C = gˢh1ⱽh2ᴿ, the tuple (S, V, R) needs to be known. Since S can be learnt by hashing the public key Q and Q can be created with private key q, the coin can be spent with knowledge of (q, V, R).Say Alice wants to pay Bob a value V.i) Bob chooses a secret x and sends Alice gˣ.ii) Alice chooses a value y and creates gˣʸ which becomes the public key for that coin. The coin’s private key is now x*y.iii) Alice now creates a coin C = gˢh1ⱽh2ᴿ where S = Hash(gˣ*ʸ). Alice cannot spend this coin since it does not now x but Bob can if he knows y.iv) Alice can now create a JoinSplit transaction where she spends a coin she owns and creates a new coin in the above manner.v) Alice now communicates y, V and R to Bob either on a private channel or it can publish them alongside this transaction encrypted with Bob’s public key gˣ (Elgamal encryption seems appropriate).

Note that Alice can learn when Bob spends the above coin C since it knows the public key gˣ*ʸ and hence serial number S. To prevent Alice from learning Bob can swap the coin for a new coin (in a Spend+Mint) immediately.

Performance

The paper describes several optimizations like the ledger batching multiple One-out-of-Many Proofs that were created over the same anonymity set. The ledger can do some precomputations to verify these proofs faster. For the prover (spender), Bulletproofs support efficient aggregation which makes JoinSplit transactions with more than 1 new coins to have shorter proof size.However, the prover does have to download (and probably store) commitments equal to his anonymity size so for an anonymity size of 2¹⁶ commitments, the prover has to download 2¹⁶ -1 commitments and do computation (and spend time) proportional to 2¹⁶. It is yet to be seen how efficient such large computations are on light clients like mobile devices.

Thanks to the paper’s author Aram Jivanyan for answering questions regarding Lelantus.