Can a Monero coin go to Bob but come back to Alice if he never takes it, without a scripting language? We give each output a second key and change the linking tag. The coin can then be spent with either key, and it can still be spent only once.
1TU Wien · 2Independent Researcher · 3Purdue University · 4Monero Research Lab
The PDF is a 33-page version with the appendix included (the paper cites its full version as Cryptology ePrint Archive, Report 2019/595). Every figure, table, definition, theorem, section and equation number on this page follows that PDF. In it the appendix is numbered §8–§12, and Definitions 2–5 appear again as Definitions 6–9.
1 · The puzzle
Monero stops double spends with a key image: every spend publishes a tag derived from the spending key, and the network rejects any tag it has already seen. Now give an output two keys. Bob may spend it before a timeout $t$; after $t$, Alice can take it back. The obvious tag that either of them can compute is Diffie–Hellman style: $\mathcal{J}=g^{sk_0\cdot sk_1}$. Bob computes it as $pk_1^{sk_0}$ and Alice as $pk_0^{sk_1}$. Alice now plays the move below. Can Bob still claim his coin?
Your guess, before block 150:
The attack is the one described in §3.1 under "Hardening key-image linkability". Tags are computed live in a toy group ($p=10007$, $q=5003$, $g=4$). Block heights and the timeout are illustrative. The key-to-time convention (Bob's $pk_0$ before $t$, Alice's $pk_1$ after) follows §5 and §6.2.
So what, exactly, must a tag for a two-key output do?
One tag, either key. The dual key image $\mathcal{J}=g^{m\,sk_0 sk_1}$ is computed as $pk_{1-b}^{m\,sk_b}$ by whoever holds $sk_b$. It comes out the same from either side, so a dual-key output can be spent once, with either key.
See it →LSAG's three guarantees carry over. In the random-oracle model, DLSAG is unforgeable with respect to insider corruption if OMDL is hard, signer-ambiguous if DDH is hard, and linkable if OMDL is hard.
See it →One extra bit, no hash-to-point. A DLSAG signature is an LSAG signature plus a parity bit $b$. In the measured runs (ring sizes 5–20), signing and verifying were never slower than LSAG. The dual-key output itself is larger.
See it →2 · Why did that happen? · §3.1
A dual-key output $(pk_0, pk_1, m)$ has two spending paths, and its tag has two jobs. First, both paths must produce the same tag, otherwise Bob can spend before $t$ and Alice again after $t$. Second, the tag must be unique to this output, otherwise someone can burn it with a copy (the puzzle). Switch between three candidate tags and see which jobs each one does. The "Bob spends / Alice spends" toggle shows who computes what.
§3.1 states the requirement: one key image that identifies the pair $(pk_0,pk_1)$ and can be computed from either $sk_b$, made unique to the output with $m$. The first scheme is our own strawman, Monero's LSAG tag $H_p(pk)^{sk}$ applied to each key separately, shown only to explain why a single tag is needed. Toy group and toy hash as in the puzzle. Here $H_p$ is modelled as $g^{H_s(\cdot)}$, which is fine for a picture but not for real use.
We have the tag. What does a whole signature built around it look like?
3 · The definition that falls out · Figure 2
DLSAG is Monero's LSAG ring with one change. Wherever LSAG uses $H_p(pk_i)$, DLSAG uses the other key of the pair raised to that output's identifier, $pk_{i,1-b}^{m_i}$. The signer's tag is $\mathcal{J}=pk_{n,1-b}^{m_n\cdot sk_b}$. Below, the signer signs for real (Fig. 2, in a toy group). Then you step through Verify: each ring member turns $h_{i-1}$ into $h_i$, and the signature is valid only if the ring closes, $h_n=h_0$. Switch to the verifier's view: every member looks the same.
$\mathsf{Link}$ verifies two signatures and compares their tags. Sign a second transaction from the same output, or from a different output that reuses both keys (the puzzle's move). Then try the second one again under the "every $m_i=1$" preset.
Sign, Verify and Link are implemented as in Figure 2. As in its caption, the signer's output sits at position $n$; in practice the position is chosen uniformly at random. Output identifiers are $m_i=H_s(\text{outpoint}_i)$, following §3.1's "hash of the transaction and the output's position". Toy parameters: the order-$q$ subgroup of $\mathbb{Z}_p^*$ with $p=10007$, $q=5003$, $g=4$, and a non-cryptographic toy $H_s$ (FNV-1a mod $q$). This is an illustration; Monero uses ed25519.
One tag for two keys, and still one spend per output. What does that buy?
4 · What it buys · §6.2
With one tag for two keys, a refund needs no script and no second signature from Bob. Alice opens a channel by paying into the dual key $(pk_{AB}, pk'_A)$ with timeout $t$. Before $t$, the coins move only with both shares of $sk_{AB}$ (a 2-of-2 DLSAG, §6.1, Fig. 4). After $t$, Alice alone can take everything back with $pk'_A$. Off-chain, Alice pays Bob by half-signing a transaction and handing him her share $[\sigma]_A$. Bob keeps the newest one and must close before $t$.
Protocol from §6.2 (open, off-chain payments, close). The amounts (10 coins, payments of 1) and the timeout (block 16) are illustrative; the paper uses $x$, $x'$ and $t$. We follow §5 and §6.2: $pk_0$ spends before block $t$ and $pk_1$ after. The parenthetical example in §3.1 states the opposite order.
The same 2-of-2 signing, run with an extra secret $y$ (Fig. 4's highlighted lines), gives a conditional payment. It completes only if the receiver knows $y$ with $g^y=Y$, and once it is on chain Alice can read $y$ back out of the signature (§6.3). Chaining conditional payments under one $y$ gives a payment-channel network (§6.4). Tying $y$ to a hash lock on another chain gives an atomic swap (§6.5). None of these need a script, and to an observer the conditional transaction looks like any other spend.
| LSAG (Monero today) | DLSAG | Source | |
|---|---|---|---|
| Output | $(pk, \mathsf{Com}(x), \Pi)$ | $((pk_0, pk_1), \mathsf{Com}(x), \Pi, t)$, plus identifier $m$ | §2, §3.1 |
| Key image | $\mathcal{I}=H_p(pk)^{sk}$ | $\mathcal{J}=g^{m\,sk_0 sk_1}=pk_{1-b}^{m\,sk_b}$ | §3.1, Figs. 2, 5 |
| Who can spend | the holder of $sk$ | $sk_0$ before $t$, $sk_1$ after | §5, §6.2 |
| Work per ring member | as DLSAG, plus one hash-to-point $H_p$ | $\approx 4$ group operations and $1$ hash-to-scalar | §4 |
| Signature | $(s_0,\dots,s_{n-1},h_0,\mathcal{I})$ | $(s_0,\dots,s_{n-1},h_0,\mathcal{J},b)$: one bit more | Figs. 2, 5; §4 |
| Unforgeability | yes (§2; analysed in Noether–Mackenzie, Ring CT) | w.r.t. insider corruption (Def. 3), if OMDL is hard, ROM | Theorem 1 |
| Signer ambiguity | yes (§2; analysed in Noether–Mackenzie, Ring CT) | Def. 4, if DDH is hard, ROM | Theorem 2 |
| Linkability | yes (§2; analysed in Noether–Mackenzie, Ring CT) | Def. 5, if OMDL is hard, ROM | Theorem 3 |
| Refund without a script | no | yes | §3.1, §6 |
4 · What it buys, continued · Table 1
We implemented both schemes in C++ with libsodium on ed25519, the curve Monero uses, and timed them on an Intel Core i5-7400 at 3.00 GHz with 12 GB RAM (§4). DLSAG drops LSAG's per-member hash-to-point. At every measured ring size it signed and verified a little faster than LSAG. The ring-size control snaps to the four sizes that were measured.
Times in milliseconds, copied from Table 1. The "DLSAG faster by" figures are derived here as (LSAG − DLSAG) / LSAG; the paper does not tabulate them. Only four ring sizes were measured, so the lines only connect measured points.
Cheap, and it makes refunds possible. What does it leave open?
5 · Where this goes next · §7, §12
Illustration · §12, Eq. (1)
Bob's stealth address is $(B_1,B_2)=(g^{b_1},g^{b_2})$. Alice pays him twice, creating dual keys whose secret keys are $sk=H_s(B_1^{r_j})+b_2$ for her own random $r_1,\dots,r_4$. Write $a_j = H_s(B_1^{r_j})$; Alice knows every $a_j$. When Bob spends, the tags are $\mathcal{J}_1=g^{m(a_1+b_2)(a_2+b_2)}$ and $\mathcal{J}_2=g^{m'(a_3+b_2)(a_4+b_2)}$, and Alice can compute $m$ and $m'$. The unknown $g^{b_2^2}$ cancels:
$$\frac{\mathcal{J}_1^{\,m^{-1}}}{\mathcal{J}_2^{\,m'^{-1}}}=\frac{g^{a_1a_2}\,B_2^{\,a_1}\,B_2^{\,a_2}}{g^{a_3a_4}\,B_2^{\,a_3}\,B_2^{\,a_4}}$$
Every factor on the right is known to Alice, so she can precompute it and recognise Bob's spends. Mitigation (§12): Bob moves received funds to a fresh dual address. This costs one more transaction, but channels save many more.
Appendix
| Inputs |
| [0] $\{(pk_1, \mathsf{Com}(v_1), \Pi_1), \ldots, (pk_{n-1}, \mathsf{Com}(v_{n-1}), \Pi_{n-1}),$ $(pk_A, \mathsf{Com}(5), \Pi_A)\}$ |
| Outputs |
| [0] $pk_B$, $\mathsf{Com}(4)$, $\Pi_B$; [1] $pk'_A$, $\mathsf{Com}(1)$, $\Pi'_A$ |
| Authorizations |
| [0] $\sigma$ |
Alice ($pk_A$) puts in 5 coins, pays 4 to Bob and gets 1 back as change.
| Inputs |
| [0] $((pk_{1,0}, pk_{1,1}), \mathsf{Com}(v_1), \Pi_1, \mathsf{Com}(t_1), \Pi\text{-}time_1), \ldots,$ $((pk_A, pk'_A), \mathsf{Com}(10), \Pi_A, \mathsf{Com}(t_A), \Pi\text{-}time_A)$ |
| Outputs |
| [0] $(pk_B, pk''_A)$, $\mathsf{Com}(10)$, $\Pi'_A$, $\mathsf{Com}(t_B)$, $\Pi\text{-}time_B$ |
| Authorizations |
| [0] $\sigma^0$ |
Alice pays Bob 10 coins with timeout $t_B$. Bob claims them before $t_B$, or they go back to Alice at $pk''_A$.
Reproduced from the tables in background.tex (Fig. 1) and integration.tex (Fig. 3). In Fig. 3, $t$ is hidden in a Pedersen commitment. To show it has passed, the signer publishes $t'$ with $t<t'<T$ and a range proof for $\mathsf{Com}(t'-t)$ (§5). §10 works through this in full.
| Step | LSAG (Fig. 5) | DLSAG (Fig. 2) |
|---|---|---|
| KeyGen | $sk$, $pk=g^{sk}$ | $sk_0, sk_1$, $pk_b=g^{sk_b}$, and $m$ |
| Key image | $\mathcal{I}=H_p(pk_n)^{sk}$ | $\mathcal{J}=pk_{n,1-b}^{\,m_n sk_b}$ |
| $L_i$ | $g^{s_i}\,pk_i^{h_{i-1}}$ | $g^{s_i}\,pk_{i,b}^{h_{i-1}}$ |
| $R_i$ | $H_p(pk_i)^{s_i}\,\mathcal{I}^{h_{i-1}}$ | $pk_{i,1-b}^{\,s_i m_i}\,\mathcal{J}^{h_{i-1}}$ |
| $h_i$ | $H_s(\mathsf{tx}\,\|\,L_i\,\|\,R_i)$ | same |
| Close the ring | $s_0=s'_0-h_{n-1}\,sk$ | $s_0=s'_0-h_{n-1}\,sk_b$ |
| Output | $(s_0,\dots,s_{n-1},h_0,\mathcal{I})$ | $(s_0,\dots,s_{n-1},h_0,\mathcal{J},b)$ |
| Link | $\mathcal{I}_1=\mathcal{I}_2$ | $\mathcal{J}_1=\mathcal{J}_2$ |
| Number | Statement | Where |
|---|---|---|
| Def. 1 | LSAG: $(\mathsf{KeyGen},\mathsf{Sign},\mathsf{Vrfy},\mathsf{Link})$, with an explicit linking algorithm | §2 |
| Defs. 2, 3 | Existential unforgeability with respect to insider corruption (game, and $(t,\epsilon,N,q_H,q_S,q_C)$-forger), following Bender et al. | §3.2 |
| Def. 4 | Signer ambiguity: with $t$ corrupted keys and $n-t\ge 2$, guessing the signer succeeds with probability within a negligible amount of $\frac{1}{n-t}$ | §3.2 |
| Def. 5 | Linkability: $\mathsf{Link}$ errs on (same key and identifier) versus (different) only with negligible probability | §3.2 |
| Theorem 1 | Unforgeable against adaptive chosen-plaintext attack, provided OMDL is hard, in the random-oracle model | §3.2, proof §9.3 |
| Theorem 2 | Signer ambiguous, provided DDH is hard, in the random-oracle model | §3.2, proof §9.3 |
| Theorem 3 | Linkable, provided OMDL is hard, in the random-oracle model | §3.2, proof §9.3 |
| Defs. 6–9 | Definitions 2–5, repeated | §9.1 |
| Def. 10, Lemma 1 | Forking algorithm and the generalized forking lemma (Bellare–Neven) | §9.2 |
| Defs. 11–13 | One-more discrete logarithm hardness (Defs. 11, 12) and the decisional Diffie–Hellman assumption (Def. 13) | §9.2 |
| Construction | What it does | Where |
|---|---|---|
| 2-of-2 DLSAG | Alice and Bob jointly sign from a shared dual key, with commit-then-reveal nonces and $\Sigma$-protocol proofs. Each can check the other's share: $g^{[s_0]_A+[s_0]_B}\overset{?}{=}(R_A R_B)/pk_{AB,b}^{h_{n-1}}$ | §6.1, Fig. 4 |
| Payment channel | Open into $(pk_{AB},pk'_A)$ with timeout $t$; pay off-chain with half-signatures; close by completing the latest one, or refund after $t$ | §6.2 |
| DTLC | Discrete-log timelock contract: Bob is paid if he reveals $y$ with $g^y=Y$ before $t$; otherwise Alice is refunded | §6.3 |
| Payment-channel network | Alice → Bob → Carol → Dave under one secret $y$. Each hop needs its own $Y^*_i$, so an extra round lets the receiver issue $(Y,Y^*_i)$ with a zero-knowledge proof of the same $y$ | §6.4 |
| Atomic swap | An HTLC on Bitcoin with $h=H(y)$, and a DTLC on Monero with $Y=g^y$, linked by a zero-knowledge proof (e.g. ZKBoo or Bulletproofs) that both use the same $y$ | §6.5 |
| Hidden timelocks | Commit to $t$ and prove expiry through $\mathsf{Com}(t'-t)$ and a range proof, keeping timeouts indistinguishable | §5, §10 |
Reference
@inproceedings{morenosanchez2020dlsag,
title = {{DLSAG}: Non-Interactive Refund Transactions for
Interoperable Payment Channels in {Monero}},
author = {Moreno-Sanchez, Pedro and Blue, Arthur and Le, Duc V. and
Noether, Sarang and Goodell, Brandon and Kate, Aniket},
booktitle = {Financial Cryptography and Data Security (FC)},
year = {2020},
note = {Full version: Cryptology ePrint Archive, Report 2019/595}
}
Code and data. The paper has no data availability statement. Its §4 cites the prototype C++ implementation used for Table 1: github.com/levduc/DLSAG-prototype-number. Every number on this page comes from the paper, is computed live in the toy group from Figure 2's definitions, or is an illustrative value (block heights, channel amounts) labelled as such.