Contents

1. Motivation
2. Summary of idea
3. Isn't this like X?
4. Sketch of practical use cases
5. Technical summary
6. Enforcing scarcity by preventing reuse
7. Anonymity set degradation vectors
8. Aren't the privacy promises a bit dodgy?
9. Some loose ends

(Thanks to Ruben Somsen for several helpful comments and suggestions while drafting this)

Motivation

The perhaps central problem of the digital age is how users of services and providers of services can allow interaction without one of:

• Invasion of privacy leading to complete loss of autonomy and unacceptable security risks via hacking, doxxing etc.
• Rampant botting/spamming/Sybilling and a tragedy of the commons
• Avoiding both the above by imposing large financial costs

This problem is seen in sign ups for websites, for example, or comment posting, or public API usage. It also becomes a particularly keen problem in Bitcoin protocols like Lightning Network or Joinmarket where we want participants to be able to participate but are open to spam and snooping attacks, and sometimes have to make unfortunate privacy tradeoffs.

This document introduces, and argues for, usage of a cryptographic mechanism which is already well known (to experts, if not the general public), as a potential solution for this problem in a wide variety of contexts, leveraging Bitcoin's utxo set.

We would caution that this is not an identity system; it cannot identify individuals (we hope!) and has nothing to say about distributed or centralized naming services (at least, not as described here). It's basically about anonymised and lightweight rate limiting.

We would also briefly caution that this cryptographic technique offers realistically practical privacy but definitely not strong anonymity, as discussed a bit here.

This mechanism can work in the following context:

• Some broad taproot usage on Bitcoin (though the exact usage pattern will not matter) (taproot is needed only because of exposed public keys in utxos, not because of Schnorr or other features of BIP340/1.
• This mechanism requires real time access to the utxo set for the service provider, and at least accessibility of the utxo set occasionally for the user, but the impact on user experience is likely to be minimal.
• It does not require buy-in from other taproot users to gain the anonymity set of taproot utxos

"Ring signature based IDentities using Discrete Log Equivalence" or "RIDDLE" for short (the name is appropriate in suggesting that this mechanism creates a very difficult, usually unsolvable puzzle for the adversary .. also, one could imagine, whimsically, a UI presenting this to a user as "your wallet is solving the riddle", like a captcha).

Summary of idea

The LSAG or "Linkable Spontaneous Anonymous Group" signature is a more developed version of the basic ring signature described here. It was first described in the literature by Liu, Wei and Wong here. The user can choose a set of public keys, only one of which they own the private key for; they can then create a signature that's verifiable, and doesn't reveal which key of the set was used, but has a special twist: in creating the signature they must also create a "key image" which is fixed over any such signature. Thus, if a protocol wants to prevent repeated use of the key, it can do so by recording key images. The technical details will be covered in this section.

The set of public keys referenced in the previous paragraph could be a set of taproot keys corresponding to unspent bitcoin, i.e. utxos. A set of such utxos could be chosen spontaneously, referred to compactly, and the age in blocks, unspentness, and bitcoin value of the utxos can all be referred to, to assess validity of the "RIDDLE" created.

These kind of signatures can be created from users' existing wallets and need not lock funds. Let's discuss that, probably surprising statement, next:

Does a signature on existing funds really have any anti-Sybil value?

The line of reasoning that led to this document was this:

• Fidelity bonds (see below) would be better if anonymised, but:
• Anonymity set would be limited to the custom scriptpubkey used for the fidelity bonds (includes a CLTV timelock) and in some way to the amounts of the bonds (it's hard to argue for amount ranges like 1-2BTC if someone at the bottom of the range gets an unfair advantage).
• With small anonymity set the problem of 'someone else spends before expiry' is particularly acute, so a very rigid approach (literally only keys with the exact same timelock) might be needed

If we accept that this timelocking of funds is too impractical for ring signatures, this leads to a quandary: if you don't actually **lock up** funds, what's the value? The answer in practice is basically: **rate limiting** and that's exactly the problem we addressed in Joinmarket with the PoDLE tokens. The idea is: you can use a service only if you provide a token that proves you own a utxo that is at least \(N\) blocks old and has a bitcoin value of at least \(A\).

But a more precise answer 'does it have any value?' is: there is a sacrifice of value inherent, even if small, in such a token, via two mechanisms:

1. If you use a RIDDLE token for service \(S\), you cannot use it for service \(S^{*}\) (this will be explained later).
2. By using age and BTC value requirements, a cost - in the form of BTC network fees - is imposed that is almost zero for slow, occasional use but becomes (nonlinearly) much larger for anyone attempting to use the service very frequently (and due to block arrival rate, *no* amount of money may be enough to achieve very high Sybilling rates).

(The limitation of PoDLE tokens, and the comparison with fidelity bonds, is expanded on in the next section).

Isn't this like X?

The reader is most likely to start thinking about similarities and differences to other systems, so we'll refer to these connections here:

Hashcash for anti-spam

Yes. This idea is attacking the same problem. Hashcash is a purer, more direct solution, but has never taken off as a general mechanism except for rare use cases like bitmessage, outside of Bitcoin itself and PoW cryptocurrencies generally - probably because hardware specialisation makes it problematic in a situation where users are not capable of countering adversaries (as opposed to cryptocurrencies where it's only relevant for miners, who are all adversaries and not in a user/customer role).

Joinmarket PoDLE (or DLEQ) tokens

This idea is a development from that idea. In PoDLE we use a commit-reveal mechanism. We effectively have a "key image" in which the key is revealed, and hence the utxo is revealed, after the necessary information is gleaned from the counterparty. This leads to difficulties due to the fact that the taker (the one who generates the PoDLE) has to give up some information to the counterparties (one utxo; usually it's one inside the coinjoin, which would usually be deducible anyway). RIDDLE improves on that by revealing a potentially large anonymity set of utxos, instead of the single taker-owned utxo, at the cost of more utxo set queries and a larger signature size.

Joinmarket-style Fidelity Bonds

See here for summary and standardisation of this; it's basically funds that are locked for a specific timeframe.

Mechanically, these are also signatures, but standard ECDSA (Schnorr would be the same) signatures on existing utxo keys, i.e. not ring signatures and not anonymised. This allows us to reference the value of the utxo directly, and we also in this model, actually time-lock the funds allowing a concrete sacrifice of value to measured and applied in-protocol. RIDDLE is a much lighterweight model, and as discussed above the value sacrifice is much smaller; hence the scope of applicability of RIDDLE is very different (more appropriate for 'customers' than service providers).

(We have previously considered LSAG for fidelity bonds here).

Isn't this what Monero uses (LSAG)?

Yes, with a tweak for reuse. That construct, which as per my summary of the history of the development of these type of ring signatures here, came out of several prior constructions. What is proposed here is referred to there as "Back-LSAG", after Adam Back, which MLSAG, used in Monero, is an extension of (mainly it extends by allowing multiple ring sigs at once).

Sketch of practical use cases

1. Take as an example the website https://stacker.news . This is a discussion forum similar to reddit, hacker news, in that it allows user-generated links and content to be prioritised based on user feedback, and like the earlier yalls.org in that it uses satoshi level Lightning payments as part of the user experience (paying to vote; paying to comment; being paid for content). This is an example of a service where botting or Sybil attacks could easily be a problem, especially at scale, because there is incentive directly (getting paid for content) to game the system in certain ways. Incentives of course are not always directly financial; twitter bots may be used to steer user attention, etc.Users on sign up could be required to provide a valid RIDDLE of age 2 weeks in blocks and size at least 500K sats (finger in the air values). Since there are (hypothetically) thousands of such taproot utxos, the user's wallet can generate a RIDDLE of size between 4kB and 40kB (see technical details below) with anon set between 100 and 1000 and send it to the website, which can then generate some form of authentication token associated with the user's chosen nym. Thus:But what's wrong with lnurl-auth ? This question is natural as that is the current login method for stacker.news. lnurl-auth is fundamentally only providing authentication on a "free" nym as a key derived from a LN wallet/node is not scarce, in itself. It would be possible to build on it/extend it to e.g. require funds in channels (functioning similar to a fidelity bond), but this would reintroduce the problem of anonymity loss (channel utxos) which was removed in lnurl-auth with the linkingKey derivation. RIDDLE allows both anonymity and cost imposition.
   • the website/service provider does not learn anything about the user's wallet (not literally true, but close enough).
   • no funds are spent.
   • the funds are not locked (they only need to be unspent and satisfy the above, at the time of sign up).
   • the sign up is quasi immediate, at least most of the time.
   • while one user could for sure generate more than one account, generating a lot of such accounts is a little costly
   • generating a very large number of such accounts quickly (e.g. if they are being banned and you want to keep recreating bots) is nonlinearly more expensive.
2. Public, free APIs : A RIDDLE could be required to receive some gated/restricted/streamed service, like an API. This could involve generating more RIDDLEs over time, rather than just one. This is particularly appropriate because as discussed, the primary cost in RIDDLEs is creating them quickly, i.e. they provide substantial rate limiting, something that public APIs often have to address carefully.

Does size matter?

A quick aside before diving into the technical details of these RIDDLE objects.

If the verifier chooses to allow any utxo > 100K sats for example, but the user has consolidated their wallet and has only 1 utxo of size 1M sats, it seems rather unfair to only allow them one usage.

We can address this, but cautiously: we allow the single 1M utxo to, possibly, create about 10 such RIDDLE objects that can be used in different services, by changing the definition of key image as in LSAGs previously defined, to include a counter variable. See below for details.

The user in so doing should be judicious in his choice of other utxo keys to form the ring signature over, if he is not using the counter value of '1'. See here for more details on that.

The TLDR is that users will sometimes be able to use the same utxo for more than one service, and if the wallet software treats it intelligently, this should only rarely degrade the anonymity set, and only a little.

Technical summary

Verifier policy:

The service provider, or verifier V has policy requiring minimum BTC amount \(A\) and minimum age in blocks \(N\). They also set a maximum anonymity set \(M'\) for provided RIDDLEs (to avoid having to deal with too-large ring signatures).

Choosing a set of keys.

Both the signer S and the verifier V will need access to the utxo set in order to sign/verify. The signer must choose a set of \(M \le M'\) utxos that all satisfy requirements of the above policy (and of course one index \(\pi\) in that set of \(M\) must refer to a utxo which the signer owns).

Forming the RIDDLE LSAG signature and publishing

The keyset, consisting of \(M\) utxos (public keys being therefore directly available, in taproot) must be communicated along with the signature in this case; the best way to do that is probably to use the equivalent of Lightning's `short_channel_id` which is an 8 byte structure referring to block, tx num and output index. The full structure of what is published should therefore be (the signing algorithm, written below, will explain the details here):

keys: \(8N\)

\(s\)-values: \(32N\)

\(e_0\)-value: 32

key image \(I\): 32

where the figures after the colon are in bytes.

Anonymity set scaling

We see from the above listing that the signer must publish \(40N + 64\) bytes. So for an anonymity set of 100 we require abut 4kB and for an anonymity set of 1000 we require about 40kB.

Algorithm for constructing the RIDDLE

Defining \(\mathbf{H}\) as a hash mapping from a string of bytes to a point on the curve secp256k1, we, instead of defining the key image as \( \mathbf{H}(P_{\pi})\), define it as: \\ \mathbf{H}(P_{\pi} || j) where \(j\) is an integer counter. Additionally, and similarly, for all other keys in the set \(L\), we use the offset basepoint \(\\ \mathbf{H}(P_{i} || j)\), i.e. always include the counter.

The signing in detail:

S finds a set of \(M\) utxos that satisfy the policy, including one of their own, and construct as a list of pubkeys \(P_i\), with their own signing index \(\pi\)(knowing corresponding privkey \(x_{\pi}\), and having amount \(A_{\pi}\)) being randomly placed in the list \(0 \ldots M-1\). Note that the signer has some free choice in whether to choose smaller non-owned utxos (reducing the number of reuses via the counter value \(j\)), or larger utxos, increasing it. Define the smallest btc amount in the set of chosen utxos to be \(A_{\textrm{min}}\).

Define the list of pubkeys as \(L\).

1. Find the lowest positive integer \(p\) such that \(p < \frac{A_{\textrm{min}}}{A}\) and \(x_{\pi}\mathbf{H}\left(P_{\pi}||p\right)\) is not an already-used key image.
2. Calculate key image \(I = x_{\pi}\mathbf{H}\left(P_{\pi}||p\right)\).
3. Choose a random scalar \(k_{\pi}\), and choose \(M-1\) random scalars \(s_i\ \forall i \ne \pi\). Define \(R_{\pi} = k_{\pi}G\) and \(R_{\pi} = k_{\pi}G\).
4. For \(i\) from \(\pi+1 \ldots \pi-1\) (modulo \(M\)):
   a. Calculate \(e_{i} = \mathbf{H}\left(\textrm{'global'} || L|| R_{i-1} || R_{i-1}^* || I\right)\).
   b. Calculate \(R_{i} = s_{i}G - e_{i}P_{i}\) and \(R_{i}^* = s_{i}\mathbf{H}(P_{i}||p) - e_{i}I\).
5. For index \(\pi\), calculate \(R_{i}^* = s_{i}\mathbf{H}(P_{i}||p) - e_{i}I\).
6. Publish the signature as \((L, \{s_i\} \forall i \in 1 \ldots M, e_0, I\).

Note: the \(L\) can be published compactly and indirectly from the set of utxos as discussed earlier; and \(L\) is included in the hash challenge, as was briefly noted as preferable in the blog post.

Also note: the signing of the message global is intended to imply that the default signing algorithm is the same for the whole universe of possible services requiring RIDDLE tokens/key images. The possibility of a single service preferring not to consider usage of a utxo, outside itself, is discussed below.

Also note: it is probably better to include the utxo outpoint in the hash so \(U_i\) instead of \(L\) just in case of key reuse on-chain.

The verification in detail:

V is given: \((L, \\{s_i\\} \forall i \in 1 \ldots M, e_0, I)\).

1. Reject if \(M > M'\) or \(A_{U_{i}} < A\) for any \(i\).
2. Calculate \(x = \textbf{min}(A_{U_{i}})\)
3. Calculate \(y=\lfloor x/A \rfloor\)
4. For \(k \in 1 \ldots y\):
   1. For \(j \in 1 \ldots M\):
      a. Calculate \(R_{j} = s_{j}G - e_{j-1}G\) and \(R_{j}^* = s_{j}\mathbf{H}(P_{j}||k) - e_{j-1}I\) (note \(e_j\) is given for the first iteration).
      b. Calculate \(e_{j} = \mathbf{H}\left(\textrm{'global'}||L||R_{j}||R_{j}^{*}||I\right)\)
   2. If \(e_{M} == e_{0}\) return True.
      return False.
5. If step 4 returns False, reject. If step 4 returns True, check \(I\) against the key image database; if \(I\) is already present, broadcast \(I\) and reject. If it is not in the database, broadcast \(I\) and add \(I\) to the database, and accept.

Enforcing scarcity by preventing reuse

A rather crucial issue here is: we need to make sure that someone doesn't reuse a key image - because if they can do that, there is no scarcity here. Let's examine how that is currently working in Joinmarket with PoDLE:

• a user requests a service (makers for a coinjoin) and sends the 'key image' (basically) to each maker.
• makers check the validity and unused-ness of the key image; if it's invalid then reject and do nothing; otherwise:
• each maker communicates with several other makers, some of which publish the key image to a bulletin board
• every participant (maker or not) keeps listening to the bulletin board and updates their internal database of 'used key images', only ever adding to that database (subject to space limits of course)
• any attempt to reuse a key image is therefore banned by individual users (no one is in central control)

We envisage the exact same principle - as briefly noted in the verification algorithm above - of "broadcast valid PoDLEs, and let everyone listen" applies to RIDDLE, but:

Can it work the same for *multiple* services as it currently does for *one* service (Joinmarket makers)?

This is really what Fujisaki-Suzuki/Cryptonote/Back-LSAG addressed (that was not in LWW-LSAG).

For digital cash and voting schemes, it's very often important that not only can a key not be signed against twice in a specific group of keys but it cannot be signed against globally (meaning not only every key that exists now, but every key that might exist in the future). That's why the key image is defined as:

\(I = x_{\pi}\mathbf{H}(P_{\pi}||j)\)

and not:

\(I = x_{\pi}\mathbf{H}(P_{\pi}||j)\)

This way, as long as there is a broadcast or gossip mechanism that's sufficiently global, of key images, then usages will be known across multiple services. The possibility of spamming such a broadcast channel is more or less prevented by requiring that the RIDDLE be valid to be a candidate for broadcast. This kind of thing is not too hard to achieve as seen in e.g. Bitcoin and Lightning gossip.

But what if I actually want to use it for just one service and ignore the rest?

That's also possible. You would simply create a different class of RIDDLE, one which was tagged for your specific service (S); it would not verify for any other service. This is done most simply by having a custom message be signed:

\(e_i = \mathbf{H}\left(\textrm{'special RIDDLE for S'}||L||R_{i-1}||R_{i-1}^*||I\right)\)

Since this would not verify for the 'global' class of RIDDLEs, it will not get broadcast globally (though it wouldn't hurt since obviously there are no collisions possible).

Anonymity set degradation vectors

Are unanticipated spends out of the keyset a problem?

No. This is based on using utxo age and not forward time-locking of the utxo.

By definition, the token does *not* become invalid once we spend the utxo at index \(\pi\), i.e. the index which is that of the real signer. Therefore the sequence of spends out of the entire set \(U_i\) does not convey information to the adversary. In specific contexts, the behaviour of those spends might convey information, but that is outside the scope of the protocol.

Is the anonymity set really all taproot utxos in the ring?

Yes and no. The reason to say no is principally the same reason taproot utxos may not all be indistinguishable in the first place: some people may use exotic scripts (good example: complex threshold multisigs using OP_CHECKSIGADD) and may not use the 'taproot assumption' part in spending (i.e. even when the script is complex, it is always possible to fall back on key path spending). But this 'reason to say no' is pretty weak, of course, as it'll only apply to very small sets and it's tough to deduce for sure that such a spend is not corresponding to the actual signer of the RIDDLE.

Choosing counter values > 1

As per the signing and verifying algorithms above, the user can choose a counter in the key image, \(j\) in \(x_{\pi}\mathbf{H}\left(P_{\pi}||j\right)\), for any value from 1 to \(Q\), where \(Q\) is how many times larger their *minimum* utxo amount \(A_{\textrm{min}}\) is than the policy required amount \(A\).

While there is substantial flexibility in this, the signer/developer would be cautioned that:

• trying to maximise the number of utxo reuses achieved by choosing rings of utxos that all have values at least the same as your own utxo's value (so e.g. if your utxo is 1Msat and you choose all 1M sat and above, so that if the verifier requires 100K you can use counters up to 10), while efficient, will have a tendency to leak data about utxo size over time.
• hence, it is better to make use of more, smaller utxos if that is possible. Typical wallets tend to have 10+ utxos over time (even 30+ is not uncommon for active users), so the biggest pain point is likely to be on wallet creation/startup, but even one utxo may be fine if you only need access to 1 or 2 services.

Aren't the privacy promises a bit dodgy?

As briefly noted in the introductory section, one should be careful not to treat ring signatures as a privacy guarantee - they are simply not that. Technically a ring signature can be a zero knowledge proof of knowledge of 1 out of many keys, but that doesn't mean the protocol as a whole has any kind of zero knowledge property - not even close! Putting aside possible vectors for the anonymity set to be degraded, as discussed in the previous section, we must also consider the broad class of attacks based on the compounding effects of the behaviour of other (decoy) participants in the group; this is a problem well known in the case of Monero and coinjoin (which doesn't use ring signatures, but there is a very similar mechanic). There is also the problem of the cross referencing of different ring signatures - see the concept of 'set intersection attacks'.

There are two perspectives to keep strongly in mind here:

• this is not a blockchain, but only references a blockchain -and that makes a lot of difference! While behaviour of the on-chain utxos can be used by the adversary, the adversary does not have a global view of all the ring signatures created.
• there is no possibility that this kind of system can provide iron-clad privacy guarantees. If protecting the location of the real signing utxo is a matter of life and death, on no account use a system like this!

Some loose ends

Lest this document get even larger, we will leave some technical details undiscussed:

• If age from creation to spending is the requirement, might it be reasonable to include spent utxos? A couple of problems: access to spent txos is harder for verifiers (the main reason for focusing on utxos); but also certain attacks might be easier here (because you can arrange for large numbers of utxos to exist in advance).
• Can we finesse what resource we force the user to use up for the anti-Sybil effect? We could count the age of the utxo, or combine the amount with the age in some formula like \(N^{\alpha}A^{\beta}\) based on some analysis of what gives more anti-Sybil effect. We could possibly allow multiple values of the counter (j), per pubkey. Ther are many variants that might make the system more flexible.
• Wallet developers have a stumbling block: this is a non-standard (to Bitcoin developers) ring signature; integration into the libsecp256k1 API of the basic DLEQ or ring signature or even full Back-LSAG would clearly be desirable
• Storage scaling of key images: we've addressed that all out spam should not be possible, but for global RIDDLEs (i.e. not specific to one service), how do we go about pruning the list of key images?
• Most users we would hope to have the required utxos, at the point of use, but for wallet integration, how to handle the case where they don't, is annoying UI-wise if not coding-wise; it may involve creating in-wallet spends.
• Scaling of ring signature size: the LSAG is linear in the anonymity set (see above; 40N+64), which is probably fine for sensible sets of say 100-1000. Can we get a sublinear linkable ring signature algorithm that doesn't require pairing friendly curves? (secp256k1 is not pairing friendly).
• RIDDLEs could be transferred, i.e. sold. I'm not sure if or why that might be a good or bad thing. Even more interesting: could they be sold trustlessly?