Klaytn Improvement Reserve
Auditable Privacy Preserving FT/NFT Transfer on Klaytn Blockchain
Date: 2022.07.18
Summary
Following the KIR scheme at Klayton, we successfully developed Zklay, a zero-knowledge proof-based Klay (and FT) transfer scheme that supports privacy and auditability in Klaytn. Subsequently, we expanded our research to propose KIPs supporting privacy, auditability, and zero-knowledge proof. We have improved Zklay’s proof generation performance and reduced gas consumption cost. In addition, we have extended the proposed scheme to support security and privacy concerns relating to the transfers of NFTs (non-fungible tokens).
In detail, we will propose a new KIP (auditable privacy preserving fungible token) to execute privacy and auditability similarly to KIP-7. Moreover, to reduce the gas cost in the current version of the proposed scheme, we propose new native instructions called “MiMC” and “Poseidon” hashes in Klaytn as KIP. Since the current SHA256 is too slow for the zk-SNARKs proof generation, we propose MiMC accelerating the hash computation in zk-SNARKs proof generation. However, since the native instruction does not support MiMC, it encounters higher gas costs in comparison to the existing native format of SHA256.
To improve the proof generation performance, which determines the transaction generation performance from the user side, and the proof verification performance that affects the gas consumption in a smart contract, we devise a time-efficient and coherent membership proof which resolves previous bottleneck performance in zk-SNARK based on RSA accumulator. The proposed scheme is available in eprint of which title is “Succinct Zero-Knowledge Batch Proofs for Set Accumulators”, and will appear in ACM Conference on Computer and Communications Security (ACM CCS 2022) which is the top security conference.
Finally, we will extend Zklay to support NFT with auditability and privacy and define a new KIP (auditable privacy preserving non-fungible token) similar to KIP-17 (non-fungible token) and KIP-37 (multi-token). For NFT Zklay, we will define the transaction format by presenting the wallet interface with a wallet example and reveal a successful NFT Zklay demonstration.
Having invested an immense amount of time and effort in the research and development stage, we were able to review and complete this proposal earlier than scheduled. In this progress report, we include all achievements, including milestone 1 (Fast membership), milestone 2(KIP for FT, KIP for MiMC hash, design of Auditable privacy preserving transfer NFT), and milestone 3 (MiMC implementation for Klaytn). Furthermore, we exhibit our KIP designs for Poseidon hash and the implementation of Poseidon hash. Our final report will illustrate privacy preserving NFT transfer demonstration. In addition, we will upload the KIP proposals.
Proposed Project Milestones and Schedule
Project Details
1. Fast membership proof algorithm
In ZKP powered applications, the membership proof or semaphore is crucial since it is frequently employed and it increases the proof generation time. Therefore it is a great chanlledge to accelerate the proof generation performance of the membership proof in ZKP. Althought ZKP friendly hash functions such as MiMC and Poseidon alleviate the burden of the proof generation, it is a significant bottleneck to deploy ZKP powered applications in the real world. In this project, we will develop a new efficient membership proof algorithm for ZKP. The proposed scheme improves the membership proof generation performance not only for a single member but also many members. The proposed scheme combines a zk-SNARK and a hidden order group accumulator (or RSA accumulator).
-
Algorithm overview
Setup: The setup algorithm takes security parameter, a commitment key ck, and public parameter pp as inputs and outputs common reference string crs which consists of ck, pp, crsarithm , crsbound . Note that crsarithm denotes the crs required to check whether membership proof k is same with r+ush mod l and crsbound denotes the crs for user element ui is big enough.
Prove(crs, acc, cu , Wu, ou) → =( Wu , Q, R, cs, r , p1, p2, p3) : The prove algorithm takes common reference string crs, accumulator acc, commitment cu , and an opening ou as inputs. Then, prover generates proof . Note that Wu , Q and R are membership proof, cs, r denotes a commitment for s and r. p1, p2, p3 are proof for membership constraint. p1 is for membership proof using Proof of knowledge exponent, p2 ensures that a membership proof k is not just some integer but is exactly r+ush mod l and p3 ensures user elements are big enough.
Verify(crs, acc, cu , p) → 0/1 : The verification algorithm takes common reference string crs, accumulator acc, commitment cu and proof p as inputs. Verification accepts if and only if membership proof is correct(the user element u is in set S), k is exactly equals r+ush mod l and the user element is in the right domain.
The algorithm overview is depicted in Figure 1.
[Figure 1. Efficient membership proof algorithm]
It shows an interaction between a prover and a verifier. As shown in Figure 1, what to focus first is a novel technique for preserving privacy of set elements. By randomly exponent of prime number ei over a membership proof W, zero-knowledge of membership proof can be achieved. It is proven under f-DDH-II assumption and the detailed proof is depicted in the technical report. As well as zero-knowledgeness, our approach is also succinct in terms of performance including proving time, verification time, and proof size.
Proving set membership preserving privacy, using zkSNARKs in general, is not efficient since encoding Merkle tree in zkSNARKs circuit is pretty expensive. Encoding RSA accumulator in zkSNARKs is expensive as well. We avoid encoding RSA accumulator directly, and take a commit-and-prove technique instead. With commit-and-prove technique, a user element is committed and the membership proof can be generated outside of the zkSNARKs circuit. Later, with the commitment, it is guaranteed that the membership proof is not for an arbitrary member but for exactly committed elements. cu , and cs, r in Figure 1 are for it. Merkle tree, for example, is costly and does not support membership proof for batch elements. Our approach is about 6x faster when proving for 1 element. This difference is getting bigger as the batch size is bigger (This is displayed in section 6 in the technical report.).
For proving set membership of batch elements, we adopt Proof of Knowledge Exponent(PoKE) in [BBF19]. Proof size is fixed with modulo l (256 bits in our implementation), however the batch size is big. In Figure 1, a verifier samples l, a prover computes r+ush mod l and sends it to the verifier as membership proof. However, the prover computes one more exponentiation for computing Q and the proof includes one more RSA group element in consequence. Yet, still proving time and the proof size is constant in this case. To summarize, verification cost is constant with slightly more computing on prover side and bigger proof size. -
Implementation and experiment of the fast membership proof algorithm Zklay:
The proposed scheme is implemented in Python and Solidity. Setup phase and proving phase is on python, and with solidity, verification can be executed on a smart contract. We compare our work with merkle tree membership since it is used to prove membership in many blockchain systems. The Hash function in merkle tree is MiMC and we use a 2048 bits RSA group. In regards to the number of randomness prime, lambda, we push the conventional boundaries of 128 to 256. We take this risk in order to assume and prepare for unseen tribulations and setbacks.
Observing gas consumption, Merkle tree membership in Zklay requires about 3M gas while our approach takes about 5M gas when it comes to a single membership proof. However, if the batch size gets bigger, this is reversed. Since our approach only supports efficient batch proof for set membership, gas consumption for batch membership verification is still 5M approximately while the Merkle tree membership grows in proportional to the batch size.
- Technical report : Succinct Zero-Knowledge Batch Proofs for Set Accumulators Succinct Zero-Knowledge Batch Proofs for Set Accumulators
- It will be appearing in ACM Conference on Computer and Communications Security (ACM CCS 2022) which is the top security conference.
2. Definition of KIP for an auditable privacy preserving fungible token
In our initial experiment with Zklay, we assumed the requirement to revise the blockchain core to support the privacy in each transaction. Fortunately, the completed Zklay does not request any modification of the blockchain core. Most difficult works are concentrated on the zero-knowledge proof generation. In accordance with the finding of the first round KIR, we will define a KIP to support privacy and auditability in FT. The proposal will follow the format of SNIP-20 (SNIPs/SNIP-20.md at master · SecretFoundation/SNIPs · GitHub ). But the proposed one will be compatible with the proposed Zklay.
In the KIP, functions and queries in our proposal interface will be defined:
interface IKIP {
/// @dev Emitted when executing 'zkTransfer'.
/// Since the ciphertext's length is different according to encryption scheme, sets ciphertext to 'uint256[]'
event ZkTransfer(
uint256 root,
uint256 nullifier,
uint256 commitment,
uint256[] ciphertext,
);
/// @notice Stores an auditor's public key.
/// @dev Return if the public key is already registered.
/// @param apk An auditor public key.
/// @return 'bool' representing whether the function succeeded.
function registerAuditor(uint256 apk) external returns (bool)
/// @notice Registers a new encrypted account for address.
/// @dev If the address already exists in the ENA map, the transaction is reverted. Otherwise, it registers a new ENA and initializes it with zero amount
/// @param address A user's address.
/// @return 'bool' representing whether the function succeeded.
function registerUser(uint256 address) external returns (bool)
/// @notice Checks the validity of the transaction, and executes zkTransfer procedure.
/// @dev 'input' consists of Merkle Tree root(rt), a nullifier(nf), a sender's address(addr), a new commitment(cm), a new encrypted balance, a new ciphertext, and publicly transferred values(v_in, v_out)
/// Verifies the following; root exists in the root list, nullifier does not exist in the nullifier list, address exists, commitment does not exist in the commitment list, and a proof is valid.
/// If it is a valid transaction, proceeds as follows; update Merkle Tree with a new commitment(cm), and appends the updated root to the root list. Also, a nullifier is appended to the nullifier list and the new encrypted balance is stored in sender's ENA. Acquires v_in from owner, and delivers v_out to 'recipient'. Otherwise, if the transaction is invalid, reverts.
/// Emits an {Transfer} event.
/// @param proof A zk-SNARK proof for anonymous transfer transaction.
/// @param input The input values required to verify the zk-SNARK proof.
/// @param recipient The recipient's address for sending token publicly
/// @return 'bool' representing whether the function succeeded.
function zkTransfer(uint256[] memory proof, uint256[] memory input, address recipient) external returns (bool)
/// @notice Returns the user's encrypted account information
/// @dev If the address does not exist, it returns -1.
/// @param address A user's address
/// @return 'uint256[]' representing the user's encrypted balance.
function getEnaBalance(uint256 address) external view return (uint256[] memory)
/// @notice Returns the auditor public key
/// @return 'uint256' The registered auditor public key
function getAuditorKey() external view returns (uint256)
/// @notice Returns the authentication co-path
/// @param index The index to commitment inserted in Merkle Tree
/// @return 'uint256[]' The authentication co-path from a commitment appearing in Merkle Tree.
function getMerkleTreePath(uint256 index) external view returns (uint256[] memory)
/// @notice Returns the current Merkle Tree root.
/// @return 'uint256' The current Merkle Tree root.
function getMerkleTreeRoot() external view returns (uint256)
}
3. Auditable privacy preserving NFT transfer
There is a similar privacy preserving NFT proposal for ERC-721 NFT called SNIP-721 ( SNIPs/SNIP-721.md at master · SecretFoundation/SNIPs · GitHub ), which does not support auditing. In this project, we will support NFT transfer and propose the KIP- Auditable privacy preserving non-fungible token (NFT).
The anonymous transfer function (zkTransfer) for NFT generates a commitment with NFT id preimage. The NFT transaction will include a ciphertext including NFT id, recipience, and use of a random key. Using the auditor private key key as well as the recipience private key, it is possible to decrypt the ciphertext to trace the NFT transfer.
interface IKIP {
/// @dev Emitted when executing 'nft_zkTransfer'
/// 'ciphertext' is arbitrary, since the length of ciphertexts is different according to encryption scheme, sets ciphertext to uint256[]
event Transfer(
uint256 root,
uint256 nullifier,
uint256 commitment,
uint256[] ciphertext
);
/// @notice Stores an auditor's public key.
/// @dev Returns if the public key is already registered.
/// @param apk An auditor public key.
/// @return 'bool' representing whether the function succeeded.
function registerAuditor(uint256 apk) external returns (bool)
/// @notice Checks the validity of the transaction, and executes zkTransfer procedure.
/// @dev 'input' consists of Merkle Tree root(rt), a nullifier(nf), a sender's address(addr), a new commitment(cm), a new ciphertext(pct), and publicly transferred values(v_in, v_out)
/// One of publicly transferred values is 0, and the other is tokenId
/// Verifies the following; root exists in the root list, nullifier does not exist in the nullifier list, commitment does not exist in the commitment list, and a proof is valid.
/// If it is a valid transaction, proceeds as follows; update Merkle Tree with a new commitment(cm), and appends the updated root to the root list. Also, a nullifier is appended to the nullifier list and the nft is transferred to sender. Otherwise, if the transaction is invalid, reverts.
/// @param proof A zk-SNARK proof for anonymous transfer transaction.
/// @param input The input values required to verify the zk-SNARK proof.
/// @param recipient The recipient's address for sending token publicly
/// @return 'bool' representing whether the function succeeded.
function zkTransfer(uint256[] memory proof, uint256[] memory input, address recipient) external returns (bool)
/// @notice Returns the user's amount of nft
/// @dev If the address does not exist, it returns 0.
/// @param address A user's address
/// @return 'uint256' representing the user's amount of nft.
function getBalance(uint256 address) external view returns (uint256)
/// @notice Returns the auditor public key
/// @return 'uint256' The registered auditor public key
function getAuditorKey() external view returns (uint256)
/// @notice Returns the authentication co-path
/// @param index The index to commitment inserted in Merkle Tree
/// @return 'uint256[]’ The authentication co-path from a commitment appearing in Merkle Tree.
function getMerkleTreePath(uint256 index) external view returns (uint256[] memory)
/// @notice Returns the current Merkle Tree root.
/// @return 'uint256' The current Merkle Tree root.
function getMerkleTreeRoot() external view returns (uint256)
}
4. zk-SNARKs friendly hash function
Another lesson from the first round of KIR is related to a hash function. To generate a rapid zero-knowledge proof, it is almost mandatory to adopt a zk-SNARKs friendly hash function such as MiMC or Poseidon. However, since the hashes are not a native instruction in Klaytn, these require high gas cost and decrease the Klaytn performance. If the zk-SNARKs friendly hashes are natively supported in the Klaytn then it would be beneficial to support zk-SNAKRs efficiently. Hence, we propose a new KIP to support the zk-SNARKs friendly hash function of MiMC and Poseidon. Note that the proposed hashes does not mean that we devise a new hash algorithm. We utilize the existing hash design and implementation code, and port it in the Klaytn. In addition, we will propose an example of how to use the MiMC and Poseidon precompiled contracts.
MiMC7 and Poseidon hashes:
- Introduction
MiMC and Poseidon are designed to minimize prover and verifier complexities when zero-knowledge proofs are generated and validated.
The following pseudofunction reflects how mimc7 should be calculated:
Details MiMC protocol: https://eprint.iacr.org/2016/492.pdf
Details MiMC7 protocol: https://iden3-docs.readthedocs.io/en/latest/_downloads/a04267077fb3fdbf2b608e014706e004/Ed-DSA.pdf
Details Poseidon protocol: go-iden3-crypto/poseidon at master · iden3/go-iden3-crypto · GitHub
KIP precompiled contract proposal:
Assuming a constant
-
How to use precompiled contract MiMC7 in Solidity
-
How to use precompiled contract Poseidon in Solidity
Test Cases
Test vector 0
- input:
0x0000000000000000000000000000000000000000000000000000000000000000 - output(mimc7):
0xf140047dfa92d9b77787cfc243ba6da07d8f8aa9301be9bf49042d7f203264a - output(poseidon):
0x2a09a9fd93c590c26b91effbb2499f07e8f7aa12e2b4940a3aed2411cb65e11c
Test vector 1 - input:
0x0000000000000000000000000000000000000000000000000000000000000001 - output(mimc7):
0x2f81229fea90cc0b53ce8ea692be6993d9e6f8ea2fb56751b5d8cf4893f686fd - output(poseidon):
0x29176100eaa962bdc1fe6c654d6a3c130e96a4d1168b33848b897dc502820133
The following github contains the Klaytn implementation to support the MiMC7 and the Poseidon hash functions written in GO language.
Key Deliverables
Deliverables are included as below:
- Technical papers: research paper for fast membership proof (Succinct Zero-Knowledge Batch Proofs for Set Accumulators Succinct Zero-Knowledge Batch Proofs for Set Accumulators). Zklay for NFT (It will be included in the final report.)
- Zklay Dapps for FT and NFT with a fast membership proof (It will be included in the final report.)
- Zklay smart contracts in Klaytn blockchain (It will be included in the final report.)
- KIP proposals (It will be uploaded in KIP proposals.)
- MiMC hash code for Klaytn core (GitHub - snp-labs/klaytn: Official Go implementation of the Klaytn protocol)
Deliverables are included as below:
- Technical papers: research paper for fast membership proof (Succinct Zero-Knowledge Batch Proofs for Set Accumulators Succinct Zero-Knowledge Batch Proofs for Set Accumulators), and will appear in ACM CCS 2022
- KIP proposals (It will be uploaded in KIP proposals.)
- MiMC and Poseidon hash codes for Klaytn core (GitHub - snp-labs/klaytn: Official Go implementation of the Klaytn protocol)
- Auditable privacy preserving FT/NFT transfer demonstration ( NFT transfer demo : zklay demo in Korean - YouTube . cf) Previous FT transfer demo in English is available at zklay demo in English - YouTube and in Korean at Privacy Preserving NFT transfer - YouTube )