Hash function requirements for Taproot

Summary:

The Financial Cryptography conference 2020 featured a poster presentation by LLFourn that aimed to demonstrate the security requirements for the tweak hash function in Taproot. The author explained that Taproot requires no new assumptions of SHA256 over what are already made by Schnorr signatures themselves, except when using a non-interactive key generation protocol to produce a Taproot internal key. In this scenario, an additional assumption about SHA256 is needed, which states that it must satisfy a collision resistance that makes it hard to find h_1 - h_2 = d for any d when challenged to find h_1 and h_2 with random prefixes.The author's motivation for creating the poster came from questions raised after discussions held in Taproot Study Group #18. The poster used the Generic Group Model to figure out how the hash function would have to fail for Taproot to be insecure. There are three scenarios/games to consider when asking whether Taproot is secure in the context of Bitcoin: Taproot Forge, Covert Taproot, and Second Covert Taproot.Properties (1) and (2) can be argued succinctly if we prove that Taproot is a secure commitment scheme. Property (2) is more difficult to argue as it depends on the multi-party key generation protocol. To answer the question of what assumptions we are making about the hash function, Neven et al. analysed Schnorr signatures by idealising the group in the "Generic Group Model" (GGM), where they were able to isolate the security requirements of the hash function away from any assumptions being made about the group. Proving that Taproot is a binding commitment scheme in the Random Oracle Model is straightforward. This proves properties (1) and (3). For property (2), the MuSig key generation protocol is considered. If we model the MuSig key tweak hash function as a random oracle as well, then the adversary has to query the MuSig hash oracle to determine the joint key X = X_1*H(X_1||L) + X.Taproot is a way of combining two signature schemes into one public key - Schnorr and Tapscript. Poelstra presented a proof in the Random Oracle Model (ROM) for the security of Taproot. The proof only shows that Taproot forgeries are hard. To prove Taproot was a binding commitment scheme in the Generic Group Model (GGM), a new property called "Chosen Offset Prefix-Collision" (COPC) resistance was introduced. COPC is necessary and sufficient to prove Taproot is a secure commitment scheme in the GGM.There are three independent proofs in the poster for each Taproot security property with MuSig assumed to be the key generation scheme for properties (2) and (3). It is shown that an adversary who forges Taproot openings can be used as a black box to mount a "Random Prefix-Preimage" (RPP) attack against the hash function. For Covert Taproot (MuSig), the adversary is split into two types, and it is shown that the reduction does not work for n-party MuSig. Second Covert Taproot (MuSig) is the only scenario where COPC needs to be hard to ensure this property.The cost of Taproot is mostly borne by theoreticians as they have to consider the implications of it being both a public key and a commitment. The user and Bitcoin as a whole benefit from the complexity it adds to making security claims in the GGM, offering exciting new opportunities for non-interactivity and fungibility over what just Schnorr would provide. The work is not considered a final proof of anything, and anyone who wants to take over this research direction and do a proper job of it is welcome to do so.

Updated on: 2023-05-20T21:52:38.531519+00:00