Lightweight anti-Sybil with anonymity in Bitcoin

RIDDLE.md

RIDDLE

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.

@phyro

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 $N$ keys of size roughly $32(7 log_{2}(N))$ bytes using that exact construction. Albeit, that is a specific construction using Pedersen commitments to a value of zero where the secret key is the randomness; I think that to translate it to our setting is likely trivial (for example, if you prove that 1 of $N$ of a set of commitments to zero, $C_i = 0H + r_{i}G$, then those commitments are exactly public keys as we use), but I haven't checked that.
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.