SDBS #31: Stealth Feeless Transactions

Summary

In a significant improvement to the Stealth protocol, feeless transactions successfully went live on the Stealth public testnet just a few days ago. Today’s post describes in considerable detail what feeless transactions are (and aren’t) and how they work on the Stealth blockchain. I will also highlight some design and implementation decisions, to help readers understand how Stealth feeless transactions represent an improvement over other models. In some respects, this post might be considered the Stealth Feeless Transaction Whitepaper.

Transaction Fees

In all but a few notable exceptions, financial transactions require an additional monetary fee to execute the transaction. For example, at the time of writing, the Ethereum (ETH) fee for a simple value transfer (sending some money) is $21.41 (USD). So, let’s say you want to pay $4 for a latte. To pay with Ethereum, the total cost for that latte would be $25.41, an absurd cost to say the least. Bitcoin is no better, as the current fee is $23.45.

Clearly, with such astronomical fees, Bitcoin and Ethereum fail at being “electronic cash”. These high fees are not momentary spikes. Both Bitcoin and Ethereum fees have been at least $5 since January 1. High fees for the major cryptocurrencies are likely here to stay.

The following chart, taken from bitinfocharts.com, shows the magnitude of Ethereum fees for the last year:

Although transaction fees can get out of hand, in cryptocurrencies they serve an important function, which is to prevent malefactors from spamming the blockchain with useless transactions. At a cost of $23.45 for each transaction, an individual wishing to clog Ethereum would quickly go broke. Even national governments would quickly deplete their budgets in such attacks. Asking taxpayers for funding aimed at slowing Ethereum transactions would be political suicide. In non-democratic nations, despotic leaders would simply graft such budgets for their own coffers, and Ethereum would proceed unaffected. The bottom line is that fees are awesome to prevent spam.

In some blockchains, transaction fees also compensate block producers. In fact, Bitcoin transaction fees represent almost 10% of miner income.

In other blockchains, like Stealth, transaction fees are effectively burnt, rewarding all stakeholders proportional to their stake. Even though a single Stealth balance doesn’t change, its share of the money supply increases each time a fee is burnt.

As great as they are for spam prevention and revenue sharing, transaction fees have a couple of drawbacks. First is that they can quickly spiral out of hand, as described above for Ethereum and Bitcoin. Neither project has a plan for reducing fees and making their blockchains directly useful for electronic cash payments, ignoring clunky “layer 2” approaches, like Bitcoin’s “Lightening Network”.

— — — — — — —

Feeless Transactions

Before we can define a “feeless transaction”, we first have to clarify what is meant by the term “feeless”. As used with cryptocurrencies, the term is somewhat of a misnomer. According to several online dictionaries, “feeless” means the absence of any fee. In other words, the traditional use of the term “feeless” essentially means “free”. However, for cryptocurrencies, feeless typically does not mean free. The reason for this specialized definition is, of course, to fight spam. Free transactions do nothing to prevent spam, and free spam will completely kill a blockchain.

In the context of blockchain, the term “feeless” means the absence of a money fee. For Bitcoin, the money fee is paid in BTC, and for Ethereum, the money fee is paid in ETH.

If a feeless transaction has no money fee, what prevents free spam?

Cryptocurrencies have two approaches.

The first approach to feeles transactions uses a type of proof-of-work (PoW) to replace a fee. While most every person somewhat knowledgeable of cryptocurrencies has heard of PoW in the context of Bitcoin mining, it is not widely known that the concept of PoW was invented around 1997 to discourage email spam. Though it has been around for nearly a quarter of a century, PoW has not been used widely to prevent spam of any type, except in the area of cryptocurrencies. In fact, to my knowledge, the first and only use of PoW to gain traction as spam prevention has been in the NANO cryptocurrency (ignoring any NANO clones, of course).

The second type of fee replacement in cryptocurrencies was pioneered by Steem. With Steem, accounts need to “vest” (impermanently lock) enough coins to allow the account to make transactions, with the number of transactions per day proportional to the amount of STEEM vested.

Central to Steem’s concept of feeless transactions is the use of accounts. As we shall see, Stealth does not have accounts on its blockchain, making any approach to bonded accounts too cumbersome to be practical. Additionally, Steem-type accounts are not truly “permissionless”, requiring an existing account to create a new account. In other words, users have to get permission from an existing account to have their own account.

— — — — — — —

Stealth Feeless Transactions

Like Nano, Stealth uses PoW for its feeless transactions, but with some important differences.

Hash Functions

To understand Stealth feeless transactions, and to understand many concepts in blockchain technology, it is critical to understand what a hash function is. While I don’t have time to fully explain the concept here, I can vastly simplify it with an approximate description (see elsewhere for a complete technical description).

A hash function takes an input, like say someone’s name (e.g. “Alice”) and produces a long number from that input. For example, a commonly used cryptographic hash function is called SHA-256. If we use “Alice” as an input to SHA-256 and encode the result as hexadecimal, we get

3bc51062973c458d5a6f2d8d64a023246354ad7e064b1e4e009ec8a0699a304

This long, seemingly random sequence of hexadecimal digits is known as a “hash”.

You can verify this with python-3:

hashlib.sha256("Alice".encode("ASCII")).hexdigest()

To calculate a hash, a computer must do a little work. In fact, calculating a specific hash will always take the same number of computer operations. Theoretically, no shortcuts exist to compute the result of a viable cryptographic hash function (finding shortcuts is an active area of research in cryptography).

Proof of Work

We can make the computer do a little more work if we require that the hash start with a specific sequence of digits. Let’s use “0” as an example. To fulfill this requirement, the computer must be allowed to add to the input data. We’ll allow the prepending a number to the word “Alice”. This number is called a “nonce”.

In python-3, prepending a number (represented as a string) looks like this:

print(hashlib.sha256("1Alice".encode("ASCII")).hexdigest())

Prepending “1” didn’t work, however, because the result is:

96c15ebcee6fe1713e5a6d9141bccf3db3c318f4023415f9cff5848f6f00f4db

What nonce will work? To find out, we can write a python-3 program that searches for the appropriate number to make the hash start with 0:

i = 0
h = "" while not h.startswith("0"):
i = i + 1
h = hashlib.sha256((str(i) + "Alice").encode("ASCII")).hexdigest()
print i

If you run this program, then you will find that it prints out “5”. The result can be verified like this:

print(hashlib.sha256("5Alice".encode("ASCII")).hexdigest())

This yields the following hash, which starts with “0”.

09fe9461e9b586cf758a49291928dcdad5e268b4bd3ea138fd64c8d5bf4f7e21

Here, it took five tries to find a hash satisfying the requirement that the first hexadecimal digit is zero. Because no direct relationship exists between the inputs (“Alice”, “1Alice”, “5Alice”) and the hashes, the only viable procedure to find a nonce that satisfies the leading zero requirement is to try nonces until one works.

Intuitively, the more computing power that works on this problem, the faster it can be solved. For example, if one had a computer that could run five threads at once, it would find the appropriate nonce in the same amount of time as a single thread would try one nonce. This approach is called “parallel computing”. It is important to consider the possibility for parallel computing when designing blockchain protocols, such as feeless transactions. Note that even though the parallel (a.k.a “multithreaded”) approach found the nonce (“5”), faster than the single-thread approach, the same amount of work was done in both cases. The multithreaded approach just did that work faster, but not any more efficiently.

Verifying Proof of Work

What exactly is the proof? The “proof” in “proof-of-work” is simply the nonce.

For a given hashing algorithm (e.g. SHA-256) all someone needs to prove they did the work is to supply the nonce, given that the rest of the input is known. Here we all know that we want to find a satisfactory hash for “Alice”, where satisfactory means the first digit is “0”.

It is important that finding the nonce is hard but verifying it is easy. In this case, it was 5 times easier to verify the nonce than to find it. The ease of verifying versus finding a proof-of-work nonce improves as the constraints on the hash are increased. For example, what if we stipulated we wanted two leading zeros in the hash? It would be, on average, about 16 times harder than finding a hash with one leading zero. What if we stipulated we wanted three leading zeros? That’s about 16 times harder than two leading zeros, and so on.

Just to get an idea, let’s check out the most recent Bitcoin block hash as of the time of writing:

000000000000000000036baac69689e621f9780b3b4585ce4f0e371880f0e914

That’s 19 leading zeros, in case you get lost trying to count them. On average it takes about 75,557,863,725,914,323,419,136 tries to find a satisfactory nonce for a Bitcoin proof-of-work block with a requirement of at least 19 leading zeros. Now we know why Bitcoin is considered an energy hog. That’s a lot of work to earn a 6.25 BTC block reward.

But verifying the proof that a miner did all that work only takes one try, because we already know the nonce that produces a hash with 19 leading zeros.

Proof of Work Inputs

One question is what data are miners combining with the nonce to produce the block hash? The answer is simply the block data, which is all of the transactions bundled into a block. In fact, once the nonce is found, it is part of the block, because it was added to the block when calculating the hashes.

Fighting Transaction Spam with Proof of Work

Now that we understand the basic concepts of “mining” a proof-of-work, we can see how these concepts are applied to fighting spam.

Let’s imagine a transaction where Alice sends 10 XST to Bob. In Stealth’s ledger model (called a UTXO ledger), Alice signs a note (called an “input” in blockchain parlance), and then writes a new note (an “output”) for the amount to send to Bob (10 XST) and any change that Alice might get back, minus fees. Let’s imagine Alice has a note of 100 XST (which she signs), sent to her previously, she sends 10 XST to Bob, and the fee is 1 XST:

100 XST input -> 10 XST output (Bob) + 89 XST output (Change back to Alice)

The outputs add up to 99 XST, so the missing 1 XST is “burnt” as fees.

Don’t worry, real XST fees are not 1 XST per transaction. At the moment they are 0.01 XST, or about $0.0025, as of time of writing. I simply use 1 XST here to make the math easier to follow.

From here, we’ll take this transaction as an example. But first, let’s get rid of that pesky fee:

100 XST input -> 10 XST output (Bob) + 90 XST output (Change back to Alice)

Now the fee is 0 XST because the inputs (100 XST) add up to the outputs (10 XST + 90 XST). Much better.

But to this transaction we need to add a proof-of-work, which from here on I will call “feework”. From the discussion so far, it might now be obvious how to construct the feework: take the transaction data and a nonce, calculate the hash. If it meets the criterion, then add that nonce to the transaction data and submit the transaction as feeless. If it doesn’t meet the criterion, try another nonce.

— — — — — — —

Stealth Feework

The Stealth feework mechanism is very similar to this description, but with a couple of important additions: (1) include the number of a recent block (a.k.a. “block height”) and (2) include a number representing the difficulty of feework calculation. This information is rolled into the hash. I’ll explain the importance of both the height and the difficulty.

Feework Memory Hardness

Imagine what happens when there is a lot of demand for Stealth blockchain space, like Ethereum and Bitcoin are experiencing right now (as evidenced by the high fees). A feeless mechanism needs some way to prioritize transactions. The way to do this is by how difficult it was to find the proof.

As we saw above, difficulty can be increased by requiring more leading zeros. If a user submits feework that results in more leading zeros in the hash, then the user likely did more work mining the feework proof. This is how Bitcoin does PoW mining, and how Nano does its feeless transactions.

Stealth, in contrast, doesn’t use this type of difficulty adjustment. Instead, the limit (how many leading zeros) is always fixed, but the memory requirement of the hashing function is adjusted. For this type of adjustment to be possible, Stealth uses what is known as a “memory hard hash function”. The specific hash function used by Stealth is called Argon2d.

Briefly, a specific memory hard hash function requires a certain amount of memory no matter what. The amount of memory can be changed to create a different hash function with the same basic properties. If the memory requirement is changed, then the result of the hash function changes. Also, if the memory requirement increases, the difficulty of calculating the hash also increases.

To distinguish the type of difficulty that adjusts the number of zeros from the type of difficulty that adjusts the memory requirement, I use the term “memory hardness”. In other words, Stealth feeless transactions use dynamic memory hardness to prioritize inclusion in the blockchain, much in the same way Ethereum uses the amount of fees to prioritize inclusion in its blockchain.

For Stealth, the critical property of the Argon2d hashing function is that the memory required to calculate the hash cannot be efficiently substituted by parallel computing. Also, Stealth feeless transaction hardness increases as transactions get bigger and blocks get fuller. For transactions smaller than 1 KB, being added to a completely empty block, the memory requirement is 256 KB. The memory requirement can go up to about 4.5 MB, for a large transaction going into a very full block.

Why use dynamic memory hardness instead of simply adjusting the number of leading zeros? The reason is that as memory hardness increases, the parallel computing advantages enjoyed by GPU (graphical processing unit) miners rapidly decrease. This means that, if someone wanted to spam the Stealth blockchain using GPU mined feeless transactions, they would make the job disproportionally tougher for themselves, while desktop users would feel only slightly increased inconvenience.

Feeless Transaction Mempool Attacks

To prevent an attacker from filling blocks with feeless transactions, the last ¼ of each block is reserved for money fee transactions, so that there is always a way to send a transaction, even when the chain is under feeless spam attack. The fact that any spam attack is rendered practically useless simply by the design of the protocol should be a significant deterrent to such attacks.

But reserving ¼ of a block does not prevent a so-called “mempool exhaustion attack”, where feeless transactions build up in the pool of transactions that have not yet gone into a block. This pool is called the “memory pool”, or “mempool” for short.

Imagine that someone wanted to mount a multi-pronged attack on the Stealth blockchain, using an array of GPU miners to create feeless transactions. In principle, they could first fill blocks to ¾ full, then flood the mempool with feeless transactions that have insufficient hardness to get into nearly full blocks. These transactions would build up in the mempool awaiting inclusion and preempting legitimate transactions — unless there was some mechanism by which the oldest feeless transactions were periodically cleared.

Stealth transactions can’t be cleared by a timestamp because they have none. Also, timestamps can be forged, making checks specifically for timestamps inherently fragile. However, blocks do have timestamps. In fact they have two different types of timestamps. The first type is what we typically think of as a timestamp: it’s just the time, expressed as the number of seconds since 00:00:00 AM January 1, 1970.

The second type of timestamp is the block height. In Stealth, blocks are required to be temporally ordered, with lower numbered blocks preceding higher numbered blocks in time. For timestamps, Stealth feeless transactions include a block hash (not height) in the data that a user hashes to find the feework proof.

In case that wasn’t clear: instead of the height, the hash of the block at that height is prepended to the transaction data when mining the feework proof. This hash not only serves as a reference to a timestamp (the block’s timestamp), but also implicitly identifies a specific chain. Identifying a specific chain limits many attacks that could exploit healthy block reorganizations that form the heart of Stealth’s network stability.

Including the block height, rather than a time, has an additional advantage that the time of the feework is verifiable. Because the block is necessarily integrated into the blockchain, the feework must come after that block, and the feework’s expiration is guaranteed. Once a feeless transaction expires, it is automatically cleared from the mempool.

This system dramatically increases the resources required to launch a successful spam attack on the Stealth blockchain.

Stealth Feeless Transaction Structure

A Stealth feeless transaction has the following structure

1. Inputs
   a. Input 1
   b. Input 2
   c. …
2. Outputs
   a. Output 1
   b. Output 2
   c. …
3. Feework
   a. Block Height
   b. Memory Hardness
   c. Nonce (also called “work”, or, more colloquially herein, “proof”)

I should mention that the feework only requires 19 additional bytes and is technically an output itself, though it is not treated as one in the traditional sense.

For completeness, here’s the feework of the very first successful feeless transaction on the Stealth testnet:

"value" : 0.00000000,
"n" : 2,
"scriptPubKey" : {
"asm" : "003d0a3400000100b2184a6951819ff2 OP_FEEWORK",
"hex" : "10003d0a3400000100b2184a6951819ff2d1",
"type" : "feework",
"height" : 4000308,
"block_hash" : "593a3d44c4f4606ebecf0a6d2ea6ea67a73d3a845bf499510f11ef176cdd877c",
"mcost" : 256,
"bytes" : 218,
"limit_hex" : "0006ffffffffffff",
"limit_denary" : 1970324836974591,
"work_hex" : "b2184a6951819ff2",
"work_denary" : 12833088954391699442,
"hash_hex" : "00055199b36a0ffc",
"hash_denary" : 1497095465471996
}

The transaction ID is:

13802d181ed03b88e6eebccf6538c0985c6447261fb2885172c3d15135edb9e9

— — — — — — —

The Stealth Team

— — — — — — —

Website / Telegram / Slack / Medium / Twitter / Reddit