ERC721 Extension for zk-SNARKs

Hi community,

I’ve recently been working on this draft that describes zk-SNARK compatible ERC-721 tokens:
https://github.com/Nerolation/EIP-ERC721-zk-SNARK-Extension

Basically every ERC-721 token gets stored on a Stealth Address that constists of the hash h of a user’s address a, the token ID tid and a secret s of the user, such that stealthAddressBytes = h(a,tid,s). The stealthAddressBytes are inserted into a merkle tree. The root of the merkle tree is maintained on-chain. Tokens are stored at an address that is derived from the user’s leaf in the merkle tree: stealthAddressBytes => bytes32ToAddress().

For transfering a token, the contract requires a proof that a user can
i) generate a stealth address that is included in the merkle tree
ii) generate the merkle tree after updating the respective leaf

For minting a token, the contract requires a proof that a user can
i) generate a stealth address and add it to an empty leaf in the merkle tree
ii) generate the merkle tree after updating the respective leaf

For burning a token, the contract requires a proof that a user can
i) generate a stealth address and delete it from a leaf in the merkle tree
ii) generate the merkle tree after updating the respective leaf

NOTE: The generation of the stealth address requires to have access to a private key. E.g. a user signs a message, the circuit parses the public key (…and address), hashes the address together with the token ID and a secret value and inserts the result into a leaf of the merkle tree. In the end the circuit compares the calculated and user-provided roots for verification.

For general information, have a look at Vitalik’s short section on private POAPs in this article on SoulBound tokens.
I think, this EIP is the exact implementation of what Vitalik described.

This is the current draft of the interface:

// SPDX-License-Identifier: CC0-1.0
pragma solidity ^0.8.6;
...
interface ERC0001 /* is ERC721, ERC165 */ {

    /// @notice Mints token to a stealth address `stA` if proof is valid. stA is derived from
    ///  stealthAddressBytes which is the MIMC Sponge hash `h` (220 rounds) of the user address `eoa`,
    ///  the token id `tid` and a user-generated secret `s`, such that stA <== address() <== h(eoa,tid,s).
    /// @dev Requires a proof that verifies the following:
   ///        - prover can generate the StealthAddress (e.g. user signs msg => computePublicKey() => computeStealthAddress() ).
    ///       - prover can generate the merkle root from an empty leaf.
    ///       - prover can generate the merkle root after updating the empty leaf.
    /// @param currentRoot A known (historic) root.
    /// @param newRoot Updated root.
    /// @param stealthAddressBytes Hash of user address, tokenId and secret.
    /// @param tokenId The Id of the token.
    /// @param proof The zk-SNARK.
    function _mint(bytes32 currentRoot, bytes32 newRoot, bytes32 stealthAddressBytes, uint256 tokenId, bytes proof) external;

    /// @notice Burns token with specified Id from stealth address `stA` if proof is valid.
    /// @dev Requires a proof that verifies the following:
    ///       - prover can generate the StealthAddress (e.g. user signs msg => computePublicKey() => computeStealthAddress() )
    ///       - prover can generate the merkle root from an non-empty leaf.
    ///       - prover can generate the merkle root after nullifieing the non-empty leaf.
    /// @param currentRoot A known (historic) root.
    /// @param newRoot Updated root.
    /// @param stealthAddressBytes Hash of user address, tokenId and secret.
    /// @param tokenId The Id of the token.
    /// @param proof The zk-SNARK.
    function _burn(bytes32 currentRoot, bytes32 newRoot, bytes32 stealthAddressBytes, uint256 tokenId, bytes proof) external;

    /// @notice Transfers token with specified Id from current owner to the recipient's
    /// stealth address, if proof is valid.
    /// @dev Requires a proof that verifies the following:
    ///       - prover can generate the StealthAddress (e.g. user signs msg => computePublicKey() => computeStealthAddress() ).
    ///       - prover can generate the merkle root from an non-empty leaf.
    ///       - prover can generate the merkle root after updating the non-empty leaf.
    /// @param currentRoot A known (historic) root.
    /// @param newRoot Updated root.
    /// @param stealthAddressBytes Hash of user address, tokenId and secret.
    /// @param tokenId The Id of the token.
    /// @param proof The zk-SNARK.
    function _transfer(bytes32 currentRoot, bytes32 newRoot, bytes32 stealthAddressBytes, uint256 tokenId, bytes proof) external;

    /// @notice Verifies zk-SNARKs
    /// @dev Forwards the different proofs to the right `Verifier` contracts.
    ///  Different Verifiers are required for each action, because of the merkle-tree logic involved.
    /// @param currentRoot A known (historic) root.
    /// @param newRoot Updated root.
    /// @param stealthAddressBytes Hash of user address, tokenId and secret.
    /// @param tokenId The Id of the token.
    /// @param proof The zk-SNARK.
    /// @return Validity of the provided proof.
    function _verifyProof(bytes32 currentRoot, bytes32 newRoot, bytes32 stealthAddressBytes, uint256 tokenId, bytes proof) external returns (bool);
}

This EIP is still in idea stage (no pull-request yet).
Looking for collaborators!

4 Likes

I feel like you can accomplish this with much lighter-weight technology.

Just use regular stealth addresses:

  • Every user has a private key p (and corresponding public key P = G * p)
  • To send to a recipient, first generate a new one-time secret key s (with corresponding public key S = G * s), and publish S
  • The sender and the recipient can both compute a shared secret Q = P * s = p * S. They can use this shared secret to generate a new address A = pubtoaddr(P + G * hash(Q)), and the recipient can compute the corresponding private key p + hash(Q). The sender can send their ERC20 to this address.
  • The recipient will scan all submitted S values, generate the corresponding address for each S value, and if they find an address containing an ERC721 token they will record the address and key so they can keep track of their ERC721s and send them quickly in the future.

The reason why you don’t need Merkle trees or ZK-SNARK-level privacy is that each ERC721 is unique, so there’s no possibility of creating an “anonymity set” for an ERC721. Rather, you just want to hide the link to the sender and recipient’s highly visible public identity (so, you can send an ERC721 to “vitalik.eth” and I can see it, but no one else can see that vitalik.eth received an ERC721; they will just see that someone received an ERC721).

You can generalize this scheme to smart contract wallets by having the smart contract wallet include a method:

generateStealthAddress(bytes32 key) returns (bytes publishableData, address newAddress)

which the sender would call locally. The sender would publish publishableData and use newAddress as the address to send the ERC721 to. The assumption is that the recipient would code generateStealthAddress in such a way that they can use publishableData and some secret that they personally possess in order to compute a private key that can access ERC721s at newAddress (newAddress may itself be a CREATE2-based smart contract wallet).

One remaining challenge is figuring out how to pay fees. The best I can come up with is, if you send someone an ERC721 also send along enough ETH to pay fees 5-50 times to send it further. If you get an ERC721 without enough ETH, then you can tornado some ETH in to keep the transfer chain going. That said, maybe there is a better generic solution that involves specialized searchers or block builders somehow.

18 Likes

Possible correction - Public key where G is the base point of ECG

2 Likes

是否可支持跨链支付其他的代币呢,因为所有网络都是一个大家庭,覆盖率广,使用率高,效益越好,即流量为王

Stealth Address (BSAP/ISAP/DKSAP) 只能暂时隐藏吧,一旦接受地址被转账,则发送者->隐藏接收地址-》提取地址 的转账路径还是会出现在 ERC20/NFT 合约的 transfer event 中。

Given the pure stealth address are essentially generating fresh ethereum addresses for the purposes of this scenario wouldn’t it make more sense to implement as a wallet level protocol rather than in a token standard?

As @vbuterin stated above this would make the most sense in a smart contract wallet, but the problem remains that has needs to be paid in an unlinkable way otherwise the protocol would only delay the construction of a transaction graph by an observer rather than properly prevent it.

I see 2 approaches here assuming our stealth address protocol is smart contract wallet based: A) an out of band payment is made to compensate a gas related, or B) the transaction compensates a gas relayer from a seperate stealth address where stealth addresses. B is the ‘decentralized’ approach, but would only really achieve UTXO levels of privacy, A would be as private as the out of band payment method to the gas relayer and strongly private to everyone else assuming the gas relayer can be trusted to not reveal any data they obtain but this is obviously a fairly centralized approach.

Side note: Using a zk shielded pool with approach B would prevent visibility of the transaction graph which should result in a strongly private protocol, I’m not sure another generalized approach is possible without a significant change to Ethereum’s transaction format.

Only Stealth Address is not enough to cut off the linkage between sender and receiver, but combining with a Merkle tree(like Tornado Cash’s), and using the stealth address’s private key as the Merkle tree leaf’s committed value to withdraw the money, can work here. This is how Eigen Network(https://www.eigen.cash) implements its anonymous payment.

1 Like

The main difference between a Zcash-style zk-SNARKs + Merkle tree method vs stealth addresses method mentioned by Vitalik above is in terms of confidentiality vs anonymity–the token id transacted can be hidden with zk-SNARKs but not with stealth addresses (which only provide anonymity). Note that token ids transacted does represent some information leak. In the particular case of transfers, we can aim for full confidentiality of transactions instead of just anonymity. However, for supporting more complicated smart contract logic taking token type and amount (ERC20 / 1155), then we can only hope to achieve anonymity.

An additional downside to stealth address is that if it is applied to anything beyond 721 (like 20 or 1155), then there is very little privacy added as the chain of transfers can be traced. Whereas a zk-SNARK based method can preserve confidentiality or anonymity completely.

Ideally, L1s should support privacy-preserving tokens that can be used by smart contract applications (anonymity for composable on-chain transactions and confidentiality for P2P swaps / transfers). This can be achieved with known techniques. Effectively, one can take the best part of privacy-focused L2s like Aztec, ZkOpru, Railgun, and Eigen and make the privacy-preserving token accounting default on the L1. This is described in FLAX. The main problem to have built-in privacy on Ethereum is that we have a fixed gas fee payment mechanism tied to EOAs, making all privacy-preserving token standard moot unless we have a privacy-preserving gas payment method. This is why privacy is currently best done in a separate layer for Ethereum unless privacy-preserving gas payments are possible. A privacy layer also has the added benefit of not needing to change token standards on L1–the smart contract own assets on behalf of its “L2” users on L1.

However, there are ways to salvage this with anonymous gas payments and privacy-preserving ERC20/721/1155s. For gas payments, we can combining a shielded token pool (e.g. Zcash style zk-SNARKs + Merkle tree) into EIP-4337. Composable usage of tokens in these shielded pools require alternative to ERC20 approve that is atomic and stateless (can be done by expanding call stack access as described here). The caveat is that this means we need to change user transaction / ERC20 / Defi ecosystems entirely, and at that point, might as well build a privacy layer on-top of Ethereum.

1 Like

Likely this is a better fit for Soulbound Tokens, where we

  • don’t necessarily desire anonymity but just unlinkability of nyms
  • gas less of an issue / out-of-band gas more viable (DAO can provide gas station for SBT holders to do SBT-related stuff)

If SBTs:

  • each go to a fresh stealth address (if the mint is self-serve the user can generate a private key themselves, rather than going through the stealth address generation protocol)
  • can optionally be linked
  • can be issued/revoked via semaphore/interep proof (there’s a question of whether all-or-nothing sharing is achievable here)
  • can be added/removed from semaphore/interep group

This pretty much gets us to DeSoc, except of course you’d need at least one social recovery set per connected component of nyms.

1 Like

Hello guys.
I developed an NTF smart contract based on DKSAP(Dual-Key Stealth Address Protocol) last month, I welcome everyone to discuss it.

1 Like

The reason why this needs to be standardized is that the sender needs the ability to automatically generate an address belonging to the recipient without contacting the recipient.

I like the idea and it makes full sense to implement it in the way suggested
Removing the zk-SNARK part comes with further simplification, which is great.

Only one thing:
In the case, C representing a contract (going to be) deployed on A through CREATE2, the sender would have to use a different method (using the recipient’s address, salt, bytecode) to generate the address for C, which would destroy privacy, or do I miss something here? How would the recipient be able to have a contract already waiting at A to receive the token? In other words, would the sender have to anticipate a specific CREATE2 call eventually executed by the recipient at address A?

Addressing the remaining challenge mentioned, I’m generally a fan of specialized searchers (as implemented in Surrogeth) implemented in the final app. However, this would require to have some additional functionality for handling related incentives for frontrunners within the standard. Therefore I agree that the “pay for the recipients’ transfers and then tornado-refill” is the better approach.

I’m keen to implement it.
EDIT: Find a minimal poc with stealth addresses here.

I guess, the approach suggested by @vbuterin is the one that we should go for:
I’ve started drafting an EIP here.

Please feel free to provide feedback!

Also, I’m looking for contributors with experience in the EIP process and Crypto/Ethereum in general, to help me implementing it.

In other words, would the sender have to anticipate a specific CREATE2 call eventually executed by the recipient at address A?

Yes, this is exactly the idea. In general, this is a common pattern for smart contract wallets, which is necessary to replicate the existing functionality where users can receive coins to an address they generate offline without having to spend coins to register that address on-chain first.

@Nerolation now that I think more about this, I am realizing that it doesn’t actually make sense to make this standard part of ERC721 per se. There are lots of potential use cases for it. So it probably should be an independent ERC that lets users generate new addresses that belong to other users, and both ERC721 applications and other applications can use that ERC.

Aside from that, my main feedback to the EIP so far is that I do hope that something like the generateStealthAddress method idea from my earlier post can be added so that we can support smart contract wallets.

1 Like