Skip to content

Latest commit

 

History

History
316 lines (190 loc) · 19.5 KB

tip-137.md

File metadata and controls

316 lines (190 loc) · 19.5 KB
Raw
tip: 137 
title: Zero-knowledge Proof Verification functions 
author: federico<federico.zhen@tron.network>
discussions-to: https://github.com/tronprotocol/tips/issues/137
status: Final
type: Standards Track
category: VM
created: 2020-03-09

Simple Summary

The TIP provides the zero-knowledge proof verification functions in the shielded TRC-20 contract (TIP-135), which can be used in shielded token transactions.

Abstract

The TIP introduces three new functions: verifyMintProof, verifyTransferProof, and verifyBurnProof, which are implemented in the form of the precompiled contract, and can accelerate the zero-knowledge verification for the mint, transfer and burn operations in the shielded TRC-20 contract.

Motivation

To implement the shielded transactions for TRC-20 token, We have developed the shielded TRC-20 contract (TIP-135). The contract has three core modules: mint, transfer and burn. mint is used to transform the public TRC-20 tokens into shielded tokens. transfer is used for shielded token transactions. burn is used to transform the shielded tokens back to public TRC-20 tokens. The shielded contract is implemented based on zero-knowledge proof, so it needs the complex zero-knowledge proof verification in mint, transfer and burn methods. To accelerate the speed, we will make use of the new functions in the contract to implement the verification process.

Specification

The following defines the implementation of the methods for the shielded TRC-20 contract.

Preliminaries

NoteCommitment

The TRC-20 token is transformed into shielded token in the form of commitment by cryptographic method, which is defined as:

note-commitment = NoteCommitmentr(v)

The v value is hidden by note_commitment with the blinding factor r.

SpendDescription

The SpendDescription includes zk-SNARK proof related data, which is used as the input of the shielded token transaction.

message SpendDescription { 
  bytes value_commitment = 1; // value commitment
  bytes anchor = 2; // merkle root
  bytes nullifier = 3; // used for check double spend
  bytes rk = 4; // used for check spend spend authority signature
  bytes zkproof = 5; // zk-SNARK proof
  bytes spend_authority_signature = 6; //spend authority signature 
}

ReceiveDescription

The ReceiveDescrion also includes zk-SNARK proof related data, which is used as the output of the shielded token transaction.

message ReceiveDescription { 
  bytes value_commitment = 1; // value commitment used for binding signature
  byte  note_commitment = 2;  // note commitment used for hiding the value
  bytes epk = 3;  // ephemeral public key used for encryption
  bytes c_enc = 4;  // encryption for note plaintext
  bytes c_out = 5; // encryption for audit
  bytes zkproof = 6; // zk-SNARK proof 
}

For more details about note commitment, SpendDescription and ReceiveDescripton, please refer the TRONZ shielded transaction protocol.

Function

(1) verifyMintProof

verifyMintProof function is used to verify the validity of zero-knowledge proof when transforming the public TRC-20 token into shielded tokens.

bytes32[9] output = abi.encode(note_commitment, value_commitment, epk, zkproof);
(bytes32[] memory ret) = verifyMintProof(output, bindingSignature, value, signHash, frontier, leafCount);
  • bindingSignature - the binding signature
  • value - the amount of TRC-20 tokens to be shielded
  • signHash - the message hash for the binding signature
  • value - the value balance
  • frontier - used to compute the Merkle tree root
  • leafCount - the leaf number in the Merkle tree

The other parameters are specified in the above preliminaries.

[32 bytes for note_commitment][32 bytes for value_commitment][32 bytes for epk][192 bytes for zkproof][64 bytes for bindingSig][8 bytes for value][32 bytes for signHash][1056 bytes for frontier][32 bytes for leafCount]

The total input length of verifyMintProof is 1480 bytes. For the output, The length of ret is 96 ~ 1120 bytes. Its first 32 bytes can be converted as a bool value to indicate whether the proof verification succeeds and the other bytes return the slot and node value to construct the Merkle tree. The time cost of verifyMintProof function takes about 10ms.

（2）verifyTransferProof

verifyTransferProof function is used to verify the validity of zero-knowledge proof for shielded tokens transactions.

bytes32[10][] input;
bytes32[2][] spend_authority_signature;
bytes32[9][] output;
(bytes32[] memory ret) = verifyTransferProof(input, spend_auth_sig, output, bindingSignature, signHash, value, frontier, leafCount);

input, spend_authority_signature , and output are variable length arrays. The length of a single input is 320 bytes, it includes:

[32 bytes for nullifier][32 bytes for anchor][32 bytes for value_commitment][32 bytes for rk][192 bytes for zkproof]

The length of a single spend_authority_signature is 64 bytes, it includes:

[64 bytes for spend_authority_signature]

The length of a single output is 288 bytes, it includes:

[32 bytes for note_commitment][32 bytes for value_commitment][32 bytes for epk][192 bytes for zkproof]

The other parameters are:

[64 bytes for bindingSignature][32 bytes for signHash][8 bytes for value][1056 bytes for frontier][32 bytes for leafCount]

The total input length of verifyTransferProof is also variable. According to the input and output number in a transfer transaction, there are four scenarios:

  • one input and one output
[320 bytes for input][64 bytes for spend_authority_signature][288 bytes for output]

The total input length of verifyTransferProof is 1864 bytes.

  • one input and two output
[320 bytes for input][64 bytes for spend_authority_signature][576 bytes for output]

The total input length of verifyTransferProof is 2152 bytes.

  • two input and one output
[640 bytes for input][128 bytes for spend_authority_signature][288 bytes for output]

The total input length of verifyTransferProof is 2248 bytes.

  • Two input and two output
[640 bytes for input][128 bytes for spend_authority_signature][576 bytes for output]

The total input length of verifyTransferProof is 2536 bytes.

For the output, the length of ret is 96 ~ 1152 bytes. Its first 32 bytes can be converted as a bool value to indicate whether the proof verification succeeds and the other bytes return the slot and node value to construct the Merkle tree. The time cost of verifyTransferProof function takes about 10~15 ms in parallel mode.

（3）verifyBurnProof

verifyBurnProof function is used to verify the validity of zero-knowledge proof when transforming the shielded tokens back to public TRC-20 tokens.

bytes32[10] input = abi.encode(nullifier, anchor, value_commitment, rk, zkproof)
(bool result) = verifyBurnProof(input, spend_auth_sig, value, bindingSignature, signHash);
  • value - the amount of shielded tokens to be made public

The other parameters are specified as above.

[32 bytes for nullifier][32 bytes for anchor][32 bytes for value_commitment][32 bytes for rk][192 bytes for zkproof][64 bytes for spend_authority_signature][8 bytes for value][64 bytes for bindingSignature][32 bytes for signHash]

The total input length of verifyBurnProof is 488 bytes. For the output, result is a bool value to indicate whether the proof verification succeeds. The time cost of verifyBurnProof function takes about 10ms.

Rationale

By introducing the zero-knowledge proof verification functions, it will be more convenient for shielded TRC-20 contract implementation, which can provide users stronger privacy for shielded token transactions.

Test Cases

(1) verifyMintProof

Input:

  • note_commitment : 0x3de8252d728c47e8aa99c9053f46ba4fa9f8400c7e20cbebd8b468e660139d4d

  • value_commitment ：0x66e85667260007c4483f42383985c26b2bef564950092bc14e551edc7c699d5c

  • epk : 0xcebea6669929700f6263da3645206b8d8bd10849b36159bc8c909c355dcca641

  • zkproof : 0x954850036b3a5799bd873ac64b37202823dff69442e68163f14d65fc8384ccc9c467fcb3a08c1ba39beaf28c6e65e6dca7b1c77d59998b81bcac0ddd5ed192d7268868221ae788be004c8188eb13cbf390fd5ba5f0cfcb91c6a8cae0f6f61f9919e53bda1af546fa2309a49c8c2ec03d218d2bf8961f139916611a447c30fb7b33b7ab459c8fc73889e1c9931b2096c7a157874b617256bace03a8d34eb7d0e180aba44864bf59f3551516d66a4d1a1b1c661ef130dd8866f9ae439fecffdebe

  • bindingSignature : 0xc42eb9b7f40f0a0d6392f2c379fc3bdae9921aca7c2a2c7ab9110fa749bb728485d9362aecd99495096ef4c40f28f33e277170f4fa5425b74ec266b2948ca709

  • value : 0x0000000000000000000000000000000000000000000000000000000000000064

  • signhash : 0x53f00a28433d697918fe93c611fc96efeb21f0794035df81ddd356a733cabb36

  • frontier :

    0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000

  • leafCount : 0x0000000000000000000000000000000000000000000000000000000000000000

Output:

  • ret :

    00000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000269ae71602fa48f21211790ab99ccbc39370c82d299123c60ff2e565b8522d04

(2) verifyTransferProof

For the two input and two output scenerios:

Input:

  • Input1 :

    0xd547b83623d24f0ca14df534c3b225999f91a47a95c1a7d3cf87cfae7a5d964ee987b29e51cf855189aa788b6575fd6ecbb3d0e2f44602fa08aa9cb47905063756356551cf1cc0d409d2ec654708d2ee918718b7a7a65254d4764aa5ddfa41be1260a3dcce2a7f98f16e80c2b716e54ee086998ced117e00f6c3f34887cb19b5a636740a929edcf69f01eea3d2e752b4e5a743da1357c8a6cbb8e133a04345a4319f7892708889fc6a8c7c0421032393a24049766749623e75abcaca3c781a7953c4a6565607e437506fb2d4e47a64f97342e36f10508631f0d9fdec72d5423216e30969b8f64896e4a0e11a12666f78aaf0f548e1e7be66ebc6a7929e4cd1a2e4eb426008828718f0bcbb750ef4f750809887c2af2507bcd984483f0ac1f68ea869c8b8bb81945363b54a2c4a33abffc1718287ffca6c3192b8e18190e6e406

  • input2 :

    0xd547b83623d24f0ca14df534c3b225999f91a47a95c1a7d3cf87cfae7a5d964ee987b29e51cf855189aa788b6575fd6ecbb3d0e2f44602fa08aa9cb47905063756356551cf1cc0d409d2ec654708d2ee918718b7a7a65254d4764aa5ddfa41be1260a3dcce2a7f98f16e80c2b716e54ee086998ced117e00f6c3f34887cb19b5a636740a929edcf69f01eea3d2e752b4e5a743da1357c8a6cbb8e133a04345a4319f7892708889fc6a8c7c0421032393a24049766749623e75abcaca3c781a7953c4a6565607e437506fb2d4e47a64f97342e36f10508631f0d9fdec72d5423216e30969b8f64896e4a0e11a12666f78aaf0f548e1e7be66ebc6a7929e4cd1a2e4eb426008828718f0bcbb750ef4f750809887c2af2507bcd984483f0ac1f68ea869c8b8bb81945363b54a2c4a33abffc1718287ffca6c3192b8e18190e6e406c4cf158457b270dfeb43dcee8f6aedaed806cf095e819e4e256bde3bd474eb9b195e8e1557e405889d06eb1e91adbeda485a9d803ec28130b71ee91ffb83695cb998c9c176a50b11e2664cf5329876b59f43044b755779fad604e0b251fae7caed1d3bd0b3487ee358f4e40faecbe29c2814c70c861ff835c85052374958dfbb81d8797844f877fa2cf713c0f277c7b3fe727eea4de824b5ccc5c76910c92d5342ad8cffa0003ba95ada9a32e29ff60095f77c7c76a35b2252a5f0cc23b4b602c523494d9ed4899ad54264263a9a1feb23b01dc80e260c3ec6cf4549e55cf05b189f7df299dec2149727d1191e5fa3977ff020fcafcb65b5bfd6ae00b9b71be893f057bedde288fc16cbd4390f62fad896817215176d6e14f49658b0eebc944b7334def3eeabe1422a9f64e1f462cbe7c5234c2acef55c34839a393e1dd5de3e

  • spend_authority_signature :

    0xd760e33d82aec3fa90193a1e67c7a80da3392567559ee9f69c914ac9851eb20a073db4615d1386194b8db3d7e9d1ba6c002c5222257b7f975296064056a20a08adf21c285424e698bb57ccca5980e139374dee60fcadb8917aaf3aa2d47ad570e1fb50cbbe5e639edd6bc55879934cc62704f39fe1d8e84a34f0e7b86123570b

  • output1 :

    0xcd950de9eae63584ac7481538556235f2c92e0cd72da3b2406d60354ee1de416f01daa796a6eb54a0f912fd07be1d38507dd8dd2f6729edf57414188ff83ac3174649fc5a5fdeb175fa2c39356cc4014a0547d6e4c7bbcab4d8fb0f64890422181fb63cc4b7b394cc53680d84af52492ff207472e981eac4a15b283120b1a61d606df5e0524c59103c2e65230d9becf4b3dc6b4c7f32aa6475cbd04e91d943829a2d040ec82b69c1aa925536da90c5bb843ca035e71894eb4fe93b519447fd110479e211f5834432fac46ca341478f7135d9db389c7fcdbab6a69f0696a403e838f994e173848b94aed53170323e2731a3c7227a614459b480f8ff3f7b50561b2de9e43e4c07a90ab2af4d62755ac1a62e2a858542d1e6e2fb9922da33c8471e

  • output2 :

    0x337bd40d6a43562b508e91ea490f237dbbe9ae0cd46929b593001ac980769127573bfac13dcd24262805df76264ae39df3b66696d145f3d36d07b77c05c65544557bc55a4f1d5dba9b2de7006de6612e27048951e8aabc3e7b2b50ca66089f4bb6d334dcde6d36cb36c0135888f3dd00ad0c6717b77cbde30f08ee5b2e125d57ffc5eb5056f58a71ee8026bae64f20ada3491b261ace0ddc2c85ab4cb7f2056147d2cfaa7092de5e7aa3cc9c5c4d0bd3041e9acc847a5aba1288d182857e3d9011fe31ea9ba1af2e371c9f188aa0b5959a8a7f8d05eb2f2b340f9db790d2e653001bb2ebaea831e10fd59b0c5d2062968e5ec2536a0265be17d25585f8f9fc65903cc688dbbd4623f22424510b7c88244712a4c0fe694f07dc4a8d4bc6998b9a

  • bindingSignature :

    0x7535e69dfa14e025300ab694f1fab9d06c069ffd8671057c19852416f9865e65e953e32bc0ed9b14d2f40a326b06d46609b280714ee755fd610a32a8e3ca1e0a

  • signHash :

    0x221785089e9a0eb15ff01478f0597e08144c6884f6ca63dd5484a3a44c5ef6a2

  • value : 0

  • frontier :

    0x0536530017784386dbdbc2a787d31c69070c9a4667494b29b5949ee7c21b823c, 0x2591182bce1c24ba7109b8fcd392f2c372e1b7210b8fa0396ed8fe9ede525b23, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000, 0x0000000000000000000000000000000000000000000000000000000000000000

  • leafCount : 0x0000000000000000000000000000000000000000000000000000000000000002

Output:

  • ret :

    0x0000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000023348b181267f4629e1f0fca87e7e2fc10f63d4287616668a400769d033513b4fd981f7463bc4952a3d2a17f9065f20c78551844f65352ff34aadd390fe81933e54e5c609a01058f91a400ddd74ed12d6f48400f787a6be85adc1ebee71768423

(3) verifyBurnProof

Input:

  • nullifier :

    0x5181a5f50528e03834f1063829b6d11c4007e686469877cc038aa6e343493f13

  • anchor :

    0x38057fa6fc670b4aeaaa90db77a183f873578b36a2d572c82031aab2a8a00c3d

  • value_commitment :

    0x80a7b6aaaa729fd8a25bf8d15e5df645c6966cc353e8b1c87420aba32696499c

  • rk :

    0x12530bf5afa25bdc2519ea146f5dae62a2b560e5acec8e9575402d5c61dc29a3

  • zkproof :

    0x81b6d5b8ba3229193cc78fa8a007de0da69ce9dadbe59e7e140a0434be8d8aa29c860a088a89bce54f139d3d6c9999f78dab78547bf91035c66af457d67f8d243755b7a2dcaf77bd03e9be25dd38074a70a19a6b31b09ec5374c45f465faa0a90945c5597d663ca8d9bf1a535b738da04e14c284007a7d8c38a6c7186f9f9049a10131c505203dbb473390f4b9e1398e86f1ac25fb1fc3c5b2a17403b3189df5776ad4065760b684a5c50d9566cedf4f41ddee99212c374f61386249910b902d

  • spend_authority_signature : 0x911adda5ba2eac4b07bdd134fb37fa9e5074fd52801509c397d229aacefb43dc, 0x7388fdced88ee1c76bf10fbb5e9d999e63f7308eb49f77f5fd15dade8cb41d01

    0xa1568800ac65256d93f1d134eff529d37abb6b4550b29f01bcbf2706ca526458e3f9c7f6ab1290ed187e1070ebfc1218aeb506f94146b2cd54ac5ca2963a5504

  • bindingSignature :

    0x21d5d06ee75278b02d4c9e474177c4f5751afbece55a8b10874c8cf91ae2f191ea86e568cf8737a57b73cae85c6e8b76dcffeab26e2877c7305003857da93d0d

  • value : 0x0000000000000000000000000000000000000000000000000000000000000064

  • signHash : 0x800f1efe377f2ef20cf1961ae9ad3dd804e05b58d41b90483c7d272514e23de3

Output:

  • result : true

Implementation