[Simplicity] Questions about Simplicity

[ZmnSCPxj]

Good morning Russell,

> * I have an open problem that unfortunately isn't written up in detail yet, but essentially asks if Simplicity's type inference can use polymorphic type inference instead of monomorphic type inference without opening of Denial of Service attacks?  Polymorphic type inference takes exponential time in the worse case (as opposed to monomorphic type inference which can be done in linear (or more realistically quasi-linear) time); however, polymorphic type inference also allows for exponentially smaller terms on some cases too.  So if polymorphic type inference only takes exponentially more time in those cases where we use exponentially smaller terms, then there is no real cost to using it and many benefits that go beyond the exponentially smaller amounts of bandwidth used in some cases.

My PL is old and out-of-date, but if my stale local cache is correct, even if polymorphic type inference is potentially exponential, if type annotations are provided, polymorphic type verification is linear on expression size.
If so, potentially inference can have some engineered limit imposed by consensus, and optional type annotations added to the encoding.
A Simplicity script would then have to add some annotations if it would violate that limit.
Or simply annotate all polymorphic sub-expressions.

Regards,
ZmnSCPxj