Blockchain Cohomology?

Abstract

The following explores topological models of distributed computing for scalability focused Blockchain technologies1. Applications of these models are provided in terms of emerging Blockchain protocols and scalability approaches as well as programming models allowing type-level veri cation. Existing models of blockchain technology are being expanded to incorporate scalability advancements in distributed computing. However, despite their compatibility, these new approaches lack veri cation methods common in large scale data processing. By connecting topological models of distributed computing to scalable distributed architectures using Homotopy type theory, we create a hybrid topological model applicable to common architectures in Big Data and emerging scalable blockchain technology. Applications are provided across common scalable architectures in distributed computing that are being adopted by new blockchain technology.

Keywords

• Distributed computing
• Homology
• Algebraic topology

Introduction

1.1

Related Work

The following is a literature overview of references used in formulating this work's main results, from a historical perspective.

Topological Models in Distributed Computing Topology is a mathematical eld focused on higher dimensional connective properties of algebraic objects. In the context of distributed computing, these objects are generalizations of graphs, and their connectivity properties related to the computability of distributed algorithms. Exploiting certain topological properties of higher dimensional geometric objects to prove results of distributed algorithms is referred to as the topological approach to distributed computing. Techniques from combinatorial and algebraic topology have advanced characterization of synchronous and asynchronous distributed algorithms as well as their solvability [1{4]. 1 Supported by Constellation Labs * Copyright c 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0)

The rst applications of topology to distributed computing were in deriving the lower bounds for solving the distributed set agreement [ 12 ], which introduced a new paradigm based on algebraic topology for reasoning about asynchronous computations, where at-most one process can fail. The framework consisted of modeling tasks and protocols as simplicial complexes, and applied homology [ 5, 9 ] theory to reason about them. A key feature in this framework is that the exponential number of possible executions can be compactly represented using a static topological object in a model independent manner. In certain systems, such as those explored below relating to blockhain technology and scalability, the simplicial complexes are manifolds [6{8], a special class of simplicial complexes that are intuitive due to their geometric nature. The application of homology theory in these models forms a direct connection to Homotopy type theory [ 9, 10 ], the basis for modern static analysis in software engineering as well as in programmatic proof assistants. This connection is realized by a result known as the Curry-Howard correspondence which is an isomorphism between mathematical proofs and programs. This correspondence allows us to verify programs at compile time, given a type system and typesafe (type preserving) implementation, as is enforced by the functional programming paradigm.

Homotopy Type Theory and Veri cation Homotopy type theory is an

interpretation of constructive type theory that connects logic and topology [ 15 ]. Speci cally, Homotopy theory is a tool for constructing models of systems of logic and constructive type theory is a formal calculus for reasoning about homotopy. Computational implementation of type theory allows computer veri ed proofs in homotopy theory and is the formalism from which static analysis and functional programming emerged from [ 10 ].

Proof assistants and type systems are explicit examples of tools for proofs or programs for which compilation veri es correctness. Their use in mathematics and computer science is increasingly common for managing complex proofs and programs. Examples of the success of proof assistants and type systems respectively include the proof of the Four Color Theorem and the Feit-Thompson Odd-Order Theorem, as well as large pieces of software such as a C compiler and the Standard ML programming language. Homotopy type theory is used in strongly typed programming languages like C and functional languages like Haskell to provide compile time veri cation. The ability to verify a program, especially all aspects of a distributed system before deployment, has been a fundamental advantage that ushered the emergence of Big Data over the last ten years.

Functional Programming and Big Data Big Data [11, 16] refers to appli

cations pertaining to data sets so big that distributing the processing is not an optimization but a fundamental requirement. Given the exponentially increasing amount of data generated by human information systems, the eld continues to grow. It is widely held that the advent of Big Data stems from the MapReduce white paper [ 14 ], which introduced the rst programming model strictly designed for processing and generating large, inherently distributed, datasets.

A programming model is the style and interface used for development and the leading programming model in Big Data, MapReduce, is fundamentally a functional programming model as it is just the combination of :map() and :reduce() operators, which are by de nition declarative functional operations on collections. Functional, as opposed to procedural, programming is a paradigm in software engineering that simpli es veri cation and improves visibility in distributed processes due to statelessness [ 17 ]. If something fails during state transformations developers have to recompile and redeploy their source code, restarting a work ow from scratch. The reason why functional languages encourage scalable software architectures is because of the fact that they eliminate as much shared state as possible from a language. This leads to scalable micro-services or components and these micro-services then scale naturally into larger components. Blockchain Technology and Scalability The rst Blockchain was formulated roughly 30 years ago as a way to time-stamp digital documents [ 13 ]. At its core a Blockchain is an application of a distributed consensus algorithm operating on cryptographically signed data to form a secure append only log; secure in the sense that forgery is computationally intractable. Lately blockchain technology has become popular due to its application in creating cryptocurrencies like Bitcoin, but wider applications in veri able decentralized code execution (provided by Smart Contract platforms like the Ethereum protocol) and open network security (provide by the Constellation protocol) have emerged.

A major limitation in adoption of blockchain applications is an inherent scalability issue due to the fact that traditional Byzantine Fault Tolerant consensus algorithms require serial execution across a distributed system, making concurrency di cult or impossible. New parallelizable consensus algorithms and system architectures have emerged however, based on the design of highly concurrent and distributed data processing tools common in Big Data. These new approaches [ 20, 23 ] lack formal veri cation methods employed by similar tools in both blockchain and the Big Data space however, the creation of which is the focus of the models constructed below. 2

Consensus Protocols

Recent advancements in distributed computing have adopted methods from algebraic topology to formally de ne consensus protocols [ 1, 2 ]. First de ne an execution space as a topological space equipped with a discrete product topology [ 3 ]. De ning a distributed process in terms of topology only requires us to care about the structure of the set of possible schedules of a distributed system [ 4 ]. By de ning an execution space in terms of the homology of Protocol Complexes [ 2 ], de ne a Protocol Complex Sk : Pk q as the q-dimensional standard simplex q = fx 2 Rj xj = 1; xj where P S is the set of all admissible con gurations and S is the set of all possible con gurations.

De ne a consensus protocol P (S) : fSk; @kg as the singular homology of a simplicial chain complex, carried by a group morphism implementing distributed consensus. Let Sk be a simplex con guration at step k and @k be the di erential of a distributed consensus morphism:

P (S) : 0 where Pk = ker@k=im@k+1 and is also an abelian group. Thus, P = (Pk) jk 2 Z is a graded abelian group which is referred to as the homology of a Protocol Complex S. We abuse our notation of P but rectify by noting that an admissible state k is required for anther step k + 1, thus we de ne P as the functor carrying our consensus operator de ned below.

De ne a consensus operator as the group morphism on the singular qsimplex : q ! S k : Sk 1

Pk ! Sk which are continuous on discrete topologies such as q [ 1 ]. De ne homology between con gurations as a measure of divergence given by the di erential q+1 X( 1)i 1( i=1 qi) for continuous functions qi : q 1 ! qj1 i

q + 1 where qi(x1; : : : ; xq) = (x1; : : : xi 1; 0; xi; xi+1; : : : ; xq 1; : : : ; xq)

As the graded abelian group of our Protocol Complex is the simplicial singular homology group and is our homology preserving map, it is trivial to note that homology holds 8k 2 Z, i.e. at morphism k described by the following vertex set

Sk = fvi;0 : : : vi;qg As a corollary of the fact that the geometric realization of a simplicial complex is dually a topological space, due to the vanishing homology up to k, Pk q is k-acyclic, or that there is a consistently forward moving "arrow of time". 2.1

Protocol Topologies

It's possible to layer Protocol Complexes de ned as above with guarantees about consistency as long as continuity is preserved. Our de nition of homology above is veri cation criteria for the ability to exchange con guration states between Protocol Complexes. (2) (3) (4) (5) (6) (7)

Speci cally, a valid 'layering' as the existence of a functoral vertex map between singular homologies (de ned equivalently here as the disjoint subset of Protocol Complexes) l : Sk P ! Sk P +1.

Making use of Homotopy type theory allows us to focus on structure by treating topological characteristics called homotopy groups as primitives. Noting that simplicial complexes together with simplicial vertex maps form a category, if we rede ne our k-acyclic distributed consensus protocol categorically as the functoral carrier we can form a chain complex that adheres to the homology theory of homotopy types [ 5 ].

Let us de ne a 'layering' as a Protocol Topology TP : P , the singular homology of a chain complex of Protocol Complexes carried by a homotopy preserving functor . The Protocol Topology is given by the following chain complex

TP : 0

P where : ker@k =im@k+1 ! @k +1=im@k++11

For Protocol Complex morphisms ; +1 chain homotopy from +1 is a homotopy preserving graded abelian group morphism l : P yielding a vanishing homology, i.e.

! P +1 2.2

Applications: Scale out Networking

Traditional Blockchains have come up short in their ability to support real world use cases, mainly due to scalability issues. In terms of scalability, sharding or partitioned approaches have taken form in improvements to Bitcoin with Lightning [ 21 ] as well as base layer protocols like Zilliqa [ 22 ]. In these approaches, relays or subnets are deployed to ferry larger amounts of transactions into a xed-size con guration state (block). The key to their success is the application of Scale Out Networking [ 11 ], adding another layer to the network topology to bu er and compress data which results in faster routing and query times. If we consider either base layer protocol as a Protocol Complex, then a partitioned or sharding mechanism is described by our model of Protocol Topology. A type hierarchy is enough to verify a protocol's equivalence to a Protocol Topology due to covariance, which is a valid null di erential as detailed by R. Grahm above. Speci cally, given a base layer protocol with block type , a type preserving operation +1 such as a bu ering service in a multi layered (in this case L2) topology, then if there exists covariance between their data types , + 1 then @ @ +1 = 0. Speci cally, consider a protocol with an L2 topology: TP : 0 (10) (8) to (9) This Protocol Topology is a corresponding model to an L2 system architecture (see Fig. 1). A program implementing the above protocol is veri able by ensuring functoral covariant state transitions which can be enforced by static analysis [ 10 ] (type checking at compile time). Distributed architectures designed topologically can be veri ed at the type level. In order to model distributed state, we need to design our topologies such that data locality, or the logic behind the distribution of data in distributed database is mathematically tractable. We introduce methods from Abstract Di erential Geometry, namely nitary cech-deRham cohomology in order to de ne an orientable manifold from our de nition of Protocol Topology. First we need to introduce the dual of homology as described above, namely cohomology. In describing our Protocol Complex it only makes sense to have an arrow moving 'forward in time' as consensus itself is acyclic, with each iteration pointing 'backwards in time' to its previous state. In this sense our evolution was the compounding dimensionality of the space of all con gurations, as implied by the discrete product topology of a Protocol Complex. In de ning an orientable manifold, we need to move 'backwards' through our space, i.e. from higher to lower dimension. This is shown as the di erential on an arrow going right instead of left.

In principle, Abstract Di erential Geometry (ADT) admits any topological space as a base space on which to 'solder sheaves' for carrying out di erential geometry [ 6 ]. i.e. constructing a manifold. By constructing the Protocol Topology within a monoidal category, A. Malios et al. showed that the singular cohomology of a Protocol Topology is equivalent to an A-module of Z+-graded discrete di erential forms, otherwise known as discrete di erential manifolds. This forms an execution tree, a sequence of con gurations in a poset (directed acyclic graph) topology. A decision tree can be assigned to any set of executions that captures the decision of choosing a successive con guration. A Blockchain can be de ned as an extension of an execution tree, where each block is formulated as a sheaf with a well de ned tensor operation and each successive block veri ed by a decision tree. We de ne a sheaf as the 'enrichment' of any cochain A-complex of positive degree/grade, corresponding to the A-resolution of an abstract Amodule

S : 0 ! ! S 0 d!0 S 1 d!1 : : : (11) and homomorphism given by Cartan-Kahler-type of nilpotent di erential operator d. We will make use of the fact that an A-module sheaf on any arbitrary topological space (shown above with an arbitrary simplicial cochain-complex) admits an injective resolution.

Blockchains are naturally equipped with a sheaf, known as a block hash, which contains topological state data about the con guration of the system. Every abelian unital ring (of which this sheaf theortic construction derives from) admits a derivation map [ 7 ], allowing us to 'unpack' data within a block recursively under the product operation. By noting the equivalence of Sorkin's ntoposets to simplicial complexes, A. Mallios et al. showed that the Gelfand duality implies that a manifold can be constructed from simplicial complexes [ 6 ]. Thus if we reformulate our de nition of a consensus protocol above as a sheaf with semigroup operations carried by right derived functors with monadic bind, we can form a manifold.

For a ntoposet (the topological equivalent of a directed acyclic graph), it's incidence algebra can be broken down into a direct sum of vector subspaces (P ) = M

i = i2Z+ 0 1 := A

R (12) where (P )s are Z+ graded linear spaces, A is a commutative sub algebra of and R := Li 1 i is a linear (ringed) subspace. It is trivial to notice that (P ) is an A-module of a Z+-graded discrete di erential form.

A manifold can be constructed by organizing the incidence algebras of our Protocol Complexes into algebra sheaves. The n-th (singular) cohomolgy group Hn(X; ) of an A-module sheaf (X) over topological space X, can be described by global sections X ( ) (X; )

Hn(X; ) := Rn( (C; ) := Hn[ (C; S )] := ker X (dn)=im X (dn 1) (13) where Rn is the right derived functor of the global section functor x(:) (X; :). Note that Rn is equivalent to the ith linear ringed subspace above. These dual de nitions of gamma correspond to out de nitions of and with respect to our functoral vertex map l in our de nition of a Protocol Topology.

The sheaf cohomology of a topological space is the cohomology of any X acyclic resolution of [ 15 ]. The corresponding abstract A-complex S can be directly translated by the functor x to the 'global section A-complex' X (S ) X (S ) : 0 ! which is the abstract de Rham complex of a discrete manifold X. The action of d is to e ect transitions between the linear subspaces i of (P ), as follows: d: i ! i+1.

The nitary de Rham theorem de nes a nitary equivalent of the typical c1 smooth manifold. Noting mPm is ne by construction, Mallios et al. show that nsheaf-cohomology di erential tetrads := (Pm;

M ; d; dMeR) (15) is equivalent to the c1-smooth Cech-de Rham complex. In our de nition of ,

M is the categorically dual nsheaf ( nitary sheaf) of Sorkin's ntoposets Pm, d is an exterior product, and dMeR is the abstract de Rahm complex. 3.2

Protocol Manifold

We've shown how to create a manifold from the cohomology of a discrete topological space. We now show how to construct a manifold from of a Protocol Topology. De ne a cochain-complex within the cohomology theory of homotopy types under the cup product. Making note of the existence of a tensor product in the cohomology theory of homotopy types by E. Cavallo [ 9 ] de ne the protocol manifold as the ringed vector space formed by the direct sum over all protocol sheaves = M 0 i i (16) 3.3

Applications: Data Locality and Dynamic Partitioning

Data locality refers to the ability to move a query close to node where actual data resides within a distributed system as opposed to moving data over network to the process executing the query. This minimizes network overhead, increases overall throughput and is a best practice in the development of distributed applications. A Protocol Manifold is a construction that forms the total state space of data across nodes implicitly respective of the network topology of a stateful distributed system such as a Consensus Protocol. For elastic or dynamically partitioned systems, where data storage needs to be rebalanced across nodes in the system when nodes join or leave, it provides a convenient consistency check for the state of the network and an implicit way to organize the rebalancing of data across nodes. A prime example of a distributed data store that corresponds to the Protocol Manifold is the Hadoop Distributed File System (HDFS)(see Fig. 2), which stores data across nodes with an optimal data locality and minimal redundancy to prevent data loss in the case of partial system failure. This allowed for creation of high level strongly typed APIs managing implicit orchestration of distributed data storage in tools such as Apache Spark and is key to the ability to form MapReduce APIs across stateful systems as demonstrated by the Poincare Complex below.

Consider an enrichment of a type hierarchy : : : n, and a state transition J (t) : (t) !

(t+1) M 0 i

M 0 i (t) i = (t + 1) i where the number of nodes increase or decrease, if all commute and then the total con guration space is consistent under the state transition of nodes joining or leaving. Such an implemented as a type with a product operation [ 19 ] would allow us to verify the state transition J by an 'unpacking' operation across block sheaves under the product operation, allowing for veri cation at the type level both at compile time and run time). Up until now we have not explicitly de ned functoral group homomorphisms that can construct the complexes described above. We show that the dual nature of the hylomorphic and metamorphic recursion schemes maintain vanishing di erentials and thus Poincare duality for all .

If we de ne a catamorphism and anamorphism with the same f-algebra and f-coalgebra, we can show by construction that the resulting co/chain-complexes are valid de nitions of Protocol Topologies/Manifolds and that Poincare duality of the protocol manifold is maintained up to isomorphism. We de ne in terms of and , noting that our functor is a valid f-algebra and sheaf a co-algebra.

Let us de ne a hylomorphism and metamorphism

P :

T ( ; P ) (P; ) : ! P (17) (18) (19) we formally verify by the construction of the following geometric cw-complex

T ( (P0)) : : :

T ( (P )) (21) that T and form a Poincare complex, clearly satisfying the Poincare duality as @ vanishes in our construction of T and . The fundamental class of our corresponding space is T which carries the type signatures of our hylo and metamorphisms. Formally de ne T as a Poincare protocol. 4.1

Applications: MapReduce APIs

The design of tools in the data engineering and data science space often employ principles from functional programming and type theory due to the bene ts they have at verifying code at compile time. Network queries can be implemented with guarantees around correct access governed at the type level, as functoral operators such as .map() and .reduce(). This is largely a source of the origins of scalable data processing tools for analysis and modeling like Hadoop and Spark. Distributed data stores and microservice architectures employ monadic design patterns for improvements on concurrency, static type checking, testing, design patterns, cluster management, training models etc. One bene t is the development of convenient API's with Map/Reduce operations simplifying queries by abstracting low level data locality management [ 16 ], a key example would be Spark's RDD [ 18 ]. Monadic execution models allow complex data pipelines (see Fig. 3) to be implemented and governed declaratively, providing distributed data stores constructed with high level API's. As such, if we follow their construction at the type level in architecture and code design we can develop increasingly complex distributed systems with greater guarantees. A Poincare Protocol is a consensus protocol with a monadic execution model like the Big Data tools discussed above. It describes a distributed data store of topological data formed of con guration data across blocks. An example of this is the Constellation protocol, the design of which is also its origin. Constellation was designed with a monadic execution model [ 23 ] that can be layered like a Protocol Topology and has the consistency guarantees of a Protocol Manifold. In this model, multiple independent consensus operations can coexist across heterogeneous data types, allowing for complex queries to be performed across concurrent or composite services, like common data pipelines (see Fig. 3). Each of these consensus operations is referred to as a state channel, an operates on its own corresponding data type . By constructing a Poincare Protocol, Constellation de ned a high level MapReduce API [ 20 ] for constructing new state channels out of API callbacks across existing state channels (see Fig. 4). Using an algebraic representation of these APIs in the callback tree, common in functional programming [ 17 ], each step in the call back tree is governed by the respective 's f-algebra and f-coalgebra and we can verify correctness at the type level both at compile time and runtime. The end result is a consensus protocol with the same model and guarantees of the functional programming paradigm, allowing for interoperability between the Blockchain and Big Data ecosystems. We have successfully constructed topological models of scalability focused Blockchain technologies and Big Data architectures. The protocol models above can be expanded to other distributed systems that undergo nite state transitions. The key advantage of these models is that they can be designed within functional languages with strong type systems that allows for veri cation at compile time. Future work can apply these models to systems undergoing more complex and possibly di erentiable state transitions.

References

1. Nowak T. , Schmid U. : Topology in Distributed Computing, Master's Thesis , Vienna University of Technology, ( 2010 )

2. Herlihy M. , Rajsbaum S.: Algebraic topology and distributed computing a primer . In: van Leeuwen J. (eds) Computer Science Today. Lecture Notes in Computer Science , vol 1000 . Springer, Berlin, Heidelberg. ( 1995 )

3. Alpern , B. , Schneider F. : De ning liveness . Information Processing Letters 21 , 4 ( October 1985 ), 181 { 185 . Cornell University, ( 1985 )

4. Saks , M. , Zaharoglou , F. : Wait-free k-set agreement is impossible: the topology of public knowledge . SIAM J. Comput . 29 ( 5 ), 1449 { 1483 ( 2000 )

5. Grahm R. : Synthetic Homology in Homotopy Type Theory Robert Graham . arXiv: 1706 .01540 ( 2017 )

6. Mallios A. , Raptis I.: Finitary Cech-de Rham Cohomology : much ado without smoothness . Int.J.Theor.Phys . 41 1857 - 1902 ( 2002 )

7. Mallios , A. : Geometry of Vector Sheaves: An Axiomatic Approach to Di erential Geometry , vols. 1-2 , Kluwer Academic Publishers, Dordrecht ( 1998 )

8. Mallios , A. : On an Axiomatic Treatment of Di erential Geometry via Vector Sheaves . Applications, Mathematica Japonica(International Plaza), 48 , 93 . ( 1988 )

9. Cavallo , E.: Synthetic cohomology in Homotopy Type Theory . Master's thesis , Carnegie-Mellon University ( 2015 )

10. Nielson F. Nielson H. R.: Type and E ect Systems . In: Olderog ER., Ste en B. (eds) Correct System Design. Lecture Notes in Computer Science , vol 1710 . Springer, Berlin, Heidelberg 114-136, ( 1999 )

11. A. Vahdat , M. Al-Fares , N. Farrington , R. N. Mysore , G. Porter , and S. Radhakrishnan , Scale-out networking in the data center , IEEE Micro , vol. 30 , no. 4 , pp. 29 { 41 , https://doi.org/10.1109/MM. 2010 .72

12. Herlihy M. and Shavit. N.: The asynchronous computability theorem for t-resilient tasks . In: Proceedings of the twenty- fth annual ACM symposium on Theory of computing, STOC , ( 1993 )

13. Haber , S. and Stornetta , W.S. J. Cryptology 3 : 99 . https://doi.org/10.1007/BF00196791 ( 1991 )

14. Dean J. , Ghemawat , S.: MapReduce: Simpli ed data processing on large clusters , In: Proc. 6th USENIX Symposium on Operating Systems Design and Implementation , OSDI 2004 , San Francisco, USA, Dec. ( 2004 )

15. Gallier J. , Quaintance J.: A Gentle Introduction to Homology , Cohomology, and Sheaf Cohomology . Preprint ( 2016 )

16. Wu D. , Sakr S. , Zhu L.: Big Data Programming Models . In: Zomaya A.Y, Sakr S . (eds) Handbook of Big Data Technologies, Springer International Publishing, AG,https://doi.org/10.1007/978-3- 319 -49340-4 2 ( 2017 )

17. Chuisano P. , Bjarnason R. : Functional Programming in Scala, Manning Publications Co ., Greenwich , CT , ( 2014 )

18. Apache Spark RDD documentation , https://spark.apache.org/docs/latest/r dd -programming-guide.htmln#resilient-distributed-datasets-rdds . Last accessed 15 Oct ( 2019 )

19. Product operator from functional programming library Cats , http://eed3si9n.c om/herding-cats/Cartesian.html. Last accessed 18 April ( 2019 )

20. Constellation Protocol repository, MapReduce interface via recursion schemes ht tps://github .com/Constellation-Labs/constellation/blob/7aeaa786d42e019 4e31cd8fd0c6b99462cb63f33/src/main/scala/org/constellation/Cell.scala. Last accessed 18 April ( 2019 )

21. The Bitcoin Lightning Network: Scalable O -Chain Instant Payments. Joseph Poon , Thaddeus Dryja https://lightning.network/lightning-network-paper. pdf Last accessed 18 April ( 2019 )

22. The ZILLIQA Technical Whitepaper , The Zilliqa Team. https://whitepaper.i o/document/16/zilliqa-whitepaper Last accessed 18 April ( 2019 )

23. Constellation Protocol repository, Validation Monad https://github.com/Const ellation-Labs/constellation/blob/dev/src/main/scala/org/constellation/ util/Validation.scala. Last accessed 18 April ( 2019 )

24. Hadoop Distributed File System design documentation https://hadoop .apache. org/docs/r1.2 .1/hdfsn design. html Last accessed 18 April ( 2019 )