Eliminating finalize step

Let’s say Alice wants to send to Bob. Can Alice derive extended public key specifically for Bob, so that he would be able to generate a valid Alice’s slatepack address (let’s ignore excess and only look at nonce)? I know Bob can then generate the same nonce, but is it possible to somehow use time (or smth else) as index for generating public nonce from Alice’s extended public key and then send that “time” to Alice to verify, that the public nonce was generated using this time? If possible it would be good to only perform the first step once per different participant

I think this should be prioritized, this would make things easier for mobile wallets, @i1skn recently opened a funding request which is great, and personally I’m trying to get Grin++ working on Mobile. If we ever want mass adoption we must start simplyfing stuff.

2 Likes

if not Grin wont be dead but it will be walking dead.Zombi coin…i agree with you man.

Submit a funding request!

I’m sure we all would love to see a little competition for mobile wallets, and you’ve certainly done a ton of work, and an incredible job overall on the Grin++ UI. I’m excited to see what you come up with for mobile.

3 Likes

Cross-posting a comment I posted earlier on the github RFC here for reference -

Edit: Not sure why its not linking directly to the comment.

The other thing that bugs me here is this proposal effectively pre-shares the public nonce prior to the message being committed to. There is not a lot of freedom in the message as we only include the features, the fee and potentially lock height, but there is some freedom.
So if the recipient publishes their public nonce, is the sender now able to potentially bias the message by choosing different fee and lock_height values? And in turn bias the hash function?

See “Pre-shared nonces in MuSig” here -

tl;dr Sharing the public nonce prior to committing to the message to be signed may be a bad idea.

I honestly don’t know if this is an issue with this approach - but something we should understand.

I don’t see what you mean? The sender, in this order:

  1. Calculates his partial nonce R_a.
  2. Calculates x = Hash(c||B||R_a||tx_amount||timestamp) . (c is the Diffie-Hellman secret, useful to make x not recoverable by others, plus to be sure the recipient is the intended recipient, and the sender the expected sender).
  3. Calculates the receiver’s nonce R_b = x.G + B, where B is the receiver’s permanent address.
  4. Calculates the message of the signature m = Hash(R_a + R_b||fees).
  5. Calculates s_a = r_a + Hash(m).x_a, his partial signature.
  6. Sends R_a, s_a, X_a = x_a.G, and m to the receiver.

Then, the receiver, in this order:

  1. Computes x.
  2. Computes m and verifies that it matches with the m sent by the sender.
  3. Generates randomly his private excess x_b.
  4. Calculates s_b = x + b + Hash(m).x_b (where b is the secret key to B)
  5. Broadcasts the kernel, kernel = (R = R_a + R_b, X = X_a + X_b, s = s_a + s_b).

So, first the sender needs to compute R, and then he needs to compute the message m in order to compute his s_a. Only then, can he send the data to the receiver.

I don’t see why “Sharing the public nonce prior to committing to the message” is true at all.

OK, I have looked at the link that you provided on MuSig @antioch. The question that you asked is relevant and deserves to be addressed in our scheme.
In your sentence, I thought you were saying that it is the receiver that will choose the message “for the sender” after the sender had sent him the nonce, and I did not read the blog post first.

I’ll explain the Wagner’s attack described in the blog, and then see its applicability (or not) in our scheme. First I’ll explain what the Wagner’s algorithm is in the general case.

What a Wagner’s algorithm does in the general case:

Given a fixed number alpha fixed before the attack, the Wagner’s algorithm allows to find k numbers n_1,...,n_k in reasonbale time such that
alpha = Hash(n_1) + ... + Hash(n_k).
That’s all (the algorithm to be able to do this in reasonable time is actually very refined).

Wagner’s attack in the case of the MuSig with nonce pre-sharing:

In MuSig the total message M of the signature is composed of R, the total nonce, X, the aggregated key, and m, the “extra data” (fees, etc).

What the Wagner’s attack consist of in the setting with nonce-pre-sharing MuSig is that the attacker opens k parallel signing sessions with the victim and collects the k respective partial nonces of the victim (one per signing session) so that he can compute the k total nonces R_1,...,R_k for the respective k signing sessions. This is the first step of the attack.

In the second step, the attacker fixes for himself a message m_0, takes the aggregated key X, and computes the nonce R_0 = R_1 + ... + R_k.
He then computes M_0 = Hash(X||R_0||m_0). Note that M_0 will play the role of alpha.

In the third step of the attack, the attacker, using the Wagner’s algorithm, comes up with k messages m_1,...,m_k that are such that:
M_0 = Hash(X||R_1||m_1) + ... + Hash(X||R_k||m_k).

At the end of the parallel MuSig protocols, the attacker possesses k valid signatures s_i such that for each i:
s_i = r_i + Hash(X||R_i||m_i).x, which is a valid signature for X with nonce R_i.
x being such that x.G = X, and r_i such that r_i.G = R_i.

This is where the attack can be applied to come up with a rogue signature s_attack, signing the aggregated public key X. It is left as an exercise to the reader in the blog post, so I post in what follows the solution to the exercise.

s_attack is in fact just the sum of the k signatures:
s_attack = s_1 + ... + s_k = (r_1 + ... + r_k) + Hash(X||R_1||m_1).x + ... + Hash(X||R_k||m_k).x.

Given that the k signatures were done on the same aggregated key X, with secret key x, the above expression can be actually factorized:

s_attack = r_0 + (Hash(X||R_1||m_1) + ... + Hash(X||R_k||m_k)).x,
where r_0 = r_1 + ... + r_k corresponds to the secret to R_0 (since R_0 = R_1 + ... R_k).

But if we remember, we had, thanks to Wagner’s algorithm:
M_0 = Hash(X||R_0||m_0) = Hash(X||R_1||m_1) + ... + Hash(X||R_k||m_k).

Thus, s_attack = r_0 + Hash(X||R_0||m_0).x, which means that the attacker has been able to create a valid signature against the aggregated key X with nonce R_0, and message m_0 that the victim never actually signed.
This is the end of the attack.

Wagner’s attack in our scheme:

Irrelevant since the receiver always chooses different partial excesses at each signing session.

1 Like

This raises an interesting (and nuanced) difference between the use of signatures in Grin/MW and other UTXO based currencies.

In Bitcoin the private key used in the signature is fixed. The sender has no freedom in choosing the private key as this is based entirely on which utxo is being spent. Multiple attempts to spend the same utxo will necessarily result in multiple reuse of the private key, hence the insecurity around sharing nonces.
The signature is used to prove ownership of the output being spent.

  • No freedom to choose private keys == you must securely exchange nonces.

In Grin/MW this is different. The sender and recipient both have freedom is choosing their partial private excess and can ensure a partial excess is never reused.
The signature is used to prove collective ownership of all private keys (existing inputs and new outputs) involved in the transaction.

  • Freedom to choose new private keys each time == greater flexibility around nonce exchange.
1 Like

Yeah, but what I am noting here with this Wagner’s attack on MuSig is that Blockstream does not tolerate it. And guess what, the threat model to fully protect them, would just be that the MuSig user checks that they never sign two times the same key.

There is a criticial attack I described above Eliminating finalize step which is protected by a uniqueness check. As I said, on the paper we have theoretically two solutions to prevent from this attack:

  1. User checks nonce or timestamp uniqueness.
  2. Nonce uniqueness is ensured at consensus level.

What MuSig and Blockstream are clearly telling us, and that I have been telling for months now, by adding a third round to prevent the Wagner’s attack and relief a (uniqueness) check burdon from the user is that solution 1. makes striclty no sense at all.

Finally say hi to kernel uniqueness at consensus level.

1 Like

Yes agreed. Things would be way easier if we had kernel uniqueness enforced at the consensus level. In this case we’d enforce uniqueness, not on the public excess, but on the nonce R.

We just need to find a way to do this efficiently across the full set of global kernels. And this as far as we understand, is unfortunately impossible.

1 Like

Oh yeah, totally impossible, I think we can give up and just leave Grin as it is. I think I never provided several solutitons to do it. This is too sad.

The issue with bitcoin is that for an existing UTXO this is not possible. Multiple aborted attempts to spend this utxo will necessarily result in multiple uses of the same key.

1 Like

Of course, I am certain it is impossible that a wallet prevents from re-signing 32,000 times a same key and then send the 32,000 nonces to the other co-signers.

YESSSSSS killing it. Digital cash here we come…

MACKER

1 Like

I want to describe another attack on the scheme, which is fixable with a slight modification of the protocol.

EDIT: As tromp points out below, I did a mistake in this attack and the below is not correct.

The attack:

Party A does a first legit transaction to party B. s_A: partial signature of the sender, s_B: partial signature of the receiver.
s_B = x + b + Hash(m).x_B.
with x = Hash(R_a, B, amount, timestamp).
Total nonce R is R = R_a + B + x.G.
Then, s = s_A + s_B is a valid signature on total excess X for total nonce R. Up to here, everything is fine.

But later Party A can replay the transaction without the participation of party B with using a different x (call it x’) on a different partial nonce R’_a:
R’_a = R_a - x’.G + x.G.
x’ = Hash(R’_a, B, amount’, timestamp’),

s = s_A + s_B is in fact a valid signature on excess X for total nonce R’ = R’_a + (B + x’.G).
But one can notice that R’ = R, which means the message of the first signature can be replayed with using R’_a as sender’s address and x’ as the “payment proof part” of the receiver’s nonce.

Use amount’ = $1,000,000 in x’ and party A is able to prove that he paid $1,000,000 to party B without party B participating.

In initial proposal, we had:
R_b = x.G + B.

Fix: replace by
R_b = x.G + x.B.

That way, party A would have to use an adjusted nonce R’_a for the second transaction equal to:
R’_a = R_a - x’.G + x.G - x’.b + x.b
But he would not know the private key of this R’_a because he does not the value of b.

Hence party A will not be able to provide correct payment proof for the second transaction as a correct payment proof requires a proof of knowledge of the private key to sender’s nonce.

Of course the fix is only necessary if solution 1. (put burden on user and wallet devs) is chosen. If nonce uniqueness at consensus level is chosen one can keep R_b = x.G + B since the attack relies on using the same total nonce.

2 Likes

Circular definitions…

1 Like

You’re right, indeed.

I guess that’s why I notified the importance of committing to R_a in x in an earlier post in this thread.

So, sharing the nonce is not a problem, but it turns out, the scheme where we no longer commit to pub excess in the challenge string actually is vulnerable to Wagner’s attack after all. A huge thanks to Beam’s Vlad Gelfer for working this out. I’ll describe the attack now.

The proposed (insecure) signature scheme:
k = nonce, k*G = pub nonce
r = excess, r*G = pub excess
M = message
e = Hash(M | k*G)
s = k + e*r
Signature = (k*G, s)

The attack:
Rather than using k*G as the pubnonce, the attacker generates another random number, x, and uses k*G + x*H as the pub nonce. Then, he can calculate a pub excess after performing the challenge as:
pub excess = r*G - x*(e^-1)*H. He now just built a valid signature which, in addition to the excess (r), also has a value x*(e^-1).

This is still not trivial to perform in mimblewimble, since in order to build outputs with the value of x*(e^-1), the value has to fit in 64-ish bits to build a bulletproof (actually, closer to 70, because you could build say 1,000 outputs). But as it turns out, you can sum multiple kernels together so that the sum of their x*(e^-1) only has to total 70-ish bits, which Wagner’s attack tells us is much easier. Performing this attack results in undetected inflation :cry:

Solution:
Left as an exercise for the reader.

2 Likes

Thanks for sharing this.

An uninformed question: Would this apply to the scheme proposed here as well? Integrated Payment Proofs and Round Minimization

1 Like