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.
