Author: Robert Quattlebaum darco@deepdarc.com
Date: 2015-08-03
This document describes a mechanism for achieving a significant improvement in the efficiency of merle signatures, allowing public keys that are 5% smaller and signatures that are 37% smaller.
The key is to use a larger base representation of the hash instead of base-2, using several hashes-per-digit instead of two.
For example, using base-3 instead of base-2, we can represent the value of a 128-bit hash as 81-trits:
3^81/2^128 = 1.3
With only 81 hashes-per-signature needed compared to 128, we can achieve a substantial reduction in the size of the signature:
# Signature Space Savings
1 - (81)/(128) = 37%
...and a modest reduction in the size of the public key:
# Public Key Space Savings
1 - (3*81)/(2*128) = 5%
This same concept can be used to reduce the size of the signatures even further by using larger bases. However, the size of the public key tends to be just as large, if not larger.
For example, using base-4 the signature size is cut in half, but the public key remains the same size. Using base-5 yields signatures 57% smaller than normal, but the public key is actually 8% larger.