Lucky transactions (51% attack mitigation)

[tevador]

This is another proposal to bolster chain security against 51% attacks. I'm not very convinced that this should be implemented, but I think it can be discussed as an alternative to the finality layer proposal.

A finality layer marks blocks as finalized. Such blocks can never be replaced, they are cemented in the chain forever. It's the ultimate protection from 51% attacks.

However, this comes at a cost. Finality layers must be Byzantine fault tolerant (BFT), so they need a complex P2P protocol. An attacker controlling at least 1/3 of the stake can stall the finality layer or cause a permanent chain split (i.e. two parts of the network will finalize different blocks).

The following table shows the properties of some of the proposed soft-forking mitigation strategies:

Strategy	stops 51% attack	stops selfish mining	can stall/split	impl. complexity	decentralized
DNS checkpoints	Yes	No*	Yes	Low	No
PoS finality layer	Yes	No*	Yes	High	Yes
Publish or Perish	No	Yes	No	Medium	Yes
Lucky transactions	Yes**	No*	No	Medium	Yes

* Cannot stop reorgs of depth 1.

** With assumptions (see the Security section below).

Lucky transactions

Intuitively, given two alternative chains, the "correct" chain should be the one where the majority of the economic value takes place.

However, "economic value" cannot be defined simply as the transaction volume because miners can create their own fake transactions at virtually no cost.

Instead, we define "economic value" in terms of "lucky transactions", which cannot be easily spoofed.

Assuming H(...) is a hash function and || is the concatenation operator, a transaction spending an output created at height input_height with a key image key_image and amount amount is "lucky" if:

H(checkpoint_hash || key_image) < target * amount * (checkpoint_height - input_height)

(Eqn. 1)

Here checkpoint_hash is the hash of a recent block with a height of checkpoint_height and target is a dynamically adjusted value so that the blockchain contains on average 1 lucky transaction per block.

The above formula basically says that a transaction has a higher chance of being "lucky" if it spends an old output or an output with a high amount.

The minimum relay fee doesn't apply to lucky transactions.

Verification

If a transaction is lucky, the sender includes a special field in tx_extra that contains:

1. The index of the lucky input.
2. checkpoint_hash and checkpoint_height
3. amount and blinding_factor of the input pseudo-commitment.

This is only about 80 bytes of data.

Before selecting the decoys, the sender calculates:

anchor_height = checkpoint_height - H(checkpoint_hash || key_image) / (target * amount)

(Eqn. 2)

Ring members are selected from heights below anchor_height. Note that by Eqn. 1, anchor_height > input_height, so the ring can always include the lucky input.

To verify that a transaction included in the blockchain at height height is lucky, any chain observer does the following:

1. Check that height - checkpoint_height <= K, where K is a parameter (the maximum checkpoint age).
2. Check that the checkpoint_hash matches the block at height checkpoint_height.
3. Check that H(checkpoint_hash || key_image) < target * amount * (checkpoint_height - newest_ring_member_height).
4. Check that input_commitment = amount * H + blinding_factor * G.

Fork choice

A new chain weight formula is used for the fork choice rule that replaces the "longest chain" rule. A block at height height has the following weight:

block_weight = (included_lucky_diff + current_lucky_diff / M) * pow_diff

(Eqn. 3)

Here included_lucky_diff is the sum of the difficulties of the valid lucky transactions included in the block, current_lucky_diff is the difficulty of a lucky transaction at height (calculated using the difficulty adjustment formula), pow_diff is the standard Proof of Work difficulty at height and M is a parameter.

Eqn. 3 basically says that a chain with lucky transactions has approximately (M+1)-times higher weight than the same chain without lucky transactions.

The canonical chain is the chain with the highest total weight.

Incentives

Miners have an incentive to include lucky transactions because they increase the weight of their blocks.

Users have an incentive to submit lucky transactions because they can be sent with a zero fee, they take priority over all non-lucky transactions and reduce the chance of their transaction being invalidated by a fork.

Lucky transactions can be "mined" by checking Eqn. 1 for each of the user's unspent outputs everytime a new block is published. However, there is no reward for that. It can be done altrustically to support the chain, as the cost is nearly zero (just a couple of hashes). Wallets could have an option to mine lucky transactions in the background.

Privacy

A lucky transaction leaks the amount spent in one of the inputs and also leaks the minimum age of the input. However, the identity of the spent input is still protected with a ring signature.

Security

With the recommended parameters of K = 3 and M = 3, lucky transactions can commit to one of the previous 3 blocks and a block without lucky transactions has about 1/4 of the weight of a block with 1 lucky transaction.

The new fork choice rule makes 51% attacks harder under the assumption that the majority of lucky transactions come from honest users.

The table below lists the required combinations of lucky transactions and hashrate as a percentage of the total to attack the chain. An attacker without any lucky transactions would need >80% of the network hashrate to overtake the honest chain (this applies to relatively short reorgs where the difficulty adjustment can be ignored).

Lucky transactions	Hashrate needed
0%	>80%
33%	>60%
50%	>50%
67%	>40%
100%	>20%

[kayabaNerve]

At ~3 TPS, isn't this proposing that every second, we get 3 * hashes_per_transaction in a secondary PoW algorithm? Wouldn't that be trivial for a hostile actor to independently replicate? If a user was willing to perform a large amount of hashes, wouldn't it better for them to directly contribute to Monero's PoW?

[tevador]

No.

By Eqn. 1, you can see that for each unspent output, you need to calculate 1 hash per block. Let's assume there are 12 million unspent outputs and all Monero holders are actively mining lucky transactions. That would amount to 100 000 hashes per second. If we assume that H(...) is RandomX (in practice, there is no need to use a slow hash function), that's 100 kH/s compared to 4 GH/s that miners do for PoW. That's a completely negligible number of hashes that would have no impact on PoW security.

[kayabaNerve]

That was partially my point though. A malicious adversary can easily organize an additional 100 KHs. How is crowdsourcing PoW in this manner superior to crowdsourcing via p2pool? Why is one insignificant and one significant?

[tevador]

Of course, an adversary can easily calculate 100 000 hashes per second, but that's not very useful by itself.

1. You cannot calculate hashes on behalf of other users because you don't know their key images.
2. Even if you somehow knew everyone's key images, you still cannot submit any lucky transactions, unless you also have access to everyone's spend keys.

Basically, an adversary cannot outperform the honest majority of users unless he owns more XMR than all active honest users combined.

[kayabaNerve]

Premising on share of outputs, especially when we prior had a rather notable spam attack, seems problematic but I do hear the distinction.

[tevador]

Spamming outputs also won't help much.

Someone who owns 1 million outputs of 0.001 XMR each has about the same chance of finding a lucky transaction as someone with 1 output of 1000 XMR (assuming similar age of outputs).

[kayabaNerve]

Sorry, I'm up quite late and missed the amount incorporation. I'll think on it again tomorrow. Thank you for your patience.

[SChernykh]

Realistically, only the pool's hot wallets would participate in the "lucky transaction" mining. People aren't going to risk their cold wallets for this. As I understand, you need to run an active hot wallet for this, with large amounts in it?

[SChernykh]

target is a dynamically adjusted value so that the blockchain contains on average 1 lucky transaction per block.

How would you dynamically adjust it, if every mined lucky transaction changes the chances of that specific miner because their input height will update? Dynamic adjustment algorithm assumes there is a rather stable "mining power", but here it reduces with every lucky tx mined.

P.S. On the other hand, it increases with every block mined, so these two factors might cancel each other out. It will need real-life testing.

[SChernykh]

block_weight = (included_lucky_diff + current_lucky_diff / M) * pow_diff

Do I get it right, blocks without lucky transactions have no weight at all? Is it a design choice?

[lnchan]

How should the amount in the transaction scale compared to checkpoint_height - input_height? Having enough Monero seems to give a lot of power compared to having old coins, which show a commitment to using the network.

I also presume the amount unit isn't piconeros.

Also, is the amount variable sufficiently useful to the interest of strengthening a specific chain? I'm not quite certain it helps to serves the purpose well.

EDIT: Nevermind, with the case of spam attacks, this is relevant.

[tevador]

As I understand, you need to run an active hot wallet for this, with large amounts in it?

Yes, for "mining", the wallet must be open and able to spend. However, the idea is that lucky transactions will be submitted mostly opportunistically when you are sending funds anyways.

How would you dynamically adjust it, if every mined lucky transaction changes the chances of that specific miner because their input height will update? Dynamic adjustment algorithm assumes there is a rather stable "mining power", but here it reduces with every lucky tx mined.

The chance decreases for that specific "miner", but increases for everyone else as more blocks are added. I think this could be analyzed on a transparent chain like Bitcoin, where you can see how many "coin-blocks" are spent per day on average (i.e. for each spent input, you multiply the amount and the age). It's likely that this will be a relatively stable number.

Do I get it right, blocks without lucky transactions have no weight at all? Is it a design choice?

No. A block with no lucky transactions has block_weight = current_lucky_diff / M * pow_diff, where current_lucky_diff is the difficulty a lucky transaction would need to meet. Maybe the notation is a bit confusing.

Assuming a steady state where difficulty doesn't change, a block with no lucky transactions will have 1/(M+1) of the average weight, or 25% of the average weight if M=3.

How should the amount in the transaction scale compared to checkpoint_height - input_height? Having enough Monero seems to give a lot of power compared to having old coins, which show a commitment to using the network.

I also presume the amount unit isn't piconeros.

Since they are multiplied together, there is no need for scaling. amount can be in arbitrary units. If we wanted to disqualify dust transactions, we could use millineros.

[SChernykh]

transactions will be submitted mostly opportunistically when you are sending funds anyways.

So all end user wallets must support this for it to be efficient. Especially exchange and pool wallets because they move larger amounts regularly.