Due to unexpected failures of github's LaTeX parsing (which were not evident until I published this, but have persisted afterwards), and since the mathematical parts are important in this, I have migrated this proposal to a blog post with identical content, but correctly formatted equations.
Please continue to put any comments here.
probably the only disadvantage is that it's bringing complexity into a core protocol description (decoy choice) that would be nice to keep outside.
Unless I've misunderstood, I don't know why it has to be in the core protocol? The verifier can accept any ring of UTXOs, it's just the signer that is strongly recommended to pick the ring in a deterministic way. The protocol doesn't have to enforce anything.
(hash(our utxo, service name) is a crude example of the top of my head)
Make sure the seed has some kind of non-public information. With the example you came up with it, the verifier could try inserting every UTXO in the ring into the "our_utxo" value and see if the pseudorandom function gives exactly the whole ring. I'd suggest using the privkey as in hash(our_utxo_privkey, service name)
especially as you don't deal with re-org issues etc.
right, the whole fork issue (which always amused me because they're very reminiscent of the mechanics of the security reduction arguments used to guarantee soundness in crypto proofs .. rewind time and play back the same algorithm with the same starting state but inject fresh randomness, extract the secret information!) seems not to apply here, but thinking about it firms up the content of what @chris-belcher was saying and makes me rethink my response there. Look at it from two perspectives: if you are only allowed to use your utxo once (so counter value, as discussed in doc, is kept to always be 1), then double spend is your own fault as a user. But if we allow counters > 1 for more flexibility, as discussed, we need to ensure that there is no linkage between the rings chosen for counters 1,2,3.. etc. It's publically verifiable what counter value is being used (the verifier plugs in j=2 for example, for every key in the ring). So anyway the long and short of it is that I think the right approach is deterministic random generation of decoy/ring set based on public info, i.e. verifier policy: btc amount, utxo age and counter value.
Another way to say it, that the set of decoys is disjoint between different runs is only a problem if there is a linkage between two runs of the protocol. With counters we don't get that, only a "real" "double spend" gets that, which means same counter value, which we mustn't do.
Enforcing a decoy selection algorithm would be ideal
Enforcement is clearly a bit trickier here, but I agree. Not being on a consensus ledger makes it different. But the concept still applies since there's interaction. Verifiers individually can enforce a rule, and a protocol spec can clarify what the rule MUST be, which gets us most of the way to enforcement (if both sides, signer and verifier, choose not to apply it, then they're just doing their own thing, and we can't help).
Yeah this one looks like a very interesting read to consider some details. Some overlap, but some differences. I see that there is a deterministic random generated from key images of inputs (and other stuff). That makes sense there but not here; we are not chaining these ring sigs so we have no concept of 'input'.
Make sure the seed has some kind of non-public information. With the example you came up with it, the verifier could try inserting every UTXO in the ring into the "our_utxo" value and see if the pseudorandom function gives exactly the whole ring. I'd suggest using the privkey as in hash(our_utxo_privkey, service name)
Right! That one doesn't fly, oops :)
But it's interesting to contrast with the discussion above with @sethforprivacy . You might not want to use private information, because it can't be enforced (albeit, that is viable). If we based it on public information but not specific to the specific signer, then you get that enforcement potential: so example is : current blockheight and verifier policy (age, amount minimums) and signer chosen minimum size (which has to be bigger than verifier policy amount minimum) - that last one sort of implies the counter value.
The argument for trying to do the public-info way is to help prevent users footgunning. But it's a pretty good argument to do that, if it's possible.
If that seeds the choice from the set defined by the policy then it still has the properties we want, doesn't it?
If we based it on public information but not specific to the specific signer, then you get that enforcement potential: so example is : current blockheight and verifier policy (age, amount minimums) and signer chosen minimum size (which has to be bigger than verifier policy amount minimum)
Sorry, heh, managed to contradict myself in one sentence there :) Can't be (realistically) signer-chosen minimum size. I can't help wondering if the "current blockchain state" is OK then, as I vaguely suggested 'block height', it's a little inelegant for various reasons, not least being that of course there can easily be more than one signer at the same time, and time (even block height) is not globally synchronous.
Hmm, on second thoughts, maybe I take back what I said earlier about how the seeding works in the above Monero document. I think we could do that: we have precisely one key image being consumed in each RIDDLE. So seed the ring/decoy selection with exactly that, which is public information.
Yes, there might even develop a market around these which could allow activists to purchase these tokens privately. In theory, a user could issue just-in-time ring signature as a token to some other user, but this seems less obvious. One issue with having a market of CT could be that it seems impossible to tell whether they've been spent because the nullifier set is available to the service.
I agree; I think this line of research makes a lot of sense. The only downside is, to have a market that really works for those kind of users, it needs to not be centralized and/or have really good privacy properties. It's tough to build markets like that, but it's definitely desirable.
I slightly prefer the model where an output is a citizen due to direct correlation to on-chain bytes rather than how rich the output is, both are valid though.
I certainly take that point of view on board. My sense is that you can't get around the fact that this is basically measuring wealth, in the sense that even if you correlate specifically to chain space, that still is specifically something that costs, and so the richer person can do more of it. The main idea of this RIDDLE system to me, is that you can make a large nonlinear cost to attack, versus a minimal to zero cost to use honestly. The closer we get to that model the happier I'd be.
P.S. the math isn't rendering properly for me on many parts of the document, probably some syntax errors to fix.
Yeah, usually that's the reason, but here the new github markdown latex parser was actually genuinely kind of losing it. It was perfect a day or two before then went crazy s.t. I had to write $\\ x $ instead of $x$ in a large number of places - no joke. Anyway I "fixed" it as soon as I saw it, it seems almost perfectly readable now.
Having spent some time reading it, I now think that Groth's 2014 construction as described in How to leak a secret and spend a coin would do the job of creating a logarithmic sized ring signature using only the ECDLP. Specifically, you can create a ring sig on
That could mean that figures of 1k-20k+ keys could be more practical, albeit one has to consider the computational cost of signing and verifying too.
Afaik Monero research here into sublinear ring signatures was based on similar ideas, though I haven't read and understood that paper yet.
Following up on the previous, here's my attempt at a simple proof of concept in Python: https://gist.github.com/AdamISZ/77651979025d16b778494047c86c3a7c
Basically you have about 1.9kB for a ring size of 256 secp256k1 keys, and 2.3kB for 1024 keys. The latter takes about 10-13 seconds (and the former, maybe 3 seconds), but my algorithms are laughably bad and it's in Python, I'd expect it to be about 2 orders of magnitude faster if done properly, and in C :) (also this is for sign + verify together, and of course, ignores any potential batching benefit verify side).
The paper, obviously, discusses the performance scaling in some detail.
(*edited because had got byte sizes wrong)
Editing to note: to go from ring signatures to linkable ring signatures, I should note, there is a simple transformation as explained in the paper: commit, instead of to 0 with randomness r, to S with randomness r, and then form a ring signature over each key in the ring added to C(-S, 0).
The idea here is that S are effectively 'serial numbers' of the 'coins' or tokens represented by the user's key, and therefore are one time and function like key images.
This is somewhat similar to Rate Limiting Nullifiers a zkSNARKs construct
Rate Limiting Nullifiers
Thanks @sambacha for that breadcrumb! Some pretty interesting ideas there.
Very excited to see this progress, this seems like an excellent way to improve Bitcoin-based auth protocols with Sybil-resistance. Would love to see something like this implemented in Auth47 or lnurl-auth long-term!
Just FYI, these issues may be relevant if you decide to go the route of decoy binning or deterministic decoy selection, as this is a recent topic of discussion within the Monero community:
monero-project/research-lab#84
monero-project/research-lab#86
monero-project/research-lab#87
Enforcing a decoy selection algorithm would be ideal if at all possible, especially as you don't deal with re-org issues etc. in this proposal as it's not publishing transactions. That way authenticators would be bound to best-practices for both privacy and Sybil-resistance.