On Some Approaches to the Solution of the “Useful Proof-of-Work for Blockchains” Task View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2018-12

AUTHORS

V. G. Durnev, D. M. Murin, V. A. Sokolov, D. Ju. Chalyy

ABSTRACT

The blockchain technology is based on the “proof-of-work” principles. The essence of this principle is that some event (for example the bill-to-bill money transaction) becomes significant after the confirmation by certain computer work. So, a demand arose for such computational problems to work on, and we will spend for it about the whole blockchain system computing capacity. Now the main class of such problems is a “hash-puzzle” – the problem to find a bit string with a hash that satisfies some conditions. The major hash-puzzle weakness is the lack of the useful application outside of the blockchain technology. In this work, we offer some approaches to the “Useful Proof-of-work for blockchains” task, namely, we consider some practical variants of the NP-complete problems (tasks) that could be solved with the help of SAT-solvers as the proof-of-work computational problems. The use of the FPT-problems requires special study. The approach offered allows to provide the following characteristics of the proof-of-work computational problems: usefulness, problems complexity management (through the dimension change, choosing problems of certain type, the indication of necessary solution precision), mass character. Herewith we admit that not every solved task can be useful but we consider the opportunity to solve some practical tasks with the help of the blockchain technology. Among other things it is also possible to compare the virtual crypto-currency value (through the energy costs spent) and the effective result of the practical problems solution. The most complicated points of the described approach are the realization of the events-tasks (providing the computer work for these events) relations and the realization of the tasks complexity analysis system. This issue should be viewed as a research program because of many technical details that must be worked out further. More... »

PAGES

880-884

References to SciGraph publications

  • 1999. Parameterized Complexity in NONE
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.3103/s0146411618070337

    DOI

    http://dx.doi.org/10.3103/s0146411618070337

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1112534973


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Yaroslavl State University", 
              "id": "https://www.grid.ac/institutes/grid.99921.3a", 
              "name": [
                "Demidov Yaroslavl State University, 150003, Yaroslavl, Russia"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Durnev", 
            "givenName": "V. G.", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Yaroslavl State University", 
              "id": "https://www.grid.ac/institutes/grid.99921.3a", 
              "name": [
                "Demidov Yaroslavl State University, 150003, Yaroslavl, Russia"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Murin", 
            "givenName": "D. M.", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Yaroslavl State University", 
              "id": "https://www.grid.ac/institutes/grid.99921.3a", 
              "name": [
                "Demidov Yaroslavl State University, 150003, Yaroslavl, Russia"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Sokolov", 
            "givenName": "V. A.", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Yaroslavl State University", 
              "id": "https://www.grid.ac/institutes/grid.99921.3a", 
              "name": [
                "Demidov Yaroslavl State University, 150003, Yaroslavl, Russia"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Chalyy", 
            "givenName": "D. Ju.", 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://app.dimensions.ai/details/publication/pub.1050354225", 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4612-0515-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050354225", 
              "https://doi.org/10.1007/978-1-4612-0515-9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4612-0515-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050354225", 
              "https://doi.org/10.1007/978-1-4612-0515-9"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2018-12", 
        "datePublishedReg": "2018-12-01", 
        "description": "The blockchain technology is based on the \u201cproof-of-work\u201d principles. The essence of this principle is that some event (for example the bill-to-bill money transaction) becomes significant after the confirmation by certain computer work. So, a demand arose for such computational problems to work on, and we will spend for it about the whole blockchain system computing capacity. Now the main class of such problems is a \u201chash-puzzle\u201d \u2013 the problem to find a bit string with a hash that satisfies some conditions. The major hash-puzzle weakness is the lack of the useful application outside of the blockchain technology. In this work, we offer some approaches to the \u201cUseful Proof-of-work for blockchains\u201d task, namely, we consider some practical variants of the NP-complete problems (tasks) that could be solved with the help of SAT-solvers as the proof-of-work computational problems. The use of the FPT-problems requires special study. The approach offered allows to provide the following characteristics of the proof-of-work computational problems: usefulness, problems complexity management (through the dimension change, choosing problems of certain type, the indication of necessary solution precision), mass character. Herewith we admit that not every solved task can be useful but we consider the opportunity to solve some practical tasks with the help of the blockchain technology. Among other things it is also possible to compare the virtual crypto-currency value (through the energy costs spent) and the effective result of the practical problems solution. The most complicated points of the described approach are the realization of the events-tasks (providing the computer work for these events) relations and the realization of the tasks complexity analysis system. This issue should be viewed as a research program because of many technical details that must be worked out further.", 
        "genre": "research_article", 
        "id": "sg:pub.10.3103/s0146411618070337", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1136763", 
            "issn": [
              "0146-4116", 
              "1558-108X"
            ], 
            "name": "Automatic Control and Computer Sciences", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "7", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "52"
          }
        ], 
        "name": "On Some Approaches to the Solution of the \u201cUseful Proof-of-Work for Blockchains\u201d Task", 
        "pagination": "880-884", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "326704c9c15732ea7f9f710359489d9c193079bd486277c4e6256a0500c087eb"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.3103/s0146411618070337"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1112534973"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.3103/s0146411618070337", 
          "https://app.dimensions.ai/details/publication/pub.1112534973"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T11:01", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000352_0000000352/records_60347_00000004.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://link.springer.com/10.3103%2FS0146411618070337"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.3103/s0146411618070337'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.3103/s0146411618070337'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.3103/s0146411618070337'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.3103/s0146411618070337'


     

    This table displays all metadata directly associated to this object as RDF triples.

    84 TRIPLES      21 PREDICATES      29 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.3103/s0146411618070337 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N0f569db6f37044fd897f7335b801d4b6
    4 schema:citation sg:pub.10.1007/978-1-4612-0515-9
    5 https://app.dimensions.ai/details/publication/pub.1050354225
    6 schema:datePublished 2018-12
    7 schema:datePublishedReg 2018-12-01
    8 schema:description The blockchain technology is based on the “proof-of-work” principles. The essence of this principle is that some event (for example the bill-to-bill money transaction) becomes significant after the confirmation by certain computer work. So, a demand arose for such computational problems to work on, and we will spend for it about the whole blockchain system computing capacity. Now the main class of such problems is a “hash-puzzle” – the problem to find a bit string with a hash that satisfies some conditions. The major hash-puzzle weakness is the lack of the useful application outside of the blockchain technology. In this work, we offer some approaches to the “Useful Proof-of-work for blockchains” task, namely, we consider some practical variants of the NP-complete problems (tasks) that could be solved with the help of SAT-solvers as the proof-of-work computational problems. The use of the FPT-problems requires special study. The approach offered allows to provide the following characteristics of the proof-of-work computational problems: usefulness, problems complexity management (through the dimension change, choosing problems of certain type, the indication of necessary solution precision), mass character. Herewith we admit that not every solved task can be useful but we consider the opportunity to solve some practical tasks with the help of the blockchain technology. Among other things it is also possible to compare the virtual crypto-currency value (through the energy costs spent) and the effective result of the practical problems solution. The most complicated points of the described approach are the realization of the events-tasks (providing the computer work for these events) relations and the realization of the tasks complexity analysis system. This issue should be viewed as a research program because of many technical details that must be worked out further.
    9 schema:genre research_article
    10 schema:inLanguage en
    11 schema:isAccessibleForFree false
    12 schema:isPartOf N63249c01c5964a8bb7dbad47f7dad071
    13 N89649b56ef8547759682cc10295b2f23
    14 sg:journal.1136763
    15 schema:name On Some Approaches to the Solution of the “Useful Proof-of-Work for Blockchains” Task
    16 schema:pagination 880-884
    17 schema:productId N17159c7952e74a348e752a5b0269062f
    18 N1e73bed4d4bd49339055552f3f0a3754
    19 Nbcff502693ee40078d14cf95277ec271
    20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1112534973
    21 https://doi.org/10.3103/s0146411618070337
    22 schema:sdDatePublished 2019-04-11T11:01
    23 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    24 schema:sdPublisher Nd614229e1e06474890e51989aa65b27e
    25 schema:url https://link.springer.com/10.3103%2FS0146411618070337
    26 sgo:license sg:explorer/license/
    27 sgo:sdDataset articles
    28 rdf:type schema:ScholarlyArticle
    29 N0f569db6f37044fd897f7335b801d4b6 rdf:first Nf1ce93de0f5a4ceb8fb4b59cb47dcaf6
    30 rdf:rest N738174a7d0714433ad067458c656075d
    31 N17159c7952e74a348e752a5b0269062f schema:name dimensions_id
    32 schema:value pub.1112534973
    33 rdf:type schema:PropertyValue
    34 N1e73bed4d4bd49339055552f3f0a3754 schema:name readcube_id
    35 schema:value 326704c9c15732ea7f9f710359489d9c193079bd486277c4e6256a0500c087eb
    36 rdf:type schema:PropertyValue
    37 N53cf04e3fa3b4db18adebf7eb829824f schema:affiliation https://www.grid.ac/institutes/grid.99921.3a
    38 schema:familyName Chalyy
    39 schema:givenName D. Ju.
    40 rdf:type schema:Person
    41 N63249c01c5964a8bb7dbad47f7dad071 schema:volumeNumber 52
    42 rdf:type schema:PublicationVolume
    43 N738174a7d0714433ad067458c656075d rdf:first Nba8ae9f2488b4db4a7617f302576e2c0
    44 rdf:rest N8d1904e2125a4755b7c6c875994d7860
    45 N89649b56ef8547759682cc10295b2f23 schema:issueNumber 7
    46 rdf:type schema:PublicationIssue
    47 N8d1904e2125a4755b7c6c875994d7860 rdf:first Ne43d315c759d4deca33994f4b1ea27de
    48 rdf:rest Ne103ca3b6aa1490ab881cee8837e7693
    49 Nba8ae9f2488b4db4a7617f302576e2c0 schema:affiliation https://www.grid.ac/institutes/grid.99921.3a
    50 schema:familyName Murin
    51 schema:givenName D. M.
    52 rdf:type schema:Person
    53 Nbcff502693ee40078d14cf95277ec271 schema:name doi
    54 schema:value 10.3103/s0146411618070337
    55 rdf:type schema:PropertyValue
    56 Nd614229e1e06474890e51989aa65b27e schema:name Springer Nature - SN SciGraph project
    57 rdf:type schema:Organization
    58 Ne103ca3b6aa1490ab881cee8837e7693 rdf:first N53cf04e3fa3b4db18adebf7eb829824f
    59 rdf:rest rdf:nil
    60 Ne43d315c759d4deca33994f4b1ea27de schema:affiliation https://www.grid.ac/institutes/grid.99921.3a
    61 schema:familyName Sokolov
    62 schema:givenName V. A.
    63 rdf:type schema:Person
    64 Nf1ce93de0f5a4ceb8fb4b59cb47dcaf6 schema:affiliation https://www.grid.ac/institutes/grid.99921.3a
    65 schema:familyName Durnev
    66 schema:givenName V. G.
    67 rdf:type schema:Person
    68 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    69 schema:name Information and Computing Sciences
    70 rdf:type schema:DefinedTerm
    71 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    72 schema:name Computation Theory and Mathematics
    73 rdf:type schema:DefinedTerm
    74 sg:journal.1136763 schema:issn 0146-4116
    75 1558-108X
    76 schema:name Automatic Control and Computer Sciences
    77 rdf:type schema:Periodical
    78 sg:pub.10.1007/978-1-4612-0515-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050354225
    79 https://doi.org/10.1007/978-1-4612-0515-9
    80 rdf:type schema:CreativeWork
    81 https://app.dimensions.ai/details/publication/pub.1050354225 schema:CreativeWork
    82 https://www.grid.ac/institutes/grid.99921.3a schema:alternateName Yaroslavl State University
    83 schema:name Demidov Yaroslavl State University, 150003, Yaroslavl, Russia
    84 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...