{"type":"rich","version":"1.0","author_name":"npub1m230cem2yh3mtdzkg32qhj73uytgkyg5ylxsu083n3tpjnajxx4qqa2np2","author_url":"https://nostr.ae/npub1m230cem2yh3mtdzkg32qhj73uytgkyg5ylxsu083n3tpjnajxx4qqa2np2","provider_name":"njump","provider_url":"https://nostr.ae","html":"📅 Original date posted:2016-06-20\n📝 Original message:In light of Ethereum's recent problems with its imperative, account-based,\nprogramming model, I thought I'd do a quick writeup outlining the building\nblocks of the state-machine approach to so-called \"smart contract\" systems, an\nextension of Bitcoin's own design that I personally have been developing for a\nnumber of years now as my Proofchains/Dex research work.\n\n\n# Deterministic Code / Deterministic Expressions\n\nWe need to be able to run code on different computers and get identical\nresults; without this consensus is impossible and we might as well just use a\ncentral authoritative database. Traditional languages and surrounding\nframeworks make determinism difficult to achieve, as they tend to be filled\nwith undefined and underspecified behavior, ranging from signed integer\noverflow in C/C++ to non-deterministic behavior in databases. While some\nsuccessful systems like Bitcoin are based on such languages, their success is\nattributable to heroic efforts by their developers.\n\nDeterministic expression systems such as Bitcoin's scripting system and the\nauthor's Dex project improve on this by allowing expressions to be precisely\nspecified by hash digest, and executed against an environment with\ndeterministic results. In the case of Bitcoin's script, the expression is a\nForth-like stack-based program; in Dex the expression takes the form of a\nlambda calculus expression.\n\n\n## Proofs\n\nSo far the most common use for deterministic expressions is to specify\nconditions upon which funds can be spent, as seen in Bitcoin (particularly\nP2SH, and the upcoming Segwit). But we can generalize their use to precisely\ndefining consensus protocols in terms of state machines, with each state\ndefined in terms of a deterministic expression that must return true for the\nstate to have been reached. The data that causes a given expression to return\ntrue is then a \"proof\", and that proof can be passed from one party to another\nto prove desired states in the system have been reached.\n\nAn important implication of this model is that we need deterministic, and\nefficient, serialization of proof data.\n\n\n## Pruning\n\nOften the evaluation of an expression against a proof doesn't require all all\ndata in the proof. For example, to prove to a lite client that a given block\ncontains a transaction, we only need the merkle path from the transaction to\nthe block header. Systems like Proofchains and Dex generalize this process -\ncalled \"pruning\" - with built-in support to both keep track of what data is\naccessed by what operations, as well as support in their underlying\nserialization schemes for unneeded data to be elided and replaced by the hash\ndigest of the pruned data.\n\n\n# Transactions\n\nA common type of state machine is the transaction. A transaction history is a\ndirected acyclic graph of transactions, with one or more genesis transactions\nhaving no inputs (ancestors), and one or more outputs, and zero or more\nnon-genesis transactions with one or more inputs, and zero or more outputs. The\nedges of the graph connect inputs to outputs, with every input connected to\nexactly one output. Outputs with an associated input are known as spent\noutputs; outputs with out an associated input are unspent.\n\nOutputs have conditions attached to them (e.g. a pubkey for which a valid\nsignature must be produced), and may also be associated with other values such\nas \"# of coins\". We consider a transaction valid if we have a set of proofs,\none per input, that satisfy the conditions associated with each output.\nSecondly, validity may also require additional constraints to be true, such as\nrequiring the coins spent to be \u003e= the coins created on the outputs. Input\nproofs also must uniquely commit to the transaction itself to be secure - if\nthey don't the proofs can be reused in a replay attack.\n\nA non-genesis transaction is valid if:\n\n1. Any protocol-specific rules such as coins spent \u003e= coins output are\n   followed.\n\n2. For every input a valid proof exists.\n\n3. Every input transaction is itself valid.\n\nA practical implementation of the above for value-transfer systems like Bitcoin\ncould use two merkle-sum trees, one for the inputs, and one for the outputs,\nwith inputs simply committing to the previous transaction's txid and output #\n(outpoint), and outputs committing to a scriptPubKey and output amount.\nWitnesses can be provided separately, and would sign a signature committing to\nthe transaction or optionally, a subset of of inputs and/or outputs (with\nmerkle trees we can easily avoid the exponential signature validation problems\nbitcoin currently has).\n\nAs so long as all genesis transactions are unique, and our hash function is\nsecure, all transaction outputs can be uniquely identified (prior to BIP34 the\nBitcoin protocol actually failed at this!).\n\n\n## Proof Distribution\n\nHow does Alice convince Bob that she has done a transaction that puts the\nsystem into the state that Bob wanted? The obvious answer is she gives Bob data\nproving that the system is now in the desired state; in a transactional system\nthat proof is some or all of the transaction history. Systems like Bitcoin\nprovide a generic flood-fill messaging layer where all participants have the\nopportunity to get a copy of all proofs in the system, however we can also\nimplement more fine grained solutions based on peer-to-peer message passing -\none could imagine Alice proving to Bob that she transferred title to her house\nto him by giving him a series of proofs, not unlike the same way that property\ntitle transfer can be demonstrated by providing the buyer with a series of deed\ndocuments (though note the double-spend problem!).\n\n\n# Uniqueness and Single-Use Seals\n\nIn addition to knowing that a given transaction history is valid, we also want\nto know if it's unique. By that we mean that every spent output in the\ntransaction history is associated with exactly one input, and no other valid\nspends exist; we want to ensure no output has been double-spent.\n\nBitcoin (and pretty much every other cryptocurrency like it) achieves this goal\nby defining a method of achieving consensus over the set of all (valid)\ntransactions, and then defining that consensus as valid if and only if no\noutput is spent more than once.\n\nA more general approach is to introduce the idea of a cryptographic Single-Use\nSeal, analogous to the tamper-evidence single-use seals commonly used for\nprotecting goods during shipment and storage. Each individual seals is\nassociated with a globally unique identifier, and has two states, open and\nclosed. A secure seal can be closed exactly once, producing a proof that the\nseal was closed.\n\nAll practical single-use seals will be associated with some kind of condition,\nsuch as a pubkey, or deterministic expression, that needs to be satisfied for\nthe seal to be closed. Secondly, the contents of the proof will be able to\ncommit to new data, such as the transaction spending the output associated with\nthe seal.\n\nAdditionally some implementations of single-use seals may be able to also\ngenerate a proof that a seal was _not_ closed as of a certain\ntime/block-height/etc.\n\n\n## Implementations\n\n### Transactional Blockchains\n\nA transaction output on a system like Bitcoin can be used as a single-use seal.\nIn this implementation, the outpoint (txid:vout #) is the seal's identifier,\nthe authorization mechanism is the scriptPubKey of the output, and the proof\nis the transaction spending the output. The proof can commit to additional\ndata as needed in a variety of ways, such as an OP_RETURN output, or\nunspendable output.\n\nThis implementation approach is resistant to miner censorship if the seal's\nidentifier isn't made public, and the protocol (optionally) allows for the\nproof transaction to commit to the sealed contents with unspendable outputs;\nunspendable outputs can't be distinguished from transactions that move funds.\n\n\n### Unbounded Oracles\n\nA trusted oracle P can maintain a set of closed seals, and produce signed\nmessages attesting to the fact that a seal was closed. Specifically, the seal\nis identified by the tuple (P, q), with q being the per-seal authorization\nexpression that must be satisfied for the seal to be closed. The first time the\noracle is given a valid signature for the seal, it adds that signature and seal\nID to its closed seal set, and makes available a signed message attesting to\nthe fact that the seal has been closed. The proof is that message (and\npossibly the signature, or a second message signed by it).\n\nThe oracle can publish the set of all closed seals for transparency/auditing\npurposes. A good way to do this is to make a merkelized key:value set, with the\nseal identifiers as keys, and the value being the proofs, and in turn create a\nsigned certificate transparency log of that set over time. Merkle-paths from\nthis log can also serve as the closed seal proof, and for that matter, as\nproof of the fact that a seal has not been closed.\n\n\n### Bounded Oracles\n\nThe above has the problem of unbounded storage requirements as the closed seal\nset grows without bound. We can fix that problem by requiring users of the\noracle to allocate seals in advance, analogous to the UTXO set in Bitcoin.\n\nTo allocate a seal the user provides the oracle P with the authorization\nexpression q. The oracle then generates a nonce n and adds (q,n) to the set of\nunclosed seals, and tells the user that nonce. The seal is then uniquely\nidentified by (P, q, n)\n\nTo close a seal, the user provides the oracle with a valid signature over (P,\nq, n). If the open seal set contains that seal, the seal is removed from the\nset and the oracle provides the user with a signed message attesting to the\nvalid close.\n\nA practical implementation would be to have the oracle publish a transparency\nlog, with each entry in the log committing to the set of all open seals with a\nmerkle set, as well as any seals closed during that entry. Again, merkle paths\nfor this log can serve as proofs to the open or closed state of a seal.\n\nNote how with (U)TXO commitments, Bitcoin itself is a bounded oracle\nimplementation that can produce compact proofs.\n\n\n### Group Seals\n\nMultiple seals can be combined into one, by having the open seal commit to a\nset of sub-seals, and then closing the seal over a second set of closed seal\nproofs. Seals that didn't need to be closed can be closed over a special\nre-delegation message, re-delegating the seal to a new open seal.\n\nSince the closed sub-seal proof can additionally include a proof of\nauthorization, we have a protcol where the entity with authorization to close\nthe master seal has the ability to DoS attack sub-seals owners, but not the\nability to fraudulently close the seals over contents of their choosing. This\nmay be useful in cases where actions on the master seal is expensive - such as\nseals implemented on top of decentralized blockchains - by amortising the cost\nover all sub-seals.\n\n\n## Atomicity\n\nOften protocols will require multiple seals to be closed for a transaction to\nbe valid. If a single entity controls all seals, this is no problem: the\ntransaction simply isn't valid until the last seal is closed.\n\nHowever if multiple parties control the seals, a party could attack another\nparty by failing to go through with the transaction, after another party has\nclosed their seal, leaving the victim with an invalid transaction that they\ncan't reverse.\n\nWe have a few options to resolve this problem:\n\n### Use a single oracle\n\nThe oracle can additionally guarantee that a seal will be closed iff some other\nset of seals are also closed; seals implemented with Bitcoin can provide this\nguarantee. If the parties to a transaction aren't already all on the same\noracle, they can add an additional transaction reassigning their outputs to a\ncommon oracle.\n\nEqually, a temporary consensus between multiple mutually trusting oracles can\nbe created with a consensus protocol they share; this option doesn't need to\nchange the proof verification implementation.\n\n\n### Two-phase Timeouts\n\nIf a proof to the fact that a seal is open can be generated, even under\nadversarial conditions, we can make the seal protocol allow a close to be\nundone after a timeout if evidence can be provided that the other seal(s) were\nnot also closed (in the specified way).\n\nDepending on the implementation - especially in decentralized systems - the\nnext time the seal is closed, the proof it has been closed may in turn provide\nproof that a previous close was in fact invalid.\n\n\n# Proof-of-Publication and Proof-of-Non-Publication\n\nOften we need to be able to prove that a specified audience was able to receive\na specific message. For example, the author's PayPub protocol[^paypub],\nTodd/Taaki's timelock encryption protocol[^timelock], Zero-Knowledge Contingent\nPayments[^zkcp], and Lightning, among others work by requiring a secret key to\nbe published publicly in the Bitcoin blockchain as a condition of collecting a\npayment. At a much smaller scale - in terms of audience - in certain FinTech\napplications for regulated environments a transaction may be considered invalid\nunless it was provably published to a regulatory agency.  Another example is\nCertificate Transparency, where we consider a SSL certificate to be invalid\nunless it has been provably published to a transparency log maintained by a\nthird-party.\n\nSecondly, many proof-of-publication schemes also can prove that a message was\n_not_ published to a specific audience. With this type of proof single-use\nseals can be implemented, by having the proof consist of proof that a specified\nmessage was not published between the time the seal was created, and the time\nit was closed (a proof-of-publication of the message).\n\n## Implementations\n\n### Decentralized Blockchains\n\nHere the audience is all participants in the system. However miner censorship\ncan be a problem, and compact proofs of non-publication aren't yet available\n(requires (U)TXO commitments).\n\nThe authors treechains proposal is a particularly generic and scalable\nimplementation, with the ability to make trade offs between the size of\naudience (security) and publication cost.\n\n### Centralized Public Logs\n\nCertificate Transparency works this way, with trusted (but auditable) logs run\nby well known parties acting as the publication medium, who promise to allow\nanyone to obtain copies of the logs.\n\nThe logs themselves may be indexed in a variety of ways; CT simply indexes logs\nby time, however more efficient schemes are possible by having the operator\ncommit to a key:value mapping of \"topics\", to allow publication (and\nnon-publication) proofs to be created for specified topics or topic prefixes.\n\nAuditing the logs is done by verifying that queries to the state of the log\nreturn the same state at the same time for different requesters.\n\n### Receipt Oracles\n\nFinally publication can be proven by a receipt proof by the oracle, attesting\nto the fact that the oracle has successfully received the message. This is\nparticularly appropriate in cases where the required audience is the oracle\nitself, as in the FinTech regulator case.\n\n\n# Validity Oracles\n\nAs transaction histories grow longer, they may become impractical to move from\none party to another. Validity oracles can solve this problem by attesting to\nthe validity of transactions, allowing history prior to the attested\ntransactions to be discarded.\n\nA particularly generic validity oracle can be created using deterministic\nexpressions systems. The user gives the oracle an expression, and the oracle\nreturns a signed message attesting to the validity of the expression.\nOptionally, the expression may be incomplete, with parts of the expression\nreplaced by previously generated attestations. For example, an expression that\nreturns true if a transaction is valid could in turn depend on the previous\ntransaction also being valid - a recursive call of itself - and that recursive\ncall can be proven with a prior attestation.\n\n## Implementations\n\n### Proof-of-Work Decentralized Consensus\n\nMiners in decentralized consensus systems act as a type of validity oracle, in\nthat the economic incentives in the system are (supposed to be) designed to\nencourage only the mining of valid blocks; a user who trusts the majority of\nhashing power can trust that any transaction with a valid merkle path to a\nblock header in the most-work chain is valid. Existing decentralized consensus\nsystems like Bitcoin and Ethereum conflate the roles of validity oracle and\nsingle-use seal/anti-replay oracle, however in principle that need not be true.\n\n\n### Trusted Oracles\n\nAs the name suggests. Remote-attestation-capable trusted hardware is a\nparticularly powerful implementation - a conspiracy theory is that the reason\nwhy essentially zero secure true remote attestation implementations exist is\nbecause they'd immediately make untraceable digital currency systems easy to\nimplement (Finney's RPOW[^rpow] is a rare counter-example).\n\nNote how a single-use seal oracle that supports a generic deterministic\nexpressions scheme for seal authorization can be easily extended to provide a\nvalidity oracle service as well. The auditing mechanisms for a single-use seal\noracle can also be applied to validity oracles.\n\n\n# Fraud Proofs\n\nProtocols specified with deterministic expressions can easily generate \"fraud\nproofs\", showing that claimed states/proof in the system are actually invalid.\nAdditionally many protocols can be specified with expressions of k*log2(n)\ndepth, allowing these fraud proofs to be compact.\n\nA simple example is proving fraud in merkle-sum tree, where the validity\nexpression would be something like:\n\n    (defun valid? (node)\n        (or (== node.type leaf)\n            (and (== node.sum (+ node.left.sum node.right.sum))\n                 (and (valid? node.left)\n                      (valid? node.right)))))\n\nTo prove the above expression evaluates to true, we'll need the entire contents\nof the tree. However, to prove that it evaluates to false, we only need a\nsubset of the tree as proving an and expression evaluates to false only\nrequires one side, and requires log2(n) data. Secondly, with pruning, the\ndeterministic expressions evaluator can automatically keep track of exactly\nwhat data was needed to prove that result, and prune all other data when\nserializing the proof.\n\n\n## Validity Challenges\n\nHowever how do you guarantee it will be possible to prove fraud in the first\nplace? If pruning is allowed, you may simply not have access to the data\nproving fraud - an especially severe problem in transactional systems where a\nsingle fraudulent transaction can counterfeit arbitrary amounts of value out of\nthin air.\n\nA possible approach is the validity challenge: a subset of proof data, with\npart of the data marked as \"potentially fraudulent\". The challenge can be\nsatisfied by providing the marked data and showing that the proof in question\nis in fact valid; if the challenge is unmet participants in the system can\nchoose to take action, such as refusing to accept additional transactions.\n\nOf course, this raises a whole host of so-far unsolved issues, such as DoS\nattacks and lost data.\n\n\n# Probabilistic Validation\n\nProtocols that can tolerate some fraud can make use of probabilistic\nverification techniques to prove that the percentage of undetected fraud within\nthe system is less than a certain amount, with a specified probability.\n\nA common way to do this is the Fiat-Shamir transform, which repeatedly samples\na data structure deterministically, using the data's own hash digest as a seed\nfor a PRNG. Let's apply this technique to our merkle-sum tree example. We'll\nfirst need a recursive function to check a sample, weighted by value:\n\n    (defun prefix-valid? (node nonce)\n        (or (== node.type leaf)\n            (and (and (== node.sum (+ node.left.sum node.right.sum))\n                      (\u003e 0 node.sum)) ; mod by 0 is invalid, just like division by zero\n                                      ; also could guarantee this with a type system\n                 (and (if (\u003c node.left.sum (mod nonce node.sum))\n                          (prefix-valid? node.right (hash nonce))\n                          (prefix-valid? node.left (hash nonce)))))))\n\nNow we can combine multiple invocations of the above, in this case 256\ninvocations:\n\n    (defun prob-valid? (node)\n        (and (and (and .... (prefix-valid? node (digest (cons (digest node) 0)))\n             (and (and ....\n                            (prefix-valid? node (digest (cons (digest node) 255)))\n\nAs an exercise for a reader: generalize the above with a macro, or a suitable\ntypes/generics system.\n\nIf we assume our attacker can grind up to 128 bits, that leaves us with 128\nrandom samples that they can't control. If the (value weighted) probability of\na given node is fraudulent q, then the chance of the attacker getting away with\nfraud is (1-q)^128 - for q=5% that works out to 0.1%\n\n(Note that the above analysis isn't particularly well done - do a better\nanalysis before implementing this in production!)\n\n\n## Random Beacons and Transaction History Linearization\n\nThe Fiat-Shamir transform requires a significant number of samples to defeat\ngrinding attacks; if we have a random beacon available we can significantly\nreduce the size of our probabilistic proofs. PoW blockchains can themselves act\nas random beacons, as it is provably expensive for miners to manipulate the\nhash digests of blocks they produce - to do so requires discarding otherwise\nvalid blocks.\n\nAn example where this capability is essential is the author's transaction\nhistory linearization technique. In value transfer systems such as Bitcoin, the\nhistory of any given coin grows quasi-exponentially as coins are mixed across\nthe entire economy. We can linearize the growth of history proofs by redefining\ncoin validity to be probabilistic.\n\nSuppose we have a transaction with n inputs. Of those inputs, the total value\nof real inputs is p, and the total claimed value of fake inputs is q. The\ntransaction commits to all inputs in a merkle sum tree, and we define the\ntransaction as valid if a randomly chosen input - weighted by value - can\nitself be proven valid. Finally, we assume that creating a genuine input is a\nirrevocable action which irrevocable commits to the set of all inputs, real and\nfake.\n\nIf all inputs are real, 100% of the time the transaction will be valid; if all\ninputs are fake, 100% of the time the transaction will be invalid. In the case\nwhere some inputs are real and some are fake the probability that the fraud\nwill be detected is:\n\n    q / (q + p)\n\nThe expected value of the fake inputs is then the sum of the potential upside -\nthe fraud goes detected - and the potential downside - the fraud is detected\nand the real inputs are destroyed:\n\n    E = q(1 - q/(q + p)) - p(q/(q + p)\n      = q(p/(q + p)) - p(q/(q + p)\n      = (q - q)(p/(q + p))\n      = 0\n\nThus so long as the random beacon is truly unpredictable, there's no economic\nadvantage to creating fake inputs, and it is sufficient for validity to only\nrequire one input to be proven, giving us O(n) scaling for transaction history\nproofs.\n\n\n### Inflationary O(1) History Proofs\n\nWe can further improve our transaction history proof scalability by taking\nadvantage of inflation. We do this by occasionally allowing a transaction proof\nto be considered valid without validating _any_ of the inputs; every time a\ntransaction is allowed without proving any inputs the size of the transaction\nhistory proof is reset. Of course, this can be a source of inflation, but\nprovided the probability of this happening can be limited we can limit the\nmaximum rate of inflation to the chosen value.\n\nFor example, in Bitcoin as of writing every block inflates the currency supply\nby 25BTC, and contains a maximum of 1MB of transaction data, 0.025BTC/KB. If we\ncheck the prior input proof with probability p, then the expected value of a\ntransaction claiming to spend x BTC is:\n\n    E = x(1-p)\n\nWe can rewrite that in terms of the block reward per-byte R, and the transaction size l:\n\n    lR = x(1-p)\n\nAnd solving for p:\n\n    p = 1 - lR/x\n\nFor example, for a 1KB transaction proof claiming to spending 10BTC we can omit\nchecking the input 0.25% of the time without allowing more monetary inflation\nthan the block reward already does. Secondly, this means that after n\ntransactions, the probability that proof shortening will _not_ happen is p^n,\nwhich reaches 1% after 1840 transactions.\n\nIn a system like Bitcoin where miners are expected to validate, a transaction\nproof could consist of just a single merkle path showing that a single-use seal\nwas closed in some kind of TXO commitment - probably under 10KB of data. That\ngives us a history proof less than 18.4MB in size, 99% of the time, and less\nthan 9.2MB in size 90% of the time.\n\nAn interesting outcome of thing kind of design is that we can institutionalize\ninflation fraud: the entire block reward can be replaced by miners rolling the\ndice, attempting to create valid \"fake\" transactions. However, such a pure\nimplementation would put a floor on the lowest transaction fee possible, so\nbetter to allow both transaction fee and subsidy collection at the same time.\n\n\n# References\n\n[^paypub] https://github.com/unsystem/paypub\n[^timelock] https://github.com/petertodd/timelock\n[^zkcp] https://bitcoincore.org/en/2016/02/26/zero-knowledge-contingent-payments-announcement/\n[^rpow] https://cryptome.org/rpow.htm\n\n-- \nhttps://petertodd.org 'peter'[:-1]@petertodd.org\n-------------- next part --------------\nA non-text attachment was scrubbed...\nName: signature.asc\nType: application/pgp-signature\nSize: 455 bytes\nDesc: Digital signature\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20160620/73f11845/attachment.sig\u003e"}