Specification

We describe in the following the Ledgera protocol through which data can be stored and computations performed.

Storing data

The diagram below describes the expected behavior of the Ledgera network whenever a storage request is send by a client.

To request the storage of some data on the Ledgera network, the client publishes a dedicated message (here denoted as M_{arch}), that will eventually be received by all the voters.

Upon receiving that message, a voter may agree on granting that request and publish a corresponding vote (here denoted as V_{arch}). Any such vote will eventually be received by all the voters.

Upon gathering f+1 V_{arch} votes, any voter will build a quorum of signatures and emit two messages:

• a signed storage request - that contains the quorum - (here denoted as S_{val}) to the storage nodes
• a vote (here denoted as V_{stored}) confirming the fact that is has managed to build the quorum and publish the signed storage request

Upon receiving any such S_{val} message, a storage node will verify the authentificity of the contained quorum and, if it is valid, will store the value locally.

Upon gathering f+1 V_{stored} votes, any voter will build a quorum of signatures, that we call a Proof Of Storage (PoS). The voter will then send a transaction (here denoted as T_{arch}) - that contains the PoS - to the secure log in order to anchor the PoS on the secure log.

Via a consensus mechanism, the secure log then guarantees that, eventually, exactly one such T_{arch} transaction (one per valid PoS) will be delivered.

The content of the secure log being public, non-revocable and non-falsifiable, any of the nodes will eventually have access to it. Thus any node will eventually have the confirmation that one of the T_{arch} has been included in the log. In the diagram below we denote this fact by the dashed arrow carrying deliver(T_{arch}).

In the storage request video demonstration, this part of the protocol is executed.

Lifecycle of a computation instance

The lifecycle of a computation instance can be separated into 3 phases:

• the first phase corresponds to the declaration of the instance
• the second phase occurs only if the computation specification involves arguments that are not known in advance. It consists in the system agreeing on which values to use for these unknowns.
• finally the third phase consists in the actual computation and agreement on the final result

The diagram below describes the expected behavior of the Ledgera network during these three phases.

Three video demonstrations illustrate different executions of this protocol on more or less complex cases:

• with only raw values
• with a reference to storage
• with an unknown argument

Phase 1

To propose a new computation instance, a given client publishes a dedicated message (here denoted as M_{comp}), that will eventually be received by all the voters.

Upon receiving that message, a voter may agree on granting the right to execute and publish a corresponding vote (here denoted as V_{comp}). Any such vote will eventually be received by all the voters.

Upon gathering f+1 V_{comp} votes, any voter will build a quorum of signatures. The voter will then send a transaction (here denoted as T_{comp}) - that contains the quorum - to the secure log in order to anchor information about the computation instance on the secure log (the computation specification and a client-unique id).

Via a consensus mechanism, the secure log then guarantees that, eventually, exactly one such T_{comp} transaction will be delivered.

The content of the secure log being public, non-revocable and non-falsifiable, any of the nodes will eventually have access to it. Thus any node will eventually have the confirmation that one of the T_{comp} has been included in the log. In the diagram below we denote this fact by the dashed arrow carrying deliver(T_{comp}).

Phase 2

In the case where the computation specification contains unknown arguments, it cannot be immediately executed. One must first agree on the value of the missing arguments, which is the object of the second phase.

For each missing argument, any client can propose a value by sending a dedicated message (here denoted as M_{arg}). This message contains:

• the unique identifier of the computation instance
• the argument number
• a value, which is either a raw value or a reference to storage (with accompagnying Proof Of Storage)

Upon receiving such M_{arg} messages voters verify that it corresponds to a missing argument of a known computation instance and that the proposed value satisfies the corresponding predicate in the computation specification. If so, the voter will emit a corresponding vote (here denoted as V_{arg}).

There may be concurrent proposals for the same argument. To favor order-fairness, for each missing argument, any voter only builds a quorum for the first proposal for which they receive f+1 corresponding V_{arg} votes.

Upon having built such a quorum for each missing argument, a voter send a transaction (here denoted as T_{args}) to the secure log. This transaction contains the aforementioned vote quorums for each missing argument.

Via a consensus mechanism, the secure log then guarantees that, eventually, exactly one such T_{args} transaction (one per computation instance) will be delivered.

For the actual computation in phase 3, voters will use the values in this delivered T_{args} for the missing arguments. The delivery of that unique transaction guarantees that everyone will use the same values.

Phase 3

Whenever a voter has been notified of the declaration of a new computation instance (i.e., delivery of a T_{comp}), once it has knowledge of all the arguments of the computation instance (either immediately or upon delivery of a subsequent T_{args}), it performs the computation locally.

When the local computation terminates, the voter sends a specific vote carrying the digest of the result value (here denoted as V_{loc}).

Upon having collected f+1 corresponding V_{loc} votes (i.e., with the same computation instance digest and result digest), the voter builds a quorum of signatures - that we call a Proof Of Integrity (PoI) - and sends two messages:

• a notification, addressed to the client that initially proposed the computation instance. This notification (here denoted as N_{res}) carries both the PoI and the actual value of the result
• and a transaction (here denoted as T_{res}), addressed to the secure log. This transaction contains the PoI, in order to anchor the PoI on the secure log.