258 lines
12 KiB
Markdown
258 lines
12 KiB
Markdown
Storage proof network
|
|
=====================
|
|
|
|
Authors: Codex Team
|
|
|
|
In this document we explore a design for an off-chain network for validating
|
|
[storage proofs][1]. Instead of checking each storage proof in a smart contract
|
|
on-chain, we let the proof network check these proofs. Only when a proof is
|
|
missing we go on-chain to enact slashing. The main goal of this exercise is to
|
|
reduce the costs of submitting and validating proofs, which has shown to be a
|
|
limiting factor for the profitability of storage providers and the scaling of
|
|
the storage network, even when deploying on a [rollup][2] or [sidechain][3].
|
|
|
|
[1]: proof-erasure-coding.md
|
|
[2]: ../evaluations/rollups.md
|
|
[3]: ../evaluations/sidechains.md
|
|
|
|
Overview
|
|
--------
|
|
|
|
The main idea is that validators in the network sign off on blocks of
|
|
transactions. Transactions either contain a storage proof, or indicate that a
|
|
storage proof is missing. These validators deposit stake on-chain that allows
|
|
them to participate in a staked consensus protocol. This consensus protocol
|
|
ensures that transactions are only validated when a subset of the validators
|
|
representing > 2/3 of the total network stake have signed off on it. The
|
|
assumption here is that less than 1/3 of the validators are byzantine, meaning
|
|
that the rest is online and following protocol.
|
|
|
|
Roles in the network are:
|
|
|
|
- storage providers: they submit storage proofs
|
|
- validators: they keep track of submitted and missed proofs, and trigger
|
|
slashing on-chain
|
|
|
|
The validators form a consensus network that allows them to agree on blocks of
|
|
transactions. Storage providers submit transactions containing a storage proof
|
|
to one of the validators, which includes it in a block of transactions.
|
|
Validators also monitor the on-chain marketplace to check when storage proofs
|
|
are missed.
|
|
|
|
consensus network
|
|
|
|
--------------------------------------
|
|
storage providers | |
|
|
| validator |
|
|
--------------------- | ^ ^ |
|
|
| | | / \ |
|
|
| provider | | / \ |
|
|
| v v |
|
|
| provider <---------------------> validator <----> validator |
|
|
| ^ ^ |
|
|
| provider | | \ / |
|
|
| | | \ / |
|
|
--------------------- | v v |
|
|
^ | validator |
|
|
| | |
|
|
| --------------------------------------
|
|
| ^
|
|
| |
|
|
| ethereum |
|
|
| |
|
|
| ------------------ |
|
|
| | | |
|
|
\------- | marketplace | <--------------/
|
|
| |
|
|
------------------
|
|
|
|
Transactions
|
|
------------
|
|
|
|
The types of transactions that can be included in blocks are:
|
|
|
|
- `StorageProof(slot id, period, inputs, proof)`
|
|
- `MissingProof(slot id, period, inputs)`
|
|
|
|
Each transaction is signed by its sender. A *slot id* parameters refers to a
|
|
[slot in a storage request][4] on the marketplace. It uniquely identifies the
|
|
data for which a storage proof is required. The *period* refers to a [time
|
|
interval][5] in which the storage proof should be submitted. By *proof* we mean
|
|
a [zero-knowledge proof][5], and by *inputs* we mean its public inputs.
|
|
|
|
#### StorageProof ####
|
|
|
|
A storage provider sends a `StorageProof` transaction to a validator to indicate
|
|
to the network that it calculated a storage proof as required by the
|
|
marketplace. This validator includes it in its next block.
|
|
|
|
#### MissingProof ####
|
|
|
|
A validator includes a `MissingProof` transaction in its next block when it
|
|
notices that a required storage proof was not submitted.
|
|
|
|
[4]: marketplace.md
|
|
[5]: https://github.com/codex-storage/codex-storage-proofs-circuits#circuit
|
|
|
|
Flows
|
|
-------
|
|
|
|
### Successfull proof submission ###
|
|
|
|
Storage providers monitor the on-chain marketplace to check in which periods
|
|
they need to provide a storage proof. When a provider sees that a proof is
|
|
required for a slot in the current *period*, it gathers public *inputs* for the
|
|
slot, including the random challenge and calculates a zero-knowledge storage
|
|
*proof*. The provider then submits `StorageProof(slot id, period, inputs,
|
|
proof)` to a single validator.
|
|
|
|
|
|
StorageProof
|
|
storage provider ---------------------------------------> validator
|
|
|
|
|
|
The validator will include the transaction in the next block that it proposes to
|
|
the consensus network. When the proposed block is sequenced by the consensus
|
|
network, the validator will return an inclusion proof to the provider. This is a
|
|
proof that the transaction was included in a block, and that the consensus
|
|
network included the block.
|
|
|
|
|
|
inclusion proof
|
|
storage provider <--------------------------------------- validator
|
|
|
|
|
|
This inclusion proof doesn't need to be succinct, and can for example consist of
|
|
a record of the messages that were exchanged between validators as part of the
|
|
consensus protocol.
|
|
|
|
Notice that validators do not check the correctness of `StorageProof`
|
|
transactions prior to including them in blocks. In this design sequencing and
|
|
evaluation of transactions are separated. First, the validators reach consensus
|
|
on a sequence of blocks of transactions. Then, each of the validators evaluates
|
|
these transactions in order.
|
|
|
|
When evaluating a `StorageProof` transaction a validator checks that it was
|
|
submitted within the *period* and that the *proof* is correct w.r.t. to the
|
|
*inputs*. If that is all in order then it updates its internal accounting to
|
|
reflect that the proof was submitted and correct.
|
|
|
|
### Missing proofs ###
|
|
|
|
Validators monitor the on-chain marketplace to check which slots require a
|
|
storage proof to be submitted and what the public *inputs* for the proof are.
|
|
For each required proof they check at the end of its *period* whether that proof
|
|
was submitted and correct. If they did not receive a correct proof then they
|
|
will add a `MissingProof(slot id, period, inputs)` transaction to the next
|
|
block.
|
|
|
|
The `MissingProof` transactions are sequenced by the consensus algorithm. They
|
|
are then evaluated by each validator. They will note the first `MissingProof`
|
|
transaction that correctly notices a missing proof, and allow the sender of that
|
|
first transaction to go on-chain to mark the proof as missing.
|
|
|
|
The validator that sent the first `MissingProof` transaction for a missing proof
|
|
can now request BLS signatures from the other validators to enact on-chain
|
|
slashing of the storage provider for missing a proof. When the validator
|
|
receives enough signatures to represent > 2/3 stake it can combine these
|
|
signatures into a single combined BLS signature. The validator can then submit
|
|
*slot id*, *period*, *inputs* and the combined signature to the marketplace.
|
|
|
|
The marketplace will then verify the correctness of *inputs* for the *slot id*
|
|
and *period*, and checks that the combined signature is representative for > 2/3
|
|
stake. If these conditions are met, it will then slash the storage provider
|
|
collateral and reward the validator.
|
|
|
|
### Faulty proofs ###
|
|
|
|
The storage proofs that a storage provider submits can be faulty for a number of
|
|
reasons:
|
|
|
|
1. The zero knowledge *proof* is incorrect
|
|
2. The submitted *period* is not the current time period
|
|
3. The public *inputs* to the proof do not match the values from the on-chain
|
|
marketplace
|
|
|
|
Faults 1 and 2 are caught by the validators. Validators check the zero-knowledge
|
|
*proof*, and that the *period* is the current time period when evaluating a
|
|
`StorageProof` transaction. If these are incorrect then they ignore the
|
|
transaction, effectively treating the proof as missing. Validators now go
|
|
through the same flow that we described in the previous section.
|
|
|
|
Fault 3 is caught by the validators and the on-chain marketplace. Validators
|
|
will look for a correct `StorageProof` transaction that has the same *inputs* as
|
|
specified by the marketplace. If it doesn't find it because the storage provider
|
|
submitted a `StorageProof` transaction with a different value for *inputs*, then
|
|
it will treat the proof as missing, and go through the same flow as in the
|
|
previous section.
|
|
|
|
Consensus
|
|
---------
|
|
|
|
Our design depends on a consensus algorithm between validators. This can be any
|
|
byzantine-fault-tolerant consensus algorithm for sequencing transactions. The
|
|
[Mysticeti][6] algorithm seems to be particularly suited because it is highly
|
|
performant.
|
|
|
|
The consensus algorithm is only used to sequence transactions. Evaluation of the
|
|
transactions is done after sequencing. This means that storage proofs can be
|
|
checked in parallel, which allows validators to scale up and support a large
|
|
storage network that produces many proofs.
|
|
|
|
[6]: https://arxiv.org/pdf/2310.14821
|
|
|
|
Staking
|
|
-------
|
|
|
|
The marketplace smart contract only slashes a storage provider when there is a
|
|
combined BLS signature that represents > 2/3 stake.
|
|
|
|
It can be expensive to calculate the amount of stake associated with a combined
|
|
BLS signature on-chain. Because any combination that represents > 2/3 stake is
|
|
valid, there can be many different valid combinations. If we have to calculate
|
|
the amount of stake every time that a validator submits a combined signature
|
|
that signals that a proof was missed, then the gas fees would be prohibitive.
|
|
|
|
So instead we expect there to be pre-calculated combined public keys that
|
|
represent > 2/3 stake majorities. The gas costs for validating the stake that
|
|
these combined public keys represent can be borne by the validators when they
|
|
put down their stake.
|
|
|
|
Pros and cons
|
|
-------------
|
|
|
|
There are a couple of advantages to this design in which we use a consensus
|
|
protocol to sequence transactions.
|
|
|
|
A storage provider only needs to send its proofs to a single validator, and
|
|
the consensus protocol ensures that all validators see it.
|
|
|
|
There is no need for validators to sign off on individual storage proofs. The
|
|
[Mysticeti paper][6] points out that signing and verifying signatures is one of
|
|
the main contributors to latency in a consistent broadcast design. By only
|
|
signing entire blocks of transactions this is avoided in the Mysticeti protocol.
|
|
|
|
This design is suitable for supporting other kinds of transactions later on,
|
|
such as payments, payment channels, and marketplace interactions.
|
|
|
|
Compared to a [previous iteration][7] of this design we have one less role.
|
|
There no longer is a separate role that monitors the on-chain marketplace to
|
|
check which storage proofs are required. Also, there is no longer a race to go
|
|
on-chain to mark a proof as missing. Because we have a consensus protocol we can
|
|
select which validator goes on-chain.
|
|
|
|
In exchange for these advantages we have some drawbacks as well.
|
|
|
|
The number of validators is by necessity fairly small (in the order of < 100
|
|
validators) because of the communication between the validators. Measures can be
|
|
taken to increase the decentralization of the validators. We could for example
|
|
introduce epochs in which some validators are chosen from a larger set of
|
|
potential validators, but that comes at the expense of added complexity.
|
|
|
|
The latency is larger than in a [previous iteration][7] of this design, because
|
|
the consensus protocol requires 3 rounds of communication before it has
|
|
sequenced the transactions. That might be mitigated by using the fast path from
|
|
the Mysticeti protocol for `StorageProof` transactions.
|
|
|
|
[7]: https://github.com/codex-storage/codex-research/pull/194
|