Git Product home page Git Product logo

rust-miniscript's Introduction

Rust Bitcoin

Rust Bitcoin logo by Hunter Trujillo, see license and source files under /logo

Library with support for de/serialization, parsing and executing on data-structures and network messages related to Bitcoin.

Crate Info CC0 1.0 Universal Licensed CI Status API Docs Rustc Version 1.63.0+ Chat on IRC

Documentation

Supports (or should support)

  • De/serialization of Bitcoin protocol network messages
  • De/serialization of blocks and transactions
  • Script de/serialization
  • Private keys and address creation, de/serialization and validation (including full BIP32 support)
  • PSBT v0 de/serialization and all but the Input Finalizer role. Use rust-miniscript to finalize.

For JSONRPC interaction with Bitcoin Core, it is recommended to use rust-bitcoincore-rpc.

It is recommended to always use cargo-crev to verify the trustworthiness of each of your dependencies, including this one.

Known limitations

Consensus

This library must not be used for consensus code (i.e. fully validating blockchain data). It technically supports doing this, but doing so is very ill-advised because there are many deviations, known and unknown, between this library and the Bitcoin Core reference implementation. In a consensus based cryptocurrency such as Bitcoin it is critical that all parties are using the same rules to validate data, and this library is simply unable to implement the same rules as Core.

Given the complexity of both C++ and Rust, it is unlikely that this will ever be fixed, and there are no plans to do so. Of course, patches to fix specific consensus incompatibilities are welcome.

Support for 16-bit pointer sizes

16-bit pointer sizes are not supported and we can't promise they will be. If you care about them please let us know, so we can know how large the interest is and possibly decide to support them.

Documentation

Currently can be found on docs.rs/bitcoin. Patches to add usage examples and to expand on existing docs would be extremely appreciated.

Contributing

Contributions are generally welcome. If you intend to make larger changes please discuss them in an issue before PRing them to avoid duplicate work and architectural mismatches. If you have any questions or ideas you want to discuss please join us in #bitcoin-rust on libera.chat.

For more information please see CONTRIBUTING.md.

Minimum Supported Rust Version (MSRV)

This library should always compile with any combination of features on Rust 1.63.0.

Use Cargo-minimal.lock to build the MSRV by copying to Cargo.lock and building.

External dependencies

We integrate with a few external libraries, most notably serde. These are available via feature flags. To ensure compatibility and MSRV stability we provide two lock files as a means of inspecting compatible versions: Cargo-minimal.lock containing minimal versions of dependencies and Cargo-recent.lock containing recent versions of dependencies tested in our CI.

We do not provide any guarantees about the content of these lock files outside of "our CI didn't fail with these versions". Specifically, we do not guarantee that the committed hashes are free from malware. It is your responsibility to review them.

Installing Rust

Rust can be installed using your package manager of choice or rustup.rs. The former way is considered more secure since it typically doesn't involve trust in the CA system. But you should be aware that the version of Rust shipped by your distribution might be out of date. Generally this isn't a problem for rust-bitcoin since we support much older versions than the current stable one (see MSRV section).

Building

The cargo feature std is enabled by default. At least one of the features std or no-std or both must be enabled.

Enabling the no-std feature does not disable std. To disable the std feature you must disable default features. The no-std feature only enables additional features required for this crate to be usable without std. Both can be enabled without conflict.

The library can be built and tested using cargo:

git clone [email protected]:rust-bitcoin/rust-bitcoin.git
cd rust-bitcoin
cargo build

You can run tests with:

cargo test

Please refer to the cargo documentation for more detailed instructions.

Just

We support just for running dev workflow commands. Run just from your shell to see list available sub-commands.

Building the docs

We build docs with the nightly toolchain, you may wish to use the following shell alias to check your documentation changes build correctly.

alias build-docs='RUSTDOCFLAGS="--cfg docsrs" cargo +nightly rustdoc --features="$FEATURES" -- -D rustdoc::broken-intra-doc-links'

Testing

Unit and integration tests are available for those interested, along with benchmarks. For project developers, especially new contributors looking for something to work on, we do:

There are always more tests to write and more bugs to find, contributions to our testing efforts extremely welcomed. Please consider testing code a first class citizen, we definitely do take PRs improving and cleaning up test code.

Unit/Integration tests

Run as for any other Rust project cargo test --all-features.

Benchmarks

We use a custom Rust compiler configuration conditional to guard the bench mark code. To run the bench marks use: RUSTFLAGS='--cfg=bench' cargo +nightly bench.

Mutation tests

We have started doing mutation testing with mutagen. To run these tests first install the latest dev version with cargo +nightly install --git https://github.com/llogiq/mutagen then run with RUSTFLAGS='--cfg=mutate' cargo +nightly mutagen.

Code verification

We have started using kani, install with cargo install --locked kani-verifier (no need to run cargo kani setup). Run the tests with cargo kani.

Pull Requests

Every PR needs at least two reviews to get merged. During the review phase maintainers and contributors are likely to leave comments and request changes. Please try to address them, otherwise your PR might get closed without merging after a longer time of inactivity. If your PR isn't ready for review yet please mark it by prefixing the title with WIP: .

CI Pipeline

The CI pipeline requires approval before being run on each MR.

In order to speed up the review process the CI pipeline can be run locally using act. The fuzz and Cross jobs will be skipped when using act due to caching being unsupported at this time. We do not actively support act but will merge PRs fixing act issues.

Githooks

To assist devs in catching errors before running CI we provide some githooks. Copy the hooks in githooks/ to your githooks folder or run just githooks-install to copy them all.

Policy on Altcoins/Altchains

Since the altcoin landscape includes projects which frequently appear and disappear, and are poorly designed anyway we do not support any altcoins. Supporting Bitcoin properly is already difficult enough and we do not want to increase the maintenance burden and decrease API stability by adding support for other coins.

Our code is public domain so by all means fork it and go wild :)

Release Notes

Release notes are done per crate, see:

Licensing

The code in this project is licensed under the Creative Commons CC0 1.0 Universal license. We use the SPDX license list and SPDX IDs.

rust-miniscript's People

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

rust-miniscript's Issues

Miniscript Resource Limit calculations

Review the codebase to re-verify which of the resource limits are tested and document how are tested/calculated.

In general, we only enforce limits of standardness of the bitcoin-core node policies. Taken from https://github.com/rust-bitcoin/rust-miniscript

  • Scripts over 10000 bytes are invalid by consensus (bare, P2SH, P2WSH, P2SH-P2WSH).

  • Scripts over 520 bytes are invalid by consensus (P2SH).

  • Script satisfactions where the total number of non-push opcodes plus the number of keys participating in all executed thresh_ms, is above 201, are invalid by consensus (bare, P2SH, P2WSH, P2SH-P2WSH).

  • Anything but c:pk(key) (P2PK), c:pk_h(key) (P2PKH), and thresh_m(k,...) up to n=3 is invalid by standardness (bare).

  • Scripts over 3600 bytes are invalid by standardness (P2WSH, P2SH-P2WSH).

  • Script satisfactions with a serialized scriptSig over 1650 bytes are invalid by standardness (P2SH).

  • Script satisfactions with a witness consisting of over 100 stack elements (excluding the script itself) are invalid by standardness (P2WSH, P2SH-P2WSH).

Tests in fuzz directory

I guess the purpose of duplicate_crash() functions to replicate crashes on Travis for debugging, but I don't think they should belong in the fuzz directory.
The current codebase seems to have the same fuzz test extend_from_vec across all files.

Support for sortedmulti descriptor script expression?

Any plans to add support for the sortedmulti script expression? Some wallets like Spectre and hww's like Coldcard produce / expect BIP67 format.

This would improve compatibility for bdk, which uses rust-miniscript as a dependency and doesn't easily allow for loading descriptors with sortedmulti.

Optimize 1-of-N thresholds to or()s

#113 left out a FIXME that we are unsure to fix at all, opening this to clarify if we want it or not.

We now optimize N-of-N thresholds to and(), and i propose to do the same for 1-of-N thresholds (using or()s). After discussing this with sipa (who implemented this in C++) and @sanket1729 the main issue with the latter seems to be the exponential complexity with the number of or()s.

I personally think (user point of view) that if the complexity growth is only applied on the policy compilation it's fine, as we only ever compile once to miniscript per user and then store the Miniscript Descriptor while the Script size is felt onchain For Ever (:tm:).

Compiling invalid policy "thresh(2,pk(),thresh(0,pk()))" causes "threshold subs, which we just compiled, typeck: TypeCheck("fragment «thresh(0,jtvc:pk_h())» has a threshold value of 0")"

Compiling invalid policy thresh(2,pk(),thresh(0,pk())) causes threshold subs, which we just compiled, typeck: TypeCheck("fragment «thresh(0,jtvc:pk_h())» has a threshold value of 0").

Crash location:

https://github.com/apoelstra/rust-miniscript/blob/2aee5708e3e4f29a4d41301adc998d6b95fc4c76/src/policy/compiler.rs#L960-L964

How to control branching through `Satisfier`?

I am currently trying to use miniscript to create HTLCs and construct the redeem/refund transaction for it.

However, I run into the limitation that I never get a chance to state somewhere, which branch of the script I'd like to execute for my spending transaction. It always places 01 onto the witness stack.

Is this by design?
The only way on how to overcome that at the moment is to manually modify the witness stack after the call to satisfy. However, that doesn't seem to be the most elegant solution.

Satisfaction::satisfy on `AndV` flips the two branches

I was recently playing around with Miniscript and I noticed that whenever I try to satisfy a descriptor in the form of and_v(vc:pk_k(A),c:pk_k(B)), the two signatures appears to be inverted in the scriptSig/witness.

By inverted I mean that the signature made with key B is placed on the stack in such a way that it will be checked against key A. I'm honestly not sure if this happens every time an "and_v" is involved or if this is some kind of edge case.

I threw together this quick example to demonstrate the issue. The idea is that I'm creating two public keys and two signatures, then I assign the signature "with many zeros" as if it was made by the public key that also has "many zeros". It sucks but I guess it works to kinda tag the key and signature:

    let public_keys = vec![
        bitcoin::PublicKey::from_slice(&[2; 33]).expect("key 1"),
        bitcoin::PublicKey::from_slice(&[
            0x02,
            0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08,
            0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08,
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        ]).expect("key 2"),
    ];
    let bitcoin_sigs = vec![(
        // copied at random off the blockchain; this is not actually a valid
        // signature for this transaction; Miniscript does not verify
        secp256k1::Signature::from_str(
            "3045\
             0221\
             00f7c3648c390d87578cd79c8016940aa8e3511c4104cb78daa8fb8e429375efc1\
             0220\
             531d75c136272f127a5dc14acc0722301cbddc222262934151f140da345af177",
        )
        .unwrap(),
        bitcoin::SigHashType::All,
    ), (
        secp256k1::Signature::from_str(
            "3045\
             0221\
             00f700000000000000000000000000000000000000000000000000000000000000\
             0220\
             5300000000000000000000000000000000000000000000000000000000000000",
        )
        .unwrap(),
        bitcoin::SigHashType::All,
    )];

    let descriptor_str = format!(
        "sh(and_v(vc:pk_k({}),c:pk_k({})))",
        public_keys[0], public_keys[1],
    );

    println!("{}", descriptor_str);

    // Descriptor for the output being spent
    let my_descriptor =
        BitcoinDescriptor::from_str(&descriptor_str[..]).expect("parse descriptor string");

    println!("{}", my_descriptor.witness_script());

    let mut sigs = HashMap::<bitcoin::PublicKey, miniscript::BitcoinSig>::new();
    sigs.insert(public_keys[0], bitcoin_sigs[0]);
    sigs.insert(public_keys[1], bitcoin_sigs[1]);

    assert!(my_descriptor.satisfy(&mut tx.input[0], &sigs).is_ok());
    println!("{}", tx.input[0].script_sig);

And that's the output:

sh(and_v(vc:pk_k(020202020202020202020202020202020202020202020202020202020202020202),c:pk_k(020102030405060708010203040506070800000000000000000000000000000000)))
Script(OP_PUSHBYTES_33 020202020202020202020202020202020202020202020202020202020202020202 OP_CHECKSIGVERIFY OP_PUSHBYTES_33 020102030405060708010203040506070800000000000000000000000000000000 OP_CHECKSIG)
Script(OP_PUSHBYTES_72 3045022100f7c3648c390d87578cd79c8016940aa8e3511c4104cb78daa8fb8e429375efc10220531d75c136272f127a5dc14acc0722301cbddc222262934151f140da345af17701 OP_PUSHBYTES_72 3045022100f7000000000000000000000000000000000000000000000000000000000000000220530000000000000000000000000000000000000000000000000000000000000001 OP_PUSHBYTES_70 21020202020202020202020202020202020202020202020202020202020202020202ad21020102030405060708010203040506070800000000000000000000000000000000ac)

So if we ignore the last push that is just the script for the P2SH, we can see that the first signature it is going to check is the "one with many zeros", but it's going to check it against the other public key in the first OP_CHECKSIGVERIFY.

The stupid/obvious fix I came up with is just to flip the two branches like this:

--- a/src/miniscript/satisfy.rs
+++ b/src/miniscript/satisfy.rs
@@ -580,7 +580,7 @@ impl Satisfaction {
                 let l_sat = Self::satisfy(&l.node, stfr);
                 let r_sat = Self::satisfy(&r.node, stfr);
                 Satisfaction {
-                    stack: Witness::combine(l_sat.stack, r_sat.stack),
+                    stack: Witness::combine(r_sat.stack, l_sat.stack),
                     has_sig: l_sat.has_sig || r_sat.has_sig,
                 }
             }

But I guess this could have some side effects that I don't know of.

I would love to work on a proper fix for this, I guess I just need a little bit of help to head to the right direction.

Thanks!

Change Satisfier trait for consistency with BIP 65/112

The current implementation of satisfier trait is not enforcing other rules strictly from BIP65/BIP 112.

TODO:

  • Check timelocks values can be compared if both are either below or above 500 million

  • In pbst finalizer, also check additional rules in BIP 65(transaction version) and BIP 112(whether inputs are finalized etc)

Bug: `thresh(k, pubkeys[21])` policy does not compile for `k < 3`

<sanket1729> Yup, that is indeed a bug. The issue is for k = 1 to 3, we pick sub-compilations for children optimally. All pk() are mapped to pkh() with a likely wrapper and that exceeds the max-opcount for 200 
20:01 <sanket1729> The correct compiler logic would pick optimal compilation for children keeping tract of possible op-counts. 
20:02 <sanket1729> But that would lead to even slower compiler with high space requirements. 
20:03 <sanket1729> For k = 4, the probabilities for leaf are high, so their optimal compilations are mapped correctly under the MAX_OP_COUNT
20:03 <sanket1729> sipa: Do you have any inputs?
20:04 <jeremyrubin> "taproot fixes this"
20:06 <sipa> lol
20:06 <sipa> yes
20:06 <sanket1729> Maybe, if the optimal greedy compiler fails. We should build another version that minimizes the op-counts but still constructs some miniscript. 

Should Taproot or us fix this ?

Feature request: "lax" interpreter that will flag (but not fail) some issues

Our current interpreter assumes standardness rules and will fail when one is violated during evaluation (e.g. a non-null invalid signature, or a non-minimal if). Would be good if we could recover from these but somehow indicate to the user that something is wrong.

Probably ought to be prototyped in Esplora.

Compiling thresh-policy with after(0) or older(0) (such as "thresh(2,after(0),pk(),pk())") causes panic

Crash location:

https://github.com/apoelstra/rust-miniscript/blob/2aee5708e3e4f29a4d41301adc998d6b95fc4c76/src/policy/compiler.rs#L449-L452

When compiling thresh(2,after(0),pk(),pk()):

thread 'main' panicked at 'called `Result::unwrap()` on an `Err` value: 
Error { fragment: [TYPECHECK FAILED]older(0), error: ZeroTime }', src/libcore/result.rs:1084:5

When compiling thresh(2,older(0),pk(),pk()):

thread 'main' panicked at 'called `Result::unwrap()` on an `Err` value: 
Error { fragment: [TYPECHECK FAILED]older(0), error: ZeroTime }', src/libcore/result.rs:1084:5

FWIW, a related problem with after(N)/older(N) handling with invalid N was found and fixed in the C++ implementation: sipa/miniscript#4

How to run it?

Hi, Rust noob here :)
I have Rust and Cargo installed, I can run cargo build in the repo and it doesn't return any error, but then when I try cargo run, it tells me this: error: a bin target must be available for cargo run
It seems I'm lacking a binary file, but I don't know where it's supposed to be, I had a look in the target directory but didn't found it, can someone help me on this?

Fuzz failure for parse descriptor

Fuzzer failed roundtrip for the following:

`>>bytes.fromhex("5b31313131314631315d3033333333333333333333333333333333333333333333333333333333333332333333333333333333333333333333333333333333333333333433333333333333335d5d3333335d5d335d5d3130313333333333333333333333333433333333335d5d5d31305d3333333333336d6d6d6d")
b'[11111F11]033333333333333333333333333333323333333333333333333333333433333333]]333]]3]]101333333333333433333]]]10]333333mmmm'

How stable is the miniscript implementation in terms of the generated script?

While playing around with the policy compiler, I noticed that the generated script has some cool optimizations! At the same time, I was quite surprised in the way it was structured.

For our trustless atomic swap usecase, we need to infer, what the HTLC address will be that the other party will lock the funds on. For this, we currently rely on a static HTLC script which allows us to deterministically compute the HTLC address given the parameter (identities, secret-hash and expiry).

My question is, how stable is miniscript in terms of the generated script? If we were to define our Bitcoin-HTLCs through miniscript, we somehow have to ensure that two versions of the software generate the same underlying script (resulting in the same address).

What is the versioning policy of miniscript in regards to that?
Are changes to the generated script considered breaking changes?
Can we rely on the generated script being the same across future versions?

And()s compilation can produce invalid Script

The translation of thresh(n, n*policy) to a concatenation of and() uncovered that we can actually compile policy that are creating invalid (non-standard) Scripts.

A small test to reproduce the behaviour with a 100-of-100 multisig (which cannot be spent by a standard transaction as the number on the stack would excess the MAX_STANDARD_P2WSH_STACK_ITEMS).
We can create (eg) 128-of-128 p2wsh as well, which are also invalid by the witness script size.

diff --git a/src/policy/compiler.rs b/src/policy/compiler.rs
index 31ea530..28d0bec 100644
--- a/src/policy/compiler.rs
+++ b/src/policy/compiler.rs
@@ -1436,6 +1436,17 @@ mod tests {
             };
         }
     }
+
+    #[test]
+    fn test_limits() {
+        let (keys, _) = pubkeys_and_a_sig(100);
+
+        let pubkeys: Vec<Concrete<bitcoin::PublicKey>> =
+            keys.iter().map(|pubkey| Concrete::Key(*pubkey)).collect();
+        let big_thresh_ms: Result<SegwitMiniScript, _> =
+            Concrete::Threshold(100, pubkeys).compile();
+        assert_eq!(big_thresh_ms, Err(CompilerError::MaxOpCountExceeded));
+    }
 }
 
 #[cfg(all(test, feature = "unstable"))]

Compiling heavily nested policy causes "fatal runtime error: stack overflow"

Compiling heavily nested policy causes fatal runtime error: stack overflow:

Code:

use miniscript::{policy, DummyKey};
use std::str::FromStr;

type DummyPolicy = policy::Concrete<DummyKey>;

fn main() {
    let policy_string = "thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk()))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))";
    if let Ok(policy) = DummyPolicy::from_str(&policy_string) {
        if let Ok(_) = policy.compile() {}
    }
}

Output:

thread 'main' has overflowed its stack
fatal runtime error: stack overflow
Aborted

What needs doing?

Just heard about this on the noded podcast and it sounds like a really cool / worthwhile project! What sort of work needs to be done? I'm familiar with Rust and web development but not with Bitcoin Script.

Inconsistent translate_pk method signatures

Is there a particular reason why there are different signatures for the translate_pk methods on the various types?

  • Descriptor::translate_pk has
        mut translatefpk: Fpk,
        mut translatefpkh: Fpkh,
    where
        Fpk: FnMut(&Pk) -> Result<Q, E>,
        Fpkh: FnMut(&Pk::Hash) -> Result<Q::Hash, E>,
  • Miniscript::translate_pk has
        translatefpk: &mut FPk,
        translatefpkh: &mut FPkh,
    where
        FPk: FnMut(&Pk) -> Result<Q, Error>,
        FPkh: FnMut(&Pk::Hash) -> Result<Q::Hash, Error>,
  • Terminal::translate_pk` has
        translatefpk: &mut FPk,
        translatefpkh: &mut FPkh,
    where
        FPk: FnMut(&Pk) -> Result<Q, Error>,
        FPkh: FnMut(&Pk::Hash) -> Result<Q::Hash, Error>,
  • Policy::translate_pk (both semantic and concrete) has
        mut translatefpk: Fpk
    where
        Fpk: FnMut(&Pk) -> Result<Q, E>,

Add detailed docs for compiler

The compiler part of the miniscript project has created some confusion about its usage. A detailed doc might be good place to redirect people with general questions about the usage and functioning of the compiler.

So far,

  • Explain general usage of compiler API

  • Explain optimality guarantees

  • Non-determinism of the compiler.

  • Edge cases and op-code related knapsack problems

Speed of descriptor derivation

I noticed deriving a bunch of addresses from a descriptor containing a single xpub was quite slow compared to ExtendedPubKey::derive, the reason is that secp context is initialized at every derivation here:

let ctx = secp256k1::Secp256k1::verification_only();

I am not sure which is the best way to avoid initialization at every derivation, since passing secp as parameter "pollute" the API and I don't see an easy way to add secp as field of DescriptorXPub since there would be problem with the derived trait of DescriptorXPub such Clone. Also, I don't think lazy_static! globally is a viable option.

Are there plan to improve this?

Miri flag passing changed

cargo miri test changed to be more compatible with cargo test, but this means we had to find a different way to pass flags to the interpreter, so there now is a MIRIFLAGS environment variable for that. The old way still works for now, but is deprecated.

This affects the following line:

cargo miri test -- -- miri_

This should now be cargo miri test miri_, running the same tests as cargo test miri_.

Detect key reuse in policy and Miniscript (was: Optimise policy compilation when keys are shared across branches)

Currently, the policy needs to be tweaked to get the most optimized Bitcoin Script when thresh() that share some keys are used across or() branches.

For example:

or(thresh(4,pk(A),pk(B),pk(C),pk(D)), thresh(4,pk(A),pk(B),pk(E),pk(F)))

Currently returns (on http://bitcoin.sipa.be/miniscript/, but tested the same behaviour with rust-bitcoin locally)

OP_IF
  <A> OP_CHECKSIGVERIFY <B> OP_CHECKSIGVERIFY <C> OP_CHECKSIGVERIFY <D>
OP_ELSE
  <A> OP_CHECKSIGVERIFY <B> OP_CHECKSIGVERIFY <E> OP_CHECKSIGVERIFY <F>
OP_ENDIF
OP_CHECKSIG

    Script: 282 WU
    Input: 293.500000 WU
    Total: 575.500000 WU

And needs to be optimized by hand:

and(thresh(2,pk(A),pk(B)),or(thresh(2,pk(C),pk(D)),thresh(2,pk(E),pk(F))))

To return

<A> OP_CHECKSIGVERIFY <B> OP_CHECKSIGVERIFY OP_IF
  <C> OP_CHECKSIGVERIFY <D>
OP_ELSE
  <E> OP_CHECKSIGVERIFY <F>
OP_ENDIF
OP_CHECKSIG

    Script: 212 WU
    Input: 293.500000 WU
    Total: 505.500000 WU

Would a PR adding an analysis of duplicated keys to the policy compiler be welcome ?

Depending on rust-miniscript, Passing Config Flags to Sub-Crates

The config flags on the secp linked are not configurable, and the provided version does not set many flags. E.g., this fails with no method generate_keypair.

 use libminiscript::bitcoin;
 use libminiscript::secp256k1::Secp256k1;
 use rand::rngs::OsRng;
 fn main() {
     let secp = Secp256k1::new();
     let mut rng = OsRng::new().expect("RNG Failure");
     let (secret_key, alice) = secp.generate_keypair(&mut rng);
     let (secret_key_bob, bob) = secp.generate_keypair(&mut rng);
}

So you need to require an independent version:

Rust linker seems to not like linking multiple versions of Secp, so it seem best to use the re-exported rust-bitcoin (and secp) out of miniscript when depending on miniscript. E.g., this fails with a linker error:

 use libminiscript::bitcoin;
 use secp256k1::Secp256k1;
 use rand::rngs::OsRng;
 fn main() {
     let secp = Secp256k1::new();
     let mut rng = OsRng::new().expect("RNG Failure");
     let (secret_key, _alice) = secp.generate_keypair(&mut rng);
     let (secret_key_bob, _bob) = secp.generate_keypair(&mut rng);
     let alice = libminiscript::bitcoin::PublicKey::from_slice(&_alice.serialize()).unwrap();
     let bob = libminiscript::bitcoin::PublicKey::from_slice(&_bob.serialize()).unwrap();
}
$ cargo rustc -- --version
rustc 1.46.0 (04488afe3 2020-08-24)
error: linking with `cc` failed: exit code: 1
  |
  = note: "cc" "-Wl,--as-needed" "-Wl,-z,noexecstack" "-m64" "-Wl,--eh-frame-hdr" "-L" "/home/jr/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/x86_64-unknown-linux-gnu/lib" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.170p5648qkcuy0oo.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.18k0wifup38o15dp.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.18upit0vyug8qf31.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.1bt0zti0w6mffpfr.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.1mo0j3mu7g506mj4.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.1npgcu2je0vc7xyr.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.1olsg1xkfz8uzzf.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.1p94loch6yt9g6xg.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.22i480apytqpfpsx.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.23gj0wzlfraeox1a.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.24eyw41ep47gv297.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.2e3x1z0gy572p2dw.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.2erf6i20arqkcil8.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.2qcmheiheoa7ucux.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.2svpe9yv9u0q9gdf.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.2u2ddafj3oug5n8a.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.2ycn88crtdrgud5j.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.3anw5w3m9ptr3ld2.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.3j4d8hu9g4v673s.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.3msj4lspfwm1yf8m.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.3nlifsnwrlsmjnbt.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.3opvw4hy9hxi1zcp.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.3p6z636kdsjc1pi3.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.3wiocd80ads3w8hq.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.3xstet1aljjh6wwd.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.40edsd1nwldiuydy.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.40higgc7ejdaapre.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.41cygthe85xuu0bj.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.43ovqnwbgxc0seiq.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.46cweys3e3xt06ir.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.494s2ws8rf0by4i4.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.4a7h5fj2n6kbokkd.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.4eo4pqdrt8tqc210.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.4eogku3bpjjfwuql.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.4kgnlu4n5e8rcp9c.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.4novwhyy3zebuhzl.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.4qtmhtdl4d2h3x23.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.4srobd9yncu8n7t.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.4v8r7f86tvl74ggg.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.50z65saw54ezhdq7.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.52ytbbup1nhbivm0.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.56beqtyw7ncy5aya.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.59rzhcn5n8pyh3ab.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.5g1ysvsjra35ovpz.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.5hddhpdlodh2f50.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.7ilae30exwiqpyg.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.o7b8gdma9jw3ehp.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.q5veo0gli1ex6xt.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.rnwsl0aomnone5f.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.t0xv43p9rkh92sy.rcgu.o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.z5fxzad0ji1s7yx.rcgu.o" "-o" "/home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b" "-Wl,--gc-sections" "-pie" "-Wl,-zrelro" "-Wl,-znow" "-nodefaultlibs" "-L" "/home/jr/develop/rust-play/target/debug/deps" "-L" "/home/jr/develop/rust-play/target/debug/build/secp256k1-sys-a54628866a2bb93f/out" "-L" "/home/jr/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/x86_64-unknown-linux-gnu/lib" "-Wl,-Bstatic" "/home/jr/develop/rust-play/target/debug/deps/libsapio-017cb2db2ad49065.rlib" "/home/jr/develop/rust-play/target/debug/deps/liblazy_static-adcdbda25352d993.rlib" "-L" "/home/jr/develop/rust-play/target/debug/deps" "-Wl,-Bdynamic" "-llibminiscript-1b433a83ca55005a" "-Wl,--start-group" "-L" "/home/jr/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/x86_64-unknown-linux-gnu/lib" "-lstd-cf0f33af3a901778" "-Wl,--end-group" "-Wl,-Bstatic" "/home/jr/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/x86_64-unknown-linux-gnu/lib/libcompiler_builtins-f1a9d8c443e20b5e.rlib" "-Wl,-Bdynamic" "-ldl" "-lrt" "-lpthread" "-lgcc_s" "-lc" "-lm" "-lrt" "-lpthread" "-lutil" "-ldl" "-lutil"
  = note: /usr/bin/ld: /home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.2svpe9yv9u0q9gdf.rcgu.o: in function `<secp256k1::Secp256k1<C> as core::ops::drop::Drop>::drop':
          /home/jr/.cargo/registry/src/github.com-1ecc6299db9ec823/secp256k1-0.17.2/src/lib.rs:584: undefined reference to `rustsecp256k1_v0_1_1_context_preallocated_destroy'
          /usr/bin/ld: /home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.40higgc7ejdaapre.rcgu.o: in function `secp256k1::key::PublicKey::from_secret_key':
          /home/jr/.cargo/registry/src/github.com-1ecc6299db9ec823/secp256k1-0.17.2/src/key.rs:226: undefined reference to `rustsecp256k1_v0_1_1_ec_pubkey_create'
          /usr/bin/ld: /home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.40higgc7ejdaapre.rcgu.o: in function `secp256k1::key::SecretKey::new':
          /home/jr/.cargo/registry/src/github.com-1ecc6299db9ec823/secp256k1-0.17.2/src/key.rs:(.text._ZN9secp256k13key9SecretKey3new17h018b2c71fe92cf66E+0x33): undefined reference to `rustsecp256k1_v0_1_1_context_no_precomp'
          /usr/bin/ld: /home/jr/.cargo/registry/src/github.com-1ecc6299db9ec823/secp256k1-0.17.2/src/key.rs:118: undefined reference to `rustsecp256k1_v0_1_1_ec_seckey_verify'
          /usr/bin/ld: /home/jr/develop/rust-play/target/debug/examples/channel-4301c293d5c8634b.4qtmhtdl4d2h3x23.rcgu.o: in function `secp256k1::key::PublicKey::serialize':
          /home/jr/.cargo/registry/src/github.com-1ecc6299db9ec823/secp256k1-0.17.2/src/key.rs:257: undefined reference to `rustsecp256k1_v0_1_1_context_no_precomp'
          /usr/bin/ld: /home/jr/.cargo/registry/src/github.com-1ecc6299db9ec823/secp256k1-0.17.2/src/key.rs:262: undefined reference to `rustsecp256k1_v0_1_1_ec_pubkey_serialize'
          collect2: error: ld returned 1 exit status

This poses a challenge for using miniscript from dependent projects :)

Compiling invalid policy "or(pk())" causes "index out of bounds: the len is 1 but the index is 1"

Crash location:

https://github.com/apoelstra/rust-miniscript/blob/2aee5708e3e4f29a4d41301adc998d6b95fc4c76/src/policy/compiler.rs#L835

Compiling invalid policy or(pk()) causes index out of bounds: the len is 1 but the index is 1:

Code:

use miniscript::{policy, DummyKey};
use std::str::FromStr;

type DummyPolicy = policy::Concrete<DummyKey>;

fn main() {
    let policy_string = "or(pk())";
    if let Ok(policy) = DummyPolicy::from_str(&policy_string) {
        if let Ok(_) = policy.compile() {}
    }
}

Output:

thread 'main' panicked at 'index out of bounds: the len is 1 but the index is 1', /rustc/9af17757be1cc3f672928ecf06c40a662c5ec26d/src/libcore/slice/mod.rs:2715:10
stack backtrace:
   0: backtrace::backtrace::libunwind::trace
             at /cargo/registry/src/github.com-1ecc6299db9ec823/backtrace-0.3.35/src/backtrace/libunwind.rs:88
   1: backtrace::backtrace::trace_unsynchronized
             at /cargo/registry/src/github.com-1ecc6299db9ec823/backtrace-0.3.35/src/backtrace/mod.rs:66
   2: std::sys_common::backtrace::_print
             at src/libstd/sys_common/backtrace.rs:47
   3: std::sys_common::backtrace::print
             at src/libstd/sys_common/backtrace.rs:36
   4: std::panicking::default_hook::{{closure}}
             at src/libstd/panicking.rs:200
   5: std::panicking::default_hook
             at src/libstd/panicking.rs:214
   6: std::panicking::rust_panic_with_hook
             at src/libstd/panicking.rs:477
   7: std::panicking::continue_panic_fmt
             at src/libstd/panicking.rs:384
   8: rust_begin_unwind
             at src/libstd/panicking.rs:311
   9: core::panicking::panic_fmt
             at src/libcore/panicking.rs:85
  10: core::panicking::panic_bounds_check
             at src/libcore/panicking.rs:61
  11: <usize as core::slice::SliceIndex<[T]>>::index
             at /rustc/9af17757be1cc3f672928ecf06c40a662c5ec26d/src/libcore/slice/mod.rs:2715
  12: core::slice::<impl core::ops::index::Index<I> for [T]>::index
             at /rustc/9af17757be1cc3f672928ecf06c40a662c5ec26d/src/libcore/slice/mod.rs:2566
  13: <alloc::vec::Vec<T> as core::ops::index::Index<I>>::index
             at /rustc/9af17757be1cc3f672928ecf06c40a662c5ec26d/src/liballoc/vec.rs:1792
  14: miniscript::policy::compiler::best_compilations
             at DIR/.cargo/git/checkouts/rust-miniscript-1175aea50517de2b/8ad6fea/src/policy/compiler.rs:835
  15: miniscript::policy::compiler::best_t
             at DIR/.cargo/git/checkouts/rust-miniscript-1175aea50517de2b/8ad6fea/src/policy/compiler.rs:1102
  16: miniscript::policy::compiler::best_compilation
             at DIR/.cargo/git/checkouts/rust-miniscript-1175aea50517de2b/8ad6fea/src/policy/compiler.rs:1079
  17: miniscript::policy::concrete::Policy<Pk>::compile
             at DIR/.cargo/git/checkouts/rust-miniscript-1175aea50517de2b/8ad6fea/src/policy/concrete.rs:67
  18: […]::main
             at src/main.rs:12
…

Consensus testing of minscripts

#123 brought an interesting point that we should consensus test our miniscript with rust-libbitcoinconsensus.

Create transactions using rust-miniscripts and check the transaction validity/satisfaction logic/weight calculation etc and other features with https://github.com/rust-bitcoin/rust-bitcoinconsensus. We can also grammar that Pieter had to generate random miniscirpts.

Not completely sure of how we are going to do this, but I think we should have this.

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.