Motivation
We would like to be able to create proofs that a transaction was indirectly referenced by another transaction without having to provide the full chain of actual transactions between the two.
Solution: Merkle Proofs
From the perspective of a transaction, the tangle looks “like a binary tree” where every parent references two children (with the exception that here, a parent can reference the same child twice). The easiest and most straight forward way to achieve a “proof of inclusion” in such a datastructure, would most probably be a merkle tree like approach, where a sequence of hashes can be used to prove inclusion in the referenced subtangle.
In contrast to normal merkle trees, where only the leafs of the tree carry payload in the form of data, here every node (transaction) has a payload which contains the transaction specific details. To be able to anyway use a chain of hashes instead of the actualy transaction data to “proove inclusion”, we need to modify the way the transaction hash is caluclated. We first define the “payloadFingerprint” of a transaction to be the hash of all its trits excluding the trits used to encode its branch and trunk:
payloadFingerprint(tx) = hash(tx.fullTritsWithoutBranchAndTrunk)
Then we can use this payloadFingerprint in combination with the branch and trunk hashes to form the actual “transactionHash”:
transactionHash(tx) = hash(payloadFingerprint(tx) + tx.branchTransactionHash + tx.trunkTransactionHash)
This way, we can provide a chain of hashes instead of the actual data to derive a transaction hash and therefore use a similar approach as in merkle trees to prove that a transaction was referenced by another transaction.
The only downside of this approach is that we need to hash twice, to calculate the transaction hash of a transaction. Since hashing is an expensive task, I would prefer to find a more efficient way to combine the three hashes (payloadFingerprint, branch, trunk) into a unique transaction hash.
In the binary world, the XORing of hashes is a commonly used mechanism to create such a new unique hash. XORing two numbers with roughly random distribution results in another number still with roughly random distribution, but which now depends on the two values. This is due to the fact, that the output probability for the XOR function is 50% “0s” and 50% “1s” - see example of the LUT:
A B AxB
-----------
0 0 0
0 1 1
1 0 1
1 1 0
The XORing of hashes can be problematic because of the following special cases:
-
H(a) x H(a) = 0
-
H(a) x H(b) = H(b) x H(a)
-
H(a) x H(a) x H(a) = H(a)
Since we have a well defined number of operands, the commutative nature of the XOR operation is not problematic here, but the fact that H(a) x H(a) = 0 is actually a problem. If branch and trunk reference the same transaction, then XORin their hashes results in a complete loss of information regarding the references.
While this is problematic for the binary version of this approach, we can define a custom XOR-like operation for the trinary world that has an equally balanced percentage of output probabilities, but that does not suffer from H(a) x H(a) = 0 but instead behaves like: H(a) x H(a) = H(a) which retains the full “reference information” in these cases. The LUT for this operation looks like this:
A B AxB
-----------
0 0 0
0 1 T
0 T 1
1 0 T
1 1 1
1 T 0
T 0 1
T 1 0
T T T
This “custom” ternary XOR operator now allow us to calculate the transactionHash in a faster way than going through a full hashing procedure a 2nd time in the following way:
transactionHash'(tx) = (tx.branchHash \oplus tx.trunkHash) \oplus payloadFingerprint(tx)
Conclusion
This change will be very cheap and will at the same time provide us with a very powerfull tool. We can now provide “proofs of inclusion” between two transactions without having to present the actual transactions. This will be relevant for the discussed solutions for inter-shard transactions and might also get relevant for the “selective permanodes”.