Eliminating finalize step

Development and Technical Discussion
64

Me too! It feels unavoidable, but I’m still looking for a clever solution.

2 Likes
65

Maybe it is as with everything Grin, see it as an a strength instead of a weakness :wink:.
In this way the receiver knows exactly before hand which addresses are used for receiving funds.

Do I understand correctly this can also be used for accepting transactions were the receiver is offline?
If an ephemeral or other private-key derivative can be generated which only allows signing for one of these specific “receive only” addresses, this would solve the other problem of users needing to be online, although you need a trusted third party to do the signing for you.

66

This is very true.
This thread got my hopes up again as they where slowly dying. GJ

2 Likes
67

No not slowly dying. But slowly overcoming major bumps in the road to a wonderful project.

2 Likes
68

I find wise method just make slatepack rele for exchange slate online

1 Like
69

1.Stop http transaction and use more anonymous save metod.
2. Stop and delete file transaction.
3. Start Offline transaction.
4. Use slate transaction at mobile wallet when can send slate token by telegram or Viber or SMS or Wechat and others
5. Swap Bitcoin core wallet to grin wallet or grin to BTC without exechanges and swap company us atomicswap
6. add qr code for address and slate

1 Like
70

2 questions:

  1. what is that time_to_live in slate’s format?
  2. is there a way to somehow preserve the list of one-time addresses when syncing from 0 or if multiple devices are used?
71

ttl is an existing slate field. If populated, the transaction will not be finalized if the timestamp is in the past.

There is a way to preserve it, but it’s not entirely safe. If wallets accidentally create 2 signatures with the same nonce, the private excess can be learned. For this reason, the RFC just recommends generating a completely random nonce.

1 Like
72

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

73

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
74

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

75

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
76

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.

77

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.

78

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
79

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
80

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
81

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
82

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.

83

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