Skip to main content

Zero-Knowledge Proofs

Zero-knowledge proofs are tools that allow users to prove certain properties of encrypted data. Most of the zero-knowledge proofs that are used in the confidential extension are relatively small systems that are specifically designed for the simple use-case of the confidential extension. Due to their simplicity, none of the zero-knowledge systems that are used in the program require any trusted setup or sophisticated circuit design.

The zero-knowledge proofs that are used in the confidential extension can be divided into two categories: sigma protocols and bulletproofs. Sigma protocols are simple systems that are tailor designed for the confidential extension use-cases. Bulletproofs is an existing range proof system that was developed in the specified paper.

Transfer Instruction Dataโ€‹

The confidential extension Transfer instruction data requires a number of cryptographic components. Here, we provide intuition for each of these components by building the transfer data in a series of steps.

struct TransferData {
...
}

ElGamal Public Keysโ€‹

A transfer instruction has three associated ElGamal public keys: sender, receiver, and auditor. A transfer instruction data must include these three encryption public keys.

struct TransferPubkeys {
source_pubkey: ElGamalPubkey,
destination_pubkey: ElGamal Pubkey,
auditor_pubkey: ElGamalPubkey,
}

struct TransferData {
transfer_pubkeys: TransferPubkeys,
}

If there is no associated auditor associated with the mint, then the auditor pubkey is simply 32 zero bytes.

Low and High-bit Encryptionโ€‹

Transfer instruction data must include the transfer amount that is encrypted under the three ElGamal public keys associated with the instruction. To cope with ElGamal decryption as discussed in the previous section, the transfer amount is restricted to 48-bit numbers and is encrypted as two separate numbers: amount_lo that represents the low 16-bits and amount_hi that represents the high 32-bits.

Each amount_lo and amount_hi is encrypted under the three ElGamal public keys associated with a transfer. Instead of including three independent ciphertexts as part of the transfer data, we use the randomness-reuse property of ElGamal encryption to minimize the size of ciphertexts.

/// Ciphertext structure of the transfer amount encrypted under three ElGamal
/// public keys
struct TransferAmountEncryption {
commitment: PedersenCommitment,
source_handle: DecryptHandle,
destination_handle: DecryptionHandle,
auditor_handle: DecryptHandle,
}

struct TransferData {
ciphertext_lo: TransferAmountEncryption,
ciphertext_hi: TransferAmountEncryption,
transfer_pubkeys: TransferPubkeys,
}

In addition to these ciphertexts, transfer data must include proofs that these ciphertexts are generated properly. There are two ways that a user can potentially cheat the program. First a user may provide ciphertexts that are malformed. For example, even if a user may encrypt the transfer amount under a wrong public key, there is no way for the program to check the validity of a ciphertext. Therefore, we require that transfer data require a ciphertext validity proof that certifies that the ciphertexts are properly generated.

Ciphertext validity proof only guarantees that a twisted ElGamal ciphertext is properly generated. However, it does not certify any property regarding the encrypted amount in a ciphertext. For example, a malicious user can encrypt negative values, but there is no way for the program to detect this by simply inspecting the ciphertext. Therefore, in addition to a ciphertext validity proof, a transfer instruction must include a range proof that certifies that the encrypted amounts amount_lo and amount_hi are positive 16 and 32-bit values respectively.

struct TransferProof {
validity_proof: ValidityProof,
range_proof: RangeProof,
}

struct TransferData {
ciphertext_lo: TransferAmountEncryption,
ciphertext_hi: TransferAmountEncryption,
transfer_pubkeys: TransferPubkeys,
proof: TransferProof,
}

Verifying Net-Balanceโ€‹

Finally, in addition to proving that the transfer amount is properly encrypted, a user must include a proof that the source account has enough balance to make the transfer. The canonical way to do this is for the user to generate a range proof that certifies that the ciphertext source_available_balance - (ciphertext_lo + 2^16 * ciphertext_hi), which holds the available balance of the source account subtracted by the transfer amount, encrypts a positive 64-bit value. Since Bulletproofs supports proof aggregation, this additional range proof can be aggregated into the original range proof on the transfer amount.

struct TransferProof {
validity_proof: ValidityProof,
range_proof: RangeProof, // certifies ciphertext amount and net-balance
}

struct TransferData {
ciphertext_lo: TransferAmountEncryption,
ciphertext_hi: TransferAmountEncryption,
transfer_pubkeys: TransferPubkeys,
proof: TransferProof,
}

One technical problem with the above is that although the sender of a transfer knows an ElGamal decryption key for the ciphertext source_available_balance, it does not necessarily know a Pedersen opening for the ciphertext, which is needed to generate the range proofs on the ciphertext source_available_balance - (ciphertext_lo + 2^16 * ciphertext_hi). Therefore, in a transfer instruction, we require that the sender decrypt the ciphertext source_available_balance - (ciphertext_lo + 2^16 * ciphertext_hi) on the client side and include a new Pedersen commitment on the new source balance new_source_commitment along with an equality proof that certifies that the ciphertext source_available_balance - (ciphertext_lo + 2^16 * ciphertext_hi) and new_source_commitment encrypt the same message.

struct TransferProof {
new_source_commitment: PedersenCommitment,
equality_proof: CtxtCommEqualityProof,
validity_proof: ValidityProof,
range_proof: RangeProof,
}

struct TransferData {
ciphertext_lo: TransferAmountEncryption,
ciphertext_hi: TransferAmountEncryption,
transfer_pubkeys: TransferPubkeys,
proof: TransferProof,
}

Transfer With Fee Instruction Dataโ€‹

The confidential extension can be enabled for mints that are extended for fees. If a mint is extended for fees, then any confidential transfer of the corresponding tokens must use the confidential extension TransferWithFee instruction. In addition to the data that are required for the Transfer instruction, the TransferWithFee instruction requires additional cryptographic components associated with fees.

Background on Transfer Feesโ€‹

If a mint is extended for fees, then transfers of tokens that pertains to the mint requires a transfer fee that is calculated as a percentage of the transfer amount. Specifically, a transaction fee is determined by two paramters:

  • bp: The base point representing the fee rate. It is a positive integer that represents a percentage rate that is two points to the right of the decimal place.

    For example, bp = 1 represents the fee rate of 0.01%, bp = 100 represents the fee rate of 1%, and bp = 10000 represents the fee rate of 100%.

  • max_fee: the max fee rate. A transfer fee is calculated using the fee rate that is determined by bp, but it is capped by max_fee.

    For example, consider a transfer amount of 200 tokens.

    • For fee parameter bp = 100 and max_fee = 3, the fee is simply 1% of the transfer amount, which is 2.
    • For fee parameter bp = 200 and max_fee = 3, the fee is 3 since 2% of 200 is 4, which is greater than the max fee of 3.

The transfer fee is always rounded up to the nearest positive integer. For example, if a transfer amount is 100 and the fee parameter is bp = 110 and max_fee = 3, then the fee is 2, which is rounded up from 1.1% of the transfer amount.

The fee parameters can be specified in mints that are extended for fees. In addition to the fee parameters, mints that are extended for fees contain the withdraw_withheld_authority field, which specifies the public key of an authority that can collect fees that are withheld from transfer amounts.

A Token account that is extended for fees has an associated field withheld_amount. Any transfer fee that is deducted from a transfer amount is aggregated into the withheld_amount field of the destination account of the transfer. The withheld_amount can be collected by the withdraw-withheld authority into a specific account using the TransferFeeInstructions::WithdrawWithheldTokensFromAccounts or into the mint account using the TransferFeeInstructions::HarvestWithheldTokensToMint. The withheld fees that accumulate in a mint can be collected into an account using the TransferFeeInstructions::WithdrawWithheldTokensFromMint.

Fee Encryptionโ€‹

The actual amount of a transfer fee cannot be included in the confidential extension TransferWithFee instruction in the clear since the transfer amount can be inferred from the fee. Therefore, in the confidential extension, the transfer fee is encrypted under the destination and withheld authority ElGamal public key.

struct FeeEncryption {
commitment: PedersenCommitment,
destination_handle: DecryptHandle,
withdraw_withheld_authority_handle: DecryptHandle,
}

struct TransferWithFeeData {
... // `TransferData` components
fee_ciphertext: FeeEncryption,
}

Upon receiving a TransferWithFee instruction, the Token program deducts the encrypted fee under the destination ElGamal public key from the encrypted transfer amount under the same public key. Then it aggregates the ciphertext that encrypts the fee under the withdraw withheld authority's ElGamal public key into the withheld_fee component of the destination account.

Verifying the Fee Ciphertextโ€‹

The remaining pieces of the TransferWithFee instruction data are fields that are required to verify the validity of the encrypted fee. Since the fee is encrypted, the Token program cannot check that the fee was computed correctly by simply inspecting the ciphertext. A TransferWithFee must include three additional proofs to certify that the fee ciphertext is valid.

  • ciphertext validity proof: This proof component certifies that the actual fee ciphertext is properly generated under the correct destination and withdraw withheld authority ElGamal public key.
  • fee sigma proof: In combination with range proof component, the fee sigma proof certifies that the fee that is encrypted in fee_ciphertext is properly calculated according to the fee parameter.
  • range proof: In combination with the fee sigma proof components, the range proof component certifies that the encrypted fee in fee_ciphertext is properly calculated according to the fee parameter.

We refer to the proof specifications below for the additional details.

Sigma Protocolsโ€‹

Validity Proofโ€‹

A validity proof certifies that a twisted ElGamal ciphertext is a well-formed ciphertext. The precise description of the system is specified in the following notes.

[Notes]

Validity proofs is required for the Withdraw, Transfer, and TransferWithFee instructions. These instructions require the client to include twisted ElGamal ciphertexts as part of the instruction data. Validity proofs that are attached with these instructions certify that these ElGamal ciphertexts are well-formed.

Zero-balance Proofโ€‹

A zero-balance proof certifies that a twisted ElGamal ciphertext encrypts the number zero. The precise description of the system is specified in the following notes.

[Notes].

Zero-balance proofs are required for the EmptyAccount instruction, which prepares a token account for closing. An account may only be closed if the balance in an account is zero. Since the balance is encrypted in the confidential extension, the Token program cannot directly check that the encrypted balance in an account is zero by inspecting the account state. Instead, the program verifies the zero-balance proof that is attached in the EmptyAccount instruction to check that the balance is indeed zero.

Equality Proofโ€‹

The confidential extension makes use of two kinds of equality proof. The first variant ciphertext-commitment equality proof certifies that a twisted ElGamal ciphertext and a Pedersen commitment encode the same message. The second variant ciphertext-ciphertext equality proof certifies that two twisted ElGamal ciphertexts encrypt the same message. The precise description of the system is specified in the following notes.

[Notes].

Ciphertext-commitment equality proofs are required for the Transfer and TransferWithFee instructions. Ciphertext-ciphertext equaltiy proofs are required for the WithdrawWithheldTokensFromMint and WithdrawWithheldTokensFromAccounts instructions.

Fee Sigma Proofโ€‹

The fee sigma proof certifies that a committed transfer fee is computed correctly. The precise description of the system is specified in the following notes.

[Notes]

The fee sigma proof is required for the TransferWithFee instruction.

Range Proofsโ€‹

The confidential extension uses Bulletproofs for range proofs. We refer to the academic paper and the dalek implementation for the details.