Date: Thu, 11 Aug 2022 15:31:48 +0000
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
From: AdamISZ <AdamISZ@protonmail.com>
Reply-To: AdamISZ <AdamISZ@protonmail.com>
Message-ID: <utryS1r9tVYCguFAvdt-laVEsHtSPPqaGEuwDMJlptuU9HRVCdLMNlHOiz0Flr7oPxYvsMQQdw858r_7FQ32t5cO3s9lbDx0fYQKRplUh_M=@protonmail.com>
In-Reply-To: <HT3SgKh3WjJhJz9ozfy8E0MuGveya8Grb3SYrmYShZcHTQOPKpIBfArFupyAVV44k3XHNjSaKHmimqX_BCrUsXm5QvadXK5Z_24uGL60KWg=@protonmail.com>
References: <Kq8x6RTAGitSLOir_j1JcWHxTODreQpRTtqfW0NCTrrwTJBHQ9smptiZA1rIbh6aJl9wc_Ca6DvQr7xrMSate62s4r9nmQSypugYYKJXEZY=@protonmail.com>
 <HT3SgKh3WjJhJz9ozfy8E0MuGveya8Grb3SYrmYShZcHTQOPKpIBfArFupyAVV44k3XHNjSaKHmimqX_BCrUsXm5QvadXK5Z_24uGL60KWg=@protonmail.com>
Feedback-ID: 11565511:user:proton
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Subject: Re: [bitcoin-dev] RIDDLE: Lightweight anti-Sybil with anonymity in
	Bitcoin
Precedence: list

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 siz=
ed ring sigs on taproot keys (and built on the explanation and code of Grot=
h/Kohlweiss [2] in the previous blog [5]).
I left as an outstanding question, how to get one/N time usage of these rin=
g 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 ind=
ex. Then, Bootle et al. in "Short Accountable Ring Signatures Based on DDH"=
 in 2015 [4] found a significant further efficiency/compaction by generalis=
ing 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 thi=
s 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, a=
nd adds one more element: a key image, as in the basic cryptonote , LWW, LS=
AG design.
Of note is that Bootle et al. claim their construction is "2.8 times smalle=
r" than the GK [2] design (which is ~ 7log_2 N + 1 size, so in practice may=
be 2.5kB for 2000 keys for example). I mention this because although I *bel=
ieve* the same key image appending idea would work with GK [2] design, ther=
e'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 b=
y 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 giv=
e both things we need: first, a key image, which is absolutely needed for s=
omething 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 f=
eature (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 si=
gnatures and Groth/Kohlweiss 2014 can give logarithmic scaled ring signatur=
es, whose security is reducible to that of the Pedersen commitments (essent=
ially ECDLP). I made a note on what this looks like concretely here [2], TL=
DR 1 o 2 KB for 256-1024 keys. Open question how much the computational loa=
d 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 mi=
ght be practical. Again to mention: though bilinear pairings crypto could g=
ive substantially more efficient constructions, that would not work on 'bar=
e' secp256k1, though there might be a sensible way of 'transferring' over t=
o other curves (I'll leave that to others to figure out!).
>
> [1] https://reyify.com/blog/riddle
> [2] https://gist.github.com/AdamISZ/51349418be08be22aa2b4b469e3be92f?perm=
alink_comment_id=3D4210892#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 convenien=
tly 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