Klaytn Improvement Reserve
Auditable Privacy Preserving FT/NFT Transfer on Klaytn Blockchain
Date: 2022.03.03
Summary
We have successfully developed Zklay which is a zero knowledge proof based Klay (and FT) transfer scheme to support privacy and auditability in Klaytn at the first KIR. From the lesson, we will propose KIPs for privacy, auditability, and zero-knowledge supporting. We improve the proof generation performance and reduce the gas consumption for Zklay. In addition we extend the proposed scheme to support NFT (non-fungible token).
In detail, we will propose a new KIP (auditable privacy preserving fungible token) to allow privacy and auditability similarly to KIP-7. Moreover, to reduce the gas cost in the current version of the proposed scheme, we will propose a new native instruction called “MiMC” hash in Klaytn as KIP. The MiMC hash has been proposed to accelerate the hash computation in zk-SNARKs proof generation since the SHA256 is too slow in zk-SNARKs proof generation. However, since it is not supported as a native instruction, its gas cost is too high compared with the existing SHA256 that is supported as a native instruction.
To improve the proof generation performance which determines the transaction generation performance in a user side, and the proof verification performance that affects the gas consumption in a smart contract, we devise a new faster and more efficient membership proof which is the major performance bottleneck in zk-SNARK based on RSA accumulator.
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, the wallet interface with a wallet example, and so on. And we will implement and show the NFT Zklay demo.
Since it took more time than we expected to review this proposal, we are able to complete the project milestones earlier than scheduled. In this progress report, we includes 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). In addition, we design KIP for Poseidon hash and implementation of Poseidon hash. In the next final report, we will show the 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 smart contract. We compare our work with merkle tree membership since it is used to prove membership in many blockchain systems. Hash function in merkle tree is MiMC and we use a 2048 bits RSA group. Also, the number of randomness prime, lambda, we set it to 256. Although 128 is enough, we estimate the worst case.
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 only our approach 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 Cryptology ePrint Archive: Report 2021/1672 - Succinct Zero-Knowledge Batch Proofs for Set Accumulators
2. Definition of KIP for an auditable privacy preserving fungible token
When we start the Zklay in the previous round, we thought that it may be required 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. From the lesson in 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 to 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 using 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 KIR is related with a hash function. To generate a zero-knowledge proof rapidly, it is almost mandatory to adopt a zk-SNARKs friendly hash function like MiMC and 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 will propose a new KIP to support the zk-SNARKs friendly hash function of MiMC and Poseidon. Note that the proposed hashes do 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 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 Cryptology ePrint Archive: Report 2021/1672 - 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)