<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Oct 9, 2014 at 12:16 AM, Trevor Perrin <span dir="ltr"><<a href="mailto:trevp@trevp.net" target="_blank">trevp@trevp.net</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span><br>
</span>By consistency for STHs I just meant check that a newer STH is chained<br>
from an older one (which might require requesting the intervening STHs<br>
from the server).<br></blockquote><div><br></div><div>Yes of course. Sorry, I wasn't clear but I was also assuming you chain the STH/Merkle Roots together for this reason. I just wasn't imagining you do any consistency check otherwise.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
That's not strictly necessary, if you assume that each epoch everyone<br>
relying on a key will be connected to the parties monitoring that key<br>
through gossip.<br>
<br>
But if you check consistency for STHs, then if an attacker signs<br>
different STHs for the same epoch they have to do this for all future<br>
epochs, so gossip has a better chance of eventually detecting this.<br>
<span><br>
<br>
> Users can request proofs on demand that their desired key material is<br>
> correctly included every day at the hash of their username. Your software<br>
> can automate this. Each proof would be 1 signature plus 256*256 bits of<br>
> Merkle proof<br>
<br>
</span>I think it's log(# of users) * 256 bits, since the lower part of the<br>
Merkle path / proof is constant.  So hopefully < 1 KB.</blockquote><div><br></div><div>Yes.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Leaking information about non-queried usernames is a concern.  A<br>
Merkle path would reveal if there are usernames that exist with a hash<br>
that shares a prefix of bits with you.  Maybe you could live with<br>
that<br></blockquote><div><br></div><div>Can definitely live with that. Learning that some random person exists who shares 30 bits of a 256-bit hash with you is essentially useless, right?</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
The sparse tree requires calculating 256 hashes to verify a Merkle<br>
path, but most of them just chain the previous value with a constant.<br>
Not a big deal, but seems like that could be optimized by just storing<br>
each entry at a leaf determined by its minimum unique prefix?</blockquote><div><br></div><div>Yes, you could speed up verification a little by caching all of these. Very minor savings though.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Yeah, not sold on that.  You might want to give the log a chance to<br>
explain itself.  The Sword of Damocles is always there anyways, we can<br>
just stoping trusting the service.<br>
<br>
You also want whoever detects the inconsistency to be incentivized to<br>
publicize it, instead of keeping the (valuable!) private key for<br>
themselves.<br></blockquote><div><br></div><div>That's a good point. Tagged one-time signatures are probably more theoretically interesting than practical the more I think about them.</div><div><br></div><div>As an alternate idea, I wonder if there's a way to use the same techniques so that if anything is ever signed twice, instead of the server's private key you learn the private key to some fidelity bond of Bitcoins. So if you're a startup, you can put a nice bug bounty there, and if you ever double-sign in an epoch whoever finds it gets to seize the bond and maybe you could rig this so that doing this revealed the proof that this happened.</div></div></div></div>