[Cryptography] [Crypto-practicum] Please critique this mining-free blockchain design

[Ron Garret]

On Jul 18, 2017, at 6:20 PM, Bryan Bishop <kanzure at gmail.com> wrote:

> On Tue, Jul 18, 2017 at 8:11 PM, Ron Garret <ron at flownet.com> wrote:
> My main concern here is whether this design is sufficient to prevent the TTP from cheating.
> 
> Your trusted third-party can forge multiple conflicting alternate histories and then choose to only share those histories with different users. If a double spend is later found, or inflation or something else, then you end up with potentially many years of subsequent activity built on top of the fraud, and users often have no recourse at that point.

Yes, I thought of that.  That’s why the hash at the tip of the tree is periodically committed to a publication of record.

> In bitcoinland there is a similar theoretical problem where miners might choose to withhold information used to construct overly large blocks: even if you have a system where you can create fraud proofs, you cannot guarantee that the miners will publish all the data included in a block-- why would anyone ever show you the full set of information required to prove the inclusion of double spends (or other rule violations)?

The strictly serialized design prevents records from being omitted or inserted.  Every entry commits to the signing key that will be used for the next entry, so you can always trace back a unique history that led to any entry.

The TTP could fork the chain by signing two entries with the same key, but that would be discovered no later than at the periodic commitment to the publication of record.

> Btw for your purposes I also recommend looking into these opentransactions wiki pages:
> http://opentransactions.org/wiki/index.php?title=Auditing
> http://opentransactions.org/wiki/index.php/Triple-Signed_Receipts

Thanks for these pointers!

BTW, I noticed that you cc’d cryptography at metzdowd.com, which was (intentionally) not included in the original distribution.  For the benefit of readers on that list, here is the original post:

-----------

Bitcoin achieves consistency through a combination of proof-of-work (mining) and a longest-chain Merkle tree.  This eliminates the need for a trusted third party to achieve a shared consensus. But it comes at a high cost: mining is inherently expensive (it is the cost of mining that is the principal defense against attacks), and hence transaction confirmations are slow (tens of minutes).

If one’s risk posture or ideology does not lead them to reject trusted third parties (TTPs) then more efficient solutions are possible.  If you really trust the TTP then you just take them at their word that the ledger they publish is authentic.  This is an efficient solution, but this gives the TTP too much power: the TTP can easily cheat without being caught, and so the incentive to cheat is high. But if the ledger is structured so that it is self-authenticating like the BitCoin blockchain, then any attempt by the TTP to cheat will be immediately detected.  This removes the incentive to cheat, and so you get the best of both worlds: reliable distributed consensus that is both fast and efficient.

Here’s the design: Ledger entries are arranged in a linear linked list.  Every entry is signed by the TTP and contains the hash of the previous entry.

The twist is the following:

1.  Every entry is signed with a different key

2.  In addition to the hash of the previous entry, each entry also contains the public key that will be used to sign the *next* entry.

Hashes are published electronically in real time and periodically committed to publications of record.

The reason for committing to the next key in the current entry is that it allows the chain to maintain continuity while still allowing the key generator to be re-seeded between any two transactions. The TTP *could* use a fresh key for every transaction, but in practice they would probably use keys generated by a CSPRNG which is periodically re-seeded.  The reason for this is that losing the next key before it is actually used to sign the next transaction is  catastrophic: the chain is irretrievably broken, and some other process must be invoked to start a new chain, link it to the old one, and establish trust in the authenticity of the new chain.  Because of this, any key material must be securely written to non-volatile storage (with multiple backups) before it is used.  Then it must be securely erased after it is no longer needed.  It might be possible to arrange for this to happen fast enough that a truly fresh key can be used for every transaction, but it is not necessary.  Re-seeding the key generator every few minutes should be plenty.  I can’t think of any attacks that this would enable that could not be carried out with equal ease against a key generator that is re-seeded more quickly.

The main advantage of this design over mining-based blockchains is that transactions can be processed almost instantaneously.  The limit on latency is the time it takes to generate a signature. Throughput can be increased virtually without limit by pipelining the process of signing entries.  To make this work, the previous-entry hash cannot includes the signature.  It can only be a hash over the content of the entry.  At this point, the limiting factor on throughput becomes hashing, which cannot be pipelined since each entry must contain the hash of the previous entry.  However, if a product based on this design ever encounters that as a limiting factor that would be a very nice problem to have.

Committing to the signing key for the next ledger entry in the current entry prevents the TTP from publishing two different versions of the ledger.  Any attempt by the TTP to cheat in this way would immediately be caught and proven by exhibiting two ledger entries signed by the same key.  Any entry signed by a key other than the next key would be immediately detected as a forgery.

The TTP can still unilaterally deny service by delaying the recording of an entry, and they could use this as leverage to extract rents.  This could be addressed by entering into a contractual obligation with users not to engage in such practices, and by establishing a competitive marketplace for TTP services.

Thoughts?

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20170718/bf9b6569/attachment.html>