A Blockchain Based Framework for Information System Integrity

Mahalingam Ramkumar

Department of Computer Science and Engineering,Mississippi State University,MS 39762,U.S.A.

Abstract: A blockchain based system integrity(BCSI) framework for assuring the integrity of information system processes is presented.BCSI is well suited for a broad class of large scale real-world information systems.Under the BCSI framework,the integrity of any information system I is assured by executing the finite state machine model for system I processes in a blockchain network.The BCSI framework is compared and contrasted with the Clark-Wilson (CW) system integrity model,and existing blockchain based frameworks like Ethereum.

Keywords: blockchains; finite state machine model; ordered merkle tree

I.INTRODUCTION

Aninformation system(IS) is an “organized system for the collection,organization,storage and communication of information” [1].From the perspective of implementation,an IS is a set of computing processes that manipulate data.

Attacks on the integrity of ISes stem from the ability of rogue processes to illegitimately read/write the heap,stack,code,or data,of other processes.Most often,attackers exploit undesired functionality,viz.,accidental bugs and/or deliberate malicious functionality in IS software or the platform,to gain illegitimate read/write access.

Securing computing platforms calls for careful consideration of dynamic access control permissions for processes to read,write,create,and delete objects (files,memory contents,etc.).Substantial efforts [2]have been focused on the problem ofspecifyingdynamic security policies.Unfortunately,mechanisms toenforcesuch policies are often hindered by the increasing complexity of computing platforms.This is primarily due to the steady addition of performance enhancing features like copy-on-write [3],out-of-order execution [4],virtualization [5],hyperthreading [6],multiple cores [7],etc.Eliminating undesired functionality in IS software is also becoming increasingly challenging due to growing complexity of software.

In other words,the currently predominant approach for assuring integrity of ISes -- by i)eliminating undesired functionality in complex software,and ii) securing complex computing platforms -- is increasingly unviable.Furthermore,the growing adoption of cloud computing [8]implies lack of transparency regardingwhichplatforms are used for runningwhichIS software.Consequently,securing platforms become less relevant as a step towards assuring IS processes.

1.1 State model approaches

State-model based approaches to assure integrity of IS processes view an IS as a finite-state-machine (FSM),where ISdata items,represent IS states.Crucial IS states,that need to be subject to well-defined rules,are regarded asconstrained data items(CDIs)C.The desired assurances regarding CDIs of a system are expressed in the form of a FSMstate-transition modelM.Specifically,the state-model MIgoverning CDIs CIof an ISIcan be seen as consisting of a set ofmstatechange functions

whereTrepresents unconstrained inputs that trigger state-transitions.

Consider a “model execution” process P,or more specifically,

thatcomputes nominal valuesof CDIs CIfollowing a state transition (triggered byT).To the extent it is possible to guarantee the correctness of i) the modeland ii) the integrity of the model-execution process P(),the output of P can be considered as theground truthfor the state of ISI.Anyone with access to the ground truth ofIcan compare it to responses (to queries) from the actual systemI,to convince themselves of the integrity ofI-- even while actual ISIsoftware,and the platform for executing ISIsoftware are opaque and/or untrusted.

State model based approaches to assure systems replace two hard problems with two simpler problems.Specifically,the two hard problems of i) eliminating unintended functionality in complex IS software,and ii) assuring the integrity of complex computing platforms,are replaced by the simpler problems of a) verifying and certifying correctness of a static system model M,and b) assuring the integrity of a generic model-execution process P() (for computing nominal CDIs).Furthermore,a generic P() for assured execution of state-change functions inanyM can be used to assure the integrity of any IS.For example,the integrity of the domain name system(DNS) [9],with a state-transition model Md,can be assured by executing P() with statechange functionsas inputs; integrity of a banking system with model Mbcan be assured by executing P() with state-change functionsas inputs.

1.2 Blockchain networks

A blockchain network enables creation of an unalterable append-only ledger,shared by participants of a broadcast network,where every ledger entry is made by consensus among all participants.Blockchain ledger entries can be seen as a representation of the states of a process “executed” in the blockchain.As consensus on ledger entries implies consensus on the nominal state of the process,a blockchain network can be regarded as auniversally trusted platform.

The main contribution of this paper is a novel blockchain based framework for assuring the integrity of a wide range of real-world information systems.In the proposed blockchain system integrity (BCSI) framework,assuring the integrity of an information systemIwill merely require i) specification and certification of system-Istate-transition modelexecutingin the BCSI blockchain.Using the blockchain ledger,anyone can reliably and ef ficiently determine the nominal value of any dynamic data itemx(t) ∈CI(t),for anyt≤tc,wheretcis the current time.

The rest of this paper is organized as follows.Section II begins with an overview of i)cryptographic protocols central to blockchain networks,ii) and mechanisms in blockchain networks for ledger creation,representing and incentivising consensus,and dissuading forking.

Section III outlines the salient features of the BCSI framework.Several examples are used to describe a core component of the BCSI framework -- a hierarchical data structure,an ordered Merkle tree (OMT) [16],for representing system-states and state-transitions.Section IV on related work discusses similarities and differences between the BCSI framework the Clark-Wilson [17]system integrity model,and the Ethereum blockchain[15].Conclusions are offered in Section V.

II.BLOCKCHAIN NETWORKS

A blockchain broadcast network is a mechanism for every participant in a broadcast network to reach consensus,by maintaining identical copies of a blockchain ledger.In its naive form,every participant 1) listens to every broadcasttransaction; 2) decides (on their own) if the transaction iswell-formed,and (if so) 3) adds the transaction to their copy of the ledger.

As every participant may not desire to actively participate atalltimes,practical blockchain networks have 2 categories of users,viz.,i)incentivisedusers who take active part in making ledger entries; and ii)regularusers with sporadic participation.

Depending on the incentive mechanism,incentivised users either compete,or are randomly chosen,to “make a motion” to add ledger entries.The incentive mechanism rewards them for making correct motions,and/or penalizes them for incorrect ones.Most often,such motions are correct,and go unchallenged; regular users may simply follow suit (by accordingly updating their copy of the ledger).Active participation of regular users is necessary only when two or more incentivised usersmake conflicting motions.Under such scenarios it is up to each user to decide for themselves,as towhich fork to follow.As long as all users follow the correct fork (and thus,maintain identical copies of the ledger),universal consensusis achieved.

2.1 Cryptographic protocols

Central to blockchain networks are cryptographic protocols constructed using a secure(preimage and collision resistant) cryptograpic hash functionh().Specifically,given

(oryis an-bit hash of pre-imagexof any size)one can safely conclude that “xexisted beforey.” This is due to O(2)ncomplexity for determine a suitable pre-image (ifywas chosen first).Two cryptographic protocols used in blockchain networks that leverage this property of a one-way hash functionh() include hash accumulators [18],[16]and Merkle hash trees[19].

A hash accumulator is a protocol for computing a commitment to an ordered list of valuesv1…vnas

Specifically,the accumulated hashαiis a commitment to all valuesv1…vi,and the order in which they were accumulated.From the properties ofh(),it is impractical to determine any sequence of values(of any lengthj),different fromv1…vi,for which the accumulated hash is alsoαi.

A Merkle hash tree of depthdcan have up to 2d=NleavesL0,…,LN-1,andTheNnodes at depthd=log2Nareleaf-nodes,each obtained by hashing a leaf asThe 2jnodes at depthj＜dare obtained as

Corresponding to any node at depthd,aredcomplementary nodes -- also referred to as verification objects (VOs).In Figure 1,the 3 yellow shaded nodes are VOs of nodeu33at depth 3.In general,for any depth-knodeuwith a set of VOs u,there exists a simple se-quence ofkhash operations that result in the rootr,which can be conveniently represented as

From the properties of the hash function,givenrfu=mt(,)u it is computationally impractical to determineuu′≠,or uu≠′satisfyingrfu=mt(,)′u orrfu=mt(,)u′.In other words,thatrfu=mt(,)u is proof that “nodeuand its VOs u,exist in a tree with rootr.” Having determine that a nodeuexists in the tree with rootr,any leafLsatisfyingh Lu()= is proof that “leafLexists is a tree with rootr”

A compelling utility of the Merkle hash tree is that it also permits ef ficientincremental updatesto any node.Specifically,givenr=fmt(u,u),one can readily compute the effect of updating nodeutou′asr′=fmt(u,u).The reason for an incremental update to a leaf node can be for 3 very different purposes:

1)h(L) →h(L′) for updating a leaf fromL→L′;

2)h(L) →h(h(L),h(L′)) for inserting a leafL′;

3)h(h(L),h(L′) ) →h(L)→ for deleting leafL′;

2.2 Ledger creation

Blockchain ledgers are very similar to ledgers created by a timestamping service (TSS) [20]-[21].Timestamping is a process that attributes a “seen-at-time”tto a cryptographic hashv.Given the existence of an entry (,)t vin the TSS ledger,a documentDsatisfyingv=h(D),is conclusive proof that documentDexisted before timet.

Fig.1.A binary Merkle hash tree.The three yellow-shaded nodes are complementary to leaf L3.

A TSS maintains a ledger of timestamp records of the form (t,v),along with a dynamic commitment to the entire ledger -- in the form of an accumulated hash.In the approach in[21]for a scaleable TSS,multiple timestamp records corresponding to an interval of timeti-1≤t＜tiare batched together as leaves of a hash tree (say,with rootri).The accumulated hash for the TSS ledger is computed once for each interval as

In other words,the ledger maintained by the TSS in [21]can be seen as a chain of blocks,where each block has several timestamp entries (as leaves of a hash tree).A TSS authority attests consecutive values of accumulated hash (for example,αi-1andαi),as proof of existence of a rootriin the chain.Existence of a specific entry (,)t vin a tree with rootrican then be demonstrated using log2NiVOs,whereNiis the number of entries in theithblock.

1) Blockchain Ledger vs TSS Ledger: A blockchain network is very similar to the TSS in [21].In both,the accumulated hash corresponds to a chain of Merkle tree rootsr1,r2,….In both,the leaves of a tree with rootriare ledger entries in theithblock of the chain.The main differences are as two fold.

Firstly,in blockchain networks each entry(in a block) corresponds to asigned “transaction”broadcast over the blockchain network.

Secondly,no authority exists in a blockchain network to explicitly certify progression of the accumulated hash.This is due to the existence of a blockchain mechanism for reachingconsensusamong all participants on every ledger entry.More speci fically,explicit consensus on the commitmentαto the entire ledger is implicit consensus on every ledger entry.

2.3 Consensus in a blockchain

As all participants can listen to the blockchain broadcast network,all participants experience the same sequence of signed1In practice,“broadcast”of signed transactions is realized through strategic relays over a peerto-peer network; most blockchain networks use elliptic curve digital signature algorithm (ECDSA) [22]signatures.}transactions.Each transaction triggers execution of a well-definedfunction,resulting in astatechangein the information system represented by the blockchain.For example,in a blockchain network like Bitcoin [10],a transactionTsigned by a payerAis for purposes of transferring some bitcoins fromA's wallet to wallets of one or more payees -- sayBandC.The state-change following this transaction is the change in the “unspent balance” in walletsA B,andC.

1) Well-Formed Transactions:Onlywellformedtransactions may be added to the ledger.Application specific rules dictate if a transaction is well-formed.For example,a transaction to transferxcoins from a walletAto a walletBis considered well-formed if i)transaction {,}B xis signed byA,and ii) unspent balance in walletAisax≥.

As a second example,a transaction in a system like the Domain Name System (DNS)[9]may involve transfer of rights to a domain name --- say namec.b.afrom an entityAto an entityB.Such a transaction can be considered to be well-formed if i) a transaction with values {a,b,c,B} is signed byA; and ii)Ais the current owner of the parent nameb.a.

A TSS can itself be implemented as a blockchain (without a TSS authority).In such a blockchain network,transactions are timestamp requests of the form (t,v).A transaction(t,v) is well-formed if (according to consensus) it was broadcast at a timet′≤t.Such transactions need not be signed,as the source of the timestamp request is irrelevant.

Earlier blockchain networks [10]were each intended for a speci fic application.Consequently,rules to verify “well-formedness”of transactions where fixed/inbuilt.Emerging blockchain networks like Ethereum [15]are intended to be used as a platform for a wide variety of applications,thanks to mechanisms in Ethereum for specifying “smart-contracts.”

Specifically,Ethereum transactions can trigger operations that involve execution of contract-specific Ethereum byte-code,leading to modification of contract specificstates.

2.4 Consensus on system state

Given a sequence of (well-formed) transactionsT1…Tn,and the initial state of the system S0,any one can reconstruct the progression of system states.Speci fically,the time evolution of system states can be expressed as

where S0is the initial state of the system and Siis the state following transactionTi.

As one can always obtain the sequence of state changes S1… Snfrom the sequence of transactionsT1…Tn(and the initial state S0),it issufficientto include every well-formed transaction in the ledger.However,it isconvenientto also include in the ledger,the state Sifollowing each transaction.More specifically,using a Merkle hash tree to capture all system states as leaves,permits a single hashsi(the root of the tree) to be entered in the ledger as consensus on “the system-state following well-formed transactionTi.”

In Bitcoin,ledger entries are merely wellformed transactions.The system states areimplicit,as anyone joining the network can reconstruct the unspent balance in every Bitcoin wallet by processing every transaction starting from the first transaction (in the “Bitcoin Genesis” block).Ethereum ledger entries,on the other hand,include both well-formed transactions and an explicit commitment to system-states following such transactions.

More specifically,in blockchain networks withimplicitstates (for e.g.,Bitcoin),ledger entries in each block take the form (ti,Ti),whereTiis a transaction; in blockchain networks withexplicitstates (for e.g.,Ethereum),ledger entries in each block are of the form(ti,Ti,si) whereTiis a well-formed transaction andsiis a commitment to all system states following transactionTi.

2.5 Incentivizing consensus and forking

The security guarantees provided by a blockchain network stem from the fact that anyone can audit theentire historyof the ledger.In other words,anyone can audit the entire history ofall statesof the system.In practice,that anyonecanaudit,does not imply that everyonewill.It is for this purpose,a special class of users are incentivised to audit.

Incentivised users can be seen as those who make a motion to add an entry to the ledger.The incentive structure penalizes them for making incorrect motions,and rewards them for making correct motions.Consequently,most often,such users make correct motions,which go unchallenged by other users.The participation of regular users is necessary only in scenarios where a motion is challenged.A challenge can be seen as a fork in the block chain.In such scenarios,every regular user has to determine by themselves as towhich fork to follow.

Popular incentive mechanisms [23]-[25]include Proof-of-Stake (PoS) [23],and Proofof-Work (PoW) [10].In Bitcoin (with PoW incentive) incentivised users are “Bitcoin miners” who have to expend energy to solve a puzzle.Specifically,the puzzle to be solved to add a block (a hash tree with rootri) to the chain is discovering a nonceνi,such that the accumulated hash

has more than a certain number of leading zeros.Solving the puzzle is necessary to both“mine” new bitcoins (which are credited to the miner's wallet),andearn the privilege of adding a block to the blockchain (making the motion).

Note that the puzzle itself has nothing to do with the main purpose of the blockchain --viz.,reaching consensus on unspent Bitcoins in every wallet.The incentive for miners to audit every transaction is that their valiant efforts to solve the puzzle may be rendered moot if an ill-formed transaction is erroneously included in the block.An erroneous entry will be challenged by another user to create a fork.The main shortcoming of PoW based incentives stem from growing sustainability concerns [26]regarding energy expended for mining.

In PoS based systems incentivised users will be required to explicitly have some stake(for example,balance in their wallet) in the system.A randomly chosen subset of such users may be required to certify the correctness of each transaction (or all transactions included in a block) by betting their stake.As a reward,they earn a small payment,typically proportional to the amount staked.Any error (deliberate or otherwise) in verifying well-formedness will result in loss of stake.

While regular (passive) users may not audit every transaction,it is important to note thattheir ability to do so is vital.If the reason for the fork is addition of ill-formed transaction in forkB,users can reject this fork and follow the correct forkA.If all forks have only wellformed transactions,unambiguous tie-breaking rules should exist to permit users to identify the correct fork.

III.OVERVIEW OF BCSI MODEL

The blockchain system integrity (BCSI) model(MI,CI) for any information systemIconsists of i) a state-model MI,specified asmstatechange functionsand ii) a representation of CDIs CI,as leaves of hash trees.

The state-change functionδjIis executed in response to a transactionTjof typejm={1}…,broadcast over the blockchain network.More specifically,a state-change function triggered by a transactionTjat timet,viz.,

is specified as a set of explicit predicates,viz.,

1)preconditionsto be satisfied by contents of CI(t-) andTjbefore the state-change; and

2)postconditionsto be satisfied by contents of CI(t+) after the state-change.

The BCSI model for a systemIcan be more concisely represented as (µI,sI(t)),where

1)µIis the root of a static hash tree withmleaves,where each leaf is a description of predicates (pre/postconditions) for a statechange function; and

3.1 Ordered merkle trees

The hash tree employed by the BCSI model is a Ordered Merkle Tree (OMT).

Recall that a Merkle hash tree permits an entity who tracks only the rootrof the tree to verify existence of any leafL∈L,where L is adynamicset of leaves,with no practical restrictions on | |L.The ability to cater for dynamics of the set L is due to the ability to perform incremental updates; the ability to cater for practically unlimited cardinalityN=||L of the set stems from the fact that only log2Nhash operations are required for verifying existence of any leaf,and performing incremental updates.

By imposing some additional structure on leaves of the hash tree any entity with access to rootrcan also verifynon-existenceofitemsrepresented by leaves.Two such extensions include i) the Merkle-Patricia [28]tree2The key-value store in Ethereum is realized using a Merkle-Patricia hash tree,whose root is the commitment to the entire key-value store.,for maintaining a collection of key-value pairs;and ii) Ordered Merkle tree (OMT) [29]for maintaining a collection of collections.

An OMT is a rich and flexible data structure for creation of application-specific hierarchical data structures for representing CDIs.Every OMT leaf is of the form

whereCis a collection identifier,iis a key(unique in collectionC),andinis the is the next key in collectionC.The interpretation of the valuevidepends on the type of the collection.

OMT Collections can be of two types --dictionary,or look-up table (LUT).Existence of a leaf {C,i,in,v} in a dictionary collection implies that a key-value pair (i,v) exists in collectionC.Thatinis the next key implies that keys in the interval ]i,in[ donotexist.Ifin＜i,theniis the highest key,and the next key is the smallest key in the collection.For example,]25,42[= { 26,27,…,41},and]42,25[= { 0,… ,2 4,43,…}.

Existence of a leaf {C,i,in,v} in a LUT collection implies the value of some function represented by the collection isvfor the interval[i,in[.For example,[25,42[= { 25,26,… ,41}and [42,25[= { 0,… 2 4,42,…}.

Both types of collections are alwayscomplete.A LUT collection is complete as it can be used to answer a query regarding any keyjby providing the valuevcorresponding to the interval [i,in[ in whichjfalls.A dictionary is complete,as a query for any keyjcan be answered with the value,or that “key does not exist,” (ifj∈]i,in[).

In the rest of this paper we shall use notations likeD,D1,D2etc.,to represent dictionary collection identi fiers andL,L1,L2etc.,to represent LUT collection identi fiers.We shall also use the notation

to imply that “a dictionary item {D,i,in,v}(for keyi) exists in an OMT with roots” or “a LUT item {L,i,in,v} (for interval [i,in[) exists an OMT with roots.” If there is no ambiguity,we may sometimes omit the collection identifier.We may also omit the next-index for dictionary items (notation (i,v)).

An OMT may include multiple collections with unique collection identifiersC.As an example,an OMT may have 3 dictionary collectionsD1,D2andD3and 2 LUT collectionsL1andL2.If the number of items in each of the 5 collections are (respectively)m1,m2,m3andn1,n2,the OMT hasN=m1+m2+m3+n1+n2leaves.Any one with the knowledge of the rootscan verify existence of specificleaves in the OMT (or specificitem in a collection),or update the rootsto make incremental updates to the OMT - given appropriate VOs.Such incremental updates can be for purposes of inserting/deleting items,modifying the values of items,etc.By verifying the existence of a single leaf,the verifier can gain some holistic inferences regarding a collection,like non-existence of items,highest/lowest key in a collection,etc.

3.2 Hierarchical OMTs

The valuevof an item (in any collection in an OMT) can itself be a root of an OMT at a lower level of hierarchy.Any number of such hierarchical levels may exist.In other words,the root of the OMT at the highest level of hierarchy can be a commitment to any number of OMTs.More specifically,each OMT (in a hierarchical arrangement of OMTs) can be seen as having a unique hierarchical identity.For example,consider an OMT identified as (D‖i) ‖(L‖j) ‖(D‖q).This refers to an OMT at level-4 of the hierarchy.More specifically,at level-1 there exists an itemiin collectionD,whose value is the root of an OMT at level-2.ThusD‖i) can be interpreted as a unique identi fier for a level-2 OMT.In the level-2 OMTD‖i,there exists a collectionLwith an itemj,whose value is the root of a level-3 OMT (identi fies as (D‖i) ‖(L‖j)),and so on.

As an illustration of notations used in the rest of this paper for depicting nested items

represents a level-2 dictionaryDitem (for keyp),housed in a level-1 LUTLitem (for interval [,[i j).More specifically,in an OMT with roots,there exists an LUT collectionL;the value of the item in collectionLfor interval [,[i jis a level-2 OMT root (say,x).The level-2 OMT with rootxincludes a dictionary collectionDin which an item (,)p wpnexists.

3.3 BCSI state-change functions

In the BCSI model,hierarchical OMTs are used for representing system-specific CDIs.More specifically any number of OMTs - each with a unique hierarchical identity,and any number of dictionary/LUT collections with unique collection identifiers,where each collection can have any number of items with unique keys - can be used to capture system CDIs.The root of the lone OMT at level-1 is a commitment to all system CDIs.

1)µIis the root of a static hash tree withmleaves,where each leaf is a description of predicates (pre/postconditions) for a statechange function; and

2)sI(t) is the root of a dynamic (level-1)OMT.

Only incentivised users have to maintain OMTs.Regular users will merely be required to track the consensus ledger root.With the knowledge of the ledger root,any regular user can ascertain the existence of a ledger entry.Every ledger entry will include a timestampt,a well-formed transactionTand the statesstI()-andsI(t)-before and after the transaction.UsingT,sI(t)-andsI(t)+,any regular user can verify the existence/non-existence of any item in C by demanding VOs from incentivised users.As all state-changes will ultimately boil down to a small set of predicates involving existence/non-existence of items in C,regular users can also verify the correctness of any state-change.

Signed BCSI transactions of the form T=[,,]µIi… that trigger state-change functions unambiguously identify

1) the system/processI,by specifyingµI,the root of a static tree representing system model MI;

2) the indexjm=1… to identify a specificstate-change function in MI; and

3) additionaltransaction-specificvalues to unambiguously identify CDIs implicated in the state-change.

In other words,a leaf with indexjin the static OMT with rootµI,along with values included in the transaction T,contain all necessary data to unambiguously determine the CDIs implicated in the state-change functionIn conjunction with some auxiliary values provided by incentivised users,regular users candeterminethe predicates (pre/postconditions) associated with the state change.The predicates can then beverifiedby demanding VOs from incentivised users.

A BCSI ledger entry corresponding to a well-formed transactionTjat timetis of the form

wheres-ands+are (respectively) the commitments to the CDIs of a process identified asµ,before and after the state-change triggered by transactionTj.

3.4 Generic an system-specificOMT updates

It is advantageous to attribute a special interpretation to OMT items with value 0.A dictionary item (,0)iwith value 0 is a place-holder;a LUT item [,,0]i infor interval [,[i inimplies that the function isundefinedfor that interval.Operations like inserting/deleting a dictionary place-holder (in any OMT at any hierarchical level),or splitting an LUT item like [2,8,]vinto two items (for example [2,4,]vand[4,8,]v),or combining two items [2,4,]vand[4,8,]vinto one item [2,8,]v,do not affect the system-specific interpretation of CDIs.Similarly,reordering leaves in an OMT do not affect the CDIs in any way.However,such OMT updates (inserting/deleting dictionary placeholders,splitting/ combining LUT items,reordering OMT leaves) do affect the roots.Such OMT updates can be considered asgenericupdates.

System-specificOMT updates,governed by system-specificstate change functions will be restricted to

1) updating values of items; and

2) initialization of OMT roots for trees with a plurality of collections

For example,consider an OMT structure where at level-1 of the hierarchy there is a single dictionary collectionD,whose item values are level-2 OMT roots.Specifically,assume that each of the level-2 OMTs has a dictionary collectionDand a LUT collectionL.As a practical example,every item in the level-1 OMT may correspond to a file.The level-2 LUT for a fileφcan be an access-control list and the level-2 dictionaryDmay provide some information (for example,file-hash) for every version of the file.

Initialization of a level-2 OMT will involve setting the root to a valuevwhich is the root of a tree with two leaves,viz.,

Note that once the first item exists in a collection,generic OMT updates can be used to insert/delete items.For example,inserting a place-holder for an indexiin dictionaryDwill call for replacing the leaf-node corresponding to {D1,1,1,0} with the parent of two leaf nodes,{D1,1,i,0 },{D1,i,1,0}.Similarly,the lone LUT item {L,1 ,1,0} can be split into 2 items {L,1 ,i,0 },{L,i,1 ,0} using generic OMT updates.

3.5 Transaction,ledger update,and verification

As a simple example,consider a state-change in a banking systemIfor transferring an amountxfrom accountAto accountB.The signed (by the payerA) transaction broadcast over the blockchain network,viz.,

identifies the state-change function indexjin the static hash tree with rootµ,the account identifiers of the payer and payee (AandB),the transacted amountx,and the signature ΣAof the payer covering all values included in the transactionT.

Assume that the CDIs of a simplified banking system are key-value pairs like (,)A a,(,)B betc.,with account numbers are keys,and account balances are values.Thus,all CDIs can be captured in an OMT with a single dictionary collection.The preconditions and postconditions for this transaction are

wheremis the minimum balance,andfis a transaction fee.More specifically,the OMT roots-before the transaction should be consistent with the existence of dictionary items(A,a) and (B,b); the OMT roots+following the transaction should be consistent with the existence of dictionary items (A,a′) and (B,b′).

To convince the veri fier that the ledger entry (t,T,s-,s+) is correct,incentivised users should be able to prove that

1) the predicates in Eq (17) are consistent with the system model (expressed in leafLjof the static OMT with rootµ); and

2) the preconditions are consistent with OMT roots-,and the postconditions are consistent with OMT roots+

Contents of i) leafLj,and ii) the transactionT={µ,j,A,B,x}ΣA,will enable the veri fier to unambiguously identify the CDIs implicated in the state-change.Constants likem,f,and the collection identi fierDwill be included inLj.Auxiliary values provided by incentivised users will include current balances likeaandb,and next-indexesAnandBnfor the 2 dictionary items.Thus,with information included in i)Lj,ii) the transactionTand iii) auxiliary data provided by incentivised users,any verifier will be able to construct the predicates as

The verifier can then demand VOs necessary to verify that

1) leaves {D,A,An,a} and {D,B,Bn,b} exist in a tree with roots-; and

2) leaves {D,A,An,a′ } and {D,B,Bn,b′} exist in a tree with roots+.

1) A Less Trivial Example:The motivation for flexible hierarchical representation of CDI is to efficiently identify CDIs implicated in system-specific state-change functions.As illustrative examples of the utility of hierarchical representations of CDIs in real-world information systems,we shall consider a remote file storage system.

In a state model for a (simplified) remote file storage system,CDIs will include i)unique identi fiers for every file; ii) an access control list (ACL) for every file; iii) version numbers; and iv) file-hashes associated with different version numbers.The CDIs of such a system can be organized as follows.

At level-1 is a single dictionary collectionD,with one item per file; an itemD:(φ,v)φnindicates thatvis the root of a level-2 OMT for fileφ,and that files with identi fiers betweenφandφndo not exist.

The level-2 OMT for each file has two dictionary collectionsD1andD2.

An itemD1:(u,a)unconveys that useruhas access permissionafor fileφ,and that,users with identifiers that fall in betweenuandunhave no access rights.For example,access rights could bea=1 for read-only access,a=2 for read-write access,etc.

An itemD2:(m,ν)mnconveys thatνis the file-hash corresponding to versionmof the file,and thatifmn＜m,andν＞0,thenmis the highest version number.

We shall now consider a transaction for adding a new version (with version numbern) of fileφ.From the perspective of the state model,a CDI updateD2:(n,0→ν)n′is required whereνis the hash of versionnof fileφ,wheren′＜n,indicatingnas the highest version number.The transaction requesting this modi fication should be signed by a useruwith access righta=2.More specifically,an itemD1:(u,2)unshould exist in the level-2 OMT for fileφ.

The triggering transaction,and predicates for this state change can be expressed as

The description of predicates (for transaction typemin modelµ) can be seen as providing atemplatethat can be applied to any fileφ,any useru,any file hashν,and any versionn.The values necessary to determine the pre/postconditions are made available as values(likeφν,,n) included in the transactionT,and auxiliary values provided by incentivised users.

If the OMT roots before and after the statechange aresands′ respectively,the “existence proofs” that need to be verified by users (using VOs provided by incentivised users) are as follows:

The values shown in red are included in the static template for the state-change.The values in black are conveyed by the transaction.The values in cyan are auxiliary values provided by incentivised users to enable verifiers to construct OMT leaves (whose existence will then need to be verified using VOs).

3.6 Predicates for DNS transactions

As an example of a model for an entire system,in this section we outline predicates for all state-change functions for the Domain Name System (DNS) [9],which is an information system for hierarchical delegation of a namespace,and associating information to names.More specifically,information pertaining to a domain name takes the form of different types of DNS records.DNS records are created by the owner of the name,where ownership was gained through delegations.

At the top of the DNS hierarchy is an entity referred to as the root.The root creates and delegates top-level names like com,net,etc.The beneficiary of a name com can create second-level names like this.com,and that.com etc.Such created names can be delegated to other entities,or,alternately,information can be bound to undelegated names,in the form of DNS records of different types (for example,type ‘A' for IP address,type ‘MX'for mail-exchange,etc.).Multiple DNS records for the same name and type may exist,and are collectively referred to as an RRSET.The beneficiary of a name like this.com,can likewise create any number of new names ending with this.com (for example,who.this.com),and either delegate such names,or create different types of RRSETs for owned names.

In this section we outline the system model M for DNS,consisting of 6 state-change functionsδ1…δ6.More specifically,this section outlines

1) the OMT structure for organizing DNS CDIs;

2) predicates (pre/postconditions) for each of the 6 state-change functions; and

3) transactions of 6 different types.

Ultimately,the purpose of executing DNS state-change functions in the BCSI blockchain is to permit anyone to determine nominal CDIs.Specifically,at any time,any one can compare the response to any DNS query(made to the actual DNS system),to nominal CDIs computed by the BCSI blockchain.More specifically,DNS queries are made for an RRSET corresponding a specificname and type.The response (the RRSET) can be compared for integrity with a nominal CDI (the hash of the RRSET) for the name (name-hash) and type.

An OMT is used to store various data items like hashes of DNS names,hashes of RRSETs,and counts.More specifically,it is assumed that the name-hash corresponding to the root is Ξ.The name hashNcorresponding to a name like “.net” isN=h( Ξ,′net′) (obtained by hash-extension of the root name-hash Ξ).Similarly,the name-hash corresponding to “xyz.net” isN′ =h(N,′xyz′) (obtained by hash-extendingN=h( Ξ,′net′)),and so on.

The OMT for capturing DNS states has three dictionary collectionsDo,DcandDrat level-1 of the hierarchy.In all three dictionaries name-hashes are item keys.More speci fically,

1)Do:(N,P)Nn:Pis the public keyPfor name-hashN.OnlyPcan sign transactions for creating/deleting DNS records for nameN,delegating/surrendering nameN,etc.

2)Dc:(N,ct)Nn:ct-1othernames have been derived from nameN(by hash-extending nameN);

3)Dr:(N,u)Nn:uis the root of a level-2 dictionary whose items corresponds to RRSETs for all DNS record types (for nameN).More specifically,an itemDr:(N,D:(τ,ρ)τn)Nnconveys that the RRSET-hash for typeτ(and nameN) isρ.

The initial state of the system corresponds to an OMT with roots0,with one entry in each of the 3 level-1 dictionaries,viz.,

where Φ is the public key associated with the owner of the root zone.

From this point on wards,changes to the OMT dictionaries can happen only due to

Fig.2.Transaction and predicates (s- and s+) for 6 DNS state changes.

1) generic BCSI transactions (for adding/deleting place-holders,reordering leaves,etc.,),and

2) 6 DNS-specific transactions outlined in Figure 2.

More specifically,the initial state public key Φ for name Ξ to sign transactions for creating new top-level domain names,and binding public keys for delegated names.Items corresponding all newly created names are added to bothDoandDc.Other transactions signed by the owner of a name can similarly be used to delegate a name (by changing the public key associated with the name),surrender a name,or create/delete an RRSET of a specifictype.

1) DNS Transaction Types:As described earlier,every model M transaction specifies the same static commitmentµto the state-model M,and a transaction typejm={1}… (m=6 for DNS).In addition,every transaction has some transaction-specific items.

Transaction type 1 which conveys valuesN,N′ signed byPis for creating a new nameM=h(N,N′).The preconditions are i)Do:(N,P) (orPis public key for nameN);and ii)Do:(M,0) (nameMdoes not exist currently).The postconditions are i)Do:(M,P)(the created name is also associated with public keyP); and ii)Dc:(N,ct- 1),Dc:(M,1)(the count associated with nameNis incremented,and the count associated with the new nameMis set to 1).Transaction type 2,which also conveys valuesN,N′ signed byP,is for deleting a nameM=h(N,N′) by the owner ofN(andM).When a nameMis deleted i) all DNS records for the nameMare deleted; and ii) the count associated with the parent nameNis decremented.

Transaction type 3,which conveys valuesNv,,τsigned byPis for creating an RRSET for nameNand typeτ,with RRSET hashv.The preconditions are that the nameNshould be owned byP,and RRSET for nameNand typeτshould not exist currently,as is demonstrated by existence of the place-holderDr:(N,D:(τ,0)) in the level-2 dictionaryD.The post-condition is that the value of item(τ,0) is set tov.Transaction type 4,which also conveys valuesN,τ,vsigned byPis for deleting RRSETDr:(N,D: (τ,v)) by setting valuevto 0.Recall that generic OMT operations can be used to delete the place-holder left behind,if necessary.

Transaction type 5 which conveys valuesN,N′,P′ signed byPis for delegating a nameM=h(N,N′) owned byPto a new owner(with public key)P′.The preconditions are that both namesNandMshould be owned byP.The postconditions are i) new owner for nameMisP′; and ii) removal of all DNS records for nameM(that may have been created by the previous owner).

Transaction type 6 which conveys valuesN,N′ signed byPis for surrendering a nameM=h(N,N′) received through delegation(from the owner ofN).The preconditions are i)Do:(M,P) (the nameMshould be owned byP); and ii)Dc:(M,1) (no names should have been created by hash extendingM).The postconditions are i) erasing owner,count,and all DNS records associated with nameM; and ii) decrementing the count associated with the parent nameN.

3.7 Utility of collection types

To see the utility of two different collection types,we shall consider two examples involving two very different information systems,viz.,border gateway protocol (BGP) [30]and geographic information systems (GIS) [31].

BGP routers facilitate routing between autonomous systems (ASes) of the Internet.For this purpose,BGP routers maintain reachability information for all possible destination IP addresses -- by clumping ranges of IP addresses together as an IP prefix3For example,100.1.2.0/24 represents 28 IP addresses for which the first 24 bits are the same as 100.1.2.0:viz.,addresses 100.1.2.0 -100.1.2.255..The information corresponding to each IP prefix will typically consist of multiple paths,with different path weights.Only the best-weight path may advertised by a BGP router to its neighboring BGP routers.

The information maintained by a router can be seen as an OMT where

1) the OMT at level-1 has a single LUT collectionL; an itemL: [i,in,v]in this collection corresponds to IP pre fix [i,in[;vis the root of a level-2 OMT which provides various information regarding the pre fix [i,in[.

2) all level-2 OMTs (one corresponding to each pre fix) include two dictionary collectionsD1andD2; an itemD1:(p,w)pninD1implies that a pathphas weightw; an itemD2:(w,c)wnconveys thatcdifferent paths exist with weightw.

More speci fically,ifL: [i,j,v]∈rand {D1:(p,w)pn,D2:(w,c)wn}∈vany entity with access toris convinced that

1)wis the highest weight,ifw＞wnandc＞0; and

2)p(with weightw) is (possibly one of) the best path to IP addresses in the range [i,j[.

In geographic information systems,several features common to a geographic region that falls between latitude coordinates [l1,l2[ and longitudes [g1,g2[ may be expressed in a dictionary as (feature,value) pairs.An item

corresponds to an interval (latitude coordinates) [l1,l2[ of LUTLat level-1,whose value is a level-2 OMT root.The OMT at level-2 includes an LUTLwith an item for an interval(longitude coordinates) [g1,g2[.The value of the item is a level-3 root.The level-3 OMT includes a dictionaryD(indicating feature-value pairs).An item in the dictionary is (u,v).For example (u,v) may imply that “for all residents living in the rectangular region described by [l1,l2[ and [g1,g2[,the “polling station” (u)isv.”

IV.RELATED WORK

The BCSI model is closely related to the Clark-Wilson (CW) model for system integrity[17].In the CW model for an information systemI,only well-formedtransformation procedures(TPs) can modify CDIs.A TP is well-formed if it is guaranteed to always take the system from one acceptable state to another.The primary triggers for execution of TPs are external inputs,which areunconstrained data items(UDIs).

Under the CW model,the time-evolution of a system can be seen as a sequence of “snapshots of CDIs,” … → Ci-1→ Ci→ Ci+1→ …,where the change from one snapshot to the next is due to a chain of events,(typically) beginning with a UDI,which triggers execution4TPs may also be triggered by internal forcings -- for example,when the value of a CDI (or some function of one or more CDIs) is above/below a threshold.of a TP,which results in the modification of one or a small number of CDIs.

CWintegrity verification procedures(IVPs)are responsible for verifying if the current snapshot of all system CDIs correspond to a system in an acceptable state.If a CDI snapshot was first verified by an IVP,and thereafter,if only well-formed TPs are allowed to modify CDIs,by simple induction,it follows that such a system will always remain in an acceptable state.

As the CW model was intended for application processes running on a general purpose multi-user computing platform,the model includes a set ofCW-tuplesof the form (user,TP,CDIs/UDIs) which dictate i) which user process (in a multi-user computing environment) has rights to execute which TP,ii) which CDIs can be modified by a TP,and iii) which UDIs can be converted to CDIs by a TP.More formally,the CW model is associated with 5 certi fication rules (C1…C5) and 4 enforcement rules (E1…E4).

Certification rules demand attestation of correctness of various components of the CW model:

C1IVPs should correctly validate of all CDIs;

C2TPs should be well-formed;

C3CW-tuples should take into account the principles of least privileges,and separation of duty.

C4state-changes should be logged as append-only CDIs.

C5a UDI should either be converted to a CDI,or be rejected.

Enforcement rules demand existence of mechanisms for

E1ensuring that a specific TP can only modify speci fic CDIs.

E2associating a user with each TP.

E3authenticating users;

E4ensuring that only “security officers”who certify correctness of TPs and IVPs can associate (or change existing associations between) users and TPs.

The main shortcoming of the CW model is that securing general purpose computers for satisfying enforcement rulesE1…E4is an intangible problem.This disadvantage is be overcome in BCSI by interpreting TPs as processes executed in a blockchain network.Speci fically,BCSI framework replaces the 5 CW certi fication rules and the 4 enforcement rules with a single certi fication rule,viz.,“correctness of state-change predicates.”

4.1 CW vs BCSI vs Ethereum

The similarities between all three are as follows.Signed blockchain transactions in Ethereum / BCSI are equivalent to UDIs in the CW model.UDIs trigger

1) execution of TPs (in CW model) or

2) smart contracts (in Ethereum) or

3) explicit state-changes (in BCSI).

The end result is a change of state in the information system.The main difference between the CW vs Ethereum/BCSI is the execution platform,viz.,multiuser general purpose computer for the CW model vs blockchain for Ethereum/BCSI.

From a security standpoint,a similarity between BCSI and CW is that they mandate simplicity of TPs/IVP (CW),or explicit predicates (BCSI) to aid formal certification of correctness of TPs/state-change functions.Ethereum is different in this respect,as it places no constraints on the complexity of state-change functions.Ethereum state-change functions are“smart contracts” written in a JavaScript-like language,intended to be executed in a Ethereum virtual machine (with 1024 256-bit word stack,and an “infinitely expandable” byte array as heap.

The main differences between CW and BCSI are 3-fold.Firstly,IVPs are not required in the BCSI model.The purpose of IVPs in the CW model is to determine and report if the current state of all CDIs implies “a system in an acceptable state.” IVPs do not change system state.A blockchain network does not have an authority who is trusted to report correctness of the initial system state.Specifically,as every one has access to all system states,anyone can convince themselves of its correctness.IVPs do not serve any purpose,rendering certification ruleC1(which validates IVPs) moot in BCSI.

Secondly,processes for verifying predicates are executed by the same “user,” viz.,“everybody in the network.” Consequently,certification ruleC3for CW tuples (specifying which user can invoke which TPs and which TPs can modify which CDIs) becomes irrelevant.For the same reason,enforcement rulesE1(only specific TPs can modify specific CDIs),E2(only specificusers can execute specificTPs),andE3(mechanism for user authentication)become irrelevant.However,BCSI can take advantage of the mechanism for authentication of UDIs - viz.,by signing transactions.

Thirdly,CW TPs can be broadly classified into i) TPs triggered by UDIs (and consequently,convert UDIs to CDIs),and ii) TPs that do not deal with UDIs,that are triggered by the current state of some CDIs (for example,some CDIs may indicate an expiry time,and thus passage of time becomes a trigger for executing a TP -- to possibly delete an expired CDI).In a blockchain network,execution of any process has to be triggered by an UDI(signed transaction).Consequently,every state-change either converts UDIs to CDIs,or rejects the UDI (transaction) as ill-formed.Thus,both certification rulesC2(TP results in acceptable state change) andC5(either convert UDIs to CDIs,or reject UDIs) are applicable to every state-change,and may be combined into a single BCSI certification ruleC,viz.,“state-change predicates should be correct/well-formed.”

Timer based triggers can be handled indirectly in blockchain networks.For example,some special users may be deemed responsible for broadcasting transactions that trigger state-changes for removal of stale CDIs.If stale CDIs do not exist,such transactions may be safely ignored as ill-formed.Such special users may also trigger generic state-changes.

4.2 BCSI vs Ethereum

The similarity between BCSI and Ethereum is that in both (unlike Bitcoin) commitments to process states are explicitly included in the transaction.The main difference between Ethereum and BCSI is that evenstate-change predicatesare explicit.

In other words,there are two broad ways to specify a state-change functionδj.In the conventional algorithmic approach (used in Ethereum),δj() is a sequence of steps written in a blockchain specific language,and is intended to be executed in a blockchain speci fic virtual machine.State changes that occur on execution of the function areimplicitlyspecified by functionδj().In the BCSI framework,the state-changes are explicit predicates.

There are two good reasons why explicit specification of predicates is a good idea.Firstly “you can not secure what you do not understand” [27].Explicitly specifying permitted state changes is an unambiguous way ofcapturing the intention of the process.After all,attempting to ensure the integrity of a process by consensus,has very little utility if “what the process should do” is not well understood.This important requirement has been ignored in Ethereum,which includes a mechanism to address the halting problem (by demanding a fee for each step of execution).This is clear evidence that very little importance is placed on disambiguating “what the process should do.”

Secondly,explicit predicates make it easier for regular users to verify the correctness of state transitions.In a scenario wherekCDIs are implicated in a specific state-change,at mostkNlog2complementary hashes are needed for users to verify all predicates.The need for regular users to be capable of verifying any state transition -- even if they use this ability only sparingly -- is vital to dissuade forking of the blockchain.The easier it is for regular users to verify the correctness of any transaction,the easier it is for users to identify and follow the correct fork,and thus,the harder it is to fork the chain.

V.CONCLUSIONS

State model based approaches for assuring integrity of systems replace two hard problems,viz.,i) eliminating bugs and Trojan horses in complex software,and ii) guaranteeing the integrity of modern complex computing platforms,with two simpler problems,viz.,i) verifying correctness of a FSM model of a system,and ii) guaranteeing the integrity of a simple process P() for executing FSM statechange functions to compute nominal system states.

The main contribution of this paper is framework for assuring the integrity of a wide range of information system processes/applications,by executing process P() in a blockchain network.A blockchain network can be seen as a trustworthy computer,as any one can audit the complete history of all states of any well-defined process executed by the computer.Enhancing the utility of blockchain networks to assure integrity of systems calls for

1) a uniform strategy to execute a wide variety of applications/processes on the “blockchain computer,” and

2) strategies for users/stakeholders to efficiently i) query information system states,and ii) verify correctness of state transitions.

Both these requirements are furthered by the use of a flexible hash tree based data structure for representing system states and state-transitions.

In most blockchain applications (with the exception of Ethereum [15]) the system-state is not explicitly included in the ledger.Both BCSI and Ethereum require system-states following every transaction to be made explicit.In Ethereum,the state of a smart-contract is a collection of key-value pairs whose succinct commitment is the root of a Merkle-Patricia tree.In BCSI,important states of a process(or CDIs) are captured as items of flexible,nested collections,whose commitment is the root of an OMT.More specifically,two types of collections can be used,and any number of nested levels may exist.

Both Ethereum and BCSI have a common goal,viz.,catering for a wide range of possibly complex systems.The significant difference between the two approaches to reach the common goal can be summarized as follows.

1) Ethereum utilizes a less flexible data structure,and relies on the ability to execute complex smart contracts (in a complex VM).

2) BCSI,on the other hand,relies on a highly flexible data structure,which can be intelligently chosen to realize an explicit specification of easily verifiable predicates.

Explicit specification of predicates is necessary to ensure an unambiguous understanding of “what the consensus is on.” Efficient verif ication of predicates by regular users is necessary to prevent forking of blockchains.

Our ongoing work is focused on investigating predicates for a wide range of real-life information systems to identify suitable nested OMT structures,and design of a simple BCSI“byte code” to specify pre/postconditions.