Last week, we announced a collaboration with ZeroPool that will add support for private transactions to the NEAR Protocol. In NEAR today, all transactions are public—similar to Bitcoin and Ethereum. That means that—for every transaction—the sender, the receiver, and the amount transacted are all public. This is what allows everyone to audit the ledger and confirm that all the transactions are valid and no tokens are spent twice.
In many cases, it is desirable to transact in a way where only the participants involved in the transaction can have any insight into it. Achieving this while maintaining the ability to validate the correctness of the ledger is a complex task involving non-trivial cryptography.
In this blog post, I will dive deep into the internals of how private transactions will be implemented on NEAR so that no information about the participants or amounts are revealed—all without sacrificing the ability to validate the correctness.
Each leaf of the tree is either an UTXO, or null, indicating a vacant spot that can in the future be occupied by a new UTXO. Once a spot is occupied, it never frees up. Initially, all the leaves are nulls.
The actual UTXO is never revealed to anyone but the receiver. Instead, the leaves of the merkle tree are hashes of the UTXOs—thus the need for the salt. Without the salt, if Alice knows Bob’s public key, she can brute-force different amounts and see if the hash of amount, Bob’s public key appears as the leaf of the tree, thus deanonymizing a transaction sent to Bob.
The transaction has exactly two inputs and exactly two outputs (the exact number of input and output UTXOs doesn’t have to be two but does need to be the same for all the transactions). The inputs are some existing UTXOs that correspond to some leaves of the merkle tree, and the outputs are brand-new UTXOs that will be appended to the tree.
When Alice is sending the transaction, if she actually publishes the two input UTXOs that are being spent, she will link the transaction to the transactions that produced those UTXOs. The goal of the pool is to make sure that such links cannot be established and thus the input UTXOs cannot be published.
How can we implement the transactions in such a way that the validators can confirm that it spends some existing UTXOs without revealing the actual UTXOs being spent?
ZeroPool, like many other privacy-preserving transaction engines, uses zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARKs) for this purpose.
Zero-knowledge arguments of knowledge for a particular computation allow producing cryptographic proofs of the following form:
Given public input 1, public input 2 …
I know such private input 1, private input 2 …
That [some claim]
The way such arguments of knowledge work is outside the scope of this writeup. For more on this topic, this blog post provides a great overview with a lot of details.
For the purposes of the private transactions, in the most naive way, the argument of knowledge can have the following form:
Given the merkle root, and two hashes OUT_HASH1 and OUT_HASH2,
I know four such UTXOs IN1, IN2, OUT1, OUT2, two merkle proofs P1 and P2 and a private key x,
That hashes of OUT1 and OUT2 are correspondingly OUT_HASH1 and OUT_HASH2, and the receiver in IN1 and IN2 is equal to the public key X that corresponds to x, and the merkle proofs P1 and P2 are valid proofs of inclusion of IN1 and IN2 in a tree with the given merkle root, and the sum of amounts in IN1 and IN2 is equal to the sum of amounts in OUT1 and OUT2.
The transaction then consists of merkle_root, out_hash1, out_hash2, argument of knowledge, and nothing in the transaction reveals the recipients of the output UTXOs nor links the output UTXOs to the particular input UTXOs. Moreover, even the amount transacted is not revealed in the transaction.
For example, in the figure above, say the first and third UTXOs in the merkle tree have Alice as the recipient and amounts of $100 and $17 correspondingly. Alice knows those two UTXOs but has no insight into any other UTXO in the tree. If she wants to send $42 to Bob, she creates a transaction that uses both of her UTXOs as inputs and creates two new outputs: one sending $42 to Bob and another sending the remaining $75 to herself. She reveals the UTXO that is intended for Bob to Bob. But the remaining UTXOs are not known to anyone but her. Moreover, even the hashes of the input UTXOs are not revealed to anyone.
The smart contract that maintains the pool, once it receives such a transaction, verifies the argument of knowledge. If it checks out, it appends the two new UTXOs to the tree:
Once Bob receives the UTXO from Alice, he waits until the hash of the UTXO appears in the tree. Once it does, Bob has the tokens.
The problem with this naive approach is that the same input UTXO can be spent twice. Since nobody but Alice knows the hashes of the input UTXOs, the pool cannot remove the spent UTXOs from the merkle tree because it doesn’t know what to remove to begin with.
If Alice creates two different zero-knowledge arguments that both spend the same two inputs, everybody will be able to verify that both transactions spend some UTXOs existing in the merkle tree but will have no insight into the fact that those UTXOs are the same in the two transactions.
To address this problem, we add a concept of a nullifier. In the simplest form for a particular UTXO the nullifier is a hash of the UTXO and the private key of the receiver of that UTXO. We then change the argument of knowledge for the transaction to the following:
Given the merkle root, and two hashes OUT_HASH1 and OUT_HASH2, and two more hashes NULLIFIER1 and NULLIFIER2
I know four such UTXOs IN1, IN2, OUT1, OUT2, two merkle proofs P1 and P2 and a private key x,
That hashes of OUT1 and OUT2 are correspondingly OUT_HASH1 and OUT_HASH2, and the receiver in IN1 and IN2 is equal to the public key X that corresponds to x, and the merkle proofs P1 and P2 are valid proofs of inclusion of IN1 and IN2 in a tree with the given merkle root, and the sum of amounts in IN1 and IN2 is equal to the sum of amounts in OUT1 and OUT2, and hash (IN1, x) is equal to NULLIFIER1 and hash (IN2, x) is equal to NULLIFIER2
Note that any transaction that spends a particular UTXO will have the same NULLIFIER computed because the NULLIFIER only depends on the hash of the UTXO and the private key that uniquely corresponds to the public key in the UTXO. And since the NULLIFIER in the argument of knowledge above is in the “Given” clause, which is public, if two transactions that spend the same UTXO are ever published, everybody will be able to observe that they have the same NULLIFIER and discard the later of the two transactions.
Also note that, for as long as the hash used to compute it is preimage resistant, the NULLIFIER reveals nothing about either the input UTXO or the private key of the receiver.
April 22, 2020