Enforcing that all kernels are different at consensus level?

As we will see below, while the vulnerability may not have direct financial consequences for Grin users today, it is possible in Grin, under some circumstances, to replay a transaction by replicating an existing kernel on the blockchain and use inputs for a second transaction that the sender actually does not own.

This vulnerability only appears in the cases where some outputs are duplicated on the blockchain (which just means that one output is a strict copy of another output, in particular that Pedersen commitments are identical in the two outputs), which we will describe in the first instance of the vulnerability, or when a transaction with two identical outputs is able to be validated by verifiers.

If my understanding is correct, today Grin does not allow duplicate outputs so that the vulnerability can only happen if network participants do not validate correctly this rule, which is not trustlessly verifiable for new network participants since it cannot be checked for cut-through blocks where spent outputs are pruned and do not appear on the blockchain anymore.

Let’s describe the vulnerability in a bit more details.

1st instance of the vulnerability:

An attacker is able to replicate a transaction, transaction A, already posted on the blockchain previously by broadcasting a new transaction, transaction B, with the exact same inputs, outputs and kernel.

That would only effectively be able to be performed if all the inputs in Transaction A were actually in duplicate on the blockchain, but this is not something impossible to happen if a user, against the common wallets’ good practice, would actually create two same outputs, with in particular the same Pedersen commitments.
In this scenario, the attacker has successfully sent a transaction with inputs that they do not own, by broadcasting a kernel whose they do not actually know about the private key to the kernel excess, which is an instance of a rogue-key attack. (EDIT: not a rogue-key attack, but a replay attack. apologies for the mistake here)

Note that the attack is extremely unlikely to happen, as it would necessitate that a same user has fabricated two same outputs and that they actually spent only of them first, as opposed to those two outputs being spent together in a same transaction.

But the duplicate outputs need not necessarily to be built by its owner, as they can also be directly sent to them, as described below.

a second instance of the vulnerability:

This instance probably asks to introduce some notations. We introduce two transactions, tx1 with input P_in and output P_out, and tx2, with inputs P1_in and P2_in and outputs P1_out and P2_out, such as:

tx1: P_in = vH + rG; P_out = vH + X which makes for an excess of P_out - P_in = X - rG.
tx2: P1_in = P_out and P2_in = vH + r’G ; P1_out = P_out and P2_out = P_out
which makes for an excess of P1_out + P2_out - (P1_in + P2_in) = 2X - (X + r’G) = X - r’G = (x - rG) + (r - r’)G.

As we can see by comparing the two excesses, tx2 can be broadcast using the same kernel as tx1 by just adjusting offset of tx1 by (r-r’).

The user that controls P_out may be really happy since they acquired in the operation twice the number of coins that they had originally in P_out, by actually receiving two times P_out through the second transaction.
The thing is that the second transaction can actually be sent by the sender of the first transaction. They would just have to copy and paste the kernel from the first transaction, together with the bulletproof for P_out, and they would manage to send tx2 successfully without the owner of P_out specifically asked for it.

One of the problems of this vulnerability is not necessarily the ability to lose or win new money, but it is the fact that an owner of an UTXO actually sees their UTXO being spent by a third party without their authorization, which breaks the concept of ownership of UTXO as defined in Bitcoin.

The operation could also leak private information about users and have unfortunate or dramatic consequences if some information can be utilized against them.

How we could fix the vulnerability:

For fixing the vulnerability, we could think of enforcing at consensus layer that no two same UTXOs are on the blockchain and both instances of the vulnerability would indeed not happen if verifiers do properrly their verification jobs.
But this verification cannot be performed for cut-through block by participants that newly join the network (due to cut-through) so it is not really enforcable at consensus level as new network participants need to trust previous network participants.

The most natural fix is in fact to not allow duplicate kernels on the blockchain since for those attacks, the attacker always needs to replicate a kernel that pre-exists on the blockchain by copying and pasting this kernel for their malicious transaction.

This fix would fully fix the problem and allow for any grin user to have (trustlessly) full ownership and control of their UTXOs. It would also allow all new verifiers to be trustlessly convinced of that.

Algorithms that verify that no two same elements are within a list may not be efficient to run on a very large list, such a list of grin kernels (at least hopefully in the future :)). So, for enforcing that all kernels are different on the blockchain, we could think of how we could make the task easier for full nodes.

One solution would be probably to include a new data in the message of all the kernels’ signatures, like for example the block height, so that participant are able to verify that no two same kernels are on the blockchain by just verifying this on separate and small batches of kernels, making the verification probably a lot more efficient at several levels.

It would be good to think rather sooner than later about this topic to maybe think what we could include in the kernel’s signature to facilitate verification of this consensus rule (if it were to be included in grin’s consensus rules) for future grin verifiers.

By enforcing that no two same kernels are on the blockchain grin would be able to objectively claim that it has the same security and trust models to those of bitcoin: Each new participant that newly joins the network can be trustlessly convinced that proper ownership of coins have been achieved in grin since genesis block.

On top of that, it would ensure to grin users that their outputs are not used by other people without they have asked for it.

Overall, it looks very beneficial to Grin to add this consensus rule on the kernels.

5 Likes

Grin does not allow simultaneous duplicate utxo.
You cannot say that cut-through vulnerabilities could occur before the 1-week horizon, since the security model requires only a valid UTXO set and kernel history at the horizon.

This is illegal since it has an output P1_out equal to an input P1_in.

In Grin, after I spend an output P that I once received from Alice, Alice can publish another tx that recreates output P without my knowledge. Do I “own” this? That’s questionable, since I didn’t agree to receive it and would never recreate this old output myself. (It’s true that if I run a wallet restore, my wallet would find this recreated output and claim it as owned, not realizing that I spent its duplicate earlier.)

There seems to be little point in this replay attack by Alice, except for being able to claim “Haha! I was able to replay your tx by paying you twice”. Even if you consider that a vulnerability, then surely it’s a pretty benign one.

I would hesitate to complicate the consensus rules of Grin to safeguard us against payment replay attacks. At least until I can see how such attacks would do any actual damage. And especially if the new consensus rules break the desirable property that a tx in the mempool remains valid as long as its inputs are unspent.

1 Like

“This is illegal since it has an output P1_out equal to an input P1_in.”

In Bitcoin you do not care that previous verifiers may have had a broken node with a broken code before you arrived in the network. You do not need to trust that your predecessors have done proper live verifications of transactions.

You can be convinced of proper ownership of coins since genesis block when you download the blockchain by simply verifying the chain by yourself, checking the signatures one by one. And it will be true in 50 years.

Enforcing that no two same kernels are on the blockchain would achieve that exact same thing in Grin by making all replay attacks on kernel excess infeasible, while maintaining this unique ability of Mimblewimble to prune spent outputs.

1 Like

Perhaps in bitcoin it’s also possible to replay a signature script to respend a recreated output?!

Well, any construction that i am not aware of is possible. you know better than me. i am sure they made sure in those constructions (atomic swap, lightening ?) that non proper ownership of coins, against the desire of the owner of the utxo, has been perfectly achieved.

And i m sure this is the very same reason why blockstream has spent two years on schnorr multisig research to make sure that rogue key attacks can be achieved using their schemes

The correct term for these vulnerabilities is replay attack, and not rogue-key attack. Thank you Tromp for correcting me on keybase on this.

But it changes not the fact that UTXOs are moved against their owner’s will, and nobody likes the possibility and realization of things like that

I do not understand what Kurt writes about, but I know for sure that hackers can change the code of the grin wallet and compile it, so all the rules will become invalid again, the best option is to check everything during mining or make the miners do it.

But I’m sure you’ve taken all this into account.

The first vulnerability can be also achieved with two different outputs.

They would have same Pedersen commitments but two different bulletproofs for that same commitment (For a given commitment, one can build almost an infinity of valid bulletproofs, due to randomness intervening in bulletproof generation, similarly to Schnorr signature and their generation procedure).

The difference with Bitcoin, on a trust model standpoint, is that in Bitcoin you can download the chain by yourself and if all signatures validate correctly, you can be convinced that everyone had total control over the funds corresponding to their utxos.

In Grin, if you do not enforce different kernels and that in 10 years you download the blockchain and can notice that some old kernels are the same on the blockchain, then you will not be able to know if funds have been spent without the will of their owners (see the two vulnerabilities) or not (two same kernels can also be built honestly in two separate txs by honest users). You’ll be no longer sure that correct ownership of coins have been achieved from the first block to today, which makes for an objective difference of trust/ownership models between those of grin and bitcoin

the fix is just to enforce different kernels, and both models can be identical, which would be cool

1 Like

Can we find out the number of coins mined by time and how many coins are currently available?

This way we can be sure that there was no break-in.

Extra checks will not prevent us, because programmers often make mistakes and if we do not know the exact data, this vulnerability may be hidden

“ownership” and “no infllation” (no coins created out of the thin air) are two different things :slight_smile:

Proper balance (no inflation) can be verified trustlessly during your IBD, even if two kernels are the same.

on top of that you can also also be sure that for each individual tx, no coin was created. this is true in grin and btc, with two different blockchain designs

I was referring to double-spend :slightly_smiling_face:

double-spend is a separate question. there is no practical or theoretical difference between grin and bitcoin on that side, i think

Actually it’s not possible in bitcoin since it refers to inputs by the hash of (the full serialization of) a previous transaction together with an output index, and it’s impossible to recreate a transaction with the same hash, as David Burkett first pointed out on keybase.

2 Likes