[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Date: Wed, 30 Sep 2015 17:58:25 -0400
From: John Tromp <john.tromp@...il.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Re: Asymmetric proof-of-work based on the Generalized
Birthday problem
dear Dmitry,
> I could not obtain explicit statements of the time and memory requirements
> of your scheme from the paper.
Have you read the latest version of the paper at
https://github.com/tromp/cuckoo/blob/master/doc/cuckoo.pdf?raw=true
or
https://eprint.iacr.org/2014/059.pdf
?
>From the abstract:
"Our cycle finding algorithm uses one bit per edge, and up to one bit per node.
Runtime is linear in graph size"
So for a graph with N nodes, time is O(N) and memory is 1.5N bits.
This can be tweaked to time O(2^k N) for memory (0.5+2^{-k})N bits.
> Some claims in our paper possibly came from
> some misunderstanding.
>
> Andersen's analysis stated that what previously can be done in time T and
> memory M
That refers to my "The basic algorithm" in the same named section,
which uses time O(N) and memory 32N bits (NlogN to be precise for
arbitrary N).
> in some form to claim any positive statements about amortization and
> tradeoff resilience.
Amortization is completely orthogonal and is achieved by having an expected
0.025 42-cycles per random graph (i.e. 2.5% chance of having a 42-cycle).
Tradeoff resilience is considered in the section on TMTOs.
The TMTO algorithm uses time O(kN) and memory N/k bits, and
we study the quite important constant factors involved in that O().
> Currently it is unclear from the paper how much
> Andersen's analysis affected the scheme properties. As a result, I had to
> rely on his analysis first and parallelizability he explains.
Andersen's edge-trimming reduced the memory from NlogN to (0.5+2^{-k})N bits.
> If you could make more rigorous claims about behaviour of your scheme under
> certain memory reductions and increases, this would help me to reference
> your work properly.
Memory increases don't help, since runtime is still Omega(N).
regards,
-John

Powered by blists - more mailing lists