Efficient solution to verify kernel uniqueness + better absolute timelocks

If this is the retained choice with respect to the replay attacks (who knows! maybe we will respect users) here is a proposed solution.

PROTOCOL:

  1. Two users want to make a transaction.
  2. They look at the current block height of the Grin blockchain, represented by the integer signature_block_height.
  3. They sign the transaction with signature_block_height in the signature’s message of the kernel excess.
  4. Similarly to kernel offset, they join signature_block_height with their transaction (of course, unlike kernel offset, signature_block_height is not to be aggregated).
  5. Transaction enjoys some time in the mempool up to inclusion_block_height, where inclusion_block_height is the block at which the miner includes the kernel in the blockchain (precisely, he includes it in the kernel MMR).

Instead of having its leaves on (kernel), the kernel MMR has its leaves on (kernel, relative_height). Kernels are still comprised of excess and signature only. signature_block_height is not included in Kernel and is not onchain data (but just mempool data).


  1. Miner includes the kernel into the kernel MMR through the leaf (Kernel, relative_height) where relative_height = inclusion_block_height - signature_block_height.
  2. Finished.

Protocol rules:
(i) Grin protocol rules has to set a maximum value allowed for relative_height, for example call it relative_max.
(ii) kernel verification rule: Each couple (kernel, relative_height) corresponds to a unique inclusion_block_height (visible by verifiers) and is valid (protocol rule) if and only if the signature for the kernel excess is correct for the message inclusion_block_height - relative_height.

This protocol allows:
(a) Verifiers to verify signatures easily since they directly derive the message of the signature in the leaf of Kernel MMR:
message = signature_block_height = inclusion_block_height - relative_height.
(b) Verifiers to verify efficiently kernel uniqueness on the whole blockchain without the need to keep all the history in memory but a very short history instead; all the kernels belonging to blocks older than current_block_height - relative_max can be forever removed of uniqueness check, where current_block_height is the current block height (most recent block on the blockchain).

The method doesn’t change the current composition of a kernel, and stores relative heights rather than absolute heights. Scalability and protocol elegance blows are essentially negligible.

More on scalability of the construction, absolute time locks as side effect, and security are discussed in posts below.

4 Likes

Nice, no need to store kernels forever. Keeping them in the mempool is a elegant and lightweight solution. Just thinking, would it be possible for an attacker to flood the mempool or can this be avoided?

0 BIT ADDED: (most of the time)

99% of the time: No need to add any onchain data (percentage decreases as blocks become full)

Most of the time:
inclusion_block_height = signature_block_height ,
especially when blocks are not full.
In this situation miner doesn’t even need to add a single bit on the blockchain compared to today: By making relative_height optional and default to relative_height = 0 when void.

1 Like

It turns out that there is some useful side effects that we can enjoy from the design of the proposal.

ABSOLUTE TIMELOCKS:

The integer signature_block_height can be in fact set to potentially any integer of the choice of the two parties building the transaction; given an arbitrary choice of signature_block_height, the transaction can only make it to a block contained in the interval (signature_block_height, signature_block_height + relative_max), and never to blocks outside this range. In other words, inclusion_block_height can only be a block inside this interval, and never outside (due to consensus rules (i) and (ii), in OP).

That is, in the protocol described in OP, the two parties involved in the transaction could together agree to set signature_block_height equal to a block height in the past (not equal to a block older than current_block_height - relative_max, otherwise the transaction will not make it to the blockchain) as much as to a block height in the (potentially distant) future.

The former case allows to narrow down the window/range of the upcoming blocks wherein the transaction can land, while the latter case falls back to an absolute timelock transaction design, more private (kernels indistinguishable on chain), cleaner (no need of a separate kernel type for absolute timelocks) and also more scalable (we do not store any block heights on chain) than the solution for absolute timelocks proposed in NRD RFC(1) (Note that NRD content is essentially for relative timelocks).

This opens the doors for a minimalist and novel way of designing scriptless timelock transactions and related applications, by using the exact same construction described in OP useful to verify kernel uniqueness.

(1) NRD proposal:

2 Likes

Still wondering about whether it is possible to spam the mempool with kernels of transactions that will never be actually be used to complete a transaction?
If so, some locking of funds on the blockchain should be made mandatory, e.g. locking a certain amount until the transaction window for the kernel passes after which the funds will be returned. Or is that already the case since we are talking about NRD kernels in which case there always is a smart contract with some locked funds.

Not more or less spamming than current Grin. Exactly same.

SECURITY:

Despite your question doesn’t really say it, you are close to a real point that has to be resolved: what happens if the transaction doesn’t make it to the blockchain on a block before or equal to the block height signature_block_height + relative_max?
Then it means that the transaction will never make it to the blockchain.
Is that a problem? Can we for example ”play” the kernel? Fortunately the answer is no, because for a transaction with a certain signature_block_height = n to be published (strictly) after the block = signature_block_height + relative_max, the message signed in the signature cannot be equal to n, but needs to be an integer strictly greater than n. Hence the kernel that never made it to the blockchain cannot be utilized in order to perform a “play“ attack (the term was recently coined by Tromp).

On a separate note, transaction not making it to blockchain is an event extremely unlikely with a sufficiently large relative_max (and it doesn’t need to be that large).

So, we are good :+1:

2 Likes

My recommendation is to take a decision for kernel replay fix as soon as possible to start working on it asap by making it a priority and make sure we have a fully secure and robust grin for HF4.

Some work that needs to be done if consensus change is chosen:

  • proper algorithm of uniqueness check. What is the data we keep in the uniqueness list, is it the signature, is it the excess, do we really need to keep 32 bytes for it? Or can we do a truncation of this data (taking the first 16 bytes only for example) and have an even more scalable algorithm to still verify the uniqueness?
  • what is the value of relative_max. We can even do several possibilities of this value by actually assigning multiple kernel types. there are several small variations possible. Is it useful?
  • How fees calculation is impacted by this? by setting signature_block_height in the past the transaction is forced to spend less time in the mempool.
  • Do we change NRD implementation given we do not need a specific kernel type for absolute time lock anymore and that wr have a better solution for this?
  • Can this construction be utilized to enhance NRD for payment channels? (I have no idea for this).
  • All the testing work for kernel uniqueness.
  • Finally, we need to make sure that network propagation and mempool tx management is good to prevent the “play” attacks (maybe all is good already).

Important note:
As noted in the previous post about security “play” attacks are naturally narrowed in time with this uniqueness check proposal (cannot happen after relative_max blocks), which is a good thing for grin security. The smaller the value of relative_max is set, the less of a concept actually “play” attacks is.

Given that last HF is in 6 months and the piece of work that is needed to fix replays (and that everyone will be very busy to prepare for it as the HF becomes closer and closer), we, in my opinion, cannot afford to lose time to fix the replays problem.

Of course, choice can also be taken to not use kernel uniqueness and/or to fix the replays later, but it makes a lot of sense to have it ready for last planned Hardfork.

3 Likes

Thanks @Kurt for writing this down.

I think this is a good overview of how we could enforce kernel uniqueness within a limited window of relative time.

The downside is this introduces transaction expiration as transactions are now only valid within this window. I believe this is something we are hoping to avoid.

The obvious alternative is to simply enforce uniqueness across kernels globally but this is not workable in practice as this would require all nodes to maintain a full index of all historical kernels.

Neither of these kernel uniqueness approaches are desirable.

To solve “replay attack” using kernel uniqueness we need to find a way to enforce uniqueness that does not also introduce additional limitations, namely transaction expiration.

I disagree. Window for transaction validity is not an absurd concept. You can make two-week window if you like.

2 Likes

Nobody said it was an absurd concept. But it is undesirable. We aim to maintain the rule that a “transaction (with spendable outputs) once valid will not become invalid”.

It is not the size of the window that is undesirable here, but the existence of the window itself.

I understand your disagreement here and I understand your desire to solve the “replay attack” at the consensus level like this with kernel uniqueness.
But my feeling here is the downsides outweigh the benefits and this is not the solution.

Then, happy sweeping for everyone

From a UX point of view having funds indeffintely in limbo is absurd. In 99% of the cases this would be a mistake by the user and not done on purpose.
How about simply warning the users about transactions passed the 2 week limit, asking them if they want to reclaim, sweep these specific funds. Alternatively I think having a ‘safe wallet restore function’, migrating all UTX0’s is desirable.

Why though? It is intellectually sound but doesnt seem practically important at all.

Just one of many downsides of your preference is ruining the UX of running the same seed on multiple devices, which MANY users are going to do. I still have yet to hear downsides to unique kernels that are practical instead of intellectual (other than it requires a consensus change) or could not be easily mediated.

If a transaction doesn’t confirm in a week or so, I think most of us would rather it expire. Otherwise it’s like writing a check and not knowing when it will be cashed. Having inputs stuck in limbo for months is strange.

3 Likes

Second layer transactions require to be valid offline for very long time, possibly years. Grin is currently not building L2 solutions, but this may make it much harder to build something like Lightning Network on Grin later.

This can be solved by forcing Lightning channel owners to be online.
The answer given below for Bitcoin LN channels will also hold for Grin as far as I can see:

"Based on your comments, I think one fundamental issue you’re missing is that to pay with LN, the other party has to be online at the time. There’s no question of “what happens if Bob is offline” because if he is offline, no payment is possible.

The other thing you need to know - especially if you meant that Bob is offline after the payment was completed - is that LN is complicated. Many transactions are involved in each payment. To get the full details you will have to read the whitepaper - https://lightning.network/lightning-network-paper.pdf.

But a main point is that as part of the process of accepting an LN payment, Bob gets a penalty transaction. If Alice ever tries to broadcast a tx representing an old channel state, thus reverting an earlier payment, Bob can broadcast his penalty tx, and take all the money in the channel (even the part that never belonged to him).

Because of this, it is recommended that Bob either stays online constantly, or delegates watchtowers to this job (which does not give the watchtowers access to Bob’s money).
"

“Constantly” is certainly not needed. If you set the revocation window to one week for example, then coming briefly online just once a week would suffice for Bob.

1 Like

Andrew Poelstra is saying in this video below that things like my scheme of unique kernel verification can make LN more secure.

By disabling, due to transactions expiring, the ability to publish on the blockchain ancient (and off chain) LN transactions that would be more financially advantageous to me.

Starts at 1:05:30, and the crux at 1:08:00.
Interesting discussion after on how tricky the issue is for Bitcoin, when they also try to solve the scalability issue.

The windows in my scheme could likely make this problem obsolete.

Even without that, I would love that people like Antioch or Tromp tells us seriously why breaking transaction monoticity is worst than breaking UX and security. It honestly seems like pure trolling to me and it is time consuming. Time to go back to Earth at some point for grin.

@tromp has a good explanation of one approach (NRD kernel based) for payment channel revocation here - https://lists.launchpad.net/mimblewimble/msg00636.html

Andrew is talking about how they approach it today in Bitcoin/LN with penalty txs. The approach in Grin is a little different as we can cannot put locktimes on outputs themselves, only on the kernels.

The window between two NRD kernels provides the relative locktime necessary for this to work.
Within the window the other tx can be used to revoke the channel close. Once the lock expires outside this window the tx containing the NRD kernel can be broadcast to complete the channel close.


We can disagree on approaches. Maybe take a step back if debate around your proposal feels like trolling.

:-1: That comment adds nothing to the conversation.

Thanks for the technical explanations.

For everyone that has not followed all the tech details of this long debate, to understand a bit, Tromp and Antioch are OK with a sweeping output party.
Maybe it is OK to sweep outputs, if we think about it, not speaking about the scalability issue since each tx leaves 100 bytes of data on the blockchain for ever.

The issue is that Replay attacks are not prevented, and it is not possible after a traditional restore to know which outputs are at risk.

So the rational behavior is to sweep mostly everything.
But not only that, in fact the rational behavior is to sweep all outputs ASAP.
We are talking about people’s money here. We are talking about the fact that each user will have the rational behavior to wish having the more money as possible when you restore. There are countless real life examples of people not taking track of their finance, and here you want to put the anxiety (maybe not to you because you are very strong emotionally maybe and have an academic and clinical definition of ownership in mimblewimble) of sweeping the outputs asap, to try having more money as possible before an attacker maybe spend your outputs ONE sec before you click on the “send” button on your wallet?

Why do you want to put this experience on users? Why? you will say, oh but the outputs at risk are maybe not really your money. but this is absurd to give this experience to people. This is like absurd. Most of the people will be super anxious to sweep asap, this is the rational behavior.
No coin today, absolutely no coin, gives this kind of horrible experience.

Grin is meant to be usable by everyone. Why put this weight on user because we break tx monoticity ?
Why ?
Is it a problem that you cannot put yourself in the shoes of people that may have a different emotional being than you? Is it the reason? Is it because you think this is not the true Mimblewimble?

Go open grin.mw and read what is written on it, for Satoshi’s sake.