Applied ZK part 2 or how we improved the proof generation time from 46 hours to 10 seconds

Hi Internet! This is the second part of the series on our ZK research and the direct sequel to the previous issue, "Applied ZK or how we built a ZK product and why it took us 18 repositories" — make sure to read that article first. I'll only dive into how the new approach differs and won't cover any ZK or cryptography basics discussed earlier.

Let's go!

The main changes

• We launched SealCred email domain verification if you haven't heard already. You can verify that you work at some company by proving that you own, for instance, a google.com email — and then get a ZK badge attesting it.
• We abandoned the Merkle tree approach altogether (at least for now) for being slow, expensive — and apparently utterly unnecessary if we fix a few issues I'll discuss in this article.
• So what do we use instead? We swapped ECDSA signatures created by users with EdDSA signatures created by attestors to be used in the ZK circuits. This allowed us to move the proof generation to the browser! Read on to learn more.
• We added support for any ERC721 contracts (NFTs) as inputs for the ZK badges! Yes, we no longer allowlist the contracts — you now can mint a derivative from a MyFavoriteNFTCollection NFT.
• We added support for the mainnet NFTs! Yes, you can "bridge" the credentials and pieces of your identity from the Ethereum mainnet to the Goerli testnet! Try it out at SealCred. It's up and completely free!
• We moved away from fetching the largest getLogs request on our own server to getLogs on the Alchemy infrastructure, which made the initial loading time of the website drop from ~3 minutes to ~2-5 seconds!
• We have improved the privacy aspect by moving the nullifier generation to the client-side from the server-side. Even though we haven't saved any logs before that could potentially dox users, now we can't do this even if we want! Can't be evil > don't be evil, they say.

First, how did we decrease the proof generation time by so much?!

Well, by outwitting the physical limitations of the algorithms, markets and physics, really. While everybody else looks at the ZK attestation problem from one point of view (i.e. generating Merkle trees, storing their roots and providing the Merkle proofs), we took a step back. We noticed that there is a whole branch of developing cryptography that, for some reason, gets ignored by companies in the space.

See, there are a few problems with the Merkle tree approach and ECDSA verification in ZK circuits that make the tech inferior and unusable:

• Merkle roots have to be centrally updated on the blockchain for every supported collection (hence most of the ZK badge solutions have "allowlists" of supported NFTs or credentials).
• ECDSA verification in ZK circuits is not viable for most users (the best solution so far is being developed by the heyanon.xyz team, but still requires using Chrome).
• Merkle roots are getting outdated extremely fast. Basically, every time the NFT in question changes hands! Which makes ZK proofs generated for a specific Merkle root invalid. So you first wait a few minutes until your ZK proof is ready — and then pray that the Merkle root hasn't changed in the meantime.

Not to mention a variety of other issues that @0xShitTrader and @gubsheep pointed out after reading my tech dive into the previous way of how SealCred worked (the Merkle tree way).

But the worst part so far is that most users have to outsource ZK proof generation to a centralized outside server beefed up enough to efficiently use the verify function of circom-ecdsa! What does this mean? It means sending all your private inputs to other parties that generate the proofs! (Let's be honest: no user will ever spin up their beefed-up server to generate a ZK badge).

Initially, we also went this way, as evident by the code in our open source repositories and the previous issue of this series. But we were on a hunt to achieve supremacy on the ZK battlefield amongst all the companies trying to release a similar product.

And life found a way, as it usually does. We have a given: it is prohibitively expensive to run the verify function for ECDSA in ZK circuits. What can we use instead? What works way better and faster than ECDSA in circom? The answer is evident to anyone familiar enough with cryptography:

Yo, why didn't anyone think of it sooner? The implementation of the EdDSA verify function in circom is so lightweight that my Texas Instruments calculator could run it (if it wanted to). I mean, "if the mountain won't come to Muhammad, then Muhammad must go to the mountain."

But the Devil is in the details. Wallets don't support EdDSA signatures (the last time I checked, none of the popular ones did), so the user can't efficiently prove the ownership of an Ethereum address.

Why, yes, the user can't — but we certainly could! So we created the 🌈attestor🌈 — a magical being that could attest to anything we wanted — yet could dox no one. The plan was to make it check the sources of the ZK badges, issue an attestation signed with EdDSA — and then create a ZK badge on the client-side from this attestation revealing only a part of it.

This way, the attestor could attest to almost anything! It's an oracle!

But Nikita — you might ask — isn't it the same as sending all the private inputs to a centralized server and generating a ZK proof on it? No — I'd answer — it is not if you don't have a connection between different attestations.

The 🌈attestor🌈

Our attestor can attest to the following things at the moment:

• Email ownership
• Ethereum address ownership
• Balance of an Ethereum address in any smart contract with the balanceOf function
• Contract metadata (name and symbol) of the given contract from the mainnet

The first three are signed with EdDSA and the fourth with ECDSA (I'll tell you why in a moment). Let's go over them one by one.

@Post('/email')
async sendEmail(@Body({ required: true }) { email }: EmailVerifyBody) {
  const domain = email.split('@')[1].toLowerCase()
  const domainBytes = padZeroesOnRightUint8(utils.toUtf8Bytes(domain), 90)
  const signature = await eddsaSigFromString(domainBytes)
  return sendEmail(email, "Here's your token!", signature)
}

This is us generating an EdDSA signature for the message containing just the domain part of the email. So if you wanted to create a ZK badge for the fact that you own an @apple.com email, you'd submit your full email here, and the server would send you the apple.com message signed with EdDSA private key owned by our attestor. This signature will be sent to the specified email and will be the password that anyone owning an @apple.com email would be able to obtain.

In fact, we got like 9,665 badges generated for @gmail.com emails at v0.2.0 and 1,293 badges for @gmail.com at v0.2.4 of the SCEmailLedger contract. I have no idea who would want to verify ownership of this domain email, but people have their reasons, and I'm not here to judge.

One peculiarity is us padding (and effectively limiting) the length of the domain to 90 characters when the RFC limit is 255. For now, I simply hope that 90 characters will be enough for everyone. However, in the future, we will explore ways of getting the limit closer to standard 255. This is done due to how circom circuits are written, and I'll explain more in the circuits section. This is what the token looks like:

Then, you simply paste this token into sealc.red and generate the ZK proof that you indeed know the "password" (or, more accurately, the EdDSA signature) for the email domain you've posted. I'll tell you how this ZK proof can be used later in the contracts section.

But how would smart contracts know what are the correct attestor public keys? We've got you covered!

@Get('/eddsa-public-key')
async publicKey() {
  if (publicKeyCached) {
    return publicKeyCached
  }
  const babyJub = await buildBabyjub()
  const F = babyJub.F
  const eddsa = await buildEddsa()
  const privateKey = utils.arrayify(env.EDDSA_PRIVATE_KEY)
  const publicKey = eddsa.prv2pub(privateKey)
  publicKeyCached = {
    x: F.toObject(publicKey[0]).toString(),
    y: F.toObject(publicKey[1]).toString(),
  }
  return publicKeyCached
}

@Get('/ecdsa-address')
ecdsaAddress() {
  if (ecdsaAddress) {
    return ecdsaAddress
  }
  const ecdsaWallet = new ethers.Wallet(env.ECDSA_PRIVATE_KEY)
  const address = ecdsaWallet.address
  ecdsaAddress = address.toLowerCase()
  return ecdsaAddress
}

These are the two methods that you can actually call by simply landing here and here! You will find the public key and the address there. We're using the field math in the EdDSA public key to make sure everything is compatible with the EdDSA verify function in circom.

And in case you want to fetch where the emails should come from:

@Get('/email')
email() {
  return env.SMTP_USER
}

Simple so far, isn't it? One of the most prominent qualities of the code we try to thrive for is simplicity. Simplicity runs in our veins. We breathe simplicity. Simple means less fragile. Less moving pieces are easier to maintain and audit.

@Post('/ethereum-address')
async ethereumAddress(
  @Body({ required: true })
  { signature, message }: AddressVerifyBody
) {
  // Verify ECDSA signature
  const ownerAddress = ethers.utils.verifyMessage(message, signature)
  // Generate EDDSA signature
  const eddsaMessage = ownerAddress.toLowerCase()
  const eddsaSignature = await eddsaSigFromString(
    utils.toUtf8Bytes(eddsaMessage)
  )
  return {
    signature: eddsaSignature,
    message: eddsaMessage,
  }
}

And this is how we verify ownership of an Ethereum address! We take your ECDSA signature that is unviable in the ZK world and return you an EdDSA signature verifying the same thing but more compatible with circom! This is all there is to it, really.

Verifying the balance of an Ethereum address in a smart contract is a bit more complicated, though:

@Post('/balance')
async balance(
  @Ctx() ctx: Context,
  @Body({ required: true })
  { tokenAddress = zeroAddress, network, ownerAddress }: BalanceVerifyBody
) {
  const provider = networkPick(network, goerliProvider, mainnetProvider)
  // Verify ownership
  let balance: BigNumber
  try {
    // Check if it's ethereum balance
    if (tokenAddress === zeroAddress) {
      balance = await provider.getBalance(ownerAddress)
    } else {
      const abi = ['function balanceOf(address owner) view returns (uint256)']
      const contract = new ethers.Contract(tokenAddress, abi, provider)
      balance = await contract.balanceOf(ownerAddress)
    }
  } catch {
    return ctx.throw(badRequest("Can't fetch the balance"))
  }
  // Generate EDDSA signature
  const eddsaMessage = `${ownerAddress.toLowerCase()}owns${tokenAddress.toLowerCase()}${network
    .toLowerCase()
    .substring(0, 1)}`
  const eddsaSignature = await eddsaSigFromString([
    ...utils.toUtf8Bytes(eddsaMessage),
    balance,
  ])
  return {
    signature: eddsaSignature,
    message: eddsaMessage,
    balance: balance.toHexString(),
  }
}

As you may have noticed, we pass three parameters: tokenAddress, network and ownerAddress. If tokenAddress is zero, we assume we're looking for the simple Ethereum balance. If, for some reason, we can't fetch the balance, too bad. We just throw an error.

The signature, in the end, looks like this:

0xbf74483DB914192bb0a9577f3d8Fb29a6d4c08eEowns0xd9b78a2f1dafc8bb9c60961790d2beefebee56f4m

The first 42 bytes are the UTF-encoded owner address, then the word owns, then the 42 bytes of UTF-encoded token address, then either a g or an m (depending on the source of the credential). This schema is subject to change in the future. It is probably just a thing we dreamed up when developing the concept and didn't give it too much thought. For instance, we can probably substitute 42 address bytes for a single uint256 and ditch the owns word altogether.

Oh, and then we append the balance as a simple uint256 into the signature. Because we'll need the actual balance in the circuits section. For now, just know that this allows the attestor to verify the balance of any given Ethereum address at any given Ethereum smart contract supporting the balanceOf function on the mainnet and the Goerli testnet!

And the myth, the legend, the saviour of this "bridge":

@Post('/contract-metadata')
async contractMetadata(
  @Ctx() ctx: Context,
  @Body({ required: true })
  { tokenAddress, network }: MetadataVerifyBody
) {
  // Get metadata
  let name: string
  let symbol: string
  const contractMetadata = reservedContractMetadata[tokenAddress]
  if (contractMetadata) {
    name = contractMetadata.name
    symbol = contractMetadata.symbol
  } else {
    try {
      const abi = [
        'function name() external view returns (string memory)',
        'function symbol() external view returns (string memory)',
      ]
      const contract = new ethers.Contract(
        tokenAddress,
        abi,
        networkPick(network, goerliProvider, mainnetProvider)
      )
      name = await contract.name()
      symbol = await contract.symbol()
    } catch (error) {
      return ctx.throw(
        badRequest(
          `Can't fetch the metadata: ${
            error instanceof Error ? error.message : error
          }`
        )
      )
    }
  }
  if (!name || !symbol) {
    return ctx.throw(badRequest('Name or symbol not found'))
  }
  const message = [
    ...ethers.utils.toUtf8Bytes(tokenAddress.toLowerCase()),
    networkPick(network, 103, 109), // 103 = 'g', 109 = 'm',
    ...ethers.utils.toUtf8Bytes(name),
    0,
    ...ethers.utils.toUtf8Bytes(symbol),
  ]
  const signature = await ecdsaSigFromString(new Uint8Array(message))
  return {
    signature,
    message: utils.hexlify(message),
  }
}

What's going oooooooooooooooooon here?! In reality, we just fetch the name and the symbol of the given token on the given network and sign it with ECDSA private key specific to this attestor. The message signed consists of 42 bytes of UTF-encoded address, g or m as the network identifier, an arbitrary number of bytes for the name of the contract, \0 as the delimiter, and an arbitrary number of bytes for the symbol of the contract.

This serves as a certification of the name and the symbol of the original contract on the mainnet when minting derivatives on another network (Goerli in our case here).

This is all the attestor can do for now!

🍪 The circuits 🍪

Time to talk business. All this cryptography stuff above is boring. Everybody knows it. Let's spill the beans about what's happening under the hood. We'll start with the helper circuits first.

pragma circom 2.0.4;

include "../../node_modules/circomlib/circuits/mimcsponge.circom";

template Nullify() {
    signal input r;
    signal input s;

    component mimc = MiMCSponge(2, 220, 1);
    mimc.ins[0] <== r;
    mimc.ins[1] <== s;
    mimc.k <== 0;

    signal output nullifierHash <== mimc.outs[0];
}

This is our nullifier. It will be helpful a bit later, but for now, just keep in mind that it takes 2 numbers as an input, hashes it with MiMCSponge (a ZK-friendly hash function) and outputs just one number — the hash.

pragma circom 2.0.4;

include "../../node_modules/circomlib/circuits/eddsamimc.circom";
include "../../node_modules/circomlib/circuits/mimc.circom";

template EdDSAValidator(messageLength) {
  // Check if the EdDSA signature is valid
  signal input pubKeyX;
  signal input pubKeyY;
  signal input R8x;
  signal input R8y;
  signal input S;
  signal input messageHash;
  signal input message[messageLength];

  component verifier = EdDSAMiMCVerifier();
  verifier.enabled <== 1;
  verifier.Ax <== pubKeyX;
  verifier.Ay <== pubKeyY;
  verifier.R8x <== R8x;
  verifier.R8y <== R8y;
  verifier.S <== S;
  verifier.M <== messageHash;
  // Check if the EdDSA's "M" is "message" hashed
  component mimc7 = MultiMiMC7(messageLength, 91);
  mimc7.k <== 0;
  for (var i = 0; i < messageLength; i++) {
    mimc7.in[i] <== message[i];
  }
  messageHash === mimc7.out;
}

The EdDSA validator circuit is a bit more complicated. We pass it the components of an EdDSA signature and the unhashed message. This is done purely for convenience so we can operate on the raw message outside this validator.

We check that the raw message is indeed the one hashed before signing, verify the signature and return the public key of the signer. Easy-peasy! Now, let's see how we use the helpers in the email verifier circuit:

pragma circom 2.0.4;

include "../node_modules/circomlib/circuits/mimc.circom";
include "../node_modules/circomlib/circuits/comparators.circom";
include "./helpers/Nullify.circom";
include "./helpers/EdDSAValidator.circom";

template EmailOwnershipChecker() {
  var domainLength = 90;
  var messageLength = 90;
  // Get message
  signal input message[messageLength];
  // Output domain
  signal output domain[domainLength];
  
  for (var i = 0; i < domainLength; i++) {
    domain[i] <== message[i];
  }
  // Check if the EdDSA signature is valid
  signal input pubKeyX;
  signal input pubKeyY;
  signal input R8x;
  signal input R8y;
  signal input S;
  signal input M;

  component edDSAValidator = EdDSAValidator(messageLength);
  edDSAValidator.pubKeyX <== pubKeyX;
  edDSAValidator.pubKeyY <== pubKeyY;
  edDSAValidator.R8x <== R8x;
  edDSAValidator.R8y <== R8y;
  edDSAValidator.S <== S;
  edDSAValidator.messageHash <== M;
  for (var i = 0; i < messageLength; i++) {
    edDSAValidator.message[i] <== message[i];
  }
  // Create nullifier
  signal input r2;
  signal input s2;

  component nullifier = Nullify();
  nullifier.r <== r2;
  nullifier.s <== s2;
  
  signal output nullifierHash <== nullifier.nullifierHash;
}

component main{public [pubKeyX]} = EmailOwnershipChecker();

We add the following ingredients to the ZK pie:

• Domain string as message (e.g. gmail.com)
• Deconstructed EdDSA signature from the /email endpoint of the attestor
• Mysterious r2 and s2 for the nullifier
• No sodium

When the ZK pie cools down, we get the following public inputs/outputs:

• The domain string
• The public key of whoever signed the message with EdDSA
• The nullifier hash

Woah, that's deep. This is basically the example everyone talks about when explaining ZK. That part about Alice knowing the password to the door in the cave that leads to the second path and Bob patiently waiting outside proving his theory that Alice would do anything to show that she knows the password (presumably from the wifi controlling the door), except for telling the password to Bob.

Anyway, I'm getting derailed a bit. Basically, suppose you have this ZK proof. In that case, you can verify that you know a password (the EdDSA signature) created by a specific attestor (the public key) for a particular email domain (the domain string).

The nullifier is here so that other people can't use the same ZK proof again. The proof is public, after all, and can only be used once. r2 and s2 are basically an ECDSA signature created by the user who generates the proof on the client-side. Or it can be any 2 random numbers; we really don't care. They are there to simply represent an ID of this proof so that it can be saved on the blockchain and not used again.

There are no security concerns about it with anonymity as no one can track you by just two random numbers that appear precisely once.

Now to the real MVP, the balance verifier circuit that is ‼️universal️️‼️ — and you heard that right, here's what it all means:

pragma circom 2.0.4;

include "../node_modules/circomlib/circuits/mimc.circom";
include "../node_modules/circomlib/circuits/comparators.circom";
include "./helpers/Nullify.circom";
include "./helpers/EdDSAValidator.circom";

template BalanceChecker() {
  var addressLength = 42;
  var ownsWordLength = 4;
  var networkLength = 1;
  var messageTokenLength = addressLength + ownsWordLength + addressLength + networkLength;
  // Get messages
  signal input messageToken[messageTokenLength];
  signal input messageAddress[addressLength];
  // Check if token owner address is the same
  for (var i = 0; i < addressLength; i++) {
    messageToken[i] === messageAddress[i];
  }
  // Export token address
  var tokenAddressIndex = addressLength + ownsWordLength;
  
  signal output tokenAddress[addressLength];
  for (var i = 0; i < addressLength; i++) {
    tokenAddress[i] <== messageToken[tokenAddressIndex + i];
  }
  // Check if the EdDSA signature of token balance is valid
  signal input pubKeyXToken;
  signal input pubKeyYToken;
  signal input R8xToken;
  signal input R8yToken;
  signal input SToken;
  signal input MToken;
  signal input balance;

  component edDSAValidatorToken = EdDSAValidator(messageTokenLength + 1);
  edDSAValidatorToken.pubKeyX <== pubKeyXToken;
  edDSAValidatorToken.pubKeyY <== pubKeyYToken;
  edDSAValidatorToken.R8x <== R8xToken;
  edDSAValidatorToken.R8y <== R8yToken;
  edDSAValidatorToken.S <== SToken;
  edDSAValidatorToken.messageHash <== MToken;
  for (var i = 0; i < messageTokenLength; i++) {
    edDSAValidatorToken.message[i] <== messageToken[i];
  }
  edDSAValidatorToken.message[messageTokenLength] <== balance;
  // Check if the EdDSA signature of address is valid
  signal input pubKeyXAddress;
  signal input pubKeyYAddress;
  signal input R8xAddress;
  signal input R8yAddress;
  signal input SAddress;
  signal input MAddress;

  component edDSAValidatorAddress = EdDSAValidator(addressLength);
  edDSAValidatorAddress.pubKeyX <== pubKeyXAddress;
  edDSAValidatorAddress.pubKeyY <== pubKeyYAddress;
  edDSAValidatorAddress.R8x <== R8xAddress;
  edDSAValidatorAddress.R8y <== R8yAddress;
  edDSAValidatorAddress.S <== SAddress;
  edDSAValidatorAddress.messageHash <== MAddress;
  for (var i = 0; i < addressLength; i++) {
    edDSAValidatorAddress.message[i] <== messageAddress[i];
  }
  // Check if attestors are the same
  pubKeyXToken === pubKeyXAddress;
  // Get the network
  signal output network <== messageToken[messageTokenLength - 1];
  // Check if the balance is over threshold
  signal input threshold;

  component lt = LessThan(252);
  lt.in[0] <== threshold;
  lt.in[1] <== balance + 1;
  lt.out === 1;
  // Create nullifier
  signal input r2;
  signal input s2;
  
  component nullifier = Nullify();
  nullifier.r <== r2;
  nullifier.s <== s2;

  signal output nullifierHash <== nullifier.nullifierHash;
}

component main{public [threshold, pubKeyXToken]} = BalanceChecker();

The inputs:

• Token ownership string (x owns y on z
• The owner's address string (e.g. 0xbf74483DB914192bb0a9577f3d8Fb29a6d4c08eE)
• The token ownership EdDSA signature from the attestor
• The owner address ownership signature from the attestor (obtained separately from the token ownership signature)
• The token balance of the owner's address
• The threshold for the amount verification
• The no longer mysterious r2 and s2 for the nullifier

The outputs:

• The token address balance of which we're proving
• The network of the attestation source (either g or m)
• The nullifier to prevent reusing the ZK proof
• The threshold used in the proof
• The public key of the attestor

Along the way, we're checking some conditions about the proofs' token addresses and owner addresses matching each other and the balance being over the threshold. Basically, this proves that you know the private key of an Ethereum address that owns at least threshold balance of the specified token.

Again, you already know what will come next having this ‼️universal️️‼️ proof, but I won't spoil our future products for you.

See? Circom isn't that scary after all! And even better than that, the fact that we went away from the ECDSA verification in ZK circuits allows us to iterate on the circuit designs much faster. Basically, any potato can compile the circuits now in a fraction of the time that the ECDSA verify function made us wait.

Now, what are the attack vectors here? What can we do to dox a person creating a ZK badge? Technically, we can keep logs of all the Ethereum address ownership verification requests and the requests close to them with the balance verifications for the same address.

How can we eliminate this potential issue? There are a few ways that we're currently exploring:

1. Allowing users to compile ZK proofs from attestations obtained from multiple attestors
2. Pre-publish the signed balances of all active Ethereum addresses and keep the list updated

We'll talk about the first one a bit later in the article, but the second one can be done on a very tight budget! Just publish the list of signatures on IPFS; it is as simple as that. We can even mix in the block number into the ZKP to "expire" the proofs that are too old! It depends on the next few months of our cryptography research advancements, but in the worst-case scenario, we'll just pre-publish all the signatures and call it a day. Then we won't be physically able to dox people at all.

🦄 The smart contracts 🦄

They didn't change much, except for the following parts:

• The number of arguments for the proofs passed to the verifiers has changed
• Proofs that are passed into the mint functions are now structs
• Ledgers now also have the mint function that spawns derivative contracts if they don't exist yet and proxies the call to the derivatives
• All of our smart contracts are now fully covered with tests
• Mint functions got refactored
• ExternalSCERC721Ledger was added as a "bridge" into other networks (primarily the mainnet)
• ExternalSCERC721Ledger's mint function takes in the ECDSA signed metadata for the contracts originating in the mainnet (that's why you need it in the attestor)
• All of the ledger and derivative contracts check the attestor public key from the ZK proofs against the key predefined when created

All of our contract code is very self-explanatory! Go check it out; it's all open source!

The drawbacks and potential solutions

Keep in mind that SealCred is in the active development and experimentation phase! There will be breaking changes, and we can't promise that whatever you read above won't change in the next few weeks!

However, there are a couple of apparent issues in the current approach that we're taking:

1. attestor can potentially generate malicious proofs
2. attestor can potentially implicitly connect ZKP to a user (but cannot prove it entirely, and there are ways already to mitigate this issue)

The second issue can be solved by either allowing multiple attestors in the same ZK proof — I talked about it a bit earlier. The first issue is a bit more challenging to tackle. We'll either find a cryptographically sound way to eliminate this issue (like we did with the nullifiers) or simply decentralize the attestors! Whatever route we'll take, make sure to follow our blog for the upcoming updates!

Conclusion

This was a long article! Thank you a lot for reading it whole! Ultimately, we moved away from using ECDSA signatures towards using EdDSA signatures in the ZK circuits. Even though there are some drawbacks, this solution can be viable while we look for new ways of approaching the ZK problems. And it is still way better than sending all the private inputs at once to a centralized ZK proof generator shared between multiple users.

I hope you enjoyed this deep tech dive into our new approach. Join our Discord server if you have further questions or feedback! Or just shoot us an email at [email protected].

Good luck!