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.
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.
@chris-belcher
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?