[Cryptography] blockchain and trustworthy computing

[Natanael]

Den 5 okt 2015 23:58 skrev "ianG" <iang at iang.org>:
> This seems to solve the problem for me, but trustworthy computing was
always about being able to run my code on someone else's facility.  For
example, I-as-movie-mogul run my movie on your TV, after payment received.

That needs tamper proof trusted hardware. Software can't do it alone. And
the analog hole remains.

> Right.  But we solved that problem with the odometer already - you're not
allowed to rewind your odometer any more.

Like I noted later in that email and which you commented on further below -
it isn't always a question of reversing the output you've committed to
previously, but about finding alternative ways to make the output you
commit to appear acceptable.

However, regarding HOW to prevent it from rewinding, within internally
trusting groups you can do this;

Coming across Forward Secure Pseudo Random Generators a second time (used
in systemd to implement Forward Secure Sealing for logs) and then
remembering the recent post about Forward Secure Asynchronous Messaging
from Puncturable Encryption, I thought that parts of the latter (those
derived from Forward Secure PKE) can be used in a multiuser model much in
the same way the former is intended to be used for single user models.

https://eprint.iacr.org/2013/397 + https://eprint.iacr.org/2014/479
https://github.com/imichaelmiers/libforwardsec/

So we modify this. We take the blockchain and move from PoW to threshold
signatures where the signers are selected by a gatekeeper.

This variant of the threshold signing implementation is the novel part
(AFAICT); Each party still has a public key as usual. But now the private
keys has a number of components, each assigned to one time-slot.

So we then have two layers of thresholds, one per signer and one for the
group. And the per-signer layer is derived from Forward Secure PKE, used as
a signing algorithm instead of as an encryption algorithm (I believe it is
achievable, even if may not be straightforward).

So now with an m-of-m threshold, we only need one signer to delete any old
key component for it to be impossible to sign any new data corresponding to
that time-slot, and with the hash chain still in place there's a heavily
reduced incentive to selectively keep old components to later substitute
individual entries, as everything must be updated at once at serious risk
of detection.

And thanks to the hash chain, collectively signing messages dated into the
future requires either halting operations until that point to not break the
hash chain and thus not creating conflicting forks (and this is immediately
detectable) or speeding up the clocks (and again losing ability to act
instantaneously up until that point in time), although with full collusion
they can create forks at will within the current time-slots.

So if you trust that at least one signer instantly deletes his most
recently used key component for each block / time-slot, even if it is a
different signer doing it for each block, you know that the chain can't be
rolled back in full since a *complete* alternate chain can not be
successfully signed in its entirety. What's been committed stands.

So in your car example, having one small device with no storage beyond
what's enough for this type of private key per relevant agency would let
them all trust that no rewinding is taking place. They don't need to store
the latest signed hash chain headers and verify the headers, they just need
to sign the latest block that's one time-slot past the previous one they
signed and then update their key material. The device won't even be able to
sign two blocks for the same time-slot! This can easily be done using cheap
smartcards (yay cost savings). When looking at the chain later (when the
car is in service?) they can all see it is *one single complete chain*,
with little to no reason to believe that every device key has been
successfully extracted early on in order to rewind the chain past where
illicit modifications were done.

Now making sure the blocks contain all the data they should and that it is
accurate is still a trustable sensor issue. While incomplete, you could
potentially have the smartcards used for this scheme look for current
signatures in each block from every sensor they're programmed to care about
before they sign the block.

(Does anybody know of any Proof-of-stake altcoin doing anything like this?
If not, they should. Currently the naive constructions would make rewind
attacks child's play to TLA:s, also see the Nothing At Stake argument,
FS-PKE modified for group threshold signatures would be a huge improvement.)

Is anything doesn't make sense, just ask. I just fleshed this idea out over
the past hours.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20151018/bed4d28b/attachment.html>