Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Attacking Depth Robust Graphs #96

Closed
nicola opened this issue Mar 11, 2019 · 4 comments
Closed

Attacking Depth Robust Graphs #96

nicola opened this issue Mar 11, 2019 · 4 comments

Comments

@nicola
Copy link
Contributor

@nicola nicola commented Mar 11, 2019

The security of Proof-of-Replication (as well as other Proof-of-Space schemes) relies on the best known attacks to Depth Robust Graphs.

An (e,d)-depth-robust directed acyclic graph (DAG) has the property that after removing any subset of up to e nodes (and adjacent edges) there remains a directed path of length d.

The algorithm we are using for generating Depth Robust Graph is based off the DRSample algorithm described by Alwen et. al and BucketSample by Fisch et al. and have been implemented in drgraph.rs. Both papers describe the best known attacks to these graphs.

The output of this work is to implement the current best known attacks in Rust and run them against the DRSample, BucketSample and ZigZag graphs.

@nicola nicola mentioned this issue Mar 21, 2019
@nicola nicola changed the title Improving on the best known attacks for Depth Robust Graphs Implement the current best known attacks for Depth Robust Graphs May 24, 2019
@nicola nicola changed the title Implement the current best known attacks for Depth Robust Graphs Implement the best known attacks for Depth Robust Graphs May 24, 2019
@nicola nicola changed the title Implement the best known attacks for Depth Robust Graphs Attacking for Depth Robust Graphs May 24, 2019
@nicola nicola changed the title Attacking for Depth Robust Graphs Attacking Depth Robust Graphs May 24, 2019
@jon-chuang
Copy link

@jon-chuang jon-chuang commented May 1, 2020

Hi Nicola, have any of these attacks been implemented yet?

Loading

@schomatis
Copy link

@schomatis schomatis commented May 1, 2020

Loading

@jon-chuang
Copy link

@jon-chuang jon-chuang commented May 2, 2020

@schomatis , yes I stumbled upon it ytd, going to take it for a spin this weekend :) it seems to have halted development? Is there are outstanding work?

Loading

@nicola
Copy link
Contributor Author

@nicola nicola commented May 5, 2020

there seems to be no outstanding work - closing this old issue

Loading

@nicola nicola closed this May 5, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
3 participants