Apply Batch Verification Technique to increase Incognito throughput

What privacy problem are you solving?

Currently, based on the performance evaluation shown in the Incognito White Paper, the throughput of Incognito chain is quite low: 4TPS for each shard and 32 TPS for 8 shards. Compared with other privacy chains such as Monero, ZCash, or Beam, Grin, 4TPS for each shard is a number with room for improvement (4TPS for Monero, 6TPS for ZCash, 10TPS for Beam, and 17TPS for Grin).

The majority of overhead comes from the heavy cryptographic operations required to verify the correctness and soundness of each transaction. Specifically, for each new output that is created in a transaction by a sender, Pedersen commitment is used to shield the amount. To verify the correctness of the shielded amount, the sender must provide a range proof to show that all computations are correct and this amount is in the range [0, 264). This incurs a large computation cost in the process of verifying a transaction.

What is the solution?

Fortunately, the verification range proof in each transaction can be executed in parallel. Thus, we can apply the batch verification technique [Bunz et al., 2018] to verify a batch of transactions at once.

Batch verification is based on the observation that g x = 1 and g y = 1 can be checked by drawing a random scalar c from a large enough domain and checking g cx+y = 1. With high probability, the latter equation implies that g x = 1 and g y = 1, but the latter is more efficient to check. The batch verification technique is especially helpful in verifying a large number of transactions.

More details on batch verification is carefully presented in [Bunz et al., 2018].

Who are you?

The project will be implemented by @hieutran and @anpham from the core team. We are attracted by the mystical world of cryptography – with blockchain, it’s the real world now!

@hieutran is a cryptography researcher. His research topics are applied cryptography, privacy-preserving for outsourced data, and privacy blockchains.

@anpham is a cryptography engineer. He is currently completing his degree at the University of Science, Ho Chi Minh City. His research topics are applied cryptography and searchable encrypted data. He also has 1-year experience as a Software Engineer and will help in completing this task.

Why do you care?

As previously mentioned, 4TPS is not an impressive number. We believe that we can increase this number by twofold at least. We hope this will make Incognito one of the top privacy solutions for the crypto world.

What’s your plan? What’s your schedule?

The project duration will be 1 month from Feb 01, 2020, Feb to 29, 2020.

What’s your budget?

The project will be undertaken by 2 cryptography engineers:

Resource Cost Quantity Monthly Cost
Cryptography engineer 1,000 PRV 2 2,000 PRV
Subtotal 2,000 PRV
TOTAL (x 1 months) 2,000 PRV

Is there an existing conversation around this idea?

Not yet in this forum

Is there anything else you would like the community to know?

Let us know what you think!

Reference

[Bunz et al., 2018] Bunz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., and Maxwell, G. (2018). Bulletproofs: Short proofs for confidential transactions and more. In 2018 IEEE Symposium on Security and Privacy (SP), pages 315-334. IEEE.

7 Likes

@hieutran, can you please add progressing for this proposal today

1 Like

Update Progress (28 Feb)

We have finished this project with impressive results.

Specifically, each block is able to process more than 500 transactions in the most common case (one input and two outputs per transaction). That means Incognito throughput can achieve 12.5TPS per shard, and linearly scale up to 100TPS per 8 shards at this time.

The detail is shown in this figure:
image

This result is integrated on test-net from 20 Feb and integrated on main-net from 27 Feb.

4 Likes

Awesome! Great result. All funds have now been disbursed.

Moved this project to the ‘Completed’ subcategory. :smiling_face_with_three_hearts: