Proof-of-Archival-Storage
Public Parameters and Values
Protocol Constants
These parameters are fixed at the beginning of the protocol and used by all clients.
-
SLOT_PROBABILITY
: the probability of successful block in a slot (active slots coefficient), currently 1/6. This defines the expected block production rate of 1 block every 6 seconds -
INITIAL_SOLUTION_RANGE
: solution range for proof-of-replication challenge for the first era -
ERA_DURATION_IN_BLOCKS
: solution range is adjusted after this many blocks, currently 2016 (as in Bitcoin) -
KZG_PUBLIC_PARAMETERS
: universal reference values for KZG Polynomial Commitment scheme obtained through an MPC ceremony -
KZG_MAX_DEGREE
is : the maximum degree of the polynomial possible to commit to under the KZG scheme -
CONFIRMATION_DEPTH_K
: minimal depth after which a block can enter the recorded history (a global constant, as opposed to the client-dependent transaction confirmation depth), currently 100 -
EXPECTED_VOTES_PER_BLOCK
: number of votes expected per block, currently 9 -
SAFE_BYTES
is 31 bytes: the size into which raw history data is partitioned before Archiving for KZG commitment, required to ensure that values fit the size of the point subgroup of BLS12-381 curve -
FULL_BYTES
is 32 bytes: the size into which encoded data is partitioned after Archiving -
NUM_CHUNKS
is : number of KZG field elements that compose a record,NUM_CHUNKS
≤KZG_MAX_DEGREE
. -
NUM_S_BUCKETS
: number of s-buckets in a record (and by extension in plot sector), currently (NUM_CHUNKS / ERASURE_CODING_RATE
) -
RAW_RECORD_SIZE
is 1 MiB: the size of a record of raw blockchain history before Archiving to be transformed into a piece (SAFE_BYTES * NUM_CHUNKS = 1015808 b
) -
NUM_RAW_RECORDS
is 128: the number of raw records in a Recorded History Segment -
RECORDED_HISTORY_SEGMENT_SIZE
is roughly 128 MiB: size of raw recorded history segment ready for Archiving (RAW_RECORD_SIZE * NUM_RAW_RECORDS
) -
RECORD_SIZE
is 1 MiB: the size of useful data in one piece (FULL_BYTES * NUM_CHUNKS = 1048576 b
) -
WITNESS_SIZE
is 48 bytes: the size of KZG witness -
COMMITMENT_SIZE
is 48 bytes: the size of KZG commitment -
PIECE_SIZE
is 1 MiB: a piece of blockchain history (RECORD_SIZE + COMMITMENT_SIZE + WITNESS_SIZE = 1048672 b
) -
ERASURE_CODING_RATE
: parameter of erasure code operation, specifies what portion of data is enough to recover it fully in case of loss, currently 1/2 -
NUM_PIECES
is 256: the number of pieces in an Archived History Segment after erasure coding (NUM_RAW_RECORDS/ERASURE_CODING_RATE
) -
K
: space parameter (memory hardness) for proof-of-space, currently 20 -
RECENT_SEGMENTS
: number of latest archived segments that are considered Recent History for the purposes of Plotting (currently 3) -
RECENT_HISTORY_FRACTION
: fraction of recently archived pieces from theRECENT_SEGMENTS
in each sector (currently 1/10) -
MIN_SECTOR_LIFETIME
: minimum lifetime of a plotted sector, measured in archived segments, currently 4
Dynamic Blockchain Values
These parameters are derived from the blockchain and are dynamically updated over time.
slot_number
: current slot number, derived since genesis from the Proof-of-Time chainsolution_range
: farming difficulty parameter, dynamically adjusted to control the block generation ratevoting_solution_range
: voting difficulty parameter, dynamically adjusted to control the vote generation rate. This range is larger thansolution_range
to allow for multiple votes per block (solution_range * (EXPECTED_VOTES_PER_BLOCK+1)
)global_randomness
: used to derive slot challenges, from the Proof-of-Time chainpieces[]
: all pieces of the recorded blockchain historyhistory_size
: number of archived segments of the blockchain history until this momentsegment_commitments[]
: hash map of KZG commitments computed over pieces in a segment and stored in the runtimeBlockList
: list of public keys that committed offenses
Consensus Parameters
These parameters are fixed at the beginning of the protocol and used by all clients, however they can be updated if necessary.
max_pieces_in_sector
: number of pieces to be retrieved from blockchain history by a farmer under Verifiable Sector Construction (VSC) and encoded in a single sector by an honest farmer, currently 1000sector_size
: size of a plotted sector on disk, currently ~1 GiB (max_pieces_in_sector * RECORD_SIZE
)
Archiving
Preparing the history
-
The genesis block is archived as soon as it produced. We extend the encoding of the genesis block with extra pseudorandom data up to
RECORDED_HISTORY_SEGMENT_SIZE
, such that the very first archived segment can be produced right away, bootstrapping the farming process. This extra data is added to the end of the SCALE-encoded block, so during decoding of the genesis block it'll be ignored. -
Once any block produced after genesis becomes
CONFIRMATION_DEPTH_K
-deep, it is included in the recorded history. Recorded history is added to a buffer of capacityRECORDED_HISTORY_SEGMENT_SIZE
. -
When added to the buffer, blocks are turned into
SegmentItem
s. -
Each segment will have parent
segment_header
included as the first item. Eachsegment_header
includes hash of the previous segment header and the segment commitment of the previous segment. Together segment headers form a chain that is used for quick and efficient verification that somepiece
corresponds to the actual archival history of the blockchain. -
Segment items are combined into segments. Each segment contains at least two of the following
SegmentItem
s, in this order:- The previous segment’s
SegmentHeader
BlockContinuation
, if remained from the previous segmentBlock
(s), as many as fit fully into the current segment, may be noneBlockStart
, if the next block doesn't fit within the current segmentPadding
(zero or more) in case padding bytes are necessary to complete the segment toRECORDED_HISTORY_SEGMENT_SIZE
- The previous segment’s
-
When the buffer (after SCALE-encode) contains enough data to fill a record of
RAW_RECORD_SIZE
bytes, it is archived:- Split the record into = =
NUM_CHUNKS
chunks of sizeSAFE_BYTES
. - Interpolate a
polynomial
over the chunks of the record withpoly(record)
. - Commit to the record polynomial under KZG and obtain the source
record_commitment
asCommit(polynomial)
. This will allow us to later compute proofs that a chunk belongs to a particular record.
- Split the record into = =
-
Once
NUM_RAW_RECORDS
(128) records have been committed, stack them into a matrix ofNUM_RAW_RECORDS
rows and columns. Each row is a record. -
Erasure code records column-wise with
extend(column, ERASURE_CODING_RATE)
This effectively doubles the number of rows and thus, records per segment to
NUM_PIECES
(256). -
Erasure code commitments with
extend(record_commitments, ERASURE_CODING_RATE)
. -
Hash each
record_commitment
, both source and parity, into 254-bit scalarrecord_commitment_hash
es values . -
Interpolate a polynomial
segment_polynomial
over these hashes and commit to it under KZG to get thesegment_commitment
ascommit(Poly(record_commitment_hashes))
. -
For each
record_commitment_hashes[i]
, compute arecord_witness
to thesegment_commitment
ascreate_witness(segment_polynomial, i)
.This will allow us to prove that a record belongs to an archived history segment without having to provide all other segment commitments at a cost of storing additional 48 bytes per piece.
-
For each record, form a
piece = record || record_commitment || record_witness
-
Append the
segment_commitment
to the globalsegment_commitments[]
table of the chain. -
The segment now consists of
NUM_PIECES
records of 1MiB each,NUM_PIECES
piece commitments,NUM_PIECES
proofs of 48 bytes each and one 48-bytesegment_commitment
.The pieces with even indices ((0, 2, …, 254) of this segment) correspond to source records and the pieces with odd indices ((1, 3, …, 255)of this segment) correspond to parity records. The blockchain history data is effectively contained only in pieces with an even
piece_index
.
Plotting
Pre-plotting Initialization
Determining and retrieving the assigned portion of the history
-
Given the total allocated disk space, reserve some space () for commitments and other auxiliary information.
-
Create a single plot of
plot_size = allocated_plotting_space
. Sizes of farmer plots are independent from size of blockchain history, but must be a multiple ofsector_size
. -
Generate a farmer identity, that is a key pair
public_key, secret_key
under the digital signature scheme. These signing keys are independent from reward address of an entity (exactly as payout address in Bitcoin mining) described in Block reward address. -
Derive an identifier
public_key_hash
ashash(public_key)
. This farmer id will also serve as the basis for their single global network peer id in the DHT. -
Determine the
sector_count = plot_size / sector_size
. -
Verifiable Sector Construction (VSC):
Determine which pieces are to be downloaded for this sector:
- Index the sectors sequentially and for each sector derive
sector_id = keyed_hash(public_key_hash, sector_index || history_size)
, wheresector_index
is the sector index in the plot andhistory_size
is the current history size at the time of sector creation. - For each sector, for each
piece_offset
in0..max_pieces_in_sector
, derive thepiece_index
in global blockchain history this slot will contain, as follows:- At the start of the chain, if
history_size <= RECENT_SEGMENTS / RECENT_HISTORY_FRACTION
the pieces for this sector are selected uniformly aspiece_index = keyed_hash(piece_offset, sector_id) mod (history_size * NUM_PIECES)
forpiece_offset
in0..max_pieces_in_sector
- Later, when history grows (
history_size > RECENT_SEGMENTS / RECENT_HISTORY_FRACTION
) to make sure recent archived history is plotted on farmer storage as soon as possible we selectRECENT_HISTORY_FRACTION
of pieces for each sector from the lastRECENT_SEGMENTS
archived segments. - For
piece_offset
in0..max_pieces_in_sector * RECENT_HISTORY_FRACTION * 2
:- If
piece_offset
is odd, select a piece from recent history aspiece_index = keyed_hash(piece_offset, sector_id) mod (RECENT_SEGMENTS * NUM_PIECES) + ((history_size - RECENT_SEGMENTS) * NUM_PIECES)
- If
piece_offset
is even, select a piece uniformly from all history aspiece_index = keyed_hash(piece_offset, sector_id) mod (history_size * NUM_PIECES)
- If
- The rest of the pieces for this sector are selected uniformly as
piece_index = keyed_hash(piece_offset, sector_id) mod (history_size * NUM_PIECES)
forpiece_offset
in(2 * RECENT_HISTORY_FRACTION * max_pieces_in_sector)..max_pieces_in_sector
- At the start of the chain, if
- Retain the
history_size
count at the time of sector creation. This sector will expire at a point in the future as described in Sector Expiration.
- Index the sectors sequentially and for each sector derive
-
Retrieve each piece from the Distributed Storage Network (DSN) and verify against segment commitment obtained from the node.
- For each synced sector, proceed to Plotting phase.
Plotting to Disk
Sealing the history
For each sector, given that all pieces assigned to the sector reside locally in memory, encode pieces row-wise (piece by piece or one piece at a time).
For each piece in the sector:
-
Extract the bundled record from the piece and retain the
record_witness
andrecord_commitment
alongside the plot. -
Split the extracted record into
FULL_BYTES
-sizedrecord_chunks
, which are guaranteed to contain values that fit into the scalar field. -
Erasure code the record with
extended_chunks = extend(record_chunks, ERASURE_CODING_RATE)
-
Derive an
evaluation_seed
fromsector_id
andpiece_offset
within this sector asevaluation_seed = hash(sector_id || piece_offset)
-
Derive a Chia proof-of-space table
pos_table = generate(K, evaluation_seed)
-
Initialize
num_successfully_encoded_chunks = 0
to indicate how many chunks were encoded so far. -
Iterate through each
(s_bucket, chunk)
inextended_chunks
:- Query the
pos_table
for a valid proof-of-spaceproof_of_space
for this chunk asfind_proof(pos_table, s_bucket)
. - If it exists, encode the current chunk as
encode(chunk, hash(proof_of_space))
and increasenum_successfully_encoded_chunks
by 1. Otherwise, continue to the next chunk. - Place the encoded chunk into a corresponding s-bucket for given index
s_bucket
and set corresponding bit in theencoded_chunks_used
bitfield to1
.
- Query the
-
If
num_successfully_encoded_chunks >= NUM_CHUNKS
all chunks were encoded successfully, take the necessaryNUM_CHUNKS
and proceed to the next record. -
Else, if
num_successfully_encoded_chunks < NUM_CHUNKS
, select extra chunks to store at the end after encoded chunks:- Compute
num_unproven = NUM_CHUNKS - num_successfully_encoded_chunks
- Save as
extra_chunks
the firstnum_unproven
chunks of the source record corresponding to the indices whereencoded_chunks_used
is not set.
- Compute
-
Once all records are encoded, write the sector to disk, one s-bucket at time in order of the index, each followed by
encoded_chunks_used
bitfield corresponding to selected chunks. -
The final plotted sector consists of
max_pieces_in_sector
manyencoded_chunks_used
bitfields of sizeNUM_S_BUCKETS
each,NUM_S_BUCKETS
s-buckets and commitments and witnesses of pieces in this sector.Each
encoded_chunks_used
indicator vector has bit set to1
at places corresponding to the record positions whose chunks are encoded in this s-bucket and are eligible for farming.
Sector Expiration
After MIN_SECTOR_LIFETIME
segments were archived (since sector creation), the farmer should check whether the sector have expired and can no longer be farmed based on the “age” (history size at plotting) of each sector.
For each sector sector_id
and history_size
when this sector was plotted:
- When current history size of the chain reaches
sector_expiration_check_history_size = history_size + MIN_SECTOR_LIFETIME
farmer should check when to expire this sector based on correspondingsegment_commitment
of last archived segment. - Compute
sector_max_lifetime = MIN_SECTOR_LIFETIME + 4 * history_size
. With this limitation on sector lifetime, a sector with expire with probability ~50% by the time history doubles since it’s initial plotting point and is guaranteed to expire by the time history doubles again. - Compute
expiration_history_size = hash(sector_id || segment_commitment) mod (sector_max_lifetime - sector_expiration_check_history_size) + sector_expiration_check_history_size
- When the current history size reaches
expiration_history_size
, expire this sector. - Replot the sector for new history size as described in Plotting.
Farming
Auditing the history
Challenge Generation
- For each
slot_number
, compute theglobal_challenge
ashash(global_randomness||slot_number)
. Theslot_number
andglobal_randomness
are derived from PoT (see derive_global_randomness). - Compute the
sector_slot_challenge = global_challenge XOR sector_id
- Compute the
s_bucket_audit_index = sector_slot_challenge mod NUM_S_BUCKETS
Audit
- Read the corresponding s-bucket at
s_bucket_audit_index
from disk into memory. - For each
chunk
in the bucket, computeaudit_chunk = keyed_hash(sector_slot_challenge, chunk)
, truncated to 8 bytes - Check if the result (as integer) falls within +/-
voting_solution_range/2
of theglobal_challenge
- Sort all the potentially winning
audit_chunks
by their “quality” - the closest toglobal_challenge
first. - Prove the best chunk and submit the solution.
Proving
-
For a winning
audit_chunk
(8 bytes), derive thechunk_offset
from the parent full chunk’s position in the s-bucket. -
Get the full 32 byte
chunk
at thatchunk_offset
. -
From
encoded_chunks_used
bitfields determine if it is an encoded chunk. -
If not, chunk is not eligible for proving.
-
If yes, then determine parent record
piece_offset
of thischunk
. -
Compute the steps 1-7 in Recovering the Record and obtain
plotted_chunks
-
Save the
proof_of_space
for thischunk
used for decoding -
Recover the
extended_chunks_poly
using decoded chunks withrecover_poly(plotted_chunks)
. -
Retrieve the
record_commitment
. -
Compute the
chunk_witness
for the decoded winningchunk
that ties back to therecord_commitment
ascreate_witness(extended_chunks_poly, s_bucket_audit_index)
, and attach both to the solution for verification against the original record commitment stored in the history. -
Retrieve the
record_witness
that ties back to thesegment_commitment
. -
Produce a
solution
consisting ofstruct Solution {
public_key: 32 bytes
reward_address: 32 bytes
sector_index: 2 bytes
history_size: 8 bytes
piece_offset: 2 bytes
record_commitment: 48 bytes
record_witness: 48 bytes
chunk: 32 bytes
chunk_witness: 48 bytes
proof_of_space: 160 bytes
}
Submitting a solution
If the winning audit_chunk
is within solution_range
:
- Attach
solution
to block header. - Forge a new
block
(as defined in Substrate framework). - Seal the
block
content withsign(secret_key, block)
.
Otherwise, submit a vote extrinsic with solution
.
Verification
Ensuring a solution comes from a valid plot
- If the
public_key
of the block's farmer is in the block list, ignore the block. - Verify that the consensus log in the block header is correct. This includes
solution_range
andglobal_randomness
. - Verify that PoT items in the header are correct according to New Blocks
- Verify that
solution_range
andglobal_randomness
are correct for theslot_number
of the block. - Compute the
global_challenge = hash(global_randomness||slot_number)
. - Verify that current chain history size in segments is greater than winning
piece_index / NUM_PIECES
. - Verify that
piece_offset ≤ max_pieces_in_sector
- Re-derive
sector_id
- Compute
public_key_hash = hash(public_key)
- Re-derive the
sector_id = keyed_hash(public_key_hash, sector_index || history_size)
- Compute
- Verify that the
sector_id
submitted has not expired:- Compute
sector_expiration_check_history_size = history_size + MIN_SECTOR_LIFETIME
andsector_max_lifetime = MIN_SECTOR_LIFETIME + 4 * history_size
. - Take the archived segment
segment_commitment
atsector_expiration_check_history_size
. - Compute
expiration_history_size = hash(sector_id||segment_commitment) mod (sector_max_lifetime - sector_expiration_check_history_size) + sector_expiration_check_history_size
- Check that
expiration_history_size
is smaller than current history size of the chain.
- Compute
- Re-derive the
sector_slot_challenge = global_challenge XOR sector_id
- Re-derive the
s_bucket_audit_index = sector_slot_challenge mod NUM_S_BUCKETS
- Re-derive the
evaluation_seed
for the record from thesector_id
andpiece_offset
ashash(sector_id || piece_offset)
- Verify
proof_of_space
withIs_Proof_Valid(K, evaluation_seed, s_bucket_audit_index, proof_of_space)
- Ensure the
chunk
satisfies the challenge criteria:- Compute the
masked_chunk
asEncode(chunk, hash(proof_of_space))
- Compute the keyed hash
keyed_hash(sector_slot_challenge, masked_chunk)
truncated toaudit_chunk
size - Ensure the result falls within +/-
solution_range/2
of theglobal_challenge
- Compute the
- Ensure the provided
chunk
was correctly extended from a history piece for the assigned record commitment:- Verify the
chunk_witness
for the givenchunk
,record_commitment
, ands_bucket_audit_index
- Verify the
- Ensure the encoded record belongs to the assigned slot and that record also belongs to the history:
- Re-derive the
piece_index
from thepiece_offset
andhistory_size
the same way as during pre-plotting (as described in Verifiable Sector Construction) - Retrieve the
segment_commitment
of the segment that contains the assignedpiece_index
- Hash the
record_commitment
to obtain therecord_commitment_hash
- Verify the
record_witness
for thepiece_index
,record_commitment_hash
andsegment_commitment
- Re-derive the
- Ensure the farmer did not outsource solving to a third-party without revealing their private keys by verifying the
farmer_signature
with thepublic_key
andchunk
. - Verify the signature on the block content.
- If another block signed with the solution with same solution (
public_key
,sector_index
,piece_offset
,chunk
,chunk_audit_index
andslot_number
) had already been received, report an equivocation bypublic_key
and ignore the block.
The above steps assume standard block and transaction verification.
Extraction
Serving data from the plot
- When requested a piece at
piece_index
identifysector_index
andpiece_offset
where that piece is stored. - For the record plotted at
piece_offset
in that sector perform record recovery and compose the piece.
Recovering the Record
- From the record’s
encoded_chunks_used
bitfield determine which s-buckets contain chunks of this record. - Read all the
plotted_chunks
of the parent record from their respective s-buckets. Set the encoded chunk valueNone
in places whereencoded_chunks_used
is0
. Total length ofplotted_chunks
should beNUM_CHUNKS/ERASURE_CODING_RATE
. - Derive the
evaluation_seed
for the record fromsector_id
andpiece_offset
within this sector asevaluation_seed = hash(sector_id || piece_offset)
- Derive a Chia proof-of-space table
pos_table = generate(K, evaluation_seed)
- Iterate through each
(s_bucket, plotted_chunk)
inplotted_chunks
:- If
plotted_chunk
isNone
, continue to next chunk. - Else, query the
pos_table
for a valid proof-of-spaceproof_of_space
for this chunk asfind_proof(pos_table, s_bucket)
. The proof should exist if the chunk was encoded and plotted. - Decode the chunk in-place with
decode(plotted_chunk, hash(proof_of_space))
.
- If
- If the number of
plotted_chunks
is less thenNUM_CHUNKS
, we need extra chunks to recover the record. Insert eachextra_chunk
in places ofNone
inplotted_chunks
from the beginning, however many extra chunks there are. - Recover the source
record
from the decoded chunks withrecover(plotted_chunks))
.
Composing the Piece
- Retrieve the
record_commitment
andrecord_witness
from the sector table. - Return the recovered piece as
record || record_commitment || record_witness
.
Randomness Updates
Global randomness is updated every slot with the output of Proof-of-Time chain for that slot. See Proof-of-Time Specification.
Solution Range Updates
Initial solution range INITIAL_SOLUTION_RANGE
is computed based on a single plotted sector with the goal of getting a single winning chunk in each slot with probability SLOT_PROBABILITY
, as follows:
Let num_audit_chunks
be the number of tickets read during single slot audit in a sector. For each piece (max_pieces_in_sector
), we audit a single full chunk in a single s-bucket. The probability of s-bucket containing a full chunk at that position is NUM_CHUNKS/NUM_S_BUCKETS
(1/2). Thus, a farmer has this many tickets at each slot:
To compute initial solution range for one sector, maximum possible solution range (U64::MAX
) is divided by num_chunks
and multiplied by slot probability:
INITIAL_SOLUTION_RANGE
becomes solution_range
for the first era.
Global solution_range
is adjusted every era accordingly to actual and expected blocks produced per era to keep block production at the same pace while space pledged on the network change:
- After every
ERA_DURATION_IN_BLOCKS
number of blocks, a new era begins. - At the start of a new era, compute and store new
solution_range
.
Conversion Rate Between Solution Range and Space Pledged
The relationship between the solution range and the amount of space pledged is dynamically calculated using the function solution_range_to_sectors
. This function computes the number of sectors corresponding to a given solution range by adjusting for slot probability and the configuration of data within sectors. Specifically, the maximum possible solution range (SolutionRange::MAX
) is first reduced according to the slot probability, which reflects the desired frequency of successful block production. This is further adjusted by the distribution of data, particularly the ratio of the number of chunks per s-bucket in each sector (MAX_PIECES_IN_SECTOR * Record::NUM_CHUNKS / Record::NUM_S_BUCKETS
), to account for the probability of an occupied s-bucket being successfully audited in the verification process. The resulting figure is then divided by the current solution range to determine the total number of sectors that this solution range can effectively cover.
const fn solution_range_to_sectors(solution_range: SolutionRange) -> u64 {
let sectors = SolutionRange::MAX
// Account for slot probability
/ SLOT_PROBABILITY.1 * SLOT_PROBABILITY.0
// Now take sector size and probability of hitting occupied s-bucket in sector into account
/ (MAX_PIECES_IN_SECTOR as u64 * Record::NUM_CHUNKS as u64 / Record::NUM_S_BUCKETS as u64);
// Take solution range into account
sectors / solution_range
}