📅 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
Christian Decker [ARCHIVE] /
npub1wt…gtuyn
2023-06-09 13:02:02
in reply to nevent1q…0a8k
Author Public Key
npub1wtx5qvewc7pd6znlvwktq03mdld05mv3h5dkzfwd3dc30gdmsptsugtuynPublished at
2023-06-09 13:02:02Event JSON
{
"id": "56888d6b62f099482e6076db2386d072ef673246c4a25a2ba47569744423492a",
"pubkey": "72cd40332ec782dd0a7f63acb03e3b6fdafa6d91bd1b6125cd8b7117a1bb8057",
"created_at": 1686315722,
"kind": 1,
"tags": [
[
"e",
"314d09df8983f36a6cfef295360e46d7142fc01ed765a13fbdab5e1db6b5c415",
"",
"root"
],
[
"e",
"5ccb11ce8bc7b59d01797c923994f80783017413b56d645cc0838deccdf4a09b",
"",
"reply"
],
[
"p",
"4505072744a9d3e490af9262bfe38e6ee5338a77177b565b6b37730b63a7b861"
]
],
"content": "📅 Original date posted:2021-02-27\n📝 Original message:\n\u003e The `!(a \u0026\u0026 b \u0026\u0026 ...)` can be converted to a reversal of the payment.\n\u003e The individual `!BUYER` is just the buyer choosing not to claim the\n\u003e seller-\u003ebuyer direction, and the individual `!ESCROW` is just the\n\u003e escrow choosing not to reveal its temporary scalar for this payment.\n\u003e And any products (i.e. `\u0026\u0026`) are trivially implemented in PTLCs as\n\u003e trivial scalar and point addition.\n\u003e\n\u003e So it may actually be possible to express *any* Boolean logic, by the\n\u003e use of reversal payments and \"option not to release scalar\", both of\n\u003e which implement the NOT gate needed for the above. Boolean logic is a\n\u003e fairly powerful, non-Turing-complete, and consistent programming\n\u003e language, and if we can actually implement any kind of Boolean logic\n\u003e with a set of payments in various directions and Barrier Escrows we\n\u003e can enable some fairly complex use-cases..\n\nThis got me thinking about my first year logic course and functional\ncompleteness [1], and it it trivial to prove that any boolean logic can\nbe expressed by this construction. We can trivially build a functionally\ncomplete set by just constructing a NAND, a NOR, or {AND, NOT}, all of\nwhich you've already done in your prior mails.\n\nThe resulting expressions may not be particularly nice, and result in a\nmultitude of payments going back and forth between the participants to\nrepresent that logic, but it is possible. So the problem should now\nsimply be reduced to finding a minimal representation for a given\nexpression, which then minimizes the funds committed to a particular\ninstance of the expression.\n\nCheers,\nChristian\n\n[1] https://en.wikipedia.org/wiki/Functional_completeness",
"sig": "d2be11fa44d371be3262fa4ad83450e4daac24dea345f21e4cd137353e8092d1647e6a13c08870daeb5f29e78a419b6a7f72fd1383e304ced3e360b33b27deee"
}