One Way Aggregate Signatures & Privacy — Revisited
One-way aggregate signatures allow signatures to be freely mergeable across transactions in a way that the inputs and outputs are no longer linked together in the same way that they would be in a single transaction. This adds a degree of privacy to the transactions stored in a block as the linkage is broken when transactions are combined. They were first mentioned by Dr Hoyas Mouto [1] in a paper titled “Increasing Anonymity in Bitcoin”.
The cost to do with is that one must add a new public key for each output in the transaction to the transaction making it bigger than just normal BLS transactions. This is derived from an ephemerally and randomly generated private key that has a one-time use.
The block generating node will collect the individual transactions and assemble them together in a block. The grouped transaction will be different than the simple sum of the individual ones because the individual signatures (which are aggregates in themselves) will be replaced with a single aggregate signature.
In the case where there are many inputs and only 2 outputs (most typical spends), there is not a lot of extra cost to this method over normal transactions since just 2 extra public keys are stored in the transaction.
Detailed Descriptions of Transactions
Now let’s look in detail for a single transaction and what is required
From the above you can see the transaction in question requires revealing 2 public keys and 2 signatures based on those keys. We typically reveal a public key per input for previous payments to public key hashes. For a transaction with 10 inputs, we’d need to reveal 10 public keys and have 10 signatures. As you can see the signature size itself is significant.
Now let’s look at our BLS transaction
For this case, while we have to sign three different times, we can actually combine those signatures so that the size is the same as one signature. In addition because we sign the inputs and outputs separately they are no longer linked together. This gets interesting when we combine two transactions together as shown in the next figure
As can be seen above, not only do we reduce the size by only having 1 signature for 2 input transactions, but it is no longer possible to tell specifically which of the 20 valued inputs are going to each of the outputs.
These small transactions won’t show much benefit in size, however. There will be some benefit though when we combine 100s or 1000s of transactions in a single block as we’ll show below.
Transaction Sizes Details
To determine the size of a legacy DeVault transaction we can use the following formula
size = 146 * number of inputs + 33 * number of outputs + 10;
while the formula for our BLS transactions is
size = 91 * number of inputs + 83 * number of outputs + 110;
The multiplier for the number of inputs is smaller for BLS because we just need to reveal the public key (48 Bytes) + one overall signature.
However, the multiplier for the number of outputs is larger because we add a random public key (48 bytes) per output.
This is illustrated in the following diagrams
While there are pluses and minuses for BLS vs Elliptic Curve Signatures for a single transaction, an advantage that BLS has is that the size of the aggregate of individual transactions will be smaller than just the sum of the sizes. This is because the signatures (96 bytes per transaction), can be aggregated so that only one signature is needed for all of the transactions.
So to compare let’s look at 2 different blocks where they all have 2 inputs and 2 outputs.
BLS size for one transaction = 458 bytes
Legacy size for one transaction = 368 bytes
Block with 1000 transactions
BLS size for aggregate = 36296 bytes
Legacy size for aggregate = 36800 bytes
Block with 10000 transactions
BLS size for aggregate = 362,096 bytes
Legacy size for aggregate = 368,000 bytes
So, you can see that the sizes are roughly the same. However, the benefit of BLS here is that we get confidential transactions.
If we were willing to give up confidential transactions, BLS would have a bigger size advantage, however, we believe that getting confidential transactions on the blockchain without paying a size penalty is ultimately more attractive than just reducing sizes.
Conclusion
With BLS’s support for simple aggregation and through the use of one-way aggregation, thousands of individual signatures can compressed into one and likewise transactions can be consolidated into one also so that individual transactions will be confidential. Due to the advantages of BLS aggregate, we get this benefit without significantly increasing block or blockchain sizes. At this point, the price we pay for use of BLS though is that verification will be slower. The impact of this remains to be seen but there are some comparisons in [2]
References
[1] One Way Aggregate Signatures
[2] Is BLS that slow?
