Concepts

Nodes and Byzantine threshold

A Ledgera network is composed of a number of nodes that correspond to independent entities that each have their own unambiguous identity (characterized by a public/private key pair).

Among these nodes, some can be malicious. We denote by f the maximum number of such malicious nodes.

Thus, among any sub-group of f+1 nodes, at least one of them is honest.

Signatures

Any node can use its unique private key to produce digital signatures.

Given a message (or any piece of data) m, a node can n can produce a unique signature s_n(m).

From s_n(m) one can deduce that n has signed message m.

Under the hypothesis that honest nodes have securely stored their private keys, we have strong authentication and non-repudiation properties i.e.:

• we are certain that is is indeed node n that has signed s_n(m)
• node n cannot later deny having signed the message m

Quorums

Combining the previous observations on the Byzantine threshold and on signatures, if one have f+1 signatures from distinct nodes for the same message m, then, one can be certain that at least one honest node has signed m.

We call such collection of f+1 signatures a Quorum.

Application Use-Case

Ledgera allows one to perform computations that are replicated accross nodes so as to ensure the correctness of their result.

Defining the nature of those operations requires defining a Ledgera application use-case that is characterized by:

• the nature of the data values that are manipulated
• the nature of the operations that may be applied to these values
• predicates that may or may not hold on these values

See the toy example.

Digests

Depending on the application use case, data values might be arbitrarily large. To refer to such values in messages and proofs, we therefore rely on fingerprinting.

Given a certain agreed upon hash function, we use fixed sized digests :

• to refer to data values from the application use case
• and also as unique identifiers for instances of computations being executed in the Ledgera network

Storage

A Ledgera network implements a distributed storage in the form of a key-value store where the values are data values which types depend on the application use case, and the keys are the digests of those values.

One can read from and write on the storage but one cannot delete elements. Any write of a pair (key,value) on the storage must satisfy the fact that “key = digest(value)”. Thus, one cannot use the write operation to overwrite data.

In a Ledgera network, the storage must be replicated on at least f+1 nodes.

Proof Of Storage

A Proof Of Storage (PoS) is a quorum of signatures that guarantee that a value will eventually be stored on the storage.

Let us remark that a PoS might be built via f+1 messages from the storage replicas themselves, declaring they have stored the value. However, as f nodes (and thus storage replicas) might be malicious, they might refuse to participate in building the proof. To guarantee that such a proof can be built, one would require 2f+1 storage replicas so that f+1 of them are honest.

However, storage is costly. In Ledgera, we only require f+1 storage replicas and we built the PoS differently. Please refer to how data is stored to see how such PoS can be built in practice.

Computation specification

A specification of a computation is a template which may be used to define and execute computations. It depends on the types defined in the application use-case and contains:

• the choice of a specific operation, of a given arity k
• the specification of k arguments on which the operation will be applied
• for each argument in 1..k, the argument specification taking the form of either:
  • a concrete raw value
  • a reference to a value in storage (with an accompanying Proof Of Storage)
  • or a predicate (that is used to refer to values that are not known in advance)

Instance of computation

An instance of a computation corresponds to a process that is running in the Ledgera network and which goal is the realization of a given computation specification.

An instance of a computation is characterized by:

• a computation specification
• a unique integer identifier provided by the node which initially proposed the execution of the computation
• the signature of these two elements by that node

Any such instance is identified via a digest that takes these 3 parameters into account.

As a result, if the computation instance is initially proposed by an honest node we can guarantee that the identification is unambiguous.

In particular, another malicious node cannot introduce another computation instance which would have the same digest.

Proof Of Integrity

A Proof Of Integrity (PoI) is a quorum of signatures that guarantees that the result of an instance of a computation is valid.

Please refer to the lifecycle of a computation instance to see how such PoI can be built in practice.

Roles and components

In Ledgera, nodes may play any of the following four roles:

• client: In this role, the node formats, signs, and sends computation requests, storage requests or argument proposals to the Ledgera network and handles the returned results and proofs.
• voter: In this role, the node votes on granting write access to storage, executes computations locally and vote on the result integrity, produces proofs of storage and of the integrity of computation results.
• storage: In this role, the node maintains a persistent replicated storage of data which guarantees that if a proof of storage exists, then the corresponding data is available in at least one honest storage component.
• logger: In this role, the node maintains an append-only auditable log of events which allows for audit and enable agreement on concrete values for unknown arguments of computations.