Logo
    SnapDeals Theory Audit

    SnapDeals Theory Audit

    Team

    @

    @

    @Nicola

    @

    @

    @

    What is this Audit About

    We are going through the entire SnapDeals protocol together in order to have a final validation of the theory behind it. Team includes people who directly worked on SnapDeals as well as researchers who did not directly work on it in the past but have extensive expertise in analyzing cryptographic protocols and their security: in this way we aim to minimize potential biases.

    Resources

    SnapDeals main doc

    SnapDeals Security Analysis expanded doc

    What is in Scope for this line of work

    A deep dive into the SnapDeals protocol in order to check all the technical details of it, including Security. In details:

    Double check the encoding function and agree we are fine with it
    Go over all the assumptions and validate them together
    Why Assumption 1 is broken
    Which concrete attack we can put in place
    Why we are convinced the assumptions we are using
    We are fine with considering the flipping adversary as specified in the protocol description
    We will investigate how resampling affects Kolmogorov bounds and the Kolmogorov theorem
    Analyze the security proofs of SnapDeals
    Two bytes for one bit (probabilistic)
    Kolmogorov bound-based (information theoretic)
    Review bucketing analysis and take a final decision on it
    Agree on the calculation about the additional spacegap
    Agree we are overall taking a quite conservative approach, and that we are fine with it
    Agree on number of different hashes used in the protocol (512 or 1024?)
    1024 have to communicate it
    Produce a list of important items to be checked during the next implementation audit
    Challenge generation (using Poseidon inside the circuit)

    Main concerns addressed during the Audit

    • Flipping adversary Assumption: We went over the assumption with the aim of validating if translating 80 bits of security in Fiat Shamir would actually translate into flipping 80 bits of adversarial choice in an uncompressible string
      • We came up with a proof that 80 bits of security in Fiat Shamir translates in the actual choice of the adversary among 2^80 different vectors. This translates in the actual control of 80 bits (via flip) by the adversary
        • We are confident this fact reduces to the Kolmogorov theorem that we are using the actual proof of security of the SnapDeals protocol (writing down a formal technical doc on it)
    • Bucketing Challenges: we validated the analysis we proposed in the actual SnapDeals protocol and we agreed on it. We are confident bucketing challenging is safe
    • Proof of Space Implications: We went over the possibility of exploiting the additional spacegap given by the SnapDeals protocol in order to allow the adversary to use it for space hardness purposes. Given sealing and SnapDeal update are two different and independent protocols, we agreed there is not a risk in terms of putting at risk the sealing process by using the additional spacegap. The estimation for which the worst scenario is having the additional spacegap to sum up with the sealing spacegap is reasonable and conservative. Anything more than this would break even the sealing security proof or the SnapDeals security proof, which we are both convinced about. We'll write formally this reduction in the technical report

    What is not in scope

    Everything which is not regarding the theory behind the SnapDeals is not in scope. Concretely, this audit is NOT about:

    • Checking implementation matches the theoretical description of the protocol
    • Going over Circuit Design
    • Going over SnapDeals efficiency limitations (SnagDeals, ..)

    Outcome of this Audit

    Team will produce a document explaining

    All the steps that were taken
    All the controversial points (if any) and how we decide to move forward
    A final list of TODOs (if needed) in order to consider the audit completed and the protocol ready to ship.

    When do we consider this audit done?

    This audit will be considered finished when the final document mentioned above will be released and everyone below has checked the ack checkbox (meaning everyone is comfortable with the theory part of SnapDeals).

    Ack (comfortable with SnapDeals Theory)

    Nicola
    Luca
    Kuba
    Irene
    Aayush
    Dragan

    Meeting Notes

    First Meeting: November, 12th, 2021

    @, @Nicola, @, @

    List of concerns

    • Bucketing at the Replica Key encoding step could break local properties that should be maintained from the proof of space

    CryptoNet is a Protocol Labs initiative.