SnapDeals Theory Audit

SnapDeals Theory Audit

Team

@Luca

@Irene

@Nicola

@Kubuxu

@Dragan Zurzin

@Aayush Rajasekaran

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

@Luca , @Nicola, @Irene, @Kubuxu

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.