delvingbitcoin
Anonymous usage tokens from curve trees or autct
Posted on: May 22, 2024 09:44 UTC
The discussion centers around the limitations of ring signature-based mechanisms due to their failure in achieving sublinear verification times.
The conversation highlights the necessity for either a succinct proof with linear proving time or altering the problem to one that inherently possesses sublinear complexity, such as utilizing a Merkle tree structure. However, an innovative solution presented through the Curve Trees approach offers a promising avenue for trustless setups. This method not only addresses the verification challenge but also showcases impressive keyset sizes ranging from 50K to 2.5M while maintaining verification times primarily between 40 and 70ms.
Further advancements have been made in applying Curve Trees to Monero, leading to even more efficient outcomes. Specifically, verification of one proof has been reduced to 35ms, employing two curves without specialized field implementations yet leveraging crypto-bigint's Residue type; batch verification further decreases this time to 11ms for ten proofs. This efficiency is partly due to an effective algorithm that resolves the "yyy-coordinate tiebreaker" issue within the arithmetic circuit, ensuring that the transformation from xxx-coordinate to curve point is unambiguous. This algorithm, discussed in detail here, allows for the optimization of the initial key setup process, thus mitigating the time cost associated with trustless bootstrapping.
Moreover, the dialogue touches upon the challenge of producing a collision on the layers by hashing negative words and proposes using an initialization generator with a constant coefficient of 1 to avoid negation issues, which would otherwise necessitate solving the Discrete Logarithm Problem (DLP) for both the initialization generator and other generators.
The conversation also distinguishes between Generalized Bulletproofs, which Curve Trees are based upon, and traditional Bulletproofs. Generalized Bulletproofs offer advantages in terms of 'native' operations regarding Pedersen Vector Commitments. Additionally, it's mentioned that Microsoft’s SPARTAN, accessible here, presents another viable approach that doesn't rely on pairings or assumptions beyond the Elliptic Curve Discrete Logarithm (ECDL). However, implementing Spartan might be more resource-intensive due to the need for manual construction on the towering curve.
Lastly, the possibility for users to prove ownership is acknowledged through the re-randomized output key opening. This method leverages an existing Discrete Logarithm Equality (DLEq) proof, which also facilitates linkability, illustrating a comprehensive approach to address both technical challenges and user-centric needs within the cryptographic domain.