# Bulletproofs+, Arcturus, Pruning, & Massive Ring Sizes

It's been about 3 months since our last update regarding v2 development and we figured it was about time to provide the community with an update on our progress. There's a lot of awesome news packed into this update so sit back, relax, and get your party poppers ready. We've got some news... and it's going to make *some people* **very** upset...

## Cryptographic Methods

At the heart of every blockchain project is the code that makes the magic happen. The fundamental math that handles the calculations required to handle our good friend [Elliptic Curve Cryptography](https://en.wikipedia.org/wiki/Elliptic-curve_cryptography) ("ECC"). ECC serves as the method for how private keys and public keys are generated, how those points on the graph are related, and how those points are manipulated (added, subtracted, multiplied, etc.). The ability to manipulate the points in a secure way provides us with the foundational building tools to build the vast majority of blockchain networks.

TurtleCoin® is no different. Today, v1 relies on a slight variation of [ED25519](https://en.wikipedia.org/wiki/EdDSA#Ed25519) using [Curve25519](https://en.wikipedia.org/wiki/Curve25519). The implementation differs from ED25519 which relies on SHA-512 ([SHA-2](https://en.wikipedia.org/wiki/SHA-2)) by instead utiliziling a non standards compliant implementation of Keccak (aka [SHA-3](https://en.wikipedia.org/wiki/SHA-3)) in the form of `cn_fast_hash()` as well as encoding private keys slightly different than as defined in the RFCs.

> For the nerds in the crowd, the implementation is non standard due to a use of a slightly different padding.

Those of you that have worked to create various implementations of wallet software, address generators, etc. have undoubtedly came across this variation a few times and said to yourself "wtf" when you try to use a standard SHA-3 or ED25519 library in the language of your choice.

#### Out With The Old, In With The New

The new crypto core is still built on Curve25519; however, instead of using non-standard Keccak, we're moving to the SHA-3 standard. Every construction whether it be key derivations, output creation & scanning, signature construction, view key generation, etc. has been moved over to better support the use of standard hashing libraries. It's not a huge change, but it does make a difference. The result of this is that if you were to restore a v2 wallet using a wallet seed generated by v1 software, you will get two totally different wallet addresses.

To be abundantly clear, **v1 and v2 keys, seeds, and wallets will not be interoperable**.

In addition to that change, considerable work has been done to make using the primitives a lot easier in downstream code. The framing around the cryptographic foundations has been rewritten to make using, reading, and understanding how those primitives work as easy as possible while still maintaining as much performance as we can. The end result is a generally easy to understand and read implementation of the framework required to build a blockchain project.

Turning code that looks like this:

bool secret_key_to_public_key(const SecretKey &sec, PublicKey &pub)
{
    ge_p3 point;
    if (sc_check(reinterpret_cast<const unsigned char *>(&sec)) != 0)
    {
        return false;
    }
    ge_scalarmult_base(&point, reinterpret_cast<const unsigned char *>(&sec));
    ge_p3_tobytes(reinterpret_cast<unsigned char *>(&pub), &point);
    return true;
}

Into this:

crypto_public_key_t secret_key_to_public_key(const crypto_secret_key_t &secret_key)
{
    // A = (a * G) mod l
    return secret_key * Crypto::G;
}

Not only makes the code about 1000x easier to read and understand but greatly reduces the entry barrier required to get in there and start working with things. It also makes it a lot easier to build more advanced constructs including some of the additions that have been baked into the new cryptographic core.

## Reducing Transaction Size

As we have outlined in previous updates, one of the foundational issues that the network has had in the past is the explosive growth of the chain in terms of storage requirements. While dropping junk in TX_EXTRA has been a large driver of that growth, the vast majority of the storage is driven by the input signatures attached to each transaction input. Today, these signatures amount to 512bytes (0.5KB) per input with a ring size of 4. It doesn't seem like much, but when some transactions have 10s or hundreds of inputs that 512 bytes explodes at a very linear rate.

While the bulk of a transaction is the signatures of those inputs, the need for working with certain denominations of coins or "pretty amounts" (ie. 1, 2, 3, 10, 20, 30, 100, 200, 1000, etc.) also contributes to the bulk of a transaction size. The use of pretty amounts is what drives the need for fusion transactions whereby all of the smaller denominations ("dust") are traded in for larger denomination outputs that can be spent later. The requirement that denominations exist and are used results in more dust, more transactions, and a larger chain overall.

To combat this issue, we're doing away with the requirement to transact in denominations and changing the ways in which signatures are constructed.

### Masked Amounts

To get rid of the requirement to transact in certain denominations v2 will utilize masked amounts and rely on [Pedersen Commitments](https://en.wikipedia.org/wiki/Commitment_scheme) to denote both input and output values of the coins that are transacted without ever revealing to a third-party the actual value of the coins. Pedersen Commitments have been heavily used in other blockchain projects such as Monero (XMR). A side benefit to this method includes the increased privacy of the transactions on the network.

Pedsersen commitments have a nifty property in that they can be added and subtracted from each other much like regular numbers can be added and subtracted from each other and arrive at the same result.

For example, assuming our commitment generator is $C$:

$C(a + b) = C(a) + C(b)$

The commitments do not reveal the actual values of $a$ and $b$ and an outside party has no clue what those values are.

This is very handy for ensuring that the tally of output commitments is equal to the tally of input commitements -- or put simply, that a transaction is in balance.

#### Range Proofs

The primary issue with using Pedersen Commitments for transacting on a network are that it is possible to construct output commitments that overflow the number space that ultimately results in the rampant creation of new coins without the authorization to do so.

For example, let's assume that we have an unsigned 8-bit number space available. We know that if we overflow the maximum value of that space (255), that the number overflows and comes back around to end up where it doesn't make sense. We also know negative values stuffed into thay same space results in a value that underflows and arrives at a place that doesn't make sense.

Let's take a quick look at this in practice and how this can be exploited.

**Note:** The values are shown below for explanation purposes, in practice, they are hidden by their commitments.

$i_1 = 4$
$i_2 = 40$
$i = 4 + 40$

Then we construct two (or more) outputs to arrive at the same value.

$o_1 = 100$
$o_2 = 200$
$o = 100 + 200$

We can clearly see that $300 \ne 44$ However; in 8-bit math, the number rolls over the top such that $100 + 200 = 44$ resulting in the tally of inputs and outputs matching. If you're following along, you can see that we just minted coins (256 to be exact) out of thin air. **Not cool**.

The same trickery can be performed using negative values as well (ie. $-100 + -120 = 44$) because of the number bounds that turn that into $156 + 112 = 300$ which wraps around again such that $156 + 112 = 44$. **Definitely not cool**.

This is where Zero Knowledge Range Proofs come in to save the day. They allow us to prove to a third-party (ie. the network) that the values contained in the output commitments of a transaction are within a certain range without revealing the values they represent. In our case, the range is defined as 0 to $2^{64} - 1$ otherwise known as what can fit within an unsigned 64-bit number space.

### Bulletproofs+

We will be using [Bulletproofs+](https://eprint.iacr.org/2020/735.pdf) ("BPs+") for our Zero Knowledge Range Proof in v2. To prove to a third-party (the network) that the values of the commitments in our transactions are within the bounds specified.

You may have noticed that we skipped right over [Bulletproofs](https://eprint.iacr.org/2017/1066.pdf) ("BPs") and instead went straight for Bulletproofs+. The constructions are relatively similar with the resulting difference being that the cryptographic proof of the values of our commitments are within the defined range are *smaller* in terms of byte size and verify just a little bit faster than Bulletproofs.

Another huge benefit of BPs or BPs+ is that a proof can be batched meaning that we can prove the values of multiple commitments all within a singular proof. Instead of submitting one proof for each output commitment, we are able to submit a single proof for all of the output commitments in a single transaction. This **greatly** reduces the amount of storage required to transmit and/or store the transaction while still maintaining masked amounts. This results in smaller transactions and thus **lower transaction fees**.

For the sake of testing and benchmarking the new cryptographic core contains implementations of both Bulletproofs and Bulletproofs+. We'll be relying on BPs+ until something better comes along.

### Signature Construction

#### Borromean Ring Signatures

Today, v1 uses Borroeman Ring Signatures and each input in a transaction contains such signature whose size is proportional to the ring size. As the size of the ring grows, the size of the ring signature for each input grows as mentioned above. The growth is linear to the number of ring participants which is detremeninal to the size of transactions and thus drives up **transaction fees**.


Adding commitments into the mix only further slows things down and causes massive chain bloat. So, what are our options if we want to increase ring size as part of the change to v2?

At a ring size of 256 participants, the signature size is `16,384` bytes or 16KB without including signing the commitments. **Yikes!**

#### Concise Linkable Ring Signatures (CLSAG)

You may recognize [CLSAG](https://eprint.iacr.org/2019/654.pdf) from a recent XMR upgrade performed in October 2020. CLSAG greatly reduces the size of the signature of each input supplied for a transaction. While it still grows at a linear rate it grows quite a bit slower. It's also a bit faster in the construction and verification routines as opposed to Borromean.


At a ring size of 256 participants, the signature size is considerably smaller in our construction coming in at `8,259` bytes or ~8KB *including* commitments which is a drastic reduction in storage space.

Cutting the size of the signatures in about half results in our transactions costing significantly less. **Woot!**

Can we do better? Can we crank this thing up to 11? You're damn right we can.

#### Arcturus

[Arcturus](https://eprint.iacr.org/2020/312.pdf) is the new hotness put together by the Monero Research Lab ("MRL") that significantly reduces the size of a "ring signature". Not only that, but it also performs the work of protocols such as RingCT that check that the tally of input commitments and output commitments balance while proving the commitments to zero for those commitments (ie. proving that you know the real values of those commitments). If that were not enough, it also permits multi-index proving such that it's possible to combine all of the attestations that we know the values of the commitments as well as have the private ephemeral for each real input being spent into a single proof.

> I'm taking a bit of liberty here in calling Arcturus a ring signature as it's not so much a ring signature as it is a cryptographic proof; however it is functionally equivalent to a ring signature for our purposes and helps keep the information relatable.

Comparatively speaking, verification times are, at times, about twice (2x) as fast (or more) as a CLSAG verification of the same ring size.

The multi-index capabilities of Arcturus have massive benefits to v2. Instead of having a signature for each input in a transaction, we are able to combine all of the inputs into a single signature (proof). This means that as we include more inputs in a transaction the signature does not grow linearly anymore thus reducing transaction size resulting in **even lower transaction fees**.

The downside is that the construction (generation) time is considerably longer for large rings. That's okay though as signatures/proofs are only constructed when you use your wallet to create a new transaction.


As you can see, the size of the ring no longer grows linearly with the size of the ring. At a ring size of 256 participants, the signature size comes in at a panty dropping `1,294` bytes in our implementation. This means that our signature is not only ~16% the size of a CLSAG signature but is also ~8% of the size of a Borromean signature. Couple that with the fact that we can now bake multiple spends inside a single signature (proof) and we've potentially cut **up to 99%** (depending on the number of inputs) of the signature bulk off a transaction sent on the network. **HELL YES!**

What's this mean for users? **Very, very, very, very low transaction fees!**

#### The Code

You can find C++ code for all of these signing mechanisms as well as the range proofs in this article in the [turtlecoin-crypto](https://github.com/turtlecoin/turtlecoin-crypto) repo on the development branch. The code is currently licensed under the MIT License. In addition to the C++ code, this repo also builds the Node Native C++ Addon Module, Javascript (ASM.js), and WASM targets for use in other downstream projects.

> Please note that as of the time of this writing, the final touches are being put on the Arcturus code but it will be pushed up in the next few days.
>
> None of the code has been audited nor are there any plans to have any audits performed. It works and passes our unit tests and right now, that's good enough for us. We are misfits after all, right?

## Just The Tip

Now that we have cut down the size of transactions so that they are a fraction of their previous size, we got to thinking... how else can we cut down on the storage requirements of the v2 chain and cut down on chain sync time. As we all know syncing the chain on a node is by far the best way to find the time to learn a new hobby. It's not fast -- even with checkpoints -- it takes a while.

After mulling it over a bit, the thought came to us that we don't need to carry around our range proofs and transaction signatures indefinitely... that they are in fact... **immediately and forever prunable**. Notice we said **immediately prunable** as in we don't need to wait for a certain number of blocks to pass before pruning the signatures and range proofs from the transactions. Nor do we need to make this *optional* for node operators -- it just *is*. Transactions can be pruned as soon as they are committed to the chain (included in a block).

> Nodes will keep transactions in an alternate mempool for a certain number of blocks, in the rare event that a re-organization event does occur, they will be able to pluck the full details of the transaction from that alternate mempool. Once enough blocks have passed, transactions in the alternate mempool can be purged.

You may be scratching your head and wondering what we're thinking as that information has to be there to verify a transaction during the sync process... right? **No, it doesn't.**

In a traditional PoW network, such information has to be maintained to ensure that the blockchain is valid from start to the tip of the chain -- verifying *every bit* along the way. This method also allows for handling chain re-organization events which are common in blockchain networks.

We already use checkpoints to short-circuit many of the checks normally performed by providing a list of *trusted* hashes for prior blocks. Checkpoints allow us to bypass the need to verify everything in that range of blocks (including the transactions and their signatures/proofs) and saves a lot of time.

In the v2 PoS scenario, we vote to trust that the block producers and validators have verified the signatures and range proofs for each transaction in a block before throwing their stamp of approval on the block (via a signature). Once the producers and validators sign a block, it's solid, it's not going anywhere. It is "in stone" as they say and while a chain re-organization is *possible*, it's very unlikely. If they don't properly verify signatures and range proofs well... that's where they get *penalized*.


What this allows us to do is to define the structure of our transactions *differently*. Whereas today transaction hashes (and thus the hashes included in blocks) are generally constructed based upon the hash of every byte of a transaction `(prefix || signature || range_proof)`, TurtleCoin® v2 transaction hashes will be computed based upon the hash of `(prefix || H(signature) || H(range_proof))`.

By constructing our transactions in this way, we are able to keep the **full** transaction (including the full signature and range proof) in the pending transaction mempool so that producers and validators can verify the signatures and range proofs. When the transaction is committed to the chain (included in the block), we can instantly drop the full signature and range proof from the data and swap the hashes of those structures into their place for long term storage which **drastically reduces the storage required to operate a node**.

While a signature + range proof may require `1,938` bytes in the mempool, once committed to disk, that same signature and range proof will only require `64` bytes of storage. This results in a reduction in transaction storage requirements of **over 96%**.

Pretty cool aeh?

## Enhanced Privacy Features

If you've read through all that, you can see that the vast majority of the work for v2 has focused on reducing the chain size and making verifications faster to support making the chain faster to sync and allowing wallets to sync as fast as possible. This greatly improves the experience when working with the network which was on of the core goals for v2.

However, in focusing on improving the experience of using TurtleCoin® we picked up numerous privacy enhancements along the way. What we have in the oven now is something truly unique. The combination of enabling Amount Masking and Arcturus allow us to provide 100% privacy with ring sizes far larger (and thus much harder to trace) than other projects -- all coupled together with PoS.

While we test, benchmark, and debate whether 256, 512, 1,024, or larger ring sizes make the most sense for the network, we know that any of those ring sizes far exceed the ring sizes used by other projects (including XMR) and provide people with a network that they can securely and easily transact on. Throw in the fact that the relaunch allows us to enable the use of massive ring sizes starting with block `0`, the privacy offered by TurtleCoin® v2 will exceed that of practically every other privacy project out there.

No *tainted* outputs, no *legacy* spends, no *small traceable rings*, no messy *output migrations*. Just secure, confidential, and highly anonymized transactions on a small lightweight chain.

## What's Next?

Now that we have the core cryptography out of the way we can direct our focus back to finalizing block and transaction structures (90% complete) then start work on building up the blockchain storage subsystem, building the staking system, and wiring up the rest of the network node. From there, we'll work on building out the new CLI wallet that will be designed from the ground up.

We hope you're as excited as we are as we continue to build the next generation of the TurtleCoin® network from scratch using the latest and greatest technology available.