Non-deterministic behavior in two different scenarios

[ross-spencer]

Describe the bug

I am seeing non-deterministic behavior in two separate cases with OpShin going back to 0.16.0.

e.g. looping a build on 0.18.0:

./loop.sh 
run: 1
opshin build spending assert_sum.py
Wrote script artifacts to build/assert_sum/
addr_test1wrfah8x8ct9a493tcjdxpgsx677x9mne4ur87r3jz8f6hcse4y4dh
run: 2
opshin build spending assert_sum.py
Wrote script artifacts to build/assert_sum/
addr_test1wpyjgg4nwkwgjsvaechqq8cmtpl3k304x092h7x80jn9afc3ny327
run: 3
opshin build spending assert_sum.py
Wrote script artifacts to build/assert_sum/
addr_test1wzvqe0hxeha4kh5rglmcn3fp0uzz8j490e8g07wlzff235svw3vdw
run: 4
opshin build spending assert_sum.py
Wrote script artifacts to build/assert_sum/
addr_test1wqg6nthqagt466a7uync540erhx5a75n80ufda5larp2k5ctpzy8l
run: 5
opshin build spending assert_sum.py
Wrote script artifacts to build/assert_sum/
addr_test1wpd0ucawlpre63f3qtau8wc4dqzy8e7huy48djwgtauptssplupvz
run: 6
opshin build spending assert_sum.py
Wrote script artifacts to build/assert_sum/
addr_test1wrn536e4h9lunpt8axk8z2gevf4ua5xcaazlaka8zud9ayc9syyk4

To Reproduce
Steps to reproduce the behavior:

In both cases I am using the sample contract here (I accidentally mislabelled it first trying to use a simpler contract):

• https://github.com/OpShin/opshin/blob/61a9ed97987bfe0cb7fea434d5aa4cd65449699f/examples/smart_contracts/marketplace.py

Helper files and script:

marketplace_fstrings.zip
marketplace_no_fstring.zip

with f-strings

1. create a file assert_sum.py, use the contents from marketplace.py.
2. create a venv and Install opshin 0.16.0.
3. create a looping script to build the contract, say 100 times, and build the contract, and observe the address.
4. the address will change regularly for each iteration.
5. install the next version of opshin, e.g. 0.17.0 and see the same behavior.

Example looping script:

#! /usr/bin/bash

for i in `seq 1 100`;
do
 echo "run: $i"
 echo $(opshin build spending assert_sum.py)
 echo $(cat build/assert_sum/testnet.addr)
done

results

marketplace contract <-- f-strings

0.16.0 <- non-deterministic
0.17.0 <- non-deterministic
0.18.0 <- non-deterministic

without f-strings

I noticed removing f-strings had an impact based on a local contract. Remove them from the asset_sum.py, e.g. replace f"{string}" with "removed".

Repeat the steps above.

results

marketplace contract <- without f-strings

0.16.0 <- deterministic
0.17.0 <- deterministic
0.18.0 <- non-deterministic

Expected behavior

OpShin script output is deterministic.

Desktop (please complete the following information):

Python 3.10.12 (main, Jun 11 2023, 05:26:28) [GCC 11.4.0] on linux
Type "help", "copyright", "credits" or "license" for more information.

No LSB modules are available.
Distributor ID:	Ubuntu
Description:	Ubuntu 22.04.3 LTS
Release:	22.04
Codename:	jammy

Additional context

Two factors that seem to make a difference:

• f-strings <--- depending on their complexity, their inclusion generates less random output than the other case.
• isinstance(...) <--- seems to create the most randomized output.

The removal of both, results in deterministic output in 0.18.0.

[nielstron]

Thanks for this detailed report! Could you please share the output of pip freeze? I have a hunch at what might cause this (might be a specific issue of the newest pluthon version)

[ross-spencer]

Sure thing!

0.16.0 env from above:

appdirs==1.4.4
asn1crypto==1.5.1
attrs==23.1.0
blockfrost-python==0.5.3
cbor2==5.5.0
certifi==2023.7.22
certvalidator==0.11.1
cffi==1.16.0
charset-normalizer==3.3.1
cose==0.9.dev8
cryptography==41.0.5
ecdsa==0.18.0
ECPy==1.2.5
frozendict==2.3.8
frozenlist==1.4.0
frozenlist2==1.0.0
idna==3.4
mnemonic==0.20
opshin==0.16.0
oscrypto==1.3.0
pluthon==0.3.9
pprintpp==0.4.0
pycardano==0.9.0
pycparser==2.21
PyNaCl==1.5.0
python-secp256k1-cardano==0.2.3
requests==2.31.0
rply==0.7.8
six==1.16.0
typeguard==2.13.3
uplc==0.6.7
urllib3==2.0.7
websocket-client==1.6.4

0.18.0 env from above:

appdirs==1.4.4
asn1crypto==1.5.1
attrs==23.1.0
blockfrost-python==0.5.3
cbor2==5.5.0
certifi==2023.7.22
certvalidator==0.11.1
cffi==1.16.0
charset-normalizer==3.3.1
cose==0.9.dev8
cryptography==41.0.5
ecdsa==0.18.0
ECPy==1.2.5
frozendict==2.3.8
frozenlist==1.4.0
frozenlist2==1.0.0
idna==3.4
mnemonic==0.20
opshin==0.18.0
oscrypto==1.3.0
pluthon==0.4.0
pprintpp==0.4.0
pycardano==0.9.0
pycparser==2.21
PyNaCl==1.5.0
python-secp256k1-cardano==0.2.3
requests==2.31.0
rply==0.7.8
six==1.16.0
typeguard==2.13.3
uplc==0.6.7
urllib3==2.0.7
websocket-client==1.6.4

[nielstron]

Okay did some internal tests as well. The nondeterminism vanishes when pattern optimization (added in pluthon 0.4.0) is disabled. The reason is likely a topological sort being performed nondeterministically (depending on the currently employed hash function which detemrines the order of iteration through sets. Therefore differences only pop up between invocations of the python executable and not within a single call.). Thank you for your input!

[ross-spencer]

hi @nielstron I appreciate the speedy fix but it looks like you may have missed a case in the library, I'm not sure, but trying it today, I get the same results.

In fact, simplifying the script component:

#!opshin
from opshin.prelude import *


def validator(datum: int, redeemer: int, context: ScriptContext) -> None:
    purpose = context.purpose
    assert isinstance(purpose, Spending), f"Wrong script purpose: {purpose}"
    assert (
        datum + redeemer == 42
    ), f"Expected datum and redeemer to sum to 42, but they sum to {datum + redeemer}"

loop:

#! /usr/bin/bash

for i in `seq 1 100`;
do
 echo "run: $i"
 echo $(opshin build spending assert_sum.py)
 echo $(cat build/assert_sum/testnet.addr)
done

output:

./loop.sh 
run: 1
Wrote script artifacts to build/assert_sum/
addr_test1wpc3e4ma9984k7e72jqxx7q96yk7rpjet0gjd4jy50th36qlj8u6n
run: 2
Wrote script artifacts to build/assert_sum/
addr_test1wr7t5xvwxaqrapf8dgz3w6rqxtcrxadya3c4wr254mwld3g4t2mru
run: 3
Wrote script artifacts to build/assert_sum/
addr_test1wqn500lldptzaphwcqmzzxc6x9lwuvlkgjed3lmhuyg0dcgsepdcg
run: 4
Wrote script artifacts to build/assert_sum/
addr_test1wrxpxsewf8accs8day5nsakxs2ed44v7yltkqx6cpvggkxq2mmr8d

for completeness, the deactivation and removal of the environment and then reinstall log:

(venv) ross-spencer:/tmp/strings$ deactivate
ross-spencer:/tmp/strings$ rm -r venv
ross-spencer:/tmp/strings$ python3 -m venv venv
ross-spencer:/tmp/strings$ source venv/bin/activate
(venv) ross-spencer:/tmp/strings$ python -m pip install opshin
Collecting opshin
  Using cached opshin-0.18.1-py3-none-any.whl (106 kB)
Collecting pluthon<0.5.0,>=0.4.1
  Using cached pluthon-0.4.1-py3-none-any.whl (12 kB)
Collecting frozenlist2<2.0.0,>=1.0.0
  Using cached frozenlist2-1.0.0-py3-none-any.whl (14 kB)
Collecting uplc<0.7.0,>=0.6.6
  Using cached uplc-0.6.7-py3-none-any.whl (36 kB)
Collecting pycardano<0.10.0,>=0.9.0
  Using cached pycardano-0.9.0-py3-none-any.whl (71 kB)
Collecting frozenlist<2.0.0,>=1.3.3
  Using cached frozenlist-1.4.0-cp310-cp310-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl (225 kB)
Collecting frozendict<3.0.0,>=2.3.8
  Using cached frozendict-2.3.8-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (115 kB)
Collecting mnemonic<0.21,>=0.20
  Using cached mnemonic-0.20-py3-none-any.whl (62 kB)
Collecting ECPy<2.0.0,>=1.2.5
  Using cached ECPy-1.2.5-py3-none-any.whl (43 kB)
Collecting blockfrost-python==0.5.3
  Using cached blockfrost_python-0.5.3-py3-none-any.whl (29 kB)
Collecting websocket-client<2.0.0,>=1.4.1
  Using cached websocket_client-1.6.4-py3-none-any.whl (57 kB)
Collecting PyNaCl<2.0.0,>=1.5.0
  Using cached PyNaCl-1.5.0-cp36-abi3-manylinux_2_17_x86_64.manylinux2014_x86_64.manylinux_2_24_x86_64.whl (856 kB)
Collecting typeguard<3.0.0,>=2.13.3
  Using cached typeguard-2.13.3-py3-none-any.whl (17 kB)
Collecting cose==0.9.dev8
  Using cached cose-0.9.dev8-py3-none-any.whl (48 kB)
Collecting pprintpp<0.5.0,>=0.4.0
  Using cached pprintpp-0.4.0-py2.py3-none-any.whl (16 kB)
Collecting cbor2<6.0.0,>=5.4.3
  Using cached cbor2-5.5.0-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (228 kB)
Collecting requests
  Using cached requests-2.31.0-py3-none-any.whl (62 kB)
Collecting certvalidator
  Using cached certvalidator-0.11.1-py2.py3-none-any.whl (31 kB)
Collecting attrs
  Using cached attrs-23.1.0-py3-none-any.whl (61 kB)
Collecting cryptography
  Using cached cryptography-41.0.5-cp37-abi3-manylinux_2_28_x86_64.whl (4.4 MB)
Collecting ecdsa
  Using cached ecdsa-0.18.0-py2.py3-none-any.whl (142 kB)
Collecting rply<0.8.0,>=0.7.8
  Using cached rply-0.7.8-py2.py3-none-any.whl (16 kB)
Collecting python-secp256k1-cardano<0.3.0,>=0.2.3
  Using cached python_secp256k1_cardano-0.2.3-py3-none-any.whl (28 kB)
Collecting cffi>=1.4.1
  Using cached cffi-1.16.0-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (443 kB)
Collecting appdirs
  Using cached appdirs-1.4.4-py2.py3-none-any.whl (9.6 kB)
Collecting pycparser
  Using cached pycparser-2.21-py2.py3-none-any.whl (118 kB)
Collecting oscrypto>=0.16.1
  Using cached oscrypto-1.3.0-py2.py3-none-any.whl (194 kB)
Collecting asn1crypto>=0.18.1
  Using cached asn1crypto-1.5.1-py2.py3-none-any.whl (105 kB)
Collecting six>=1.9.0
  Using cached six-1.16.0-py2.py3-none-any.whl (11 kB)
Collecting idna<4,>=2.5
  Using cached idna-3.4-py3-none-any.whl (61 kB)
Collecting certifi>=2017.4.17
  Using cached certifi-2023.7.22-py3-none-any.whl (158 kB)
Collecting urllib3<3,>=1.21.1
  Using cached urllib3-2.0.7-py3-none-any.whl (124 kB)
Collecting charset-normalizer<4,>=2
  Using cached charset_normalizer-3.3.2-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (142 kB)
Installing collected packages: python-secp256k1-cardano, pprintpp, frozenlist2, ECPy, asn1crypto, appdirs, websocket-client, urllib3, typeguard, six, rply, pycparser, oscrypto, mnemonic, idna, frozenlist, frozendict, charset-normalizer, certifi, cbor2, attrs, requests, ecdsa, cffi, certvalidator, PyNaCl, cryptography, blockfrost-python, cose, pycardano, uplc, pluthon, opshin
Successfully installed ECPy-1.2.5 PyNaCl-1.5.0 appdirs-1.4.4 asn1crypto-1.5.1 attrs-23.1.0 blockfrost-python-0.5.3 cbor2-5.5.0 certifi-2023.7.22 certvalidator-0.11.1 cffi-1.16.0 charset-normalizer-3.3.2 cose-0.9.dev8 cryptography-41.0.5 ecdsa-0.18.0 frozendict-2.3.8 frozenlist-1.4.0 frozenlist2-1.0.0 idna-3.4 mnemonic-0.20 opshin-0.18.1 oscrypto-1.3.0 pluthon-0.4.1 pprintpp-0.4.0 pycardano-0.9.0 pycparser-2.21 python-secp256k1-cardano-0.2.3 requests-2.31.0 rply-0.7.8 six-1.16.0 typeguard-2.13.3 uplc-0.6.7 urllib3-2.0.7 websocket-client-1.6.4
(venv) ross-spencer:/tmp/strings$ python -m pip-freeze
/tmp/strings/venv/bin/python: No module named pip-freeze
(venv) ross-spencer:/tmp/strings$ python -m pip freeze
appdirs==1.4.4
asn1crypto==1.5.1
attrs==23.1.0
blockfrost-python==0.5.3
cbor2==5.5.0
certifi==2023.7.22
certvalidator==0.11.1
cffi==1.16.0
charset-normalizer==3.3.2
cose==0.9.dev8
cryptography==41.0.5
ecdsa==0.18.0
ECPy==1.2.5
frozendict==2.3.8
frozenlist==1.4.0
frozenlist2==1.0.0
idna==3.4
mnemonic==0.20
opshin==0.18.1
oscrypto==1.3.0
pluthon==0.4.1
pprintpp==0.4.0
pycardano==0.9.0
pycparser==2.21
PyNaCl==1.5.0
python-secp256k1-cardano==0.2.3
requests==2.31.0
rply==0.7.8
six==1.16.0
typeguard==2.13.3
uplc==0.6.7
urllib3==2.0.7
websocket-client==1.6.4
(venv) ross-spencer:/tmp/strings$ ./loop
bash: ./loop: No such file or directory
(venv) ross-spencer:/tmp/strings$ ls
abc.cbor  assert_sum.py  build  def.cbor  loop.sh  Makefile  venv
(venv) ross-spencer:/tmp/strings$ ./loop.sh 
run: 1
Wrote script artifacts to build/assert_sum/
addr_test1wpc3e4ma9984k7e72jqxx7q96yk7rpjet0gjd4jy50th36qlj8u6n
run: 2
Wrote script artifacts to build/assert_sum/
addr_test1wr7t5xvwxaqrapf8dgz3w6rqxtcrxadya3c4wr254mwld3g4t2mru
run: 3
Wrote script artifacts to build/assert_sum/
addr_test1wqn500lldptzaphwcqmzzxc6x9lwuvlkgjed3lmhuyg0dcgsepdcg
run: 4
Wrote script artifacts to build/assert_sum/
addr_test1wrxpxsewf8accs8day5nsakxs2ed44v7yltkqx6cpvggkxq2mmr8d

[nielstron]

You are right, it seems I missed the isinstance issue. Investigating...

Update: It appears that printing of Union type objects is the culprit - I can imagine that there is some unordered-set stuff going on that is invalid

[nielstron]

Keeping this open and delaying another patch version until @ross-spencer had time to look at the latest dev branch version :)

[ross-spencer]

a bit late with other tasks this morning but I will have a look now @nielstron

[ross-spencer]

@nielstron nice work! the fix looks great to me, I only ran through the examples above, and a few of the local contracts we've been working on where we first saw the issue, but seeing the same each time.