Smart Signatures - Christopher Allen

Video

• Slideshare — Smart Signatures—Experiments in Authentication (Stanford BPASE 2018 final)

Transcript

Note: This is mostly just a copy paste of the youtube transcript - I haven’t finished cleaning it up, yet.

okay good afternoon my name is Christopher Allen I’m with Blockstream and today I wanted to give you an introduction to something, it isn’t about consensus isn’t about proof of stake, and other things. Want to pop up a level, I want to talk about smart signatures, these are a number of experiments in authorization.

First we need to recap what is a digital signature so it demonstrates the validity of a message it was invented in 1976 you know the year before Star Wars came out okay it was patented in 1980 and the expiration the patent expired it was made practical by Rivest Shamir and Adleman in the RSA algorithm and became part of the standards world in 1988 using the X dot 509 digital signature standard

The fundamental architecture of digital signatures has not significantly changed in over 40 years. The traditional data digital signature it validates the message by canonicalizing it, it hashes it, it encrypts it with a private key and it validates it with a public key. These are then embodied in various certificate data formats the most popular of which is that original one SN dot one which is a data format standard from the 70s I believe originally and the X dot 509 these certificates are then signed and turned by hierarchies of certificates and then finally confirmed by a trust policy and this is where things often break down.

so what are trust policies well right now our trust policies are defined by a certificate authority or actually in more reality by the app a browser or the operating system the trust policy is not defined by the signer who basically signs these things nor the verifier who’s basically trying to determine that things are all correct is the intent of the signer fully expressed I’m not sure does the verifier understand the intent of the signer probably not and does the CA or app understand the trust requirements of the verifier this is the I think it is most important no I do not believe so.

another challenge for traditional digital signatures is that modern crypto is allowing a lot more new forms we have multi signatures being talked about tomorrow in Peter Woolies and Andrew pollsters talk we have ring signatures used by Monero by our own products at block stream blind signatures at different forms aggregated signatures confidential signatures etc the traditional digital signature data formats have had very difficult times adapting to these new forms so we have to like look at the roots what is the duration traditional digital signature doing what is its core use well its core use is for authorization basically a trust policy ensures that the conditions have been met for a particular task you know have we gone through and authorized this party to have access to this website or whatever so the traditional digital signature authenticates that a specific party signed a message and then certifies that the signing party is authorized to do the task.

That’s the real challenge. does the signing party actually is it actually authorized to you do that task and I think we can do better this is where we come up with this concept of smart signatures its core use is also for authorization except instead we’re using scripts a smart signature has additional parties that can be authorized the parties can offer delegation services you know you can basically say that somebody else now has the privilege to be able to do this we want to be able to support and and/or expressions and we want a lot more kinds of conditions so fundamentally the difference between a traditional digital signature and a smart signature is that the trust policy is interpreted is not interpreted by a CA or encode executed by an app browser or us instead the trust policy is embedded embedded by the signer into the signature itself.

this concept was come up at the rebooting web of trust in the fall of 2015 some of the contributors early on include Peter Maxwell McHugh with Greg Maxwell Joseph bono Joseph poon tighter clothes etc so our inspiration was the Bitcoin transaction signature because it works it uses a stateless predicate language sometimes known as script the the script is created by the signer and it’s based on the signers Trust policy thus can support ands and ORS and multi SIG’s various complex things like time locks and puzzles and even other scripts there are many many use cases so what are some of the use cases well clearly the most important one right now is multi factor expressions we want n of n signatures M of n signatures we want the logical ands and ORS but there may be other elements we want to be able to include biometrics and signatures proof of Hardware control etc we want to support that signature delegation we want to be able to delegate to another party and we want to limit that delegation we want maybe to say that somebody can use it for a month for only purchases and purchases that aren’t more than 5 K

we also potentially want to have the ability to permanently pass control to someone else in case usage of a keys ceases which could be because of an employment change or because of some significant scenario like a disaster or death we want to be able to combine these in multiple and interesting ways for instance in a development release or a continuous integration tool chain it might have at the top level of multi-factor three of five signature but then one of those three at one of those five signatures has authorized their assistant to be able to do the signing for the development release because he’s on leave and then another signer has a very strong security policy that requires two of two of keys to be applied to the signature where one those keys is stored on a hardware token finally we want to be able to support transactions because that’s one of the primary uses for authenticate authentication.

Signature Authorization

so signature authorization signatures are often part of a larger process they can prove that specific transactional States exist before they proceed we want to be able to test against various Oracle’s for instance we want to be able to say no more than five K has already been spent this month which basically means it needs to know that how much has already been spent by other authorizations in the history of the smart signature there may be other uses such as provenance may be a piece of art requires a transactional history in order for you to be able to purchase it in looking at a lot of these different usage scenarios we’ve come up with some requirements for smart signatures I will divide them into two big categories there are requirements around the language and then there the rate requirements around the system

the first requirement is composability so a smart signature language should be something that allows you to take simple behavior small things well described well understood and then basically build them into more complex ones we really need to have simple data structures stacks lists etc and the reason why we have both of those requirements is that the constrained set of operations allows us to do sufficient security review to understand what is actually going on, that errors are not being encountered our inspirations around composable languages our fourth scheme haskell etc

the second requirement is inspect ability so this is really about the the program or the developer we want it to be the the script to be understood by a qualified programmer we want those elements of the signature script to be brought out and exemplified so the developer can actually know this is what it is going to do and how it’s going to function and because in the end the programmer has to evaluate is this going to do the business function that I want to have authorized a third language requirement is we want it to be provable so a smart signature language should be formally analyzable to prove correctness and it should support a variety of expert tools to discover hidden bugs so those are our three language requirements we have three sort of system requirements the system as a whole needs to be deterministic the scripts should always produce the same result even on a different Oz or hardware and I might even add if in the future there is a new version of the script language it should still function the second system requirement is that it should be bounded execution should not exceed the appropriate CPU or memory limitations the script size should be minimal in order to lemon limit bandwidth and storage costs and then to go back to kind of the previous requirement in order to do this bounding those bounds need to be deterministic so we have you know we these all interact with each other

finally there’s a requirement of efficiency now we are not putting in requirements on the difficulty for creating signatures in fact you know if it takes several seconds or even longer to create a signature that’s acceptable where we’re really concerned about efficiency is that the cost of verifying should be extremely low so these are all of the primary requirements that we wanted to have in any smart signature system I do want to add in something we were considering as a seventh requirement which is privacy so there’s always a trade-off between flexibility of a sophisticated smart signature and the privacy that it offers because every time you do a signature its revealing information about the signers

Bitcoin

that’s certainly a lesson that we’ve learned from Bitcoin smart signature functionality may allow for correlation and some scenarios that can be bad in particular in transactional scenarios it reduces substitutability and it can break fungibility and various bearer aspects of authorizations so I don’t consider privacy to be a requirement but it is something you should carefully consider some advice limit sharing of the smart cart signatures themselves execute them off chain as much as possible if you and I have a contract then we don’t need everybody else to see it unless there’s a problem be transparent and be very deliberate in your privacy designs think about privacy as one of your considerations

so there have been a number of experiments in this area obviously the most successful experiment is Bitcoin it’s you know securing billions of dollars worth of transactions Bitcoin script itself is a fourth like language in that it is stacked based it is well tested well trusted but obviously has some limited capabilities this is a good thing from a security review perspective it’s gonna if it’s going to secure these billions of dollars we have to be very careful about what we put in it there are some things coming out masked and snore and other improvements that will continue to help Bitcoin

it’s a great sort of starting place because we’ve just we’ve demonstrated the deterministic aspects we’ve demonstrated that that’s possible we’ve demonstrated that it’s bounded we’ve demonstrated that it’s efficient well we have not demonstrated as a Bitcoin script is very composable being able to combine scripts in various ways is hard it’s definitely not very inspectable most people can’t just like look at a bitcoins script and basically say what they know what’s going on and it is not at this point provable we cannot have a formal proof of Bitcoin script there have been some experiments to extend Bitcoin script the most notable is IV from chain com it basically compiles to Bitcoin script but it has a much easier syntax it adds name variables it adds static types this makes it kind of an inspector boleyn of Bitcoin script but other than that it has the same limitations that as Bitcoin script does mainly that it’s not provable

Deterministic Predicate Expressions Language -Peter Todd

First Attempt to Create a Language for Smart Signature Requirements

the first sort of attempt to take smart signature requirements and come up with a language for it was the deterministic predicate expressions language by Peter Todd in it he discusses a scheme like lambda calculus that’s really optimized for hash trees which among other things allows for partial proofs which I think is kind of cool I can basically give you a long dex predicate that you may only be able to solve a small part of it you can basically collapse that to a hash give it to the next party who is able to take a different part of it and collapse it to a hash bring it back to me and I can basically prove that the particular authorization is allowed without necessarily knowing all the other aspects it’s specifically designed to support state machines and systems that need state machines

it is composable it’s deterministic efficient and bounded I’m not quite sure about its inspect ability or prove ability it is strongly typed and with some additional work is probably provable one of the most interesting experiments in smart signatures is Russell O’Connor’s simplicity which is from my company block stream it is a sequent calculus which is something a lot of people may not be familiar with which offers finite airy functions with bounded complexity basically we it allows you to create scripts that are very very solidly understood it already has a formable provable semantics and then scripts that are written in simplicity can be provable via the the tool called caulk

thus it is of all the different experiments right now is the most provable deterministic bounded efficient composable where it is challenging is that it’s not very inspectable at this point maybe as it evolves will create higher level things that allow us to do it but I just can’t look at a simplicity script and have a you know intuitive feeling oh here’s the expression of the intent of the author of this script and what it’s going to do you’re going to hear a lot more about this in a session tomorrow at 10:50 a.m. where Russell is going to be talking more about simplicity another experiment is Sigma state by Alexander chirp Noi it uses Sigma protocols which is a class of digital signatures and crypto systems that are optimized for ZK proofs

some interesting things about it is that it supports natively ring and threshold signatures so it’s sort of different than a lot of the other languages in order to support hopefully ultimately prove ability it does have strong types and some other features it looks like it’s reasonably inspectable composable should be able to be deterministic and efficient at this point he doesn’t have a formal proof of the language itself so the path to prove ability is still to be determined and I personally have some questions about the boundedness of it it’s supposed to be non Turing complete but there may be some accidental Turing isms in there

Mickelson -Tezos

Mickelson is the next experiment that I’m finding interesting it’s by tezo’s it is sort of in the Bitcoin family of of being stacked based but it is using sort of Oh camel as its language mechanism it is very strongly tight its composable inspectable and efficient at this point there is not a strong proofs for it but I believe that it is provable and is likely bounded and deterministic in the same way that bitcoin is but there are no formal proofs of that at this point

this is radically different this is not a script but this is another approach to a sort of addressing the constraints problem so crypto conditions is not a late a language it is a JSON description of a number of keys which basically allows you to do a very deterministic boolean algebra the advantage of this particular technique it is very easily to test is this code properly Express the intent of the of the user because it you know it’s all deterministic boolean we can test the hell out of it and get you know a real thing but it has no flexibility at all it either fits into the JSON format or it doesn’t so it is bounded it is efficient it is deterministic

I find Jason a little bit hard to read but that’s okay so it’s in the questionable category it is explicitly not composable there are no composable elements of it and i don’t really know how to prove it either I can test it but I can’t necessarily prove it so what are the status of these various experiments obviously Bitcoin script is fully integrated in Bitcoin but at this point there is no standalone version you just can’t take the Bitcoin script interpreter and use it there is a open source project from Cali wolf which is called BTC dev which is a Bitcoin debugger

I noticed that the latest version of it adds masked the the in one of the branches so basically people can begin to experiment with extending Bitcoin script ivy has a full white paper and they have a full script playground available where you can basically try out various IV functions and there’s even now a IV to BTC Debb branch going on right now so you can actually debug IV Dex Peter Todd well he’s written a blog post about and done a couple of presentations but at this point there is no white paper and as far as I know there is no implementation

so it’s interesting as one of the first attempts in this area but there’s not a lot you can do with it at the moment simplicity which is again gonna be talked about by Russell tomorrow the white paper is available I’ve seen some people try to do some things based on the white paper but there isn’t any public code yet it’s coming but it’s not available Sigma state the white paper is supposed to be out next month I don’t have all the details there is no public code out but he’s been working on some you know hopefully we’ll know more about the state of next month

Mickelson has a whitepaper has a script playground you can definitely do some things with Mickelson now and finally crypto conditions it’s part of the inner lecturer reference release and they’re in the process of standardizing crypto conditions I’m watching some other efforts so these aren’t necessarily experiments smarm by Christopher Lamar Weber has basically been designing a scheme like language that is maybe gonna be on top of simplicity when simplicity comes out so it basically allows some of the scheme composability and those elements you know at the top but basically compiles to simplicity it can also compile to native code

so it’s kind of an interesting effort at this point it we only have a requirements documents for that but presuming that the requirements are met it would be composable and spectable deterministic can the proof proofs move up from simplicity to it at this point there’s not a formal description for that so i don’t know yet but it’s at least an interesting project worth watching frozen realms

this is part of the ECMCA this is the JavaScript community it’s by Miller Morningstar and PT know it’s a safe subset of JavaScript with limited prime Oriels it compiles may compile to Assam I just think it’s there’s some interesting things we might be able to learn from this language it certainly has is composable and in spectable in the same way javascript is will it ever be able to be provable I’m not sure and finally you know it is a turing-complete language so boundedness is always going to be a challenge for turing-complete languages

you can do it with gas and other different different mechanisms but you can’t prove it in the ethereum community there is a high-level language called bamboo it’s JavaScript like like solidity and such but it very much tries to call out the explicit state transactions state transitions which is one of the classic bugs that happens when you’re doing a variant Hren C and I’m sorry interested in it from a inspect ability point of view like can they are they allowing the programmer to more explicitly understand the various reenter SC issues that you have with any kind of asynchronous script

that’s why I’m watching a bamboo not on there I have not studied the ke VM which is also trying to prove ability of the EVM layer of ethereum the community that is beginning to work on these we have a number of open questions one area is the area of context in Bitcoin the context is the trend the previous transaction so you basically start with the previous transaction you have a script and then it executes but in these smart signatures we want to be able to refer to things

like we want to look at the transaction and go hey it’s you know it’s $5,000 but the script says you can’t do $5,000 but those messages might be lists they might be trees or they may even be very complex basically graphs so how does the script refer to the contents of the message that it is signing there’s also runtime context what is the time what is it being executed by what information needs to be passed and is available to the script while it’s executing from the runtime if you think about it from bitcoins perspective we know the block height and so there is a variety different things that can be passed the script that allows it to do its functionality when we start talking about stuff that’s outside the message the external process State things like the Bitcoin script does not have access to the whole blockchain it can’t know that that particular set of keys was used in another transaction elsewhere it can only know that it wasn’t used with the prior transaction so how do we handle external process States which sort of leads to this larger problem of Oracle anytime you have this sort of asynchronous state we end up into much more complex territory.

how do we preserve the execution boundaries when we’re in these sort of asynchronous states and then within them in the same way that we’ve kind of constrained script to be predicate expressions what are the simplest minimum viable product Oracle’s that are out there I mean obviously we need a time Oracle we may want some Bitcoin price Oracle’s etc how those work how do we want to assure them etc

there was a big long discussion by the smart signature team around revocation like revocation turns out to be a real hard problem I think originally you know Peter Wooley and Peter Todd we’re both talking about that it should be able to be in the primary script that you can basically have the revocation as a and type of operator inside the the script in and I think we’re all in rough consensus that likely revocation cannot be done directly within a signature script do we how are we going to do revocation do we want some kind of proof of non revocation as another script or we’re not really clear here clearly one of the answers is to basically make the scripts very short-lived so you know maybe a day a month or whatever and that way you don’t necessarily need to do revocation

Object Capabilities

there is another sort of system security architecture than what we is popular today called object capabilities I don’t know how many people here are familiar with the concept of object capabilities so it’s a very minority architecture it’s however been in development for over 10 years has some very interesting properties it turns out that Oh cap and various least authority architectures may really benefit from smart signatures so you know if we’re gonna add that as another use case we need to understand their requirements more and it may enable some of the types of things that they would be able to do that can really significantly increase the security of our systems another open question is the cryptographic primitives what do we want to include in our smart signature systems if we look at Bitcoin a lot of the underlying operators were deprecated because they caused various kinds of you know challenges could make basically you know allows an attacker to do a denial service by you know using up a lot of memory etc so do we want to offer some cryptographic primitives

I know I’m personally interested and the script being able directly derive HD keys I think that would be a very useful primitive Andrew Polster ax has been talking at various conferences about script list scripts where we’re basically embedding into a single signature multiple signatures in a form that kind of resembles simple script operations can we leverage that that gives us some privacy may give us some other capabilities and then there’s sort of this line between the smart signature and the smart contract

I mean a smart signature is a predicate script it basically is returning true or false but is there some value in some non predicate scripts where basically we are providing true and false and maybe a hash or something of that nature so there’s some interesting open questions there and then of course all of these experiments are not turing-complete they’re not they’re very much exploring sort of the efficient and bounded side of things by not attempting to be fully Turing complete but where is the line between a smart signature contract and a true smart contract is it purely is Turing the only difference between the two there are a lot of things that we can do without becoming fully turing-complete…

unknown at this point references the the most recent paper is bitly smart signature smarter signatures and that will basically get you the paper that was published last spring you can obviously look at the tag smart signatures in Twitter and you’ll see other discussions about it but we are evolving it it was

Rebooting Web of Trust

the concept came up at the first rebooting web of trust we’re gonna have our six rebooting web of trust in Santa Barbara in just a few weeks March 6 through 8 if you’re a language geek and this is something that really gets you excited and you basically go that experiment is okay I want you to come to this event and tell us what’s wrong and help us fix it

okay I would like to really begin to explore some of these use cases these requirements and actually begin to have some more solid demos of what the future of smart signatures is so again it’s rebooting web of trust and it’s in March six and seven six to eight my name is Christopher Allen and you can reach me at Christopher a at block stream comm

[Applause] [Music] [Applause]

very interesting topic about smart signature my question is is it possible because it’s still early in the stage in terms of experiments so you don’t want to have a standard right yeah like x5 909 certificate is it possible to have a kind of extension to expire nice certificate to including this math signature language constructs you clear the data structure and I think that there has been some exploration of how we can extend existing digital signatures with some of these scripts I mean to a certain extent you can just put in the signature field the script exam and all of the predicate expression in there I’m more interested in what’s happening in the w3c there is something called the verifiable credentials community verifiable claims community and they’re using a special form of JSON that is a graph Jason it’s called json-ld and it can be signed as a graph signature which is I think very intriguing

Decentralized Identity

so I’m more expecting that the innovation in this space will evolve in the json-ld signatures area rather than the X dot 509 thank you so another question is they use it like this sinus policy is kind of like a self solving identity it’s seeing another space about like as a sign or the code of the key can decide the policies is this a nice idea they’re usually kind of for bio-port or consensus the IBM they have a kind of for what is called a decentralized the identity folks group right you guys talking well I’m the I coined the term self sovereign identity and rebooting web of trust is where the decentralized identifiers spec was first bootstrapped

so basically the decentralized identifiers spec is allows multiple block chains to create centralized identifiers x’ that can be used for a variety of purposes including self sovereign identity on ethereum there’s uPort there’s a Bitcoin version of it there’s a big chain DB there’s a a public but permissioned blockchain called sovereign that is also using D IDs and we’re basically meeting every Tuesday morning to try to move that forward in the w3c thank you

I’m a little unclear you were saying it’s a smart signature as a predicate language but she showed simplicity and I thought simplicity was more than that yes simplicity is more than that but to be clear it also it’s not Turing complete basically it unwinds all the loops and all the different aspects of it so that you can basically have a complete expression and I think for what most people want to use it for right now is for you know things like provable predicate scripts but clearly can be used for more than just a predicate again it has the same sort of the same open questions you know when we start hitting you know various levels we start talking about asynchronously having scripts talk to each other we run into all the problems that we already know about from the ethereum world every entrance ii and things of that nature

so there’s still a lot of work to do and I think you mentioned if I missed it what so the relationship with your work in the sovereign foundation I’m not part of the sovereign foundation the they are part of the rebooting web of trust community so they’re one of the many different people many of which are in this room today that cooperated at rebooting web a trust to incubate the di D standard and then basically last June the w3c basically gave permission to move it forward as a work item so it’s it is not an on the on a standards track right now it’s in you know the first stage we we had a big meeting last week to try to reconcile the last draft and hopefully this year we’ll be moving it to standards track where it will actually become a potential international standard thank you okay that’s all the questions I think well thank you very much again reshaping media [Music]