This is the proof that the number of 1's in the transaction count, excluding the extra transaction, determines the number of digests that need to be provided for the Merkle branch.
Define C(n) as the number of digests needed for the Merkle branch if there are n leaves
The assumption is that
C(n) = NumberOfOnes(n - 1)
Base Case
If there is just one digest then that is the root, so no additional digests are required.
C(1) = 0
C(1) = NumberOfOnes(1-1) = NumberOfOnes(0) = 0
The assumption holds for C(1)
Odd Case
If n is odd, then the last digest is repeated. This means that no branch digest is required.
C((n + 1)/2) = C(n) + 0
For the assumption to hold,
NumberOfOnes((n + 1)/2 - 1) = NumberOfOnes(n - 1) for n odd
This is the same requirement as
NumberOfOnes(((n + 1) + 1)/2 - 1) = NumberOfOnes((n + 1) - 1) for n even
NumberOfOnes((n + 2)/2 - 1) = NumberOfOnes(n) for n even
NumberOfOnes((n + 2 - 2)/2) = NumberOfOnes(n) for n even
NumberOfOnes(n/2) = NumberOfOnes(n) for n even
The is true since right shifting an even number by 1 causes it to be divided by 2 without any 1's being lost.
This means that if the assumption is true for (n+1)/2, then it is true for n, when n is odd.
if n > 1 and n is odd, then (n + 1) / 2 >= 1, as (n + 1) >= 2.
Even Case
If n is even, then the last digest is not repeated. This means that a branch digest is required.
C(n/2) = C(n) - 1
For the assumption to hold,
NumberOfOnes(n/2 - 1) = NumberOfOnes(n - 1) - 1 for n even
This is the same requirement as
NumberOfOnes((n + 1)/2 - 1) = NumberOfOnes((n + 1) - 1) - 1 for n odd
NumberOfOnes((n + 1 - 2)/2) = NumberOfOnes(n) - 1 for n odd
NumberOfOnes((n - 1)/2) = NumberOfOnes(n) - 1 for n odd
This is true, since if n is odd, subtracting 1 from n has the effect of setting the LSB to zero. The divide by 2 shifts everything one to the right without changing the number of ones.
This gives one fewer one relative to n, as required.
This means that if the assumption is true for n/2, then it is true for n, when n is even.
If n > 1 and n is even, then n/2 >= 1.
Conclusion
The assumption is true for n = 1.
If it is true for 1 <= n < k, then it is true for k by one of the above two cases.
By induction, the assumption is true for all n >= 1.
Topic: Auxiliary Header - Improved Proposal (Read 1134 times)
This is based on the proposal I made a while back. It is a process where the header size can be increased. The cleanest way to do it would be a hard-fork change to the Merkle root.
Merkle_root = Hash(old merkle root | hash aux header)
This is a way to do it with a soft fork, but with a loss of efficiency.
The original proposal is here:
https://bitcointalksearch.org/topic/auxiliary-header-abusing-blank-transactions-263996
The problem with that proposal is that it limits the number of transactions to a power of 2.
The basic idea was to have 2^n + 1 transactions. For example, if there was 513 transactions, then the first 512 transactions would contribute to the left child of the root and the 513th transaction alone would contribute to the right child.
This means that you only need to send the 513th transaction and you can compute the right child of the root node in the merkle tree. If you provide the hash of the left child and the hash of the 513th transaction (64 bytes), then you can prove that the 513th transaction is part of the set. You need almost none of the merkle branch.
The 513th transaction would have the hash of the auxiliary header encoded in it. This means that a short proof could be used to prove that the auxiliary header was part of the block.
Normally, when providing a Merkle branch, you need to provide the hash of the path not taken. When moving from parent node to the left child, you provide the hash of right child and vice versa.
However, when dealing with the last transactions, there is only a left child. If there is no right child, then you don't need to send its hash, since it is a copy of the left child's hash. This happens if there is an odd number of nodes for that level.
If there is 513 transactions, then it will happen for every level except the last.
513 -> 257 -> 129 -> 65 -> 33 -> 17 -> 9 -> 5 -> 3 -> 2 -> 1
Only the 2 -> 1 conversion requires the left hash to be provided (as it has an even number of nodes). This means that the Merkle branch path can be encoded with 32 bytes. A block with 512 transactions would ordinarily require around 300 bytes for the path and the requirement would increase a blocks become larger 32 * log2(tx_count).
The difficulty with this proposal is that the number of transactions is limited. A miner with 1023 transactions in his memory pool would only be able to include 512 of them in the block he is mining. Padding transactions could be used to fill up the extra space.
The number of hashes that must be provided is equal to the number of non-zero bits in the binary representation of the transaction count (excluding the extra header transaction).
For example, if there was 11 normal transactions and 1 header transaction, the merkle tree would be as follows
11 transactions + 1: 12 -> 6 -> 3 -> 2 -> 1
11 = 1011 (3 non-zero)
27 transactions + 1: 28 -> 14 -> 7 -> 4 -> 2 -> 1
27 = 11011 (4 non-zero)
This means that the number of hashes that must be provided can be limited by limiting the number of non-zero bits in the transaction count. If the number of non-zero bits was limited to 3, then almost all the transactions could be included (or very few padding transactions would be required).
16: 10000
17: 10001
18: 10010
19: 10011
20: 10100
21: 10101
22: 10110
23: 10111
24: 11000
25: 11001
26: 11010
27: 11011
28: 11100
29: 11101
30: 11110
31: 11111
If 31 transactions were in the memory pool, then only 28 could be included (90.3%).
If 4 non-zero bits were allowed, then 95% of the transactions could be included and normally more than that.
For large tx counts, 3 bits would have a worst case of 87.5% of the transactions included and 4 bits would have a worst case of 93.75.
Merkle_root = Hash(old merkle root | hash aux header)
This is a way to do it with a soft fork, but with a loss of efficiency.
The original proposal is here:
https://bitcointalksearch.org/topic/auxiliary-header-abusing-blank-transactions-263996
The problem with that proposal is that it limits the number of transactions to a power of 2.
The basic idea was to have 2^n + 1 transactions. For example, if there was 513 transactions, then the first 512 transactions would contribute to the left child of the root and the 513th transaction alone would contribute to the right child.
This means that you only need to send the 513th transaction and you can compute the right child of the root node in the merkle tree. If you provide the hash of the left child and the hash of the 513th transaction (64 bytes), then you can prove that the 513th transaction is part of the set. You need almost none of the merkle branch.
The 513th transaction would have the hash of the auxiliary header encoded in it. This means that a short proof could be used to prove that the auxiliary header was part of the block.
Normally, when providing a Merkle branch, you need to provide the hash of the path not taken. When moving from parent node to the left child, you provide the hash of right child and vice versa.
However, when dealing with the last transactions, there is only a left child. If there is no right child, then you don't need to send its hash, since it is a copy of the left child's hash. This happens if there is an odd number of nodes for that level.
If there is 513 transactions, then it will happen for every level except the last.
513 -> 257 -> 129 -> 65 -> 33 -> 17 -> 9 -> 5 -> 3 -> 2 -> 1
Only the 2 -> 1 conversion requires the left hash to be provided (as it has an even number of nodes). This means that the Merkle branch path can be encoded with 32 bytes. A block with 512 transactions would ordinarily require around 300 bytes for the path and the requirement would increase a blocks become larger 32 * log2(tx_count).
The difficulty with this proposal is that the number of transactions is limited. A miner with 1023 transactions in his memory pool would only be able to include 512 of them in the block he is mining. Padding transactions could be used to fill up the extra space.
The number of hashes that must be provided is equal to the number of non-zero bits in the binary representation of the transaction count (excluding the extra header transaction).
For example, if there was 11 normal transactions and 1 header transaction, the merkle tree would be as follows
11 transactions + 1: 12 -> 6 -> 3 -> 2 -> 1
11 = 1011 (3 non-zero)
27 transactions + 1: 28 -> 14 -> 7 -> 4 -> 2 -> 1
27 = 11011 (4 non-zero)
This means that the number of hashes that must be provided can be limited by limiting the number of non-zero bits in the transaction count. If the number of non-zero bits was limited to 3, then almost all the transactions could be included (or very few padding transactions would be required).
16: 10000
17: 10001
18: 10010
19: 10011
20: 10100
21: 10101
22: 10110
24: 11000
25: 11001
26: 11010
28: 11100
If 31 transactions were in the memory pool, then only 28 could be included (90.3%).
If 4 non-zero bits were allowed, then 95% of the transactions could be included and normally more than that.
For large tx counts, 3 bits would have a worst case of 87.5% of the transactions included and 4 bits would have a worst case of 93.75.
Jump to: