path: root/9d/b299528e4573b6910656d27b28871e05e3a85a

Return-Path: <AdamISZ@protonmail.com>
Received: from smtp3.osuosl.org (smtp3.osuosl.org [140.211.166.136])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 77C39C002D
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu, 11 Aug 2022 15:31:56 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp3.osuosl.org (Postfix) with ESMTP id 52BD560A9C
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu, 11 Aug 2022 15:31:56 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 52BD560A9C
Authentication-Results: smtp3.osuosl.org;
 dkim=pass (2048-bit key) header.d=protonmail.com header.i=@protonmail.com
 header.a=rsa-sha256 header.s=protonmail3 header.b=DWYyIJDI
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -1.102
X-Spam-Level: 
X-Spam-Status: No, score=-1.102 tagged_above=-999 required=5
 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
 DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001,
 PHOTO_EDITING_DIRECT=1, RCVD_IN_MSPIKE_H2=-0.001,
 SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=no autolearn_force=no
Received: from smtp3.osuosl.org ([127.0.0.1])
 by localhost (smtp3.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id ybfws8jORclZ
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu, 11 Aug 2022 15:31:54 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org B410160A8B
Received: from mail-4322.protonmail.ch (mail-4322.protonmail.ch [185.70.43.22])
 by smtp3.osuosl.org (Postfix) with ESMTPS id B410160A8B
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu, 11 Aug 2022 15:31:54 +0000 (UTC)
Date: Thu, 11 Aug 2022 15:31:48 +0000
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com;
 s=protonmail3; t=1660231912; x=1660491112;
 bh=ytw2zA6twiWESeFlYWFbjbcZBd+GqnZUJgEpYcbnFuA=;
 h=Date:To:From:Reply-To:Subject:Message-ID:In-Reply-To:References:
 Feedback-ID:From:To:Cc:Date:Subject:Reply-To:Feedback-ID:
 Message-ID;
 b=DWYyIJDIMbVb3y+JimdByrdO8sTn/IDmoxPapgsdSwFhPfUdTWJexzXvn/VQRYsI/
 F6f5zWrC0o0YIp49b2qeN+4l3JlmMbs+k1g9Yv12Oh38zD5JYOqtFyvBLDBicVwhuP
 JdxOsjOj6RhluEqYSimh7mLZx1Vd/ulwDPnjJC9HlNFHTO044SaKNycxtZ6Ea9V5S+
 Nu4ZkOF97mABEasr0TVT20LrcE8iRP6lLWPz4elnmYsBwvBgwyShR88yduhqI64AUe
 ByhbaOGM5aaJTgQ95+7H5CVxM/ql6nVxvFWGfU1Q2Ga8Z0rg3WIMYMDwWt22KbEwM/
 gqaz/fnULJaWQ==
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
X-Mailman-Approved-At: Thu, 11 Aug 2022 15:38:11 +0000
Subject: Re: [bitcoin-dev] RIDDLE: Lightweight anti-Sybil with anonymity in
	Bitcoin
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Thu, 11 Aug 2022 15:31:56 -0000

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