Lelantus MW

Linkability is the Achilles' heel of MW.

Beam has several improvements to the original MW to obfuscate the transaction graph. Now we're building a hybrid, of MW and Lelantus, which should be a huge step forward in this direction.

Disclaimer

The Lelantus protocol is the work of Zcoin's cryptographer Aram Jivanyan as part of its research to improve its privacy protocol.

Our design and implementation are based on the publicly-available Lelantus scientific paper. All our code was developed from scratch based on this paper alone.

Our design

To fit our needs and utilize the full power of MW we made several modifications to the original protocol.

1. Instead of focusing on transaction types described in the paper (Mint, Spend, Joint-Split) we implement this in terms of primitives, which can be combined and used in various transaction types.
2. Minted/spent values are never revealed.
3. We use other technique to prove the transaction balance. We removed the balance proof from the original Lelantus protocol, hence it's now closer to the original Sigma protocol by Jens Groth.

MW blockchain consists of the following objects (primitives):

1. Inputs - references to existing UTXOs, that are being spent
2. Outputs
3. Transaction kernels

Our design, which we call Lelantus-MW, keeps this structure, and the Balance-to-zero principle also holds. All those 3 object types, however, are modified to support Lelantus.

We use the following notation in the code:

• G - generator (nothing-up-my-sleeve EC point) multiplied by UTXO blinding factor
• H - generator multiplied by UTXO Value
• J - generator multiplied by UTXO 2^nd blinding factor (i.e. double-blinded commitment).

Outputs

Normal MW output consists of a Pedersen commitment (EC point) and the Bulletproof signature. After validation it's added to the UTXO set, and later can be referenced as inputs in consequent blocks/transactions.

The modified output, used in Lelantus, is called Shielded output. Unlike normal output, shielded output is double-blinded, hence its bulletproof is (slightly) extended.

After validation it's added to the Shielded pool (rather than UTXO set).

Kernels

As we said, shielded outputs are double-blinded. Hence, in order to keep the balance-to-zero principle, transaction kernels can optionally contain the 2^nd blinding factor excess as well. So that transactions are allowed to have excess of both blinding factors, but not the value (obviously).

Such kernels are signed by generalized Schnorr's signature (rather than normal Schnorr's signature), to prove that their revealed commitment is indeed of the form k*G + s*J

Note: the generalized Schnorr's signature does not reveal which part of the kernel commitment is due to each of the blinding factors. I.e. the attacker can't split it into k*G and s*J. This is important, as the 2^nd blinding factor (a.k.a. serial number) eventually gets revealed, there is still no way to identify its corresponding transaction kernel.

Inputs

Normal inputs are just commitments (EC points) that correspond to previous outputs that must be in the current UTXO set.

Shielded inputs, in addition to the commitment, have the Spend Proof, which proves that:

• A valid shielded element is being-spent
• No double-spend
• The specified input commitment encodes the value equal to the one being spent (with different blinding factor though).

Spend Proof

In the original Lelantus paper the proof idea is the following:

• Convert the revealed public Spend Key into serial number s
• Subtract (methodically) s*J from each commitment in the referenced anonymity set (a.k.a. cmList)
• Prove the knowledge of the opening of one of the elements in the form of k*G + v*H, i.e. without the serial number
• Additionally prove that the revealed being-extracted value corresponds to the value of that element
  • For this the original Sigma protocol was modified

We modified it into the following:

• Convert the revealed public Spend Key into serial number s
• Prove that the revealed commitment C is of the form k*G + v*H, i.e. does not conceal additional serial number
• Subtract (methodically) s*J + C from each commitment in the referenced anonymity set
• Prove the knowledge of the opening of one of the elements in the form of k*G only, i.e. without the serial number or additional value

In such a scheme there is no need to provide additional balance proof, since the value of extracted commitment should be the same as of the element being-spent. Because of this there is also no need to prove the value is non-negative (by bulletproof), as it was already proven when the element was added to the shielded pool.

So, the whole Spend proof, in addition to the commitment being-extracted, contains the following:

• Generalized Schnorr's proof that this commitment is of the form k*G + v*H
• Public spend key, and the whole spend proof is signed by the appropriate private key
• Standard 1-out-of-N Sigma protocol in terms of a single G-generator only.

Compared to original Lelantus paper

What is similar:

• Shielded outputs are double-blinded, with the appropriate (extended) bulletproof signature
• To spend a shielded element the public Spend Key must be revealed, and the Spend Proof must be signed by the appropriate private key
• Spend proof is also based on the 1-out-of-N Sigma protocol (by Jens Groth)

What is different:

• Rather than specifying transactions, Lelantus-MW is formulated in terms of inputs and outputs (i.e. MW-style). Hence:
  • Just a single type of shielded input and output primitive is enough
  • Transactions are easily merged (as usual)
  • Despite better size and verification time, we don't implement multi-input spend proofs.
    • Limiting all the inputs to the same anonymity set seems to be practically restricting
    • This also potentially reveals their linkability
• Added/spent values are never revealed
• Separate balance proof is not required: it's an inherent part of each MW block/transaction.
• Spend proof is improved
  • Implemented in terms of classical (unmodified) Sigma protocol
  • Significantly smaller size
  • Better verification time
    • Significant in batch mode, when all the proofs refer to the same anonymity set