Eliminating finalize step ReLoAdEd

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)

12 Likes

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

Yes, you can do that too indeed :wink:

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?

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.

  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?

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

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.

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.