mimblewimble team mailing list archive

[John Tromp <john.tromp@xxxxxxxxx>]

dear imblers,

While discussing kernel signatures and possible optimizations with Igno,
I got this idea about how to single-handedly turn ordinary outputs
into 2-of-2 outputs with myself as additional recipient, effectively
holding them at ransom. Note that this attack seems limited to the use
of Schnorr signatures, and may force us to abandon them. So, on to the
attack.

Suppose I am relaying or mining Igno's transaction spending output o0 into
outputs o1 and o2, with fee f and Schnorr signature (s,e).
I can verify this signature by computing kG = s*G - e*xG
where xG = o1+o2-o0+f*H is the kernel public key,
and checking that e = H(f | kG).

Now I generate ransom keys r1 and r2, and define
o1' = o1 + r1*G
o2' = o2 + r2*G
xG' = o1'+o2'-o0+f*H = xG + (r1+r2)*G
s' = s + e*(r1+r2)
Now kG = s'*G - e*xG', so (s',e) multi-signs the transaction with
o1/o2 replaced by o1' and o2'.

Each output has a rangeproof consisting of several ring signatures
corresponding to different denominations that sum to the hidden value
(see [1] [2]).
For binary denominations, each such ring signature is of the form
(e0,s0,s1) satisfying, for some P0,P1 differing by 2^i * G,
e1 = H(s0*G-e0*P0)
e0 = H(s1*G-e1*P1)
To fix a rangeproof, say for o1, it suffices to add r1 to both s0 and s1
in the ring signature for any single denomination, which will compensate
for the increase by r1*G in P0 and P1.

Picking r2 = -r1 even lets me ransomize the outputs without changing
the signature (although the rangeproofs still need adjusting).

I can demand a pretty penny for revealing the ransom keys that let the
recipients spend their outputs...
This attack could be prevented by having the Schnorr signatures sign
the outputs as well as the fee, but that completely undermines our
goal of increasing unlinkability.

Questions:
Does this attack indeed work as advertised, or did I miss something?
Is there any defense using Schnorr signatures that doesn't add linkability?
Does this affect ElGamal signatures as well?

[1] Borromean ring signatures
     https://github.com/Blockstream/borromean_paper/blob/master/borromean_draft_0.01_9ade1e49.pdf
[2] Confidential Transactions, Content privacy for Bitcoin transactions
      https://bitcointalk.org/index.php?topic=1085273.0

regards,
-John