This was a bug— it asked for the key in those cases but did nothing with it.

No, 100 addresses (by default) are precomputed— this is also what makes your backups stable. If it runs out it will prompt you for the password so it can generate more.

You can run a full node without storing the whole historic block chain. See section 7 of the Bitcoin whitepaper for one approach.

Can hyped up non-existent vaporware cure cancer?  Anyone's guess.  I saw and early whitepaper for that and it was full of technobabble and set of my personal sleaze alarms.

What/which "storage problem" are you talking about?

I can't tell what this is about, so it's offtopic.

It was, you're not crazy.

The reason I mentioned it is because someone recently contacted me about using this kind of technique to make things like having tor hidden service ID's concurrently costly... e.g. you could still connect to as many peers as you want, but you'd still need to use one identity across all of them. It's a different application, but would work with the original proposal just by using a constant value for the peer challenge.

Yes, thats not news though. All of these so far allow for a choice of time/memory tradeoff, it's still maximally fast if you keep everything. The invocation of the sequential function was to try to diminish the available level of choice.

Right. The way to do that is to basically use the idea here.

You don't ask them for (2^(2^t)) (mod n),  you give them H((2^(2^t)) (mod n)) and ask them for t.  I don't see how to construct a rainbow table out of the hashed form because there is no useful function H(R) -> R  that maps to R's along your solution path. You could still extract some parallelism by first computing T sequentially and then saving way-points along the way, though that requires you to store elements of n which are large compared to the hashes... but probably reasonable enough for extracting some parallelism. Hm.

Downside of this is you can't do a publicly verifiable version, e.g. where you have just one piece of storage per identity but one piece per identity,peer pair (which was what I wanted in the motivation for this post; but there are other applications, e.g. like making a hidden service identity costly).

If you really want more than two, you could search for either a seed or set of passwords (if the seed is fixed by prior use, since password searching is strictly slower) resulting in check value sharing.

I'm not sure how valuable the blockchain scan is, since what you'd do there is extract all addresses seen in the blockchain into a bloom filter ... one which fits in L3 cache can have a low enough false positive rate to be effective.

I did a simple empirical test of the false positive rate, mostly to check to see how much rejecting results with too many bits set improved things, and because I'm too lazy to check the math. I found much lower performance than expected:


#include <stdio.h>
#include <stdint.h>
#include <stdlib.h> /*random()*/
#include <assert.h>

uint32_t toflt(uint64_t x)
{
  int i;
  uint32_t result=0;
  for(i=0;i<11;i++)
  {
    result |= 1U<<(x&31);
    x>>=5;
  }
  return result;
}

int chkflt(uint32_t flt, uint64_t x)
{
  int i;
  uint32_t flt2=0;
  int result=1;
  for(i=0;i<11;i++)
  {
    if (!((1U<<(x&31))&flt)){
      result=0;
      break;
    }
    flt2 |= 1U<<(x&31);
    x>>=5;
  }
  if (__builtin_popcount(flt&(~flt2))>11)return 0;
  return result;
}

int main(int argc, char **argv)
{
  int i;
  uint64_t total=0;
  uint64_t fp=0;
  (void)argc;
  (void)argv;
  assert(RAND_MAX == 2147483647);
  for(i=0;i<9973;i++)
  {
    int j;
    uint64_t x;
    uint64_t y;
    uint32_t flt;
    x = ((uint64_t)random()<<24)^random();
    y = ((uint64_t)random()<<24)^random();
    flt = toflt(x)|toflt(y);
    for(j=0;j<1021;j++){
      uint64_t x2;
      int match;
      x2 = ((uint64_t)random()<<24)^random();
      match = chkflt(flt,x2);
      if (x2==x || x2==y){
        if(!match){
          printf("Something bad happened.\n");
          exit(1);
        } else {
          continue;
        }
      }
      total++;
      fp+=match;
    }
  }
  printf("%llu false positives out of %llu tests.\n",(long long unsigned)fp,(long long unsigned)total);
  return 0;
}


Which yields 7508 false positives out of 10182433 tests or 8148 with the too-many test disabled.

I think thats an unacceptably high failure rate.  The one of two 16 bit check values approach gets me 289 with the same sequence. (I could argue that the 16 bit check is too lossy too, considering that someone might get the password wrong, use the result to generate public keys, then later be able to recover the funds— but I think on the balance the denyability feature is pretty good.)

What am I screwing up here? A copy using /dev/urandom instead of random() gets the same results, so it's not just random() having some odd correlations or a low period.

I've unlocked this because there are people complaining to me about unshipped orders.

That isn't true!  The network tries to discourage you from _creating_ such outputs (because they tend to be uneconomical to spend), but you are in no way discouraged from spending them other that just from the cost of doing so.

Constant, not linear.

I'm not sure now if there was a reason I thought I needed the tree-structured PRNG, or if I'd just worked myself into a design corner before coming up with the working idea. If there is, I don't see it now. My original goal had been to find a function that was linear-time and mostly-sequential (e.g. not fast on PRAM) the first time for the client, but fast the second time... and always fast (log or better) for the server. The tree imposes some upper bounds on the non-precomputed search parallelism, but fairly weak ones— the non-precomputed search must do 2x the work and that work has geometrically increasing parallelism.

The reason to reduce parallelism in the non-precomputed search is, of course, based on the notion that any ridiculously fast hardware for bypassing this would likely work by searching most of the space concurrently.

An interesting question is can it be changed in the other direction— rather than simplified (thanks!), slightly complexified to decrease the parallelism in the client further?— I don't think the log() behavior in the server hurts one way or another, though I agree if its not doing anything important simpler is better!

Signing? Verification? Key generation?

This subject is relevant to my interests, but I haven't seen anyone doing anything in it.

Sounds good. Yes, it would be ~1/65536*2.  I was about to suggest something where you need N of M of even smaller checksums and then realized that the bloom filter is basically the limit case of that.   If you don't want to support more than two values, you could specify having more than 11 extra 1s is also regarded as a false match.   E.g. if this key only sets 8 ones and there are 20 set in the filter (including these) then then also regard it as a false positive (because there is no possible single second value which would result in more than 11 bits being set).

The structure I gave has the same property.     If you have StrongH and the encrypted wallet you still need the whole output of the initial KDF, which means you need to know or guess the password and grind the initial KDF.

Practically all of the web keygen / signing apps I've audited use a really sketchy structure where access to the system's cryptographically strong prng is inside a try/catch block and failure results in silently replacing the entropy with snake oil...

Interesting to see that this instance was a different failure mode where the inadequate type-safety of JS combined with a lack of testing for deterministic DSA yielded sadness. (It appears to use a derandomized DSA, but had no tests for it, and the ability to test is one of the big advantages of derandomizing DSA... an underlying library change the behavior of the hash function and the signatures started using a constant nonce).

The data posted here appears to be purely http server data.  I don't see the relationship with bitcoin except they used running-a-bitcoin-client as a way to find interesting targets.

Is there an advantage I'm not seeing to this approach instead of

preH=PBKDF2-HMAC-SHA512(salt,passphrase)
strongH=KDF(preH[first 256 bits])
H = HMAC-SHA512(preH,strongH)

?

This construction seems simpler and faster—or, more importantly, would allow moving the computation budget from postH into preH where it could add more strength against dictionary attack by the delegatee.

Snazzy approach to denyablity. I certantly like it better than what some other people have done.

Do you have any number on the false positive rate for the no-specified second key?  How does it compare to "two 16 bit check values, ordered randomly"? Presumably its better when there is no second key or where you've done some brute force search to find two that share their bloom bits?

We'd proposed something like this in P2Pool a while back— at least the basics of it: announcing key in share and doing threshold cryptography so that larger p2pool miners could automatically peer with similarly sized miners—  there are some obvious shortcomings that come up like even if you assume a large miner will keep the data secret out of self-interest they may not be a large miner forever: once a large miner is no longer a large miner they don't have as much reason to keep the data a secret.

You could constantly re-share new introduction keys to end leaking, but knowing the miners address alone is enough to DOS attack it.  This kind of approach also doesn't address the issue large miners often suspect other large miners of being a perpetrating attacker, e.g. delegating your peering to a hopefully neutral third party can make business sense. I guess you do accommodate that by virtue of the miners being able to choose the addresses they share, allowing them to instead delegate a third party at that point.

I guess these reasons along with a lack of visible attacks on P2Pool, the ease of the manual peering method, and the complexity of implementing something like this is why it hasn't been done so far... but its good to see someone thinking out more of the details.

Very little happens at all if it doesn't work. It's only used for hosts which are behind nat, which don't use UPNP to learn their address, and which don't have a manually configured address. These addresses are only used for announcing to other peers what addresses they can connect to.

Because it should have been lower based on the hashrate, but the system imposes a minimum (which is the definition of difficulty 1).