Challenges

In-depth walkthrough of Züs System Storage Challenges.

Challenges are the means by which blobbers get rewards for storing users' data, also validators get reward for verifying those challenges. Let's take a look into the flow of challenge generation, verification and response through the different nodes of the system

Challenge Generation

For each block generated by the miners, one generate_challenge transaction is added by the miners. Following is the details of the txn. Check protocol_block.go

	brTxn := transaction.Provider().(*transaction.Transaction)
	brTxn.ClientID = node.Self.ID
	brTxn.PublicKey = node.Self.PublicKey
	brTxn.ToClientID = storagesc.ADDRESS
	brTxn.CreationDate = b.CreationDate
	brTxn.TransactionType = transaction.TxnTypeSmartContract
	brTxn.TransactionData = fmt.Sprintf(`{"name":"generate_challenge","input":{"round":%d}}`, b.Round)
	brTxn.Fee = 0

In block verification step, the miner runs the txns of the block, including the generate_challenge txn, against the smart contracts.
This txn is handled by: storageSmartContract.generateChallenge and on the condition that the config: smartcontracts.storagesc.challenge_enabled is true (check sc.yaml). The smart contract does some checks:
- If the round field in the txn data is the same as the current round running
- If the current healthy validators is more than or equal to the config: smartcontracts.storagesc.validators_per_challenge
Healthy means it sent a health check beat in less than an hour
- If there is blobbers to be challenged
- After selecting a random blobber, if this selected blobber has allocations to be challenged.
- After selecting an allocation hosted on that blobber to be challenged, If this allocation is valid for challenging on this blobber particularly (i.e. It has data and the blobber knows that, i.e. UsedSize > 0 && blobberAlloc.AllocationRoot != ''
- If this allocation isn't finalized nor expired
As a side effect, if the allocation is finalized, The allocation is removed from the list of allocations for this blobber in the MPT
If all the conditions pass, the allocation is generated with the following data:

	var storageChallenge = new(StorageChallenge)
	storageChallenge.ID = challengeID
	storageChallenge.TotalValidators = len(selectedValidators)
	storageChallenge.ValidatorIDs = validatorIDs
	storageChallenge.BlobberID = blobberID
	storageChallenge.AllocationID = alloc.ID
	storageChallenge.Created = txn.CreationDate
	storageChallenge.RoundCreatedAt = balances.GetBlock().Round

	challInfo := &StorageChallengeResponse{
		StorageChallenge: storageChallenge,
		Validators:       selectedValidators,
		Seed:             seed,
		AllocationRoot:   allocBlobber.AllocationRoot,
		Timestamp:        allocBlobber.LastWriteMarker.Timestamp,
	}

It then removes all expired challenges from the MPT, updates the stats fields related to challenge of the selected allocation and blobAlloc and finally adds three events to be run by the sharder after the block is finalized: TagAddChallenge, TagAddChallengeToAllocation and TagUpdateBlobberOpenChallenges
When the sharder runs the events, following changes are applied to the db:
- Add the challenge to the challenges table
- Update total_challenges, open_challenges, failed_challengesfor the allocation selected.
- Update open_challenges. for the selected blobber

Sync. of challenges in the blobbers

On startup, the blobber runs a worker that synchronizes the challenges with the network. That is by periodically sending http requests to the sharders to get the open challenges. The endpoint used is: /v1/screst/6dba10422e368813802877a85039d3985d96760ed844092319743fb3a76712d7/openchallenges?blobber=<sending_blobber_id>&limit=50&from=<round_lower_bound>\
The challenges are then sorted asc. by round of creation and sent to a channel: toProcessChallenge to another goroutine within the challenges worker that processes those challenges

Challenge Processing in Blobbers

The blobber starts by checking if the challenge already exists in the blobber's db, if so it ignores the challenge
If it's not found, It's added to the list of challenges the blobber perserves in memory. The blobbers assigns the processing of this challenge to one of its workers (their number is challenge_response.num_workers in 0chain_blobber.yaml). This worker pool is virtualized by a weighted semaphore. Check challengeProcessor in 0chain.net/blobbercore/challenge/worker.go.
First step is adding 2 entries to the blobber's db, the challenge itself and challenge_timing.
Loads the write markers related to that allocation from the timestamp of the challenge on from the db.
Selects a random block of the allocation and computes object_path of this block.
The blobber computes the challenge_proof which will be used by the validator for verification as the MPT Path of the allocation.
The blobber then sends validation requests to the validators with validatorIds defined in the challenge info to receive validation ticket from each of the validators. The endpoint used is: POST /v1/storage/challenge/new with the following data

type ChallengeRequest struct {
	ChallengeID    string                           `json:"challenge_id"`
	ObjPath        *ObjectPath                      `json:"object_path,omitempty"`
	WriteMarkers   []*writemarker.WriteMarkerEntity `json:"write_markers,omitempty"`
	ChallengeProof *ChallengeProof                  `json:"challenge_proof"`
}

type ObjectPath struct {
	RootHash     string                 `json:"root_hash"`
	Meta         *FileMetaData          `json:"meta_data"`
	Path         map[string]interface{} `json:"path"`
	FileBlockNum int64                  `json:"file_block_num"`
	RootObject   *DirMetaData           `json:"-"`
}

type WriteMarkerEntity struct {
	ClientPublicKey string       `json:"client_key"`
	WM              *WriteMarker `json:"write_marker"`
}

type WriteMarker struct {
	AllocationRoot         string           `json:"allocation_root"`
	PreviousAllocationRoot string           `json:"prev_allocation_root"`
	FileMetaRoot           string           `json:"file_meta_root"`
	AllocationID           string           `json:"allocation_id"`
	Size                   int64            `json:"size"`
	BlobberID              string           `json:"blobber_id"`
	Timestamp              common.Timestamp `json:"timestamp"`
	ClientID               string           `json:"client_id"`
	Signature              string           `json:"signature"`
}

type ChallengeProof struct {
	Proof   [][]byte `json:"proof"`
	Data    []byte   `json:"data"`
	LeafInd int      `json:"leaf_ind"`
}

Challenge result is determined based on the recieved response from the validators
- If received valid success tickets from more than 1/2 the validators, even if the other validators didn't respond at all => Passed challenge
- If received valid tickets from more than 1/2 the validators, whatever the status is, but not more than 1/2 the validators sent success tickets, even if the other validators didn't respond at all => Failed challenge
- If didn't receive valid tickets at all from 1/2 of the validators => Cancelled
- Validation in the blobber of the ticket is as follows
```
func (vt *ValidationTicket) VerifySign() (bool, error) {
	hashData := fmt.Sprintf("%v:%v:%v:%v:%v:%v", vt.ChallengeID, vt.BlobberID, vt.ValidatorID, vt.ValidatorKey, vt.Result, vt.Timestamp)
	hash := encryption.Hash(hashData)
	verified, err := encryption.Verify(vt.ValidatorKey, vt.Signature, hash)
	return verified, err
}
```
Blobber then updates the status of the challenge to Processed, its UpdatedAt (both in memory) then updated challenge_timing.complete_validation for all the processed challenges in the db.

Challenge Validation in the Validators

The validator starts by getting allocation info from the network using gosdk. Check Transaction.Verify in 0chain.net/core/entity.go in blobber repo. Basically is gets the allocation info by sending a request to the endpoint that returns transaction confirmation and then uses transaction output as allocation info.
It also gets the challenges as saved in the network by sending a GET request to the endpoint: `v1/screst/6dba10422e368813802877a85039d3985d96760ed844092319743fb3a76712d7/getchallenge?blobber=<BlobberId>&challenge=<ChallengeID>
The validators then decodes the challenge request and starts verifying its parameters:
- Verifies object path.
- Verifies write markers.
  - Checks if their creation is the same as the challenge's timestamp from the chain.
  - Checks if their allocation is the same as the one got from the chain for this challenge
  - Compare's the write marker's clientId with the write markers client id
  - Verifies the signature of the write marker
- Checks the order of the write markers, i.e. each write marker's PreviousAllocationRoot should be the same as the AllocationRoot of the previous write marker.
- If ObjectPath is sent in the challenge request, compares the AllocationRoot of the last WM with the AllocationRoot calculated from ObjectPath, otherwise checks it's not empty
- Computes a Merkle path from the challenge_proof sent and verifies it's correctness
- The validator then build a validation ticket, signs it and sends it back to the blobber. Its components is as follows:
```
	var validationTicket ValidationTicket

	validationTicket.BlobberID = challengeObj.BlobberID
	validationTicket.ChallengeID = challengeObj.ID
	validationTicket.Result = true
	validationTicket.MessageCode = "success"
	validationTicket.Message = "Challenge passed"
	validationTicket.ValidatorID = node.Self.ID
	validationTicket.ValidatorKey = node.Self.PublicKey
	validationTicket.Timestamp = common.Now()
```

Blobbers' sending challenge response to the network to get reward

Aside from the challenges worker, the blobbers also runs a worker that is responsible for syncing the challenge response with the chain after they're processed: commitOnChainWorker

The worker handles the challenges in batches of 5 (hardcoded), reading them from the in-memory treemap the blobbers maintains for challenges. It will only handle a ticket if its status is Processed. If no challenges were found that meet the criteria, will sleep for 2 secs (hardcoded) and tries again.
The blobber checks the expiry of the challenge. A challenge is expired when the time elapsed since its creation time is more than max_challenge_completion_time config which the blobber gets from the chain. (check sc.yaml)
It then submits a challenge_response transaction to the network with the following data:

type ChallengeResponse struct {
	ChallengeID       string              `json:"challenge_id"`
	ValidationTickets []*ValidationTicket `json:"validation_tickets"`
}

It makes sure the txn is confirmed by getting its txn confirmation from the sharder.
It then updates the challenge_timing.txn_submission in the db.

Processing challenge request in the chain (storage smart contract)

The data of the request is validated thus ChallengeID is not zero and ValidationTickets are not empty. Also checks if the challenge is already processed, as well as that the blobber sending this txn is the same as the challenged blobber by this challenge.
It then verifies the tickets
- Checks each ticket is sent by the challenged blobber and addressed to this challenge.
- Checks the public key of the validator
- Checks the number of the valid tickets and if it's more than half validators
- Checks the signature of the validator on the ticket
- Also checks the expiry of the challenge
Checks also if the allocation challenged is not finalized and checks the challenged blobber belongs to that allocation
Checks that this challenge isn't already redeemed.
If all these checks pass, then this challenge passes, where the miner does the following:
- Updates stats for allocation and blobber
- Emits the events:
  TagUpdateChallenge, TagUpdateAllocationChallenge, TagUpdateBlobberChallenge
- Runs the flow of validator and blobber rewarding.
- Checks if the latestFinalizedChallenge is sooner than the latestSuccessfulChallenge (i.e there are failing challenges) and runs the penalization flow of the blobber based on these failing challenges.
If the checks are not passing then the challenge is failing and the miner does the following:
- Updates stats for allocation and blobber
- Emits the events:
  TagUpdateChallenge, TagUpdateAllocationChallenge, TagUpdateBlobberChallenge
  to update the data in events_db.

If you have any questions or encounter any issues, please join our Discord for further assistance. Our team and the community members are available to help troubleshoot your concerns and provide guidance.

PreviousAllocations NextRead/Write Markers

Last updated 21 days ago