原文标题：《张韧全面解析 MimbleWimble》 初识 MimbleWimble 大概是两年前，我发现了 MimbleWimble 协议 ，当时就觉得它特别好玩，神秘感十足。 这个协议是以匿名的方式发布在 Bitcoin 的 IRC Channel 里，化名作者的名称取的是伏地魔的名字，而且是法文版《哈利波特》中伏地魔的名字，叫 Tom Elvis Jedusor。作者在 Tor 网络里放了一个 Dot Onion 的 Link，这个 Link 指向一个 TXT 文件，就是 MimbleWimble 协议。作者通过这样的方式更好地隐藏了自己的身份，从此之后便消失匿迹了。 不过他放的协议并没有写完，后来经过 Blockstream 的 Andrew Poelstra 深入的研究，证明了 MimbleWimble 系统的安全性，才算把这个协议真正的完成。所以，这个协议的提出者本身可以占 idea 的功劳，而 Andrew Poelstra 要占一半的功劳。 从密码学家的角度看，在区块链上把所有的交易金额用明文存放，是一个非常没道理的事。而且把所有已经花掉的交易永久的存在硬盘上，才能保证协议本身的安全性，也很浪费。 而 MimbleWimble 巧妙地组合了一些之前的设计，把这两个问题解决了，给人的感觉非常优雅。 定义 MimbleWimble 要理解 MimbleWimble 首先要搞清楚它的定位，它的定位就是 Privacy Coin，一个可以很好的支持隐私的密码学货币。我觉得在 MimbleWimble 之前只有两个 Privacy Coin，一个叫 Zcash，一个叫 Monero。而别的号称自己是 Privacy Coin 的，技术都不够强。 但是 Zcash 和 Monero 具有同样的问题：它们为了自己的隐私，都需要维护一个集合，这个集合里存着所有已经被花掉的交易输出，我们可以把它理解为「作废列表」。 如果要验证一个新的交易是不是有效交易，首先需要检查这个新交易的交易输入是不是在「作废列表」里面，如果这个交易输入已经在「作废列表」里面了，就证明这个交易输入已经失效，而如果没有在「作废列表」里面，就证明这个交易输入是有效的，交易会被矿工承认，紧接着矿工会把这个交易输入放到「作废列表」当中。 所以对于 Zcash 和 Monero 来说，它们都面临着一个很严重的问题——交易输出是永远增长的。一个公网全节点想要验证一个新交易是否有效，必须储存完整的交易数据集合。随着交易笔数的累加，数据量会越来越大，它使用起来会变得非常不友好。 MimbleWimble 协议就没有这方面的问题，它相当于比 Zcash 和 Monero 有更好的 Scalability，可以应付状态增长的问题。 举个例子，应用了 MimbleWimble 协议的 Grin Coin，它的硬盘空间占用非常小，它可以极大的压缩已花费的交易输出所占的硬盘空间。 如果只是简单的把已经花掉的交易输出删除，那么在验证区块有效性时，就无法验证这个区块是否有效，也无法验证交易签名。但是在 MimbleWimble 协议里是不存在这个问题的。 对于 MimbleWimble 来说，把已花费的交易输出和对应的交易输入都删掉以后，完全不影响整个交易图的验证，所有剩下的签名依然是有效的。而且在删掉已经花掉的交易输出之后，整个区块链依然可以通过签名和工作量进行验证。 大家可以简单的理解为这是一种类似 Accumulator 的东西，它可以把过去很多的密码学 Proof 压缩成一个很小的证据，有点像 Merkle Tree，但是会比 Merkle Tree 更加高效，性能更强。 对 MimbleWimble 的 3 个误解 误解 1：压缩空间 = 更好的隐私？ 很多人把 MimbleWimble 压缩硬盘存储空间这个特点当做更好的隐私来卖，但事实上它并不能实现更好的隐私。如果你选择把自己的硬盘空间压缩，而另外一些人选择不压缩，那么他们依然可以得到完整的交易图，可以从里面挖出交易的交易关联。 当然，在删除硬盘存储空间的时候，还是需要保留最新几天的区块原始数据，因为不知道会不会有分叉、双花攻击等这些情况出现。当确定链已经足够长，数据不会被改变时，才能把那些已经确定不会被改变的硬盘空间压缩。 网络中的全节点一般是默认裁剪存储空间的，但是也可以对源代码进行修改，让它不裁剪。 误解 2：单个交易方可以否认某笔交易？ MimbleWimble 协议有一个特性，它的交易构造方式是互动式的，这意味着一笔交易必须要双方参与才能构造完成，这和比特币、以太坊非常不一样。 拿实现了 MimbleWimble 协议的 Grin 举例子，如果我给交易所一笔钱，而交易所不做任何事情，它是收不到这笔钱的。只有当它参与了跟我互动的协议，完整的构造出这笔合法的交易以后，它才能收到这笔钱。 如果它跟我构造了这笔合法的交易，也就证明了它知道这笔交易的存在，所以说不存在交易所给我钱，我可以说没有，这个同样是外界对 MimbleWimble 的一个误会。 误解 3：交易需要交易双方同时在线？ 这个互动式交易并不要求交易双方都在线，交易双方完全可以采取发邮件的方式来完成交易构造。 前段时间我去看了 Grin 的钱包演示，钱包把交易构造过程中的中间数据，都存成一个文件。对于输入的人来说，他可以生成一个文件，然后把这个文件发给交易的接收者。交易接收者收到这个文件以后，可以把文件拖到自己的钱包客户端里，在客户端里构造完成整个交易，再把它作为一个文件发回给交易的发出者，完成交易的构造。所以需要双方参与，但并不代表需要双方同时在线，可以是异步的过程。 MimbleWimble 技术详解 现在我来和大家详细的说说 MimbleWimble 的技术细节。 MimbleWimble 有三个基本组件，第一个基本组件叫 CT （Confidential Transaction），第二个基本组件叫 Coin Join，第三个组件叫 OWAS （One Way Aggregate Signatures）。 刚才我们讲的是 OWAS 中的一部分。现在我从 CT 开始简单的给大家捋一下。CT 最复杂，剩下两个都比较简单。 Confidential Transaction CT 这个 idea 最早由 Blockstream 的 CEO Adam Back 提出。Adam Back 被称为比特币的教父，因为他是挖矿算法 Hashcash 的发明人，他是被中本聪在论文里引用了的人。 对于一个矿工或者公网节点来说，他们最关心的是某个交易是否是有效交易，以及交易并没有造成系统的通货膨胀（没有创造出新钱，比如发出者花出 50 个比特币，接收者接收到的是 50 个而不是 51 个）。除此之外，他们对于交易的具体金额并不关心。 所以 Confidential Transaction 最初的想法就是，是否能把交易金额变成密文，同时保证交易的有效性不受影响。 Gregory Maxwell 是 Blockstream 的另一个 Co-founder，也是比特币最早的五个核心开发者之一，他真正设计了一个这样的协议，以一种方法把交易的金额加密，但完全不影响交易的有效性。 协议把每笔交易的输入或者输出可表达为以下形式：（也叫 Pedersen Commitment） v*G + r*H （其中 v 为金额，r 是一个随机数，代表盲化因子，G 为生成元 1，H 为生成元 2） 这个也叫对交易金额进行盲化操作，交易的「金额」很好理解。生成元 1、生成元 2 是椭圆曲线密码的两个生成元，一个数值在乘以生成元之前是明文，乘以生成元之后，大家可以把它理解为一个经过椭圆曲线密码简单加密过后的密文。这项运算是单项的，虽然大家都知道生成元是多少，但是一旦乘过之后就不能再把它倒推回去，也没有人知道原来的明文是多少，这个难题叫做「离散对数问题」。 盲化因子是交易输入或输出的构造者自己选的随机数，这个随机数只有自己知道，不能告诉别人。 对每一个交易金额进行盲化操作以后的好处就是，它可以保持「加法同态性」，公式如下： （v1G + r2H）+（v2G + r2H）=（v1 + v2） G+（r1 + r2)H （其中 v1、v2 为交易金额 1 和交易金额 2，r1 和 r2 为盲化因子 1 和盲化因子 2，G 为生成元 1、H 为生成元 2） 简单来说就是，对加密后的数字进行加法操作，和对加密之前的数字进行加法操作再把它加密，是等价的。 到目前为止最重要的就是理解什么叫加法同态，就是先做加法后加密，和先加密后做加法，两个不同的运算顺序得到的结果是一样的。一个不知道具体金额的人，依然可以验证交易的有效性，可以验证两个金额加起来是对的。 当我们在交易中需要添加交易费用的时候，它是以明文的形式交给矿工的，并不需要额外对交易费用进行复杂的加解密操作。矿工将 f*G 与交易输出的 Pedersen Commitment 相加，验证是否能够配平交易输入的 Pedersen Commitment （f 表示交易费用的金额）。 知识点：Pedersen Commitment：将明文表示的未花费交易输出（UTXO）数值替换为加密 简单总结一下加法同态的两个好处，一个是无需解密，不知道具体交易金额也可以验证交易有效性，另外一个是可以直接和明文形式的交易费用进行运算，矿工可以直接看到自己的收入是多少，而且可以验证这个等式是有效的。 还有一点是，交易的发出者和交易的接收者，他们彼此都不知道对方的盲化因子，即交易的输入者不知道输出者的盲化因子，而交易的输出者也不知道输入者的盲化因子，但他们知道交易金额。 这会导致的结果是，等式两边交易金额那一项可以被配平抵消掉，但盲化因子这一项无法抵消。如果你把输出减去输入，最后会有一项： （ro-ri）*H （ro 为交易输出的盲化因子之和，ri 为交易输入的盲化因子之和，H 为生成元 2） 我们可以把它起名叫做「余项」。 注：（ro-ri）*H 或者 （ri-ro）*H 等于余项并不重要，取决于项目具体的选择。 在 MimbleWimble 的 Confidential Transaction 里，为了证明这个交易不是胡乱构造的（交易输出者和输入者，的确都知道自己的盲化因子，并没有拿别人的交易输出来构造自己的交易），需要有一种方式来解决。 在比特币里面比较简单，就是直接拿自己的私钥对整个交易做签名，证明这个交易是你参与并构造的。 但 MimbleWimble 方式很新颖——你只需证明你知道盲化因子差即可。 （注：此处的盲化因子差为「交易输出盲化之和—交易输入的盲化因子之和」，下文同样为此概念） 因为输入者和输出者只知道自己的而不知道对方的盲化因子，他们之间需要一个协议来共同证明，两个人的知识加在一起，可以算出盲化因子差。这和直接对整个交易进行签名是等价的，可以证明我没有胡乱构造交易。 换一种方法说，如果我能证明我知道盲化因子差，也就同时完成了对交易的授权签名，而不需要用输入的私钥对交易进行签名。 在 MimbleWimble 里，事实上是用盲化因子差对一个固定的字符串，比如说 0，做签名，证明盲化因子差我知道，然后我同时公布余项。 以上这段的核心是，对盲化因子差值的知识，可以替代比特币传统交易里的私钥。 还有额外的一点，我们需要有一个 Range Proof。 对金额的部分，你需要证明这个金额部分没有负数，因为我们不希望有人构造一个交易，交易输入是 1 交易输出是 2 和 -1，这会凭空制造出一些钱。 为了证明这个交易所有的输出里都没有负数，每个交易输出需要有一个 Range Proof，一个简短的零知识证明，来证明所有的交易输出都小于某个阈值，且都是正的。 给大家一个直观的概念，每个交易输出加密后的密文大概是 33 个 Bytes，但是 Range Proof 现在是 5 KB 左右，而且这已经是经过优化的结果了，因为 Range Proof 相当于是一个零知识证明，它很难做到更短。 Gregory Maxwell 做了第一版的 Confidential Transaction，他完善了 Range Proof，之后斯坦福大学的学生 BenediktBünz 提出了一个改进版的 Range Proof ，比原来 Gregory 的 Range Proof 长度更短，验证速度快。改进版的 =Range Proof 叫做 Bulletproofs，发表在信息安全领域 Top 1 的顶会里。Bulletproofs 让 RangeProof 缩小很多，大小约 700 Bytes。 Pieter Wuille、Gregory Maxwell 都是这篇文章的作者，他们帮助 Benedikt 完成了 Bulletproofs 的实现和测试，这样也意味着最新的密码学进展直接应用到了 MimbleWimble 的 Confidential Transaction 构造里。 我们现在简单回顾一下第一部分，MimbleWimble 有三个基本组件，第一个是 Confidential Transaction，它实现了对金额的加密，直接利用盲化因子差为私钥签名来证明自己对余项的知识，替代了传统的直接用输入的私钥做签名，而且在 Confidential Transaction 中还要附带一个 Range Proof。 Coin Join 现在我们开始讲 MimbleWimble 的第二个组件 Coin Join。 Coin Join 的想法特别简单，当我有两个交易时，每一个交易等式左边和右边都是可以配平的：把两个交易等式的左边加在一起，右边加在一起，还是一个合法的交易。比如说一个交易有输入 1 和输出 1，另一个交易有输入 2 和输出 2。我们构造一个新的交易，这个交易有两个输入，输入 1 和输入 2，有两个输出，是输出 1 和输出 2，它也是一个合法的交易。 Coin Join 最早是由 Gregory Maxwell 提出的，这是比特币早期能够实现更好隐私的方案。 但是 Gregory Maxwell 提出 Coin Join 协议时，大家有一个很大的疑问，就是交易的每个输入和每个输出只有一种配平方法。比如说一个交易的输入是 8 BTC，输出是 3 和 5，另一个交易输入是 20BTC，输出是 10 BTC 和 10 BTC，我们把这两个交易的输入放在一起，输出放在一起，人们依然可以看出来，哪个输出最早是对应哪个输入，所以 Coin Join 本身并没有提供多么好的隐私。 但是当它和 Confidential Transaction 结合在一起，把所有的交易输入和输出都加密了以后，就能够提供非常好的隐私。 Coin Join 协议很简单，但是直接把它和 CT 连在一起会有一个问题，如果用传统的签名方式（每个交易的合法性，用交易输入的公钥所对应的私钥做签名），我们完全可以根据签名所用的地址，来判断哪个输入对应的是哪个输出。 所以 Coin Join 加 Confidential Transaction 就自然地被要求选择另一种签名方式，就是直接用余项做公钥，利用盲化因子的差做私钥，用这个公私钥对对 0 做签名。这就解决了可以直接通过交易的签名，把输入和输出联系在一起的情况。 Zcash 将来是有可能实现零知识证明的智能合约的，只不过会非常的慢。在 Cash 场景下，比特币对智能合约的支持我个人觉得是足够的，因为比特币有一些基本的验证功能，我们把这些功能排列组合，可以完成现实世界非常多智能合约需要的验证任务。 Grin Coin 在设计时的智能合约支持能力，比比特币和 Zcash 都要差。但是这也激励了研究者去思考，在这个没有地址标识，很多交易会被删掉的系统里，怎么够实现智能合约。 Coin Join 还有一个问题，之前我提到对 0 进行签名，如果真的是对 0 做签名，就可以把两个签名直接加在一起，做一个新的合法签名。但是在协议的实际操作过程中，发现用 0 作为签名并不好，而应该对固定格式的字段做签名。 因为每个交易签名的对象不一样，所以并不能直接把这几个签名加在一起。那怎么样能够实现既可以把交易用 Coin Join 连在一起形成一个巨大的交易，又不影响交易验证？连在一起以后，我们有没有办法重构出哪个交易输入对应的是哪个交易输出？ One Way Aggregate Signatures 这就涉及到他的第三项技术，叫 One Way Aggregate Signatures， 单向的聚合签名。 单项聚合签名把盲化因子之差 x 拆成两项 x1 和 x2 ，其中 x1*H 作为公钥公开，当然 x1 本身不公开，需要用签名来证明我知道 x1。 x2 直接公开，证明我也知道 x2 。 x1*H + x2*H 等于之前的余项。 现在将盲化因子之差拆成两项后，x1*H 叫做 Kernel Excess，x2 叫做 Kernel Offsets，Kernel Offsets 就是偏移量。 把一个盲化因子之差拆成两部分有什么好处呢？ 当一个区块里所有的交易，组成一个大的 Coin Join 交易时，可以把那些作为明文公开的 Kernel Offsets，直接加在一起，这样就扔掉了每一笔交易的信息。 而对于那些需要签名的部分，因为签名的部分并不是都对 0 签名，而是对一个固定的字段签名，他们不可以聚合在一起，这些签名需要单独存储。也就是说把 Kernel Offsets 全都加在一起，一个区块只存一个 Kernel Offsets，但是 Kernel Excess 还是分别存。每笔交易的 Kernel 中都存储了一个 Kernel Excess 以及使用 x1 对某个固定字段的签名。 这样做的好处是，当拿到一个巨大的 Coin Join 交易区块时，可以重新把 Kernel Offsets 的聚合项和所有签名合在一起，来验证这个区块里所有交易都是有效的。而因为 Kernel Offsets 已经合在一起了，就没有办法把加在一起的 Offsets 再拆开。我们没有办法知道，每个签名对应的是哪个输入和哪个输出，所以就实现了 One Way Aggregate Signatures。 我再解释一下，One Way Aggregate Signatures 根本的作用是，当你拿到一个区块中的很多交易输入、输出时，你没有办法判断哪些交易的输入和输出原本是一个交易。它的做法是把每个交易的盲化因子之差分成两项，一项用签名证明我知道，另一项直接公布明文证明我知道。而对直接公布明文的那一项，对于所有的交易，可以直接把它们加在一起。 这里我再补充一下 Cut Through 的概念。 因为所有已经花掉的交易输出，在区块里等式的左边出现了一次，右边又出现了一次，所以我们可以把等式两边都有的项都划掉。Cut Through 的概念就是，可以把已经花掉的交易输出在区块里删掉，当有了很多的区块以后，我们可以跨区块的把不同交易的交易输入和输出删掉，从而实现压缩硬盘存储空间的目的。 但是 Mimblewimble 会有几个很难聚合的点，一个是所有交易输出的 Range Proof， 随着时间的推进，Mimblewimble 系统里的 UTXO 会越来越多，而每一个交易输出，都有一个自己的 Range Proof，来证明我这个输出是非负的。 （注：UTXO 并不会随着时间的推移单调递增，这里表达的是 UTXO 随着时间推进，用户数量变多，UTXO 变多） 当你需要去验证 UTXO 的有效性时，需要把这些 Range Proof 从头到尾算一遍，相当于验证单个交易输出有效性的时间和存储空间都要比比特币多一些。 所以 Mimblewimble 计算量和存储空间的瓶颈都是 Range Proof。另外，盲化因子被拆成两项后，每一个新的交易都有自己的签名，这个不可聚合项也是无法压缩的。 当你遍历整个区块链时，它也会影响验证的时间，以上也是最影响 Scaling 的两项。 MimbleWimble 的具体实现——Grin 接下来我们来说一说 MimbleWimble 的具体实现—Grin，它的挖矿算法叫做 Cuckoo Cycle。 Cuckoo Cycle 简单说就是两个很长的哈希表，每个表都有很多节点，以一种伪随机的方式在这两个哈希表当中连上很多根线。 哈希表 1 只能和哈希表 2 连接，哈希表 2 只能和哈希表 1 连接，表 1 的元素之间不能连接，表 2 的元素之间也不能连接。 Puzzle 本身是要找到一个长度正好为 42 的圈，就是表 1 的 A 节点连到表 2 的 B 节点，表 2 的 B 节点连到表 1 的 C 节点，这样连来连去，找出一个长度为 42 的。 这个设计最初的目的是让这个 Puzzle 本身占用尽量多的内存空间后才能开始解。 因为想要知道跟某个表 2 节点连接的有哪些表 1 的点，最好的办法就是先把所有的边都算下来，以某种数据结构保存，接着在这个数据结构里搜索，这样就能保证搜索之前需要先开一块很大的内存空间，以此来避免计算 Puzzle 只和 CPU 的使用有联系，而大的内存空间最初的初衷也是给 ASIC 造成一定的困难。 但是随着时间的发展，大家意识到 ASIC 无论如何都会存在，所以之后根据当时解这个问题最好的算法，做了一些改进，使得 Puzzle 用 ASIC 也可以算。它会在协议的初期选择一个对 ASIC 不太友好的协议，但是两年以后会全部替换成改进版的对 ASIC 很方便的协议。 这里再补充一点，作为一个密码学家的学生（我不是密码学家，但是我老板是），Cuckoo Cycle 让我觉得最震撼的一点是，在设计之初，它只有直觉，并没有数学证明哪个算法一定是最快的。而这些解 Cuckoo Cycle 的算法，都是在 Cuckoo Cycle 已经很有名的时候，大家一起讨论出来的。 所以在没有数学证明时，完全可能出现一种情况，就是突然有一个人发明了一个解 Cuckoo Cycle 特别的快算法，以至于后来所有的 Grin Coin 都让他一个人挖了。这对 Grin 目前来说也是一个问题 这对我来说也是一个教训。在 13 年时，我花了一年的时间试图设计一个自己的 PoW 算法，它和 Cuckoo Cycle 非常接近，但当时折磨我的一点是，我找不到一个数学证明，证明某一个算法解 Puzzle 一定是最快的，所以最后那篇文章我一直都没发。现在想起来觉得很遗憾，因为这种不成熟的 idea 完全可以扔出去让大家讨论，说不定能讨论出一些很好的 idea，不是所有的东西都需要有数学证明的。 所以当我前段时间听到 Cuckoo Cycle 设计时，心里是感慨万千。 到现在为止，有关 MimbleWimble 的细节就讲完了。 
—- 编译者/作者：张韧 玩币族申明：玩币族作为开放的资讯翻译/分享平台，所提供的所有资讯仅代表作者个人观点，与玩币族平台立场无关，且不构成任何投资理财建议。文章版权归原作者所有。 |
硬核：CT、Coin Join、OWAS，全面解析 MimbleWimble 三大组件
2020-04-14 张韧 来源：链闻
LOADING...