Propose a probability of confidence setting instead of FRACTION_OF_SPACE_TO_VERIFY #2

New Issue

2023-04-13T01:01:44+02:00

Benjamin_Loison commented

2023-04-13 01:01:44 +02:00

Probability to catch an adversary:

import math

# So have to verify `numberOfCellsToVerify` cells to have a probability `probabilityToCatchMailicious` to verify that the prover stores `n - malicious` cells.
# What kind of attacks are they? Because here it seems to only be about verifying the PoW.

n = 10 ** 20
malicious = n // 100
wantedProbabilityToCatchMalicious = 1 - 2 ** -50

probabilityNotToCatchMaliciousWithOneQuery = (n - malicious) / n
print(probabilityNotToCatchMaliciousWithOneQuery)

'''
    probabilityToCatchMaliciousWithNumberOfCellsToVerifyQueries >= wantedProbabilityToCatchMalicious
<=> 1 - probabilityToCatchMaliciousWithNumberOfCellsToVerifyQueries >= wantedProbabilityToCatchMalicious
<=> 1 - probabilityNotToCatchMaliciousWithOneQuery ** numberOfCellsToVerify >= wantedProbabilityToCatchMalicious
<=> - probabilityNotToCatchMaliciousWithOneQuery ** numberOfCellsToVerify >= wantedProbabilityToCatchMalicious - 1
<=> probabilityNotToCatchMaliciousWithOneQuery ** numberOfCellsToVerify <= 1 - wantedProbabilityToCatchMalicious
<=> log(probabilityNotToCatchMaliciousWithOneQuery ** numberOfCellsToVerify) <= log(1 - wantedProbabilityToCatchMalicious)
<=> numberOfCellsToVerify * log(probabilityNotToCatchMaliciousWithOneQuery) <= log(1 - wantedProbabilityToCatchMalicious)
<=> numberOfCellsToVerify <= log(1 - wantedProbabilityToCatchMalicious) / log(probabilityNotToCatchMaliciousWithOneQuery)
I would say that we expect a lower bound for `numberOfCellsToVerify`, so there's a problem somewhere. Actually the inequality sens doesn't seem right but the bound seems right.
Can see my internship email from 15/05/23 for a shorter justification.
'''

numberOfCellsToVerify = math.ceil(math.log(1 - wantedProbabilityToCatchMalicious) / math.log(probabilityNotToCatchMaliciousWithOneQuery))
print(numberOfCellsToVerify)

## For extra-precision (starting to be useful at 54, can use https://stackoverflow.com/q/53660036 for almost arbitrary precision):

from decimal import *

getcontext().prec = 123

wantedProbabilityToCatchMalicious = Decimal(1) - Decimal(2) ** -60

probabilityNotToCatchMaliciousWithOneQuery = (Decimal(n) - Decimal(malicious)) / Decimal(n)

numberOfCellsToVerify = ((1 - wantedProbabilityToCatchMalicious).log10() / probabilityNotToCatchMaliciousWithOneQuery.log10()).to_integral_exact(rounding=ROUND_CEILING)
print(numberOfCellsToVerify)

# Probability to catch an adversary: ```py import math # So have to verify `numberOfCellsToVerify` cells to have a probability `probabilityToCatchMailicious` to verify that the prover stores `n - malicious` cells. # What kind of attacks are they? Because here it seems to only be about verifying the PoW. n = 10 ** 20 malicious = n // 100 wantedProbabilityToCatchMalicious = 1 - 2 ** -50 probabilityNotToCatchMaliciousWithOneQuery = (n - malicious) / n print(probabilityNotToCatchMaliciousWithOneQuery) ''' probabilityToCatchMaliciousWithNumberOfCellsToVerifyQueries >= wantedProbabilityToCatchMalicious <=> 1 - probabilityToCatchMaliciousWithNumberOfCellsToVerifyQueries >= wantedProbabilityToCatchMalicious <=> 1 - probabilityNotToCatchMaliciousWithOneQuery ** numberOfCellsToVerify >= wantedProbabilityToCatchMalicious <=> - probabilityNotToCatchMaliciousWithOneQuery ** numberOfCellsToVerify >= wantedProbabilityToCatchMalicious - 1 <=> probabilityNotToCatchMaliciousWithOneQuery ** numberOfCellsToVerify <= 1 - wantedProbabilityToCatchMalicious <=> log(probabilityNotToCatchMaliciousWithOneQuery ** numberOfCellsToVerify) <= log(1 - wantedProbabilityToCatchMalicious) <=> numberOfCellsToVerify * log(probabilityNotToCatchMaliciousWithOneQuery) <= log(1 - wantedProbabilityToCatchMalicious) <=> numberOfCellsToVerify <= log(1 - wantedProbabilityToCatchMalicious) / log(probabilityNotToCatchMaliciousWithOneQuery) I would say that we expect a lower bound for `numberOfCellsToVerify`, so there's a problem somewhere. Actually the inequality sens doesn't seem right but the bound seems right. Can see my internship email from 15/05/23 for a shorter justification. ''' numberOfCellsToVerify = math.ceil(math.log(1 - wantedProbabilityToCatchMalicious) / math.log(probabilityNotToCatchMaliciousWithOneQuery)) print(numberOfCellsToVerify) ## For extra-precision (starting to be useful at 54, can use https://stackoverflow.com/q/53660036 for almost arbitrary precision): from decimal import * getcontext().prec = 123 wantedProbabilityToCatchMalicious = Decimal(1) - Decimal(2) ** -60 probabilityNotToCatchMaliciousWithOneQuery = (Decimal(n) - Decimal(malicious)) / Decimal(n) numberOfCellsToVerify = ((1 - wantedProbabilityToCatchMalicious).log10() / probabilityNotToCatchMaliciousWithOneQuery.log10()).to_integral_exact(rounding=ROUND_CEILING) print(numberOfCellsToVerify) ```

Benjamin_Loison changed title from ~~Propose a probability of confidence setting instead of `FRACTION_OF_SPACE_TO_VERIFY` is left for future work~~ to Propose a probability of confidence setting instead of `FRACTION_OF_SPACE_TO_VERIFY`

2023-04-13 01:01:52 +02:00

Benjamin_Loison added the left for future work label 2023-04-13 01:02:55 +02:00

Benjamin_Loison removed the left for future work label 2023-05-12 01:09:46 +02:00

Benjamin_Loison commented

2023-05-12 11:42:56 +02:00

To be able to take advantage of dedicating 1% of storage to probabilities, such that 3,449 queries allow the verifier to be 1 - 2 ** -50 sure that the prover stores 99% of claimed storage. Should make the algorithm able to support important storage proofs, as I doubt that the complexity is good enough, being able to restore from new shell stored nonces would be nice too. However pypy doesn't seem to help much.