Consensus protocols in distributed computing systems

A method comprising:

• receiving a final proof from a miner, the miner:
• receiving client data from a client;
• storing the received client data using miner-accessible storage that is not publicly accessible;
• receiving an initial input challenge at a start time, the initial input challenge having a start time time-stamp indicating the start time;
• producing an initial proof responsive to the initial input challenge, the initial proof proving that the miner is storing the received client data;
• generating a new input challenge based at least in part on the initial proof;
• producing a new proof responsive to the new input challenge, the new proof proving that the miner is storing the received client data;
• and
• repeating the generating step and the producing a new proof step a specified number of times wherein each generating step is based at least in part on a most recent new proof, to produce a final proof at a final proof time, the final proof proving the storage of the received client data over time, wherein the received client data is stored using miner-accessible storage that is not publicly accessible;
• receiving the final proof from the miner, the final proof having a final proof time-stamp indicating the time the final proof is received;
• determining that the time between the start time time-stamp and the final proof time-stamp is less than a specified period of time;
• electing a miner from the plurality of candidate miners at a specified point in time where the probability of winning the election by a candidate miner is proportional to the candidate miner's assigned storage which is indicated at least in part by a candidate miner's final proof proving the storage of the received client data during the time between the start time time-stamp and the final proof time-stamp;
• receiving a new block from the elected miner;
• and
• adding the new block to a blockchain-based file storage system.

A system comprising:

• one or more computers and one or more storage devices on which are stored instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising:
• receiving a final proof from a prover, the prover:
• receiving client data from a client;
• storing the received client data using prover-accessible storage that is not publicly accessible;
• receiving an initial input challenge at a start time, the initial input challenge having a time-stamp indicating the start time;
• producing an initial proof responsive to the initial input challenge, the initial proof proving that the prover is storing the received client data;
• generating at the prover a new input challenge based at least in part on the initial proof;
• producing a new proof responsive to the new input challenge, the new proof proving that the prover is storing the received client data;
• and
• repeating the generating step and the producing a new proof step a number of times, wherein each generating step is based at least in part on a most recent proof, to produce a final proof proving the storage of the received client data over time, wherein the received client data is stored using prover-accessible storage that is not publicly accessible;
• receiving the final proof, the final proof having a final proof time-stamp indicating the time the proof result is received;
• determining that the time between the start time time-stamp and the final proof time-stamp is less than a specified period of time;
• determining a winning prover from a plurality of candidate provers where a probability of a candidate prover being a winning prover is proportional to the candidate prover's assigned storage which is indicated at least in part by a candidate miner's proof proving the storage of the received client data during the time between the start time and the final proof time;
• receiving a new block from the winning prover;
• and
• adding the new block to a blockchain-based file storage system.