Return-Path: Received: from smtp3.osuosl.org (smtp3.osuosl.org [140.211.166.136]) by lists.linuxfoundation.org (Postfix) with ESMTP id 77C39C002D for ; 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 ; 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 ; 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 ; 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 From: AdamISZ Reply-To: AdamISZ Message-ID: In-Reply-To: References: 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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 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