Eliminating finalize step ReLoAdEd

Research
1

Recently, @david proposed the seminal idea [1] to use a signature scheme (for our kernels) that would remove the need of the last communication round, making potentially (if we can find a secure scheme for that) Grin transactions quite more user-friendly. He proposed that the sender would deterministically generate the partial excesses and nonces for the receiver.

Later in the thread, I proposed a detailed scheme bringing into practice this idea, in particular by using ideas from the Stealth Addresses protocol, and by also using the Schnorr signature variation which does not commit to the public key [2], along to describing some security analysis that brought additional precautions and insights in order to avoid some attacks [3], [4], [5], [6], [7].

Nonetheless, Valdo rightfully found an attack that uses the fact that we do not commit to the public key (the excess in the case of Grin) in the signature’s challenge, and which would allow in particular for undetectable inflation [8]. That can’t be fixed by keeping the same Schnorr signature scheme. This attack essentially comes from the fact that in blockchain protocols, there is no central authority to testify that the public keys that are used are of the form a.G, for some scalar a (in effect, the private key). Indeed, in the blockchain world, we are most of the time under the so-called “plain public key model”, which is a more general cryptographic assumption (and more difficult to deal with) that does not make any assumption on the forms of the public keys, opening for example the doors for such things as rogue-key attacks if we are not careful in the designs.

Due to this attack, we clearly need to change the signature scheme in order to try the Eliminating last step (ELS) idea once again maybe provide a scalable and secure scheme. Due to the fact that @david, @johndavies24 and @Chronos have been able to show interest to this, I am happy to propose here this new scheme that uses a variation of the Bellare-Neven multi-signature scheme [9], protecting us from the attack. First, we describe the BN scheme in the general case.

Description of the Bellare-Neven multi-signature scheme:

We denote by L the list L = {X_1 = x_1.G,...,X_n = x_n.G}. Signature generation protocol:

  • Each of the n participants draws their individual partial nonce, R_1 = k_1.G, ... , R_n = k_n.G and, after communication in order to exchange the nonces between them, computes R = R_1 + ... + R_n.

  • Each participant computes the challenge c_i = H(L, X_i, R, m).

  • Each participant computes their partial signature s_i = k_i + c_i.x_i.

  • One of the participants collects R, all the X_i, and all the s_i, and finally broadcasts the signature sigma = (R,s), where s = s_1 + ... + s_n, together with each of the n public keys.

Verification: a signature sigma = (R,s) is valid if and only if: s.G = R + c_1.X_1 + ... + c_n.X_n.

Remarks and comments:

The Bellare and Neven paper introducing this scheme proves that this multi-signature protocol is secure under the plain public key model, meaning that a valid signature actually proves knowledge of the individual private keys to each of the public keys X_i. Historically, this is the first secure multi-signature Schnorr scheme under the “plain public key model”. As a side note, if you are using the naive Schnorr signature scheme, it is for example easy to perform a rogue-key attack and to sign with sets of public keys whose you actually do not know any of the private keys. As a second side note, the Bellare-Neven scheme does not support key aggregation, which means that all the individual public keys must be kept as they are and that the verifiers must have direct access to each of them to verify the signature. Introduced quite recently, MuSig [10] allows for similar security as Bellare-Neven scheme but, unlike the Bellare-Neven protocol, the public keys can actually be accumulated (aggregated) into a unique public key.

The idea for this new ELS scheme in Grin is to use a variation of Bellare-Nevin whereby the two public keys will be the two individual partial kernel’s excesses. In the BN scheme, one can notice that each challenge c_i requires knowledge of each of the public keys being signed for (through the list L, see the description of the protocol above). If we denote by X_a the partial excess of the sender, and by X_b the partial excess of the receiver, we would have c_a = H(L, X_a, R, m) for the sender’s challenge, where L = {X_a,X_b} and R = R_a + R_b the sum of the two partial nonces. In ELS schemes, while the sender can easily compute R (because they generate the partial nonce R_b for the receiver), they nonetheless cannot compute L since they do not know the partial excess X_b of the receiver when they start building the transaction. As a consequence, we are forced to modify the formula for the challenges in our modified BN signature scheme; we will remove the list L from the challenges and rather directly use:

c_a = H(X_a, R, m) and c_b = H(X_b, R, m).

the advantage that we get here though, is that we are now committing to the public keys in the challenges, (here, the two partial excesses of the transaction) completely removing the undectable inflation attack. Now, to understand more the reason why Bellare and Nevin included the list L in each of the challenges, let’s describe an attack that exists if we use the proposed variation that does not include L in the challenges.

The Wagner’s attack on the proposed variation of the BN scheme without L in the challenges:

The following attack is a slight variation of the Wagner’s attack described in the MuSig paper.
Assume that an attacker Bob starts a signing session with an honest people Alice, using the BN variation without the list L that I am proposing:

  • Bob, the attacker, receives Alice’s partial nonce R_a partial excess X_a and message m. Bob chooses R_b = r.G - R_a and sends it to Alice.

  • Alice computes R = R_a + R_b, c_a = H(X_a, R, m), and sends to Bob her partial signature s_a = k_a + c_a.x_a (tips: which won’t actually be used by Bob).

  • Now, Bob can actually starts performing a Wagner’s attack using Wagner’s algorithm:
    a) Bob finds, for some k (typically quite large), k scalars y_i such that X_i = H(X_a, R, m).X_a + y_i.G for i = 1,...,k and that H(X_1, R, m) + ... + H(X_k, R, m) = -1 (yep, Wagner’s algorithm allows to achieve this type of relations between hashes).
    b) Now, one can see the “devastating” effect of the above relation:
    H(X_a, R, m).X_a + H(X_1, R, m).X_1 + ... + H(X_k, R, m).X_k = H(X_a, R, m).X_a + (H(X_1, R, m) + ... + H(X_k, R, m)).H(X_a, R, m).X_a + H(X_1, R, m).y_1.G + ... + H(X_k, R, m).y_k.G = H(X_a, R, m).X_a + (-1).H(X_a, R, m).X_a + H(X_1, R, m).y_1.G + ... + H(X_k, R, m).y_k.G = H(X_1, R, m).y_1.G + ... + H(X_k, R, m).y_k.G, which Bob knows the private key to (he knows each of the y_i by construction). It slightly hurts the eyes, sorry for that; it was proposed few months ago to include the latex package, but I guess no further action for this has been taken yet; maybe for the next time ; )

  • It is left as an exercise to the reader that Bob can actually forge a valid signature for the set of keys X_a, X_1, X_2, ... , X_k without knowing any of the private keys to the k+1 keys. Hence, we have shown the presence of this Wagner’s attack for this variation of BN scheme.

This attack would be infeasible to perform using the original BN Schnorr multi-signature scheme because L, the list of each individual public keys, is committed to by each individual challenge.

Furthermore, the (very) good news is that for us and this new ELS method, we don’t care about this attack since it is actually impossible to perform it with k = 1 as it would be equivalent to finding a hash collision; Wagner’s algorithm is based upon a sophisticated algorithm and k is in practive at least in the order of the hundreds, or even of the thousands [11]. We can check quite easily that each kernel contains two public keys only, (the two excesses) as it is naturally expected.

Now is the time to detail a bit the ELS proposal, whose structure is essentially the same as the one I described for the former scheme. The scheme adds an additional 33 bytes to each kernel, and is a bit slower to verify than our current signature scheme.

ELS scheme Reloaded:

Step1: The sender, Alice

  • Generates her partial commitment X_a = x_a.G and her partial nonce R_a = k_a.G.

  • Generates her ephemeral address U = u.G and computes the Diffie-Hellman secret d = H(u.B), where B is Bob’s permanent receive-only address.

  • Computes z = H(d, R_a, X_a, B, U, amount, timestamp).

  • Computes R_b = z.G + B.

  • Calculates R = R_a + R_b, c_a = H(X_a, R, m), and s_a = k_a + c_a.x_a.

  • Sends {R_a, X_a, U, s_a, m, amount, timestamp} to Bob (along with her inputs, outputs, and partial offset).

Step2: The receiver, Bob

  • Computes the Diffie-Hellman secret d = H(b.U), where b is the private key to B.

  • Computes z = H(d, R_a, X_a, B, U, amount, timestamp) and R_b = z.G + B.

  • Generates his partial excess X_b = x_b.G.

  • Computes R = R_a + R_b and s_b = z + b + c_b.x_b, where c_b = H(X_b, R, m).

  • Computes s = s_a + s_b, c_a = H(X_a, R, m), and verifies that s.G = R + c_a.X_a + c_b.X_b.

  • Builds his outputs (and maybe inputs) and computes his partial offset, and then checks that the transaction verifies the Mimblewimble balance equation with the total excess X = X_a + X_b.

  • Broadcasts the transaction with the set of the inputs and outputs, the kernel offset, and kernel = {sigma = (s,R), X_a, X_b, m}.

Verification: a signature sigma = (R,s) is valid if and only if: s.G = R + c_a.X_a + c_b.X_b.

Payment proof:

Alice, to prove that she did her payment to Bob, should just:

  • show that z.G + B = R – R_a.

  • show that z = H(d, R_a, X_a, B, U, amount, timestamp).

  • show that U = u.G and that d = H(u.G).

Conclusion: (so far)

There will be the need, of course, to study the security of this scheme in more depth. Analysis that has been provided for the previous version [3], [4], [5], [6], [7], [8] will be useful to further pursue in this direction due to the similarities in the two schemes.

[1] Eliminating finalize step (David’s OP)
[2] Eliminating finalize step (description of previous ELS scheme)
[3] Eliminating finalize step (attack)
[4] Eliminating finalize step (attack)
[5] Eliminating finalize step (attack)
[6] Integrated Payment Proofs and Round Minimization (attack)
[7] Integrated Payment Proofs and Round Minimization (attack)
[8] Eliminating finalize step (fatal attack)
[9] https://cseweb.ucsd.edu/~mihir/papers/multisignatures-ccs.pdf (Bellare-Neven paper)
[10] https://eprint.iacr.org/2018/068.pdf (MuSIg paper)
[11] https://medium.com/blockstream/insecure-shortcuts-in-musig-2ad0d38a97da (Insecure shortcuts in MuSig)

13 Likes
2

Can be simplified to X_i = X_a + y_i.G for i = 1,...,k and that H(X_1, R, m) + ... + H(X_k, R, m) = -H(X_a, R, m)

1 Like
3

Yes, you can do that too indeed :wink:

4

d is redundant, as you can just hash u.B in the z hash.
Shouldn’t you also hash a public key A of Alice in z, so that the payment proof is tied to her identity?

5

Yes, you could use Hash(u.B) or u.B. The diffie-hellman secret is often mentioned with the Hash.
Putting the sender address A in the hash would allow the receiver to prove that A paid her in case that the sender would deny. I think depending the usecase or context it can definitely be useful to include it.
You could have the flexibility to either add A, or B, or A and B, in the hash for z, so that to have payment proofs with different features and usecases.

6
  1. draws = randomly picks?
  2. let’s say I’m R_1, is it not dangerous if i pick R_1 = myRealR - R_2 - R_3 … - R_n which makes R = myRealR?
  3. why do you call private nonce k and public R? To confuse non-math people like me? :smile:

I guess H(u.B) = H(b.U) so they get the same z. So u.B = b.U which i get, but why not just use H(B + U)?

What do you mean with this? Doesn’t he hash u.B in z now?

7

yes exactly

Excellent question. I can dig more and come back to you but iirc MuSig for example had to add another new first round for something like that where they commit to the nonces first. For BN, despite I before looked at the paper and the exact scheme I think the security proof can be done without committing to the nonces and the BN I described comes from a YouTube video of Yannick Seurin (the man behind MuSig security proofs) on Schnorr signatures, and if I remember in their paper too, B and N dont use a round where the participant commits to the individual nonces first. And in fact I think a party could not produce their s_i at all if they had done a rogue-nonce as you describe. You can also read reference [11]; it is relevant to your question.
The above is not too relevant for us since the total nonce is generated by the sender in ELS schemes (R_b = z.G + B) and we have no choice but to do that otherwise we would not eliminate the last step :). Besides, to prevent the sender from choosing R_a or R_b as a function of the other, I included R_a in the hash of z to commit to it before choosing the nonce R_b; [6] describes an attack using the kind of relation you’re pointing out, on proofs of payment if you do not commit to R_a in the hash defining z.
Let’s hope that the whole sheme has no attack we haven’t seen or more importantly that we will be able to “prove” it secure maybe and that we continue to appreciate it more in the context of MW. Can’t answer for sure but I am relatively confident it could be good.

This question is too private, I won’t answer it : P

You could either use d = Hash(b.U) (what i did) or d = b.U since the whole thing is hashed again (see the expression of z) and u.B = b.U is already a secret (see a bit below in this post). I subjectively chose to include the Hash, because I think it is cleaner to reason about. But this is not really important anyways.

correct for your guess.
If I use H(B+U) instead its like trying to do a wheel by using chair, it won’t work very well:)
Diffie-Hellman had a lot of prizes and recognition for their Diffie-Hellman key exchange scheme. It is super super useful and used everywhere on internet to derive a common key between two users that want to for example authentificate / encrypt or decrypt data between them. Please Google : )

and note a few things:
u.B = u.(b.G) = u.b.G = b.u.G = b.(u.G) = b.U
So only the owner of the public key U or B can calculate this relation as you can see since u or b has to be known. This is why we call Diffie-Hellman a non-interactive key exchange (NIKE) protocol, and the resulting key (u.B, or hash(u.B)) a “shared secret”. With your proposal it is no more a secret since everyone can calculate U + B. As a side note it is an open problem to devise a NIKE for more than 2 or 3 people. with 2 people, this is super clean and simple (Diffie-Hellman), but for more than 3 people it is an open problem in crypto in 2020. I think Dan Boneh did a recent paper on a failed attempt of multi party NIKE. can Google it :slight_smile:

1 Like
8

You still need to explain why that matters. Or why hashing U and d into z even matters. I.e., how would your construction fail if you simply take z = H(R_a, X_a, B, amount, timestamp)? It would also be nice to explain why you need to hash X_a in there.

9

As you have used it sometimes in some discussion, it is here about “elegance” and easy-to-reason-about argument. In particular, I also wanted to reduce curve points in the hash in the expression of z to public keys only. u.B is a curve point whose nobody knows the private key to (aside from collusion between Alice and Bob), and hence is a not a public key. Moreover, Hash(b.U) would be the only 32-byte scalar in the hash’s pre-image.

I think u.B in the pre-image is necessary for clean payment proof (I describe the payment proof protocol in OP). You can also use signature, but since we should use ephemaral sender’s nonce it would be less scalable than just storing the u for each transactions.

The presence of U and X_a is to be humble and prudent first, since it would reduce (or at least not worsen) the surface vector of potential sender’s impersonification attacks, where an attacker would send simlataneous transactions to a receiver in a way that would somehow trick him (whether such tricks would be possible). It would also reduce (or at least not worsen) the risk of conflicts in a lawsuit due to payment proof; X_a is the only data in z related to the excess; so the receiver would be able to prove, if X_a is included in the hash of z and that they can provide the private key to X_b, that the sender actually signed their part of the excess, which would not be possible to prove that formally if the sender does not commit to X_a in z.

I would be glad if others think about this too, and if you are very confident we can remove some of these data, feel free to do so. Personnally, I’ll maybe try to think more about it later, and do hope others will do as well.

10

This specific post is to briefly discuss ELS scheme without adding an additional curve point.

A scheme attempt was done on keybase on committing to X+R (X: excess, R: nonce) in order to try getting rid of the additional curve point. Unfortunately, a still complicated one and broken at its core.

I can try to propose a scheme similar to the one in OP or the previous one but where the initiator would draw their R_a and X_a and commit, through a unique challenge, to X + R where R_b + X_b is equal to z.G + B. Signature verification would be s.G = R + H(X + R, m).X.

The payment proof would be:

  • show that z.G + B = R + X – (X_a + R_a) .
  • show that z = H(d, R_a, X_a, B, U, amount, timestamp) .
  • show that U = u.G and that d = H(u.G) .

Let r_b and x_b be the nonce and excess secrets of the receiver for a first transaction. Let s_b be their partial signature.
Let r'_b and x'_b be the nonce and excess secrets of the receiver for a second transaction. Let s'_b be their partial signature.
We have:
z + b = r_b + x_b and z' + b = r'_b + x'_b, from which you can get an equation between r_b, r'_b, x_b, and x'_b.
s_b = r_b + e.x_b and s'_b = r'_b + e'.x'_b.
In total you get 3 equations for 4 unknowns, which is not in general solvable.

And, looking at the information arising from a unique transaction, you get 2 equations: z + b = r_b + x_b and s_b = r_b + e.x_b, with 3 unknowns (r_b, x_b and b), which is not solvable too.

So, maybe a scheme with an unique challenge (like we currently have) but committing to X + R, or more generaly f(X + R), where f is a function, would not leak private information. Determining if it is really secure is another story for sure.

The scheme is - on the paper - more fragile than the scheme described in OP, but haven’t demonstrated yet that it would be insecure. Maybe is it trivial to break it. I hope some will try to think about it and see where we could go with this if there is no obvious flaw. A first angle of study could be to try to apply all the attacks that were already discussed to this scheme, and see if it resists to them.

edit:
I quickly checked the attacks, and the one that may be applicable here is the attack about knowing the value of x_b - x'_b, which is described there Eliminating finalize step. To prevent it, similarly to the previous and broken scheme with the inflation attack, it would be necessary to verify the uniqueness of X + R for the whole blockchain in order to not have 2 times the same challenge, which prevents the attack. But even if we don’t verify uniqueness of this, it seems the attack may not apply as long as the receiver always chooses different tuples (r_b,x_b) for each transaction, so that x_b - x'_b could in fact not be calculated, even when two challenges are equal (i.e. e = e').
The inflation attack does not work for this scheme since X contributes to the challenge, unlike the first scheme. It does not mean that there are no new attacks, since the scheme is still quite different, with X_b + R_b being forced to be equal to "the receiver’s permanent address + z.G".

11

By subtracting z + b = r_b + x_b to z' + b = r'_b + x'_b, we get:
r'_b - r_b = z' - z - (x'_b - x_b)
We also have s_b = r_b + e.x_b and s'_b = r'_b + e'.x'_b. We can subtract the former to the latter equation:
s'_b - s_b = (r'_b - r_b) + e'.x'_b - e.x_b, i.e, by substituting:
s'_b - s_b = z' - z - (x'_b - x_b) + e'.x'_b - e.x_b, i.e:
s'_b - s_b = z' - z + (e' - 1).x'_b - (e - 1).x_b, or:
(e' - 1).x'_b - (e - 1).x_b = s'_b - s_b - (z' - z) .
No problem if e != e', but if e = e', we get:
x'_b - x_b = (s'_b - s_b - (z' - z)).(e - 1)^(-1).
Which allows the attack.

In conlcusion, checking uniqueness of R + X on the blockchain is necessary.

12

Would be nice to use rewards for this kind of challanges, everyone loves a game/challange with reward.
Unfortunately it is beyond my current level of understanding to identify potential attacks😔, maybe after another year grinning😁

1 Like
13

Yes, no hurry to learn, it always takes a bit of time. First understanding well how Schnorr works, and then multi-sig schemes, help. There are good ressources on this on the net, and it is quite interesting. But to maybe do a change, we will need a talented cryptographer to make a security proof, which will hopefully happen, because I guess it could be really interesting to have this natural transaction scheme where the sender does not need to stay online once he has sent the data to the receiver. It could make Grin interesting and pleasant to use, with maintaining the full benefits of interaction.

3 Likes
14

I’d like to point out that this modification of the Schnorr signature protocol is insecure for Mimblewimble as it does not actually commit to the kernel public key.

Let R' = X + R and e' = e - 1 where e = H(R', m).

The signature verification equation simplifies to:

s*G = R' + e'*X

which is the standard Schnorr verification except the hash function is redefined as H'(x) = H(x) - 1.

We can see that the challenge e' is independent of the public key X, which means this scheme is susceptible to the counterfeiting attack described here: Eliminating finalize step - #91 by david

2 Likes