Monero and beyond

Part 3
Today we will describe another important component of the Monero technology platform related to transactions. Then, we will explain why it is used in CUTcoin.
In parallel with the development of Chinese researchers, which we managed to describe in the previous part, work on reducing the size of the transaction went from the side of the original RingCT protocol, among which was Greg Maxwell, who suggested to use Pedersen Commitments in the original the RingCT protocol. At the end of 2017 (an augmented version was presented in May 2018 at the IEEE Symposium on Security and Privacy), a group of authors with his participation released a work entitled "Bulletproofs: Short Proofs for Confidential Transactions and More". It will be discussed today.

What are Bulletproofs?
In short, this is not interactive zero knowledge proofs, or constructions that provide participants in the system with the opportunity to verify the truth of certain statements. Their important feature is the absence of trusted setup (i.e., participants are not required to trust a friend or a single center). In Monero, using Bulletproof, for example, it is confirmed that the encrypted number is in the specified range, while other information about it is not disclosed, as well as the equality of the amount of coins at the input and output of the transaction (money is not printed from thin air).

Bulletproof technology is based on an article on zero-knowledge proofs for arithmetic circuits, written in 2016. In theoretical informatics, an arithmetic circuit is a calculation model in which the inputs pass through a sequence of circuit elements, each of which performs a certain operation (calculates a specific function of the input data). In this work, the authors propose a zero-knowledge proof to solve the Circuit Satisfiability Problem, which grows logarithmically (and not linearly, as it was before) from its size. Somewhere we already saw a similar trick, huh?

Recall from the first part that the use of the Pedersen Obligation in Confidential Transactions allows us to determine that the nominal values of inputs and outputs are in a certain interval - this whole thing has the name range proof. Range proof is added to each transaction, thereby increasing its size.

In fact, Bulletproof is a replacement for range proof at the stage of "signing" a commitment. At the same time, bulletproof is shorter than other range proof. Bulletproof not only helps reduce the size of transactions using Confidential Transaction, but also allows the examiner to combine multiple range proofs for transactions with multiple outputs into one short proof. Instead of transactions with multiple outputs requiring range proof for each output, they can all be merged into one.

Bulletproof allows implementing protocols of confidential computing with several participants (Secure Multi-party computation, MPC), as well as creating smart contracts with increased privacy. At the same time, unlike zk-SNARK and zk-STARK, Bulletproof do not require trusted setup and are smaller in size, although their verification takes longer time.

Since the introduction of Bulletproof in Monero code, the transaction size has been reduced by 80%.

It is clear that the role Bulletproofs plays in Monero is huge, so it is important to understand what changes have occurred in them due to the implementation of tokens in CUTcoin. In the CUTcoin ecosystem, when a transaction is conducted, the sender pays a fee, and this will also work in transfers with tokens.
Moreover, the commission will be paid in CUT. This means that in one transaction there may be inputs / outputs of both tokens and CUTcoin coins. In transactions, they should create such a
Bulletproof design that:

1. the equality of the amounts of coins and tokens at the input and output of the transaction is confirmed;
2. it is confirmed that the ratings of inputs / outputs are positive.

At the same time, tokens with CUT coins should not be mixed with each other.
To make these properties available, Bulletproof has been amended to remember the identifiers of tokens participating in the transaction, and the identifiers themselves are included in the operations of forming a commitment.
From the point of view of the end user, this is good news, since minor changes in the old, well-tested technology has significantly expanded the functionality of the CUTcoin platform.