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 userfriendly. 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 socalled â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 roguekey 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 BellareNeven multisignature scheme [9], protecting us from the attack. First, we describe the BN scheme in the general case.
Description of the BellareNeven multisignature 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, computesR = 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 theX_i
, and all thes_i
, and finally broadcasts the signaturesigma = (R,s)
, wheres = s_1 + ... + s_n
, together with each of then
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 multisignature 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 multisignature 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 roguekey 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 BellareNeven 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 BellareNeven scheme but, unlike the BellareNeven 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 BellareNevin 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 excessX_a
and messagem
. Bob choosesR_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 signatures_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 somek
(typically quite large),k
scalarsy_i
such thatX_i = H(X_a, R, m).X_a + y_i.G
fori = 1,...,k
and thatH(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 they_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 thek+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 multisignature 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 nonceR_a = k_a.G
. 
Generates her ephemeral address
U = u.G
and computes the DiffieHellman secretd = H(u.B)
, whereB
is Bobâs permanent receiveonly 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)
, ands_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 DiffieHellman secret
d = H(b.U)
, whereb
is the private key toB
. 
Computes
z = H(d, R_a, X_a, B, U, amount, timestamp)
andR_b = z.G + B
. 
Generates his partial excess
X_b = x_b.G
. 
Computes
R = R_a + R_b
ands_b = z + b + c_b.x_b
, wherec_b = H(X_b, R, m)
. 
Computes
s = s_a + s_b
,c_a = H(X_a, R, m)
, and verifies thats.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 thatd = 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/multisignaturesccs.pdf (BellareNeven paper)
[10] https://eprint.iacr.org/2018/068.pdf (MuSIg paper)
[11] https://medium.com/blockstream/insecureshortcutsinmusig2ad0d38a97da (Insecure shortcuts in MuSig)