# Eliminating finalize step revisited
**URL:** https://forum.grin.mw/t/eliminating-finalize-step-revisited/10627
**Category:** Research
**Created:** [July 10, 2023, 9:49pm UTC](https://forum.grin.mw/t/eliminating-finalize-step-revisited/10627 "2023-07-10T21:49:42Z")
**Posts on this page:** 20
**Page:** 2
### Author:  [@tevador](https://forum.grin.mw/u/tevador)
#### Post date: [July 13, 2023, 6:04pm UTC](https://forum.grin.mw/t/eliminating-finalize-step-revisited/10627/23 "2023-07-13T18:04:35Z")
Good question.
There are two ways to have a duplicate sending key:
1. Finding a hash collision.
2. Reusing the same tuple (P, v, n, ts, dc).
If Bob is a bit paranoid and wants to be safe from hash collisions, the only solution is to permanently store a list of all received sending keys. That’s obviously not compatible with restoring the wallet from the seed.
Protecting from the second attack is much easier. Bob just needs to make sure that at least one of the parameters must change. This can be done for example by validating that the timestamp value is not older than 24 hours and the same sending key has not been received in the last 24 hours. After restoring the wallet, not accepting new payments for 24 hours is sufficient to ensure uniqueness.
It should be noted that if both payments have the same value, Mallory cannot actually steal anything even if Bob accepts the duplicate payment. She can only swap one output for the other. If Bob is fine with this, he might choose to skip the uniqueness check altogether.
---
### Author:  [@vegycslol](https://forum.grin.mw/u/vegycslol)
#### Post date: [July 13, 2023, 6:20pm UTC](https://forum.grin.mw/t/eliminating-finalize-step-revisited/10627/24 "2023-07-13T18:20:39Z")
Thanks for a nicely written response.
> [@tevador](#):
>
> After restoring the wallet, not accepting new payments for 24 hours is sufficient to ensure uniqueness.
If Bob is using both desktop and mobile versions with the same seed then he must have shared “list” between devices right?
Also regarding payment proofs, what if Alice gives her tuple to Carol? If i understand correctly then with this version of payment proofs Carol can claim that she’s the one who paid Bob?
---
### Author:  [@tevador](https://forum.grin.mw/u/tevador)
#### Post date: [July 13, 2023, 7:54pm UTC](https://forum.grin.mw/t/eliminating-finalize-step-revisited/10627/25 "2023-07-13T19:54:32Z")
> [@vegycslol](#):
>
> If Bob is using both desktop and mobile versions with the same seed then he must have shared “list” between devices right?
Yes, but I think it should be possible to embed the sending key into the output range proof, so it can be accessed on both devices (unless the other device doesn’t come online before the output is pruned).
> [@vegycslol](#):
>
> Also regarding payment proofs, what if Alice gives her tuple to Carol? If i understand correctly then with this version of payment proofs Carol can claim that she’s the one who paid Bob?
This is not an unusual property. Many protocols have transferable payment proofs, e.g. Monero, but it always requires sharing a secret value (here the nonce `n`). But if the payment description said for example “Alice is buying some flowers from Bob”, then this proof would not be easy to transfer to Carol.
---
### Author:  [@vegycslol](https://forum.grin.mw/u/vegycslol)
#### Post date: [July 13, 2023, 8:08pm UTC](https://forum.grin.mw/t/eliminating-finalize-step-revisited/10627/26 "2023-07-13T20:08:18Z")
What if both Alice and Bob are evil, create a transaction with description “Carol is buying some guns from Bob” and then Bob provides the tuple and claims it was Carol who paid? I mean i wouldn’t count it as a valid evidence, but Carol would probably prefer if her signature had to be a part of her transaction in this case.
---
### Author:  [@tevador](https://forum.grin.mw/u/tevador)
#### Post date: [July 13, 2023, 8:43pm UTC](https://forum.grin.mw/t/eliminating-finalize-step-revisited/10627/27 "2023-07-13T20:43:14Z")
A signature can be included in the description field, which is for arbitrary data. But I don’t recommend it as it makes the payment undeniable for the sender. A plain text description accusing Carol would not be admissible in court, but a signature could likely be considered a hard proof against her. That’s one of the reasons why Monero has payment proofs that are completely detached from the sending wallet. You can’t get a subpoena to produce evidence that does not exist.
---
### Author:  [@vegycslol](https://forum.grin.mw/u/vegycslol)
#### Post date: [July 13, 2023, 9:23pm UTC](https://forum.grin.mw/t/eliminating-finalize-step-revisited/10627/28 "2023-07-13T21:23:04Z")
I see, don’t know how payment proofs work on other chains so it’s fun to hear that. I think the best payment proofs are the ones where the sender can undoubtedly prove that he’s the sender while receiver can only prove that someone paid to him (at least that’s my current view, it might change though if i invest more time in thinking about them). My first view was that both sender and receiver should have undeniable proofs containing the sender’s information, but that’s too problematic because if receiver is amazon they can share provable data and that’s not really a good thing.
---
### Author:  [@AceKaplin](https://forum.grin.mw/u/AceKaplin)
#### Post date: [July 14, 2023, 1:37am UTC](https://forum.grin.mw/t/eliminating-finalize-step-revisited/10627/29 "2023-07-14T01:37:50Z")
> [@tevador](#):
>
> You can’t get a subpoena to produce evidence that does not exist.
This is the million dollar message ✅
---
### Author:  [@AceKaplin](https://forum.grin.mw/u/AceKaplin)
#### Post date: [July 14, 2023, 4:37pm UTC](https://forum.grin.mw/t/eliminating-finalize-step-revisited/10627/30 "2023-07-14T16:37:21Z")
> [@vegycslol](#):
>
> I think the best payment proofs are the ones where the sender can undoubtedly prove that he’s the sender
You know this is an unattainable property, right? If Alice pays Bob, she can always share her private key with Charlie, and then Charlie can submit a convincing proof that he paid Bob.
Maybe Alice pays Bob for services. She pays Bob from a dummy account with no left over funds, and then shares the keys to this account with all of her friends, so that they can steal services from Bob. There is no cryptographic scheme that can undeniably prove who signed a message, because anyone can share their private keys at will.
Such a payment proof can only hurt Alice in the event an adversary coerces her to reveal evidence of her participation in a transaction. And Bob can never assume her proof is undeniable anyways. So what good is it? Its a lose-lose.
---
### Author:  [@vegycslol](https://forum.grin.mw/u/vegycslol)
#### Post date: [July 14, 2023, 4:53pm UTC](https://forum.grin.mw/t/eliminating-finalize-step-revisited/10627/31 "2023-07-14T16:53:33Z")
Agree, when talking about digital identities we should think of private keys. However in theory you could include national identity public keys in the current payment proofs. Now sure someone can share that, but i think people won’t have many incentives to do that imo and it will be harder to share it with time i think.
---
### Author:  [@AceKaplin](https://forum.grin.mw/u/AceKaplin)
#### Post date: [July 14, 2023, 5:02pm UTC](https://forum.grin.mw/t/eliminating-finalize-step-revisited/10627/32 "2023-07-14T17:02:48Z")
I don’t see how a permissionless protocol can interoperate with central issuing organization, without the protocol ceding issuance authority to that organization… which in turn makes it no longer a permissionless protocol.
But that’s a whole other rabbit hole, lol
Not to mention, you could impose a similar constraint on the 2-step protocol, so I’m not sure it has merit in this conversation about 2-step vs 3-step.
---
### Author:  [@vegycslol](https://forum.grin.mw/u/vegycslol)
#### Post date: [July 14, 2023, 6:27pm UTC](https://forum.grin.mw/t/eliminating-finalize-step-revisited/10627/33 "2023-07-14T18:27:24Z")
What i meant is that when you get the national identity certificate you get a key pair and you could use these as part of payment proof. I also think it’s possible to generate similar proof with some 2-step variant. But that’s a bit off-topic.
---
### Author:  [@tromp](https://forum.grin.mw/u/tromp)
#### Post date: [July 17, 2023, 5:04pm UTC](https://forum.grin.mw/t/eliminating-finalize-step-revisited/10627/34 "2023-07-17T17:04:02Z")
Section 4.2.2 discussing duplicate sending keys:
> By eliminating `xb` from the two equations, Mallory is able to calculate the value of `s2*cb1-s1*cb2`, where `s1` and `s2` are the two sending keys (§ 3.4.1 step 3). This is not useful for any attack unless `s1` is equal to `s2`, in which case Mallory can learn `cb1-cb2`, which allows her to steal the difference between the values of the two Bob’s outputs. Bob must therefore make sure that all payments he accepts have a unique value of `s` (§ 3.4.2 step 7).
I’m don’t think avoiding duplicate sending keys suffices.
Once Mallory has made a few hundred payments to Bob, she can use a variant of Wagner’s algorithm to find two disjoint subsets with equal summed sending key. This still allows her to steal the difference in sum value between the two payment sets.
---
### Author:  [@tevador](https://forum.grin.mw/u/tevador)
#### Post date: [July 18, 2023, 5:58am UTC](https://forum.grin.mw/t/eliminating-finalize-step-revisited/10627/35 "2023-07-18T05:58:40Z")
With 2 identical sending keys, Mallory can calculate `cb1 - cb2 = s^(-1)*k`, where `k` is a key known to her and `s` is the duplicate sending key.
Can you elaborate how the attack would work using the Wagner’s algorithm? Assuming all of Bob’s blinding factors are generated uniformly at random.
---
### Author:  [@tromp](https://forum.grin.mw/u/tromp)
#### Post date: [July 18, 2023, 6:40am UTC](https://forum.grin.mw/t/eliminating-finalize-step-revisited/10627/36 "2023-07-18T06:40:06Z")
> [@tevador](#):
>
> Can you elaborate how the attack would work using the Wagner’s algorithm?
We can leave Wagner’s attack out of it for now and look at the simplest case that goes beyond duplicate send keys.
Let’s say Mallory made 3 payments to Bob with send keys s1, s2, and s3, which happen to satisfy s3 = s1 + s2. Mallory can then determine r3 - (r1 + r2), where r1, r2, r3 are the three blinding factors that Bob chose. This lets her steal the difference between the sum of the first payments, and the third payment.
---
### Author:  [@tevador](https://forum.grin.mw/u/tevador)
#### Post date: [July 18, 2023, 5:15pm UTC](https://forum.grin.mw/t/eliminating-finalize-step-revisited/10627/37 "2023-07-18T17:15:04Z")
Thanks. Wagner’s attack indeed applies here and would allow Mallory to steal funds from Bob.
I updated the protocol with a mitigation that ensures that Mallory can only steal a zero amount from Bob. I also removed the uniqueness check for the sending key as it’s not actually useful.
---
### Author:  [@tromp](https://forum.grin.mw/u/tromp)
#### Post date: [July 19, 2023, 1:29pm UTC](https://forum.grin.mw/t/eliminating-finalize-step-revisited/10627/38 "2023-07-19T13:29:55Z")
> [@](#):
>
> She can then make payments to Bob with each of these keys, making sure that the sum of the payment amounts for keys in set `A` is the same as the sum of the payment amounts in set `B`.
At this point it’s too late to set the amounts; since amounts are hashed the send keys that Mallory already ran Wagner’s attack on. Mallory should just make all amounts the same to simplify the attack.
> [@](#):
>
> Using the balance equation, Mallory will be able to calculate the difference of the blinding factors between Bob’s outputs in set `A` and set `B`. However, this won’t allow Mallory to steal any funds from Bob because both sets of payments contain equal amounts.
Are you sure?
Once Bob spends one set of outputs to pay Carol, then Mallory can collude with Carol to steal the other set.
A better mitigation would try to prevent the use of Wagner’s attack altogether, by changing step 3.4.1.4 to multiply Q\_b not with the value, but instead some pseudo-random scalar such as H\_q(T\_{stopWagner}, k\_s).
---
### Author:  [@tevador](https://forum.grin.mw/u/tevador)
#### Post date: [July 19, 2023, 5:58pm UTC](https://forum.grin.mw/t/eliminating-finalize-step-revisited/10627/39 "2023-07-19T17:58:59Z")
> [@tromp](#):
>
> A better mitigation would try to prevent the use of Wagner’s attack altogether, by changing step 3.4.1.4 to multiply Q\_b not with the value, but instead some pseudo-random scalar such as H\_q(T\_{stopWagner}, k\_s).
Are you sure this stops the Wagner attack? This would effectively increase the hash size from 256 bits to 512 bits, which makes the attack more expensive but I don’t think it prevents it.
What would definitely prevent the attack is hashing all previous `k_s` values, which is impractical. Another way to prevent the attack is always doing a payjoin with a self-sent output.
---
### Author:  [@tromp](https://forum.grin.mw/u/tromp)
#### Post date: [July 19, 2023, 6:13pm UTC](https://forum.grin.mw/t/eliminating-finalize-step-revisited/10627/40 "2023-07-19T18:13:25Z")
> [@tevador](#):
>
> Are you sure this stops the Wagner attack?
No, it was just the first thing that came to mind. That’s why I wrote “try to prevent”. As you point out, it only delays it:-(
---
### Author:  [@tevador](https://forum.grin.mw/u/tevador)
#### Post date: [July 19, 2023, 6:16pm UTC](https://forum.grin.mw/t/eliminating-finalize-step-revisited/10627/41 "2023-07-19T18:16:29Z")
> [@tromp](#):
>
> Once Bob spends one set of outputs to pay Carol, then Mallory can collude with Carol to steal the other set.
You are correct. So it appears that enforcing the uniqueness of kernel keys is necessary in this protocol, which is unfortunate.
---
### Author:  [@tromp](https://forum.grin.mw/u/tromp)
#### Post date: [July 19, 2023, 6:18pm UTC](https://forum.grin.mw/t/eliminating-finalize-step-revisited/10627/42 "2023-07-19T18:18:39Z")
> [@tevador](#):
>
> enforcing the uniqueness of kernel keys is necessary
How does that help in preventing the Wagner attack?
[Previous page](https://forum.grin.mw/t/eliminating-finalize-step-revisited/10627.md?page=1)
[Next page](https://forum.grin.mw/t/eliminating-finalize-step-revisited/10627.md?page=3)