Delivery-date: Sat, 07 Jun 2025 08:02:35 -0700
Sender: bitcoindev@googlegroups.com
Date: Sat, 7 Jun 2025 07:39:21 -0700 (PDT)
From: waxwing/ AdamISZ <ekaggata@gmail.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Message-Id: <a34c4b4a-b8af-44d3-9b8f-ec525438cc92n@googlegroups.com>
In-Reply-To: <8fb3deaf-417c-4ec9-9d23-424c4926905an@googlegroups.com>
References: <8fb3deaf-417c-4ec9-9d23-424c4926905an@googlegroups.com>
Subject: [bitcoindev] Re: Sybil resistance in different coinjoin implementations
MIME-Version: 1.0
Content-Type: multipart/mixed; 
	boundary="----=_Part_12426_283977031.1749307161576"
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com

------=_Part_12426_283977031.1749307161576
Content-Type: multipart/alternative; 
	boundary="----=_Part_12427_188103395.1749307161576"

------=_Part_12427_188103395.1749307161576
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Hi fd0,

You make some interesting points in these comparisons. I will address a few=
=20
things you say in the article at the end, here, but first I want to discuss=
=20
some background related to aut-ct (and yes this is mostly already implicit=
=20
in your article but for other readers, the following):

I want to expand on something I said when we were discussing this on=20
delving [1]:

There's always in my mind two very distinct threats from Sybilling. The=20
first is that your protocol might subtly (or grossly) depend on=20
non-collusion of participants. For that you want one kind of Sybil=20
resistance.

The second is the problem of free-entry, which can occur even if=20
non-collusion is not a requirement. If anyone can join a protocol without=
=20
real limits, then the resource usage implied when the number of protocol=20
users increases by 1000x can screw up resource utilization. (Bitcoin itself=
=20
deals with this beautifully through implicit PoW dependence of messages to=
=20
be considered valid.)

My feeling when working on the idea of RIDDLE and then later aut-ct was=20
that I was only really addressing or thinking about the 2nd of those two=20
cases. It's not impossible to use a utxo ownership proof to address the 1st=
=20
of the two above, but it's clearly much less strong, by default, than one=
=20
would hope.

Just a pure "I own a utxo" imposes no, or negligible cost. As per the=20
delving post, and in a few other places, I've noted you can impose an age=
=20
and value restriction to bump up the cost. So it's not inconceivable but I=
=20
suspect it's troublesome, and, it tends to fall into the "anything's better=
=20
than nothing" category. While a fidelity bond with a public timeout is more=
=20
convenient specifically because you don't need to have "prepared" it in=20
advance, a long time (so same lockup cost, but in advance).

The actual problems with fidelity bonds are twofold: privacy headache from=
=20
public utxo announcement, and expense (the expense part is unintuitive,=20
but, if a value lock is to impose cost that *specifically prevents Sybils*,=
=20
it's very valuable that it be counted super-linearly in the size of the=20
utxo; otherwise, a high-net-worth Sybiler can split his amount into 100=20
pieces e.g. to get 100 valid entry tokens. Chris Belcher originally=20
proposed and implemented a quadratic scaling [2], but we reduced that=20
default exponent and made it configurable, precisely because the HNW=20
Sybiler (or honest participant) can nearly guarantee participation. It's a=
=20
whole can of worms, though).

So given that, it's very natural to look for alternatives to, or finesses=
=20
on, fidelity bond ideas. Which you do, here, so, coming to some parts of=20
your article:

> Since WabiSabi is a coinjoin implementation based on centralized=20
coordinator, a user must also trust the coordinator not to link inputs and=
=20
outputs.

I can see that being true only in one specific sense: that Wa(bi)Sabi=20
coordinators can Sybil and thus link. Obviously in the default honest mode=
=20
of operation of coordinator this is not true of such systems.

> Joinstr uses aut-ct <https://github.com/AdamISZ/aut-ct> as the primary=20
mechanism for sybil resistance, however fidelity bonds can also be used=20
with aut-ct. There is an initiator who creates the pool and adds sybil=20
requirements to join the pool. Everyone (maker and takers) needs to provide=
=20
the proof for a successful coinjoin.

Interesting idea to blend, but I am left considering an ambiguity:

When you say "fidelity bonds can be used with aut-ct" I *thought* you=20
meant  that: the anon set can be the anon-set of all timelocked UTXOs (that=
=20
may or may not be fidelity bond type), but if you do that then of course=20
you need to form the anon set based on some time-range, I guess? The=20
problem I always had with this was how do we coordinate anything like this=
=20
for the anon set to be big enough. Like, if you did it with aut-ct it would=
=20
either have to be taproot or users publishing (where?) the pubkeys in order=
=20
to make the tree. People need to actually create these timelocked utxos, so=
=20
they need somehow to be told well in advance what the realistic parameters=
=20
are for it. It seems very difficult practically to coordinate and then to=
=20
get to decent privacy, also (in case you commit a big chunk of funds and=20
then only 5 other people do it .. you were hoping 5000, now you have little=
=20
or no privacy from a big cost. Just an example)

But reading further I see you were looking at it the other way; literally=
=20
two separate things, both fidelity bonds, and aut-ct tokens.

> Everyone shares aut-ct proof that proves they own a P2TR UTXO worth=20
0.1-0.2 BTC that is unspent until last block and aged more than 2016 blocks

For me this example illustrates why Sybil-threat type 1 is not well=20
defended by this kind of system. How much does that really cost? It's=20
reasonable to answer "almost absolutely nothing", since you don't spend=20
those coins, and while in a vague, abstract sense they are "locked" (you=20
need some that lasted that long), a well funded attacker could always have=
=20
that amount x10 or x100 sitting *somewhere*. Handwavy, but imo it's only if=
=20
we want to prevent 1000 of those at once that it starts to be in some sense=
=20
"costly". But a Sybil attack on a coinjoin does not need more than N-1=20
participants to Sybil an N-party join, so 1000 is way over the line.

Cheers,
AdamISZ/waxwing

[1]=20
https://delvingbitcoin.org/t/anonymous-usage-tokens-from-curve-trees-or-aut=
ct/862/3
[2] https://gist.github.com/chris-belcher/87ebbcbb639686057a389acb9ab3e25b

On Tuesday, May 27, 2025 at 10:21:42=E2=80=AFPM UTC-3 /dev /fd0 wrote:

> Hi Bitcoin Developers,
>
> I have written a post comparing the sybil resistance of joinmarket,=20
> joinstr and wabisabi. I did not include whirlpool in this post because it=
s=20
> not used anymore. Although it won't be any different from wabisabi.
>
> Its not a long post but written after doing a lot of research. The result=
s=20
> show that joinmarket has good enough sybil resistance. However, joinstr=
=20
> provides better solution.
>
> Feel free to share your feedback.
>
> Link:=20
> https://uncensoredtech.substack.com/p/sybil-resistance-in-coinjoin-implem=
entations
>
> /dev/fd0
> floppy disk guy
>

--=20
You received this message because you are subscribed to the Google Groups "=
Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/=
a34c4b4a-b8af-44d3-9b8f-ec525438cc92n%40googlegroups.com.

------=_Part_12427_188103395.1749307161576
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div>Hi fd0,</div><div><br /></div><div>You make some interesting points in=
 these comparisons. I will address a few things you say in the article at t=
he end, here, but first I want to discuss some background related to aut-ct=
 (and yes this is mostly already implicit in your article but for other rea=
ders, the following):</div><div><br /></div><div>I want to expand on someth=
ing I said when we were discussing this on delving [1]:</div><div><br /></d=
iv><div>There's always in my mind two very distinct threats from Sybilling.=
 The first is that your protocol might subtly (or grossly) depend on non-co=
llusion of participants. For that you want one kind of Sybil resistance.</d=
iv><div><br /></div><div>The second is the problem of free-entry, which can=
 occur even if non-collusion is not a requirement. If anyone can join a pro=
tocol without real limits, then the resource usage implied when the number =
of protocol users increases by 1000x can screw up resource utilization. (Bi=
tcoin itself deals with this beautifully through implicit PoW dependence of=
 messages to be considered valid.)</div><div><br /></div><div>My feeling wh=
en working on the idea of RIDDLE and then later aut-ct was that I was only =
really addressing or thinking about the 2nd of those two cases. It's not im=
possible to use a utxo ownership proof to address the 1st of the two above,=
 but it's clearly much less strong, by default, than one would hope.</div><=
div><br /></div><div>Just a pure "I own a utxo" imposes no, or negligible c=
ost. As per the delving post, and in a few other places, I've noted you can=
 impose an age and value restriction to bump up the cost. So it's not incon=
ceivable but I suspect it's troublesome, and, it tends to fall into the "an=
ything's better than nothing" category. While a fidelity bond with a public=
 timeout is more convenient specifically because you don't need to have "pr=
epared" it in advance, a long time (so same lockup cost, but in advance).</=
div><div><br /></div><div>The actual problems with fidelity bonds are twofo=
ld: privacy headache from public utxo announcement, and expense (the expens=
e part is unintuitive, but, if a value lock is to impose cost that *specifi=
cally prevents Sybils*, it's very valuable that it be counted super-linearl=
y in the size of the utxo; otherwise, a high-net-worth Sybiler can split hi=
s amount into 100 pieces e.g. to get 100 valid entry tokens. Chris Belcher =
originally proposed and implemented a quadratic scaling [2], but we reduced=
 that default exponent and made it configurable, precisely because the HNW =
Sybiler (or honest participant) can nearly guarantee participation. It's a =
whole can of worms, though).</div><div><br /></div><div>So given that, it's=
 very natural to look for alternatives to, or finesses on, fidelity bond id=
eas. Which you do, here, so, coming to some parts of your article:</div><di=
v><br /></div><div>&gt; Since WabiSabi is a coinjoin implementation based o=
n centralized=20
coordinator, a user must also trust the coordinator not to link inputs=20
and outputs.</div><div><br /></div><div>I can see that being true only in o=
ne specific sense: that Wa(bi)Sabi coordinators can Sybil and thus link. Ob=
viously in the default honest mode of operation of coordinator this is not =
true of such systems.</div><div><br /></div><div>&gt; <span>Joinstr uses </=
span><a href=3D"https://github.com/AdamISZ/aut-ct" rel=3D"nofollow ugc noop=
ener">aut-ct</a><span>
 as the primary mechanism for sybil resistance, however fidelity bonds=20
can also be used with aut-ct. There is an initiator who creates the pool
 and adds sybil requirements to join the pool. Everyone (maker and=20
takers)  needs to provide the proof for a successful coinjoin.</span></div>=
<div><span><br /></span></div><div><span>Interesting idea to blend, but I a=
m left considering an ambiguity:</span></div><div><span><br /></span></div>=
<div><span>When you say "fidelity bonds can be used with aut-ct" I *thought=
* you meant=C2=A0 that: the anon set can be the anon-set of all timelocked =
UTXOs (that may or may not be fidelity bond type), but if you do that then =
of course you need to form the anon set based on some time-range, I guess? =
The problem I always had with this was how do we coordinate anything like t=
his for the anon set to be big enough. Like, if you did it with aut-ct it w=
ould either have to be taproot or users publishing (where?) the pubkeys in =
order to make the tree. People need to actually create these timelocked utx=
os, so they need somehow to be told well in advance what the realistic para=
meters are for it. It seems very difficult practically to coordinate and th=
en to get to decent privacy, also (in case you commit a big chunk of funds =
and then only 5 other people do it .. you were hoping 5000, now you have li=
ttle or no privacy from a big cost. Just an example)</span></div><div><span=
><br /></span></div><div><span>But reading further I see you were looking a=
t it the other way; literally two separate things, both fidelity bonds, and=
 aut-ct tokens.</span></div><div><span><br /></span></div><div><span>&gt; <=
/span><span> Everyone shares aut-ct proof that proves they own a P2TR UTXO=
=20
worth 0.1-0.2 BTC that is unspent until last block and aged more than=20
2016 blocks</span></div><div><span><br /></span></div><div><span>For me thi=
s example illustrates why Sybil-threat type 1 is not well defended by this =
kind of system. How much does that really cost? It's reasonable to answer "=
almost absolutely nothing", since you don't spend those coins, and while in=
 a vague, abstract sense they are "locked" (you need some that lasted that =
long), a well funded attacker could always have that amount x10 or x100 sit=
ting *somewhere*. Handwavy, but imo it's only if we want to prevent 1000 of=
 those at once that it starts to be in some sense "costly". But a Sybil att=
ack on a coinjoin does not need more than N-1 participants to Sybil an N-pa=
rty join, so 1000 is way over the line.</span></div><div><span><br /></span=
></div><div><span>Cheers,</span></div><div><span>AdamISZ/waxwing</span></di=
v><div><br /></div><div>[1] https://delvingbitcoin.org/t/anonymous-usage-to=
kens-from-curve-trees-or-autct/862/3</div><div>[2] https://gist.github.com/=
chris-belcher/87ebbcbb639686057a389acb9ab3e25b</div><div><br /></div><div c=
lass=3D"gmail_quote"><div dir=3D"auto" class=3D"gmail_attr">On Tuesday, May=
 27, 2025 at 10:21:42=E2=80=AFPM UTC-3 /dev /fd0 wrote:<br/></div><blockquo=
te class=3D"gmail_quote" style=3D"margin: 0 0 0 0.8ex; border-left: 1px sol=
id rgb(204, 204, 204); padding-left: 1ex;">Hi Bitcoin Developers,<div><br><=
/div><div>I have written a post comparing the sybil resistance of joinmarke=
t, joinstr and wabisabi. I did not include whirlpool in this post because i=
ts not used anymore. Although it won&#39;t be any different from wabisabi.<=
/div><div><br></div><div>Its not a long post but written after doing a lot =
of research. The results show that joinmarket has good enough sybil resista=
nce. However, joinstr provides better solution.</div><div><br></div><div>Fe=
el free to share your feedback.</div><div><br></div><div>Link:=C2=A0<a href=
=3D"https://uncensoredtech.substack.com/p/sybil-resistance-in-coinjoin-impl=
ementations" target=3D"_blank" rel=3D"nofollow" data-saferedirecturl=3D"htt=
ps://www.google.com/url?hl=3Den&amp;q=3Dhttps://uncensoredtech.substack.com=
/p/sybil-resistance-in-coinjoin-implementations&amp;source=3Dgmail&amp;ust=
=3D1749391507074000&amp;usg=3DAOvVaw0C4R_Vnvbwi4xgb0Y9lzL7">https://uncenso=
redtech.substack.com/p/sybil-resistance-in-coinjoin-implementations</a><br>=
<br>/dev/fd0<br>floppy disk guy</div></blockquote></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;Bitcoin Development Mailing List&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:bitcoindev+unsubscribe@googlegroups.com">bitcoind=
ev+unsubscribe@googlegroups.com</a>.<br />
To view this discussion visit <a href=3D"https://groups.google.com/d/msgid/=
bitcoindev/a34c4b4a-b8af-44d3-9b8f-ec525438cc92n%40googlegroups.com?utm_med=
ium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msgid/bitcoind=
ev/a34c4b4a-b8af-44d3-9b8f-ec525438cc92n%40googlegroups.com</a>.<br />

------=_Part_12427_188103395.1749307161576--

------=_Part_12426_283977031.1749307161576--