Published on: 2013-11-15T22:06:48+00:00
In an email conversation, Mark Friedenbach proposed using per-purpose UUIDs to validate data committed to a jagged tree structure. The UUID bits are interpreted as allowed paths (0 = left, 1 = right) from the top of the tree. When building the tree, everything that is going to be committed must use its allowed path. This ensures that the paths won't collide for very many levels on average, and path lengths will remain short. Validating that some given data was committed properly is simple and easy: just check the path and ensure that the directions from the top of the tree followed the spec.Peter Todd suggested using a hash256-to-UUID mechanism explicitly for this purpose. He also mentioned that any large randomly picked integer is fine. He further suggests running the idea past forrestv, as p2pool would need to adopt the standard and there have been some oddness with mining hardware and nonces that would be good to understand.The discussion also revolves around the issue of transiently relayed data, specifically IP addresses. Hearn believes that additional complexity in storing the 256-bit root hash truncated to less in the coinbase output may not be worth it. However, Friedenbach argues that it makes a difference when merged mining, as it allows for double-counting the bitcoin PoW for more than one aux block on the same chain, potentially facilitating aux chain attacks. For merged mined aux chains to have 128 bits of security, 256 bits of hash in the coinbase are required.The idea of using UUID-as-path is appreciated for resolving the problem of sharing alt-chain merkle tree. It is suggested to make the Merkle branch a full 256 bits for proving extra data validity. However, the coinbase hash does not get stored indefinitely, so it is suggested that the data stored in the coinbase output can always be the 256-bit root hash truncated to less. Although the additional bytes may not make much difference, the idea of adding complexity to achieve better results is not entirely dismissed.In the email exchange, Todd proposes defining a standard for using the last txout so midstate compression can be applied in the future. The proposed standard involves generating a random 128-bit UUID for each thing one might want to commit, such as a merge-mined coin, a p2pool share, or a UTXO commitment. The bits of the UUID are then interpreted as an allowed path from the top of the tree. When building the tree, everything that is going to be committed uses its allowed path, resulting in a jagged tree. Validating the data is simple: just check the path and ensure that the directions from the top of the tree followed the spec.Friedenbach responds by suggesting an authenticated prefix tree with level compression, which allows for smaller path validation, traversal, and proof size. He had previously suggested using a hash256-to-UUID mechanism but is now leaning towards simply using the hash of the genesis block directly to identify aux chains. This is because level compression will allow longer keys with the same path length. Mark also mentions that he's in the middle of writing BIPs on this topic among his other tasks. Essentially, Mark's proposal is similar to Todd's, except keys don't necessarily have to be UUIDs. He offers to prioritize finishing this if there is general interest.Todd suggests setting a reasonable limit on actual path lengths and advises making allowed paths block specific by defining them as H(uuid | nonce), with nonce as an option. This could be H(uuid | nLockTime) where Coinbase transactions still have a nLockTime. The message includes contact information for Todd and a digital signature.Hearn suggests a solution to define a short hash in the coinbase that commits to extra data relayed along with block data. This can be stored temporarily in the block database and erased after some time. He also emphasizes the importance of defining a standard for using the last txout, allowing for midstate compression in the future. The proposed method involves generating a random 128-bit UUID for each thing one might want to commit, interpreting the bits of the UUID as an allowed path from the top of the tree, and ensuring that everything being committed uses its allowed path. Unlike the original merge-mining standard, this approach works for alt-coins, extends indefinitely, and is simple and easy to validate given a single merkle-path for each purpose.The email thread ends with a link to a white paper on secure code signing practices for Android apps.
Updated on: 2023-08-01T06:25:31.085024+00:00