jaesharp Posted June 27, 2017 Share Posted June 27, 2017 (edited) Okay, so I've been giving this problem some thought over the last few days and here's what I've come up with so far. !!! !! This document is a draft posted for comments. !! Please note that the "RCL TLC Implementation Protocols" section is !! especially incomplete. This post will be edited shortly to flesh out that section with !! more details. Eventually this document will move to a github project to manage contributions !! by those interested. !! !! For now, please leave comments on content/theory only -- grammar and speeling mistaks are to be expected !!!! !! Note / Draft/ Conjecture _This proposal is (okay, it might not be, but it probably is) a nonsensical pipedream_ The below described system is the result of my reading and synthesis of a number of research papers and surveys, combined with, what I hope, is a not overly ambitious extension of applicability and/or understanding of how those concepts might be applied. I am absolutely not an expert the field of mathematics -- I am certainly not an expert in the field cryptography. Take everything described here with a grain of salt until someone with more experience says that it *might* be possible. The included is pure armchair crypto design. Perhaps this proposal can serve as a starting point for an eventual production system. -- # Transledger The "solution" (herein, Transledger or, simply, TL) is a 'batteries-included' suite of cryptographic primitives and protocols which when combined implement a globally distributed, incorruptable stored-program computing system. Such a system is, in an information theoretic sense, by construction unable to divulge internal state in a manor against specification and it is robust even to circumstances in which all agents and users of the system are arbitrarily corrupt themselves. An instance of the computing system and its constituent protocols, its users included, as a whole, are known as a TL Complex (herein, TLC). ## Problem Given a population of mutually distrusting users (herein, refered to simply as the TLC Community, TLCC; individually, a TLC User, TLCU) design a TLC suitable for the purpose of : 1) Issuing and engaging in applicable lifecycle management activites of cryptographically verifiable assets which may be transferred and/or transformed via ledgers specified by arbitrarily defined protocols on behalf of TLCC 2) Permits only well-defined point-in-time modification of the TLC Contract (herein, TLCc) subject solely due to expressed will of TLCC, the accounting of which must be explicitly defined in prior iterations of the TLCc. 3) Permits the TLCC no access to any information which is not explicitly revealed in accordance with the TLCc, at any time; subject to certain explicit restrictions Given the above requirements, the following design constraints are implied: A) No TLCU may deviate from the protocol and remain a valid and recognised member of the TLCC Any deviation from protocol by any TLCU must be provably detectable by any other arbitrary TLCU C) Any deviation from protocol must not reveal any information to any TLCU not in accordance TLCc C) All TLCU Input must be encoded such that only the TLCc, when executed as a whole by the TLCC and given every TLCU's Input, may process said input. To any TLCU other than the provider of said TLCU Input, the Input must reveal nothing D) All TLCc Output must be encrypted such that only the TLCU specified in the TLCc may reveal it E) Zero information must be gained by any coalition of malicious TLCU from the receipt of suitably encoded TLCU Inputs and subsequent execution of the TLCc, by the TLCC, over those TLCU Inputs F) Zero information must be gained by any coalition of malicious TLCU from the execution of TLCc over received TLCU Inputs G) Zero information must be gained by any coalition of malicious TLCU from the despatch of suitably encoded TLCU Outputs resulting from the execution of the TLCc, by the TLCC, over those TLCU Inputs H) TLC Liveness must be preserved in the case of malicious TLCU fewer than individual TLC constraints (for example, malicious TLCU minority) I) TLC Safety must always be preserved (even in cases of malicious TLCU majority or unanimity) J) The corruption of any number of TLCU, up to and including the entire TLCC, must not result in the violation of any of the above constraints. To summarise, a computing system (TLC) to which all users (TLCC) have access to potentially all inputs (TLCU Inputs), the program (TLCc), its execution state, computational history, and all outputs (TLCU Outputs) which does not permit the discovery of any information specifically disclosed by the TLCc must be constructed. It must, by and only by its internal logic (TLCc) act as an agent in any cryptographically verified system and update itself as prompted by the application of the TLCc to instances of valid TLCC (TLCU Input) expressions. These requirements form the basis for which is essentially a distributed smart contract execution engine which can act over any number of distributed or centralised ledgers and which can execute arbitrary contracts, subject to certain practicality constraints. ## Proposed Solution The requirements seem impossible to meet -- the idea that, even if all parties are corrupted, no corruption of the system can occur is incredible. In the described system there is no such thing as a 51% attack and the execution of the distributed system itself is sufficient proof of work. Such a system could act as an incorruptable agent or gateway between any N distributed ledgers or as an oracle relying on input from all of its users to produce change in any number of blockchains. The applications are nearly limitless. However, it sounds far too good to be true -- so we must take the default stance that such a system in unimplementable and/or, if it is, the constraints can not be guaranteed with any sound certainty. Let's try to convince ourselves that the null hypothesis of impossibility is wrong. Clearly we'll need some well characterised/proven cryptographic primitives and protocols with which we can implement our concept. Given the formulatic description of our constraints, some well selected keywords quickly hit on a number of subfields of cryptography. One such subfield, for a number of reasons, stands out immediately. The subfield of cryptography known as 'secure multi-party computation' or, simply, MPC. MPC has a rich history and provides us with a number of potential solutions to the problems posed by the requirements above. Of particular interest are the definitions of security within the field which we might use to enrich our own requirements: Our requirements for security in the face of malicious adversaries even when they are majority mean that, in the language of MPC, we desire "Active Security with Abort" by which is meant: > The only thing that an adversary can do in the case of dishonest majority is to cause the honest parties to “abort” having detected cheating. If the honest parties do obtain output, then they are guaranteed that it is correct. Of course, their privacy is always preserved. - https://en.wikipedia.org/wiki/Secure_multi-party_computation#Security_definitions Given that such systems have positive proofs in generality (Yao 1986), universal composibility (Canetti 2000) as well as, more recently, examples of practical application at scale (Kreuter, Shelat, Shen 2012) the field seems a very fertile ground for discovering cryptographic primitives with which we can build TL. Now that we have an established subfield (MPC) from which to draw primitives and protocols, let's assume that we're building a TLC which will interact only with the Ripple Consensus Ledger. Given that, we can assume the following additional characteristics: 1) All TLCU will have an ordered, authenticated broadcast channel by which they may communicate and in which their communications are stored permanently (the RCL) at low bandwidth (1-2 kbps or less), at metered cost, limited total throughput and high latency (>2 s) 2) All TLCU will have a mutually authenticated, possibly indirect, peer to peer channel by which they may communicate at high bandwidth (> 500kbps) and relatively low latency (10s to 100s of ms) 3) The RCL will handle authoritative storage, transmission and exchange of all tokens issued and managed by the TLC and the RCL is trusted for those purposes. However, the RCL need not be strictly trusted, depending on TLCC desire and TLCc construction. 4) The RCL serves as source of Common Reference Strings (CRS) and as such a cryptographic model requiring trusted Common Reference Strings may be used. However, refer (Groth, Ostrovsky 2013) These particular additional characteristics, when assumed by the prospective MPC system implementing the TLC, provide a number of additional possibilities for implementing a secure, scalable solution. For example, because the RCL will handle token exchange and management, there is no need for the TLC to execute with low cycle time. In fact, the execution cycle time can be up to the time required for management tasks and nothing else -- this is possibly on the order of hours or days, all while token transactions remain as quick as the underlying ledger. Additionally, The Common Reference String characteristic provides for the usage of models such as that described in (Canetti, Lindell, Ostrovsky, Sahai 2002) instead of requiring MPC developers and optimisers to work in only the "standard" MPC model. It's clear from the above that exploration of specific MPC implementations for given TLC instances will need to occur on the basis of the specific additional constraints imposed by the underlying ledgers on which the TLC is based. I conjecture that it's possible for a TLC system to be engineered without underlying ledger services, though such a system would be at a clear disadvantage in terms of complexity and efficiency. I am not qualified to select a particular implementation for the underlying system and can only guess at what may be possible -- a large part of why I publish this is to seek input from experts in the field for what may be a very real application of this technique. From my rudamentary understanding of the topic, and in the case of an RCL implementation, it seems very possible that the system as described in (Canetti, Lindell, Ostrovsky, Sahai 2002) may be a direct solution to this issue. ### RCL TLC Implementation Protocols Even though we cannot yet decide on a particular MPC implementation on which to base the TLC, without expert input, we can conjecture as to the nature of the protocol that such an implementation would follow at the layer above. So, assuming the MPC system supports the requirements of the TLC we can proceed based on that abstraction. #### RCL TLCc Lifecycle Phases ##### Initialisation The bootstrapping phase consists of the initialisation of the MPC subsystem, selection of an initial TLCc, secure generation and distribution of any applicable secret key material shares. ##### Execution The execution phase consists of multiple executions of the TLCc according to its specific instructions ##### Transcendence The means by which information which is secret to any and all TLCU is transferred securely to a newly initialised TLCc.... ## References (Yao 1986) - How to generate and exchange secrets - DOI: 10.1109/SFCS.1986.25 (Canetti 2000) - Universally Composable Security: A New Paradigm for Cryptographic Protocols - <https://eprint.iacr.org/2000/067> (Groth, Ostrovsky 2013) - Cryptography in the Multi-string Model - DOI: 10.1007/s00145-013-9152-y (Kreuter, Shelat, Shen 2012) - Billion-Gate Secure Computation with Malicious Adversaries - <https://eprint.iacr.org/2012/179.pdf> (Canetti, Lindell, Ostrovsky, Sahai 2002) - Universally Composable Two-Party and Multi-Party Secure Computation - <https://eprint.iacr.org/2002/140> ## ETC... Per previous discussion on tagging in @JonHolmquist@Hodor@Coroneus because they might be interested. Edited June 27, 2017 by jaesharp +tags Coinseeker, Coroneus, thinlyspread and 1 other 4 Link to comment Share on other sites More sharing options...
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!Register a new account
Already have an account? Sign in here.Sign In Now