Rethinking Transactions as Proof of Stake (TaPoS)

in #fractally7 months ago

TaPoS.png

In 2014 I introduced the concept of Transactions as Proof of Stake to secure BitShares and it has been used on Steem, Hive, EOS and many other chains since. Some people consider it one of my biggest contributions to the crypto space.

TaPoS is a technique for securing a network by preventing transactions from being applied to forks other than the one seen by the user at the time they signed the transaction. This protects a network against long-range reorganizations and protects the user from signing a transaction based upon a false view of the world. With TaPoS it is possible for centralized entities to operate a blockchain while ensuring the users that the chain cannot be reorganized without all other users updating their signatures.

TaPoS works by incorporating a small amount of data from a recent block id into the transaction such that any change to the blockchain would invalidate the transaction. A blockchain only has value if the vast majority of the users can see their transactions incorporated so a targeted double-spend attack that attempts to reverse one transaction would also have to invalidate almost all other transactions at the same time. Given this situation it would be trivial for the large mass of users to identify which fork was legitimate and which is illegitimate. On other blockchains a double spend attack would only inconvenience a small minority of users and it would be much harder for the majority to reach broad consensus other than following the longest chain rule (Bitcoin).

Even if it was clear there was an attack, it would be difficult to objectively know which of the double-spend transactions was legitimate and which was not without some other public commitments in each transaction.

TaPoS works by cryptographically incorporating a recent block id into each transaction. EOSIO implements this using 16 bits to represent the lower bits of the block number and 32 bits from the block id to validate the match. Four bytes is not enough to prevent a brute force attack on a single block; however, changing one block would require changing all subsequent blocks until the secret fork is revealed and users start producing transactions on the new fork. This makes the cost of an attack equal to finding many 32 bit hash collisions. Expensive, but not impossible. In this case, the cost grows linearly depending upon how long back a reorganization is attempted. On proof of work chains, the difficulty of a brute force attack would be infeasible as each attempt at finding a 32 bit collision would require the full proof of work difficulty of the block.

While this approach works well against accidental reorganizations and replay attacks on intentionally forked chains, it could not be considered fully cryptographically secure on non-proof-of-work systems where users must still rely mostly upon the security from the byzantine fault tolerance producer set.

New Approach to TaPoS

For Fractally’s new chain we are enhancing TaPoS such that all transactions cryptographic linked to the block cannot be brute force attacked and we are doing this with 50% less overhead per transaction than EOSIO or HIVE. EOSIO and HIVE each use 6 bytes for TaPoS while our new chain only requires 3 bytes.

The secret to the new approach is that every transaction that references a particular block links itself to that block in a different way. For starters, instead of using 2 bytes to reference a block TaPoS uses 1 byte which can reference any of the past 127 blocks or 1 out of every 4096 blocks in the past 6 days. This enables more flexibility for offline signing while still allowing easy reference to any of the recent blocks.

The next 2 bytes are the checksum which requires checking a pseudo-random offset within the block id. This pseudo-random offset can be calculated by using the hash of the transaction with all bytes after the checksum byte (typically in the header) or other similar means. This hash need not be cryptographically secure so long as it is deterministic and well distributed. There is a 1 in 65,535 chance that a fork block will accidentally match the checksum of any single transaction; however, every transaction that references the same block is checking a different part of the block id which means an attacker would have to match 10 of 20 bytes in order to migrate 50% of the transactions. They would have to solve a more difficult proof of work than a bitcoin block to match 95% of the transactions and they would have to do that work 100,000 times faster than the bitcoin blockchain to keep up with 1 block per second. Even if they had the money to afford the electricity, there is not enough hardware in existence to perform that task and the hardware that does exist is already being used for legitimate mining.

If an attacker who managed to control over 2/3 of the block producers wanted to intentionally create a fork to attempt a double spend they would have to drop over 99% of all transactions that reference the block(s) they are rewriting or they would require more computational power than the entire bitcoin network to migrate even a small fraction. Long range attacks would be virtually impossible without dropping 99% of everyones transactions which means no one would have any economic interest in the hypothetical fork.

TaPoS 2.0 and Proof of Work

Proof of work blockchains suffer from a number of known vulnerabilities including selfish mining and any number of attacks that rely upon building an alternative fork in secret and revealing it later.

Using the new approach to TaPoS we can modify the consensus algorithm of Proof of Work such that every transfer produces TaPoS-Coin-Days-Destroyed (TCDD) as a side effect which is calculated as the TaPoS block number of the new transaction minus the TaPoS block number of input tokens transaction times the number of coins on the input.

The “best chain” is the one that has the most TCDD; however, to extend the chain new blocks must also have sufficient proof of work. Any hidden forks would be unable to grow TCDD beyond their own coins and would require the same amount of proof of work as the public chain. Upgrading Bitcoin to support such a feature could be done without a hard fork, meaning old and new nodes could both read transactions which leveraged TaPoS validation. Any hidden forks would be automatically ignored by the new nodes. While old nodes may follow the hidden chain for a little while, little critical infrastructure would recognize it and the old nodes would have to upgrade to recover from the attempted hack. The reduced likelihood of success would likely be enough to prevent any such attempt from occurring in the first place meaning that the network could achieve herd immunity with a sufficient number of critical players adopting the new TaPoS protocol which only requires 3 bytes per transaction.

The end result would be a hybrid-proof-of-work and proof-of-stake system which has all of the advantages of both systems while eliminating many of the disadvantages of either system operating in isolation.

Is TaPoS Useful?

TaPoS clearly has some theoretical benefits, but do any of these benefits provide practical benefits to offset the meager cost? For starters, TaPoS has been in use for years on Hive and EOS but these chains have not seen any hint of a long-range attack. The block producer selection algorithm and other social forces mean that the chance of a successful attack is already quite small.

The secondary use of TaPoS is to facilitate intentional community forks while preventing replay attacks. While TaPoS makes this trivial, it can also be achieved by a small change to the signature verification algorithm as part of the launching of a new fork.

Under Fractally there is a whole new level of subjective accountability via its robust governance processes which would make any attack at the technical level almost pointless with or without TaPoS.

This leaves the primary benefit of TaPoS to securing Proof of Work blockchains and for use by centralized private blockchains. A private company could launch a chain where they are the sole producer of blocks but where the community is the distributed validator of blocks. Utilizing TaPoS the private company would be unable to fork the chain for a double-spend without collusion of a sufficient number of its customers switching to the new fork and invalidating the all of the transactions of its customers during the fork period. This means the private company couldn’t selectively harm customers leaving the only remaining vulnerability of the private chain to be censorship. This censorship, if widespread, could easily be resolved with a community lead fork for a new centralized producer with decentralized validators.

Conclusion

The cost of TaPoS is relatively small and it provides everyone involved a meaningful degree of protection against even the most centralized set of block producers. Its presence means that there is little incentive to even attempt long-range attacks even if those attacks would ultimately only be temporally disruptive. At 1000 transactions per second, the total cost is 3kb per second or about 0.01% of the bandwidth.

It would seem that TaPoS is a low-cost method of eliminating the vast majority of theoretically possible, but likely impractical, attacks against all of the other known consensus algorithms. So for those who value total crypto-graphic and objective security, TaPoS seems like it is worth the time. For companies wanting a centralized blockchain, TaPoS seems to be the best way to provide cryptographic commitment to the past without giving up control over the future. It is probably far more cost effective and secure than publishing your hashes to another public blockchain.

For those who are look at the practical realities relative to the theoretical risks and are comfortable with subjective security, TaPoS is probably unnecessary overhead. That said, there is something to be said for silencing the vocal critics that may scare your customers with theoretical but impractical risks.

For these reasons I believe that TaPoS should be a feature of every blockchain regardless of the consensus algorithm used.


I would like to thank Todd for his contributions to help TaPoS work better with off line signing of transactions.
Sort:  

With TaPoS it is possible for centralized entities to operate a blockchain

homer-kill-urge.jpg

JK

Seems like a good idea considering every new project is inherently centralized.
Certainly all these DEFI projects with constant rugpulls would benefit.

Centralized doesn't automatically mean public.

I like it!

Can you please elaborate on: "1 out of every 4096 blocks in the past 6 days"?
Thanks!

Given block height X including transaction with TaPoS reference (R=200), then the referenced block number would be (int(X/4096)-(R-127))*4096 assuming R > 127. If R <= 127 then it would be X - R.

перевод на русский Переосмысление идеи "Транзакция как доказательство доли (TaPoS)" - https://hive.blog/blockchain/@shakhruz/pereosmyslenie-idei-tranzakciya-kak-dokazatelstvo-doli-tapos

Подписывайтесь на мой телеграм канал чтобы узнавать подробнее о Фракталли и многом другом на русском языке.

Can I create a smart contract or tokens with fractally?