summaryrefslogtreecommitdiff
path: root/9d/b299528e4573b6910656d27b28871e05e3a85a
blob: 450fe086bfdec90ea82bdc2d6a3f70656e45c9ac (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
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