I was thinking about ways to solve some of Bitcoin's main problems -- verification is too centralized, miners are too centralized and too powerful, and safe scaling is difficult/limited --, and I came up with this idea for an altcoin which improves things in those areas. Although it does have several downsides, it does not take the usual altcoin route of "fixing" things by introducing tons of centralization and then pretending to be decentralized. I'm proposing it as an altcoin because Bitcoin could probably never be adjusted to work like this (though maybe it could be done as a sidechain). I think that it could work, and I'd love to see someone create it.
The altcoin has block headers similar to Bitcoin's, and similar mining (
or better). Inside of the header is the root of a Merkelized search tree set (ie. it's a B-tree or whatever, but each tree node contains its children's hashes rather than pointers). With this sort of data structure, if you have a block's search-tree Merkle root, and you're in contact with a node which has the full tree for that block, then you can trustlessly get all branches from the tree matching a prefix. Inside of the header is also the root of a Bitcoin-style simple Merkle tree, called the
existence tree.
When receiving a block, nodes verify the format and validity of the block header and sometimes (explained later) some facts about the two trees. But most of the data in block can be anything, and isn't verified.
Search tree keys are composed of a 4-byte application ID followed by application-specific data up to 40 bytes in length. (So search tree keys are 44 bytes long.) Interpretation of search tree data is up to applications.
Application 0 is the normal cryptocurrency application. Other cryptocurrencies or non-cryptocurrencies could use the same block chain, but I will now be describing application 0 only. A block's validity does
not depend on any concept of validity of any data stored in the search tree, including application 0.
The miner of a block creates a coinbase transaction, and inserts into the search tree of the block he's generating the following key:
00000000 | first 8 bytes of hash(coinbase txid | prev-block txid) | coinbase txid. The second field is called the
coin ID. He also inserts the coinbase txid into the existence tree.
When you want to send someone your coins, you create a Bitcoin-style transaction and get some miner to insert into a block the following key:
00000000 | first 8 bytes of hash(concatenate all parent coin IDs) | txid, and you also have to get the miner to insert the transaction's txid into the existence tree.
Upon receiving a transaction, you have to do the following:
1. Verify that
all ancestor transactions all the way back to one or more coinbase transactions form a valid transaction chain (ie. check tx format, signatures, etc.).
2. Query the search tree of each block between and including the blocks which mined each ancestor transaction and its direct children, getting the txids of all transactions in those blocks with coin IDs matching the ancestor transaction. Download all of the transactions with those txids. Verify that none of them have already spent the coins being spent by the child transactions. If two conflicting transactions exist in a single block, the one listed first in the search tree is valid and the later ones are invalid/ignored. An entire application-0 search tree is not invalidated by the presence of invalid transactions.
3. For each ancestor coinbase transaction, query its block for a matching coin ID, and check that all matching transactions are not excess coinbase transactions.
4. For each block that you look at in the above two points, if you have not previously done so for that block, download the entire application-0 part of the search tree for that block and verify that it: 1) is well-formed, including being appropriately balanced; 2) it is below some size limit (which may safely be quite large); and 3) no single coin ID appears more than some arbitrary limit of times. If it fails any of these checks, then the application-0 search tree is invalid and completely ignored, but the block header is still accepted, and other applications could also be accepted. The data downloaded in this step can be discarded after checking, and you only need to do it up to one time for any given block.
5. Check that the incoming transaction is eventually confirmed in both the search tree and existence tree of a block. If it's only confirmed in one tree, then it's not complete.
So you need to download a fair bit of data in order to receive a transaction:
1. All ancestor transactions.
2. All branches of the search tree associated with ancestor transactions.
3. All transactions in those branches with the same coin ID as the ancestor transactions.
4. Zero or one time per block, the full application-0 branch of the search tree.
#2 and #3 should be very small unless you are being targetted for a denial-of-service attack, in which case it should be limited to reasonable levels by the previously-mentioned hard limit on search-table entries per coin ID per block.
#4 should also be fairly small. A block's search tree will be roughly
2 * 44 * n bytes in size, where n is the number of transactions in that block. So at 10x Bitcoin's volume of about 2000 transactions per block, that's 1.76 MB/block, which sounds fine. At 1000 transactions per second, 10-minute blocks would have search trees of 52.8 MB, which is maybe still reasonable considering that normal users would only have to download
some of them when verifying an incoming transaction, and unlike with Bitcoin full nodes, there is no particular time constraint on downloading the data.
#1 will probably be fairly large, but I'm not sure. (I was going to look through the Bitcoin block chain and collect average/median stats for this, but I haven't gotten around to it yet.)
It'll be most robust/reliable if each wallet saves data points 1 through 3 above when receiving a transaction, and then sends it to the next recipient when sending those coins. Then only the sender and recipient in a transaction have to deal with it. This could be done in many cases by associating transaction-sending with sending a file; if you want to pay someone in this altcoin, you'd always send them an email attachment or something. Both parties don't need to be online at the same time. But if this is still too cumbersome, the data could also be provided by third-party archival nodes instead, which would allow for Bitcoin-style "just send to an address" usage.
Fees would be handled by adding Script opcodes
<key> OP_CHECKTREEKEYVERIFY and
<hash> OP_CHECKEXISTENCETREEVERIFY, which return false unless the spending scriptSig is in a block with a search tree containing the prefix
<key>, or if the spending scriptSig is in a block with an existence tree containing
<hash>, respectively. So you'd add a fee to your transaction by creating a separate transaction with an output using the abvove opcodes, thereby paying the miner who mines the search/existence tree key of your original transaction. Miners would have to include in their blocks the paid-for transactions, the fee transactions paying for those transactions, and a transaction spending all fees. These opcodes could be combined with OP_CHECKSEQUENCEVERIFY or similar in order to time-out fees. This type of fee works cross-application, so you could pay a fee for some generic timestamping application via an application-0 fee payment. Since there is no first-class currency, it's also imaginable that you could pay for an application-0 transaction via a payment in a different application.
Note that changes to the currency are much easier under this system,
while remaining substantially decentralized. Changes are always made by modifying the wallet/node software, with no miner interaction. When an old node receives a new-style transaction that it doesn't recognize, it can point to exactly where it sees the problem, and recommend possibly upgrading. For example, if a new opcode is added to Script, old nodes can give the error "Somewhere in the history of this incoming transaction, unknown opcode xyz was used. Maybe an upgrade is needed?". Or if any of the limits on search trees are increased, old nodes would say, "An ancestor transaction cannot be linked to a valid block in this incoming transaction. Some too-large search trees were skipped; maybe an upgrade is needed?" But if people don't want to upgrade, then they don't have to, in which case there will be a currency split and they would be unable to transact with people sometimes. Whenever there is an upgrade that old nodes would reject, the address version should change so that new nodes don't send transactions to old nodes that won't accept it.
The altcoin can easily support Bitcoin's full scripting system, and SegWit (with some modifications) could be added to it, so Lightning and other off-chain systems could be used with it. Such off-chain systems are useful even on a high-capacity block chain because they allow for microtransactions and instant confirmations.
Especially-powerful
supernodes are needed in order to handle the following tasks:
- Hard-reject blocks with missing data, or blocks that are too large.
- Serve historical search trees and recent transactions / existence trees to other nodes.
- (Optionally) Use bloom filters or similar in order to help nodes detect incoming transactions in new search trees
- (Optionally) Store validity data for later checkpoints
- (Optionally) Store all historical transaction data to help nodes with resyncing
The most important thing is that supernodes need to download the data associated with each hash in the existence tree in order to check that it exists. If any data is missing, then they must hard-reject the entire block (including header). If miners are able to include hashes with missing data into the existence tree, then the following attack is possible:
1. A miner send coins to a bank, but secretly also sends the same coins back to himself, keeping this second transaction a secret from everyone, but inserting the txid into the search tree and existence tree of one of his blocks,
before the transaction to the bank.
2. The bank checks for double-spends using the search tree, but one of the transactions with the given coin ID can't be downloaded -- nobody seems to have a copy. Anyone can insert any hash they want into the search tree, so the incoming transaction can't be rejected based on this missing data. So the incoming transaction is accepted.
3. The miner now starts giving people the second conflicting transaction. The bank's version of the transaction is now considered invalid by everyone because it came second according to what anyone can see.
I don't think that there's any way to generate a fraud proof that a txid was missing in the past but is not missing now, so we have to fall back to the mining mechanism. Before building onto them, miners need to check that previous blocks actually have data associated with each hash in their existence trees. If a miner puts a hash into his existence tree without giving out the data for it, or if a miner builds off of such blocks, then these blocks need to be hard-rejected by the economy. Since checking for this requires downloading full blocks (which may be quite large), only supernodes can do this. The fact that only supernodes are doing this rather than the entire economy introduces some fragility, but I think that it's good enough.
When a block is invalid due to missing data, supernodes should at that point and in the future tell their connected normal nodes that that block hash is invalid, and also give them the Merkle branch to the missing txid in the existence tree so that the node can quickly check this with other supernodes. After a node has checked many supernodes for the missing data and failed to find it, he'll mark that block as invalid and reject blocks which build off of it. If the current highest-work chain is invalid due to this, then wallets should refuse to show any incoming transactions relying on blocks after the chain fork as confirmed, since the missing data could still make an appearance.
For similar reasons, the search tree also isn't allowed to be missing. Supernodes download the search tree and make sure that parts of it aren't missing, and similarly reject the block and alert normal nodes if it is.
The reason that there is a separate existence tree and search tree is that some applications on the search tree might not require the same existence guarantees, or might handle it differently.
Due to the above stuff related to proving existence, supernodes need to quickly download all transactions happening on the network, and they also need to quickly download the search tree of each new block. This will require a lot of bandwidth. To prevent only a very small handful of ultra-huge servers from being the only supernodes, a maximum size of block data is necessary. I envision supernodes being located mainly in data centers with "normal" bandwidth limits, not in homes, so the size limit will be set for that. For example, digialocean's $20/month plan has 3TB of monthly transfer, which would allow for 700 MB blocks if the supernode did nothing but download blocks all the time. Supernodes also need to serve data to regular nodes, so maybe a limit of 100 MB would be reasonable for now.
The max size would also be enforced by normal nodes. If a too-large block is produced, then supernodes can prove that it is invalid by giving out a part of the block which sums up to larger than the limit, and then linking all of that data to the block using the block's existence tree. Normal nodes would have to download data roughly equal to the single-block max size, which should be OK for a very occasional thing. Once a block is proven as being too large, it and all blocks building off of it are marked permanently invalid. Since it is rather expensive for a normal node to download full blocks, these fraud proofs might require a small one-time hashcash-style proof-of-work as an anti-DoS measure.
Although supernodes need to download all transactions, they can discard most of the data. They need to store:
1. Full search trees for all historical blocks
2. Recent (past month, maybe) transactions and existence trees in order to give to other nodes
3. (Optionally) A list of valid transactions for later checkpoints. If this is stored, then the supernode also needs to actually verify all transactions, when usually it just needs to check that they exist.
4. (Optionally) Supernodes
can store all transaction data in order to help nodes resync, though this'll require a lot of storage.
Point #1 will be the main point of storage for most supernodes, though the altcoin would need to have a transaction volume 6x greater than Bitcoin's in order to equal Bitcoin archival nodes in storage requirements, so it's not too bad. Point #2 will be large but constant, and #3 will be insignificant. #4 will be massive (5.26TB per year with 100MB blocks), so only a few supernodes will do it, most likely. If senders and recipients save their transaction data, then archival supernodes are only needed in the rare case when someone has a private key but not the transactions which go with it, or when a new archival supernode is syncing.
As an optimization, the node/wallet software can periodically have a list of valid transactions added to it. Then when you send someone a payment, you only need to send them ancestor transactions since the last checkpoint. Not every valid transaction needs to be listed in the software -- only transactions which have unspent outputs. This list should be a snapshot of the state of the system several months in the past, it should only rarely be updated (maybe every year or so), and it should be independently verified by many people running supernodes; then the trust placed in the devs who add the list is fairly low. Unlike many altcoins, this is an
optimization, not a critical component of the system's security.
Important note: In almost(?) all altcoins with a concept of supernodes, the supernodes end up being centralized controllers of the currency. I am
NOT proposing that, and I am going to be very disappointed if someone is inspired to make an altcoin based on this post and then piles a bunch of trust on the supernodes. The supernodes in my design
do not require trust, do not have special keys, do not vote, and anyone can run one and join the network as a first-class supernode. The only requirement is that regular nodes can communicate with
at least one honest supernode. One of the main ideas behind my proposal here is to emphasize individual sovereignty, so
under no circumstances should any decision-making be done by miner or supernode voting. The only acceptable way to make changes is to put a flag day in the node/wallet software and get people to upgrade.
Advantages compared to Bitcoin - Miners are less involved.
- A lot more verification is done is a much more decentralized way.
- Higher capacity is possible with reasonable safety.
- Changes can be made in a way that is in most cases easier and safer, but without sacrificing decentralization.
- You don't have to run a heavy full node in order to get halfway-decent security.
- Other applications can be added to the same PoW chain in a way that is not generally disruptive to other applications.
Disadvantages - Normal users have to download/upload and store a fair amount of data in order to receive/send transactions.
- Normal users verify most things, but not everything. Truly full verification happens only at supernodes, who will be fairly few in number. This is more fragile than Bitcoin.
- You somehow need to get enough independent entities to run supernodes and serve normal nodes. Running one will be somewhat expensive (much more expensive for archival supernodes), and there's no reasonable way to have the protocol directly reward them. Maybe normal nodes will sometimes have to pay a fee in order to access the network.
- Although someone could choose to avoid using checkpoints, in practice the checkpoints will probably become a very important optimization that people will rely on. This is a centralizing force, though if done properly it shouldn't be too bad.
- Anonymity, another big issue, is not addressed at all here, and this idea is probably incompatible with the anonymity technology in Monero, Mimblewimble, or zcash.
(I am calling this general idea "arbchains" because miners are allowed to put
arbitrary, mostly-unverified data in their blocks.)
Show Posts
