作者：AdamISZ
来源：https://delvingbitcoin.org/t/anonymous-usage-tokens-from-curve-trees-or-autct/862
译者注：如正文所述，本文所描述的技术是在证明自己拥有一个 UTXO 的同时不暴露这个 UTXO 是什么。可以用在闪电网络中广播通道的容量。如能使用，可以大大改善闪电节点的隐私性。
不知从什么时候开始（我认为是我们在 Joinmarket 中引入忠诚保单（fidelity bond）的时候），我一直在研究实现保护隐私的公钥所有权证明的最佳方式。
我也认为，闪电网络也在许多环节面临相同的问题，可能是在解决堵塞的时候，但（有人向我指出）更明显的是在通道的 gossip 中。
我认为，可能有一种优雅的方案，部分地解决了 “在 gossip 通道的时候，我们如何能既不揭晓这些通道背后的 UTXO，又让人们免于虚假通道的（严重）女巫攻击” 的问题。
让我的初步想法（见我在 RIDDLE 上的早期工作** ）难以真正付诸实践的因素是，所有基于环签名（ring signature）的方案都无法实现次线性（sublinear）的验证。粗略地说，它总是要求验证者 “通读” 一个跟环的大小相同的对象。所以，即使一个大小为 1000 的匿名集很好，证据的体积也很紧凑，但匿名集上升到 100 万的量级就完全不可行了。
但 “曲线树（Curve Trees）” 方法就解决了这个问题：你可以把它理解成一种默克尔树，只不过是代数形式的（使用的是点，而非哈希值），这就允许你创建零知识证据（ZKP）（在这里，算术电路使用 bulletproof），描述你放在这棵树上的对象（公钥）。那么，你就可以说，“这个公钥是这组 taproot 输出中的 10 万个公钥的其中之一，但你不会知道是哪一个；然后，我提供的这个 ‘公钥镜像’（可以理解成 token）已经绑定到了这个没揭晓的公钥中，所以我没法把它用在别的地方了”。我后面会介绍这个 “绑定” 是怎么实现的。
它在比特币中的显然应用是 —— 制作 N 个 taproot UTXO 公钥中的其中一个的所有权证明，并且 N 可以是任意大的数字。给定有一些 taproot 输出是粉尘，我们可以假设它是 “没有用的”，你可以设定一个下限值作为过滤器，过滤出有意义的 UTXO。几个月前，我得到的统计数字是这样的：
面额（以聪为单位） 对应 UTXO 的数量（仅限 taproot 输出）
> 5 million 51674
> 2.5 million 81512
> 1 million 154130
> 500k 238060
> 250k 352235
> 100k 800843
> 50k 1043038
> 25k 1333547
> 10k 2853756
> 1000 sat 6084116
> 100 (i.e. ~all) 39034007
所以，比如说，以 50 万聪为门槛，则只有 24 万个公钥，对曲线树来说依然是实用的。
回顾：“绑定”：曲线树证明是一种 “集合成员” 证明，并不保证稀缺性，因为从本质上说，它可以重复使用而不会暴露自己在复用。因此，我加入了一个 DLEQ（离散对数等式证明），类似于 Joinmarket 中的 PODLE（它就像环签名中的 “可链接性”），这就创建了一个额外的曲线点，可以证明你要证明其成员属性的公钥的 “公钥镜像”，而无需公开这个公钥。这里有算法的简介；它用的是完全标准的 sigma 协议技术。
实际上，我做了大量测试，公钥集合的规模从 5 万到 250 万，然后我观察到，验证时间大部分介于 40 到 70 ms（毫秒）之间，虽然这不是合理控制下的科学结果；我的意思是，它还是很快的！从曲线树论文的表一可以看到他们为 secp/secq 循环做的基准测试结果，甚至比这还要好得多。主要的点在于，树结构带来了对数扩展的效果，而 bulletproof 可以批量验证（每条曲线有一个单独的证据），所以扩展效果非常好（很难写出公式来描述它，因为有算术电路；基本上，100 万个公钥在现实中是很容易验证的）。
工作代码在我的 github 库 aut-ct 中。它也被用作曲线树论文作者的基准测试代码的基础。
运行测试应该蛮容易的，我觉得，跟着 README 做就好。有一些玩具一样的小规模和中等规模公钥集合，你可以尽情玩耍。不要细究我的 Rust 代码 : )
我甚至尽可能快地做了一个概念验证网站，是一个论坛，你需要使用一个 taproot 公钥所有权证据来登录：hodlboard 11 。注意，实情是，创建一个证明是非常复杂的，因为你必须能够触及你所拥有的一个 taproot UTXO 的一个私钥，也就是说，至少，还没有任何钱包支持这样的操作（只有 Bitcoin Core，你可以用多条命令来做到！）。不过，这种烦恼跟这个协议的应用场景（比如闪电网络）无关。只有在我们希望用户可以创建这样的证据、并且可以互操作时，才有这样的烦恼。
按照我的理解，很明显，这种办法不是 “一种完整的解决方案”：一个闪电节点想要（还是应该说 “不得不” 呢）广播其通道容量，但这个办法并不能做到这一点（除非以最基础的办法）：你可以在你的一系列 UTXO 中选择一个，也就是说，你可以广播 “一定范围内的数额”。
再来一些技术细节：
- 证据的体积：会有变化，但不多。公钥集合的大小在 $10^4$ 到 $10^6$ 之间时，证据的大小在 3 ~ 4 kB 范围内。树结构本身的差异似乎不怎么影响证据的体积（基准测试的叶子数量从 256 到 1024，深度到 2 到 6）；记住，最终我们总是得到 2 个 bulletproot，因为一条曲线（不论 secp 还是 secq）上的多个证据可以聚合。
- 曲线点在添加到树上作为叶子之前，必须预处理。这是非常重度的计算。处理的目的是为了让从 x 坐标到曲线点的转换是清楚无误的（众所周知的 “y 坐标平局” 问题），但需要使用在算术电路里有效的算法。因为只需要为每个新公钥做一次处理，所以这个时间开销在任何场景中都可以改善，除了从头开始完全免信任地启动、制作一个证据的情形。详细讨论见此处。
- 为了更大的加速效果，可以批处理验证（我认为证明也是如此，但我还不知道怎么做到）；bulletproof 算术电路 ZKP 已经有了，属性是一样的。
- 曲线树基于 bulletproot ZPK，这意味着我们不需要曲线配对（pairing），也不需要 ECDL（椭圆曲线上离散对数难题）以外的假设（并不是说人么一定会拒绝需要其它假设的提议，而是说，以 secp256k1 曲线作为我们的基础，我们真的不想处理配对 *** ）
你可能（也应该）好奇的是，还有别的技术，能够像曲线树一样，为比特币的这个应用场景提供几乎常数级的快速验证吗？最强大的技术，例如，Groth16 及其后继者，都需要曲线配对；见下面的注释。另一种想法是微软提出的 SPARTAN，已经应用在这里，也不要求曲线配对和 ECDL 之外的假设。我简单研究了 SPARTAN，但我 不认为 它强大到能够实现很快的验证。我还没有研究这个领域的 STARK（可扩展的透明知识陈述），可能也是一个方向。
这个想法可以延伸到哪里去？按我的理解，我们也许能将这个曲线树构造跟证书结合起来，比如用在 Wabisabi 中的 KVAC（公钥验证的匿名证书）。如果我们可以做到让一个人能够 独立 地构造一个综合证书 “这是价值 1.7 BTC 的公钥” 并且（a）不能复用价值；（2）无需中心协调服务端；那么 …… 我们是不是就快要满足 “良好的” 闪电网络 gossip 的需要了呢？我并不是很确定我在这一段里讲的东西。
** 虽然我一定程度上摒弃了早期 RIDDLE 的想法，但这是唯一一种我放弃了的数学构造，因为它太慢了 —— 那里关于产生自 (U)TXO 所有权的 token 的想法，我依然认为是有趣的。关于 RIDDLE 的博客
*** 值得展开的是，在一个 封闭 的对等节点系统中，显然你可以让每个人都签名任意一种你喜欢的额外类型的公钥，也包括用在基于曲线配对系统中的公钥。但这会显著降低匿名集形成的 “自发性”，例如，你将无法包括跟闪电节点的运行无关的 taproot UTXO，等等。好处是你可以得到 非常 紧凑的证据，等等。我倾向于认为，3 kB 已经够紧凑了，因为从设计上来说，这样的证据不会有几百万个！
AdamISZ 2024-05-30
https://www.btcstudy.org/2024/05/30/anonymous-usage-tokens-from-curve-trees-or-autct/