Eliminating finalize step

Development and Technical Discussion
43

Looks like an interesting discussion topic for the next developer meeting…

Could it be added to this afternoon meeting agenda @lehnberg?

May be it’s too late. Or too early :wink:

1 Like
44

There is a sneaky sneaky attack i just see in the scheme with sender-generated receiver’s nonce, and receiver-generated receiver’s partial excess. I have not seen yet an instance of the attack where it is possible to steal money, so the post can be seen as a bit of zoology on potential subtilities arising from these new schemes removing the need of a final 3rd step to build transactions. Edit: it is actually possible to steal money using the attack. Left as an exercise : )

The attack:

If an attacker could send to the same receiving party two different transactions with the same excess signature’s message:

In that case we get the following two equations:
s_1 = x_1 + b + Hash(m).sk_1
s_2 = x_2 + b + Hash(m).sk_2
Subtracting the last equation from the first one:
s_1 - s_2 - (x_1 - x_2) = Hash(m).(sk_1 - sk_2).
It means that sk_1 - sk_2 = (s_1 - s_2 - (x_1 - x_2)).Hash(m)^(-1).
So, it simply says the sender can learn the value of sk_1 - sk_2.

While knowing the value of Hash(m_1).sk_1 - Hash(m_2).sk_2 is not a problem and does not lead to an attack, learning the value of sk_1 - sk_2 can be a problem in Mimblewimble.

Why does this lead to a problem?

sk_1 + receiver_offset_1 = sum(r_1), where sum(r_1) is the sum of the blinding factors of the receiver’s outputs in first transaction. Similarly sk_2 + receiver_offset_2 = sum(r_2), where sum(r_2) is the sum of the blinding factors of the receiver’s outputs in second transaction.

so we have that sk_1 + receiver_offset_1 - (sk_2 + receiver_offset_2) = sum(r_1) - sum(r_2). Other way to put it, denoting z = sk_1 - sk_2, known by the sender as we mentioned earlier, we have:
z + receiver_offset_1 - receiver_offset_2 = sum(r_1) - sum(r_2).
But receiver_offset_1 and receiver_offset_2 can be learnt by the sender when the two transactions are broadcasted. It means that the receiver can learn sum(r_1) - sum(r_2), and yes, this is dangerous.

Indeed, it means that the attacker could basically use the tx outputs of the second transaction as transacttion’s inputs of a malicious tx he would do, and use the tx outputs of the first transaction as the transaction outputs of this malicious transaction (he can copy paste the bulletproofs), because he can recreate a valid mimblewimble balance equation, without the will of the owner of these outputs. He could do this malicious transaction without the need to use a previous kernel or kernel excess. He could just build a brand new kernel for the malicious transaction, with the knowledge of z = sk_1 - sk_2.

What can be done to prevent this?

The source of this attack arises from the fact that the two excesses of the two txs have a same signature’s message.

Two same signature’s messages means in particular that R = R_a + R_b is the same in both transactions. Denote the nonce appearing in the second transaction: R' = R'_a + R'_b.

R = R' means:
R_a + x.G + B = R'_a + x'.G + B. Which implies (the B cancelling out) r_a + x = r'_a + x'.
Unfortunately, this does not imply that x = x' since the sender could create x' first, with x' != x, and then compute r'_a so that r_a + x = r'_a + x'. This is something we want to fix, because we want a way so that the receiver can notice when the sender is trying the attack, a.k.a, using the same R in the two txs, and thus we want that the attacker must use x' = x in order to have R' = R. And then, the receiver can notice through examining the pre-image of x and comparing with what he got before to check if he is being attacked or not.

In my post earlier, I proposed x = Hash(c||B||tx_amount||timestamp). This needs to be modified to commit to the sender’s public nonce as well; we rather define x with the following formula:

x = Hash(c||B||R_a||tx_amount||timestamp).

Now, it means that the sender has to choose his private partial nonce first; before actually creating the x. if r'_a != r_a is fixed, finding x' such as r_a + x = r'_a + x' now reduces to finding a hash collision, which is considered impossible with Sha256.

It means that with that new definition of x (committing to R_a), the sender will have no choice but to choose r'_a = r_a (i.e, R'_a = R_a) in order to get R' = R. He must also choose x' = x, which implies R_b = R'_b = x.G + B, and in turn, R' = R (because R'_a = R_a).

With that new definition of x, we have just provided a way to ensure that R' = R implies x = x', which is striclty equivalent to: "x != x' implies R != R'".

Then, it suffices that the receiver verifies that he always receives different timestamp in each of his transactions to be sure that none of excess’s signatures messages provided by the sender are a duplicate.

To sum up, we recommand to rather define x as:
x = Hash(c||B||R_a||tx_amount||timestamp),
and to require checking timestamp uniqueness when receiving transactions. Those two things prevent the attack.

3 Likes
45

I don’t think it is too early. There are two variations that I think are feasable and secure. Maybe will they need in-depth review though, to fully make sure they are secure, but I have small doubt a secure, if not several, variations are available for us. So far, here is my perception of the two variations we have, which I think are both secure:

  1. Receiver can always use the same B but needs to verify that timestamp is always different (See the long previous post) for each of the transactions he receives.

  2. Receiver always uses a different address each time he receives a new transaction.

For 2., the essential reason it is secure is that the Diffie-Hellman secret (=Hash(s.B) = Hash(b.S)) between sender and receiver will always be different because the receiver always changes his address at each new tx, with the sender having no way to trick anyone; to understand why, one needs to look at the Diffie-Hellman key exchange protocol, which is not really complicated if we understand how a private key and a public key work.

If the Diffie-Hellman secrets are different, it means that the x will always be different (x, defined in the last post, is the hash of some data that includes c, the Diffie-Hellman secret).

if the x are different, it means that the receiver’s partial private nonce r_b are also always different by construction, and its public nonce R_b will for sure also be always different.
And finally, R = R_a + R_b too, since the sender commits to R_a in x, and cannot adjust anything because he committed to R_a first (some explanations in post above).
So, we always get different R, which also means that we always get different excess’s signature messages since R is part of the message.

To sum up, we always get different nonces, and always get different excess’s signature messages. This actually also true for 1. after receiver has verified that timestamp is a not a duplicate.
It is all good, I don’t see any way to attack this. On top of that, the receiver can generate himself (without the sender like for the nonce) its partial excess and the associated secret key.

Each of 1. and 2. have each their tradeoff, but as of today I would put either of these trade-offs as quite OK to have, considering that they enable A -> B communication. So let’s see what we can get out of this.

1 Like
46

Let us know how the dev meeting goes! Cool stuff
-Macker

1 Like
47

A bit of science fiction was in the meeting.
I was happy to learn that the sender can control the value of the nonce. But there are two mechanisms that prevent the sender from controlling so.

  1. Diffie-Hellman
  2. The hash function of x.

One of the two suffice to make the nonce unpredictable. We have both.

I rather try to observe facts clinicaly, in all proposals. It is more useful when you do technology.

I would have hoped that the decisional persons in Grin, Tromp and Antioch, would act in the same way more often, rather than act based on emotions or uncomplete considerations of some proposed constructions and their implications.

That’s how it is!

Diffie-Hellman output is completely unpredictable and unrepeatable with using the variation 2., because the receiver always changes his receive address. Then the value of the Diffie-Hellman output is passed to a Hash function. The output of the hash function is added to the key of the receiver, which has a secret key that the sender does not know. This is overall three rounds of unpredictabilities, one of each being totally uncontrollable by either the receiver or the sender.
For the variation 2, the Diffie-Hellman output is unpredictable, as always with Diffie-Hellman, but can be repeated if the sender always use the same ephemeral key, and that the receiver keeps the same B. Unrepeatability is controlled by the receiver which refuses transactions with a same timestamp, to make sure that the output of the hash function is not always the same. This check provides total unpredictability for both sender and receiver, as a new timestamp will always produce a brand new output for the Hash in x (x = Hash(c||B||R_a||tx_amount||timestamp)). On top of that, the sender never learns the secret key of B, so their is another round of unpredictability for the nonce of the receiver. In both variations, either by the receiver changing address or by the receiver checking timestamp we have both multiple rounds of unpredictability and unrepeatibility for the nonce.
And oh magic, this in turns provides the same property for the excess message, since the message of the kernel excess has the nonce in it.

As a side note, the attack i described earlier for 1. is possible in today’s Mimblewimble if someone always uses the same nonce. This is of course totally OK, since no proper wallet will reuse nonce, but it is interesting to note that for the canonical use of schnorr signatures, repeating the nonce is not a security problem when always changing the signing key (it is a problem if not changing the signing key), but it just turns out that it is unsecure for Mimblewimble because having the difference of two different partial signatures opens the breach to the attack i described.

There’s never been free rides with signature protocols, even for the simplier variation of the simplier signature scheme (Schnorr) as mentioned earlier. Using some nonce and some key for a signature scheme has never been the insurance to provide security for the user. Only when you follow the proper and good practice of their protocols, can you be quite sure that none of your coins will be stolen.

2 Likes
48 
do {
  pick new inputs to step 1. & 2.
  compute step 1. & 2.
} while (top 16 bits of output != 0xB145)
49

Sender cannot calculate receivers secret nonce. receivers secret nonce is = x + b, with b being unknown by the sender.

50

Yes, step

  1. form nonce by adding hash output to receiver secret

seems to keep the nonce bias free (they can still be biased toward said secret, e.g. nonce likely matches secret in top 16 bits).
But steps 1. and 2. by itself do not.

1 Like
51

I don’t see any bias being introduced.

But anyways, nonce bias is a danger only in secret key reuse, where you can use lattice-based algorithm to find the re-used secret key. In these proposals, receiver generates his partial excess secret completely freely from the sender at each new transaction.

1 Like
52

Any news on this? Sounds like it may be possible. As far as user experience goes, it would make a huge difference!
-Macker

53

It seems the goal of eliminating the finalization step would be very similar to one sided transactions from this thread. Pep Talk for one sided transactions

Really i think we are all noticing the difficulties with Grin transactions is somewhat handicapping its growth. As always balancing security with functionality.

Macker

2 Likes
54

Yep. I came up with both ideas for one simple reason: Grin is entirely unusable by the masses, and will never see mass adoption in its current form.

Many say this is a problem for 3rd party wallet developers to solve, but that’s bullshit. I’ve spent almost 2 years developing a 3rd party wallet trying to solve this very problem, and I’ve completely failed. Quite frankly, the protocol sucks. Too many things can go wrong while transacting, and it’s complicated AF for exchanges and other services to deal with the many things that can go wrong.

Removing the number of steps in the transaction building process seems to be the only way it will ever improve.

6 Likes
55

Agreed, seems promising! I’m having a hard time understanding what the latest and greatest of this proposal is, there’s already ~50 replies in thread.

Would be great we could have a summary / overview of the most up to date proposal, for example:

  1. List of currently known use cases. If we do this, how will tx-building become better? What additional things could be possible, how will UX become simpler, etc.
  2. One paragraph overview of what changes are being proposed.
  3. List of technical changes:
    • New tx-building flow
    • How is invoice flow handled
    • How are payment proofs handled
    • Any consensus related change?
    • Any pre-requisites?
    • any other related spec topic
  4. Known issues / open questions. What’s still left to figure out?
  5. Trade-offs. Any reasons not to do this? What are the costs?

I’m happy to assist and try to keep the list up to date, but don’t think I’m knowledgeable enough to take the lead on it. @david would you be willing to help me?

7 Likes
56

Yep, I’ll just go ahead and create an RFC, and continue to keep it up to date with the latest thinking.

5 Likes
57

Before we get too far ahead of ourselves, let’s see if we can settle on the basic idea of this proposal.

Do I understand correctly that the idea is to have the receiver publish two public keys P=x*G, R=k*G, from which multiple senders can derive transaction specific receiver excess and receiver nonce,
based on some unique shared secrets ss_i, ss’_i?

Using receiver excess of the form P + ss_i*G and receiver nonce of the form R + ss’_i*G is not safe.

58

No, unfortunately we require the receiver to generate a one-time address (pub excess and pub nonce) for each transaction. It’s not as nice as I originally hoped, but it’s secure, and I think it’s still a decent usability improvement.

We should be able to pre-generate hundreds of addresses and have a listening wallet which collects partial transactions that can be finalized offline later.

2 Likes
59

@lehnberg There are still a few sections to finish, but here’s the first attempt at an RFC: https://github.com/mimblewimble/grin-rfcs/pull/59

5 Likes
60

If we compare this to an invoice workflow where

  1. receiver sends public excess and public nonce
  2. sender sends public excess, public nonce, inputs, outputs, partial sig and offset
  3. receiver finalizes

then it’s not the finalize step that’s eliminated. You still do all these steps. With step 1) becoming sender/transaction agnostic.

And most importantly, with a payment proof that was missing from the receiver workflow before.

Perhaps “payment proofs for sender agnostic invoice workflow” is a better proposal description than “Eliminating finalize step” ?!

3 Likes
61

Sure, technically that’s what’s happening. But by combining the sending of public excess and public nonce with the sharing of the address, to the end user, it’s one less step they have to take.

1 Like
63

Cool! I took a pass / went to town a bit in the comments. Let me know what you think. :+1:

I got a bit bummed out by the one-time address requirement however, I hadn’t realised that was needed until now… :persevere:

1 Like