[Klaytn] 12th KIR - Auditable Privacy Preserving FT/NFT Transfer on Klaytn Blockchain

[redragonvn]

Preliminary Security review

Klaytn 12th KIR - Auditable Privacy Preserving FT/NFT Transfer on Klaytn Blockchain

August, 2022
Author: Verichains - https://verichains.io

Summary

The Klaytn 12th KIR on "Auditable Privacy Preserving FT/NFT Transfer on Klaytn Blockchain Final Report" [1] essentially contains 3 parts:

1. A proposal for fast, succinct and zero-knowledge proof of batch membership.
2. Standard contract interfaces for auditable, privacy-preserving fungible and non-fungible tokens.
3. Precompiled contracts for two zk-SNARK friendly hash functions (MiMC7 and Poseidon).

In the technical report for part 1 [2], the authors derive from the scheme proposed in [3] a proof system with slightly higher proof size (i) and verification time (ii) but faster proof generation (iii). Specifically, the whole computation for RSA accumulator batch membership/insertion proof verification is divided into sub-computations. Each sub-computation is applied a different zk-SNARK and recombined by a technique called LegoSNARK [4] to avoid the inefficiency of general-purpose SNARK schemes. More importantly, the sub-computation involving modular exponentiation is moved out of the SNARK circuit. As a result, some succinctness is lost, which explains (i); the verifier needs to execute parts of the computation by herself, which explains (ii); and the prover is able to natively perform modular exponentiation, which explains (iii).

Since the authors want to make the proposed batch membership proof zero knowledge, some work has to be done regarding the moved-out sub-computation. Specifically, both the base and exponent of each exponential operation need to be hidden since they leak information about the members to be proved. To hide the base, virtual members are added to the parent set and some of them are randomly included in the subset of members to be proved, causing the membership witness computationally indistinguishable from a random number. For the privacy of the exponent, a sigma protocol [5] similar to Schnorr’s [6] is applied.

In part 2, two standard contract interfaces for auditable, privacy-preserving fungible and non-fungible tokens are proposed. The most important methods are registerAuditor and zkTransfer which allow an auditor public key to be registered and anonymous transactions to occur respectively.

In part 3, two zk-SNARK friendly hash functions, MiMC7 [7] and Poseidon [8], are proposed to be natively supported by Klaytn, accessible via precompiled contracts. This may improve user experience (lower gas consumption) and the whole network performance (more efficient execution of zk-SNARK-utilized contracts that make heavy use of the functions). However, the benefit is not as much as it may seem since these functions usually lie inside SNARK circuits and smart contracts usually play the verifier role which does not have to execute them. Moreover, outside a SNARK system, they are significantly slower than usual Cryptographic hash functions.

Potential Issues

Part 1

• Applicability of Schnorr's protocol: By definition, Schnorr’s protocol for proof of knowledge of discrete logarithm applies to groups of known order. At step 3 of the protocol, the prover sends $s=(r+cx) \text{ mod } q$ in which $r$ is a random value committed by the prover at step 1, $c$ is a challenge randomly chosen by the verifier at step 2, $x$ is the exponent or discrete logarithm value the prover wants to prove in zero knowledge and $q$ is the group order. It can be seen that $s$ is uniformly distributed over $\mathbb{Z}_q$ independently of $x$ as $r$ and $c$ vary. This property no longer holds in the context of the proposed scheme, in which $q$ is not known and $s$ is designed to be $r+cx \in \mathbb{Z}$. As a result, knowledge of $x$ is leaked, for example, say, when $r$ < $c$, $\lfloor s/c \rfloor$ reveals $x$.

• Usefulness of zero-knowledgeness: The proposed scheme is claimed to be the first proof of batch membership which tackles both scalability and privacy. It's true that if attackers only look at the proofs, privacy is preserved. However, is privacy protected against the proof generator, say, an aggregator who collects multiple transactions and aggregates them into a single batch proof? As long as non-anonymous transactions are broadcast in the public, zero-knowledgeness of the aggregated proof does not help much.

• Other issues related to RSA-accumulator-based membership proof including trusted setup requirement (the group order is kind of toxic waste), post-quantum security, ...

Part 2

• The scope is too narrow: The proposed interfaces are too specific on how the two types of tokens should be implemented. Only a hybrid model similar to ZKlay [9] is supported. Other models, say, a purely UTXO-based one (e.g., Zcash equipped with auditability), would not fit.
• Part 2 is inconsistent with part 1: Membership proof happens to be based on Merkle tree instead of an RSA accumulator.
• Auditor public key is fixed: It is only assigned once and can not be rotated.
• Some methods are redundant: Getting the auditor's registered public key, a user's encrypted balance, the Merkle tree root or authentication path, ... does not need on-chain interaction.

Part 3

• The MiMC7 pseudocode is incomplete (some symbols are undefined) and has a typo (line 3). Moreover, the round constants rc should be precomputed and moved out of the function mimc7round since people may be confused that keccak256 is also compiled to circuit.

References

[1] KIR Forum. 2022. The 12th KIR: Auditable Privacy Preserving FT/NFT Transfer on Klaytn Blockchain Final Report. [online] Available at: https://kir.klaytn.foundation/t/the-12th-kir-auditable-privacy-preserving-ft-nft-transfer-on-klaytn-blockchain-final-report/558 [Accessed 1 August 2022].

[2] Campanelli, M., Fiore, D., Han, S., Kim, J., Kolonelos, D. and Oh, H., 2021. Succinct Zero-Knowledge Batch Proofs for Set Accumulators. Cryptology ePrint Archive.

[3] Ozdemir, A., Wahby, R., Whitehat, B. and Boneh, D., 2020. Scaling verifiable computation using efficient set accumulators. In 29th USENIX Security Symposium (USENIX Security 20) (pp. 2075-2092).

[4] Campanelli, M., Fiore, D. and Querol, A., 2019, November. LegoSNARK: modular design and composition of succinct zero-knowledge proofs. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security (pp. 2075-2092).

[5] Damgård, I., 2002. On Σ-protocols. Lecture Notes, University of Aarhus, Department for Computer Science, p.84.

[6] Schnorr, C.P., 1989, August. Efficient identification and signatures for smart cards. In Conference on the Theory and Application of Cryptology (pp. 239-252). Springer, New York, NY.

[7] Albrecht, M., Grassi, L., Rechberger, C., Roy, A. and Tiessen, T., 2016, December. MiMC: Efficient encryption and cryptographic hashing with minimal multiplicative complexity. In International Conference on the Theory and Application of Cryptology and Information Security (pp. 191-219). Springer, Berlin, Heidelberg.

[8] Grassi, L., Khovratovich, D., Rechberger, C., Roy, A. and Schofnegger, M., 2021. Poseidon: A New Hash Function for {Zero-Knowledge} Proof Systems. In 30th USENIX Security Symposium (USENIX Security 21) (pp. 519-535).

[9] KIR Forum. 2022. The 6th KIR : ZKrypto_ZKlay. [online] Available at: https://kir.klaytn.foundation/t/the-6th-kir-zkrypto-zklay/141 [Accessed 1 August 2022].