---
_id: '6378'
abstract:
- lang: eng
  text: 'In today''s cryptocurrencies, Hashcash proof of work is the most commonly-adopted
    approach to mining. In Hashcash, when a miner decides to add a block to the chain,
    she has to solve the difficult computational puzzle of inverting a hash function.
    While Hashcash has been successfully adopted in both Bitcoin and Ethereum, it
    has attracted significant and harsh criticism due to its massive waste of electricity,
    its carbon footprint and environmental effects, and the inherent lack of usefulness
    in inverting a hash function. Various other mining protocols have been suggested,
    including proof of stake, in which a miner''s chance of adding the next block
    is proportional to her current balance. However, such protocols lead to a higher
    entry cost for new miners who might not still have any stake in the cryptocurrency,
    and can in the worst case lead to an oligopoly, where the rich have complete control
    over mining. In this paper, we propose Hybrid Mining: a new mining protocol that
    combines solving real-world useful problems with Hashcash. Our protocol allows
    new miners to join the network by taking part in Hashcash mining without having
    to own an initial stake. It also allows nodes of the network to submit hard computational
    problems whose solutions are of interest in the real world, e.g.~protein folding
    problems. Then, miners can choose to compete in solving these problems, in lieu
    of Hashcash, for adding a new block. Hence, Hybrid Mining incentivizes miners
    to solve useful problems, such as hard computational problems arising in biology,
    in a distributed manner. It also gives researchers in other areas an easy-to-use
    tool to outsource their hard computations to the blockchain network, which has
    enormous computational power, by paying a reward to the miner who solves the problem
    for them. Moreover, our protocol provides strong security guarantees and is at
    least as resilient to double spending as Bitcoin.'
article_processing_charge: No
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Amir Kafshdar
  full_name: Goharshady, Amir Kafshdar
  id: 391365CE-F248-11E8-B48F-1D18A9856A87
  last_name: Goharshady
  orcid: 0000-0003-1702-6584
- first_name: Arash
  full_name: Pourdamghani, Arash
  last_name: Pourdamghani
citation:
  ama: 'Chatterjee K, Goharshady AK, Pourdamghani A. Hybrid Mining: Exploiting blockchain’s
    computational power for distributed problem solving. In: <i>Proceedings of the
    34th ACM Symposium on Applied Computing</i>. Vol Part F147772. ACM; 2019:374-381.
    doi:<a href="https://doi.org/10.1145/3297280.3297319">10.1145/3297280.3297319</a>'
  apa: 'Chatterjee, K., Goharshady, A. K., &#38; Pourdamghani, A. (2019). Hybrid Mining:
    Exploiting blockchain’s computational power for distributed problem solving. In
    <i>Proceedings of the 34th ACM Symposium on Applied Computing</i> (Vol. Part F147772,
    pp. 374–381). Limassol, Cyprus: ACM. <a href="https://doi.org/10.1145/3297280.3297319">https://doi.org/10.1145/3297280.3297319</a>'
  chicago: 'Chatterjee, Krishnendu, Amir Kafshdar Goharshady, and Arash Pourdamghani.
    “Hybrid Mining: Exploiting Blockchain’s Computational Power for Distributed Problem
    Solving.” In <i>Proceedings of the 34th ACM Symposium on Applied Computing</i>,
    Part F147772:374–81. ACM, 2019. <a href="https://doi.org/10.1145/3297280.3297319">https://doi.org/10.1145/3297280.3297319</a>.'
  ieee: 'K. Chatterjee, A. K. Goharshady, and A. Pourdamghani, “Hybrid Mining: Exploiting
    blockchain’s computational power for distributed problem solving,” in <i>Proceedings
    of the 34th ACM Symposium on Applied Computing</i>, Limassol, Cyprus, 2019, vol.
    Part F147772, pp. 374–381.'
  ista: 'Chatterjee K, Goharshady AK, Pourdamghani A. 2019. Hybrid Mining: Exploiting
    blockchain’s computational power for distributed problem solving. Proceedings
    of the 34th ACM Symposium on Applied Computing. ACM Symposium on Applied Computing
    vol. Part F147772, 374–381.'
  mla: 'Chatterjee, Krishnendu, et al. “Hybrid Mining: Exploiting Blockchain’s Computational
    Power for Distributed Problem Solving.” <i>Proceedings of the 34th ACM Symposium
    on Applied Computing</i>, vol. Part F147772, ACM, 2019, pp. 374–81, doi:<a href="https://doi.org/10.1145/3297280.3297319">10.1145/3297280.3297319</a>.'
  short: K. Chatterjee, A.K. Goharshady, A. Pourdamghani, in:, Proceedings of the
    34th ACM Symposium on Applied Computing, ACM, 2019, pp. 374–381.
conference:
  end_date: 2019-04-12
  location: Limassol, Cyprus
  name: ACM Symposium on Applied Computing
  start_date: 2019-04-08
date_created: 2019-05-06T12:11:36Z
date_published: 2019-04-01T00:00:00Z
date_updated: 2025-06-02T08:53:46Z
day: '01'
ddc:
- '004'
department:
- _id: KrCh
doi: 10.1145/3297280.3297319
ec_funded: 1
external_id:
  isi:
  - '000474685800049'
file:
- access_level: open_access
  checksum: fbfbcd5a0c7a743862bfc3045539a614
  content_type: application/pdf
  creator: dernst
  date_created: 2019-05-06T12:09:27Z
  date_updated: 2020-07-14T12:47:29Z
  file_id: '6379'
  file_name: 2019_ACM_Chatterjee.pdf
  file_size: 1023934
  relation: main_file
file_date_updated: 2020-07-14T12:47:29Z
has_accepted_license: '1'
isi: 1
language:
- iso: eng
month: '04'
oa: 1
oa_version: Submitted Version
page: 374-381
project:
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '279307'
  name: 'Quantitative Graph Games: Theory and Applications'
- _id: 25892FC0-B435-11E9-9278-68D0E5697425
  grant_number: ICT15-003
  name: Efficient Algorithms for Computer Aided Verification
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S 11407_N23
  name: Rigorous Systems Engineering
publication: Proceedings of the 34th ACM Symposium on Applied Computing
publication_identifier:
  isbn:
  - '9781450359337'
publication_status: published
publisher: ACM
pubrep_id: '1069'
quality_controlled: '1'
related_material:
  record:
  - id: '8934'
    relation: dissertation_contains
    status: public
scopus_import: '1'
status: public
title: 'Hybrid Mining: Exploiting blockchain’s computational power for distributed
  problem solving'
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: Part F147772
year: '2019'
...
---
_id: '6490'
abstract:
- lang: eng
  text: "Smart contracts are programs that are stored and executed on the Blockchain
    and can receive, manage and transfer money (cryptocurrency units). Two important
    problems regarding smart contracts are formal analysis and compiler optimization.
    Formal analysis is extremely important, because smart contracts hold funds worth
    billions of dollars and their code is immutable after deployment. Hence, an undetected
    bug can cause significant financial losses. Compiler optimization is also crucial,
    because every action of a smart contract has to be executed by every node in the
    Blockchain network. Therefore, optimizations in compiling smart contracts can
    lead to significant savings in computation, time and energy.\r\n\r\nTwo classical
    approaches in program analysis and compiler optimization are intraprocedural and
    interprocedural analysis. In intraprocedural analysis, each function is analyzed
    separately, while interprocedural analysis considers the entire program. In both
    cases, the analyses are usually reduced to graph problems over the control flow
    graph (CFG) of the program. These graph problems are often computationally expensive.
    Hence, there has been ample research on exploiting structural properties of CFGs
    for efficient algorithms. One such well-studied property is the treewidth, which
    is a measure of tree-likeness of graphs. It is known that intraprocedural CFGs
    of structured programs have treewidth at most 6, whereas the interprocedural treewidth
    cannot be bounded. This result has been used as a basis for many efficient intraprocedural
    analyses.\r\n\r\nIn this paper, we explore the idea of exploiting the treewidth
    of smart contracts for formal analysis and compiler optimization. First, similar
    to classical programs, we show that the intraprocedural treewidth of structured
    Solidity and Vyper smart contracts is at most 9. Second, for global analysis,
    we prove that the interprocedural treewidth of structured smart contracts is bounded
    by 10 and, in sharp contrast with classical programs, treewidth-based algorithms
    can be easily applied for interprocedural analysis. Finally, we supplement our
    theoretical results with experiments using a tool we implemented for computing
    treewidth of smart contracts and show that the treewidth is much lower in practice.
    We use 36,764 real-world Ethereum smart contracts as benchmarks and find that
    they have an average treewidth of at most 3.35 for the intraprocedural case and
    3.65 for the interprocedural case.\r\n"
article_processing_charge: No
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Amir Kafshdar
  full_name: Goharshady, Amir Kafshdar
  id: 391365CE-F248-11E8-B48F-1D18A9856A87
  last_name: Goharshady
  orcid: 0000-0003-1702-6584
- first_name: Ehsan Kafshdar
  full_name: Goharshady, Ehsan Kafshdar
  last_name: Goharshady
citation:
  ama: 'Chatterjee K, Goharshady AK, Goharshady EK. The treewidth of smart contracts.
    In: <i>Proceedings of the 34th ACM Symposium on Applied Computing</i>. Vol Part
    F147772. ACM; :400-408. doi:<a href="https://doi.org/10.1145/3297280.3297322">10.1145/3297280.3297322</a>'
  apa: 'Chatterjee, K., Goharshady, A. K., &#38; Goharshady, E. K. (n.d.). The treewidth
    of smart contracts. In <i>Proceedings of the 34th ACM Symposium on Applied Computing</i>
    (Vol. Part F147772, pp. 400–408). Limassol, Cyprus: ACM. <a href="https://doi.org/10.1145/3297280.3297322">https://doi.org/10.1145/3297280.3297322</a>'
  chicago: Chatterjee, Krishnendu, Amir Kafshdar Goharshady, and Ehsan Kafshdar Goharshady.
    “The Treewidth of Smart Contracts.” In <i>Proceedings of the 34th ACM Symposium
    on Applied Computing</i>, Part F147772:400–408. ACM, n.d. <a href="https://doi.org/10.1145/3297280.3297322">https://doi.org/10.1145/3297280.3297322</a>.
  ieee: K. Chatterjee, A. K. Goharshady, and E. K. Goharshady, “The treewidth of smart
    contracts,” in <i>Proceedings of the 34th ACM Symposium on Applied Computing</i>,
    Limassol, Cyprus, vol. Part F147772, pp. 400–408.
  ista: 'Chatterjee K, Goharshady AK, Goharshady EK. The treewidth of smart contracts.
    Proceedings of the 34th ACM Symposium on Applied Computing. SAC: Symposium on
    Applied Computing vol. Part F147772, 400–408.'
  mla: Chatterjee, Krishnendu, et al. “The Treewidth of Smart Contracts.” <i>Proceedings
    of the 34th ACM Symposium on Applied Computing</i>, vol. Part F147772, ACM, pp.
    400–08, doi:<a href="https://doi.org/10.1145/3297280.3297322">10.1145/3297280.3297322</a>.
  short: K. Chatterjee, A.K. Goharshady, E.K. Goharshady, in:, Proceedings of the
    34th ACM Symposium on Applied Computing, ACM, n.d., pp. 400–408.
conference:
  end_date: 2019-04-12
  location: Limassol, Cyprus
  name: 'SAC: Symposium on Applied Computing'
  start_date: 2019-04-08
date_created: 2019-05-26T21:59:15Z
date_published: 2019-04-01T00:00:00Z
date_updated: 2024-03-25T23:30:18Z
day: '01'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.1145/3297280.3297322
external_id:
  isi:
  - '000474685800052'
file:
- access_level: open_access
  checksum: dddc20f6d9881f23b8755eb720ec9d6f
  content_type: application/pdf
  creator: dernst
  date_created: 2020-05-14T09:50:11Z
  date_updated: 2020-07-14T12:47:32Z
  file_id: '7827'
  file_name: 2019_ACM_Chatterjee.pdf
  file_size: 6937138
  relation: main_file
file_date_updated: 2020-07-14T12:47:32Z
has_accepted_license: '1'
isi: 1
language:
- iso: eng
month: '04'
oa: 1
oa_version: Submitted Version
page: 400-408
publication: Proceedings of the 34th ACM Symposium on Applied Computing
publication_identifier:
  isbn:
  - '9781450359337'
publication_status: submitted
publisher: ACM
pubrep_id: '1070'
quality_controlled: '1'
related_material:
  record:
  - id: '8934'
    relation: dissertation_contains
    status: public
scopus_import: '1'
status: public
title: The treewidth of smart contracts
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: Part F147772
year: '2019'
...