Christian Decker [ARCHIVE] on Nostr: 📅 Original date posted:2021-02-27 📝 Original message: > The `!(a && b && ...)` ...
📅 Original date posted:2021-02-27
📝 Original message:
> The `!(a && b && ...)` can be converted to a reversal of the payment.
> The individual `!BUYER` is just the buyer choosing not to claim the
> seller->buyer direction, and the individual `!ESCROW` is just the
> escrow choosing not to reveal its temporary scalar for this payment.
> And any products (i.e. `&&`) are trivially implemented in PTLCs as
> trivial scalar and point addition.
>
> So it may actually be possible to express *any* Boolean logic, by the
> use of reversal payments and "option not to release scalar", both of
> which implement the NOT gate needed for the above. Boolean logic is a
> fairly powerful, non-Turing-complete, and consistent programming
> language, and if we can actually implement any kind of Boolean logic
> with a set of payments in various directions and Barrier Escrows we
> can enable some fairly complex use-cases..
This got me thinking about my first year logic course and functional
completeness [1], and it it trivial to prove that any boolean logic can
be expressed by this construction. We can trivially build a functionally
complete set by just constructing a NAND, a NOR, or {AND, NOT}, all of
which you've already done in your prior mails.
The resulting expressions may not be particularly nice, and result in a
multitude of payments going back and forth between the participants to
represent that logic, but it is possible. So the problem should now
simply be reduced to finding a minimal representation for a given
expression, which then minimizes the funds committed to a particular
instance of the expression.
Cheers,
Christian
[1] https://en.wikipedia.org/wiki/Functional_completeness
📝 Original message:
> The `!(a && b && ...)` can be converted to a reversal of the payment.
> The individual `!BUYER` is just the buyer choosing not to claim the
> seller->buyer direction, and the individual `!ESCROW` is just the
> escrow choosing not to reveal its temporary scalar for this payment.
> And any products (i.e. `&&`) are trivially implemented in PTLCs as
> trivial scalar and point addition.
>
> So it may actually be possible to express *any* Boolean logic, by the
> use of reversal payments and "option not to release scalar", both of
> which implement the NOT gate needed for the above. Boolean logic is a
> fairly powerful, non-Turing-complete, and consistent programming
> language, and if we can actually implement any kind of Boolean logic
> with a set of payments in various directions and Barrier Escrows we
> can enable some fairly complex use-cases..
This got me thinking about my first year logic course and functional
completeness [1], and it it trivial to prove that any boolean logic can
be expressed by this construction. We can trivially build a functionally
complete set by just constructing a NAND, a NOR, or {AND, NOT}, all of
which you've already done in your prior mails.
The resulting expressions may not be particularly nice, and result in a
multitude of payments going back and forth between the participants to
represent that logic, but it is possible. So the problem should now
simply be reduced to finding a minimal representation for a given
expression, which then minimizes the funds committed to a particular
instance of the expression.
Cheers,
Christian
[1] https://en.wikipedia.org/wiki/Functional_completeness