Main Page: Difference between revisions

From twiki
Jump to navigation Jump to search
Line 44: Line 44:
Computing pioneer von Neumann, in addition to his contribution to computer architecture, also penned a study on building reliable system using unreliable components using statistic multiplexing <ref>https://static.ias.edu/pitp/archive/2012files/Probabilistic_Logics.pdf</ref>. Judging from the Bitcoin network's performance to date <ref>https://buybitcoinworldwide.com/bitcoin-downtime/</ref>, von Neumann's theory seems working well.
Computing pioneer von Neumann, in addition to his contribution to computer architecture, also penned a study on building reliable system using unreliable components using statistic multiplexing <ref>https://static.ias.edu/pitp/archive/2012files/Probabilistic_Logics.pdf</ref>. Judging from the Bitcoin network's performance to date <ref>https://buybitcoinworldwide.com/bitcoin-downtime/</ref>, von Neumann's theory seems working well.


The second challenge is infrastructure performance. Since the infrastructure must deploy multiple computing, networking and storage components, unless all components can be fully exploited in any scale, incremental performance delivery is impossible. Thus, von Neumann's statistic multiplexing theory must also apply here. The result is a new computing paradigm: Statistic Multiplexed Computing (SMC). At this front, all existing blockchain protocols fall short for this goal.
The second challenge is infrastructure performance. Since the infrastructure must deploy multiple computing, networking and storage components, unless all components can be fully exploited in any scale, incremental performance delivery is impossible. Thus, von Neumann's statistic multiplexing theory must also apply here. The result is a new computing paradigm: Statistic Multiplexed Computing (SMC). At this front, all existing blockchain protocols fall short.


Infrastructure scalability challenge is automatically resolved once the performance challenge is resolved without negatively impacting reliability.
Infrastructure scalability challenge is automatically resolved once the performance challenge is resolved without negatively impacting reliability.
Line 50: Line 50:
However, monolithic increase may reach some theoretical limits in deliverable performance. Thus, the only remaining challenge is '''Finality''' -- can any blockchain protocol design practically deliver ledger finality in perpetuity for real?
However, monolithic increase may reach some theoretical limits in deliverable performance. Thus, the only remaining challenge is '''Finality''' -- can any blockchain protocol design practically deliver ledger finality in perpetuity for real?


Theoretically, only statistic multiplexed blockchain protocol can meet this challenge. The proof lies in two facts:  
Theoretically, only statistic multiplexed blockchain protocol can meet this challenge. The proof makes two assumptions:  


* The number of available components has no upper bound in time.
* The number of available components has no upper bound over time.
* The computation problem size can expand without a bound in time.
* The computation problem size can expand without a bound over time.


A formal proof requires a quick study of Amdahl's Law <ref>https://en.wikipedia.org/wiki/Amdahl%27s_law</ref> and Gustafson's Law <ref>https://en.wikipedia.org/wiki/Gustafson%27s_law</ref> where the two "laws" seem to calculate complete opposite performance predictions. These laws have been used to build parallel computing systems and multi-processor operating systems and computing clouds.
A formal proof requires a quick study of Amdahl's Law <ref>https://en.wikipedia.org/wiki/Amdahl%27s_law</ref> and Gustafson's Law <ref>https://en.wikipedia.org/wiki/Gustafson%27s_law</ref> where the two "laws" seem to calculate complete opposite performance predictions. These laws have been used to build parallel computing systems and multi-processor operating systems and computing clouds.
Line 59: Line 59:
A careful examination revealed that the two laws are mathematically dependent <ref>https://cis.temple.edu/~shi/wwwroot/shi/public_html/docs/amdahl/amdahl.html</ref> where Amdahl's formulation has a tight peak performance bound <math>\left ( \frac{1}{x} \right )</math> where x = the percentage of serial portion of instructions in a program.  Thus the peak performance of every parallel program is above-bounded to <math>\left ( \frac{1}{x} \right )</math>. When x -> 0, the performance will asymptotically approach infinity. This will only happen when the computing problem size is open. Therefore, the Amdahl's formulation has the power to produce the identical results as the economic rule of diminishing return when the problem size is fixed. It also proves any parallel program can produce infinite performance if the problem size is open.
A careful examination revealed that the two laws are mathematically dependent <ref>https://cis.temple.edu/~shi/wwwroot/shi/public_html/docs/amdahl/amdahl.html</ref> where Amdahl's formulation has a tight peak performance bound <math>\left ( \frac{1}{x} \right )</math> where x = the percentage of serial portion of instructions in a program.  Thus the peak performance of every parallel program is above-bounded to <math>\left ( \frac{1}{x} \right )</math>. When x -> 0, the performance will asymptotically approach infinity. This will only happen when the computing problem size is open. Therefore, the Amdahl's formulation has the power to produce the identical results as the economic rule of diminishing return when the problem size is fixed. It also proves any parallel program can produce infinite performance if the problem size is open.


In practical blockchain applications, the number of transactions to be processed can only increase if the infrastructure is secure, efficient and reliable.




In practical blockchain applications, the number of transactions to be processed can only increase if the infrastructure is secure, efficient and reliable.


These discussions delivered a single conclusion: a statistic multiplexed blockchain protocol can deliver infinitely scalable infrastructure in performance and reliability while data and processing authenticity is guaranteed by the lock-step cryptographic proofs. This surprising result is also applicable to ledger storage. The SMC blockchain protocol promises to hold the true finality of all transactions without size limitation.


These discussions delivered a single conclusion: a statistic multiplexed blockchain protocol can deliver infinitely scalable infrastructure in performance and reliability while the security is guaranteed by the lock-step cryptographic proof. This surprising result is also applicable to ledger storage. The SMC blockchain protocol can potentially deliver infinitely large ledgers to hold the true finality of all transactions.
This leaves consensus protocol the only guardian for natural and man-made disasters.


== Proof of Stake Protocols ==
== Proof of Stake Protocols ==

Revision as of 14:14, 16 June 2023

Welcome to Twiki -- A Toichain wiki

This is the unofficial Toichain wiki site. Content on this site is subject to frequent changes.

Introduction

The blockchain protocol was introduced via a paper entitled "Bitcoin: A peer-to-peer Electronic Cash System" [1] by Satoshi Nakamoto in 2008. Although there were other peer-to-peer file-sharing projects before this time, such as Napster [2] and Bittorrent [3], and other electronic currency attempts, the Bitcoin project demonstrated the strongest staying power compared even to the currently running 23,000+ other blockchains. Unlike the new cryptocurrencies, the Bitcoin is often referred to as "digital gold" for its scarcity, there are only 21 million hard-coded Bitcoins in the protocol. Other protocols (and associated currencies) have different token supply amount and monetary policies.

The most attractive common blockchain features are the decentralized consensus-driven decision making process and step-by-step cryptographic proving system. In addition to cryptocurrencies, there are many applications that can benefit from such a secure store of value with transaction ledger design without any central authority.


Before trying to understand the Blockchain protocol and its variants, it is important to understand the differences between an algorithm and a protocol.


In general, an algorithm is a program that runs on a single computer solving a single problem. A protocol, however, is a program that runs on all computers in parallel solving a single problem. An algorithm must be transformed to run on all computers in parallel solving the same problem before it to be called a protocol. Therefore, protocol development is significantly more difficult than algorithms.

Consensus Protocols

There are two popular types of consensus protocols: Proof of Work (POW) [4] or Proof of Stake (POS) [5]. Others include Proof of Possession(POP)[6], Proof of History(POH)[7]. The design goal of the consensus protocol is to eliminate double-spending, unfairness and code tampering, since most protocols are Open Source. For cryptocurrency applications, hacking and code tampering are difficult to avoid if not impossible. To date, the Bitcoin network using POW has suffered criticism on escalating electricity consumption [8]. The POH network Solana suffered multiple single-point-failure incidents [9]. All consensus protocols are susceptible to 51% attacks [10]. However, since 2009, Bitcoin has been proven the strongest against the common hacks [11]. As the POW difficulty has increased over the years, the probability of 51% attack on the Bitcoin network becomes more difficult.

Cryptographic Proof

The Blockchain protocol relies on UTXO (unspent transaction output) model and lock-step cryptographic proofs to authenticate every transaction. Once spent, the UTXO is destroyed. Double-spending is theoretically impossible. Each proof step must be executed on a script engine running the same protocol on all nodes. The concurrently produced results are confirmed by the consensus protocol mentioned above before committed to the chain.

Blockchain Trilemma

Blockchain protocols have three common aspects: security, decentralization and scalability -- the three terms that do not have precise definitions but intuitively understood [12]. To date, the existing cryptographic tools have been proven effective for transaction security before the introduction of smart contracts. Decentralization is given by the nature of the protocols. In theory, there should be no service downtimes unless the entire network is down and all nodes crash at the same time. The scalability challenge eludes to deliverable performance and transaction finality which remained unclear.


The trilemma was first introduced by Vitalik Buterin[13], one of the co-founders of Ethereum network. The problems are real. There seems no obvious solutions to accomplish all three goals using known methods. Therefore, all proposed solutions revolve around reducing "opportunity costs" focusing only on partial goals.


Treating the blockchain network as an infrastructure for transaction processing, one would find the trilemma was only an extension of the legacy infrastructure scaling performance and reliability dilemma, where "infrastructure reliability" also does not have a commonly accepted definition. Fortunately all these metrics, although important, are non-functional. Every proposed solution can be a "feasible" solution with varying "opportunity costs". There was also no obvious solutions to overcome the dilemma.

Definitions

It helps to define the challenging metrics more precisely as infrastructure design guidelines. For definitions #1 and #2, the word "infrastructure" implies all applications running on the infrastructure.

  1. Infrastructure Reliability: MTBF (mean time between failure) =
  2. Infrastructure Performance:
  3. Infrastructure Scalability: Expanding the infrastructure in number of processors, networks or storage should have incrementally better impacts on reliability and performance.
  4. Record Immutability: For transaction ledgers, all records and changes are final. This is required for blockchain ledger infrastructures.

Protocol Design and Proofs

Before building a robust protocol for infrastructure computing, there are well-known impossibilities and possibilities in physics and computer science that must be thoroughly examined for extreme cases.

The first challenge is infrastructure reliability. A computing infrastructure must deploy multiple components including computing, networking and storage. An infrastructure protocol defines how applications can compute, communicate and store results. A formal proof was found that it is impossible for reliable communication in the face of arbitrary crashes [14]. The laws of physics dictate component reliability [15] that 100% component reliability is not possible. These facts demands the infrastructure protocol (software program) to provide complete component (processing, networking and storage) decoupling from application software. The blockchain protocol proved the feasibility of such protocol. The Internet

Computing pioneer von Neumann, in addition to his contribution to computer architecture, also penned a study on building reliable system using unreliable components using statistic multiplexing [16]. Judging from the Bitcoin network's performance to date [17], von Neumann's theory seems working well.

The second challenge is infrastructure performance. Since the infrastructure must deploy multiple computing, networking and storage components, unless all components can be fully exploited in any scale, incremental performance delivery is impossible. Thus, von Neumann's statistic multiplexing theory must also apply here. The result is a new computing paradigm: Statistic Multiplexed Computing (SMC). At this front, all existing blockchain protocols fall short.

Infrastructure scalability challenge is automatically resolved once the performance challenge is resolved without negatively impacting reliability.

However, monolithic increase may reach some theoretical limits in deliverable performance. Thus, the only remaining challenge is Finality -- can any blockchain protocol design practically deliver ledger finality in perpetuity for real?

Theoretically, only statistic multiplexed blockchain protocol can meet this challenge. The proof makes two assumptions:

  • The number of available components has no upper bound over time.
  • The computation problem size can expand without a bound over time.

A formal proof requires a quick study of Amdahl's Law [18] and Gustafson's Law [19] where the two "laws" seem to calculate complete opposite performance predictions. These laws have been used to build parallel computing systems and multi-processor operating systems and computing clouds.

A careful examination revealed that the two laws are mathematically dependent [20] where Amdahl's formulation has a tight peak performance bound where x = the percentage of serial portion of instructions in a program. Thus the peak performance of every parallel program is above-bounded to . When x -> 0, the performance will asymptotically approach infinity. This will only happen when the computing problem size is open. Therefore, the Amdahl's formulation has the power to produce the identical results as the economic rule of diminishing return when the problem size is fixed. It also proves any parallel program can produce infinite performance if the problem size is open.


In practical blockchain applications, the number of transactions to be processed can only increase if the infrastructure is secure, efficient and reliable.


These discussions delivered a single conclusion: a statistic multiplexed blockchain protocol can deliver infinitely scalable infrastructure in performance and reliability while data and processing authenticity is guaranteed by the lock-step cryptographic proofs. This surprising result is also applicable to ledger storage. The SMC blockchain protocol promises to hold the true finality of all transactions without size limitation.

This leaves consensus protocol the only guardian for natural and man-made disasters.

Proof of Stake Protocols

There are many POS protocol designs.

- Statistic Multiplexed Computing - Statistic multiplexing method was first proposed in 1952 by von Neumann.

- Statistic Multiplexed Blockchain -

References

  1. ↑ https://bitcoin.org/bitcoin.pdf
  2. ↑ https://www.napster.com/us
  3. ↑ https://www.bittorrent.com/
  4. ↑ https://www.investopedia.com/terms/p/proof-work.asp#:~:text=Proof%20of%20work%20(PoW)%20is,a%20reward%20for%20work%20done.
  5. ↑ https://www.investopedia.com/terms/p/proof-stake-pos.asp
  6. ↑ https://csrc.nist.gov/glossary/term/proof_of_possession#:~:text=Definition(s)%3A,associated%20with%20the%20public%20key.
  7. ↑ https://www.infoworld.com/article/3666736/solana-blockchain-and-the-proof-of-history.html
  8. ↑ https://rmi.org/cryptocurrencys-energy-consumption-problem/#:~:text=Bitcoin%20alone%20is%20estimated%20to,fuel%20used%20by%20US%20railroads.
  9. ↑ https://cryptoslate.com/heres-why-the-recent-solana-outage-took-almost-a-day-to-resolve/#:~:text=25%20%E2%80%94%20the%20first%20interruption%20in,3%20minor%2C%20outages%20in%202022.
  10. ↑ https://originstamp.com/blog/has-there-ever-been-a-51-attack-on-bitcoin/#notable-51-attacks
  11. ↑ https://www.theguardian.com/technology/2014/mar/18/history-of-bitcoin-hacks-alternative-currency
  12. ↑ https://sensoriumxr.com/articles/what-is-the-blockchain-trilemma
  13. ↑ https://en.wikipedia.org/wiki/Vitalik_Buterin
  14. ↑ https://groups.csail.mit.edu/tds/papers/Lynch/jacm93.pdf
  15. ↑ Encyclopedia of Physical Science and Technology, Editor-in-Chief Robert A. Meyers, ISBN 978-0-12-227410-7, 2001
  16. ↑ https://static.ias.edu/pitp/archive/2012files/Probabilistic_Logics.pdf
  17. ↑ https://buybitcoinworldwide.com/bitcoin-downtime/
  18. ↑ https://en.wikipedia.org/wiki/Amdahl%27s_law
  19. ↑ https://en.wikipedia.org/wiki/Gustafson%27s_law
  20. ↑ https://cis.temple.edu/~shi/wwwroot/shi/public_html/docs/amdahl/amdahl.html


Consult the User's Guide for information on using the wiki software.

Getting started

Retrieved from "https://smcdev1.ddns.net/twiki/index.php?title=Main_Page&oldid=20"