作者: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/