Technical analysis how to realize private transactions through zk-SNARK in NEAR

Never spend the transaction output, transaction, handling fee and other angles to analyze the way of realizing private transactions in NEAR and the method of improving the security and usability of the transaction pool.

Original title: “In-depth analysis of NEAR’s private transaction function”
Author: NEAR Protocol

Not long ago, NEAR announced a partnership with ZeroPool, which will add support for private transaction functions in the NEAR agreement. At present, on the NEAR platform, all transactions are the same as Bitcoin and Ethereum, and all are publicly available. In other words, for each transaction, the initiator, receiver, and transaction amount are disclosed to the public. Using this method can ensure that everyone has the right to audit the books and confirm the validity of the transaction, while also effectively preventing the occurrence of double spending.

In many cases, the ideal transaction method is: only the participants of the transaction can see the details of the transaction. To meet this requirement, while ensuring that the account book is still verifiable is a complex task that requires advanced cryptography techniques. In this article, the author will deeply analyze how to realize the private transaction function in the NEAR system from a technical point of view, that is, to ensure that the work of verifying the correctness of the transaction is not harmed, the various parties involved in the transaction and the transaction amount And other information is hidden. Below we cut into the theme:

1. Unspent output
2. transaction
3. Token deposit and withdrawal
4. Transaction Fees
5. future development
6. Conclusion

Unspent output

In the NEAR ecosystem, we generally use the account model as the bookkeeping method, and private transactions use the UTXO (unspent output) model. Each UTXO is a tuple, containing three elements: amount, receiver, and salt. The amount refers to the transaction amount. The receiver is actually the public key of the token receiver, and “salt” is just some random numbers.

All UTXOs are stored on a Merkel tree. The Merkel tree has a preset height. The height value determines the number of transactions that the transaction pool can handle during the entire life cycle of the Merkel tree. Upper/lower limit.

Figure: UTXO Merkelgen

Each branch (leaf) on the Merkel tree is either a UTXO or null (null value). Each null represents an empty space, which can be filled into a new UTXO in the future. Once a null value is filled, it cannot return to the initial state. All branches are initially empty, that is, null.

Except for the recipient, the real UTXO will not be disclosed to anyone. Therefore, the branches on the Merkel tree are actually UTXO hashes, which is why “salt” needs to exist. Without it, once Alice knows Bob’s public key, she can use a different number to verify whether Bob’s public key (hash value) appears on the Merkel tree, thereby brute-forcing the transaction amount. At this point, Bob’s transaction is no longer anonymous.

Photo: Merkelgen

transaction

Suppose Alice wants to transfer some tokens to Bob in private. The token belonging to Alice is stored in UTXO, and the recipient of the token is equivalent to Alice’s public key. To keep the transaction private, Alice created a transaction in the following form:

This transaction has 2 inputs and 2 outputs (the exact number of inputs and outputs is not necessarily 2, but must be the same-all transactions are the same), here the input is some existing UTXO, corresponding to Merkel The branch on the tree; the output is a brand new UTXO, which will be added to the Merkel tree in the future.

When Alice initiates a transaction, if she releases exactly two UTXOs that are being spent, the transaction is linked to the transaction that generated the two UTXOs. The purpose of establishing the transaction pool is precisely to ensure that such a link cannot be established to ensure that the input UTXO will not be released. So the question is, how can we ensure that during the transaction, the verification node can confirm that a transaction cost is the existing UTXO, and at the same time it will not announce the real UTXO being spent?

Like many privacy-protected transaction engines, ZeroPool uses a non-interactive zero-knowledge proof (zk-SNARK) to implement private transactions. Zero-knowledge proofs for a specific calculation can support the following forms of cryptographic proofs:

• Given public input 1, public input 2…
• Know some kind of private input 1, private input 2…
• Can get [some conclusion]

The working principle of such knowledge proof is beyond the scope of this article. For more information about this issue, you can click on the blog link to inquire. If you want to conclude a private transaction in the simplest way, the knowledge argument can have the following form:

• Given Merkel root and two hashes OUT_HASH1 and OUT_HASH2,
• There are four such UTXOs: IN1, IN2, OUT1, OUT2, two Merkel proofs P1 and P2 and a private key x,
• The hash values ​​corresponding to OUT1 and OUT2 are OUT_HASH1 and OUT_HASH2 respectively; the receivers in IN1 and IN2 are equivalent to the public key X corresponding to x; merkel proves that P1 and P2 are in the Merkel tree determined by Merkel root Contains valid proofs of IN1 and IN2; the sum of the quantities in IN1 and IN2 is equal to the sum of the quantities in OUT1 and OUT2.

The transaction includes merkle_root, out_hash1, out_hash2, and proof of knowledge. Nothing in the transaction will expose the recipient of the output UTXO, nor will it link the output UTXO to a specific input UTXO. In addition, information such as the transaction amount will not be displayed during the transaction.

For example: As shown in the figure above, suppose that the first and third UTXO of the Merkel tree use Alice as the receiver, and the corresponding amounts are $100 and $17 respectively. Alice knows these two UTXOs, but the No other UTXO is known. If she wants to send Bob $42, the usual practice is that she will first create a transaction that will use her two UTXOs as inputs and create two outputs at the same time:-one sends Bob $42, the other will The remaining 75$ was returned to herself. She told the UTXO belonging to Bob, but the rest of the UTXO was known only to herself, and no one else knew. Moreover, even the hash value of the input type UTXO is kept secret.

The smart contract is responsible for the daily maintenance of the transaction pool. Once the contract receives such a transaction, it will verify the knowledge proof. After the verification is correct, two new UTXOs will be added to the Merkel tree.

After Bob receives UTXO from Alice, he will wait for a while until UTXO’s hash value is included in the Merkel tree before he obtains these tokens in a real sense.

Although this method seems simple, there is a problem that the same UTXO may be reused. Since no one except Alice knows the hash value of the input UTXO, the transaction pool cannot remove the consumed UTXO from the Merkel tree, because even it does not know from which start to remove.

If Alice creates 2 different zero-knowledge proofs, but consumes the same 2 inputs, everyone can verify that two transactions consume some UTXO that originally existed on the Merkel tree, but cannot know the two transactions The UTXO consumed in is actually the same. To solve this problem, we introduced the concept of nullifier. In simple terms, nullifier is the hash value of UTXO and the private key of the UTXO receiver. Then, we changed the proof of knowledge of the transaction to the following:

• Given Merkel root, and two hashes OUT_HASH1 and OUT_HASH2, the other two hashes NULLIFIER1 and NULLIFIER2,
• There are four such UTXOs: IN1, IN2, OUT1, OUT2, two Merkel proofs P1 and P2 and a private key x,
• The hash corresponding to OUT1 and OUT2 are OUT_HASH1 and OUT_HASH2 respectively; the receivers in IN1 and IN2 are equivalent to the public key X corresponding to x; Merkel proves that P1 and P2 are included in the tree with the determined Merkel root Valid proof of IN1 and IN2; the sum of IN1 and IN2 is equal to the sum of OUT1 and OUT2; and hash (IN1, x) is equal to NULLIFIER1, hash (IN2, x) is equal to NULLIFIER2

Please note that any transaction that spends a specific UTXO calculates the same NULLIFIER value, because NULLIFIER depends only on the UTXO hash value and the private key corresponding to the public key in UTXO. Since the NULLIFIER in the above proof of knowledge is in the public “given” statement (Clause), if two transactions using the same UTXO have ever been published, everyone can know that they have the same NULLIFIER, and they appear after discard That deal. It is also worth noting that as long as the hash used to calculate it is an antigen-like attack, NULLIFIER will not display any information about the input UTXO or the recipient’s private key.

Token deposit and withdrawal

The above types of transactions can be used for the transfer of assets in the pool, but for a fully functional trading pool, it must support the transfer of funds inside and outside the pool. Therefore, we added an extra field to the format of the private transaction, called delta, so that the total amount of input UTXO is equal to the number of output UTXO + delta.

• Given a Merkel tree, two hash values ​​OUT_HASH1 and OUT_HASH2, two other hash values ​​NULLIFIER1 and NULLIFIER2, and a delta value.
• It is known that for IN1, IN2, OUT1, and OUT2, four UTXOs are counted, two Merkel proofs P1 and P2, and a private key x,
• Then the hash values ​​corresponding to OUT1 and OUT2 are OUT_HASH1 and OUT_HASH2; the transaction receivers in IN1 and IN2 are equivalent to the public key X corresponding to the private key x; Merkel proves that P1 and P2 have a given hash root Valid proof of the merkel tree containing IN1 and IN2; the number of IN1 and IN2 is equal to OUT1, the sum of OUT2 plus the delta value; hash (IN1, x) is equal to NULLIFIER1; hash (IN2, x) is equal to NULLIFIE2R.

It should be noted that delta is in a given sentence and is therefore public. When NEAR processes the above types of transactions, if the delta value is negative (that is, there are fewer input tokens than output tokens in a private transaction), the extra tokens will be deposited in the account of the transaction initiator; if the delta value is Positive (that is, there are more input tokens than output tokens in a private transaction), the transaction is only valid when the remaining tokens are filled up.

Transaction Fees

Private transactions prohibit the establishment of a connection between the newly created UTXO and the UTXO that was used as transaction input. However, for any transaction that will be recorded on the NEAR chain, the sender of the transaction must pay the gas fee. It is for this reason that there must be a certain number of NEAR tokens in the issuer’s account. The account may not know some means to obtain some NEAR tokens, thus creating some kind of connection between the two UTXOs mentioned above, and the purpose of private transactions will be greatly frustrated.

In order to solve this problem, we introduced the concept of Relayer in the system. Suppose Alice wants to send Bob a transaction and intends to let Ryan act as a relay. The gas fee of this transaction is less than Ⓝ1, and Alice is willing to pay Ryan Ⓝ1, let Ryan help him to chain the transaction.

Alice may not even have a NEAR account, at this time she creates a private transaction. In this transaction, the total funds of the two UTXOs input as the transaction are exactly less than the total funds of the UTXO as the output of the transaction Ⓝ1. The remaining Ⓝ1 is withdrawn to the account of the transaction submitter. Ryan collected the transaction information from Alice, verified its validity, and used his account to submit the transaction. The gas cost consumed in the whole process is less than Ⓝ1, but he was finally rewarded with Ⓝ1.

Alice finally submitted a transaction without revealing her identity, and Ryan received a small return. Please note that in the interaction, neither party needs to gain the trust of others: Ryan cannot tamper with the transaction in any form, leaving him only two options: either submit or give up. Therefore, the biggest risk for Alice is that her transaction may not be submitted (in this case she can ask another relayer). Since Ryan validated the transaction before the transaction was submitted, unless another relayer got ahead first, there would be no risk that Ryan would spend gas but get no return.

future development

The model described above is already a transaction pool that can fully satisfy private transactions. Next, the author will briefly describe how to improve the security or usability of the transaction pool from several aspects.

Pay

In the process of describing the above transaction, the author mentioned that when Alice quietly issued the token to Bob, he also shared the newly created UTXO with the other party. The realization of this process requires Alice and Bob to communicate off-chain, which we do not want to see. To solve this problem, we can extend the transaction pool to store all UTXOs encrypted with the public key of the transaction receiver. When Alice transfers the assets to Bob and creates two new UTXOs, Bob acts as the receiver and his public key will be used by Alice to encrypt UTXO.

Looking at Bob again, he monitors all newly created UTXOs and tries to decrypt them one by one with his own private key. Once he tried the UTXO created by Alice, the decryption was successful-this way, Bob discovered their UTXO completely through NEAR’s unique on-chain communication.

Decoupling signature and proof

When Alice creates a transaction, she needs to use her private key information to design a complex certificate. Therefore, the machine that calculates the certificate needs to obtain her private key, which we do not want to see. In general, private keys are best stored in some external hardware devices. The functions of this type of hardware are usually relatively simple. For example, some products only have the function of message signature. For this kind of hardware, the proof of computing knowledge is usually outside their function.

In order to adapt to these hardware, we generate 3 keys instead of the traditional public-private key pair: private key, decryption key and public key. In this case, a piece of information encrypted with the public key can be decrypted using the decryption key. Similarly, the private key signature can be verified by interpreting the key. Only the public key can be seen by everyone. The decryption key is stored on a device that proves the operation transaction, and the private key is stored on the external device, which can only sign the information. We can make some modifications to the proof of knowledge in the following ways:

• Given Merkel root, two hashes OUT_HASH1 and OUT_HASH2, and two other hashes NULLIFIER1 and NULLIFIER2
• It is known that there are four UTXOs IN1, IN2, OUT1, OUT2, two Merkel proofs P1 and P2, a decryption key d and a signature s.
• The hash values ​​corresponding to OUT1 and OUT2 are OUT_HASH1 and OUT_HASH2; the receivers in IN1 and IN2 are equivalent to the public key X corresponding to d; Merkel proves that P1 and P2 are the Merkel tree of the given hash root and contain IN1 , Valid proof of IN2; the sum of IN1 and IN2 is equal to the sum of OUT1 and OUT2; hash (IN1, d) is equal to NULLIFIER1; hash (IN2, d) is equal to NULLIFIER2, s is message (IN1, IN2, OUT1, OUT2 ) Signature and is valid for d.

When Alice wants to create a transaction, she uses the hardware device signature (IN1, IN2, OUT1, OUT2), and then uses the signature s to generate a certificate on the machine that can only obtain the interpretation key. It should be noted that if the hardware device cannot be used, Alice cannot generate the signature s and cannot spend the money-even if you have obtained the permission to use the machine used to generate the certificate.

Support more tokens

Private transactions are not limited to NEAR tokens. Developers only need to make minor adjustments so that the trading pool can support any token issued on the NEAR platform. The specific implementation is not repeated here.

Conclusion

In addition to working with NEAR, ZeroPool is also building a private transaction function for Ethereum. At present, the funds required for team development mainly come from the community, and enthusiastic readers can support them on Gitcoin.

More story:https://en.0xzx.com/