Published on: 2017-06-27T04:13:08+00:00
In a series of email exchanges between Russell O'Connor and Peter Todd, concerns were raised about the security of the SHA-256 compression function with chosen initial values in relation to pruned trees. Todd acknowledged these concerns and stated that there is no reason to believe that the compression function will be secure under such circumstances. It was also mentioned that fixed points can be found for the SHA256 compression function if the attacker can control the initial value.The discussion also involved a proposal for the Merkle tree data structure. O'Connor suggested using the hash of tags in the first argument of the Sha256Compress function as a way to avoid the need for SHA256's padding while still maintaining the Merkle-Damgård property. However, Todd pointed out that this approach is similar to using SHA256 directly and proposed computing the midstate sha256Compress(IV, t) instead of sha256(t). They also discussed the idea of using safe tags to prevent collisions between the Sha256 and MerkleRoot functions, but Todd argued against depending on tag uniqueness as it could lead to unintended collisions. Ultimately, Todd concluded that if a system is designed where collisions don't matter, then collisions between the sha256 and merkleroot functions won't matter either.Another point of discussion involved the security of the SHA-256 compression function with chosen initial values in pruned trees. O'Connor proposed a solution involving putting the hash of the tags into Sha256Compress's first argument, which would hold the Merkle-Damgard property under certain conditions but would lose the ability to avoid collisions between the Sha256 and MerkleRoot functions using safe tags. Todd noted that this issue arises because in pruned trees, the left merkleRoot cannot be guaranteed to be a midstate of a genuine SHA256 hash.In another email conversation, O'Connor and Todd discussed the math operations used in creating a Merkle Root. O'Connor used the symbol "⋅" to represent concatenation and "×" to represent the Cartesian product. Todd asked for clarification on the specific meaning of the Cartesian product, to which O'Connor defined it as pairs of A and B in the sense of type theory used in languages like Standard ML or Haskell. They also discussed the sha256Compress function, its arguments, and its return value.In a discussion on the Bitcoin development mailing list, O'Connor described the SHA256 compression function used in creating Merkle Tries. He suggested a construction where values are already hashed down to 256 bits before being passed in, and tags are used to determine the type of node. This approach improves performance by skipping unary hashes, and there seems to be no downside as long as tags are inexpensive.The email exchanges between O'Connor and Todd revolved around the technical details of Bitcoin's cryptography, particularly regarding the math operations and functions used in the computation of MerkleRoot.In summary, the discussions focused on concerns about the security of the SHA-256 compression function with chosen initial values in pruned trees and proposed solutions involving the use of hash tags and different math operations. The conversations also delved into the specifics of the sha256Compress function and its arguments, as well as the Merkle-Damgård property and the use of safe tags to prevent collisions. Overall, the emails provided detailed insights into the complexities of Bitcoin's cryptography and its Merkle tree data structure.
Updated on: 2023-08-01T20:42:00.085812+00:00