[bitcoin-dev] RIDDLE: Lightweight anti-Sybil with anonymity in Bitcoin

[bitcoin-dev] RIDDLE: Lightweight anti-Sybil with anonymity in Bitcoin

[AdamISZ]

List denizens,

As per the title, a suggested protocol for doing anti-Sybil that isn't too demanding for the users, but actually keeps a decent level of privacy.

Notice how it's mostly focused on a user/customer of a service/product/website, but it could conceivably useful in e.g. anti-Sybil in things like Lightning.

Sorry that as usual I write rather long but there are several conveniently arranged sections you can click on :)

https://gist.github.com/AdamISZ/51349418be08be22aa2b4b469e3be92f

(with apologies for my backronym-ing sins)

Cheers,
waxwing/AdamISZ


Sent with Proton Mail secure email.

Re: [bitcoin-dev] RIDDLE: Lightweight anti-Sybil with anonymity in Bitcoin

[AdamISZ]

Just a small update to those interested:
I migrated the gist due to failures of github's new equation formatting feature (which unfortunately started just when I published this gist!), to [1](but comments still on the gist please, or here).

Secondly, I did some research (including toy code) into sublinear ring signatures and Groth/Kohlweiss 2014 can give logarithmic scaled ring signatures, whose security is reducible to that of the Pedersen commitments (essentially ECDLP). I made a note on what this looks like concretely here [2], TLDR 1 o 2 KB for 256-1024 keys. Open question how much the computational load matters. (Ring sig + key image I think is effected via ring sig + "spend a coin" part of "how to leak a secret and spend a coin", in the language of the paper).

The above paragraph is mentioned of course to address the question of how practical it might be to get genuinely big anonymity sets. In short, it might be practical. Again to mention: though bilinear pairings crypto could give substantially more efficient constructions, that would not work on 'bare' secp256k1, though there might be a sensible way of 'transferring' over to other curves (I'll leave that to others to figure out!).

[1] https://reyify.com/blog/riddle
[2] https://gist.github.com/AdamISZ/51349418be08be22aa2b4b469e3be92f?permalink_comment_id=4210892#gistcomment-4210892

Cheers,
AdamISZ/waxwing




Sent with Proton Mail secure email.

------- Original Message -------
On Sunday, June 12th, 2022 at 18:04, AdamISZ via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:


> List denizens,
>
> As per the title, a suggested protocol for doing anti-Sybil that isn't too demanding for the users, but actually keeps a decent level of privacy.
>
> Notice how it's mostly focused on a user/customer of a service/product/website, but it could conceivably useful in e.g. anti-Sybil in things like Lightning.
>
> Sorry that as usual I write rather long but there are several conveniently arranged sections you can click on :)
>
> https://gist.github.com/AdamISZ/51349418be08be22aa2b4b469e3be92f
>
> (with apologies for my backronym-ing sins)
>
> Cheers,
> waxwing/AdamISZ
>
>
>
> Sent with Proton Mail secure email.
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] RIDDLE: Lightweight anti-Sybil with anonymity in Bitcoin

[AdamISZ]

A quick summary on a lot of study I've done recently on this topic.
My last blog [1] was showing that you could concretely make logarithmic sized ring sigs on taproot keys (and built on the explanation and code of Groth/Kohlweiss [2] in the previous blog [5]).
I left as an outstanding question, how to get one/N time usage of these ring signatures, with key images.

So this can definitely be addressed using something like Noether & Goodall's Triptych [3].

The right context for Triptych:
The GK paper [2] just referenced is the core idea: bit decomposition of index. Then, Bootle et al. in "Short Accountable Ring Signatures Based on DDH" in 2015 [4] found a significant further efficiency/compaction by generalising the concept a bit: using an n-ary decomposition and delta-functions as a way to identify the index with the correct digits in n-ary. They used this to form a new "accountable" ring sig based on El Gamal ciphertexts.
Then in 2020 we have Triptych: it takes the n-ary decomposition as above, and adds one more element: a key image, as in the basic cryptonote , LWW, LSAG design.
Of note is that Bootle et al. claim their construction is "2.8 times smaller" than the GK [2] design (which is ~ 7log_2 N + 1 size, so in practice maybe 2.5kB for 2000 keys for example). I mention this because although I *believe* the same key image appending idea would work with GK [2] design, there's no point trying to do that, because Bootle et al. is just more compact and already achieves the same thing.

Adding in the key image needs more space in the proof of course, but only by less than a factor of 2 (just some commitment and response duplication in the sigma protocol).

So the endpoint of the research, for now, is that Triptych [3] seems to give both things we need: first, a key image, which is absolutely needed for something like RIDDLE, along with a very compact size for high anon sets.

I'll probably add some code for this at some point to go along with the GK [2] toy code at [6]

Regards,
AdamISZ/waxwing

[1] https://reyify.com/blog/bragging-with-brevity
[2] https://eprint.iacr.org/2014/764.pdf
[3] https://eprint.iacr.org/2020/018
[4] https://eprint.iacr.org/2015/643.pdf
[5] https://reyify.com/blog/leaking-secrets-logarithmically
[6] https://gist.github.com/AdamISZ/77651979025d16b778494047c86c3a7c

Sent with Proton Mail secure email.

------- Original Message -------
On Thursday, June 30th, 2022 at 22:50, AdamISZ via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:


> Just a small update to those interested:
> I migrated the gist due to failures of github's new equation formatting feature (which unfortunately started just when I published this gist!), to [1](but comments still on the gist please, or here).
>
> Secondly, I did some research (including toy code) into sublinear ring signatures and Groth/Kohlweiss 2014 can give logarithmic scaled ring signatures, whose security is reducible to that of the Pedersen commitments (essentially ECDLP). I made a note on what this looks like concretely here [2], TLDR 1 o 2 KB for 256-1024 keys. Open question how much the computational load matters. (Ring sig + key image I think is effected via ring sig + "spend a coin" part of "how to leak a secret and spend a coin", in the language of the paper).
>
> The above paragraph is mentioned of course to address the question of how practical it might be to get genuinely big anonymity sets. In short, it might be practical. Again to mention: though bilinear pairings crypto could give substantially more efficient constructions, that would not work on 'bare' secp256k1, though there might be a sensible way of 'transferring' over to other curves (I'll leave that to others to figure out!).
>
> [1] https://reyify.com/blog/riddle
> [2] https://gist.github.com/AdamISZ/51349418be08be22aa2b4b469e3be92f?permalink_comment_id=4210892#gistcomment-4210892
>
> Cheers,
> AdamISZ/waxwing
>
>
>
>
> Sent with Proton Mail secure email.
>
>
> ------- Original Message -------
> On Sunday, June 12th, 2022 at 18:04, AdamISZ via bitcoin-dev bitcoin-dev@lists.linuxfoundation.org wrote:
>
>
>
> > List denizens,
> >
> > As per the title, a suggested protocol for doing anti-Sybil that isn't too demanding for the users, but actually keeps a decent level of privacy.
> >
> > Notice how it's mostly focused on a user/customer of a service/product/website, but it could conceivably useful in e.g. anti-Sybil in things like Lightning.
> >
> > Sorry that as usual I write rather long but there are several conveniently arranged sections you can click on :)
> >
> > https://gist.github.com/AdamISZ/51349418be08be22aa2b4b469e3be92f
> >
> > (with apologies for my backronym-ing sins)
> >
> > Cheers,
> > waxwing/AdamISZ
> >
> > Sent with Proton Mail secure email.
> >
> > _______________________________________________
> > bitcoin-dev mailing list
> > bitcoin-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev