Categories
Feature Story

Ring Signature Performance Metrics

You won’t believe how fast transaction signature generation and verification can be with this one simple tip only TurtleCoin pros know…

I wrote a bit about the differences in the resulting signature/proof sizes in the last article I posted (Bulletproofs+, Arcturus, Pruning, Massive Ring Sizes, Oh My!) and briefly mentioned some of the performance information for each of those methods. While signature size is important to the overall storage growth of the chain, verification time of those signatures (proofs) is very important to how quickly transactions are relayed throughout the network before being added to a block.

In this article, I’ll take you through the differences in the generation/proving time and the verification times of each of the signing schemes in a bit more detail and how these methods effect the different ways we interact with the blockchain.

Signature Generation

Every user initiated transaction on the network requires a signature that cryptographically proves that you have the knowledge of the private key that generates that signature. The signature is generated just once using that private key and is done (in most cases) only when you are sending a transaction. This work is performed on your device whether it is a PC, mobile phone, or otherwise. How long it takes to construct the signature is of no concern to the network as the network does not sign your transactions, You do.

While we don’t want signature generation to take forever as it negatively impacts the user experience as the time increases — the speed of signature generation is not a large determining factor when selecting a signing scheme.

Signature Verification

What we are very concerned with is signature verification time. This is due to the fact that unlike generating a signature, every node participating in network consensus must verify that a signature is valid (producers/validators).

Checking that signature occurs not once per transaction but twice at minimum:

  • It checks that a signature is valid as the transaction enters its memory pool to ensure that we are not injecting invalid transactions into that pool.
  • Transaction signatures are also checked as they are added to blocks for exactly the same reason.

Each transaction in the memory pool requires multiple iterations of the verification routine. Including transactions in a block has the same requirement. That means that to keep things moving quickly, we need the verification routine to take as little time as possible. Doing so allows the transactions to enter the memory pool faster, propagate across the network faster, and ultimately be committed to a block faster.

In the v1 blockchain, those signatures must also be verified during the node syncing process and only those already included in checkpoints are skipped. This is why syncing a node is slow.

We plan to mitigate this problem via the pruning mechanism that was mentioned in the last article which will allow for skipping this process while syncing a node.

It is also important to note that syncing your wallet does not require that signatures are verified. After all, a wallet does not maintain network consensus and maintain the chain, a node does.

Signature Generation Times

Let’s take a look at the signature generation times of the current v2 implementations of the ring signature signing schemes: Borromean, CLSAG (w/ commitments), and Arcturus.

The y-axis depicts the time in milliseconds (ms) and the x-axis depicts the number of ring participants. As a reminder, there’s 1,000ms in a second.

Note: These results were generated using an AMD 1950X, on Windows 10, using mingw-gcc-8. Actual performance results will vary by CPU, OS, compiler, etc.

But… but… but… you said CLSAG was faster than Borromean. You’re right, I did and that does hold true when the code is optimized; however, I didn’t optimize the hell out of the CLSAG implementation in the v2 crypto library because…

While CLSAG and Borromean generation times stay relatively steady — the Arcturus generation time climbs pretty quickly as the ring size explodes. This may seem concerning; however, as discussed in the previous article the benefit of this is that the signatures are significantly smaller at those massive ring sizes. In addition, we’re forgetting something very important here:

With Borromean & CLSAG sag, we have to have a separate signature for each input of a transactions. The same does not hold true for Arcturus which allows us to prove the knowledge of multiple keys in the same signature.

So, let’s graph those same values again assuming we have eight (8) inputs in our transaction.

Now that looks like a comparison that makes a bit more sense.

Here we can see that at the largest ring sizes, Arcturus generation time is, in essence on par with CLSAG generation times. Also, as expected, Borromean Ring Signatures are still faster at those ring sizes; however, as you may recall, Borromean Ring Signatures are significantly larger.

The clear winner in this case considering the resulting signature size is clearly Arcturus.

Signature Verification Times

Now that we’ve taken a quick look at the generation times, let’s wander on over to the verification side of the fence. After all, it’s a very important side of the fence, probably the best side of the fence ever, and no one will ever make their side of the fence look like our side of the fence…

Less time is better and the gray line clearly won.

Using just one input in the transaction, Arcturus is the clear winner coming in at about 2x the speed of a Borromean Ring Signature verification and almost 4x the speed of the CLSAG verification.

Seriously though, I know my CLSAG implementation in the crypto library is unoptimized (for now) and I don’t need to remind myself with pretty graphs.

Bill Gates, 1986 – Founder at Microsoft

What’s that mean to a transaction with eight (8) inputs? Let’s take a look.

The proof is in the pudding as they say

The difference between the proving schemes is much more apparent with multiple inputs. Arcturus performance during verification of large rings doesn’t even break the one (1) second barrier until 8,192 ring participants. Meanwhile Borromean and CLSAG blow past the one (1) second mark at 512 and 256 ring participants respectively.

For the largest ring sizes measured, Arcturus is 13x faster than Borromean and 25x faster than CLSAG for the same ring size.

I’ve beat the literal crap out of CLSAG in this article. That wasn’t my intent. An optimized implementation performs far better than as shown here but Arcturus still eats CLSAG’s lunch.

And the Winner is…

Considering the sheer speed of Arcturus at larger ring sizes and the significant space savings, it’s clear that putting in the leg work to get a working implement of Arcturus in C++ was well worth the time.

Doing so allows us to investigate and use the large ring sizes (or bigger) mentioned in the previous article while knowing that in doing so we are not negatively impacting the performance of the blockchain as we continue to work towards v2.

Anyone else as elated as I am for v2? Good, you should be ­čÖé

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.