Blockchain Scalability Idea: Private Sparse Merkle Trees
I’ve been thinking off and on about how to address Blockchain scalability. In a previous article I explored using Sparse Merkle Trees and Bloom Filters in a novel way. However the proposal was complicated and suffered from a few issues, like preventing spam from clogging up blocks, that I do not have a solution for.
However I’ve had a new idea recently that is much simpler and, I think, more robust. Let me engage in the act of public brainstorming by writing it down here and collecting feedback.
The idea goes as follows:
A blockchain exists with PoW headers identical to that of Bitcoin.
Each block consists of a header and only a list of the following:
(spender address, Merkle Root hash commitment, ECDSA signature of the hash commitment).
That’s it.
I will call the above a ‘hash commitment’. There is one per spending address per block.
Each hash commitment takes up approximately ~160 bytes in total, allowing for ~6000 commitments per 1mB block. But what is the hash commitment?
Each address, if it has spent coins this block, creates a Sparse Merkle Tree. The tree is structured so that each unique coin has a unique position in the Sparse Merkle Tree. This is easy to achieve; label each unique coin with a unique number, decompose that number into binary, and the 1’s and 0’s correspond to a unique series of twists and turns through a Sparse Merkle Tree (SMT). I proposed a similar scheme, in which each token has a unique position in which all its transactions must be published in a SMT, in my previous article.
I should add, my scheme assumes non-fungible tokens. Think of coins like quarters, dimes, pennies, etc. Each coin is unique and has a linear history. There may be ways to construct a fungible scheme on top of what I’m proposing, just as we exchange money through sets of quarters, dimes, dollar bills, etc, but for simplicity assume non-fungible tokens for now.
When an address sends a token, it creates an ECDSA-signed transaction similar to Bitcoin’s today. This transaction is hashed and inserted into the correct leaf position in that address’s SMT, at the correct token-address leaf.
When Address A sends a token to Address B, Address A publishes a signed hash commitment to the blockchain in block N. Address A must now send Address B supplemental information proving that the token was transferred within block N. This consists of a Merkle Path from the correct token-address-leaf to the hash commitment, as well as the actual signed transaction itself. Address B verifies that the hash commitment is correctly signed, that the transaction is valid, and that it is a member of a valid Merkle Path to the hash commitment. This proves a few things
- Address A sent the token to Address B
- Address A couldn’t have double spent the token within Block N. There is only 1 valid place to put the transaction hash in the SMT and that place was occupied by the transaction to Address B.
Let’s say that we are convinced that Address A received the token at some historical Block M. Address A must also prove to recipient Address B that the token was not spent between blocks M and N. This can be done in the following way: for any hash commitments published by Address A between blocks M and N, Address A must provide a Merkle Path showing a NULL result at the correct token-address position in the corresponding SMT. If there are no hash commitments in certain blocks, no proofs are necessary since no spends are possible. Since Address A constructed all its own Merkle Trees, it can always prove membership or non-membership through Merkle Paths. So basically address A proves that nothing was published at the token-address position in any SMTs between blocks M and N.
Now we have sufficient proof that Address A sent the token to Address B without double spends. We’re not quite done. The last step is to prove the entire history of this particular token, including transfers between previous owner addresses. Address A should keep an append-only record of these proofs and forward them to Address B. Each time a token is transferred, its individual history is appended with additional proofs for new transactions. So if token T was originally mined at Block X to Address C, then transferred to Address D, then to Address A, then to Address B, each transfer event appends additional Merkle Path proofs to the history of the token. Each receiver must verify the entire proof history to be convinced of validity.
This scheme offloads a large amount of computation and data-transfer off-chain between participants, rather than sharing across the whole network. Let’s estimate computation and data-transfer costs, as well as peak network capacity.
To start off, all participants should verify all hash commitments in all blocks, as well as all block headers. If we assume 1mB / block / 10 minutes, we get a similar blockchain size to Bitcoin’s (but hopefully a lot more transaction volume capacity).
A receiving address must verify a Merkle Path for each hash commitment in the history of the token. This path can be, at most, log2(token_space_size) hashes long. 64 is a reasonable estimate here. Proving non-membership will involve Merkle Paths that are substantially shorter (because the SMT is pruned). In theory an address can publish a hash-commitment every block, but is likely to do so much less. Let’s say an address publishing 10 times a day produces ~3650 hash commitments over 10 years. This means approximately ~230,000 hashes. This is per-token. Transfers involving multiple tokens will be some multiple of these numbers. And the computational cost will grow over time. Still, this amount of computation seems very limited given the extreme computational efficiency of hashing.
Similarly, a proof, not counting header information, would constitute 3650*64*64 bytes of Merkle Paths according to this example. Plus add in the actual contents of transactions in the history of this token (a separate estimate. A few hundred transfers, perhaps ~20kB). We have a proof of approximately 15mB uncompressed for a 10 year history for 1 token. This is a pessimistic estimate because most Merkle Paths will be very short. If the token is actually transferred once per day, but the sender Address has 10 hash commitments per day, this comes to approximately 3mB per proof per token (assuming that pruned proof-of-non-membership paths are substantially shorter, which is very likely). 3mB proofs are large, but not unreasonable.
The scheme has the advantage of almost infinite transaction volume capacity for any address which has published a hash commitment. An address that publishes a signed Merkle Root can send all or any number of its tokens to an arbitrarily large set of recipients. The sender will have to manage the proofs for each transfer, but this is a cost borne locally not globally by the entire blockchain. An Address could send 1 million tokens to 1 million separate recipients in a single hash commitment in a single block; I believe this is unmatched by any extant blockchain technology. It does not have the limitation of network capacity of the Lightning Network (though I’m a fan regardless). It does have a few limitations. Non-fungibility is not ideal. My scheme does not currently allow for multiple transfers of the same token within a single block, although I can think of no conceptual reason why this is not possible, as it would just increase the proof size / complexity. There is still the limit of the number of hash commitments per block, although this is relatively dense at ~6000 / 1mB.
There are additional features of my proposal which I think are appealing, though less important than sheer transaction volume.
- A sending address includes proofs of individual tokens, not the entire Merkle Tree. This allows the rest of his transactions to remain private; a sender doesn’t have to disclose his other transactions to other recipients. Thus privacy is a built-in, default feature of this protocol.
- One can imagine extensions like multi-party-signed SMTs. If multiple parties jointly publish and sign a single SMT, they can represent more complex transfers of tokens, such as ‘swaps’. This is a tactic to get around non-fungibility. We can sign a SMT jointly that shows a swap of tokens, the same way we swap bills of different sizes when paying with cash, to achieve fungibility.
The main thrust of this idea is to push the work of verifying / proving transactions off-chain, in the interest of blockchain scalability. As far as I can tell, the use of Private Sparse Merkle Trees allows a single address to commit to a large set of outbound transactions. Critically, a sender can prove that a token was not double spent both within the same block, and also in previous blocks.
I’m looking for feedback, corrections, or follow-up ideas. Thanks.
You can contact me on Twitter at Andrew Barisser.
